Двойственность в линейном программировании

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

Двойственная задача — это вспомогательная задача линейного программирования, получаемая с помощью определенных правил непосредственно из условий исходной. Сформулируем правила построения двойственных задач:

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

2. Количество ограничений (m) исходной задачи равно количеству переменных двойственной, а количество переменных (n) исходной равно количеству ограничений двойственной. Переменные двойственной задачи обозначим через .

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

4. Каждой переменной неограниченной по знаку, соответствует ограничение вида «=» двойственной задачи, и наоборот.

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

6. Матрица А коэффициентов при неизвестных в ограничениях исходной задачи в двойственной транспонируется .

Для наглядности связь между исходной и двойственной задачами представлена в таблице 16.

Таблица 16

Исходная задача

Двойственная задача

Максимизация f Количество ограничений m Переменные

x_j ³0 i-е ограничение вида «£» х_j не ограничено по знаку i-е ограничение вида «=» Свободные члены ограничений b_i Коэффициенты при x_j в целевой функции (c_j) Матрица коэффициентов при неизвестных в ограничениях (А)

Минимизация z Количество ограничений n Переменные

j-е ограничение вида «³» y_i ³0 j-е ограничение вида «=»

не ограничено по знаку Коэффициенты при y_i в целевой функции (b_i) Свободные члены ограничений (c_j) Транспонированная матрица коэффициентов при неизвестных в ограничениях (A^T)

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

Двойственная к этой задаче будет иметь вид:

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

В таблице 17 приведены частные виды исходных задач линейного программирования в матричном виде и соответствующие им двойственные задачи. Через обозначена матрица — строка неизвестных двойственной задачи.

Матрица-строка Y умножается слева на матрицу — столбец В (в целевой функции) и матрицу А (в ограничениях), исходя из правил умножения двух матриц, а также правил построения двойственных задач (в частности, в двойственной задаче матрица коэффициентов при неизвестных в ограничениях должна быть транспонированной).

Первые две пары взаимно двойственных задач в таблице 17 называются симметричными, вторые две — несимметричными из-за наличия ограничений вида «=».

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

Таблица 17

	Исходная задача	Двойственная задача
I	f=CX®max AX≤B X≥0	z=YB→min YA≥C Y≥0	Симметричные задачи
II	f=CX→min AX≥B X≥0	z=YB→max YA≤C Y≥0
III	f=CX®max AX=B X≥0	z=YB→min YA≥C	Несимметричные задачи
IV	f=CX→min AX=B X≥0	z=YB→max YA≤C

Пример: Построить задачу, двойственную к данной:

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

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

Пример: Построить задачу, двойственную к данной:

Для построения двойственной задачи воспользуемся формами (II), (IV) и преобразуем данную задачу путем умножения обеих частей второго неравенства на (–1). Тогда исходная задача будет иметь вид:

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

Используя пример, поясним некоторые правила построения двойственных задач. Поскольку количество ограничений исходной задачи m=3, двойственная задача должна иметь три переменные: Количество переменных исходной задачи n=4, поэтому двойственная должна иметь четыре ограничения. Переменные x₁ и x₄ исходной задачи не ограничены по знаку. В силу этого первое и четвертое ограничения двойственной задачи имеют вид равенств. Третье ограничение исходной задачи имеет вид равенства, следовательно, переменная y₃ двойственной задачи не ограничена по знаку.

Контрольные вопросы и упражнения

1. Что представляет собой двойственная задача линейного программирования?

2. В чем отличие симметричных задач двойственной пары от несимметричных?

3. Постройте задачи, двойственные к данным:

4. Дайте экономическую интерпретацию задачи, двойственной к задаче использования ресурсов.

5. Какая задача из пары взаимно двойственных задач может быть принята в качестве исходной и какая в качестве двойственной? Какие задачи на практике считают двойственными?

6. С какими вариантами решений можно столкнуться при исследовании задач двойственной пары?

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

8. Постройте задачу, двойственную к данной:

Решите исходную и двойственную задачи графическим методом.

9. Постройте задачи, двойственные к данным:

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

10. Как по решению исходной задачи найти решение двойственной и наоборот?