D. Симплекс-метод

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

Тем не менее, исходная форма задачи, к которой непосредственно применим симплекс-метод, должна иметь специальный вид. Эта форма является частным случаем основной формы (1.5) задач линейного программирования. Здесь также система ограничений представлена ограничениями-равенствами (линейными уравнениями) и условиями неотрицательности. Однако в равенствах, кроме того, выделяются так называемые базисные переменные. В каждом из равенств присутствует одна определенная базисная переменная, взятая с единичным коэффициентом, а в других равенствах ее нет. Число базисных переменных, таким образом, совпадает с числом ограничений-равенств в системе и обычно строго меньше общего числа переменных. Остальные переменные называются небазисными или свободными. Еще одно требование заключается в выполнении условия неотрицательности свободных членов b_i в равенствах. Наконец, целевая функция задачи должна быть выражена только через небазисные переменные. Некоторые авторы называют такую форму представления задачи линейного программирования канонической.

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

Пример 1.2. Рассмотрим задачу линейного программирования вида:

L =3 x ₁+4 x ₂+6 x ₃®max

Преобразуем первое и второе неравенства в равенства, введя новые неотрицательные переменные x ₄ и x ₅. Получим новую систему ограничений:

Переменная x ₃ входит с единичным коэффициентом только в первое уравнение, переменная x ₄ – только во второе уравнение. Именно они и составляют базис задачи. Целевая функция выражена лишь через небазисные переменные x ₁, x ₂, x ₃. Таким образом, имеем каноническую форму представления.

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

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

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

Если задача линейного программирования представлена в канонической форме, то опорный план =(x ₁, x ₂, ..., x_n),, может быть получен с помощью простого правила: его базисные компоненты равны свободным членам ограничений-равенств, его небазисные компоненты равны нулю.

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

Таблица 1.1.

Базис	x 1	…	xn	xn+ 1	…	xn+m	Свободные члены
xn+ 1	a 11	…	a 1n		…		b 1
…	…	…	…	…	…	…	…
xn+m	am 1	…	amn		…		bm
	-c 1	…	-cn		…

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

Алгоритм симплекс-метода рассмотрим на решении задачи из примера 1.2. Соответствующая симплекс-таблица имеет вид:

Таблица 1.2.

Базис	x 1	х 2	х 3	x 4	х 5	Свободные члены	Симплекс-отношения
х 4							6*
х 5
	-3	-4	-6*

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

Данной симплекс-таблице, согласно выше приведенному правилу, соответствует опорный план (вершина) вида

.

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