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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

На второй итерации базисные переменные − это переменные,
1
x
и
2
x
,
тогда
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
11
05
2
B
,
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
=
−
12,0
02,0
1
2
B
;
баз2
c = (8; 1);
2
Δ
= (0; 0; 2,4; −0,2);
2
y =
баз2
c
1
2
−
B
= (1,4; 1) =
);(
2233
cc
+
Δ
+
Δ
= (2,4 − 1; 0 + 1).
На векторе
2
y
= (1,4; 1) не удовлетворяется четвертое ограничение
двойственной задачи, так как 02,0
4
<
−
=
Δ
. В части III табл. 6.2 записано
оптимальное решение. Имеем
баз3
c
= (8, 6);
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
6,11
35
3
B
;
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
−
−
=
−
12,0
6,032,0
1
3
B
;
3
Δ
= (0; 0,2; 2,36; 0;);
3
y
=
баз3
c
1
3
−
B
= (1,36; 1,2) =
);(
2233
cc
+
Δ
+
Δ
= (2,36 − 1; 1,2 + 0).
Все оценки неотрицательны,
3
y
− оптимальное решение двойственной
задачи.
maxmin
2,252,1436,115 ZW
=
=
×+
×
=
.
6.4.2. Теорема 3 (вторая теорема двойственности).
Объединяя утверждения из 6.4.1 (следствие 1) и 6.4.2, получаем, что
допустимые решения
),,,(
21 n
xxxx L=
и
),,,(
21 m
yyyy L
=
пары
двойственных задач оптимальны тогда и только тогда
, когда значения
целевых функции Z и W на этих решениях совпадают.
min0max
),(),( WyAxcZ === (6.9)
Необходимое и достаточное условие оптимальности допустимых
решений
x
и y можно записать в виде совокупности равенств. Пусть
),(),(
0
yAxc = . Тогда 0),(),(
0
=− yAxc . В силу допустимости векторов
x
, y (
0
AxA = ; 0≥
x
;
0≥− cyA
T
) можно записать такую цепочку
равенств:
=− ),(),(
0
yAxc ),(
x
c − ),( y
x
= ),(
x
c −
),( xyA
T
=
),( xcyA
T
+−=
),( xcyA
T
−=
= 0.
Скалярное произведение
∑
=
n
i
ii
ba
1
неотрицательных векторов
),,(
1 n
aaa L= и
),,(
1 n
bbb L=
равно нулю тогда и только тогда, когда
каждое слагаемое
ii
ba
равно нулю. Векторы
x
и
cyA
T
−
неотрицательны;
j
-я компонента вектора
cyA
T
−
− это разность между значениями левой
и правой части
j
-го ограничения задачи (6.4), она равна выражению

Страницы