Линейные оптимизационные модели

Построение ЭММ равновесия для задачи о поиске лучших вариантов использования ресурсов при заданных затратах и ценах. Выполнение эконометрического анализа модели.

Задание 1.

На предприятии имеется возможность выпускать 2 вида продукции П1 и П2. При её изготовлении используются ресурсы Р1 и Р2. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2. Расход ресурса i-того вида на единицу продукции jтого вида составляет аij единиц. Цена единицы продукции j-того вида равна Сj ден. ед. Для обеспечения сбыта и согласно спросу, продукция j-того вида должна производиться в размерах: не менее nj единиц, и не более mj единиц .

Требуется :

составить экономико — математическую модель задачи, позволяющую найти сбалансированный по ресурсам план выпуска продукции, обеспечивающий предприятию максимальный доход ;

графическим методом найти оптимальный план выпуска продукции по видам, дать содержательный ответ.

Все необходимые числовые данные приведены в таблице .

Решение типового варианта В-31.

1. Составим экономико-математическую модель задачи.

Обозначим через Х1, Х2 -количество единиц продукции соответственно П1, П2, планируемой к выпуску, а через fдоход от реализации этой продукции. Тогда, учитывая значения цены единицы продукции, суммарный доход — целевая функция — запишется в виде:

Переменные Х1, Х2 должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов:

По смыслу задачи:

Для обеспечения сбыта и согласно спросу, продукция П1, П2 должна производиться соответственно в размерах не более 100 и 30 единиц:

Соотношения (1)-(4) образуют экономико-математическую модель задачи:

Математически задача сводится к нахождению числовых значений Х1*, Х2*, удовлетворяющих линейным неравенствам (2)-(4) и доставляющих максимум линейной функции (1).

2. Решим задачу графическим способом.

Граничные прямые :

Областью допустимых решений задачи является многоугольник ОАВСД (рис1), ограниченный прямыми ОА с уравнением Х1=0, АВ с уравнением Х2=30, ВС с уравнением Х1+3Х2=120, СД с уравнением 3Х1+4Х2=240, ОД с уравнением Х2=0.

На рисунке построен вектор 10С=(20;30), указывающий направление наискорейшего возрастания функции f и разрешающая прямая fmax, параллельная вспомогательной прямой f=0. Разрешающая прямая засекает вершину С, в которой функция f достигает наибольшего значения в допустимой области ОАВСД. В результате совместного решения уравнений прямых ВС и СД, пересекающихся в точке С, находим её координаты:

Итак, по оптимальному плану следует изготовить 48 ед. продукции П1 и 24 ед. продукции П2 .При этом предприятие получит максимальный доход в размере 168 ден. ед. Причём, ресурсы Р1 и Р2 будут израсходованы полностью.

Задание Построить ЭММ равновесия для задачи о поиске лучших вариантов использования ресурсов при заданных затратах и ценах.

Предприятие ежемесячно имеет ресурсы трёх типов Р1, Р2,Р3, объёмы которых определяются величинами b1, b2, b3. Из этих ресурсов предприятие может организовать производство четырёх видов изделий П1, П2, П3, П4, причём продукция может производиться в любых соотношениях (сбыт обеспечен). У предприятия есть и другая альтернатива распорядиться ресурсамипродавать их (спрос на ресурсы имеется). Оценить эти два варианта с точки зрения наибольшей прибыли для предприятия.

Расход ресурсов на производство единицы изделия каждого типа aij и прибыль от реализации единицы изделия всех типов cj приведены в таблице.

Выполнить эконометрический анализ полученной модели.

Привести полученную задачу линейного программирования к каноническому виду. Объяснить смысл введённых балансовых переменных.

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

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

Определить дефицитность сырья и увеличение прибыли при изменении его объёма на единицу.

Определить цены на ресурсы, при которых прямая реализация их не менее выгодна, чем организация производства изделий из этих отходов. Рыночные цены на ресурсы соответствующего типа равны z1, z2, z3. Оценить целесообразность введения в план производства нового вида изделия П5, нормы затрат ресурсов на производство единицы продукции ai5 и прибыль от реализации единицы продукции c5 которого приведены в таблице.

Решение типового варианта В-31.

Обозначим через Х1, Х2, Х3, Х4 — количество единиц продукции соответственно П1, П2, П3, П4, планируемой к выпуску, а через fвеличину прибыли от реализации этой продукции. Тогда, учитывая значения прибыли от единицы продукции П1, П2, П3, П4 соответственно, суммарная величина прибыли — целевая функция — запишется в виде:

Переменные Х1, Х2, Х3, Х4 должны удовлетворять ограничениям, накладываемым на расход имеющихся в распоряжении предприятия ресурсов:

По смыслу задачи:

Соотношения (1)-(3) образуют экономико-математическую модель задачи. Математически задача сводится к нахождению числовых значений Х1*, Х2*, Х3*, Х4*, удовлетворяющих линейным неравенствам и доставляющих максимум линейной функции (1).

Выполним эконометрический анализ полученной модели.

Приведём модель к канонической форме: запишем ограничения задачи в виде равенств. Для этого введём в левые части неравенств дополнительные неотрицательные переменные Х5, Х6, Х7, обозначающие разности между правыми и левыми частями этих неравенств (возможные остатки ресурсов):

В модели (4) переменные Х5, Х6, Х7 являются базисными, а Х1, Х2, Х3, Х4 — свободными.

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

Составим 1-ую симплекс-таблицу:

Табл. 1.

Все элементы столбца свободных членов положительны, поэтому содержащийся в табл.1 план (0;0;0;0;2600;1800;500) является опорным, но он не оптимален, т.к. в fстроке имеются отрицательные элементы. Чтобы получить опорный план, более близкий к оптимальному, выполним симплексное преобразование табл.1. С этой целью выберем элементы, участвующие в преобразовании базиса Х5, Х6, Х7 в новый базис. Наибольший по модулю отрицательный элемент (-4) f-строки указывает, что в новый базис следует ввести переменную Х2, т. е. в качестве разрешающего в предстоящем симплексном преобразовании надо взять второй столбец. Чтобы определить переменную, выводимую из базиса, составляем симплексные отношения и выбираем наименьшее из них:

Итак, из базиса надо исключить переменную, стоящую в третьей (разрешающей) строке, т. е. Х7. На пересечении разрешающих столбца и строки находится разрешающий элемент 1, с которым и выполняется симплексное преобразование. В результате приходим к табл.2.

Симплексные преобразования — это правила пересчёта элементов симплекс-таблицы при переходе к новому опорному плану и заключаются они в следующем:

разрешающий элемент заменяется обратной величиной;

остальные элементы разрешающей строки делятся на разрешающий элемент;

остальные элементы разрешающего столбца делятся на разрешающий элемент и меняют знаки;

все остальные элементы таблицы вычисляются по формуле:

.

где aks — разрешающий элемент, aij — пересчитываемый элемент,.

ais — соответственный элемент разрешающего столбца, akj — соответственный элемент разрешающей строки, a? ij — элемент новой таблицы, стоящий в i — той строке и j — ом столбце на месте элемента aij.

В рассматриваемой задаче, например,.

Табл.2.

В f-строке таблицы 2 отрицательных элементов нет, следовательно, опорный план (0;500;0;0;100;300;0) является оптимальным, а соответствующее ему значение 2000 целевой функции будет максимальным.

Итак, по оптимальному плану следует изготовить 500 ед. продукции П2, а продукцию П1, П3 и П4 производить не следует (не выгодно). При этом предприятию будет обеспечена максимальная прибыль в размере 2000 ден. ед. Останутся неиспользованными 100 ед. ресурса Р1, 300 ед. ресурса Р2, а ресурс Р3 будет израсходован полностью.

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

Транспонируем матрицу (5). В результате получим матрицу (6) двойственной задачи:

По матрице (6) напишем модель задачи, двойственной к исходной:

Сформулируем в экономических терминах двойственную задачу.

Предположим, что некоторая организация хочет закупить все ресурсы, которыми располагает предприятие. Необходимо определить оптимальные цены на эти ресурсы, исходя из естественного условия, что покупающая организация стремится минимизировать общую оценку ресурсов. Учтём тот факт, что за ресурсы покупающая организация должна уплатить сумму, не меньшую той, которую может выручить предприятие при организации собственного производства продукции.

Итак, целевой функцией является общая оценка ресурсов, которую требуется минимизировать:

Yi-цены на эти ресурсы (i=1,3).

Из теорем двойственности следует, что если решена одна из пары двойственных задач, то одновременно найдено решение и другой задачи. Компоненты оптимального плана этой задачи Yi* находятся в строке целевой функции последней симплекс-таблицы решённой задачи.(табл.2). Выписать компоненты поможет соответствие между переменными двойственных задач. Для этого преобразуем ограничения-неравенства в эквивалентные уравнения, вычитая из левых частей дополнительные неотрицательные переменные У4, У5, У6, У7, равные разностям между левыми и правыми частями этих неравенств. Тогда модель (7)-(9) запишется в виде:

В этой модели переменные У4, У5, У6, У7 являются базисными, а У1, У2, У3 — свободными.

Сопоставим базисным переменным одной задачи свободные переменные двойственной задачи и наоборот.

Воспользовавшись соответствием, устанавливаем:

У1*=0; У2*=0; У3*=4; У4*=10; У5*=0; У6*=7; У7*=14.

Из теорем двойственности:

Итак, оптимальные цены на ресурсы составляют:

• — на единицу ресурса вида Р1: У1*=0 ден. ед.
• — на единицу ресурса вида Р2: У2*=0 ден. ед.
• — на единицу ресурса вида Р3: У3*=4 ден. ед. Т. е. при ценах У1*=0; У2*=0; У3*=4 на ресурсы соответствующего типа продажа их принесёт ту же прибыль (2000 ден. ед.), как и в случае продажи готовой продукции, вошедшей в оптимальный план.
• 4) Полученные условные оценки У1*, У2*, У3* являются мерой дефицитности ресурсов. Так как в нашей задаче

У1* =У2* =0, то ресурсы первого и второго типов недефицитны, они оказались в избытке, а оценка Уз* = 4 говорит о дефицитности ресурса третьего типа. Если положительных оценок в задаче несколько, то большей условной оценке соответствует наиболее дефицитный ресурс.

Условные оценки показывают, что увеличение сырья третьего типа на единицу приведет к увеличению прибыли на 4 ден.ед., и ее общая сумма станет равной 2004 ден. ед. Увеличение же на единицу сырья первого и второго типов не приведет к росту прибыли, так как ресурсы этих типов имеются в избытке.

5. В случае организации производства 500 ед. продукции второго вида сумма прибыли составит 2000 руб. При этом остается сырье: первого типа — 100 ед., второго — 300 ед., которое можно реализовать по рыночным ценам и общая сумма дохода составит.

z = 2000 + 100 * 0,1 + 300 * 0,2 = 2070 ден. ед.

В случае продажи всего сырья на товарном рынке предприятие должно установить такие цены, чтобы получить доход в размере 2070 ден. ед. Если соотношение рыночных цен на сырье составляет 0,1/0,2/0,5, то составим уравнение.

• 2600*0,1к+1800*0,2к+500*0,5к=2070. Откуда получим к=3,4, тогда цена на сырье первого типа должна быть равной 0,34 ден. ед., второго типа —
• 0,68 ден. ед., третьего — 1,7 ден. ед. Расчетные цены выше рыночных, следовательно, предприятию прямая реализация всего сырья менее выгодна, чем организация производства.
• 6. Если в план включаются новые виды продукции, то оценка целесообразности их введения определяется по формуле

где аij — объем ресурсов i-го типа, которые требуются на производство единицы продукции j-го вида, cj — прибыль от реализации единицы продукции j — го вида. В нашей задаче Так как ?5< 0, то прибыль превышает затраты и введение в план производства пятого вида изделия целесообразно.