Методы оптимизации. Харчистов Б.Ф. - 28 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

28
Для нахождения допустимого базисного решения системы
линейных уравнений может быть применен метод искусственных
переменных, используемый в линейном про г раммировании (ЛП)
для определения начально го базиса. При этом в уравнения систе-
мы (3.7), (3.10), в которых знаки дополнительных переменных
j
v
или
i
w
совпадают со знаками свободных членов, вводятся неот-
рицательные искусственные переменные
nmlllz
l
+≤=
maxmax
,,1,, знаки которых не совпадают со знака-
ми соответствующих свободных членов.
Затем решается вспомо гательная задача ЛП
min )(
→=
∑
l
l
zzF
при о граничениях (3.7)
−
(3.12) с введенными неотрицательными
искусственными переменными. Для решения этой задачи исполь-
зуется симплекс-метод. В процессе решения необходимо учиты-
вать условия дополняющей нежесткости (3.9) и (3.12). Выполне-
ние этих условий означает, что
j
x
и
j
v
,
i
λ
и
i
w
не могу т быть
положительными одновременно, т.е. переменную
j
x
нельзя сде-
лать базисной, если
j
v
является базисной и принимает положи-
тельное значение , также и
i
λ
с
i
w
.
В результате решения вспомогательной задачи могу т быть
два случая.
1. ,0)(min
=zF
z
т.е. все искусственные переменные выве-
дены из базиса. Полученное оптим ально е допустимое базисное
решение вспомогательной задачи ЛП является до пустимым ба-
зисным решением системы (3.7)
−
(3.12) и, следовательно, ре-
шением задачи КП.
2. ,0)(min
>zF
z
т.е. среди базисных остались искусствен-
ные переменные. Это означает, что система (3.7)
−
(3.12) не имеет
допустимого базисного решения и, следовательно, задача КП не
имеет решения.
Итак, алгоритм решения задачи КП заключается в сле-

Страницы