Теория двойственности в задачах линейного программирования. Анализ полученных оптимальных решений

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

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

Переменные двойственной задачи y_i называют объективно обусловленными оценками, или двойственными оцен­ками, или «ценами» ресурсов, или теневыми ценами.

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

Двойственная задача по отношению к исходной состав­ляется согласно следующим правилам:

1) целевая функция исходной задачи формули­руется на максимум, а целевая функция двойственной задачи— на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид £, в задаче на минимум — вид ³;

2) матрица А, составленная из коэффициентов при неизвестных в сис­теме ограничений исходной задачи и аналогич­ная матрица А^т в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи — числу переменных в исходной задаче;

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

5) каждому ограничению одной задачи соответствует переменная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записан­ному в виде неравенства £, соответствует переменная, связанная условием неотрицательности. Если функцио­нальное ограничение исходной задачи является равенст­вом, то соответствующая переменная двойственнвой; задачи может принимать как положительные, так и отрицательные значения

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

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

Две приведенные задачи образуют пару симметричных двойственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности.

Для взаимно двойственных задач имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные реше­ния, при этом значения целевых функций на оптимальных решениях совпадают: f(x) = g(y).

2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограниченна сверху. При этом у двойственной задачи будет пустое допустимое множество.

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

4.Обе из рассматриваемых задач имеют пустые допустимые множества.

Экономический смысл первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов У оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная, при из­вестных заранее ценах продукции равна затра­там на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y_i. Для всех же других планов Х и У обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов:

f(X) < g(Y}, т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Зна­чит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных Оценок ресурсов.

Из первой теоремы двойственности следует, что при оп­тимальной производственной программе и векторе оценок ресурсов производственные потери равны нулю.

Вторая теорема двойственности

(теорема о дополняющей нежесткости)

Пусть X=(x₁,x₂,...x_n) - допустимое решение прямой задачи, а Y= (y₁,y₂,...y_m) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач необходимо и достаточно, чтобы выполнялись следующие соотношения:

*

**

Условия (*) и (**) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.

Из второй теоремы двойственности в данном случае следуют такие требования на оптимальную производственную программу X=(X₁,X₂,...,X_n) и оптимальный вектор оценок Y=(Y₁,Y₂,...,Y_m):

(4)

(5)

Условия (4) можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при оптимальной производственной программе этот ресурс используется полностью, если же ресурс используется не полностью, то его оценка равна нулю. Из условия (5) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках неубыточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет вы­пускаться.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках.

Значения переменных Y_i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину

Решая ЗЛП симплексным методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи yi называют объективно обусловленными оценками.

Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи оптимального использования ресурсов.

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

Прямая задача:

f(x) = 3Х₁ +4Х₂ +3Х₃ +1Х₄

Ограничения по ресурсам

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

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

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

Х₁, Х₂, Х₃, Х₄ 0

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

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

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

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

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

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

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

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

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

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

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

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

Таблица

Показатель	Филиал предприятия
Себестоимость производства изделия, руб.
Удельные капиталовложения, руб.

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

Филиал предприятия
	100 тыс. штук	200 тыс. штук

Требуется:

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.

Y1
Y2

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

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

120´0+80´100000+50´200000+4´0 = 18000000

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

).

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

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

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

105 =95 +50´0.2 = 105

105 =89+ 80´0.2 = 105

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

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

g =300000 Y₁+18000000 Y₂ = 300000 ´105₊18000000´(–0.2) = 279 000 000

= 83X₁+89X₂+95X₃+98X₄ =83´0+89´100000+95´200000+98´0 = 279 000 000.

Полученные оптимальные планы говорят о том, что в первом и четвертом филиалах размещать заказы по выпуску новых изделий невыгодно (Х1=0 и Х4=0), так как затраты на производство единицы изделия в этих филиалах больше цены изделия.

1 ´Y₁+ 120´Y₂ =83 Y₁= 105 105+ 120´(-0.2) < 95 105< 95+24 = 119

1 ´Y₁+ 40´Y₂ = 98 Y₂ = - 0.2105+ 40´(-0.2) <89 105<98+8 = 106.

Основным литературным источником являются [5,6,7], а дополнительным – [8-11, 13].

Тема 5. Методы оптимальных решений в условиях