Материал: конспект 2

Элементы теории двойственности

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

Рассмотрим задачу, которая приводит к двойственной. Задача о использовании сырья.

Задача. Некоторое предприятие освоило выпуск 2-х видов изделий Р₁ и Р₂. При этом используется 4 вида сырья S₁, S₂, S₃, S₄. Запасы сырья и норма их расхода представлены в следующем виде

Сформулируем задачу метематически. Обозначим через х₁ и х₂ количество изделий соответственно вида Р₁ и Р₂, которое должно изготовить предприятие для получения max прибыли. Математическая модель задачи:

(1)

(2)

(3)

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

(двойственная целевая функция)

(4)

у – цена за единицу ресурса

(5)

(6)

При этом здесь задача 1–3 называется прямой задачей, а задача 4–6 называется двойственной задачей. Между прямой и двойственной задачами устанавливаются следующие соответствия:

1. Если прямая задача есть задачей максимизации, то двойственная задача – это задача минимизации.

2. В прямой задаче все ограничения неравенства имеют характер ≤, в двойственной такие ограничения имеют характер ≥.

3. Число переменных одной задачи соответствует числу ограничений другой задачи (и наоборот).

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

– Матрица при неизвестных коэффициентах

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

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

Заметим, что в задачах 1–3, 4–6 одна из них ориентирована на opt max, другая – на opt min. Все ограничения одной и другой имеют характер неравенств. Кроме того, на все переменные, как одной, так и другой задач, накладываются условия неотрицательности. Тогда такая пара двойственных задач называется симметричной парой.

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

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

1. Все ограничения неравенства прямой задачи должны иметь один и тот же знак. При этом характер неравенств ограничений и тип целевой функции согласовуются следующим образом:

а) б)

ограничение неравенств ≤ ограничение неравенств ≥

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

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

а) матрица коэффициентов при неизвестных транспонируется;

б) правые части ограничения одной из задач являются коэффициентами при неизвестных целевой функции другой задачи. При этом, если прямая задача имела opt max, то двойственная должна быть ориентирована в сторону opt min.

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

Заметим, что для пары взаимно-двойственных задач справедлива теорема о минимаксе, либо основная теорема теории двойственности, либо 1-ая теорема теории двойственности.

Теорема √ о минимаксе

√ основная теорема теории двойственности

√ 1-ая теорема теории двойственности

Если одна из задач линейного программирования (ЗЛП) имеет оптимальный план, то и другая задача будет иметь оптимальный план. Причем на оптимальных решениях значения целевых функций будут совпадать, т. е.

.

Если же в одной из задач целевая функция неограничена, то двойственная задача будет противоречива (если система ограничений несовместима). Если же, наконец, переменная задача противоречива, то для двойственной будет выполняться альтернатива, либо двойственная задача будет также противоречива, либо ее целевая функция будет неограничена.

Рассмотрим некоторые примеры составления пары взаимно-двойственных задач

(4 переменных т. к. 4 ограничения)

(т. к. х₁ ≥ 0)

(на х₂ не накладывается, только на х₁ ≥ 0 и х₃ ≥ 0)

(0 – в линейной форме

отсутствует коэффициент)

(если имеется = , то любой знак)

Основное неравенство теории двойственности. Іі теорема теории двойственности

Рассмотрим пару взаимно-симметричных двойственных задач

(1)

(2)

(3)

(4)

(5)

(6)

Пусть некоторый вектор есть некоторый допустимый план прямой задачи, а есть некоторый допустимый план двойственной задачи. Умножим каждое ограничение системы (2) на соответствующие ему значения двойственной переменной, а каждое ограничение системы (5) – на соответствующие ему значения прямой переменной. При этом имеем

(7)

(8)

После процедуры сложения ограничений (7) имеем

(9)

( – целевая форма двойственной задачи)

Реализуя аналогичную операцию для ограничения (8) имеем

(10)

Объединим неравенство (9) и (10) в одно единое сдвоенное неравенство

(11)

Неравенство (11) – основное неравенство теории двойственности. Из такого неравенства следует:

1. На любых допустимых планах max целевой функции прямой задачи не превышает min целевой функции двойственной задачи.

2. Если значение max целевой функции прямой задачи будет соответствовать значению min целевой функции двойственной задачи, то основное неравенство теории двойственности превращается в равенство.

Оказывается, что этот факт есть необходимым условием существования оптимальной пары взаимно-двойственных задач.

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

Вторая теорема теории двойственности

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

Доказательство необходимых условий теоремы:

Пусть ; есть некоторая оптимальная пара решений прямой и двойственной задачи. Тогда, вполне очевидно, что основное неравенство теории двойственности (11) будет превращаться в строгое равенство. Однако, это возможно тогда и только тогда, когда соотношения (7) и (8) будут превращаться в строгие равенства. Таким образом, для прямой задачи имеют:

(12)

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

(13)

Соотношение (12–13) и называется условиями дополняющей нежесткости Слейтера для прямой и двойственной задач.

Анализ условий дополняющей нежесткости Слейтера

Если на оптимальных планах в прямой и двойственной задачах некоторые ограничения выполняются как строгие равенства, то выражения в скобках соотношений (12–13) выполняются как строгие равенства, и соответственно обращаются в 0. Тогда соответствие двойственной переменной х_j для прямой задачи и соответствие прямой переменной х_j для двойственной задачи могут иметь любые значения.

Если на оптимальных планах некоторые ограничения превращаются в строгие неравенства, как для прямой, так и для двойственной задач, то соответственные переменные у₁ и х_j должны обращаться в 0

Доказательство теоремы

Допустим, что выполняются условия дополняющей нежесткости Слейтера. Это означает, что для некоторой пары решений х и у выполняются равенства соотношений (9) и (10). В свою очередь основное неравенство теории двойственности будет превращаться в равенство. А это означает, что

. Таким образом, пара решений х и у будет оптимальной парой. Из 2-ой теоремы двойственности следует: если задана прямая и составлена по отношению к ней двойственная задача, то для получения пары оптимальных решений х^* и у^* достаточно решить только 1 из таких задач, а затем воспользовавшись условиями дополнительной нежесткости Слейтера можно оценить оптимальный план другой задачи.

Рассмотрим примеры

По исходной задаче сост. двой. Решить ее графически, а затем по исходной задаче (восп. УДНС) оценить оптимальный план прямой задачи.