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

Аналитическое решение задачи линейного программирования осуществляется в следующей последовательности.

1. Задача приводится к каноническому виду.

2. Выбираются базисные и свободные переменные. Переменные являются базисными, если они линейно независимы и соответствуют единичным векторам (чаще всего это балансовые переменные):

и так далее.

Если в исходных ограничениях нет базиса, то он вводится в них искусственно.

3. Целевая функция выражается через свободные переменные.

4. Находится решение, приводящее целевую функцию к экстремуму.

Обычно задача поиска оптимального плана состоит из задачи определения какого-либо опорного плана , затем его оптимизации, то есть, последовательного перебора опорных планов таким образом, чтобы целевая функция возрастала (или не убывала). Геометрически это означает переход по рёбрам многогранника (по граничным прямым в случае многоугольника), являющегося областью решений, из одной вершины в другую и далее до достижения оптимального решения .

Пусть задача (1.1)-(1.5) максимизируется и система ограничений записана в симметричной форме

(1.7)

За счёт введения балансовых переменных задача приведена к каноническому виду (1.8) с условиями (1.9)

(1.8) (1.9)

Если балансовые переменные принять за базисные и выразить их через остальные переменные

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

Таблица 1.5

В первом столбце таблицы 1.5 приводятся базисные переменные (Б.П.). Во втором столбце – свободные члены. В столбцах (С.П.) приводятся свободные переменные с отрицательными знаками при переменных, за счёт чего коэффициенты при этих переменных остаются с такими знаками, как в системе неравенств. Последняя строка таблицы называется - строкой. Коэффициенты целевой функции также записываются с противоположными знаками и называются оценками.

Алгоритм поиска решения будет следующим.