4. Симплексный метод
Если система ограничений основной задачи каноническая, то задачу линейного программирования можно решить симплексным методом.
Пример 1. Решим задачу симплекс-методом:
Преобразуем стандартную задачу в основную, добавляя к левым частям ограничений балансовые переменные. Целевая функция при этом не изменится.
Получим каноническую
задачу. Неизвестные
–
базисные,
–
свободные. Можно записать исходное
опорное решение:
.
Составим симплексную таблицу:
Cj базиса |
Базис |
0 |
C1=1 |
C2=6 |
C3=0 |
C4=0 |
C5=0 |
θ |
|
|
|
|
|
|
|||
0 0 0 |
|
6 4 4 |
1 1 -2 |
1 -2 1 |
1 0 0 |
0 1 0 |
0 0 1 |
6 - 4 |
|
|
0 |
-1 |
-6 |
0 |
0 |
0 |
|
0 0 6 |
|
2 12 4 |
3 -3 -2 |
0 0 1 |
1 0 0 |
0 1 0 |
-1 2 1 |
2/3 - - |
|
= |
24 |
-13 |
0 |
0 |
0 |
6 |
|
1 0 6 |
|
2/3 14 16/3 |
1 0 0 |
0 0 1 |
1/3 1 2/3 |
0 1 0 |
-1/3 1 1/3 |
|
|
= |
98/3 |
0 |
0 |
13/3 |
0 |
5/3 |
|
=
Cj – коэффициенты целевой функции. При х1 коэффициент C1=1, при х2 – C2=6, неизвестные х3, х4, х5 отсутствуют в целевой функции, следовательно их коэффициенты равны нулю. В первом столбце таблицы записываются коэффициенты целевой функции, соответствующие базисным неизвестным второго столбца таблицы.
Алгоритм симплекс-метода
Записываем данную задачу в исходную симплекс-таблицу.
Если все элементы оценочной строки симплексной таблицы неотрицательны, то исходный план является оптимальным.
Если в оценочной строке содержится отрицательный элемент, над которым в таблице нет положительных элементов, то целевая функция не ограничена сверху и задача не имеет решения.
Если над каждым отрицательным элементом оценочной строки в соответствующем столбце есть хотя бы один положительный элемент, то можно перейти к лучшему плану.
С этой целью:
а) выбираем в
исходной таблице разрешающий столбец.
Это столбец, соответствующий наименьшей
отрицательной оценке. Пусть это столбец,
соответствующий переменной
;
б) выбираем разрешающую (q-тую) строку из условия
в) элемент – разрешающий;
г) элементы разрешающей строки делим на разрешающий элемент;
д) элементы остальных строк вычисляем по правилу «прямоугольника»;
е) элементы оценочной строки также вычисляются по правилу нахождения оценок. Эту формулу можно использовать в качестве контроля вычислений.