Теория двойственности

 

Составление двойственных задач

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

В зависимости от вида исходной задачи линейного программирования различают симметричные, несимметричные и смешанные пары двойственных задач.

Симметричные пары двойственных задач

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

Пусть исходная задача имеет вид: найти наибольшее значение функции

при ограничениях:

 

 .

 

Правило составления двойственных задач

1.   Каждому ограничению исходной задачи ставится в соответствие двойственная переменная yi, где .

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

.                        (1)

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

                  (2)

 

 

4.   Переменные yi в двойственной задаче также неотрицательны, т.е.

.                                              (3)

Двойственная задача: найти наименьшее значение функции

при ограничениях:

 

 

.

Если двойственную задачу принять за исходную и поставить в соответствие каждому неравенству системы (2 переменную хj,  и по данному правилу составить двойственную задачу, то получим исходную задачу. Понятие двойственности является взаимным. Эти задачи образуют симметричную пару двойственных задач.

 

Несимметричная пара двойственных задач

Исходная задача задана в каноническом виде: найти наибольшее значение функции

при ограничениях:

.

Двойственная задача: найти наименьшее значение функции

при ограничениях:

,

где yi свободны по знаку, .

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

 

Смешанные пары двойственных задач

Пусть исходная задача задана в общем виде: найти наибольшее значение функции

при ограничениях:

 

 

Двойственная задача: найти наименьшее значение функции

при ограничениях

 

 

 

 

Если переменная поставлена в соответствие ограничению неравенству, то она неотрицательна, если уравнению, то произвольна по знаку, и наоборот.

Пример 1. Составить двойственную задачу к исходной: найти наибольшее значение функции

при ограничениях:

 

 

х1 ³ 0, х2 ³ 0, х3 и х4 свободны по знаку.

Двойственная задача: найти наименьшее значение функции

при ограничениях:

 

 

y1, y2 свободны по знаку, у3 ³ 0, у4 ³ 0.

 

Основные теоремы теории двойственности

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

Доказательство. Дана симметричная пара двойственных задач:

исходная задача: найти максимум функции

                                                (4)

при ограничениях:

 и                                 (5)

двойственная задача: найти минимум функции

                                                                              (6)

при ограничениях:

                                                                     (7)

.

Пусть  - допустимое решение исходной задачи, т.е.  удовлетворяют неравенствам (5),  - допустимое решение двойственной задачи, т.е.  удовлетворяют неравенствам (7).

Тогда
 

Аналогично рассматривается случай минимума.

Лемма 2. Достаточный признак оптимальности.

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

Доказательство. Пусть  и  - допустимые решения пары двойственных задач, причем , и пусть исходная задача решается на максимум.

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

Теорема 1. (Первая основная теорема двойственности.) Если одна из двойственных задач имеет оптимальное решение, то двойственная ей задача также имеет оптимальное решение, причем экстремумы целевых функций равны, т.е. .

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

Вторая теорема двойственности для несимметричных двойственных задач сформулируется так:

Теорема 2. (Вторая основная теорема двойственности.) Для того чтобы допустимые решения  и  несимметричной пары двойственных задач были соответственно оптимальными решениями, необходимо и достаточно, чтобы для любого j выполнялось равенство

.

Доказательство.

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

при ограничениях:

.

Двойственная задача: найти наименьшее значение функции

при ограничениях:

где yi свободны по знаку, .

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

.

Подставим вместо  получим

.

В правой части поменяем местами знаки суммирования, получим:

 .

Перенесем все в левую часть и вынесем за скобки общий множитель :

.

По условию  и , т.е. сумма неположительных слагаемых равна 0, а это возможно только тогда, когда каждое слагаемое равно нулю, т.е.

.

Достаточность. Предположим, что для допустимых решений  и  несимметричной пары двойственных задач выполняются равенства

.

Просуммируем это равенство по всем j и проведем преобразования, противоположные предыдущим:

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

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

То есть если  то,,

если  то .

 

Нахождение оптимального решения двойственной задачи

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

Первый способ нахождения решения

двойственной задачи в симметричном случае

Пример 2.

,

 

 

 

х1 ³ 0 , х2 ³ 0.

Эта задача решена графически (пример 8):

Составим двойственную задачу:

 

 

 

уi ³ 0, .

Из первой теоремы двойственности следует, что .

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

 

 

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

9 × 23,53 + 4 × 21,18 = 296,49, т.е. 296,49<360 Þ у3 = 0.

Получим систему трех уравнений с тремя неизвестными:

 

 

Решая систему, получим .

 

Второй способ нахождения решения

двойственной задачи в симметричном случае

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

Запишем системы ограничений симметричной пары двойственных задач.

 

Приведем их к каноническому виду

     

x1, x2, …, xn - основные,        xn+1, xn+2, …, xn+m - балансовые,

ym+1, ym+2, …, ym+n - балансовые,         y1, y2, …, ym - основные.

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

.

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

.

Пример 3. Найти наименьшее значение функции

при ограничениях:

 

 

хi ³ 0, .

Составим двойственную задачу:

 

 

уi ³ 0,

Решим двойственную задачу симплексным методом, для этого приведем ее к каноническому виду

 

 

.

Целевая функция остается без изменения.

№

п/п

сj

Б.п.

5

8

4

0

0

0

 

у1

у2

у3

у4

у5

у6

bi

1

2

3

0

0

0

у4

у5

у6

2

1

1

-1

1

-1

2

-1

-2

1

0

0

0

1

0

0

0

1

2

1

3

Dj

-5

-8

-4

0

0

0

0

1

2

3

0

8

0

у4

у2

у6

3

1

2

0

1

0

1

-1

-3

1

0

0

1

1

1

0

0

1

3

1

4

Dj

3

0

-12

0

8

0

8

1

2

3

4

8

0

у3

у2

у6

3

4

11

0

1

0

1

0

0

1

1

3

1

2

4

0

0

1

3

4

13

Dj

39

0

0

12

20

0

44

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

Тогда по первой теореме двойственности .

Установим связь между балансовыми переменными двойственной задачи и основными переменными исходной задачи х1®у4 , х2®у5 , х3®у6 , тогда х1=D4 , х2=D5 , х3=D6 , .

 

Нахождение решения двойственной задачи

в несимметричном случае

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

Пример 4. Найти наибольшее значение функции

при ограничениях:

хi ³ 0, .

Эта задача решена методом искусственного базиса (пример 12), и найдено .

Составим двойственную задачу: найти наименьшее значение функции

при ограничениях:

 

 

у1 и у2 свободны по знаку.

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

По второй теореме двойственности, так как в оптимальном решении исходной задачи х2¹0 и х3¹0, то, выписывая второе и третье ограничения двойственной задачи как уравнения, получим систему из двух уравнений с двумя неизвестными:

 

 

Решая эту систему, получим у1= -2 и у2=13,

Экономическая интерпретация двойственных задач

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

Исходная задача: найти наибольшее значение функции

при ограничениях:

,

.

Двойственная задача: найти наименьшее значение функции

при ограничениях:

,

.

Установим размерность двойственных переменных yi, которые еще называют оценками.

Из ограничений двойственной задачи  следует, что размерность произведения aij yi совпадает с размерностью cj, т.е.
aij yi  cj ( знак означает эквивалентность размерности), отсюда

 

 

 

Таким образом, yi рубли на единицу ресурса, назовем yi условной ценой или оценкой i-го ресурса.

Рассмотрим свойства оценок.

1)   Оценки yi - мера дефицитности ресурса. Дефицитный ресурс полностью используется при оптимальном плане и имеет положительную оценку, т.е.

.

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

 то .

1)        

т.е.
 
Оценки yi - мера влияния свободных членов системы ограничений исходной задачи на значение целевой функции. Так

 

как

Прирост прибыли пропорционален приращению i-го ресурса, причем коэффициент пропорциональности равен уi, чем больше уi, тем эффективнее i-й ресурс.

Пример 5. Рассмотрим задачу из примера 7.

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

 

 

х1 ³ 0, х2 ³ 0.

Составим двойственную задачу:

 

 

.

Найдем решения обеих задач:

.

В оптимальном решении двойственной задачи , следовательно, третий вид сырья недефицитный, т.е. при  расходуется не полностью. у1>0 и у2>0 Þ первое и второе сырье дефицитное, так как у2> у1 Þ второе сырье оказывает большее влияние на прибыль, есть смысл увеличивать в первую очередь запасы второго сырья.