Симплекс-метод решения задачи линейного программирования

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

Cимплекс-метод можно применять в том случае, когда задача программирования задана в каноническом виде. В дальнейшем, будем рассматривать задачи линейного программирования канонического вида, так как любая ЗЛП может быть сведена к решению канонической задачи.

Задача линейного программирования имеет канонический вид, если система ограничений задана множеством уравнений:

и каждое i -е уравнение содержит переменную такую, что коэффициент перед ним в этом уравнении равен 1, а во всех других уравнениях равен 0. Если при этом , то говорят о допустимом каноническом виде. Переменные называют базисными, остальные – свободными.

ЗЛП допустимого канонического вида может быть записана в допустимой симплекс-таблице следующего вида: левый крайний столбец содержит номера базисных переменных, верхняя строка – номера свободных переменных. В точке пересечения строки, соответствующей значению , и столбца, соответствующего , стоит коэффициент при свободной переменной в уравнении i, в котором выделена базисная переменная . Соответственно, справа записаны постоянные члены уравнений, внизу – коэффициенты целевой функции от свободных переменных, а в правом нижнем углу записано значение «-Q₀».

Симплекс-таблица

		…
		…
…	…		…	…
		…
		…

Допустимому каноническому виду ЗЛП или соответствующей допустимой симплекс-таблице сопоставляется точка , , , . Координаты этой точки удовлетворяют n линейно-независимым условиям ЗЛП: m уравнениям и n-m неравенствам для свободных переменных. Эта точка является допустимым базисным решением и вершиной многогранника решений.

Допустимой симплекс-таблице соответствует точка минимума, если все коэффициенты целевой функции неотрицательны:

, …,

Тогда минимальное значение целевой функции равно

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

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

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

3) Замена базиса при помощи разрешающего элемента . Если w – какое-либо значение в таблице, то через будем обозначать значение, стоящее в новой таблице на том же самом месте:

а)номера переменных из разрешающей строки и разрешающего столбца меняются местами,	, ,
номера других переменных остаются на месте	для всех , для всех ;
б) разрешающий элемент заменяется на обратное значение:	,

остальные элементы разрешающего столбца и разрешающей строки делят на разрешающий элемент со знаком «-» для элементов разрешающего столбца и со знаком «+» для элементов разрешающей строки, то есть

элементы разрешающего столбца заменяются следующим образом: для всех ,	;
и элементы разрешающей строки заменяются следующим образом: для всех ,	;

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

для всех и ,

для всех ,

для всех ,

.

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

Отметим, что переменным, индекс которых стоит в верхней строке, в базисном решении приписывается значение 0; это свободные переменные. Каждая из переменных, индекс которых стоит в левом столбце, приравнивается к числу, записанному в правом столбце той же самой строки; это базисные переменные.

Каждой задаче линейного программирования можно сопоставить точно одну двойственную ей задачу линейного программирования.