Козлов В.Н. Системный анализ и принятие решений

где

1S +

U

– матрица, обратная для базисной матрицы на (1)s

+

-й

итерации симплекс-метода. Введем в последнее о

, умножив на нее обе части последнего я.

а по

равенств

уравнениматрицу

S

U

Тогд лучим

11SS S++S

=

UP U U

.

(10)

Рассмотрим структуру матрицы

1S

+

P

, выделив в ней столбцы:

m



11

... ...

Sk

⎡

⎤

1

l

s

=

⎢

⎥

⎢

⎥

+

⎣

⎦

PAAA

+

,

причем для данной матрицы на месте -го столбца

(соответствующего переменной выводимо из зиса) должен

быть расположен вектор

l

бай

k

A

.

Тогда соотношение (10) в развернутой форме примет вид:

=

,

который можно преобразовать к эквивалентной форме:

S

.

оскольку =

11 1SS S S++

⎡⎤

=UP U U A



1

... ...

k m S S

l

+

⎢⎥

⎣⎦

A A U U

1s+



11

... ...

SSkSmS

l

+

⎡⎤

=

⎢⎥

⎣⎦

UA UA UA U U

S

U

1

s

−

P

да, а

П - обратная базисная матрица на s-й итерации

симплек - столбцы матрицы , то справедливы

соотношения:

лученные соотношения в преобразованной форме

S

с-мето

S

j

A

P

i

UA e UA e UA x

11 1

,..., , , ( ,..., )

T

SSiSSkkmkk

iB x x==∈ = =.

Рассмотрим по

11

[ ,..., ,..., )

kmS+

=

exeU U

,

71

которую можно представить в «развернутом» виде сле

разом:

1

2

m

S

m

S

⎥

⎦

Выполнив умножение й строки на й столбец и й строки на

й столбец, получим равенства:

.

в атной базисной матрицы:

дующим

об

111SSSS+++

⎤

1111

111

2212

111

1

111

1

11 1 1

21 2

10 0

01 0

0

00 1

kl

SSS

kl

SSS

lk l ll lm

SSS

mk m ml mm

SSS

lm

S

x uuu

uuu

uu

+++

⎡⎤⎡

⎢⎥⎢

⎢

=

⎢⎥⎢

⎣⎦⎣

…… ……

……………… ……………

…… ……

……

…

2

1

.

SS

lm

SSS

llllm

SSS

mmlmm

u

uuu

⎡⎤

⎢⎥

⎣⎦

…

……………

……

……………

……

⎥⎢⎥

……………… ……………

00

i - j -

l

-

l -

11 1

,,

S S SS SS S

ij ij ik lj lk lj lj

u u xu i l xu u

++ +

=+ ≠ =

Из последних формул следуют рекуррентные соотношения для

ычисления элементов новой обр

11

,

SS

lj lj

SSS S

ij ij ik lj

SS

lk lk

u

uux u

u

x

++

=+ = . (11)

ме ия

на выведенных выше соотношений.

мулировка задачи линейн ния в

канонической форме на основе

метода искусственного базиса так,

чтобы в матрице ограничений существовала единичная базисная

7.

Алгоритм симплекс-метода. Алгоритм симплекс-

тода формулируется для задачи линейного программирован

основе

Шаг 1. Фор ого программирова

72

м

с

ичений обеспечивать

суще

с

у

м

типа (5.б):

атрица. Для этого необходимо дополнить матрицу ограничений

единичными столбцами, которые должны в совокупности

исходными столбцами матрицы огран

ствование единичной базисной матрицы. При этом

естественным образом должны быть введены соответствующие

искусственные переменные, которые включаются в целевую

функцию с большими положительными весовыми коэффициентами

для задачи на минимум. В результате запишем и ходную матрицу

ограничений

1

[ ,... ]

n

=AA

в имплекс-таблицу 2.1, а

коэффициенты левой функции

1

,...,

n

CC

запишем в строк этой

таблицы. В табл. 2.1 также включим компоненты исходного

базисного решения, определяе ого вектором

0

B

x .

Шаг 2. Вычисление характеристических разностей (оценок)

по формулам

1S

jj

C

−

, A

це

js

Δ

=−

и запись оценок в

(1)m + -ю строку симплекс-таблицы

Шаг З. Вычисление оценки

k

cP A

.

Δ

, удовлетворяющей условию:

max , 0.Δ= Δ Δ>

kjj

j

Если все 0

j

Δ< , то в с ыполнением критерия

мальности (5.в) вектор

S

x

– оп

оответствии с в

опти тимальное решение, и далее

сле –

Шаг 4. Вычисление величины нового базисного решения

дует перейти к шагу 9, иначе к шагу 4.

1

s

k

x

+

из условия (8):

1

0

min[ / ] /

ik

s

SS SS

lkkiikl

x

xx xx

+

.

Шаг 5. Вычисление компонент нового

>

==

базисного решения

1

s

+

x п

.

о формулам типа (9):

11 11

11

,,,;0,0,

SSSS S S

kikik S l j S

lBxxxxiBikx x j

++ ++

++

∉=− ∈ ≠ = =

73

Шаг 6. Вычисление элементов ново симплекс-таблицы

(s+1)-й итерации метода по формулам:

.

й для

11

/,

SSSSS SSS

ij ij ik lj lk

; /

lj lj lk

x

xxxx

++

=− ilx xx≠ =

11

,,

SS

lj lj

SSS S

ij ij ik lj

SS

uu

uux ilu

lk lk

x

++

=+ ≠ =.

Шаг 7. Корректировка симплекс-таблицы с учетом изменений

коэффициентов целевой функции, соответст ющих новому

базисному решению и формируем табл. 2.2.

Шаг 8. Переход к шагу 2.

Шаг 9. Останов, фиксация решения.

Сформулированный алгоритм определяет конечную

по ения оптимального решения.

Эта формула была выведена выше.

ву

следовательность шагов для вычисл

Пример. Имеется объект управления, для которого в

стационарных состояниях связь между управлениями

i

u

, и

выходными координатами

j

s

определяется

алг

линейной

ебраической системой:

1

10

s

⎛⎞

2

1

3

2

4

21

11

s

u

s

u

s

⎛⎞

⎜⎟

=

⎜⎟

01

⎜⎟

⎝⎠

⎜⎟

⎝⎠

О еспечивающие максимум критерия

оптима ьности , при условии: выходные координаты

статического ления

.

пределим управления, об

л

12

42zu u=+

объекта управ

i

s

принадлежат заданной

допустимой ределенной системой условий:

.

области

D , оп

12 3 41 2

5, 14, 10, 8, 0, 0ss s suu≤≤ ≤ ≤≥≥

74

Таблица 2.1

1 2

C

…

m

C

1m

C

+

…

C

k

C

№

Баз

Сто

исные

лбцы

s

B

Ба

е

S

зисное

решени

X

1

A

2

A

m

A

m+

A

……

1

k

A

1

A

S

c

S

1 1

x

1 0

…

0

s

X

1, 1

m+

…

1,

s

k

X

2

A

2

S

c

2

S

x

0 1

…

0

2,

m

X

s

2

1+

…

2,

s

k

X



l

A

S

l

c

S

l

x

0 0

…

0

…

,1

s

lm

X

+

,

s

lk

X

          

m

A

S

m

c

S

m

x

0 0

… …

1

,1

s

mm

X

+

,

s

mk

X

…

m

Δ

1m

Δ

+1

Δ

2

Δ

Оценки

…

k

Δ

Таблица 2.2

… …

1

c

2

c

m

c

1m

c

+

k

c

Базисное

решение

… …

1S +

X

1

A

2

A

m

A

1m+

A

k

A

№

Базисные

столбцы

1

s

B

+

1

A

1 S

1

S

c

+ 1

1

x

+

1 1 0

…

0

…

1, 1

s

m

X

+ 1,

s

k

X

2

A

1

2

S

c

+ 1

2

S

x

+

0 1

…

0 2

2, 1

m

+

…

s

X

2,

s

k

X

          

l

A

1S

k

c

+ 1S

k

x

+

0 0

…

0

…

,1

s

lm

X

+ ,

s

lk

X

          

m

A

1S

m

c

+ 1S

m

x

+

0 0

…

1

…

,1

s

mm

X

+ ,

s

mk

X

…

m

Δ

1m

Δ

+1

Δ

2

Δ

…

k

Δ

Оценки

75

Сформулированная задача сводится определению максимума

линейного функционала

к

12

42zu u

=

+

при ограничениях:

2

≤

з

2

1

5,u≤

12 1

12 2

8,

2 14, 0,

10, 0.

u

uu u

+≤ ≥

Решение. Приведем адачу к каноническому виду, введя

обозначения

,uxu

112

x

=

лучим: . Тогда по

функция примет

6

x

13

124

126

5,

214,

10,

xx

xxx

+=

++=

27

8, 0, 1,...,6.

j

xx x j+= ≥ =

Тогда целевая вид:

12345

420 0 0 0zxxxxx

=

++⋅+⋅+⋅++⋅

.

Систему ограничений можно переписать в векторной форме:

B

или

11 2 2 6 6

...xx x+++=AA A

=

Ax B ,

где векторы и матрицы ограничений задачи определены

с

ледующими равенствами:

123456

(, , , , , )

T

x

xxxxx=x

2

3

; ; ;

;

(5,14,10, 8)

T

=B

4

2

(0,0,0,1)

1

(0,1,1,1)=A

; (1,0,0,0)

T

=A ; (0,1,0,0)

T

=A ; (0,0,0,1)

T

=A

(1, 2,1, 0)

T

=A

5

=

A

.

П е

р а, когда все оценки

оскольку вычисляется максимум функционала, то оптимально

ешение будет получено тогд

0

j

Δ

≥ . Составим

симплекс-таблицу данной дачи управлени виде табл. 2.3

Таблиц .3

за я в .

а 2

76

4 2 0 0 0 0

I Базис

1

B

1

X

1

A

2

A

3

A

4

A

5

A

6

A

1

3

A

0 5 1 0 1 0 0 0

2 0 14 2 1 0 1 0 0

4

A

3 0 10 1 1 0 0 1 0

5

A

4

6

A

0 8 0 1 0 0 0 1

5 – – – -4 -2 0 0 0 0

Исходный базис сто из , ; у

соответствует решени ,

поскольку коэффициенты ,

то ачение иней го

со ит векторов

3 4

,

A

,x

A

56

)x==

3456

,,c

5

A

,

(0, 0,

,c

рав

6

A

,14,

ем

е

целевой

1 3

( , , , , 10,8)

T

xxxx

функции нулю

функционала

0

2 4

x

cc

5

ны

зн л но

z

=

.

В новый бази вводится в тор, торо соответствует с ек ко му

min

j

Δ такой, что разностью является

1

4

Δ

=−

р

1

A

,

, которой

вектор следовательно, векто необходимо

выводимый

.

На о ктор н о

можно определить новое базисное решение:

. В этом случае значение

j

соответствует

1

A

,

ввести в базис. Чтобы определить вектор, из базиса,

вычислим

min / minxxx===

11

ii

/ 5

kii ii

xu

снове вычислений определяем, что ве е бходимо

вывести из базиса.

Получаем разрешающую строку и столбец (они выделены в

таблице). После преобразования решения по формулам симплекс-

метода

3

A

123456

( , , , , , ,) (5,0,0,4,5,8)

T

xxxx xx==x

линейного функционала

1

20z

=

. Симплексная т лица после

первой итерации им

аб

еет вид, данный в табл. 2.4.

Таблица 2.4

77

4 2 0 0 0 0

i Базис

2

B

2

X

1

A

2

A A

4

A

5

A

6

A

3

1 4 5 1 0

1

A

1 0 0 0

2

A

0 4 1 -2 1 0 0

0

3

A

0 5 0 1 0

5

0 1 0

4 0 8

6

A

0 1 0 0 0 1

5 – – – 0 -2 4 0 0 0

Для ре ени итер оптимальности выполняется,

поскольку среди ений

ш я

2

X

знач

кр ий не

j

Δ

имеются отрицательные. Такой

разностью (оценкой явл ется) я

2

20

Δ

=− <

пре ляе

, , вектор

нужно ввести зис м ком нент вектора

ба сного шени выв имую базиса:

.

дол

ую строку

сто б н е

.

Симплексная таблица второй итерации метода имеет вид,

данный в табл. 2.5.

я р

о

Таблица 2.5

следовательно

в ба .

2

A

О де по у

зи ре я, од из

22

min( / ) min( / ) 4

kii ii

xxx xu===

ii

Определяем, что

4

A

жен быть исключен из базиса.

Определяем вторую разрешающ и новый разрешающий

л ец. Преобразовав решение

2

X

, получим овое решени

123456

( , , , , , ,) (5,4

T

xxxx xx==x

,0,0,1,4)

Очевидно, что дл ешения

3

X

критерий оптимальности

(0)

j

∀Δ > выполняется, следовательно, полученное решение

рассматриваемой задачи является птимальным.

78

4 2 0 0 0 0

I Базис

3

B

3

X

1

A

2

A

3

A

4

A

5

A

6

A

1 0

1

A

4 5 1 1 0 0 0

2

2 4 0 1 -2

A

1 0 0

5

0 1 0 1 1 -1 1 0

A

3

4 0 4 0

6

A

1 2 -1 0 1

5 – – – 0 0 0 2 0 0

Рассмотренный люст руе совокупн ть

о ий чис ний птим ьно баз ного ,

совпадающего с шен задачи линейного программирования.

2.3. Ми ми ия ней х функционалов

на компактных множествах

Рассматриваются два численно аналитического

реше ин и

функцио рующий

линейный функц

пример ил ри т ос

перац для вы ле о ал го ис решения

ре ием

ни зац ли ны

варианта -

ния задачи м имизаци линейного функционала на

компактных множествах.

1. Первый вариант условной минимизации.

Рассматривается следующая задача минимизации линейного

нала: вычислить вектор-аргумент, минимизи

ионал

*

2

,,, ,

arg min . (1

()

mn

Т n

оо o

о Z

Т

AZ b A R m n rang A m

cz R

Z d Q

×

⎧⎫

⎪⎪

=∈ ≤ =

== ∈

⎨⎬

−

⎪

⎩

)

(),

о

z

Z d r rang Q n

ϕ

−≤ =

⎪

⎭

Эллипсоид

па

пе

фо

в данной задаче может аппроксимировать

раллелепипед интервальных ограничений на переменные. Замена

ременных позволяет преобразовать ограничения к следующей

рме:

1/ 2 1/ 2

, (),()()

Т

Z

QXdXQZd ZdQZd

−

=+=− − −

=

79

1/ 2 1/ 2 1/ 2 1/2 2

()()

ТТ

QXddQQXdd XQQQXXXr

−− −−

=+− +−= =≤

,

Т

и преобразовать исходную задачу (1) к виду: вычислить вектор

1/2

*1/2

()

arg min

о

ТТ

оо

AZ A Q X d

XcQXcd

ϕ

−

⎧

1/2

.

ооо

AQ X Ad b

−

=

+=

⎪

==+

⎨

⎪

=+=

⎪

⎩

В новых переменных ограничения задачи принимают вид:

.

1/2 2

{, , , , }

Т n

ооо x

A

X b A A Q b b A d rang A m X X r R

−

== =− = ≤∈

В компактном виде последняя задача сводится к вычислению

минимума линейного функционала при ограничениях:

Необходимы для задачи,

полученной заменой квадратичного неравенства на квадратичное

)

fXcJ

Т

+=

е условия

.rXX,bAX

Т 2

≤=

равенство можно получить с помощью функции Лагранжа:

2

0

()(

ТТ Т

L

cX AX b X X r

λλ

=+ −+ −

.

Необходимые условия представляется системой равенств

02 =++=

∂

XAc

L

T

λλ

,

0

−= =

∂

b

λ

,

AX

L

0

∂x

0

2

=−

∂

=

∂

rXX

T

λ

, (2)

из которых следует:

L

(

)

[

]

Т

АсbАА

о

−−=

−

λλ

2

1

. (3)

ешение преобразованной задачи как функцияР

λ

имеет вид:

()

,

bAAAcP

~

XX

ТТo

**

(

)

AAAAEP

~

ТТo

1−

−=

1−

λ

2

−

==

. (4)

оследнее решение можно представить в форме, определяющей П

80

Козлов В.Н. Системный анализ и принятие решений

Подождите немного. Документ загружается.