Алгоритм симплекс-метода.
Изложим теперь этот метод решения, в общем виде.
Пусть дана симплексная форма задачи ЛП, то есть каноническая задача ЛП, матрица системы которой имеет разрешенный вид, свободные члены неотрицательны и целевая функция зависит только от свободных переменных:
(1)
Здесь мы считаем
свободными переменные
.
Запишем функцию
в виде уравнения:
,
(2)
Уравнениям (1) и (2) соответствует первая симплекс-таблица:
|
|
|
….. |
|
|
….. |
|
|
|
0 |
1 |
0 |
….. |
0 |
|
….. |
|
|
|
0 |
0 |
1 |
….. |
0 |
|
….. |
|
|
(3) |
….. |
….. |
….. |
….. |
….. |
….. |
….. |
….. |
….. |
|
0 |
0 |
0 |
….. |
1 |
|
….. |
|
|
|
1 |
0 |
0 |
….. |
0 |
|
….. |
|
|
|
Начало алгоритма симплекс-метода.
Шаг 1. По симплекс-таблице находим опорное решение. На первом шаге это будет:
и
(4)
Шаг 2.
Проверяем условие оптимальности
полученного опорного решения. Если
последняя (индексная) строка таблицы
(3) не содержит отрицательных элементов,
то есть, все коэффициенты целевой
функции
неположительные:
то опорное решение является оптимальным.
Решение задачи заканчивается, и мы
переходим к шагу 9.
Если условие
оптимальности:
,
не выполнено, то продолжаем решение
задачи.
Шаг 3.
Выбираем номер
одного из столбцов, содержащих
отрицательные элементы в индексной
строке. Соответствующий столбец объявляем
ведущим.
Шаг 4.
Определяем минимальное допустимое
отношение
для каждой строки по правилу:
где
- номер ведущего столбца.
Шаг 5.
Выбираем номер
ведущей строки с минимальным допустимым
отношением
.
Соответствующую
строку называем ведущей. Если такой
выбор невозможен, то есть все
,
то заканчиваем решение, поскольку в
этом случае задача не имеет решения.
Переходим к шагу 10.
Шаг 6.
Делим ведущую строку на ключевой элемент
,
стоящий на пересечении ведущей строки
и ведущего столбца. В результате на
месте ключевого элемента
получаем единицу:
.
Шаг 7. Из каждой строки таблицы, кроме ведущей, вычитаем ведущую строку, умноженную на элемент текущей строки, стоящий в ведущем столбце. В результате получаем, что все элементы ведущего столбца, кроме ключевого, равного единице, равны нулю, то есть ведущий столбец превратился в базисный. При этом оказывается, что один из базисных столбцов превратился в свободный (именно, тот, который содержал 1 в ведущей строке). Нами получена новая симплекс-таблица, отличающаяся от прежней набором базисных столбцов.
Шаг 8. Переходим к шагу 1.
Шаг 9. Объявляем, что получено оптимальное решение и выводим результаты решения. Затем переходим на конец алгоритма.
Шаг 10. Сообщаем, что задача не имеет решения и переходим на конец алгоритма.
Конец алгоритма.