Введение в линейное программирование. Палий И.А. - 31 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

Составители: 

Рубрика: 

maxcZ
2211
→+++=
nn
xcxcx L ;
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=+++
=+++
=+++
).(
)(;
)(;
2211
222222121
111212111
mmnmnmm
nn
nn
ybxaxaxa
ybxaxaxa
ybxaxaxa
L
LLLLLLLLLLLLLLLL
L
L
; (6.1)
0,,,
21
≥
n
xxx L .
Двойственная задача:
min
2211
→+++=
mm
ybybybW L ;
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≥+++
≥+++
≥+++
).(
)(;
)(;
2211
222222112
111221111
nmnmnnn
mm
mm
xyyayaya
xcyayaya
xcyayaya
L
LLLLLLLLLLLLLLLL
L
L
; (6.2)
На переменные
m
yy ,,
1
L
не наложены условия неотрицательности,
так как все ограничения задачи (6.1) − это ограничения-равенства.
Математические модели (6.1) − (6.2) можно записать компактно. Пусть
),,,(
21 n
xxxx L= , ),,,(
21 m
yyyy L
=
; ),,,(
21 n
cccc L
=
;
),,,(
210 m
bbbA L= (
0
A
− вектор-столбец, записанный как строка);
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
mnmm
n
n
aaa
aaa
aaa
A
L
LLLL
L
L
21
22221
11211
⎟
⎟
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎜
⎜
⎝
⎛
=
mnnn
m
m
T
aaa
aaa
aaa
A
L
LLLL
L
L
21
22212
12111
.
Тогда пара двойственных задач запишется так
max),( →=
x
c
Z
;
0
AxA = ; (
x
− здесь вектор-столбец); 0≥
x
. (6.3)
.min;),(
0
cyAyAW
T
≥→= (
y
,
c
− здесь вектор-столбцы) (6.4)
Задача (6.3) − это задача (1); задача (6.4) − задача (2);
−
T
A
транспонированная матрица A.
Пример 3. Симметричная двойственная пара.
max),( →=
x
c
Z
:
0
AxA ≤ ; 0≥
x
(задача (1)).
min),(
0
→= yAW ;
cyA
T
≥
; 0≥y (задача (2)).

Страницы