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

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

 

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

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

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

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

 

Y₁ ,Y₂ ,Y₃ ³ 0

Решение двойственной задачи можно найти  в отчете Поиска решений. Отчет по устойчивости. Теневые цены ресурсов труд, сырье и оборудование соответственно равны 4/3, 0, 1/3 или  в десятичных дробях 1.3333,  0,   0.3333.

 

 

Отчет по устойчивости
Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	Значение	Стоимость	Коэффициент	Увеличение	Уменьшение
	$B$3	Значение Х1	0	-7	3	7	1E+30
	$C$3	Значение Х2	30	0	4	8	1
	$D$3	Значение Х3	10	0	3	1	1.75
	$E$3	Значение Х4	0	-9.667	1	9.667	1E+30
Ограничения
			Результ.	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	Значение	Цена	Правая часть	Увеличение	Уменьшение
	$F$7	труд левая часть	80	1.333	80	150	15
	$F$8	сырье левая часть	280	0	480	1E+30	200
	$F$9	Оборудование левая часть	130	0.333	130	30	90

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

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

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

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

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

7´0 +2´30 +2´10 +6´0=80=80

2´0 +4´30 +1´10 +8´0=130=130

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

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

5´0 +8´30 +4´10 +3´0=280<480

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

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

g = 80 ´Y1 + 480´Y2 + 130´Y3 =80 ´4/3 +480´0+130´1/3 =150 тыс. руб.

 

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

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

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

 

 

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

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

7 ´4/3 + 5´0+ 2´1/3=30/3=10 >3

2 ´4/3 + 8´0+ 4´1/3=12/3= 4= 4

2 ´4/3 + 4´0+ 1´1/3= 9/3= 3= 3

6´4/3 + 3´0+ 8´1/3=32/3= 10.666 > 1

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

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

Предположим, что запас сырья ресурса «труд» изменился на 12 единиц, т. е. теперь он составляет 80 + 12 = 92 единиц. Из теоремы  об оценках, известно, что колебание величины b_i приводит к увеличению или уменьшению f(X). Оно определяется величиной y_i в случае, когда при изменении величин b_i значения переменных y_i в оптимальном плане соответствующей двойственной задачи остаются неизменными. В нашей задаче увеличение запасов ресурса «труд»  приведет к увеличению значения целевой функции на 16 тыс. руб.(Df(x)= D b₁´ y₁ =12´4/3 = 16). Для двойственных оценок оптимального плана весьма существенное значение имеет их предельный характер. Точной мерой влияния ограничений на функционал оценки являются лишь при малом приращении ограничения. Известно, что оценки не меняют своей величины, если не меняется набор векторов, входящих в базис оптимального плана, тогда как интенсивность этих векторов (значения неизвестных) в плане могут меняться.

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

Ограничение	Допустимое	Допустимое
правая часть	Увеличение	уменьшение
80	150	15
480	1E+30	200
130	30	90

 

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

 

Отчет по устойчивости 2
Изменяемые ячейки
			Результ.	Нормир.	Целевой	Допустимое	Допустимое
	Ячейка	Имя	значение	Стоимость	коэффициент	увеличение	уменьшение
	$B$3	значение Х1	0	-7	3	7	1E+30
	$C$3	значение Х2	28	0	4	8	1
	$D$3	значение Х3	18	0	3	1	1.75
	$E$3	значение Х4	0	-9.667	1	9.667	1E+30
Ограничения
			Результ.	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	значение	цена	правая часть	увеличение	уменьшение
	$F$7	труд левая часть	92	1.333	92	138	27
	$F$8	сырье левая часть	296	0	480	1E+30	184
	$F$9	оборудование левая часть	130	0.333	130	54	84

 

Задача 5.

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

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

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

Таблица

Показатель	Филиал предприятия
	1	2	3	4
Себестоимость производства изделия, руб.	83	89	95	98
Удельные капиталовложения, руб.	120	80	90	40

 

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

Филиал предприятия
1	2	3	4
0	100 тыс. штук	200 тыс. штук	0

 

Требуется:

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

 Решение

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

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

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

Ограничения

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

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

X_1,2,3,4 ³0.

 

	83	89	95	98
Y1	1	1	1	1	300000
Y2	120	80	50	40	18000000

 

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

 

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

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