Описание симплекс – метода

Симплекс – таблица задачи Таблица 2

Из анализа коэффициентов в условиях задачи (8)…(10) (или в соответствующей симплекс – таблице) можно сделать одно из следующих трех утверждений:

Теорема 1. Если в выражении (8) все коэффициенты , то в угловой точке (6) достигается минимум целевой функции на допустимом множестве Е и этот минимум равен .

q При любом значение с учетом (8) может лишь увеличиваться по сравнению с . ■

Теорема 2. Если среди отрицательных коэффициентов , в (8) есть такой, например, , то в (9) все коэффициенты , то минимум целевой функции на допустимом множестве Е не достигается, т.е. задача (8)…(10) не имеет решений.

q Положим значения всех свободных переменных, кроме , равными нулю. Тогда из уравнений (9) получаем решение

где,

Оно является допустимым, поскольку все . При этом с учетом (8) , поэтому, так как , целевая функция неограниченно убывает с ростом , т.е. целевая функция не ограничена снизу, а следовательно не имеет решения. ■

Замечание. Ситуация, описанная в теореме 2 возможна, если допустимое множество Е задачи не ограничено (см рис )

Рис. Неограниченное допустимое множество

Теорема 3. Пусть является невырожденным допустимым базисным решением задачи (8)…(10), т.е. Тогда, если хотя бы один из коэффициентов в (8), например, , отрицателен () и при этом среди коэффициентов есть хотя бы один положительный, то существует допустимое базисное решение множества Е, для которого .

q Положив в (9) значения всех свободных переменных, кроме , равными нулю, получим решение (12), (13) системы уравнений (9). По условию теоремы среди коэффициентов есть положительные, поэтому с увеличением может произойти нарушение условий неотрицательности (10) для соответствующих переменных из выражений (13). Найдем ту из них (), которая раньше всех обратиться в нуль при возрастании . С учетом (13) номер q находится из условия

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

Полагая в (12), (13) равным , получаем решение

где

Очевидно, что является допустимым базисным решением системы (9); оно соответствует базисным переменным . Отметим, что в этом решении переменные ипоменялись ролями: из базисных переменных перешла в свободные, а - наоборот.

Значение целевой функции (8) в точке из (15) равно . По условию и, следовательно, .■

Результаты теорем 1…3 лежат в основе симплекс метода решения задач линейного программирования. Идея этого метода состоит в следующем.

Если в точке из (6) выполняются условия теоремы 1 или 2, то решение задачи (1)…(3) на этом завершается.

Если же для точки выполнены условия теоремы 3, то совершается переход от к новому допустимому базисному решению из (15), для которого уменьшается. Затем в точке анализ коэффициентов задачи повторяется, и на основании теорем 1…3 делается одно из трех возможных заключений и т.д.

Так как число допустимых базисных решений задачи (1)…(3) не превосходит , то случай, описанный в теореме 3, может повторяться лишь конечное число раз. Поэтому в результате конечного числа шагов перехода к новому допустимому базисному решению задача будет решена или будет установлена ее неразрешимость.

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

Найдем канонический вид задачи, соответствующий допустимому базисному решению из (15). Считая свободными переменные , т.е. поменяв местами свободную переменную с базисной переменнойнайдем решение системы (4).

Разделив q – е уравнение из системы (9) на , запишем его в виде:

Выразим из равенства (17) переменную и подставим найденные выражения в остальные уравнения системы (9) и в формулу (8) для целевой функции. В результате получим:

Зависимость целевой функции от новых свободных переменных примет вид: .

Задача линейного программирования (17) … (19) имеет канонический вид, соответствующий допустимому базисному решению из (15)…(16) и может быть записана с помощью симплекс – таблицы. Компоненты нового базисного решения можно найти, приравняв нулю свободные переменные и и найдя при этом условии значения базисных переменных из (17), (18).

По знакам коэффициентов в системе (17), (18) и в выражении для целевой функции (19) можно сделать одно из трех приведенных выше заключений, как это было сделано для угловой точки . В случае теоремы 3 следует совершить переход к очередной угловой точке , аналогичной переходу от к , и т.д.

Как указано выше реализация симплекс – метода значительно упрощается при использовании симплекс - таблиц. Записав коэффициенты уравнений (4) и целевой функции (7) соответствующим образом (см. табл. ), получим симплекс – таблицу задачи для угловой точки из (6). Здесь введен для коэффициентов и индекс 0, показывающий, что они относятся к начальной угловой точке .