Гельруд Я.Д. Линейное программирование. Учебно-методический комплекс
Подождите немного. Документ загружается.
79
строке 3.Затем после выполнения всех операций, позволяющих перейти от
системы (I) к системе (F), и обращения в нуль всех небазисных переменных,
будем иметь
x
0
=
7
695
+
7
13
δ
1
+
7
5
δ
3
(строка 0),
x
1
=
7
50
+
7
10
δ
1
–
7
1
δ
3
(строка 1), (I)
x
6
=
7
325
–
7
61
δ
1
+ 1δ
2
+
7
4
δ
3
(строка 2),
x
3
=
7
55
–
7
3
δ
1
+
7
1
δ
3
(строка 3),
Коэффициенты при δ
i
(i = 1, 2, 3) совпадают с коэффициентами при
соответствующих свободных переменных в (F). Базис остается допустимым,
если значения x
1
, x
6
и x
3
неотрицательны. Следовательно, δ
1
, δ
2
и δ
3
должны
удовлетворять соответствующей системе неравенств.
Тема 5. Двойственность
5.1. Общие понятия
В теории линейного программирования существует понятие
двойственности, которое позволяет унифицированным образом
устанавливать взаимосвязи для всех приемов и методов анализа моделей на
чувствительность. Для тех, кто не знаком с линейным программированием,
понятие двойственности может показаться абстрактным и, следовательно,
весьма
непривычным. Только со временем это впечатление уступает место
пониманию исключительной важности и полезности этого понятия.
Первоначальное представление о двойственности мы получили в 2.5.
Начнем с определения двойственности и приведем ряд примеров. В
последующих разделах будет показано, каким образом двойственность
80
используется при анализе на чувствительность моделей линейного
программирования.
5.2. Исходная и двойственная задачи
Рассмотрим две следующие задачи линейного программирования:
максимизировать
∑
=
n
j
jj
xc
1
(5.2.1)
при ограничениях
i
n
j
jij
bxа ≤
∑
=1
(i=l, 2, ..., m), (5.2.2)
x
j
≥ 0 (j=1, 2,..., n). (5.2.3)
и минимизировать
∑
=
m
i
ii
yb
1
(5.2.4)
при ограничениях
j
m
i
iij
cyа ≥
∑
=1
(j=1, 2,..., n). (5.2.5)
у
i
≥ 0 (i == 1, 2, . . ., т). (5.2.6)
Для определенности условно назовем первую задачу [соотношения (5.2.1) –
(5.2.3)] исходной, а вторую [соотношения (5.2.4) – (5.2.6)] двойственной (по
отношению к первой).
В качестве иллюстрации рассмотрим следующие две задачи:
исходная задача:
максимизировать 4x
1
+ 5x
2
+ 9x
3
(5.2.7)
при ограничениях
1x
1
+ 1x
2
+ 2x
3
≤ 16,
7x
1
+ 5x
2
+ 3x
3
≤ 25, (5.2.8)
x
j
≥0 (j = 1, 2, 3);
двойственная задача:
81
минимизировать 16y
1
+ 25y
2
(5.2.9)
при следующих ограничениях:
1y
1
+7y
2
≥ 4,
1y
1
+ 5y
2
≥ 5,
2y
1
+ 3y
2
≥ 9, (5.2.10)
y
1
≥0, y
2
≥0.
Грубо говоря, двойственная задача – это на 90° повернутая исходная
задача. Действительно,
1) j-й столбец, составленный из коэффициентов, фигурирующих в
ограничениях исходной модели, совпадает с j-й строкой, составленной из
коэффициентов, фигурирующих в ограничениях двойственной модели;
2) строка, составленная из коэффициентов в выражении для целевой
функции, совпадает со столбцом, составленным из констант
, фигурирующих в
правых частях ограничений двойственной модели;
3) столбец, составленный из констант, фигурирующих в правых частях
ограничений исходной модели, совпадает со строкой, составленной из
коэффициентов в выражении для целевой функции двойственной модели;
4) направление знаков неравенства в исходной модели противоположно
направлению знаков неравенства в двойственной модели;
требование максимизации в исходной задаче
в двойственной задаче заменено
требованием минимизации.
Имеет место следующая важная теорема:
Теорема двойственности. А. Если и исходная и двойственная ей задачи
имеют допустимые решения, то: 1) существует оптимальное решение x
j
*
(j=1,2, . . ., п) исходной задачи; 2) существует оптимальное решение y
i
*(i = 1, 2,
. . ., т) двойственной задачи; 3) имеет место следующее соотношение:
∑
=
∗
n
j
jj
xc
1
=
∑
=
∗
m
i
ii
yb
1
. (5.2.11)
Б. Если исходная (двойственная) задача допускает оптимальное решение,
для которого значение целевой функции ограничено, то соответствующая ей
82
двойственная (исходная) задача допускает оптимальное решение при том же
значении целевой функции.
Обратим внимание на то, что теорема двойственности позволяет проверить
на оптимальность любое допустимое пробное решение исходной задачи. Если
существует допустимое решение двойственной задачи, для которого значение
целевой функции совпадает со значением целевой функции исходной задачи,
то решения обеих задач
являются оптимальными.
Одно из весьма любопытных следствий теоремы двойственности можно
сформулировать в виде следующей теоремы:
Теорема о дополнительной нежесткости. Пусть x
j
*(j = 1, 2,..., п) –
решение исходной задачи, а y
i
*(i=1, 2,..., т) – решение соответствующей
двойственной задачи. Оба решения являются оптимальными тогда и только
тогда, когда
0)(
1
=−
∑
=
∗∗
i
n
j
jiji
bxаy (i=l, 2, ..., m),
0)(
1
=−
∑
=
∗∗
j
m
i
iijj
cyаx (j=1, 2,..., n).
Отсюда вытекает, что всякий раз, когда модель содержит ограничение,
имеющее вид строгого неравенства, соответствующая переменная в
двойственной задаче принимает нулевое значение.
При формулировке исходной и двойственной задач [соотношения (5.2.1) –
(5.2.6)] была использована удобная для записи каноническая форма. С
помощью преобразований, рассмотренных в начале, любую задачу линейного
программирования можно представить либо
в виде (5.2.1) – (5.2.3), либо в
виде (5.2.4) – (5.2.6).
5.3. Решение двойственной задачи
Казалось бы, настало время, когда следует задуматься о том, как ищется
решение двойственной задачи. Но подобно небезызвестному мольеровскому
83
герою, который пришел в восторг, узнав, что всю жизнь говорил прозой, не
подозревая об этом, читателя может удивить заявление о том, что решение
двойственной задачи давно уже найдено, хотя об этом никто и не
догадывается.
Оптимальные значения переменных двойственной задачи.
А. Коэффициенты при свободных переменных в строке 0 на последней
симплекс-итерации
при решении задачи максимизации совпадают с
оптимальными значениями переменных двойственной задачи.
Б. Коэффициент при x
j
в строке 0 на последней симплекс-итерации
представляет собой разность между левой и правой частями j-го ограничения
двойственной задачи, соответствующую оптимальному решению последней.
В качестве иллюстрации рассмотрим задачу распределения ресурсов, решение
которой дано в разд. 3.2:
максимизировать
4x
1
+ 5x
2
+ 9x
3
+ 11x
4
при ограничениях
1x
1
+ 1x
2
+ 1x
3
+ 1x
4
≤15,
7x
1
+ 5x
2
+ 3x
3
+ 2x
4
≤120,
3x
1
+ 5x
2
+ 10x
3
+ 15x
4
≤ 100,
x
1
≥0, x
2
≥0, x
3
≥0, x
4
≥0.
Легко показать, что двойственная задача формулируется следующим
образом:
минимизировать 15y
1
+ 120y
2
+ 100y
3
(5.3.1)
при наличии ограничений
l y
1
+ 7 y
2
+ 3 y
3
≥ 4,
1 y
1
+ 5 y
2
+ 5 y
3
≥ 5,
l y
1
+ 3 y
2
+ 10 y
3
≥ 9, (5.3.2)
l y
1
+ 2 y
2
+ 15 y
3
≥ 11,
y
1
≥0, y
2
≥0, y
3
≥0.
84
Рассмотрим коэффициенты при трех свободных переменных в строке 0 на
заключительной симплекс-итерации [см. соотношения (F) в разд. 4.1].
Согласно утверждению, приведенному выше (см. п. а), оптимальными
значениями переменных двойственной задачи являются следующие:
y
1
* =
7
13
, y
2
* =0, y
3
* =
7
5
. (5.3.3)
Прежде всего, убедимся, что выполняются условия (5.3.2):
1⋅
7
13
+ 3⋅
7
5
=
7
28
≥ 4,
1⋅
7
13
+ 5⋅
7
5
=
7
38
≥ 5, (5.3.4)
1⋅
7
13
+ 10⋅
7
5
=
7
63
≥ 9,
1⋅
7
13
+ 15⋅
7
5
=
7
88
≥ 11.
Затем покажем, что значение целевой функции двойственной задачи
совпадает со значением целевой функции исходной задачи
15⋅
7
13
+ 120⋅0 + 100⋅
7
5
=
7
695
. (5.3.5)
Решение (5.3.3) должно быть оптимальным, поскольку удовлетворяются
все ограничения и, кроме того, значения целевых функций исходной и
двойственной задач совпадают.
Наконец, вычислим разность между левыми и правыми частями
соотношений (5.3.4). Возьмем, например, второе и третье ограничения, для
которых находим
7
38
– 5=
7
3
,
7
63
– 9=0,
т. е. получаем соответственно коэффициенты при x
2
и x
3
в строке 0 системы
уравнений (F), что согласуется с утверждением, сформулированным в п. б).
Опираясь на понятие двойственности, можно глубже понять суть
симплексного метода. В частности, нетрудно убедиться, что коэффициенты
при остаточных переменных в строке 0 на каждой итерации в процессе
85
решения исходной задачи представляют собой пробные значения переменных
двойственной задачи, что же касается других коэффициентов, фигурирующих
в строке 0 после выполнения любой симплекс-итерации, то их можно
интерпретировать как разность между левой и правой частями (5.3.2) при
заданных пробных значениях двойственной задачи. Таким образом,
симплексный метод можно рассматривать как способ получения пробных
решений
двойственной задачи путем определения допустимых решений
исходной задачи. Как только удается найти допустимое решение этих двух
задач, процесс итерации заканчивается.
Примечание. Изложенное выше объяснение того, как получаются
оптимальные значения переменных двойственной задачи, относилось к
случаю, когда все знаки неравенств имели вид (≤). Слушателю
предоставляется возможность объяснить получение оптимальных значений
переменных двойственной задачи в других случаях.
5.4. Продолжение анализа на чувствительность
В разд. 5.2 мы утверждали, что теорема двойственности позволит лучше
разобраться в анализе линейных моделей на чувствительность и освоить его
практически. Попытаемся показать, что это действительно так. Начнем с
повторения того, что уже излагалось в самом начале этой главы, стремясь
при
этом выявить те моменты анализа, которые связаны с понятием
двойственности. Затем будут рассмотрены некоторые дополнительные
вопросы, связанные с анализом линейных моделей на чувствительность.
Целевая функция. Обращаясь к примеру, рассмотренному в разд. 3.2,
вспомним, что одно из ограничений двойственной задачи, соответствующее
переменной x
2
исходной задачи, имеет вид
1y
1
+ 5y
2
+ 5y
3
≥ 5. (5.4.1)
Если коэффициент при x
2
в выражении для целевой функции положить
86
равным 5 + δ, то в правой части соотношения (5.4.1) также будет стоять 5 + δ.
Подставив в (5.4.1) оптимальные значения двойственной задачи, получим
1⋅
7
13
+ 5⋅0 + 5⋅
7
5
≥ 5 + δ, (5.4.2)
или
7
3
≥ δ. (5.4.3)
Таким образом, решение двойственной задачи остается допустимым, если
δ не превышает
3
/
7
. Если же δ принимает значение, превышающее
3
/
7
, то это
решение не является более допустимым и, следовательно, рассматриваемое
решение исходной задачи не является более оптимальным. Это согласуется с
результатом, полученным в разд. 3.2.
Константы в правых частях ограничений. В разд. 4.3 с помощью
частного приема было показано, что коэффициент при остаточной переменной
в строке 0, соответствующей оптимальному решению, определяет приращение
объема ресурса, ассоциированное с этой переменной. В предыдущем же
разделе было установлено, что оптимальное значение соответствующей
переменной для двойственной задачи совпадает со значением указанного
коэффициента. Учитывая эти два результата, приходим к следующему
заключению.
Интерпретация переменных двойственной задачи. Оптимальное значение
каждой переменной двойственной задачи определяет положительное или
отрицательное приращение значения целевой
функции за счет единичного
приращения (положительного или отрицательного) значения константы в
правой части соответствующего ограничения при условии, что
рассматриваемый базис остается допустимым. Такая интерпретация
согласуется с основным соотношением (5.2.11), которое означает, что
Оптимальное значение x
0
= ∑(Константы в правых частях ограничений) ×
× (Оптимальные значения переменных двойственной задачи). (5.4.4)
87
Оптимальные значения переменных двойственной задачи часто называют
скрытыми доходами. В случае, когда константы в правых частях
ограничений задают объемы имеющихся ресурсов, скрытые доходы
определяют вклад в прибыль, полученный за счет единицы каждого из
ресурсов, в соответствии с видом оптимального решения исходной задачи. В
задаче, рассмотренной в разд. 3.2, значение
13
/
7
есть скрытый доход,
соответствующий первому ограничению (ресурс – человеко-недели), значение
нуль – скрытый доход, соответствующий второму ограничению (ресурс –
объем материала Y), а значение
5
/
7
– скрытый доход, соответствующий
третьему ограничению (ресурс – объем материала Z). Таким образом,
увеличив первый из указанных ресурсов на одну человеко-неделю, мы
получаем дополнительную прибыль, равную
13
/
7
; каждый дополнительный
фунт материала Z увеличивает прибыль на
5
/
7
. Увеличение же объема
материала Y не приводит к увеличению прибыли. Чем это объясняется?
Причина заключается в том, что запас материала Y превышает имеющиеся в
нем потребности, что видно из того обстоятельства, что свободная переменная
x
6
входит в оптимальный базис.
Это положение носит общий характер, т. е. избыточность ресурса
приводит к тому, что в базис на последней симплекс-итерации входит
свободная переменная с неотрицательным значением. Нулевого значения
скрытого дохода в этом случае можно ожидать, поскольку увеличение
заведомо избыточного ресурса не может увеличить прибыль. Именно такая
ситуация
и имеет место. Поскольку в базис входит свободная переменная,
коэффициент при этой переменной в строке 0 на заключительной итерации
равен нулю.
Интерпретируя значения переменных двойственной задачи как скрытый
доход, мы приходим к более глубокому пониманию двойственности.
Применительно к задаче, рассмотренной в разд. 3.2, каждая из переменных
двойственной задачи может рассматриваться как потенциальная возможность
получения дополнительной прибыли за счет соответствующего ресурса при
88
условии, что фирма функционирует в оптимальном режиме. При этом
соотношение (5.4.4) означает, что суммарный доход фирмы пропорционален
объему имеющихся ресурсов. Коэффициенты а
ij
интерпретируются как
соответствующие нормы потребления i-го ресурса в j-м производственном
процессе.
Суммой
∑
=
m
i
iij
yа
1
задается экономический эффект за счет j-го
производственно-технологического процесса, вычисленный с учетом скрытого
дохода. Ограничения двойственной задачи гарантируют строгую
пропорциональность экономического эффекта затраченным усилиям, если
имеет место оптимальный режим функционирования фирмы. Более того, при
указанных условиях исключаются варианты решений, не оправданных с
экономической точки зрения.
Коэффициенты в соотношениях, задающих
ограничения. Приступая к
анализу на чувствительность по отношению к вариациям а
ij
, предположим, что
в модель вводится новая управляемая переменная. Насколько «выгодно»
включить ее в базис? Наиболее простой способ получить ответ на этот вопрос
заключается в том, чтобы проверить, удовлетворяются ли ограничения
соответствующей двойственной задачи при заданных значениях ее
переменных. Если эти ограничения не выполняются, то следует ввести в
рассмотрение новую управляемую
переменную.
Если x
j
не входит в базис, то результат изменения коэффициентов а
ij
при
данной переменной в ограничениях модели определяется аналогичным п. 4.3
образом.
Если x
j
входит в базис, то анализ результатов изменения коэффициентов
при этой переменной в ограничениях модели оказывается более сложным. Он
связан с одновременным рассмотрением как исходной, так и двойственной
задач. Такого рода анализ выходит за рамки данного курса; эти вопросы
изложены в ряде более полных учебных пособий по линейному
программированию.