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

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

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

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

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

Рассмотрим задачу линейного программирования с неотрицательными переменными и неравенствами системы ограничений следующего вида:
(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)-(4) можно получить из симметричной пары (1)-(2).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двойственность является важным понятием в линейном программировании, имеющим экономическое (практическое) применение. Например, для задачи оптимального распределения ресурсов для производства некоторых видов товаров пара прямой и двойственной задачи принимает следующий экономический смысл:
Прямая задача: Сколько и какой продукции xj необходимо производить, чтобы при заданных доходах Cj и объемах ресурсов bi максимизировать доход от продажи продукции?
Двойственная задача: Какова должна быть «теневая» цена каждого ресурса yi, чтобы при заданных количествах bi и доходах Cj минимизировать затраты?

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

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

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

Задача 1. Записать математическую модель двойственной ЗЛП по заданной прямой:

Задача 2. Составить задачу, двойственную исходной задаче:

Задача 3. Решить задачу линейного программирования; составить задачу, двойственную данной, и также найти ее решение:

Источник