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

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

а) строится начальное решение;

б) проводится оценка найденного решения по соответствующему критерию оптимальности;

в) если условие оптимальности не выполняется, переходят к новому решению.

Этапы б) и в) выполняются до тех пор, пока будет получено оптимальное решение.

Все правила проиллюстрируем на примере [6]:

Пример 2. Найти при ограничениях:

I этап.Построение начального решения.

а) Приводим задачу к каноническому виду.

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

.

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

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

Получили канонический вид уравнений.

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

где - основные переменные;

- дополнительные переменные;

- искусственные переменные.

Все переменные неотрицательны.

в) Выписывают векторы коэффициентов при неизвестных и вектор свободных членов.

г) строят первую симплексную таблицу следующего вида:

Таблица 2.

Базис	С			-1				М	М	С.О.
	M				-1
	M					-1
			-1							-
Z- строка			-2
M- строка					-1	-1

 

Заполняют таблицу по правилам:

1. Вносят все векторы .
2. В самую верхнюю строку записывают коэффициенты целевой функции при соответствующих неизвестных.
3. В качестве первоначального базиса берут векторы, образующие единичную матрицу, - в данном случае это векторы , , .
4. В столбец С переносят из верхней строки числа, соответствующие базисным векторам.
5. Чтобы получить элементы двух последних строк, вектор С умножают последовательно на векторы , ,…,и от результата вычитают соответствующие число из верхней строки.

, и т.д.

В М – строку записывают коэффициент при М, в Z – строку –коэффициент без М.

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

,

II этап.Проверка оптимальности решения.

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

Следуя данному критерию, можем заключить, что полученное из таблицы 1 решение не является оптимальным.

б) В случае, когда критерий оптимальности не выполняется, выбирают ключевой столбец - по наибольшему положительному числу в М- строке (а затем Z –строке), начиная со второго. Ключевой столбец показывает, какой вектор войдет в базис. В примере – наибольшее число в М –строке (начиная со второго) равно 6, в новый базис войдет .

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

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

III этап.Построение нового решения (табл.3)

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

б) Столбец С заполняют по правилу, изложенному выше –из верхней строки.

 

Таблица 3

Базис	С			-1				М	М	С.О.
	M			9/5	-1	1/5				5/3
				1/5		-1/5
				6/5		-1/5				10/3
Z- строка				7/5		-2/5
M- строка				9/5	-1	1/5

в) вычисления ведут по таким правилам.

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

2. Ключевой столбец дополняют нулями.

3. Если в ключевой строке есть нули, то соответствующие им столбцы переносят без изменения.

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

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

Решение, соответствующее II –й таблице, такое:

,,

Для анализа второго решения повторяют все действия, начиная со II этапа. Проверка показала, что во II таблице условие оптимальности не выполняется. Вновь выбирают ключевой столбец (), находят симплексные отношения и находят ключевую строку (первая), генеральный элемент равен 9/5. Все вычисления приводят к таблице 4. Из базиса уходит последний искусственный вектор , поэтому таблица 4 не будет содержать М-строку.

Таблица 4

Базис	С			-1				С.О.
	-1	5/3			-5/9	1/9		-
		2/3			1/9	-2/9
					2/3	-1/3
Z- строка		-1/3			7/9	-5/9

Решение в соответствии с таблицей 3 имеет вид:

,

Данное решение оптимальным не является – проверку проведем по Z- строке. Строим еще одну таблицу:

Таблица 5

Базис	С			-1
	-1	10/3				-1/6	-5/6
		1/3				-1/6	-1/6
						-1/2	3/2
Z- строка		-8/3				-1/6	-7/6

Условие оптимальности выполнилось. Оптимальное решение имеет вид: