Файл: 1ЭМММ-Линейное программирование.pdf

необходимость применения методов целенаправленного перебора, которые приводят к решению задачи за приемлемое время. Одним из таких методов является симплекс-метод.

Симплексом называется простейший выпуклый многогранник. Решение задачи ЛП симплекс-методом состоит в

определении одной из вершин многогранника условий и последовательном переходе от одной вершины к другой, причем каждый такой переход приближает решение к оптимальному. В этом заключается геометрический смысл симплекс-метода.

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

Здесь систему ограничений представляет система m линейно независимых уравнений. Эта система линейных уравнений имеет бесконечное число решений. При этом (n-m)

переменных могут принимать произвольные значения (свободные переменные), а остальные m переменных выражаются через них (базисные переменные).

О п р е д е л ен и е 7 . Решение, при котором все свободные переменные равны нулю, называются базисным решением.

Очевидно, что не всякое базисное решение является допустимым, т.е. принадлежит многограннику условий, так как

необходимо учесть последние условия неотрицательности всех

переменных, называется допустимым базисным решением, или опорным планом.

18

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

О п р е д е л ен и е 9 . Опорный план называется невырожденным, если он содержит ровно m положительных компонент, в противном случае, он называется вырожденным.

На каждой грани многогранника условий какая-либо переменная тождественно равна нулю. Например, из (16), (18)

является одной из сторон многогранника условий, соответствует условию xk +i º 0 . Поэтому в каждой вершине многогранника

условий обращаются в нуль ровно столько переменных, сколько свободных. Таким образом, допустимое решение, соответствующее какой-либо вершине многогранника условий, необходимо искать среди множества базисных решений.

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

Первоначально задача ЛП записывается в канонической форме (17), и находится произвольное базисное решение. Если решение недопустимое, то проверяется совместность ограничений, и, в случае совместности, из базиса вычеркивается определенная переменная, а вместо неё вводится другая. Тем самым, находится новое базисное решение. Если же базисное решение допустимое (т.е. найден опорный план, соответствующий одной из вершин многогранника условий), то решение проверяется на оптимальность. В случае неоптимальности допустимого базисного решения, устанавливается ограниченность целевой функции, и вновь

производится обмен между базисными и свободными переменными, который геометрически означает переход к другой вершине многогранника.

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

будет выявлена противоречивость ограничений (несуществование ОДР), либо будет видно, что целевая функция неограничена.

Алгоритм симплекс-метода представлен при помощи блочных структур на рис.7.

19

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

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

20

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com

При решении задачи симплекс-методом удобно пользоваться так называемыми симплекс-таблицами. Приведем

некоторые пояснения к алгоритму нахождения оптимального решения, основанного на последовательных переходах от одной симплекс-таблицы к другой.

П р е д с т а в л ен и е и с х о д н ы х д а н н ы х з а д а ч и в в и д е с и м п л е к с - т а б л и ц ы ( п е р в а я с и м п л е к с - т а б л и ц а ) . Для получения симплекс-таблицы общую или

стандартную задачу ЛП необходимо привести в канонический вид и разрешить систему линейных уравнений (например, методом Гаусса-Жордана) относительно выделенных базисных переменных. Далее, следует при помощи выражений для

базисных переменных выразить целевую функцию через свободные переменные.

При составлении первой симплекс-таблицы на основе разрешенной системы линейных уравнений, свободные члены записываются без изменения знаков, а коэффициенты при свободных переменных - с противоположными знаками. Предположим для определенности, дана стандартная задача ЛП

ввиде (16). Введя дополнительные неотрицательные

Предполагая, что n = k + m и равенство нулю некоторых c j , aij , эту задачу можно записать в виде (17).

Вданном случае удобно в качестве базисных

переменных выбрать xk +1,..., xk +m , относительно которых легко решить систему уравнений. Поэтому из (18) следует

21

PDF создан испытательной версией pdfFactory Pro www.pdffactory.com