5.3. Решение задачи оптимального ассортиментного выпуска продукции

Решение планово-экономических задач c линейной моделью может быть получено графическим способом (с количеством неизвестных не более двух) и с помощью матричного симплексного метода (с любым числом неизвестных).

Для иллюстрации симплексного метода используем исходные данные табл. 5.1.

Задача состоит в определении оптимального выпуска каждого вида карамели (Х₁, Х₂, Х₃), удовлетворяющего неравенствам ( 5.2 ) и максимизирующего общую сумму прибыли ( 5.3 )

Коэффициенты в неравенствах ( 5.2 ) означают удельные нормы расхода основных видов сырья a_ij,, постоянные величины правых частей неравенств - общие запасы сырья b_i., коэффициенты в уравнении целевой функции - уровни прибыли на 1 т выпускаемой продукции С_j..

Для решения задачи симплексным методом необходимо исходные неравенства ( 5.2 ) преобразовать в систему эквивалентных равенств. Для этого введем дополнительные неизвестные Х₄, Х₅, Х₆ (фиктивные продукты, имеющие нулевые уровни прибыли), которые будут равно нулю если всё сырье будет использовано на выпуск трех видов карамели, или представлять часть сырья, которая может остаться неиспользованной при выпуске указанных продуктов.

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

0,7Х₁ + 0,7Х₂ + 0,7Х₃ + 1Х₄ + 0Х₅ + 0Х₆ = 700

0,3Х₁ + 0,3Х₂ + 0,2Х₃ + 0Х₄ + 1Х₅ + 0Х₆ = 300 ( 5.8 )

0Х₁ + 0,2Х₂ + 0,3Х₃ + 0Х₄ + 0Х₅ + 1Х₆ = 150

Целевая функция:

F = 100Х₁ + 110 Х₂ + 120 Х₃ + 0Х₄ + 0Х₅ + 0Х₆ = max . ( 5.9 )

Для решения задачи сформируем симплексную таблицу, которая состоит из четырех основных частей: верхушки, корпуса, основания и целевой строки (табл. 5.2).

Таблица 5.2

Сj	P0	X0	100	110	120	0	0	0	Верхушка
			Х1	Х2	Х3	Х4	Х5	Х6	Таблицы
0	Х4	700	0,7	0,7	0,7	1	0	0
0	Х5	300	0,3	0,3	0,2	0	1	0
0	Х6	150	0	0,2	0,3	0	0	1
Коэф. при неизве-стных	Номера неизв., входящих в прогр.	0	-100	-110	-120	0	0	0	Целевая строка
		Значение целевой функции

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

В столбце Р₀ записываются дополнительные неизвестные Х₄, Х₅, Х₆, а затем, в процессе решения, номера неизвестных, включаемых в программу выпуска. В столбце С_j соответствующие им коэффициенты в уравнении целевой функции.

Столбец Х₀ называется итоговым. В нем записываются свободные величины, значения которых в симплексных таблицах изменяются в процессе вычислений. Показатели столбца указывают количество фиктивных продуктов, которое может быть выпущено при реализации плана, приведенного в табл. 5.3.

Расход сырья на единицу фиктивного продукта определяется коэффициентами при дополнительных неизвестных. Но так как эти коэффициенты равны 1, то величина выпускаемых фиктивных продуктов равняется запасам сырья, из которого вырабатывается каждый из этих продуктов: X₄ = 700 /1 = 700, X₅ = 300 /1 = 300, Х₆= 150 /1 = 150.

При введении в программу выпуска реальных видов продуктов показатели столбца Х₀ отражают количество продукции, включенное в план выпуска.

Как видно из уравнения целевой функции и показателей столбца C_j,

Уровень прибыли фиктивных продуктов равен нулю:

F =  X_0iC_i = 7000 + 3000 + 1500 = 0.

Это значение записывается на пересечении итогового столбца и целевой строки. Оно будет соответствовать данному этапу решения (значение целевой функции).

Целевая строка заполняется данными, получаемыми расчетным путем. При расчете коэффициенты при неизвестных a_ij (нормы расхода) каждого столбца умножаются на соответствующие величины столбца C_j (уровни прибыли) и полученные произведения суммируются:

Z_j =  a_ij C_j . ( 5.10 )

Из полученной по столбцу суммы вычитается уровень прибыли этого столбца C_j, записанной в верхушке таблицы: Z_j - C_j .

Например, величина записи в целевой строке рассчитывается так:

по столбцу Х₁ Z₁ = 0,70 + 0,30 = 0, 0 - 100 = -100;

по столбцу Х₂ Z₂ = 0,70 + 0,30 + 0,20 = 0, 0 - 110 = -110;

по столбцу Х₃ Z₃ = 0,70 + 0,20 + 0,30 = 0, 0 - 120 = -120;

по столбцу Х₄ Z₄ = 10 + 00 + 00 = 0, 0 - 0 = 0 и т.д.

Перед преобразованием элементов симплексной таблицы определяют ключевой столбец (с наименьшей прибылью) и ключевую строку (с минимальным значением X_0j /a_kj – ключевого столбца).

В нашем примере ключевой столбец Х₃, а ключевая строка Х₆ для которой 150/0,3 = 500 является минимальным значением.

Продукция, которая записана в ключевой строке Х₆ исключаются из плана выпуска и на ее место записывается продукция, которая включается в план производства Х₃. Ключевая строка и ключевой столбец выделяется. Элемент (коэффициент), стоящий на пересечении ключевого столбца и ключевой строки, называется ключевым (в нашем примере это коэффициент 0,3).

После определения ключевых столбца и строки показатели плана по симплексному алгоритму преобразуются в новый вариант плана (табл. 5.3).

В новую таблицу из предыдущей записывается преобразованная ключевая строка, в которой вместо Х₆ записывается вводимый в план выпуска продукт Х₃ ,а на место С₃. его уровень прибыли (120), остальные показатели делятся на ключевой элемент (0,3).

Правила преобразования элементов ключевой строки и всех остальных строк матрицы можно представить так:

1. Преобразованные Старые элементы ключевой строки

элементы ключевой = .

строки Ключевой элемент

2. Преобразованные Соответствующие Соответствующие

элементы всех = Старые - элементы х элементы

остальных строк элементы ключевой строки ключевого столбца

Следуя этому правилу, преобразуем элементы ключевой строки (см. табл. 5.3):

150 / 0,3 = 500; 0 / 0,3 = 0; 0,2 / 0,3 = 0,67; 0,3 / 0,3 = 1; 0 / 0,3 = 0; 0 / 0,3 = 0; 1 / 0,3 = 3,33.

По правилу 2 преобразуем показатели первой, второй и целевой строк:

1 строка: X₀: 700–5000,7=350; X₁: 0,7-00,7=0,7; X₂: 0,7-0,670,7=0,23; X₃: 0,7-10,7=0;

X₄: 1-00,7=1; X₅: 0-00,7=0; X₆: 0-3,330,7=-2,33.

Целевая строка: X₀: 0–500(-120)=60000; X₁: -100–0(-120)=-100; X₂: -110–0,67(-120)=-30;

X₃: -120–1(-120)=0; X₄: 0–0(-120)=0; X₅: 0–0(-120)=0; X₆: 0–3,33(-120)=400.

Все преобразованные элементы вписаны в табл. 5.3. Включение в план выпуска карамели М₃, позволяет получить сумму прибыли 60 тыс. руб. Полученный план не оптимален, поскольку два элемента в ней имеют отрицательные значения. Ключевой строкой в этой таблице является первая (Х₄), а ключевым столбцом Х₁, следовательно в план выпуска будет вводиться карамель М₁, так как она обеспечивает получение наибольшей прибыли (100).

Таблица 5.3

Сj	P0	X0	Х1	Х2	Х3	Х4	Х5	Х6
0	Х4	700	0,7	0,7	0	1	0	-2,33
0	Х5	300	0,3	0,3	0	0	1	-0,67
120	Х3	500	0	0,2	1	0	0	3,33
Zj - Cj		60000	-100	-30	0	0	0	400	Целевая строка

Новая таблица 5.4 строится следующим образом. Элементы строки Х₃ переносятся из таблицы 5.3 без изменения. Ключевая строка преобразовывается по правилу ( 1 ), строка Х₅ и целевая строка по правилу ( 2 ).

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

Таблица 5.4

Сj	P0	X0	Х1	Х2	Х3	Х4	Х5	Х6
100	Х1	500	1	0,33	0	1,43	0	-3,33
0	Х5	50	0	0,07	0	-0,43	1	0,33
120	Х3	500	0	0,67	1	0	0	3,33
Zj - Cj		110000	0	3	0	143	0	67	Целевая строка

Оптимальный план производства продукции предусматривает выпуск карамели М₁ 500 т и карамели М₃ 500 т, выпуск карамели М₂ в план не вошел, при этом сумма прибыли предприятия составит 110 тыс. руб., а элемент Х₅ = 50 означает, что останется 50 т неиспользованной патоки при выпуске продукции.