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

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Приведем задачу (6.17) к каноническому виду, добавив в каждое из ее
ограничений дополнительную переменную
i
t , mi ,,1 L
=
.
maxcZ
2211
→
+
+
+
=
nn
xcxcx L
;
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=++++
=++++
=++++
).(
)(;
)(;
2211
2222222121
1111212111
mmmnmnmm
nn
nn
ybtxaxaxa
ybtxaxaxa
ybtxaxaxa
L
LLLLLLLLLLLLLLLLLLLLL
L
L
(6.19)
0,,,
21
≥
n
xxx L
;
021
,,,
≥m
ttt L .
Задача, двойственная (6.19)
− это задача (6.18), но условия
неотрицательности
0≥y теперь включаются в систему ограничений,
поэтому условий дополняющей нежесткости всего
mn
+
, они таковы
j
x (
jmmjjj
cyayaya
−
+++ L
2211
) = 0, n
j
,,1 L
=
;
0=
ii
yt , mi ,,1 L= . (6.20)
Если выразить переменную
i
t через переменные
n
xxx ,,,
21
L
,
последние
m условий запишутся так
)(
2211 ininiii
bxaxaxay
−
+++ L = 0, mi ,,1 L
=
. (6.21)
6.5. Двойственный симплекс-метод
Из доказательства второй теоремы двойственности следует, что в
случае выполнения условий дополняющей нежесткости (6.10) для
равенства целевых функций
Z
и W задач (6.3) и (6.4) достаточно, чтобы
вектор
x
был решением системы линейных уравнений
0
AxA = задачи
(6.3). Ограничения
0≥
x
и
cyA
T
≥
могут нарушаться.
При решении задачи (6.3) симплекс-методом идет перебор допустимых
решений задачи (6.3). На всех итерациях, кроме последней, векторы
y =
=
баз
c
1−
B
не являются допустимыми решениями задачи (6.4). Но условия
дополняющей нежесткости выполняются всегда.
Действительно, если
0
>
j
x (т.е.
j
x − базисная переменная), то
j
Δ
= 0. Это означает, что
j
-е
ограничение двойственной задачи превращается в строгое равенство на
векторе
y .
Можно предложить симметричный алгоритм, основанный на переборе
допустимых решений задачи (6.4). Перебор осуществляется с помощью

Страницы