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

Пример

На предприятии имеется возможность выпускать видов продукции . При ее изготовлении используются ресурсы . Размеры допустимых затрат ресурсов ограничены соответственно величинами . Расход ресурса вида на единицу продукции j-го вида составляет единиц. Цена единицы продукции вида равна ден. ед.

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

Решение

Через обозначим планируемые к выпуску количества продукции соответственно , ,

Целевая функция задачи будет иметь следующий вид:

Ограничения на расход ресурса:

Кроме того, по смыслу задачи:

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

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

Заполняем симплексную таблицу 0-й итерации.

БП											Симплексные
			5	2	8	3	6	0	0	0	отношения
	0	3	1	1	1	2	2	1	0	0	3
	0	2	0	1	1	1	2	0	1	0	2
	0	2	1	1	0	2	1	0	0	1	—
		0	-5	-2	-8	-3	-6	0	0	0

Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.

Переход к следующей итерации осуществляем следующим образом:

Ведущий столбец соответствует .

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

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.1.

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

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

Переходим к таблице 1-й итерации:

БП											Симплексные
			5	2	8	3	6	0	0	0	отношения
	0	1	1	0	0	1	0	1	-1	0	1
	8	2	0	1	1	1	2	0	1	0	—
	0	2	1	1	0	2	1	0	0	1	2
		16	-5	6	0	5	10	0	8	0

Ключевой столбец для 1-й итерации соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 1.

Вектор выводим из базиса и вводим вектор .

Переходим к таблице 2-й итерации:

БП											Симплексные
			5	2	8	3	6	0	0	0	отношения
	5	1	1	0	0	1	0	1	-1	0
	8	2	0	1	1	1	2	0	1	0
	0	1	0	1	0	1	1	-1	1	1
		21	0	6	0	10	10	5	3	0

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

Ответ:

Таким образом, необходимо выпускать 1 единицу продукции 1-го вида и 2 единицы продукции 3-го вида При этом получаемая прибыль будет максимальна. Значение максимальной прибыли равно 21. При реализации оптимального плана остаток ресурса 1-го вида равен 1.