6. Алгоритм симплекс-метода.

Рассмотрим задачу линейного программирования в канонической форме (1.1.3).

Определение. Допустимый план x⁰ задачи (1.1.3) назовем базисным, если его можно представить в виде x⁰ = (x_Б⁰, x_Н⁰), причем x_Н⁰=0, т.е. из всех координат вектора x⁰ по крайней мере n-m равны нулю (m=rang(A)), а остальные соответствуют линейно независимым столбцам матрицы А.

Базисный план задачи однозначно определяется указанием того, какие из столбцов матрицы А (или координат вектора х) назначаются базисными, поскольку небазисные координаты у такого вектора должны быть равны нулю, а значения базисных координат можно найти из уравнения А_Бх_Б=b.

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

Выберем базис Б и приведем задачу (1.1.3) к нормальной форме с использованием этого базиса. Чтобы проверить, соответствует ли этому базису базисный план,  необходимо согласно (1.1.7) проверить условия:

0 ≤ A_Б^-1b,   (1.2.1)

при выполнении которых найдется план, дающий значение целевой функции

z = c_Б^TA_Б^-1b   (1.2.2)

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

z = c_Б^Tb +(c_Н^T– c_Б^TA_H)x_H → max,A_H x_H ≤ b, (1.2.3),x_H ≥ 0.

Поскольку план x является базисным, то в полученной задаче он соответствует вектору x_H = 0, причем оба эти вектора дают (каждый – в своей задаче) значение целевой функции равное  z = c_Б^Tb. Обозначим вектор

Δ^T=(c_Н^T– c_Б^TA_H). (1.2.4)

В случае, когда все координаты вектора Δ неположительны, то при x_H ≥ 0 выполняется условие (c_Н^T– c_Б^TA_H)x_H ≤ 0, следовательно, вектор x_H = 0 дает максимально возможное значение целевой функции, равное z = c_Б^Tb.

Если же у вектора Δ есть положительная координата, например, Δ^T_j=(c_j^T– c_Б^TA_j)>0, то в случае замены у вектора x_H = 0 j-й координаты на положительное число t значение целевой функции увеличится на величину Δz=Δ_jt, причем это увеличение будет тем значительнее, чем больше будет значение t. Ограничением на выбор t служат условия (1.2.3).

Кратко описанная выше процедура улучшения базисного плана составляет основу симплекс-метода решения задачи линейного программирования. Запишем этот алгоритм подробно:

1)    Находим начальный базисный план (и соответствующий ему перечень базисных переменных).

2)    Тождественными преобразованиями добиваемся того, чтобы матрица А_Б коэффициентов перед базисными переменными была единичной.

3)    Находим вектор-строку Δ^T = (c_Н^T– c_Б^TA_H). Если все его координаты отрицательны (или в случае вырожденного случая – неположительны), найденный план является решением задачи.

4)    Если у вектора Δ^T = (c_Н^T– c_Б^TA_H) есть положительные координаты, выбираем координату наибольшей величины (обозначим номер соответствующей переменной через j*).

5)    Проверим, можно ли с соблюдением условия A_H x_H ≤ b, заменить j*-ю координату вектора x на положительное число t. Поскольку остальные небазисные переменные остаются нулевыми, то

A_H x_H = A_j* x_j* = A_j* t ≤ b, или для всех i=1,…,m          a_ij*t ≤ b_i.

Следовательно, нужно искать максимально возможное положительное число t, такое, что для всех i, для которых a_ij* > 0, выполняется t ≤ b_i / a_ij* . Если для всех i выполняется a_ij* ≤ 0, то t = +∞, иначе t = min {b_i / a_ij* | a_ij* > 0} = b_i*/ a_i*j*.

6)     Если t = +∞, задача решения не имеет (целевая функция не ограничена на множестве допустимых планов).

7)    Если t <+∞ и i* - номер, на котором максимум был достигнут, то после замены x_j на t переменная x_i* станет равной нулю (при этом говорят, что мы выводим из базиса переменную x_i*, заменяя ее переменной x_j*). Набор базисных переменных у нас изменился, а значение целевой функции увеличилось на Δz = Δ_j* t.

8)    Переходим к пункту 2).

Работа алгоритма заканчивается либо в пункте 3), либо в пункте 6).