Тема 2. Двойственность

Тема 2. Теория двойственности в линейном программировании и её прикладное значение

1. Формулировка двойственной задачи линейного программирования, правила составления двойственной задачи.

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

3. Понятие двойственной оценки ограничения. Свойства двойственных оценок. Экономическая интерпретация двойственных оценок.

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

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

Пусть в качестве исходной дана задача:

= c₁x₁ + c₂x₂ + ... + c_nx_n → max;

 

a11x1 + a12x2 + ... + a1nxn ≤ b1, a21x1 + a22x2 + ... + a2nxn ≤ b2, ...             am1x1 + am2x2 + ... + amnxn ≤ bm;

(1)

x_j ≥ 0,  

Задача линейного программирования, двойственная задаче (1), будет иметь вид:

= b₁y₁ + b₂y₂ + ... + b_my_m → min;

 

a11y1 + a21y2 + ... + am1ym ≥ c1, a12y1 + a22y2 + ... + am2ym ≥ c2, ...             a1ny1 + a2ny2 + ... + amnym ≥ cn;

(2)

y_i ≥ 0,   .

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче ищется максимум целевой функции, то в двойственной - минимум.

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

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

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

5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

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

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

.

(3)

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

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

	(4)

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

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

На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов. В пределах устойчивости двойственных оценок имеют место свойства, рассмотренные ниже.

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

Формулировка прямой (исходной) задачи:

= 2x₁ + 4x₂ → max;

 

4x1 + 6x2 ≤ 120, 2x1 + 6x2 ≤ 72, x2 ≤ 10;

 

x₁ ≥ 0,   x₂ ≥ 0.

 

Получим двойственную задачу.

= 120y₁ + 72y₂ + 10y₃ → min;

 

4y1 + 2y2 ≥ 2, 6y1 + 6y2 + y3 ≥ 4,

 

y₁ ≥ 0,   y₂ ≥ 0, y₃ ≥ 0.

 

В результате решения получим следующие оптимальные планы:

= (24, 4); = (1/3, 1/3, 0).

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

Перейдем к рассмотрению свойств двойственных оценок.

Свойство 1. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

В нашем примере нулевую оценку получил третий ресурс ( = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени ( = = 1/3).

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

4*24 + 6*4 =120, 2*24 + 6*4 = 72, 4 < 10.

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

Свойство 2. Оценки как мера влияния ограничений на значение целевой функции. Величина двойственной оценки какого-либо ресурса показывает, насколько возрастет максимальное значение целевой функции, если объем данного ресурса увеличить на единицу. В связи с этим значение объективно обусловленной оценки иногда называют теневой ценой ресурса. Теневая цена - это стоимость единицы ресурса в оптимальном решении.

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

Для нашего примера увеличение (уменьшение) фонда времени на участке А или В должно приводить к увеличению (уменьшению) максимальной прибыли на $1/3. Соответственно, например, при увеличении фонда времени участка А на 12 н-часов общая прибыль должна увеличиться на $4 (1/3*12).

Завершая рассмотрение вопроса, отметим, что применение теорем двойственности (а именно, соотношений (3) и (4)) позволяет, зная оптимальное решение одной из взаимно двойственных задач, без труда отыскать оптимальное решение другой задачи.

Проиллюстрируем это утверждение примером.

Для производства четырех видов изделий А₁, А₂, А₃ и А₄ завод должен использовать три вида сырья I, II и III. Запасы сырья на планируемый период составляют, соответственно, 1000, 600 и 150 единиц.

Технологические коэффициенты (расход каждого вида сырья на производство единицы каждого изделия) и прибыль от реализации единицы каждого изделия приведены в таблице 1.

Таблица 1. Исходные данные задачи о четырех видах изделий

Виды сырья	Технологические коэффициенты				Запасы сырья
	А1	А2	А3	А4
I	5	1	0	2	1000
II	4	2	2	1	600
III	1	0	2	1	150
Прибыль от реализации	6	2	2,5	4

Требуется, зная решение данной задачи, решить задачу, двойственную ей.

Сформулируем исходную ЗЛП.

= 6x₁ + 2x₂ + 2,5x₃ + 4x₄ → max;

 

5x1 + x2 +           2x4 ≤ 1000, 4x1 + 2x2 + 2x3 + x4 ≤ 600, x1 +             2x3 + x4 ≤ 150;

 

x₁ ≥ 0,   x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0.

 

Оптимальное решение данной задачи состоит в следующем (сам процесс решения здесь опускаем):

= (0, 225, 0, 150); = 1050.

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

= 1000y₁ + 600y₂ + 150y₃ → min;

 

5y1 + 4y2 + y3 ≥ 6, y1 + 2y2           ≥ 2,         2y2 + 2y3 ≥ 2,5, 2y1 + y2 + y3 ≥ 4.

 

y₁ ≥ 0,   y₂ ≥ 0,   y₃ ≥ 0.

 

Подставим , , и в ограничения исходной задачи:

5*0 + 225 + 2*150 < 1000, 4*0 + 2*225 + 2*0 + 150 = 600, 0 + 2*0 + 150 = 150.

Следовательно, используя вторую теорему двойственности и первое свойство двойственных оценок, можем записать: = 0.

Рассмотрим ограничения двойственной задачи. Каждое их них соответствует одной из переменных исходной задачи. Поскольку > 0 и > 0, только второе и четвертое ограничения двойственной задачи обращаются в верное равенство при подстановке в них оптимального плана (такой вывод следует из соотношений (4)). Учитывая, что = 0, можем записать систему из двух уравнений с двумя неизвестными:

2y2      = 2, y2 + y3 = 4.

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

Полностью решение двойственной задачи запишется так:

= (0, 1, 3); = 1050.