СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Рассмотренный выше графический метод решения ЗЛП применим к задачам весьма узкого класса. Универсальным методом решения ЗЛП является симплексный метод (или метод последовательного улучшения плана).

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

Пусть ЗЛП записана в следующем виде

Предположим, что система ограничений (24) совместна в области неотрицательных значений переменных (25) и ранг системы равен r (причем r<n).

Идея метода. Симплексный метод решения ЗЛП основан на переходе отодного опорного плана к другому, где значение целевой функции является более оптимальным, чем в предыдущем опорном плане. С точки зрения геометрии симплексные процедуры можно трактовать как последовательный, целенаправленный переход по ребрам выпуклого многогранника допустимых планов W от одной его вершины к другой (соседней), где значение целевой функции более оптимально, чем в предыдущей вершине.

Симплексный метод решения складывается из двух этапов:

1. Определяется какой-либо первоначальный опорный план .

2. По специальным правилам осуществляется переход

, пока не будет найдено оптимальное значение (opt) линейной формы. Opt линейной формы будет доставлять опорный план .

ОПТИМАЛЬНЫЙ ПЛАН ЗЛП

Определение оптимального плана типа min проиллюстрируем на примере решения следующей задачи:

Анализ задачи.

1) задача представлена в первой канонической форме;

2) система ограничений (27) включает пять переменных, n = 5, r = 3;

3) так как r = 3, в системе будут три базисные переменные и n – r =2 – свободные;

4) х₁, х₂, х₃ – базисные переменные системы (27)

(х₁ – только в первом уравнении, х₂ – только во втором, х₃ – только в третьем);

х₄, х₅ – свободные переменные.

Выразим линейную форму (26) и базисные переменные через свободные

Первоначальный опорный план , значение целевой функции, соответствующее этому плану, .

Далее необходимо уменьшать значение линейной формы F. Уменьшение линейной формы F можно осуществить за счет увеличения свободных переменных. Однако увеличение свободных переменных, в данном случае х₄, сдерживается базисными переменными, которые должны оставаться положительными. Поэтому следует определить ту базисную переменную, которая первой обратится в ноль и перейдет в разряд свободных. В рассматриваемой задаче первой обратится в ноль базисная переменная х₁. Это следует из жордановой таблицы, которую составим для первоначальной задачи. После одного шага модифицированных Жордановых исключений получим новую Жордановую таблицу, из которой получим новое значение целевой функции При этом это значение будет минимальным, так как в строке линейной формы все элементы (за исключением значения функции F) отрицательны, и дальнейшее уменьшение значения целевой функции невозможно. Окончательно, имеем

Поиск по сайту: