Симплексный метод

Симплексный метод был разработан известным  американским  математиком Дж. Данцигом  и в настоящее время стал универсальном  методом линейного программирования. Алгоритм метода состоит из ряда шагов.

{spoiler=Подробнее}

1.При решении задачи симплексным методом необходимо систему уравнений привести к виду, когда какие-либо r  переменных (базисные) выражены через остальные (небазисные), причем свободные члены этих выражений должны быть неотрицательными.

Пусть для определенности  х₁, х₂, х₃ ... х_r  выражены через остальные переменные х _r+1, х_r+2, х_r+3 ... х_n .

Система ограничений принимает вид:

                      (1)

где b`<sub>1</sub>³0,  b`₂ ³0, .... b`_r³0.

Базис (х₁,х₂ , ..., х_r) обозначим через Б. Пусть все небазисные переменные равны нулю:

х _r+1= х_r+2=...= х_n =0.

Найдем из системы (1) значения базисных переменных:

x₁=b’₁ ,x₂=b’₂ ,...., x_r=b’_r .

В результате получаем базисное решение (b’₁ ,b’₂ ,...., b’_r ,0,...,0),

соответствующее базису Б.

Целевая функция F(х₁, ... ,х_n) также выражается  через небазисные переменные:

F= с₀ +с’_r+1 х _r+1+ ... +с’_nх_n.

Замечаем, что значение целевой функции, соответствующее базисному решению, равно с₀ : F_Б= с₀.

2.Следующим шагом алгоритма является проверка  достижения оптимума. Если оптимум не достигнут, то из базиса Б удаляется одна из переменных в небазисные, а в место нее из числа прежних небазисных переменных вводится  новая. Получаем новый базис Б’.

С новым базисом поступаем так же в соответствии с содержанием шагов 1 и 2. Если в результате этого  оптимум не достигнут, то все шаги повторяем снова,  причем каждый новый шаг заключается F_Б уменьшается или, по крайней мере, не увеличивается:

F_Б’£ F_Б.

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

Проследим за этой последовательностью шагов на примерах.

Задача. Минимизировать F=х₂-х₁ при неотрицательных   х₁ и  х_2, удовлетворяющих системе  ограничений:

Решение. Запишем ограничения как уравнения, выражающие базисные переменные через небазисные:

х₃=2+2х₁-х₂

х₄=2-х₁+2х₂

х₅=5-х₁-х₂.

Пусть базис Б состоит из переменных  х₃ ,х₄,х₅ .Тогда базисное решение-(0;0;2;2;5) .Теперь надо выразить F через  небазисные переменные. В нашем конкретном случае это, оказывается , уже сделано.

Проверим, достигла ли целевая функция  своего минимального значения. Коэффициент при х₁  в выражении для F отрицателен.

Следовательно, возрастание х₁ переменные х₃ ,х₄,х₅ могут уменьшается , и необходимо следить за тем , чтобы ни одна из них не стала  отрицательной. Так как увеличение х₁ ведет к увеличению х₃, то для этой переменной такой опасности не существует. Из анализа других базисных переменных  получаем, что значение х₁ может быть увеличено только до 2.Такое увеличение даст   х₄ =0,х₃=6, х₅ =3. Этот результат нас устраивает, так как число положительных переменных такое  же , как и раньше . Новые базис Б’ состоит х₁ ,х₃,х₅ .

Чтобы приступить к выполнению следующего шага, выразим эти переменные и целевую функцию F через небазисные переменные х₂ и х₄ . Это легко сделать , если решить второе уравнение относительно новой базисной переменной  х₁, а подстановка этого выражения в остальные уравнения и целевую функцию F дает:

F=-2-х₂+х₄

Коэффициент при х₂ функции F отрицателен. По этому можно и дальше уменьшать целевую функцию F , увеличивая х₂ . Однако х₂  можно увеличивать не более ,чем до 1:Это следует из уравнения  х₅=3-3х₂+х₄ (если х₂>1 , х₄=0, то х₅ <0). Подстановка х₂=1 в другие уравнения дает х₁=4 и х₃=9.Еще раз выразим базисные переменные и F через небазисные:

х₁=4-х₄/3-2x₅/3

x₂=1+x₄/3-x₅/3

x₃=9-x₄-x₅.

Базис Б’’ состоит переменных х₁, х₂ , х­₃,

F=-3+2x₄/3+x₅/3.

Увеличивая х₄ и х₅ , мы уже не можем получить дальнейшего уменьшения F.Следовательно, нами получено  оптимальное решение. Наименьшее значение F, равное-3 , достигается при х₁=4, х₂=1 ,х₃=9.

{/spoilers}