Реализация симплекс-метода на примере

Продемонстрируем применение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП

Матрица условий A = (A₁, A₂, A₃, A₄), где

Целевой вектор c =(c₁, c₂, c₃, c₄) = (1, 2, 0, 0); вектор правых частей b=(b₁, b₂) = (4, 12).

Шаг 0. Нахождение начальной угловой точки (базисного плана).

Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A_3, A₄ образуют единичную подматрицу. Значит начальная базисная матрица = (A₃, A₄); x₃и x₄ – базисные переменные, x₁и x₂ - небазисные переменные, c_Б = (c_3, c₄₎ = = (0, 0).

Начальный базисный план имеет вид x⁰ = (0, 0, x₃, x₄₎ = (0, 0, 4, 12); f( x^o)= 0.

Шаг 1. Проверка базисного плана на оптимальность.

Подсчитаем симплексные оценки для небазисных переменных по формуле (5.1)

₁ = < c_Б, A₁ > – c₁ = 0 ·(–1) + 0 ·3 – 1 = –1.

₂ = < c_Б, A₂ > – c₂ = 0 ·2 + 0 · 2 – 2 = –2.

Так как оценки отрицательны, то план x – не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.

Шаг 2. Нахождение переменной вводимой в базис.

Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x₁или x₂, поскольку обе оценки _j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x_2.

Шаг 3. Определение переменной выводимой из базиса.

После ввода в базис переменной x₂ новый план будет иметь вид

x' = (0, x_2, x₃, x₄).

Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x₃или x₄. Подставим координаты плана x' = (0, x_2, x₃, x₄) в ограничения задачи. Получим

2x₂+ x₃ = 4,

2x₂ + x₄ = 12.

Выразим отсюда базисные переменные x₃и x₄через переменную x₂, вводимую в базис.

Так переменные x₃и x₄должны быть неотрицательны, получим систему неравенств

Чем больше значение x₂, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).

Перепишем последние неравенства в виде

2x₂ ≤ 4,

2x₂ ≤ 12,

откуда максимальное значение x₂ = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x₃и x₄,получаем x₃ = 0.Следовательно x₃ выводится из базиса.

Шаг 4. Определение координат нового базисного плана.

Новый базисный план (смежная угловая точка) имеет вид

x' = (0, x_2, 0, x₄)

Базис этой точки состоит из столбцов A₂ и A₄, так что = (A_2, A₄). Этот базис не является единичным, так как вектор A₂ = (2,2),и следовательно задача (2.2)–(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x_2, x_4, то есть чтобы переменная x₂входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи

– x₁+ 2 x₂+ x₃ = 4, (p₁₎

3x₁ +2 x₂ + x₄ = 12. (p₂₎

Поделим первое уравнение на коэффициент при x₂.Получим новое уравнение = p₁ / 2, эквивалентное исходному

– 1/2 x₁+ x₂+ 1/2 x₃ = 2. ( )

Используем это уравнение, которое назовем разрешающим, для исключения переменной x₂из второго уравнения. Для этого надо уравнение  умножить на 2 и вычесть из p₂. Получим  = p₂ – 2  = p₂ – p₁:

4 x₁ – x₃ + x₄ = 8. ( )

В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x₂, x₄:

f(x) = x₁ + 2 x₂ + 0 x₃ + 0 x₄ max

– 1/2 x₁+ x₂+ 1/2 x₃ = 2 ( )

4 x₁ – x₃ + x₄ = 8 ( ₎

x_j 0, j = 1,2,3,4

Подставляя сюда представление нового базисного плана x¹ = (0, x_2, 0, x₄), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений

x' = (0, 2, 0, 8); f(x¹)=4.

На этом завершается первая итерация простого симплекс-метода. Далее процесс решения задачи продолжается с шага 1, состоящем в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда все симплексные оценки текущего базисного плана окажутся неотрицательными.

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