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

Неизвестные. Число неизвестных в двойственной задаче равно числу функциональных ограничений в исходной задаче. Исходная задача содержит 3 ограничения: по труду, сырью и оборудованию. Следовательно, в двойственной задаче – 3 неизвестных:

Y ₁ – двойственная оценка ресурса «труд», или «цена» труда;

Y ₂ – двойственная оценка ресурса «сырье», или «цена» сырья;

Y ₃ – двойственная оценка ресурса «оборудование», или «цена» оборудования.

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

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

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

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

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

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

2 Y ₁ + 4 Y ₂ + Y ₃ ³ 3,

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

Y ₁ , Y ₂ , Y ₃ ³ 0.

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

тогда

Y ₁ (7 X ₁ +2 X ₂ +2 X ₃ +6 X ₄ – 80) = 0,

Y ₂ (5 X ₁ +8 X ₂ +4 X ₃ +3 X ₄ – 480) = 0,

Y ₃ (2 X ₁ +4 X ₂ + X ₃ +8 X ₄ – 130) = 0.

Подставим оптимальные значения вектора в полученные выражения:

Y ₁ (7´0 +2´30 +2´10 +6´0 – 80) = 0,

Y ₂ (5´0 +8´30 +4´10 +3´0 – 480) =0,

Y ₃ (2´0 +4´30 +1×10 +8´0 – 130) = 0

и получим:

Y ₁ (80 – 80) = 0,

Y ₂ (280 – 480) = 0, так как 280 < 480, то Y ₂=0,

Y ₃ (130 – 130) = 0.

Воспользуемся вторым соотношением второй теоремы двойственности:

Х1(7 Y ₁ + 5 Y ₂ + 2 Y ₃ – 3)=0,

Х2(2 Y ₁ + 8 Y ₂ + 4 Y ₃ – 4)=0,

Х3(2 Y ₁ + 4 Y ₂ + Y ₃ – 3)=0,

Х4(6 Y ₁ + 3 Y ₂ + 8 Y ₃ – 1)=0

В нашей задаче Х ₂=30>0 и Х ₃=10>0, поэтому второе и третье ограничения двойственной задачи обращаются в равенства:

2 ´ Y ₁ + 8´ Y ₂ + 4´ Y ₃ = 4,

2 ´ Y ₁ + 4´ Y ₂ + 1´ Y ₃ = 3,

Y ₂= 0.

Решая полученную систему уравнений, находим Y ₁и Y ₃.

Теневые цены ресурсов «труд», «сырье» и «оборудование» соответственно равны Y ₁ = 4/3, Y ₂ = 0, Y ₃ = 1/3, или в десятичных дробях 1,3333; 0; 0,3333.

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

g = 80´ Y ₁ + 480´ Y ₂ + 130´ Y ₃ = 80 ´4/3 + 480´0+ 130´1/3=150,

f = 3´ Х ₁ +4´ Х ₂ +3´ Х ₃ + Х ₄= 3´0 +4´30 +3´10 +0=150.

Это означает, что оптимальный план двойственной задачи определен верно.

Ответ на вопрос о равенстве нулю x ₁ и x ₄ будет дан позже.

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

Отчет по устойчивости. Отчет поустойчивости состоит из двух таблиц (табл.2.5.6) Первая таблица содержит информацию, относящуюся к переменным:

· Результат решения задачи.

· Нормированная стоимость, которая показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение. Например, в отчете по устойчивости для рассматриваемой задачи (табл. 2.5.6) нормированная стоимость для ковров первого вида равна –7 тыс. руб./шт. (строка 1). Это означает, что если мы, несмотря на оптимальное решение (0; 30; 10; 0), попробуем включить в план выпуска один ковер первого вида, то новый план выпуска принесет нам доход 143 тыс. руб., что на 7 тыс. руб. меньше, чем прежнее оптимальное решение.

· Коэффициенты целевой функции.

· Предельные значения приращения целевых коэффициентов , при которых сохраняется первоначальное оптимальное решение. Например, допустимое увеличение цены на ковер первого вида равно 7 тыс. руб./шт., а допустимое уменьшение – практически не ограничено (строка 1 на табл. 1.5). Это означает, что если цена ковра первого вида возрастет более чем на 7 тыс. руб./шт., то оптимальное решение изменится: станет целесообразным выпускать X ₁. А если их цена будет снижаться вплоть до нуля, то оптимальное решение (0; 30; 10; 0) останется прежним.

Во второй таблице (табл. 1.5) содержится информация, относящаяся к ограничениям:

· Величина использованных ресурсов в колонке Результ. значение.

· Предельные значения приращения ресурсов . В графе Допустимое уменьшение показано, на сколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптимальное решение. Рассмотрим анализ дефицитных ресурсов. Анализируя отчет по результатам, мы установили, что существуют причины (ограничения), не позволяющие фабрике выпускать большее ковров, чем в оптимальном решении, и получать более высокий доход. В рассматриваемой задаче такими ограничениями являютсядефицитные ресурсы “труд” и “оборудование”. Поскольку знак ограничений этих запасов имеет вид , то возникает вопрос, на сколько максимально должен возрасти запас этих ресурсов, чтобы обеспечить увеличение выпуска продукции. Ответ на этот вопрос показан в графе Допустимое увеличение. Ресурс “труд” имеет смысл увеличить самое большее на 150 чел./дней, а ресурс “оборудование ” – на 30 станко/часов.

· Ценность дополнительной единицы ресурса i (теневая цена) рассчитывается только для дефицитных ресурсов.

Таблица 2.5.6. Содержание отчета по устойчивости.

	Ячейка	Имя	Результирующее значение	Нормируемая стоимость	Целевой коэффициент	Допустимое увеличение	Допустимое уменьшение
	$B$3	Значение Х1		-7			1E+30
	$C$3	Значение Х2
	$D$3	Значение Х3					1.75
	$E$3	Значение Х4		-9.667		9.667	1E+30
Ограничения
	Ячейка	Имя	Результирующее значение	Теневая цена	Ограничение правая часть	Допустимое увеличение	Допустимое уменьшение
	$F$7	труд левая часть		1.333
	$F$8	сырье левая часть				1E+30
	$F$9	Оборудование левая часть		0.333

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

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

Ресурсы «труд» и «оборудование» имеют отличные от нуля оценки 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), поэтому имеет нулевую двойственную оценку (Y ₂=0).

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

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

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

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

= 80 ´ Y ₁ + 480´ Y ₂ + 130´ Y ₃ = 80 ´ 4/3 +480 ´ 0+130´1/3 =150 тыс. руб.

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

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

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

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

Если стоимость ресурсов, затраченных на производство одного изделия, больше его цены, то это изделие не войдет в оптимальный план из-за его убыточности. В нашей задаче в план выпуска не вошли ковры первого и четвертого видов, потому что затраты по ним превышают цену на 7 (10–3=7) тыс. руб. и 9,666 (10,666–1=9,666) тыс. руб. соответственно. Этот факт можно подтвердить, подставив в ограничения двойственной задачи оптимальные значения вектора 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.

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

1. Сравним результаты решения задачи, полученные вручную с помощью симплексных таблиц и полученные в Поиске решения. В таблице 2.5.7 приведено решение задачи о коврах симплексным методом вручную. Все симплекс-разности второй симплексной таблицы неотрицательны, следовательно, оптимальный план получен. Решения исходной и двойственной задач содержатся в последней симплексной таблице. Оптимальный план исходной задачи равен , значение целевой функции при этом равно . При решении ЗЛП с помощью симплексных таблиц решение двойственной задачи содержится в последней строке последней симплексной таблицы (это ). При чем основные переменные двойственной задачи содержатся в столбцах, соответствующих дополнительным переменным исходной задачи , а дополнительные переменные двойственной задачи содержатся в столбцах, соответствующих основным (первоначальным) переменным исходной задачи . В Поиске решения дополнительные переменные двойственной задачи содержатся в Отчете по устойчивости (табл. 2.5.6) в столбце Нормируемая стоимость (с обратными знаками).

Таблица 2.5.7. Решение задачи о коврах симплексным методом.

№	Базис	Cj Ci	План								Q
A1	A2	A3	A4	A5	A6	A7
	A5
	A6
	A7										32.5
				-3	-4	-3	-1
	A5					1.5				-0.5
	A6						-13			-2
	A2		32.5	0.5		0.25				0.25
				-1		-2
	A3						1.3333	0.6667		-0.333
	A6			-7			-15.67	-1.333		-1.333
	A2			-0.5			1.6667	-0.167		0.3333
							9.6667	1.3333		0.3333

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

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

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

Таблица 2.5.8. Отчет по устойчивости 2.

Отчет по устойчивости 2
Изменяемые ячейки
			Результирующее	Нормируемая	Целевой	Допустимое	Допустимое
	Ячейка	Имя	значение	стоимость	коэффициент	увеличение	уменьшение
	$B$3	значение Х1		-7			1E+30
	$C$3	значение Х2
	$D$3	значение Х3					1.75
	$E$3	значение Х4		-9,667		9,667	1E+30
Ограничения
			Результирующее	Теневая	Ограничение	Допустимое	Допустимое
	Ячейка	Имя	значение	цена	правая часть	увеличение	уменьшение
	$F$7	труд левая часть		1,333
	$F$8	сырье левая часть				1E+30
	$F$9	оборудование левая часть		0,333

[1] Материал по этой теме можно найти в

Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решению задач. – 2-е изд., испр. и доп. - М.: Вузовский учебник: ИНФРА-М, 2012.

Дата добавления: 2014-12-27