Часть ш. Примеры решения задач Задание № 3. Задача об оптимальной производственной программе

Предприятие планирует выпускать четыре вида продукции. Объемы ресурсов трех видов (в условных единицах - УЕ), затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции (в условных денежных единицах - УДЕ) приведены в таблице.

Вид продукции Вид ресурса	П1	П2	П3	П4	Объем (УЕ)
Р1	3	2	4	5	4800
Р2	3	0	4	4	4200
Р3	10	8	6	8	10000
Цена на единицу продукции (УДЕ)	48	50	45	50

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

Вопросы:

1. Сколько продукции каждого вида следует производить?

2. Какова ожидаемая максимальная выручка от продажи продукции?

3. Выяснить, какой из ресурсов наиболее дефицитен, какой из видов продукции наиболее убыточен?

4. Определить пределы устойчивости двойственных оценок к изменению запасов ресурсов?

5. На сколько изменится максимальная выручка, если запасы ресурсов каждого вида уменьшатся на 100 единиц?

Решение

Для того, чтобы ответить на поставленные вопросы, необходимо:

а) построить модель исходной и двойственной задач;

б) решить исходную задачу симплексным методом;

в) найти оптимальное решение двойственной задачи;

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

Составим экономико-математическую модель данной (исходной) задачи (задачи об оптимальной производственной программе или задачи об оптимальном распределении ресурсов):

Z = 48x₁ + 50x₂ + 45x₃ + 50x₄  max, (1)

3x₁ + 2x₂ + 4x₃ + 5x₄  4800, (2)

3x₁ + 4x₃ + 4x₄  4200, (3)

10x₁ + 8x₂ + 6x₃ + 8x₄  10000, (4)

x_j  0,

а) Исходная задача записана в стандартной симметричной форме, поэтому построим двойственную ей ЗЛП, пользуясь правилами построения двойственных задач:

f = 4800у₁ + 4200у₂ + 10000у₃  min (5)

3у₁ + 3у₂ +10у₃  48, (6)

2у₁ + 8у₃  50, (7)

4у₁ + 4у₂ + 6у₃  45, (8)

5у₁ + 4у₂ + 8у₃  50, (9)

у₁  0, у₂  0, у₃ 0. (10)

б) Для решения ЗЛП симплексным методом необходимо ее записать в канонической форме

max Z = 48x₁ + 50x₂ + 45x₃ + 50x₄ + 0·(x₅ + x₆ + x₇) (11)

3x₁ + 2x₂ + 4x₃ + 5x₄ + x₅ = 4800, (12)

2x₁ + 4x₃ + 4x₄ + x₆ = 4200, (13)

10x₁ + 8x₂ + 6x₃ + 8x₄ + x₇ = 10000. (14)

Решение задачи проводим в симплекс-таблицах (таблица 1.1). Первоначальный опорный план – допустимое базисное решение, которое получаем из расширенной матрицы А системы уравнений (12 – (14).

3 2 4 5 1 0 0 4800

А ~ 2 0 4 4 0 1 0 4200

10 8 6 8 0 0 1 10000

Таблица 1.1

Номер		Базисные переменные	Ci б	План bi	48	50	45	50	0	0	0	Qij=bi /aij
симплекс-таблицы	строки i				X1	X2	X3	X4	X5	X6	X7
I	1	X5	0	4800	3	2	4	5	1	0	0	2400; 960 
	2	X6	0	4200	3	0	4	4	0	1	0	1050
	3	X7	0	10000	10	8	6	8	0	0	1	1250; 1250
	4	Zm = 0			Δ1=-48	Δ2=-50	Δ3=-45	Δ4=-50	Δ5=0	Δ6=0	Δ7=0	Q14=min; a14=5 - разреша-ющий элемент
II	1	X4	50	960	3/5	2/5	4/5	1	1/5	0	0	2400
	2	X6	0	360	3/5	-8/5	4/5	0	-4/5	1	0
	3	X7	0	2320	26/5	24/5	-2/5	0	-8/5	0	1	483,3 
	4	Zm = 48000			Δ1=-18	Δ2=-30	Δ3= -5	Δ4= 0	Δ5=10	Δ6=0	Δ7=0	Q32=min; a32=24/5-разреша-ющий элемент
Ш	1	X4	50	2300/3	1/6	0	5/6	1	1/3	0	-1/12	920 
	2	X6	0	3400/3	7/3	0	2/3	0	-4/3	1	1/3	1700
	3	X2	50	1450/3	13/12	1	-1/12	0	-1/3	0	5/24
	4	Zm = 62500			Δ1=14,5	Δ2=0	Δ3=-7,5	Δ4=0	Δ5=0	Δ6=0	Δ7=6,25	Q13 = min; a13=5/6 –разреша-ющий элемент
IV	1	X3	45	920	1/5	0	1	6/5	2/5	0	-1/10
	2	X6	0	520	11/5	0	0	-4/5	-8/5	1	2/5
	3	X2	50	560	11/10	1	0	1/10	-3/10	0	1/5
	4	Zm = 69400			Δ1=16	Δ2 = 0	Δ3=0	Δ4= 9	Δ5= 3	Δ6=0	Δ7=5,5	Все Δj  0, отсюда план -оптимален
					У4*	У5*	У6*	У7*	У1*	У2*	У3*

По критерию оптимальности полученный план оптимален, т.е. х₂^*= 560, х₃^*= 920, х₆^*=520, х₁^*= х₄^*= х₅^*= х₇^*= 0, т.е. Х^* = (0; 560; 920; 0; 0; 520; 0).

в) Из последней строки IV-ой симплекс-таблицы определяем оптимальный план двойственной задачи

Y^* = (3; 0; 5,5; 16; 0; 0; 9).

Экстремальное значение целевой функции Z_max = f_min = 69400.

г) Оптимальное решение двойственной задачи (объективно-обусловленные оценки) Y^* показывает, что производство продукции вида П₂ и П₃ (им соответствуют нулевые оценки y₅ и y₆) – рентабельно, а П₁ и П₄ – убыточно. Наиболее убыточным является производство П₁ (т.к. 16>9). Дефицитный ресурс имеет положительную оценку, т.е. Р₁ и Р₃ – дефицитные ресурсы (запасы – х₅ и х₇ -равны нулю). Поскольку 5,5 > 3, то ресурс Р₃ более дефицитен, чем Р₁.

Для того, чтобы найти пределы устойчивости двойственных оценок к изменению запасов ресурсов, построим матрицу D, обратную к матрице Ã. В основной матрице коэффициентов А выберем векторы, соответствующие базисным переменным в оптимальном решении (х₂, х₃, х₆).

2 4 0

à ~ 0 4 1

8 6 0

Определитель матрицы

2 4 0

Δ(Ã) = 0 4 1 = 20 ≠ 0,

8 6 0

т.е. обратная к Ã матрица существует. Транспонируем матрицу Ã

2 0 8

Ã^Т ~ 4 4 6

0 1 0

и к каждому элементу матрицы Ã^Т найдем алгебраическое дополнение:

Аналогично, А₂₁ = 8; А₂₂ = 0; А₂₃ = -2; А₃₁ = -32; А₃₂ = 20; А₃₃ = 8.

Таким образом, матрица

-6 0 4 - 0,3 0 0,2

D = Ã^-1 ~ (1/20) 8 0 -2 = 0,4 0 -0,1

-32 20 8 -1,6 1 0,4

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

Сначала последовательно перенумеруем базисные перменные х_k (k=1,2,3):

х₁ =х₂^*= 560, х₂ =х₃^*= 920, х₃ = х₆^*=520.

Каждая строка матрицы D соответствует своей переменной х_k (k=1,2,3), а каждый столбец – двойственной переменной у_i (у₁ = 3, у₂ = 0, у₃ = 5,5).

Определим отклонение в нижнюю сторону для ресурса Р₁. Находим положительные элементы в первом столбце матрицы D. Это d₂₁ = 0,4, соответствующий х₂ = 920. Отсюда

{x₂/d₂₁} = 920/0,4 = 2300.

Определим отклонение в верхнюю сторону для ресурса Р₁. Находим отрицательные элементы в первом столбце матрицы D. Это d₂₁ = -0,3, соответствующий х₁ =560 и d₃₁ = -1,6, соответствующий х₃ = 520.

Отсюда верхняя граница

Δb₁⁺ = |max{x_k/d_k1}|=|max{-560/0,3; -520/1,6}|=|max{-1867; -325}| =|-325| = 325.

Таким образом, в интервале изменений запасов ресурса первого вида

b₁ {b₁ - ; b₁ + Δb₁⁺} = {4800 - 2300; 4800 + 325} = {2500; 5125}

сохранится теневая (внутренняя) цена на этот вид ресурса у₁^*= 3 УДЕ.

Точно также найдем интервалы устойчивости у₂^* =0 и у₃^* =5,5 (УДЕ).

b₂ {b₂ - ; b₂ + Δb₂⁺} = {4200 - 520; 4200 + 0} = {3680; 4200};

b₃ {b₃ - ; b₃ + Δb₃⁺} = {10000 - 1300; 10000 + 9200} = {8700; 19200}.

Изменение экстремального значения целевой функции исходной задачи при уменьшении объема каждого отдельно взятого ресурса на 100 УЕ считаем по Ш-ей теореме двойственности Z = b_i · y_i (i=1,2,3).

Для Р₁ - Z _{b1 =-100} = 3 · (-100) = -300 (УДЕ); для Р₂ - Z _{b2 =-100} = 0 – недефицитный вид ресурса; для Р₃ - Z _{b3 = -100} = 5,5· (-100) = -550(УДЕ).

Ответы на вопросы:

1. Каждого вида продукции следует производить: П₁= 0 (УЕ), П₂= 560 (УЕ), П₃ = 920 (УЕ), П₄ = 0 (УЕ).

2. Ожидаемая максимальная выручка от продажи продукции составляет Zmax = 69400 (УДЕ).

3. Наиболее дефицитен ресурс Р3, наиболее убыточным является производство продукции вида П1.

4. Пределы устойчивости двойственных оценок к изменению запасов ресурсов: b1 {2500; 5125}; b2 {3680; 4200}; b3 {8700; 19200}.

5. Если запасы ресурсов каждого вида уменьшатся на 100 единиц, то максимальная выручка для Р1 – уменьшится на 300 УДЕ; для Р2 - останется без изменений и для Р3 - уменьшится на 550 УДЕ.