Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

Оценка целесообразности выпуска новой продукции

Пример №1. Для изготовления трех видов продукции используют два типа сырья. Запасы сырья, нормы его расхода и цены реализации единицы каждого вида продукции приведены в таблице.
Тип сырья Нормы расхода сырья на одно изделие Запасы сырья
АБВ
I 3 2 4 200
II 2 1 3 160
Цена изделия 4 3 5
При решении задачи на максимум общей стоимости выпускаемой продукции (вся готовая продукция реализуется) были получены следующие результаты: х1 = 0, х2 = 100, х3 = 0.
Требуется:
1) сформулировать прямую оптимизационную задачу на максимум общей стоимости выпускаемой продукции, пояснить нулевые значения х1, х3;
2) сформулировать двойственную задачу и найти ее оптимальный план;
3) проанализировать использование ресурсов в оптимальном плане;
4) определить, как изменятся общая стоимость продукции и план ее выпуска при увеличении запасов сырья I типа на 6 единиц и уменьшении на 10 единиц запасов сырья II типа;
5) определить целесообразность включения в план изделия «Г» ценой 6 ед., на изготовление которого расходуется 5 ед. сырья типа I и 2 ед. сырья типа II.

Решение.
Обозначим через х1, х2 и х3 − объем выпуска изделий вида «А», «Б» и «В» соответственно. Запишем математическую модель задачи:
max (4x1 + 3x2 + 5x3), (1)
3x1 + 2x2 + 4x3 ≤ 200, (2)
2x1 + x2 + 3x3 ≤ 160, (3)
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0. (4)
В этой модели функциональные ограничения (2)-(3) отражают условия ограниченности объемов, используемых в производстве ресурсов.
Проверим, как удовлетворяется система функциональных ограничений оптимальным планом Х* = (х1 = 0, х2 = 100, х3 = 0):
3∙0 + 2∙100 + 4∙0 = 200, (5)
2∙0 + 100 +3∙0 =100 < 160. (6)
Значение целевой функции (1) на этом плане равно
f(Х*) = 4∙0 + 3∙100 + 5∙0 = 300.
Отметим, что нулевые значения х1 и х3 означают нецелесообразность выпуска изделий вида «А» и «В» с точки зрения принятого критерия оптимальности.
Двойственная задача имеет вид:
min (200y1 + 160y2), (7)
3y1 + 2y2 ≥ 4, (8)
2y1 + y2 ≥ 3, (9)
4y1 + 3y2 ≥ 5, (10)
y1 ≥ 0, y2 ≥ 0. (11)
Для нахождения двойственных оценок y1 и y2 используем вторую теорему двойственности.
Если при подстановке компонент оптимального плана в систему ограничений исходной задачи i-е ограничение обращается в неравенство, то i-я компонента оптимального плана двойственной задачи равна нулю.
Если j-я компонента оптимального плана исходной задачи положительна, то j-е ограничение двойственной задачи удовлетворяется ее оптимальным решением как строгое равенство.

Теорема позволяет, если известно оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.
Поскольку второе ограничение прямой задачи (см. соотношение (6)) выполняется как строгое неравенство, то y2 = 0. Так как х2> 0, то второе ограничение двойственной задачи (см. соотношение (9)) выполняется как равенство:
2y1 + y2 = 3.
Итак, для получения двойственных оценок имеем систему линейных уравнений:
y2 = 0,
2y1 + y2 = 3,
т.е. Y* = (y1 = 3/2, y2 = 0).
Экономико-математический анализ оптимальных решений базируется на свойствах двойственных оценок. В пределах устойчивости двойственных оценок имеют место следующие свойства.
1. Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными, (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны). В примере недефицитным ресурсом является сырье II-го типа, поскольку y2 = 0. Дефицитным является сырье I-го типа, так как y1 = 3/2.
2. Величина двойственной оценки того или иного ресурса показывает, насколько возросло бы максимальное значение целевой функции, если бы объем данного ресурса увеличился на одну единицу (двойственной оценкой измеряют эффективность малых приращений объемов ресурсов в конкретных условиях данной задачи).
Заданные в примере изменения запасов ресурсов Δb1 = 6 и Δb2 =−10 находятся в пределах устойчивости двойственных оценок, поэтому:
− решение двойственной задачи останется тем же: Y* = (y1 = 3/2, y2 = 0);
− изменение максимального значения целевой функции (общей стоимости продукции) составит
Δfmax = y1∙Δb1 + y2∙Δb2 = (3/2)∙6 + 0∙(−10) = 9;
− новый план выпуска продукции можно найти непосредственно из системы ограничений исходной задачи, в которой х1 = 0, х3 = 0, а в правых частях указаны новые запасы ресурсов (b1' = 200 + 6 = 206, b2' = 160 − 10 = 150):
3∙0 + 2∙х2' + 4∙0 = 206,
2∙0 + х2' +3∙0 < 150,
откуда х2' = 103.
Итак, максимальное значение целевой функции составит
f(Х'*) = 4∙0 + 3∙103 + 5∙0 = 309
при оптимальном плане производства Х'* = (х1' = 0, х2' = 103, х3' = 0).
3. Двойственные оценки служат инструментом определения эффективности отдельных хозяйственных решений (технологических способов), с их помощью можно определять выгодность производства новых изделий, эффективность новых технологических способов:
если ∆j=∑aijyi – cj≤ 0 – выгодно,
если ∆j>0 – невыгодно.
Для изделия «Г»:
Г = 5∙(3/2) + 2∙0 – 6 = 3/2.
Поскольку ∆Г = 3/2 > 0, то делаем вывод, что изделие «Г» невыгодно для включения в план, так как затраты на его изготовление больше цены, за которую его можно продать.

Пример №2. Задача. На предприятии имеется возможность выпускать n видов продукции (1,2,…n). При ее изготовлении используются ресурсы Р1, Р2, Р3. Размеры прямых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход i –го ресурса на единицу продукции j-того вида составляют aij. Цена единицы продукции j-того вида равна cj ден. ед. Сформулировать прямую и двойственную задачу и раскрывать экономический смысл всех переменных.
Требуется:
Найти оптимальный план симплекс-методом.
Найти решение двойственной задачи
Указать дефицитность ресурсов
Обосновать эффективность плана производства
Оценить целесообразность приобретения ресурса
Оценить целесообразность выпуска новой продукции

Данные:
b1 = 25, b2 = 30, b3 = 42
a11= 2, a12= 3, a13= 2, a14= 1
a21= 4, a22= 1, a23= 3, a24= 2
a31= 3, a32= 5, a33= 2,a34= 2
c1= 6, c2= 5, c3= 4, c4= 3
Математическая модель прямой задачи
max (Z= 6x1+5x2+4x3+3x4)
2x1+3x2+2x3+x4< 25
4x1+x2+3x3+2x4< 30
3x1+5x2+2x3+2x4< 42
x1, x2, x3, x4 > 0

Перейти к онлайн решению своей задачи

Математическая модель двойственной задачи
min (Z*= 25y1+30y2+42y3)
2y1+4y2+3y3> 6
3y1+y2+5y3> 5
2y1+3y2+2y3> 4
y1+2y2+2y3> 3
y1, y2, y3, y4 > 0

Стандартный вид

min (Z= -6x1-5x2-4x3-3x4)
2x1+3x2+2x3+x4+S1=25
4x1+x2+3x3+2x4+S2=30
3x1+5x2+2x3+2x4+S3=42
x1, x2, x3, x4, S1, S2, S3 > 0

Экономический смысл переменных
Xi – количество произведенной продукции
Yj – цена ресурса
Si – количество оставшегося ресурса

базис значение x1 x2 x3 x4 S1 S2 S3 отношение
Z 0 -6 -5 -4 -3 0 0 0
S1 25 2 3 2 1 1 0 0 12,5
S2 30 4 1 3 2 0 1 0 7,5
S3 42 3 5 2 2 0 0 1 14
Таблица 2
базис значение x1 x2 x3 x4 S1 S2 S3 отношение
Z 45 0 -3,5 0,5 0 0 1,5 0
S1 10 0 2,5 0,5 0 1 -0,5 0 4
x1 7,5 1 0,25 0,75 0,5 0 0,25 0 30
S3 19,5 0 4,25 -0,3 0,5 0 -0,8 1 4,59
Таблица 3
базис значение x1 x2 x3 x4 S1 S2 S3 отношение
Z 59 0 0 1,2 0 1,4 0,8 0
x2 4 0 1 0,2 0 0,4 -0,2 0
x1 6,5 1 0 0,7 0,5 -0,1 0,3 0
S3 2,5 0 0 -1,1 0,5 -1,7 0,1 1

Анализ решения
Продукции 1 вида производим 6,5 ед., второго вида 4 единицы, третьего и четвертого вообще не производим. Прибыль при этом составит 59 ден. единиц.
Ресурс 1 типа стоит 1,4 ден. ед., 2 типа – 0,8 ден. ед. Третий тип ресурса у нас остался в количестве 2,5 ед., поэтому его покупать не нужно.
Ресурсы 1 и 2 типа дефицитны, 3 типа избыточен.

Эффективность производства
Z = 6*6.5+5*4+4*0+3*0=59 Z*=25*1.4+30*0.8+42*0=59 Производство в целом эффективно
2*1,4+4*0,8+3*0< 6 6=6 Производство 1 вида продукции эффективно
3*1,4+1*0,8+5*0< 5 5=5 Производство 2 вида продукции эффективно
2*1,4+3*0,8+2*0< 4 5,2> 4 Производство 3 вида продукции не эффективно
1*1,4+2*0,8+2*0< 3 3=3 Т.к. x4 не входит в базис, то оптимальный план не единственен.

Оценить целесообразность покупки 5 ед. второго ресурса по цене 10 ден. ед, т.е. единица ресурса обойдется нам в 2 ден. ед. Мы же готовы покупать только по 0,8 ден. ед. за 1 единицу ресурса.
а1 = 2, а2 = 2, а3 = 4. Цена новой продукции равна 4.
2*1,4+2*0,8+2*0< 4 4,4> 4
Производство 5 вида продукции не эффективно.

Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Нелинейное программирование
Метод Лагранжа
Метод множителей Лагранжа
Решить онлайн
Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее
Курсовые на заказ