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

Решим симплекс-методом задачу из раздела 1.1. Для этого вначале нужно привести ее к канонической форме. Это было сделано в разделе 1.4.1. В такой задаче есть готовый базис: переменные x₃, x₄и x₅. Исходная симплексная таблица примет вид таблицы 11 (столбцыJи К предназначены для вспомогательных расчетов).

Таблица 11 – Исходная симплексная таблица для задачи производственного планирования

		A		B	C		D	E	F	G	H	I	J	K
1								108	140	0	0	0
2		N		xб	cб		B	x1	x2	x3	x4	x5
3		1		x3	0		800	0,8	0,5	1	0	0	1000	1600
4		2		x4	0		600	0,2	0,4	0	1	0	3000	1500
5		3		x5	0		120	0,01	0,1	0	0	1	12000	1200
6		m+1					0	-108	-140	0	0	0	-108000	-168000

Критерий оптимальности нарушен в двух столбцах x₁и x₂. Следовательно, чтобы увеличить значение прибыли, надо увеличить (включить в базис) любую из этих переменных.

Если выбрать переменную x₁, то разрешающим элементом будет а₁₁, так какmin{800/0,8; 600/0,2; 120/0,01} =min{1000; 3000; 12000} = 1000. Тогда прибыль возрастет на 1000*108 = 108000. Если выбрать переменную x₂, то разрешающим элементом будет а₃₂, так какmin{800/0,5; 600/0,4; 120/0,1} =min{1600; 1500; 1200} = 1200. Тогда прибыль возрастет на 1200*140 = 168000. Так как 168000 > 108000, лучше ввести в базис x₂.

Описанные расчеты нет необходимости осуществлять вручную. Можно, например, ввести в J3 формулу =$D3/E3, а затем скопировать ее на К3 и J4:К5. В результате в диапазоне ячеек J3:К5 будут получены те отношения, из которых выбирается наименьшее. Если бы какой-либо из коэффициентов в столбцах Е и F был неположительным, то в столбцах J и К появилось бы отрицательное число или сообщение о попытке деления на ноль. Выбрать наименьшее из положительных отношений в такой задаче можно вручную. Затем в J6 можно ввести формулу =$D3/E3, а в К6 - =F6*K5. Результаты вычислений приведены в таблице 11. Для вспомогательных расчетов можно использовать любые свободные ячейки.

Итак, в базис войдет x₂, при этом из базиса выходит x₅, и таблица примет вид таблицы 12 (обе части третьего ограничения делят на 0,1; а из остальных трех строк вычитают преобразованное третье ограничение, умноженное соответственно на 0,5; 0,4 и -140).

Таблица 12 – Вторая симплексная таблица для задачи производственного планирования

N	xб	cб	B	x1	x2	x3	x4	x5
1	x3	0	200	0,75	0	1	0	-5
2	x4	0	120	0,16	0	0	1	-4
3	x2	140	1200	0,1	1	0	0	10
m+1			168000	-94	0	0	0	1400

Здесь критерий оптимальности нарушен только в одном столбце - x₁. Так какmin{200/0,75; 120/0,16; 1200/0,1} =min{266 2/3; 750; 12000} = = 266 2/3, из базиса выйдет x₃. Таблица примет вид таблицы 13 (обе части первого ограничения делят на 0,75; а из остальных трех строк вычитают преобразованное первое ограничение, умноженное соответственно на 0,16; 0,1 и -94).

Таблица 13 – Оптимальная симплексная таблица для задачи производственного планирования

N	xб	cб	B	x1	x2	x3	x4	x5
1	x1	108	266,67	1	0	1,3333	0	-6,6667
2	x4	0	77,333	0	0	-0,2133	1	-2,9333
3	x2	140	1173,3	0	1	-0,1333	0	10,667
m+1			193067	0	0	125,33	0	773,33

Таблица оптимальна, так как в критериальной строке нет отрицательных коэффициентов. Из таблицы видно, что решением задачи будет Х^* = (266,67; 1173,3; 0; 77,333; 0), z^*=19306,7. Если изменить формат ячеек на дробный, то ответ совпадет с полученным в разделе 2.1.

Ответ задачи: кондитерской фабрике следует выпускать 266,7 т карамели «Снежинка» и1173,3 т карамели «Яблочная». При этом сахарный песок и фруктовое пюре будут израсходованы полностью (так как x₃= x₅=0), а остаток патоки составит 77,3 т. Максимальная прибыль составит 193067 руб.