2020-01-15
97
Продемонстрируем применение симплекс-метода на примере. Рассмотрим каноническую задачу ЛП
| f(x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4→max | (2.2) |
| – x 1 + 2 x 2 + x 3 = 4, | (2.3) |
| 3 x 1 + 2 x 2 + x 4 = 12, | (2.4) |
| xj ≥ 0, j = 1,2,3,4. | (2.5) |
Матрица условий A = (A 1, A 2, A 3, A 4), где
Целевой вектор c =(c1, c2, c3, c4) = (1, 2, 0, 0); вектор правых частей b =(b 1, b 2) = (4, 12).
Шаг 0. Нахождение начальной угловой точки (базисного плана).
Задача имеет предпочтительный вид, так как правые части уравнений положительны, а столбцы матрицы условий A 3, A 4 образуют единичную подматрицу. Значит начальная базисная матрица 
= (A 3, A4); x 3и x 4 – базисные переменные, x 1и x 2 - небазисные переменные, cБ = (c 3, c 4 ) = = (0, 0).
Начальный базисный план имеет вид x0 = (0, 0, x 3, x 4) = (0, 0, 4, 12); f(xo)= 0.
Шаг 1. Проверка базисного плана на оптимальность.
Подсчитаем симплексные оценки для небазисных переменных по формуле (5.1)
1 = < cБ, A 1 > – c 1 = 0 ·(–1) + 0 ·3 – 1 = –1.
2 = < cБ, A 2 > – c 2 = 0 ·2 + 0 · 2 – 2 = –2.
Так как оценки отрицательны, то план x – не оптимален. Будем искать новый базисный план (смежную угловую точку) с большим значением целевой функции.
Шаг 2. Нахождение переменной вводимой в базис.
Целевую функцию можно увеличить, если ввести в состав базисных переменных (сделать положительной) одну из небазисных переменных x 1или x 2, поскольку обе оценки j < 0. Обычно в состав базисных вводят небазисную переменную с наибольшей по модулю отрицательной оценкой, поэтому будем вводить в базис переменную x 2.
Шаг 3. Определение переменной выводимой из базиса.
После ввода в базис переменной x2 новый план будет иметь вид
x' = (0, x 2, x 3, x 4).
Этот план не является базисным, так как он содержит только одну нулевую координату, значит надо сделать нулевой (исключить из базиса) одну из переменных x 3или x 4. Подставим координаты плана x' = (0, x 2, x 3, x 4) в ограничения задачи. Получим
2 x 2 + x 3 = 4,
2 x 2 + x 4 = 12.
Выразим отсюда базисные переменные x 3и x 4через переменную x 2, вводимую в базис.
| x 3 = 4 – 2 x 2, | (2.6) |
| x 4 = 12 – 2 x 2. | (2.7) |
Так переменные x 3и x 4должны быть неотрицательны, получим систему неравенств
| 4 – 2 x 2 ≥ 0, | (2.8) |
| 12 – 2 x 2 ≥ 0. | (2.9) |
Чем больше значение x 2, тем больше возрастает целевая функция. Найдем максимальное значение новой базисной переменной, не нарушающее ограничения задачи, то есть удовлетворяющее условиям (2.8), (2.9).
Перепишем последние неравенства в виде
2 x 2 ≤ 4,
2 x 2 ≤ 12,
откуда максимальное значение x 2 = min { 4/2, 12/2 } = 2. Подставляя это значение в выражения (2.6), (2.7) для x 3и x 4,получаем x 3 = 0.Следовательно x 3 выводится из базиса.
Шаг 4. Определение координат нового базисного плана.
Новый базисный план (смежная угловая точка) имеет вид
x' = (0, x 2, 0, x 4)
Базис этой точки состоит из столбцов A 2 и A 4, так что 
= (A 2, A 4). Этот базис не является единичным, так как вектор A 2 = (2,2),и следовательно задача (2.2)–(2.5) не имеет предпочтительного вида относительно нового базиса. Преобразуем условия задачи (2.3), (2.4) таким образом, чтобы она приняла предпочтительный вид относительно новых базисных переменных x 2, x 4, то есть чтобы переменная x 2входила в первое уравнение с коэффициентом, равным единице, и не присутствовала во втором уравнении. Перепишем уравнения задачи
– x 1+ 2 x 2+ x 3 = 4, (p 1)
3 x 1 +2 x 2 + x 4 = 12. (p 2)
Поделим первое уравнение на коэффициент при x 2.Получим новое уравнение 
= p 1 / 2, эквивалентное исходному
– 1/2 x 1+ x 2+ 1/2 x 3 = 2. ()
Используем это уравнение, которое назовем разрешающим, для исключения переменной x 2из второго уравнения. Для этого надо уравнение 
умножить на 2 и вычесть из p 2. Получим 
= p 2 – 2 = p 2 – p 1:
4 x 1 – x 3 + x 4 = 8. (
)
В итоге получили новое "предпочтительное" представление исходной задачи относительно новых базисных переменных x 2, x 4:
f (x) = x 1 + 2 x 2 + 0 x 3 + 0 x 4 max
– 1/2 x 1+ x2+ 1/2 x 3 = 2 ()
4 x 1 – x 3 + x 4 = 8 ( )
xj 0, j = 1,2,3,4
Подставляя сюда представление нового базисного плана x 1 = (0, x 2, 0, x 4), сразу найдем его координаты, так как значения базисных переменных равны правым частям уравнений
x' = (0, 2, 0, 8); f (x 1)=4.
На этом завершается первая итерация простого симплекс-метода. Далее процесс решения задачи продолжается с шага 1, состоящем в проверке найденного плана на оптимальность. Решение заканчивается тогда, когда все симплексные оценки текущего базисного плана окажутся неотрицательными.
Мы не будем проводить вторую итерацию по схеме первой, поскольку все вычисления симплекс-метода удобнее проводить в табличном виде.
