Методы решения физико-математических задач

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

Пример прямой и симметричной двойственной задачи линейного программирования
Представлены правила составления двойственных задач. Рассмотрены симметричные, несимметричные и смешанные пары. Разобраны примеры составления двойственных задач.
Содержание
См. также:

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

Симметричная двойственная задача

Рассмотрим задачу линейного программирования с неотрицательными переменными и неравенствами системы ограничений следующего вида:
(1.1)   ;
(1.2)  
Здесь , , есть некоторые числа. Все строки системы (1.2) являются неравенствами со знаками .

Двойственная задача имеет вид:
(2.1)   ;
(2.2)  
Здесь все строки системы (2.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (2.2) является транспонированной матрицей системы (1.2). Она содержит строк и столбцов. Двойственная задача имеет переменных . Все переменные неотрицательные.

Исходную задачу (1) часто называют прямой задачей, а задачу (2) – двойственной. Если за исходную взять задачу (2), то задача (2) будет прямой задачей, а задача (1) – двойственной. Задачи (1) и (2) называются симметричными двойственными задачами.

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

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

Дана задача линейного программирования:
;

Составить двойственную задачу.

Решение

Исходная задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Первое и третье неравенства содержат знак . Умножим их на –1:

Перепишем систему ограничений, явно указывая коэффициенты при переменных:

Матрица коэффициентов системы ограничений имеет вид:

Транспонируем эту матрицу. То есть первую строку запишем как первый столбец, вторую строку запишем как второй столбец, третью строку запишем как третий столбец.

Двойственная задача имеет вид:
;

Ответ

;

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

Задача на максимум

Рассмотрим каноническую задачу линейного программирования на максимум с неотрицательными переменными и равенствами системы ограничений:
(3.1)   ;
(3.2)  
Здесь , , есть некоторые числа. Все строки системы (3.2) являются равенствами. Все переменные являются неотрицательными.

Двойственная задача имеет вид:
(4.1)   ;
(4.2)  
Здесь все строки системы (4.2) являются неравенствами со знаками . Матрица коэффициентов системы ограничений (4.2) является транспонированной матрицей системы (3.2). Двойственная задача имеет переменных . Переменные могут быть как положительными, так и отрицательными.

Отличие несимметричной пары задач (3) и (4) от симметричной пары (1) и (2) в том, что система ограничений (3.2) содержит только равенства, а в системе (4.2) отсутствуют условия неотрицательности переменных.

Задача на минимум

Теперь рассмотрим каноническую задачу линейного программирования на минимум:
(5.1)   ;
(5.2)  

Двойственная задача имеет вид:
(6.1)   ;
(6.2)  

Система ограничений (6.2) отличается от (4.2) тем, что неравенства имеют знаки .

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

Покажем, что несимметричную пару задач (3.1) – (4.2) можно получить из симметричной пары (1.1) – (2.2).

Итак, пусть мы имеем прямую задачу с целевой функцией
(3.1)  
и системой ограничений
(3.2)  
Каждое равенство можно представить двумя неравенствами:

Неравенства со знаками умножим на –1:
(7)   \left\{ \begin{array}{l} a_{11} x_1 + a_{12} x_2 + \, ... \, + a_{1n} x_n \leqslant b_1 \\ -a_{11} x_1 - a_{12} x_2 - \, ... \, - a_{1n} x_n \leqslant -b_1 \\ a_{21} x_1 + a_{22} x_2 + \, ... \, + a_{2n} x_n \leqslant b_2 \\ -a_{21} x_1 - a_{22} x_2 - \, ... \, - a_{2n} x_n \leqslant -b_2 \\ ... \\ a_{m1} x_1 + a_{m2} x_2 + \, ... \, + a_{mn} x_n \leqslant b_m \\ -a_{m1} x_1 - a_{m2} x_2 - \, ... \, - a_{mn} x_n \leqslant -b_m \\ x_1 \geqslant 0; \; x_2 \geqslant 0; \; ... \; ; x_n \geqslant 0 \end{array} \right.
Получаем симметричную задачу с целевой функцией

и системой ограничений (7), которая имеет неравенств.

По формулам (1.1) – (2.2) получаем для нее двойственную задачу:
;
\left\{ \begin{array}{l} a_{11} y_{11} - a_{11} y_{12} + a_{21} y_{21} - a_{21} y_{22} + \, ... \, + a_{m1} y_{m1} - a_{m1} y_{m2} \geqslant c_1 \\ a_{12} y_{11} - a_{12} y_{12} + a_{22} y_{21} - a_{22} y_{22} + \, ... \, + a_{m2} y_{m1} - a_{m2} y_{m2} \geqslant c_2 \\ ... \\ a_{1n} y_{11} - a_{1n} y_{12} + a_{2n} y_{21} - a_{2n} y_{22} + \, ... \, + a_{mn} y_{m1} - a_{mn} y_{m2} \geqslant c_n \\ y_{11} \geqslant 0; \; y_{12} \geqslant 0; \; ... \; ; y_{m1} \geqslant 0; \; y_{m2} \geqslant 0 \end{array} \right.
Двойственная задача имеет неотрицательных переменных:
.
Нетрудно видеть, что эти переменные входят в задачу в виде разностей
.

Сделаем подстановки
.
Поскольку и , то переменные могут быть как положительными, так и отрицательными.

Тем самым мы получили двойственную задачу, которая имеет вид (4.1) – (4.2):
(4.1)   ;
(4.2)  

Если мы за исходную задачу возьмем (4.1) – (4.2), то, выполняя все действия в обратном порядке, получим двойственную задачу (3.1) – (3.2).

Тем же способом можно из задачи (5.1) – (5.2) получить двойственную задачу (6.1) – (6.2), а из задачи (6) получить двойственную задачу (5).

Смешанная задача

Теперь рассмотрим смешанную задачу.

Пусть мы имеем прямую задачу вида (1.1) на максимум, но в системе ограничений которой -я строка является равенством. Тогда двойственная задача имеет вид (2.1) – (2.2) за одним исключением – переменная может быть как положительной, так и отрицательной. То есть отсутствует ограничение .

То же самое произойдет, если мы имеем прямую задачу (2.1) на минимум, в системе ограничений которой -я строка является равенством. Двойственная задача имеет вид (1.1) – (1.2) за одним исключением – переменная может быть любого знака.

Теперь пусть мы имеем прямую задачу (1.1) на максимум, но отсутствует ограничение . То есть переменная может быть как положительной, так и отрицательной. Тогда двойственная задача имеет вид (2.1) – (2.2) за одним исключением – -я строка системы ограничений является равенством.

И наконец, пусть мы имеем прямую задачу (2.1) на минимум, но отсутствует ограничение . Тогда двойственная задача имеет вид (1.1) – (1.2) за одним исключением – -я строка системы ограничений является равенством.

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

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

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

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

Дана задача линейного программирования:
;

Составить двойственную задачу.

Решение

Целевая функция имеет свободный член 5. Чтобы привести ее к виду (2.1), введем переменную и добавим равенство . Тогда задача примет вид:

;

Эта задача является задачей на нахождение минимума. Поэтому все неравенства должны иметь знаки . Третье неравенства содержат знак . Поэтому умножим его на –1:

Перепишем систему ограничений, явно указывая коэффициенты при переменных:
\left\{ \begin{array}{l} 1 \cdot x_1 + 2 \cdot x_2 - 3 \cdot x_3 + 0 \cdot x_4 = 4 \\ 4 \cdot x_1 - 1 \cdot x_2 + 0 \cdot x_3 + 0 \cdot x_4 = 7 \\ - 2 \cdot x_1 + 3 \cdot x_2 - 1 \cdot x_3 + 0 \cdot x_4 \geqslant - 5 \\ 0 \cdot x_1 + 0 \cdot x_2 + 0 \cdot x_3 + 1 \cdot x_4 = 1 \\ x_1 \geqslant 0; \; x_2 \geqslant 0 \end{array} \right.
Матрица коэффициентов системы ограничений имеет вид:

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

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

Поскольку в исходной задаче 1, 2 и 4-я строка системы ограничений являются равенствами, то в двойственной задаче переменные , и могут иметь любой знак. Неотрицательной переменной является только . Поэтому условия неотрицательности переменных имеют вид:
.

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

Таким образом, двойственная задача имеет вид:
;

Из четвертого уравнения . Заменим переменную ее значением и умножим третью строку на –1.

Ответ

;

Автор: Олег Одинцов.     Опубликовано:

См. также:
▲
Меню