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

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

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

В классическом симплекс-методе по умолчанию предполагается неотрицательность искомых переменных и.

Последовательность вычислений для решения задачи максимизации симплекс-методом можно разделить на две основные фазы:

1) выбор исходной вершины множества допустимых решений;

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

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

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

c дополнительными условиями

Для применения симплекс-метода задачу нужно записать в каноническом виде:

(1.17)

.

Здесь — новые переменные, которые вводятся, чтобы все ограничения переписать в виде равенств.

Запишем задачу для удобства в матричном виде:

. (1.18)

Здесь:

—управляемые переменные исходной задачи (1.17),

—новые переменные, дополняющие старые таким образом, что неравенство переходит в равенство,

—коэффициенты исходной линейной целевой функции,

—переменная, которую необходимо максимизировать.

Разница между числом переменных и уравнений даёт нам число степеней свободы . Тогда мы можем присвоить этому числу переменных какие-то значения и назвать ихсвободными. Остальные переменные при этом будут вычисляться однозначно, и называться базисными. В нашем случае так называемое начальное допустимое решение (вершина, из которой мы начнём движение) очевидно, . Будем считатьсвободными переменными, все новые переменные будем считать базисными. При этом значения базовых переменныхвычисляются однозначно:.

Приведём шаги алгоритма. На каждом шаге мы будем двигаться по какому-то ребру к новой вершине. Одна из свободных переменных станет базисной, одна из базисных станет свободной, и система (2) перейдёт в систему

где

—базисные переменные начального или предыдущего шага;

—свободные переменные начального или предыдущего шага;

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

—столбцы матрицы , соответствующие базисным переменным.

Матрицу, образованную оставшимися в столбцами обозначим.

Первое действие первого шага.

Выбираем, как указано выше: , . На первом шаге — единичная матрица, так как базисными переменными являются, а свободными переменными являются, по тем же причинам. Присвоим всем свободным переменным нулевые значения, и начнём движение от вершины.

Второе действие очередного шага.

Покажем, что в выражении

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

Выберем ребро, по которому мы будем перемещаться. Поскольку мы хотим максимизировать , то необходимо выбрать переменную, которая будет более всех уменьшать выражение

,

(на первом шаге ).

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

Третье действие очередного шага.

Теперь необходимо понять, какая базисная переменная первой обратится в ноль по мере увеличения входящей переменной. Для этого достаточно рассмотреть систему:

При фиксированных значениях свободных переменных система однозначно разрешима относительно базисных, поэтому мы можем определить, какая из базисных переменных первой достигнет нуля при увеличении входящей. Эту переменную назовем выходящей. Это будет означать, что мы натолкнулись на новую вершину. Теперь входящую и выходящую переменную поменяем местами — входящая «войдёт» в множество базисных, а выходящая из них «выйдет» в множество свободных. Присвоим всем свободным переменным нулевые значения, вычислим базисные.

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

Первое действие второго и последующих шагов.

Перепишем матрицу и вектор в соответствии с новыми наборами базисных и свободных переменных. (при этом на втором шаге осуществляется переход от (2) к (3), на следующих шага меняется (3)).

Перейдём ко второму действию.

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

Легло построить аналогичные алгоритмы для задач

На практике описанный алгоритм реализуется с помощью таблиц.

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

					Таблица 1.4.
Ресурсы					Запас ресурсов
Трудовые	1	1	1	1	16
Сырье	6	5	4	3	110
Оборудование	4	6	10	13	100
Прибыль	60	70	120	130
План

Математическая модель задачи примет вид:

,

(*)

Решение. Приведем исходную задачу к каноническому виду. Для этого в ограничения задачи введём дополнительные переменные и от системы неравенств (*) перейдём к равенствам (**):

(**)

В нашем случае положение исходной вершины многогранника, ограничивающего область допустимых решений, очевидно: . Это переменные — свободные, переменные— базисные. Приполучим .

Составим первую симплекс-таблицу. Здесь в столбцах, отведённых свободным переменным, в первых трех позициях стоят соответствующие им коэффициенты из (*), в последней индексной строке стоят соответствующие им коэффициенты из выражения целевой функции с противоположным знаком (табл. 1.5).

Таблица 1.5.

Базис	Свободные члены	Свободные переменные
	16	1	1	1	1
	110	6	5	4	3
	100	4	6	10	13
Индексная строка	0	-60	-70	-120	-130

в начальной вершине с координатами

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

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

2). Положение этого элемента в индексной строке определяет входящую свободную переменную, в нашем примере , которая переместится в базис и соответствующий столбец, «ключевой столбец», в нашем примере . Символ означает операцию транспонирования.

3). Компоненты вектора свободных членов, в нашем примере , делятся на положительные элементы «ключевого столбца», у нас получится:

.

4). Базисная переменная в строке, которую назовём «ключевой строкой» и которая соответствует наименьшему полученному в пункте 3) компоненту, в нашем примере , выводится из базиса (становится выходящей) и заменяется свободной переменной из пункта 2), в нашем примере .

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

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

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

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

Вторая симплекс-таблица будет иметь вид (табл. 1.6).

Таблица 1.6.
Базис	Свободные члены	Свободные переменные на данном шаге: , ,и .
					0
					0
					1
Индексная строка	1000	-20	-10	-20	0

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

Таблица 1.7.
Базис	Свободные члены	Свободные переменные на данном шаге:,,и .
	12	1			0
	26	0		0	0
	4	0			1
Индексная строка	1240	0			0

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

Четвёртая симплекс-таблица имеет вид:

Таблица 1.8.
Базис	Свободные члены	Свободные переменные на данном шаге:,,и .
	10	1		0
	26	0		0
	6	0		1
Индексная строка	1320	0	10	0	20

В индексной строке все элементы положительны, все свободные члены положительны, следовательно, полученное решение оптимально и допустимо.

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

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

При использовании симплекс-метода могут возникнуть особые случаи.

1. Вырожденность.

2. Альтернативные решения.

3. Неограниченные решения.

4. Отсутствие допустимых решений.

С этими случаями можно ознакомиться самостоятельно, используя приведенную литературу, например [Таха].