1.5. Симплексный метод решения задач линейного программирования

Симплексный метод основывается на следующем:

ОДР ЗЛП является выпуклым множеством с конечным числом угловых точек, т.е. многогранником или многоугольным множеством;
оптимальным решением ЗЛП является одна из угловых точек ОДР, если оптимальное решение единственно и не более двух угловых точек ОДР, если оптимальных решений бесконечное множество;
угловые точки ОДР алгебраически представляют некоторые опорные решения системы ограничений задачи (опорные планы).

Данный метод состоит в целенаправленном переборе опорных решений ЗЛП. Он позволяет за конечное число шагов расчета либо найти оптимальное решение, либо установить его отсутствие.

Алгоритм решения злп симплексным методом

Привести ЗЛП к каноническому виду с неотрицательной правой частью.
Найти какой-либо начальный опорный план . Если опорный план отсутствует, то задача не имеет решения вследствие несовместности системы ограничений.
Проверить найденный план на оптимальность, используя оценки заполненной симплексной таблицы.
Если план оптимален, то задача решена.
Если план оптимален, но не единственен, то можно найти еще один оптимальный план.
Если план не оптимален, но имеет место условие неограниченности целевой функции, то задача не имеет решения.
Если пункты 4) – 6) алгоритма не выполняются, найти новый опорный план и перейти к пункту 3).

Нахождение начального опорного плана злп ( )

Пусть система ограничений ЗЛП представлена в канонической форме записи с неотрицательной правой частью.

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части () левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения-равенства – с коэффициентом, равным нулю.

Например, в системе ограничений:

первое и второе ограничения имеют предпочтительный вид, а третье – нет (предпочтительные переменные подчеркнуты).

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

Например, в системе ограничений:

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

Приравниваем свободные переменные к нулю, тогда базисные переменные примут значения:,,.

Получим начальный опорный план .

В случае, когда в каноническом виде с неотрицательной правой частью система ограничений ЗЛП не имеет предпочтительного вида, то начальный опорный план можно найти методом искусственного базиса или методом Жордановых исключений.

Нахождение начального опорного плана злп методом искусственного базиса

В случае, когда ограничение-равенство системы не имеет предпочтительного вида, к его левой части добавляют искусственную переменную . В целевую функцию переменныевводят с коэффициентом «M» в случае решения задачи на минимум и с коэффициентом «–М» в случае решения задачи на максимум, где М – большое (по сравнению с остальными коэффициентами целевой функции) положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.