Программирования

Пример 4. Для производства четырех видов продукции П₁, П₂, П₃, П₄ используются три вида ресурсов. Затраты каждого из видов ресурсов на ед. продукции, запасы ресурсов и прибыль, получаемая с ед. продукции каждого вида, приведены в таблице 2.5.

Определить план производства, при котором обеспечивается максимальная прибыль.

 

Таблица 2.5

Ресурсы	Норма расхода ресурса на ед. продукции	Запас ресурса
П1	П2	П3	П4
Трудовые
Сырье
Оборудование
Прибыль					-

Решение. Обозначим через х₁ план производства продукции П₁, х₂ - продукции П₂, х₃ - продукции П₃, х₄ - продукции П₄.

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

Приведем задачу к каноническому виду. Для этого в ограничения задачи введем дополнительные переменные х₅, х₆, х₇ и перепишем условие задачи в виде уравнений:

В качестве базисных переменных возьмем х₅, х₆, х₇, тогда небазисные – х₁, х₂, х₃, х₄. Полагаем х₁ = х₂= х₃= х₄= 0, тогда х₅ =16, х₆ =110, х₇ =100.

1-я итерация.

Составляем первую симплексную таблицу, соответствующую исходному опорному решению (таблица 2.6):

или

Таблица 2.6

ci	БП								bi
x1	x2	x3	x4	x5	x6	x7
	x5
	x6
	x7
Dj	- 60	- 70	-120	-130

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

,

,

,

и т.д.

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

, т.е. k =4.

За разрешающую строку принимаем строку переменной х₇:

, т.е. s =3.

Разрешающим является элемент а₃₄ =13, т.е. вводим в базис переменную х₄, выводим х₇.

2-я итерация.

Формируем следующую симплексную таблицу (таблица 2.7), пересчитывая предыдущую по изложенному выше правилу формирования новой симплекс-таблицы.

Таблица 2.7

ci	БП								bi
x1	x2	x3	x4	x5	x6	x7
	x5	9/13	7/13	3/13				- 1/13	108/13
	x6	66/13	47/13	22/13				- 3/13	1130/13
	x4	4/13	6/13	10/13				1/13	100/13
Dj	- 20	- 10	- 20

Из таблицы 2.7 находим опорный план:

, .

В индексной строке таблицы 2.7 имеется три отрицательные оценки. Полученное решение можно улучшить. Разрешающим элементом является а₁₁ =9/13.

3-я итерация.

Формируем следующую симплексную таблицу (таблица 2.8).

Из таблицы 2.8 находим опорный план:

, .

Таблица 2.8

ci	БП								bi
x1	x2	x3	x4	x5	x6	x7
	x1		7/9	1/3		13/9		- 1/9
	x6		-1/3			- 22/3		1/3
	x4		2/9	2/3		- 4/9		1/9
Dj		50/9	-40/3		260/9		70/9

В индексной строке таблицы 2.8 имеется одна отрицательная оценка. Полученное решение можно улучшить. Разрешающим элементом является а₃₃ =2/3.

4-я итерация.

Формируем следующую симплексную таблицу (таблица 2.9).

Таблица 2.9

ci	БП								bi
x1	x2	x3	x4	x5	x6	x7
	x1		2/3		- 1/2	5/3		- 1/6
	x6		- 1/3			- 22/3		1/3
	x3		1/3		3/2	- 2/3		1/6
Dj

Из таблицы 2.9 находим опорный план:

, .

Так как все оценки свободных переменных положительные, найденное решение является оптимальным:

, .

Максимальная прибыль составит 1320 ден. ед., при этом необходимо произвести 10 ед. продукции П₁ и 6 ед. продукции П₃. В оптимальном плане резервы трудовых ресурсов и оборудования равны нулю (х₅ = х₇ =0), так как они используются полностью. А резерв ресурсов сырья х₆ =26, что свидетельствует о его излишках.