Задание по дисциплине «Методы оптимальных управленческих решений» для МИСиС

Тема : Методы линейного программирования в принятии решений. Задание. Кондитерская фабрика производит 2 вида печенья П1 и П2, при изготовлении которых используются три вида сырья А, В и С. Месячные запасы этих сырьевых материалов, нормы их расхода на 1 т соответствующего продукта приведены в таблице. Какое количество печенья каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным. Решить задачу графически. После нахождения оптимального решения выяснить, как отразится на оптимальном решении изменение запасов ресурсов:

• на сколько можно увеличить запас ресурса для улучшения полученного оптимального значения целевой функции;
• на сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции;

Определить влияние на оптимальное решение изменения рыночных цен.

Сырьевые материалы	Расход сырьевых материалов (в тоннах) на производство 1 т печенья		Месячный запас, т
	П1	П2
А В С	10 1 2	15 1 1	100 7,5 12
Цена 1 т печенья	4	3

Решение: I Обозначим искомые переменные Х=( x₁,x₂₎ = объем выпуска продукции х₁— месячный объем производства печенья П1 х₂— месячный объем производства печенья П2 F(x)- доход Запись критерия оптимальности в виде целевой функции Целевая функция F(Х)=4x₁+ 3x₂ →max Критерий оптимальности- доход от реализации продукции, записывается в виде целевой функции. III Составим систему ограничений по расходу сырьевых материалов: Расход сырьевого материала «а» не должен превышать  его месячный запас: 10x₁+15x₂£100 Расход сырьевого материала «b» не должен превышать  его месячный запас: x₁+x₂£7,5 Расход сырьевого материала «c» не должен превышать  его месячный запас: 2x₁+x₂£12

	10x1+15x2£100
	x1+x2£7,5
	2x1+x2£12

Условия неотрицательности искомых переменных х₁≥0; х₂≥0. Модель является линейной, так как входящие в неё ограничения и целевая функция линейны (переменные в первой степени и нет их произведения). Первый шаг при использовании графического метода заключается в построении области допустимых решений, в которой одновременно удовлетворяются все ограничения модели. Условия неотрицательности искомых переменных х₁≥0; х₂≥0 ограничивают область  их допустимых значений (на координатной плоскости х₁х₂ ) первым квадрантом . Другие границы пространства решений изображаются на координатной плоскости х₁х₂ прямыми линиями, которые получаются при замене знака  ≤  на знак  = в остальных ограничениях. Построим по двум точкам граничную прямую для ограничения 1.

Ряд 1	10x1+15x2=100
x1	0	10
x2	6,666666667	0

Построим по двум точкам граничную прямую для ограничения 2.

Ряд 2	x1+x2=7,5
x1	0	7,5
x2	7,5	0

Построим по двум точкам граничную прямую для ограничения 3

Ряд 3	2x1+x2=12
x1	0	6
x2	12	0

Пространство решений  — многоугольник ABCDE. В каждой точке, принадлежащей внутренней области или границам многоугольника ABCDE, все ограничения выполняются. Решения, соответствующие этим точкам, являются допустимыми. Чтобы найти оптимальное решение, необходимо выяснить, в каком направлении возрастает целевая функция модели. На график наносят линии уровня, соответствующие произвольно выбранным значениям F(x₁,x₂). Это позволяет определить наклон линии уровня и направление, в котором происходит увеличение целевой функции. Пусть F(x)= 12. Построим линию уровня по двум точкам. 4x₁+ 3x₂ = 12

x1	0	3
x2	4	0

Перемещаем линию уровня вверх до тех пор, пока она не сместиться в область недопустимых решений. Оптимальному решению соответствует пересечение граничных прямых 2 и 3. 6). Решаем систему уравнений и получаем координаты точки, в которой будет оптимальное решение: Ограничения 2 и 3 x1+x2=7,5 2×1+x2=12 х₁*=4,5; х₂*=3 F(Х)=4x₁+ 3x₂    Максимальный доход  F(X*)= 4*4,5+3*3=27 После нахождения оптимального решения необходимо выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Насколько можно увеличить запас ресурса для улучшения полученного оптимального значения целевой функции. Ресурсы В и С являются дефицитными, так как расходуются полностью за производственный цикл. Дефицитным ресурсам соответствуют связывающие ограничения . Граничная прямая, представляющая связывающее ограничение, должна проходить через оптимальную точку. Если же прямая не проходит через оптимальную точку, значит ресурс недефицитный. А — недефицитный ресурс В и С — дефицитные ресурсы Определим на сколько можно увеличить запасы дефицитных ресурсов. 1) Произведем увеличение ресурса В. Если перемещать граничную прямую 2 выше до точки пересечения ограничений 1 и 3,ограничение 2 становиться избыточным, так как дальнейший рост запаса этого ресурса не влияет ни на пространство решений, ни на оптимальное решение Находим новую точку оптимума как точку пересечения 1 и 3: Решаем систему ограничений 1 и 3. 10×1+15×2=100 2×1+x2=12 х₁=4; х₂=4 Подставим координаты Х(4;4,) в ограничение 2: x₁+x₂=4+4=8 — max разумный запас ресурса В. Соответствующая ему величина дохода F(Х)=4x₁+ 3x₂ = 4*4+3*4= 28. 2)  Произведем увеличение ресурса С. Перемещаем ограничение 3 параллельно самой себе вправо до последней точки касания с прямой 2 и получаем новую точку оптимума: Подставим координаты Х(7,5;0) в ограничение 3: 2x₁+x₂= 7,5*2+0=15- max разумный запас ресурса С.Соответствующая ему величина дохода F(x)=4x₁+ 3x₂ =4*7,5+0= 30. Дальнейший рост запаса этого ресурса не влияет ни на пространство решений, ни на оптимальное решение. 3)  Чтобы понять какому из ресурсов отдать предпочтение, сведем данные в таблицу:

Ресурс	максимальное изменение запаса ресурса	новая точка оптимума (x1, x2)	максимальное изменение дохода (F(x)=4x1+ 3x2)
В	8-7,5= 0,5	(4;4)	28-27=1
С	15-12=3	(7,5;0)	30-27=3

Обозначим ценность дополнительной единицы ресурса  через y, тогда: y= Ресурс В    y₁ =1/0,5=  2 Ресурс С    y₂ =3/3=     1 y_{1 >} y₂ следовательно дополнительные вложения целесообразно в первую очередь  направить на увеличение ресурса В. На сколько можно снизить запас недефицитного ресурса при сохранении  полученного оптимального значения целевой функции.  У нас остался последний ресурс А, и он  является недефицитным. 1)Произведем снижение ресурса А Перемещаем граничную прямую 1 параллельно самой себе вниз  до точки пересечения граничных прямых  2 и 3(точка оптимума). Подставим координаты Х*(4,5;3) в ограничение 1: 10x₁+15x₂ = 10*4,5+15*3=90 – минимально возможный запас А. Соответствующая ему величина дохода F(x)=4x₁+ 3x₂ = 4*4,5+3*3= 27. Можно сделать  вывод, что  уменьшение  запаса ресурса А до 90т не влияет на  доход. Определить влияние на оптимальное решение изменения рыночных цен. Другими словами требуется определить допустимый диапазон  изменения коэффициентов целевой функции, при котором не происходит изменения оптимального решения Х*(4,5;3)  . Уравнение линии уровня в общем виде  c₁x₁+c₂x₂=z (const), где c₁и c₂ – цены на продукцию П1 и П2 соответственно. Тангенс угла наклона линии уровня равен с₁/с₂. Аналогично находим тангенсы угла наклона связующих ограничений: Для 2 ограничения тангенс угла наклона  равен 1. Для 3 ограничения тангенс угла наклона  равен 2. Точка [4,5;3] будет оптимальной точкой, пока наклон прямой не выйдет за пределы, определенные наклонами прямых 2 и 3. 1<c1/c2<2 Найдем пределы изменения дохода: для этого подставим в целевую функцию максимальное (max) и минимальное (min) значения с₁, а значения х₁ и х₂ возьмем из оптимального решения. Аналогичные расчеты делаем для коэффициента с₂ (рыночная цена продукции П2) пусть C1=const  = 4 Пределы изменения дохода: Задача для решения (по вариантам)  Менеджеру производственной фирмы требуется составить оптимальный по прибыли план выпуска запчастей двух видов, используя для этого ресурсы трех типов. Их запасы ограничены значениями в₁, в₂, в₃  соответственно. Пусть а₁₁, а₁₂  количество ресурсов  первого типа, расходуемых на запчасти  каждого  вида,  соответственно. Аналогичный смысл имеют  символы  а₂₁, а₂₂  и    а₃₁, а₃₂. Ожидаемая прибыль от реализации одной запчасти каждого вида составляет с₁, с₂  условных единиц, соответственно. Требуется: а) записать условия задачи в таблицу стандартной формы; б) решить задачу  графоаналитическим способом (на миллиметровке); в) решить  задачу табличным  симплекс-  методом г) решить  задачу  в  среде  EXCEL в) составить и решить двойственную  задачу, указать  дефицитные  ресурсы,  выяснить, как изменится  оптимальная прибыль при увеличении запасов каждого  из дефицитных   ресурсов на 5 единиц, соответственно. Исходные данные: в₁ = 300 — 5V, в₂ = 120-2V,  в₃ = 252-, с₁= 30, с₂ = 40,  а₁₁= 12,  а₁₂= 4, а₂₁ =  4, а₂₂ = 4 ,    а₃₁ =3,  а_{3 2}= 12.