Решение оптимизационных задач средствами Excel

2Х₁ +4Х₂ +Х₃ +8Х₄130

Целевая функция двойственной задачи формулируется на минимум. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи.

g = 80 Y₁ + 480Y₂ + 130Y₃ min

Необходимо найти такие "цены" на ресурсы (Y_i), чтобы общая стоимость используемых ресурсов была минимальной.

Ограничения. число ограничений в системе двойственной задачи равно числу переменных в исходной задаче. В исходной задаче четыре переменных, следовательно, в двойственной задаче четыре ограничения. Правыми частями в ограничениях двойственной задачи являются коэффициенты при неизвестных в целевой функции исходной задачи. Левая часть ограничения определяет стоимость ресурсов, затраченных на производство единицы продукции. Каждое ограничение соответствует определенному виду продукции.

7 Y₁ + 5Y₂ + 2Y₃ 3

2 Y₁ + 8Y₂ + 4Y₃ 4

2 Y₁ + 4Y₂ + 1Y₃ 3

6 Y₁ + 3Y₂ + 8Y₃ 1

Y₁, Y₂, Y₃ 0

Решение двойственной задачи можно найти в отчете Поиска решений. Отчет по устойчивости.

Теневые цены ресурсов труд, сырье и оборудование соответственно равны 4/3, 0, 1/3 или в десятичных дробях 1.3333, 0, 0.3333.

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

1) Анализ использования ресурсов в оптимальном плане выполняется с помощью соотношений второй теоремы двойственности.

Ресурсы труд и оборудование имеют отличные от нуля оценки 4/3 и 1/3 - эти ресурсы полностью используются в оптимальном плане, являются дефицитными, сдерживающими рост целевой функции.

Правые части этих ограничений равны левым частям.

7Х₁ +2Х₂ +2Х₃ +6Х₄ 80

2Х₁ +4Х₂ +Х₃ +8Х₄130

70 +230 +210 +60=80=80

20 +430 +110 +80=130=130

Ресурс сырье используется не полностью (280480), поэтому имеет нулевую двойственную оценку (Y2=0).

5Х₁ +8Х₂ +4Х₃ +3Х₄480

50 +830 +410 +30=280<480

Этот ресурс не влияет на план выпуска продукции.

Общая стоимость используемых ресурсов при выпуске 30 ковров второго вида и 10 ковров третьего вида составит 150 тыс. руб.

g = 80 Y₁ + 480Y₂ + 130Y₃ =80 4/3 +4800+1301/3 =150 тыс. руб.

По условию (4) не использованный полностью в оптимальном плане ресурс получает нулевую оценку. Нулевая оценка ресурса свидетельствует о его не дефицитности. Ресурс не дефицитен не из-за его неограниченных запасов (они ограничены величиной bi), а из-за невозможности его полного использования в оптимальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производства им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию f(X).

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

2) Анализ эффективности отдельных вариантов плана выполняется на основе соотношений из 2 теоремы двойственности.

Если изделие вошло в оптимальный план (Xj >0), то в двойственных оценках оно не убыточно, то есть, стоимость ресурсов, затраченных на производство единицы изделия равна его цене. Такие изделия эффективны, выгодны с точки зрения принятого критерия оптимальности. В нашей задаче это ковры второго и третьего видов.

Если стоимость ресурсов, затраченных на производство одного изделия больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В нашей задаче в план выпуска не вошли ковры первого и четвертого видов, потому что затраты по ним превышают цену на 7 (10-3) тыс. руб. и 9.666 (10.666-1) тыс. руб. соответственно. Это можно подтвердить, подставив в ограничения двойственной задачи оптимальные значения вектора Y.

7 4/3 + 50+ 21/3=30/3=10 3

2 4/3 + 80+ 41/3=12/3= 4= 4

2 4/3 + 40+ 11/3= 9/3= 3= 3

64/3 + 30+ 81/3=32/3= 10.666 1

Разницу между правыми и левыми частями ограничений двойственной задачи можно найти в Отчете по устойчивости в столбце Нормируемая стоимость.

2) Анализ влияния изменения правых частей ограничений на значения целевой функции (Чувствительность решения к изменению запасов сырья).

Предположим, что запас сырья ресурса "труд" изменился на 12 единиц, т. е. теперь он составляет 80 + 12 = 92 единиц. Из теоремы об оценках, известно, что колебание величины bi приводит к увеличению или уменьшению f(X). Оно определяется величиной yi в случае, когда при изменении величин bi значения переменных yi в оптимальном плане соответствующей двойственной задачи остаются неизменными. В нашей задаче увеличение запасов ресурса "труд" приведет к увеличению значения целевой функции на 16 тыс. руб.(f(x)= b1 y1 =124/3 = 16). Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивность этих векторов (значения неизвестных) в плане могут меняться.

Поэтому необходимо знать такие интервалы изменения каждого из свободных членов системы ограничений исходной ЗЛП, или интервалы устойчивости двойственных оценок, в которых оптимальный план двойственной задачи не менялся бы. Эту информацию можно получить из Отчета по устойчивости. В нашей задаче в ниже приведенном фрагменте отчета видно, что запасы дефицитных ресурсов труд и оборудование могут быть, как уменьшены, так и увеличены, увеличение запаса ресурса сырье не повлияет на план выпуска продукции.

После увеличения запаса ресурса труд до 92 чел/ часов было получено новое решение задачи. Изменение запасов ресурсов в пределах интервалов устойчивости двойственных оценок привело не только к изменению значения целевой функции на 16 тыс. руб., но и к изменению плана выпуска. При этом структура плана не изменилась - изделия, которые были убыточны не вошли и в новый план выпуска, т.к. цены на ресурсы не изменились. Новый план выпуска составляет 28 ковров второго вида и 18 ковров третьего вида. Изменение общей стоимости продукции на 16 тыс. руб. (24-8=16) получено за счет уменьшения на 2 единицы ковров второго вида по цене 4 тыс. руб. (4 тыс. руб.(28-30)= -8 тыс. руб.) и увеличения на 8 единиц ковров третьего вида по цене 3 тыс. руб. (3 тыс. руб.(18-10)= 24 тыс. руб.).

Задача 5.

Задача о размещении производственных заказов

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

Необходимо найти такой вариант распределения объемов производства продукции и капитальных вложений по филиалам, при котором суммарная стоимость изделий будет минимальной.

Таблица

В результате решения получен план распределения объемов производства по филиалам предприятия

Требуется:

1) Сформулировать экономико-математическую модель прямой и двойственной задачи.

2) Найти оптимальный план двойственной задачи, используя теоремы двойственности.

Решение

1) Экономико-математическая модель исходной задачи.

Xi - объем выпускаемой продукции на i-м филиале предприятия.

= 83X₁+89X₂+95X₃+98X₄ -> min,

Ограничения

X₁+X₂+X₃+X₄ 300 (тыс. штук)

120X₁+80X₂+50X₃+40X₄ 18 (млн.руб.),

X₁,_2,3,4 0.

Экономико-математическая модель двойственной задачи.

Y₁ - двойственная оценка выпускаемой продукции, которая может быть ценой изделия;

Y₂ - двойственная оценка капитальных вложений, которая может быть представлена как коэффициент эффективности капитальных вложений.

g =300000 Y₁+18000000 Y₂ -> mах

1 Y₁+120Y₂ 83

1 Y₁+ 80Y₂ 89

1 Y₁+ 50Y₂ 95

1 Y₁+ 40Y₂ 98

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

().

0+100000+200000+0 = 300000

1200+80100000+50200000+40 = 18000000

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

).

В нашей задаче Х₂=100000>0 и Х₃=200000>0, поэтому второе и третье ограничения двойственной задачи обращаются в уравнения, решая которые найдем Y₁ и Y₂ .

1Y₁ + 50Y₂ = 95Y₁= 105 - средняя цена изделия

1Y₁ + 80Y₂ = 89Y₂= -0.2 - двойственная оценка капитальных вложений.

105 =95 +50 0.2 = 105

105 =89+ 800.2 = 105

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

Проверим выполнение первой теоремы двойственности.

g=300000Y₁+18000000Y₂=300000105+18000000(-0.2) = 279000000

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

В каждой задаче требуется:

Определить план выпуска продукции из условия максимизации его стоимости.

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

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

На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

Кроме того, в каждом варианте необходимо выполнить еще два пункта задания.

Вариант 1

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

Определить, как изменятся общая стоимость продукции и план ее выпуска при увеличении запасов сырья I и II вида на 4 и 3 единицы соответственно и уменьшении на 3 единицы сырья III вида.

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

Вариант 2

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

5. Определить, как изменятся общая стоимость продукции и план выпуска при увеличении запасов сырья II и III вида на 120 и 160 ед. соответственно и одновременном уменьшении на 60 ед. запасов сырья I вида;

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

Вариант 3

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

5. Определить, как изменится общая прибыль продукции и план выпуска при увеличении запасов сырья I и III вида на 4 ед. каждого;

6. Определить целесообразность включения в план изделия "Г", на изготовление которого расходуется соответственно 1, 3 и 2 ед. каждого вида сырья ценой 13 ед. и изделия "Д" на изготовление которого расходуется по две единицы каждого вида сырья ценой 12 ед.

Вариант 4

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

5. Определить, как изменится общая стоимость продукции и план выпуска при увеличении запасов сырья I и II вида на 8 и 10 ед. соответственно и одновременном уменьшении на 5 ед. запасов сырья III вида;

6. Определить целесообразность включения в план изделия "Д" на изготовление которого расходуется по две единицы каждого вида сырья и ожидается прибыль 10 ед.

Вариант 5

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

5. Определить, как изменится общая стоимость продукции и план выпуска при увеличении запасов сырья на 18 единиц;.

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

Вариант 6

На предприятии выпускается три вида изделий, используется при этом три вида сырья:

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида увеличить на 45 кг., а II - уменьшить на 9кг.?

6. Целесообразно ли выпускать изделие Г ценой 11 единиц, если нормы затрат сырья 9, 4 и 6 кг.?

Вариант 7

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

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида увеличить на 24?

6. Целесообразно ли выпускать изделие четвертого вида ценой 11 единиц, если нормы затрат ресурсов 8, 4, 20 и 6 единиц.?

Вариант 8

Предприятие выпускает 4 вида продукции и использует 3 типа основного оборудования: токарное, фрезерное, шлифовальное.

Затраты на изготовление единицы продукции приведены в таблице; там же указан общий фонд рабочего времени, а также цена изделия каждого вида.

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если фонд времени шлифовального оборудования увеличить на 24 часа ?

6. Целесообразно ли выпускать изделие "Д" ценой 11 единиц, если нормы затрат оборудования 8, 2 и 2 ед.?

Вариант 9

На предприятии выпускается три вида изделий, используется при этом три вида сырья:

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида увеличить на 80 кг., а II - уменьшить на 10кг.?

6. Целесообразно ли выпускать изделие Г ценой 7 единиц, если нормы затрат сырья 2, 4 и 3 кг.?

Вариант 10

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

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида увеличить на 100 кг, а II - уменьшить на 150кг.?

6. Целесообразно ли выпускать изделие "Д" ценой 10 единиц, если нормы затрат сырья 2, 4 и 3 кг?

Список литературы, имеющейся в библиотеке ВЗФЭИ