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

Симплексный метод – это распространенный метод решения задач линейного программирования. Свое название метод получил от слова «симплекс», обозначающего простейший выпуклый многоугольник, число вершин которого всегда на единицу больше, чем размерность пространства. Симплексный метод разработан в США математиком Дж. Данцигом в конце 1940-х годов.

Симплексный метод включает получение неотрицательного базисного решения системы канонических линейных уравнений типа (3.1), последующую минимизацию (максимизацию) целевой функции (3.3) и нахождение таким способом оптимальных значений искомых переменных х₁, х_2… х_n.

Идея симплексного метода заключается в том, что в процессе вычисления последовательно переходят от первого базисного решения ко второму, третьему и т.д. с помощью так называемых симплексных преобразований. Преобразования производятся в форме симплексных таблиц, что значительно упрощает и ускоряет расчеты.

Чтобы получить неотрицательные базисные решения системы линейных уравнений, надо процесс исключения неизвестных вести так, чтобы свободные члены уравнений на всех этапах процесса оставались неотрицательными. При этом следует руководствоваться следующим правилом: в качестве новой базисной переменной принимается любая свободная переменная, при которой есть хотя бы один положительный коэффициент; выводится из базиса переменная, которая соответствует наименьшему отношению свободных членов уравнений к соответствующим положительным коэффициентам уравнений при вводимой в базис переменной. Такие преобразования называются симплексными преобразователями.

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

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

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

Пусть необходимо минимизировать линейную форму

L = с₁ х₁+ с₂ х₂ + … с_n х_n .

При условиях (для наглядности нулевые и единичные коэффициенты в уравнениях сохранены):

1х₁+ 0х₂ + … 0х_m + a_1m+1x_m+1…+a_1n^x_n = b₁;

0х₁+ 1х₂ + … 0х_m + a_2m+1x_m+1…+a_2n^x_n = b₂ ;

……………………………………………

0х₁+ 0х₂ + … 1х_m + a_mm+1x_m+1…+a_mnx_n = b_m.

В данной системе уравнений уже имеется готовый базис, поскольку каждое уравнение ограничений содержит неизвестную с коэффициентом, равным единице, которой нет в других уравнениях, т. е. из коэффициентов при переменных х₁, х₂…, х_m можно составить единичную матрицу.

Решим уравнения относительно базисных переменных :

х₁ = b₁ – (a_1m+1·х_m+1…+ a_1nx_n );

х₂ = b₂ – (a_2m+1·х_m+1…+ a_2nx_n );

………………………………

х_m = b_m – (a_mm+1x_m+1…+ a_mnx_n),

а целевую функцию выразим через свободные переменные, подставив в нее на место базисных переменных их выражения через свободные переменные:

L=c₁b₁+c₂b₂+c_mb_m–(c₁a_1m+c₂a_2m+1+…+c_ma_mn+1)x_m+1-…-(c₁a_1n+c₂a_2n+…+c_ma_mn)x_n…+c_nx_n..

Переменные х₁, х₂…, х_m, с помощью которых найден первый базисный план, являются базисными, а остальные x_m+1, x_m+2,…x_n – свободными. Базисных переменных должно быть всегда столько, сколько уравнений в системе. Исходя из условия неотрицательности, наименьшее значение свободных переменных равно нулю. Полученное базисное решение системы уравнений и является ее первоначальным допустимым решением, т.е. x₁= b₁, x₂=b₂, … x_m=b_m, x_m+1=0,…, x_n=0.

Этому решению соответствует значение целевой функции

L = с₁ b₁+ с₂ b₂ + … с_m b_m.

Первоначальное решение проверяется на оптимальность. Если оно неоптимально, то путем введения в базис свободных переменных находят следующие допустимые решения с меньшим значением целевой функции. Для этого определяют свободную переменную, которую необходимо ввести в базис, а также переменную, которую необходимо вывести из базиса. Затем переходят от предыдущей системы к последующей эквивалентной системе. Осуществляется это с помощью симплекс-таблиц. Решение задачи продолжается до получения оптимального значения целевой функции.

Симплексные таблицы составляют следующим образом (см. табл. 3.1). Вверху таблицы помещают все переменные х₁, х₂…, х_n и коэффициенты c_j, с которыми соответствующие переменные входят в целевую функцию. Первый столбец c_i состоит из коэффициента целевой функции при переменных, вошедших в базис. Затем следует столбец базисных переменных и свободных членов уравнений. Элементы остальных столбцов таблицы представляют собой коэффициенты при переменных, с которыми последние входят в систему уравнений. Таким образом, каждой строке таблицы соответствует уравнение системы, решенное относительно базисной переменной. В таблице показан и вариант плана, который соответствует целевой функции при данном базисе.

Нижняя строка таблицы называется индексной. Каждый ее элемент (оценка) ∆_j определяют

∆_j = z_j – c_j,

где c_j – коэффициенты при соответствующих переменных в целевой функции; z_j – сумма произведений коэффициентов целевой функции при базисных переменных на соответствующие переменные – элементы j–го столбца таблицы.

Таблица 3.1