Теоремы двойственности и их экономическое содержание

Первая теорема двойственности: если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций совпадают: z(x*) = f(y*). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

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

x1	x2		xj		xn	xn+1	xn+2		xn+i		xn+m
↕	↕		↕		↕	↕	↕		↕		↕
ym+1	ym+2		ym+j		ym+n	y1	y2		yi		ym

Отсюда имеем оптимальный план двойственной задачи. Если прямая задача решается на максимум, то

Если прямая задача решается на минимум, то

Пример.Исходя из специализации, предприятие может выпускать четыре вида продукции П_j  используя для этого три вида сырья С_i  Общие объемы имеющегося сырья b_i, нормы их расхода на единицу продукции и цена реализации единицы каждого вида продукции представлены в табл.4.1

Таблица 4.1

Требуется:

1) определить оптимальный ассортимент выпускаемой продукции, доставляющий предприятию максимум Выручки;

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

Решение Пусть х = (х₁; х₂; х₃; х₄;) – план выпуска. Математическая модель задачи:

В табл. приведены две последние итерации решения задачи симплексным методом.

Таблица 4.2

Так как все оценки после второй итерации неотрицательны, то найденный опорный план оптимален:

х^*₂ = (0; 0; 400; 550 ê0; 0; 50), z(х^*₂) = 90 000.

Первый и второй ресурсы используются полностью, а третьего остается в избытке 50 ед.

2. Составим модель двойственной задачи:

Ее решение выпишем из индексной строки симплексной таблицы, используя соответствие переменных:

Имеем: y^* = (30; 15; 0 ê0; 75; 0; 0), f(y^*) = 90 000.

Вторая теорема двойственности (о дополняющей нежесткости): для того чтобы планы х* и y* пары двойственных задач были оптимальными, необходимо и достаточно выполнение условий:

Условия (1) и (2) называются условиями дополняющей нежесткости. Из них следует: если какое-либо неравенство системы ограничений одной из задач не обращается в строгое равенство оптимальным планом этой задачи, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в строгое равенство, т. е. если , то  если > 0, то  Точно так же: если  то = 0, если > 0, то  Экономически это означает, что если по некоторому оптимальному плану х* производства расход i- го ресурса строго меньше его запаса b_i, то в оптимальном плане соответствующая двойственная оценка единицы этого ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствующего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положительную оценку, а избыточный ресурс (используемый не полностью) имеет нулевую оценку.

Пример.Продукция в цехе может производиться тремя технологическими способами Т_j Объемы ресурсов b_i и их расход в единицу времени для каждой технологии, а также производительности технологий (в денежных единицах за единицу времени работы по данной технологии) представлены в табл.4.3

Таблица 4.3

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

РешениеЗапишем модель прямой и двойственной задачи:

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

Оптимальный план использования технологий х* =(60; 0; 12 ê0; 0; 180), z(х^*) = 23 400, т. е. первую техолдогию целесообразно применять в течение 60 ч, третью – 12 ч, вторую технологию применять нецелесообразно. При этом продукции будет выпущено на 23 400 ден.ед.

Таблица 4.4

Решение двойственной задачи:

y^* = (12; 60; 0 ê0; 170; 0), f(y^*) = 23 400.

Так как  y₁* = 12 > 0, y₂* = 60 > 0,то первый и второй ресурсы используются полностью. Третий ресурс избыточен: х₁* = 180. Его двойственная оценка равна нулю: y₃* = 0. Таким образом, если при j-м технологическом способе производства суммарная оценка ресурсов, необходимых для производства единицы продукции, равна доходу с_j. Проверим условие о дополняющей нежесткости.

Для прямой задачи:

Для двойственной задачи:

Условия (1) и (2) выполняются.

Третья теорема двойственности: двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения ЗЛП, т. е.

¶z(x*)/¶b_i = y_i*    (3)

Выясним экономическое содержание третьей теоремы двойственности. Для этого в выражение (3) дифференциалы заменим приращениями, т. е. ¶b_i » Db_i, ¶z(x*) » D z(x*). Получим D z(x*) = y_i*Db_i; при Db_i = 1 имеем D z(x*) = y_i*. Отсюда двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки y_i часто называются скрытыми, теневыми или маргинальными оценками ресурсов.

Пример. В задаче о выборе оптимальных технологий (предыдущий пример) выяснить экономический смысл двойственных переменных.

РешениеИз табл.* найдено решение двойственной задачи:

y^* = (12; 60; 0 ê0; 170; 0), f(y^*) = 23 400.

Как следует из решения, первый ивторой ресурсы потребляются полностью. Их двойственные оценки положительны. Приращение первого ограниченного ресурса на единицу времени ведет к увеличению целевой функции на 12, второго – на 60, третий ресурс избыточен: х₆* = 180. Его двойственная оценка равна нулю: y₃* = 0. Поэтому дальнейшее его увеличение не влияет на значение дополнительных двойственных оценок y₄* = 0, y₅* = 170, y₆* = 0? Оптимальный план исходной задачи

х^* = (60; 0; 12 ê0; 0; 180), z(х^*) = 23 400

говорит о том, что первую технологию целесообразно использовать в течение 60 ч,третью – 12 ч. Вторая технология вообще не должна внедряться: она заведомо убыточная. Если ее все же использовать, то она в течение каждого часа работы будет снижать достигнутый уровень выпуска на y₅* = 170 ден. ед. Значения y₄* = y₆* = 0 свидетельствует о том, что первая и третья технологии являются неубыточными. В самом деле, из второго ограничения двойственной задачи следует:

20y₁ + 3 y₂ + 60 y₃ – y₅ = 250.

Стоимость ресурсов, используемых в единицу времени при работе по второму технологическому способу, составит

20y₁* + 3 y₂* + 60 y₃* = 20 × 12 + 3 × 60 + 60 × 0 = 420 ден. ед.

В единицу же времени этот способ может дать продукции на 250 ден. ед. Поэтому убыток в единицу времени при работе этим способом составит y₅* = 420 – 250 = 170 (ден. ед.).