1.12. Пара симметричных двойственных задач.

Пример №1. Рассмотрим задачу “о ресурсах”:

(1)

.

Тогда двойственная задача имеет вид:

(2)

.

Заметим, что двойственная задача (2) получается из исходной задачи (1) «транспонированием», то есть заменой строк на столбцы и обратно.

Матрица системы (2) совпадает с транспонированной матрицей исходной системы (1):

.

Строка коэффициентов целевой функции , то есть её вектор роста совпадает с транспонированным столбцом свободных членов исходной системы (1):

^Т,

а столбец ограничений двойственной задачи совпадает с транспонированной строкой коэффициентов исходной целевой функции

.

Условие максимизации исходной целевой функции заменяется условием минимизации двойственной целевой функции.

Знак ограничения двойственной задачи, которое соответствует j- тому столбцу системы (1), непосредственно связан со знаком тривиального ограничения соответствующей исходной переменной . Если переменная неотрицательна и , то соответствующее двойственное ограничение имеет вид:

.

Если же в исходной задаче и , то:

.

При изменении знака тривиального ограничения переменной меняется и знак соответствующего ограничения.

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

,

то есть переменная y_i “имеет знак «минус»”. Поскольку целевая функция задачи (2) минимизируется (также “имеет знак «минус»”), то в задаче (1) соответствующее ограничение в этом случае должно было бы иметь вид:

,

(два «минуса» дают «плюс»). На самом деле это не так, поэтому тривиальное ограничение для переменной имеет вид:

,

то есть соответствует знаку «плюс».

Итак, по задаче (1) однозначно строится двойственная ей задача (2). Верно и обратное.

Говорят, что задачи (1) и (2) образуют пару симметричных двойственных задач. Каждая из этих задач получается из другой задачи по одним и тем же правилам, и обе являются двойственными друг другу.

1.13. Правила перехода к двойственной задаче.

Сформулируем теперь общие правила перехода к двойственной задаче.

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

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

3. Компоненты вектора (строки) роста целевой функции двойственной задачи совпадают с компонентами вектора (столбца) свободных членов исходной задачи и наоборот.

4. Матрица системы нетривиальных ограничений двойственной задачи является транспонированной матрицей нетривиальных ограничений исходной задачи. Верно и обратное.

5. “Знак” ограничения двойственной задачи определяется знаком тривиального ограничения соответствующей исходной переменной и “знаком” исходной целевой функции по “правилу знаков”. Если в исходной задаче тривиальное ограничение переменной “имеет знак «плюс»” “( ), и целевая функция “имеет знак «плюс»” , то и двойственное ограничение также “ имеет знак «плюс»” (то есть вид “ ”). При изменении знака тривиального ограничения переменной исходной задачи или знака функции двойственной задачи, меняется и знак ограничения двойственной задачи. Если меняются оба знака, то знак ограничения двойственной задачи остается прежним. Если же на переменную исходной задачи не накладывается тривиального ограничения, то соответствующее ограничение двойственной задачи имеет вид равенства: .

6. Знак тривиального ограничения двойственной задачи определяется знаком соответствующего ограничения исходной задачи и “знаком” двойственной целевой функции по тому же “правилу знаков”. Если в исходной задаче ограничение “имеет знак «плюс»” ( ), и целевая функция двойственной задачи “имеет знак «плюс»” ( ), то и тривиальное ограничение двойственной задачи также “имеет знак «плюс»” (то есть вид ). При изменении знака ограничения в исходной задаче или «знака» целевой функции двойственной задачи меняется и знак тривиального ограничения переменной двойственной задачи. Если меняются оба этих знака, то знак ограничения двойственной задачи остается прежним.

Если же исходное ограничение имеет вид равенства

,

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

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

Этим замечанием мы фактически уже воспользовались, рассматривая пример 1 в 1.12.

Представим перечисленные правила в виде следующей таблицы.

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

№	Исходная задача	Двойственная задача
1
2	Ограничение	Переменная
3	Переменная	Ограничение
4	Столбец свободных членов	Вектор роста ´
	Вектор роста	Столбец свободных членов ´
5	Матрица системы	Транспонированная матрица системы
6
7	Знак переменной	«Знак» ограничения
8	«Знак» ограничения	Знак переменной

Отметим, что на знак переменной любой из задач влияет «знак» целевой функции той же задачи.

В заключение приведём пример перехода к задаче двойственной общей задаче линейного программирования.

Пример №1. Пусть дана исходная задача ЛП:

(1)

Тогда двойственная задача имеет вид:

(2)