max(f)=+∞.

В нашем примере прямая f=aпересевает область ABCDEв точке С(4;1). Поскольку это последняя точка пересечения, max(f)=f(C)=f(4;1)=19.

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

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

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

Система (4) – естественные ограничения и в таблицу не вписываются. Уравнения (1), (2), (3) образуют область допустимых решений. Выражение (5) – целевая функция. Свободные члены в системе ограничений и области допустимых решений должны быть неотрицательны.

В данном примере X3, X4, X5 – базисные неизвестные. Их надо выразить через свободные неизвестные и произвести их замену в целевой функции.

Теперь можно приступить к заполнению симплекс-таблицы:

Б.	X1	X2	X3	X4	X5	C
X3	0	-1	1	1	0	1
X4	0	1	-1	0	1	1
X5	1	1	1	0	0	2
f	0	-6	7	0	0	3

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

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

Б	X1	X2	X3	X4	X5	C
X3	-1	1	1	0	0	1
X4	1	-1	0	1	0	1
X5	1	1	0	0	1	2
f	-6	7	0	0	0	3

Для этого выбираем столбец с отрицательным коэффициентом в последней строке[2] (столбец 3) и составляем для положительных элементов данного столбца отношения свободный член/коэффициент (1/1; 2/1)[3] . Из данных отношений выбираем наименьшее и помечаем соответствующую строку[4] .

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

Б	X1	X2	X3	X4	X5	C
X3	0	0	1	1	0	2
X1	1	-1	0	1	0	1
X5	0	2	0	-1	1	1
f	0	1	0	6	0	9

Как видно из таблицы теперь все коэффициенты в последней строке больше либо равны нулю. Это означает, что нами найдено оптимальное значение. Свободные неизвестные равны нулю, значению базисных неизвестных и максимуму функции f соответствует значения свободных неизвестных.

Метод искусственного базиса

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

Суть метода довольно проста:

1. К строкам, в которых отсутствует базисная переменная добавляется по одной искусственной базисной переменной.
2. Новая задача решается Симплекс-методом, причем все искусственные базисные переменные должны стать свободными (выйти из базиса) и их сумма должна равняться нулю, в обратном случае в данной системе невозможно выделить допустимый базис.

Рассмотрим следующий пример:

min(f)-?

В первом уравнении нет базисных неизвестных. Введём искусственную базисную неизвестную Y1 и заполним первую симплекс-таблицу

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

F=Y1→min

Выражая базисную неизвестную Y1 через свободные получаем:

F+4X1+X2=4 →min

Б	X1	X2	X3	X4	Y1	С
Y1	4	1	0	0	1	4
X4	11	3	-5	-1	0	12
F	4	1	0	0	0	4

Выбираем элемент в ячейке (3;2) и делаем шаг.

Б	X1	X2	X3	X4	Y1	С
X2	4	1	0	0	1	4
X4	-1	0	-5	-1	-3	0
F	0	0	0	0	-1	0

min(f)=0, все коэффициенты в последней строке меньше или равны нулю, следовательно мы перешли к новому естественному базису. Теперь можно решать основную задачу.

Принцип двойственности

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

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