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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Двойственная задача[1] для заданной задачи линейного программирования (ЛП, англ. Linear programming, LP) — это другая задача линейного программирования, которая получается из исходной (прямой) задачи следующим образом:

  • Каждая переменная в прямой задаче становится ограничением двойственной задачи;
  • Каждое ограничение в прямой задаче становится переменной в двойственной задаче;
  • Направление цели обращается – максимум в прямой задаче становится минимумом в двойственной, и наоборот.

Теорема о слабой двойственности утверждает, что значение двойственной задачи для любого допустимого решения всегда ограничено значением прямой задачи для любого допустимого решения (верхняя или нижняя граница, в зависимости от того, это задача максимизации или минимизации).

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

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

О геометрическом смысле двойственной задачи можно почитать в книге Юдина и Гольштейна[3]. Там же можно прочитать об экономическом смысле задачи[4].

Построение двойственной задачи[править | править код]

Если дана прямая задача линейного программирования, для построения двойственной задачи может быть использован следующий алгоритм[5].

Пусть прямая задача определена как:

  • Дан набор из n переменных: .
  • Для каждой переменной i определено ограничение на знак — она должна быть либо неотрицательной (), либо неположительной (), либо ограничение не задано ().
  • Задана целевая функция: Максимизировать
  • Задан список из m ограничений. Каждое ограничение j равно: , где символ перед может быть одним из трёх — , или .

Двойственная задача строится следующим образом.

  • Каждое ограничение прямой задачи становится двойственной переменной. Таким образом, получаем m переменных: .
  • Знак ограничения каждой двойственной переменной «противоположен» знаку ограничения в прямой задаче. Таким образом, «» становится , «» превращается в , а «» превращается в .
  • Целевая функция двойственной задачи равна (минимизировать)
  • Каждая переменная прямой задачи становится двойственным ограничением. Таким образом, получаем n ограничений. Коэффициент двойственной переменной в двойственных ограничениях равен коэффициенту переменной из ограничения прямой задачи. Таким образом, каждое ограничение i есть: , где символ перед аналогичен ограничению на переменную i в прямой задаче. Так, превращается в «», превращается в «», а превращается в «».

Из этого алгоритма легко видеть, что двойственная задача двойственной задачи совпадает с прямой задачей.

Векторные формулировки[править | править код]

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

Прямая Двойственная Примечания
Максимизировать при ограничениях Минимизировать при ограничениях Такая задача называется «симметричной» двойственной задачей
Максимизировать при ограничениях Минимизировать при ограничениях Такая задача называется «асимметричной» двойственной задачей
Максимизировать при ограничениях Минимизировать при ограничениях

Теоремы двойственности[править | править код]

Ниже мы предполагаем, что прямая задача поставлена как «Максимизировать при ограничениях [ограничения]», а двойственная задача поставлена как «Минимизировать при ограничениях [ограничения]».

Слабая двойственность[править | править код]

Теорема о слабой двойственности утверждает, что для каждого допустимого решения x прямой задачи и каждого допустимого решения y двойственной задачи: . Другими словами, значение целевой функции для каждого допустимого решения двойственной задачи является верхней границей целевой функции прямой задачи, а значение целевой функции любого допустимого решения прямой задачи является нижней границей для целевой функции двойственной задачи. Из этого следует, что

В частности, если прямая задача не ограничена (сверху), то двойственная задача не имеет допустимого решения, а если не ограничена двойственная задача (снизу), то не имеет допустимого решения прямая задача.

Теорему о слабой двойственности относительно легко доказать[6]. Предположим, что прямая задача линейного программирования звучит как «Максимизировать при ограничениях ». Предположим, что мы создаём линейную комбинацию ограничений с положительными коэффициентами, такую, что коэффициенты при x не меньше . Эта линейная комбинация даёт нам верхнюю грань для целевой функции. Переменные y двойственной задачи являются коэффициентами этой линейной комбинации. Двойственная задача пытается найти такие коэффициенты, которые минимизируют результирующую правую часть. Это даёт задачу линейного программирования «Минимизировать при ограничениях »[7]. См. «Простой пример» ниже.

Сильная двойственность[править | править код]

Теорема о сильной двойственности утверждает, что границы, определяемые теоремой о слабой двойственности жёсткие, то есть

Теорему о сильной двойственности существенно труднее доказать. Обычно доказательство использует теорему о слабой двойственности в качестве леммы[8].

Одно доказательство использует симплекс-метод и опирается на доказательство того, что, при подходящем правиле выбора выводимого столбца, он даёт правильное решение. Доказательство устанавливает, что, когда симплекс-метод завершается решением прямой задачи линейного программирования, можно из конечной таблицы прочесть решение двойственной задачи. Таким образом, после прогона симплекс-алгоритма мы получим решения как прямой, так и двойственной задачи одновременно[9].

Другое доказательство использует лемму Фаркаша[10]

Теоретическое приложение[править | править код]

Слабая двойственность имеет интересное теоретическое приложение — она показывает, что нахождение отдельного допустимого решения настолько же трудно, насколько нахождение оптимального допустимого решения. Предположим, что мы имеем систему предсказывания, что данная задача линейного программирования находит произвольное допустимое решение (если оно существует). Если задача звучит как «Максимизировать при ограничениях », мы можем построить другую задачу путём комбинирования её с двойственной ей задачей. Комбинированная задача имеет как x, так и y в качестве переменных:

Максимизировать 1

при ограничениях

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

Примеры[править | править код]

Простой пример[править | править код]

Рассмотрим прямую задачу с двумя переменными и одним ограничением:

Максимизировать
При условиях

Применив вышеизложенный рецепт построения двойственной задачи, получим задачу с одной переменной и двумя ограничениями:

Минимизировать
При условиях

Легко видеть, что максимум прямой задачи достигается, когда переменная x1 минимизируется до её нижней границы (0), а переменная x2 максимизируется до её верхней границы, заданной ограничением (7/6). Максимум равен .

Аналогично, минимум двойственной задачи достигается, когда y1 минимизируется до его нижнего значения при ограничениях: первое ограничение даёт значение 3/5, в то время как второе даёт более строгую границу 4/6, так что фактический минимум равен 4/6 и минимум целевой функции равен .

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

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

Пример фермера[править | править код]

Рассмотрим фермера, который может выращивать пшеницу и ячмень на площади L, используя удобрения F и пестициды P. Чтобы вырастить одну единицу пшеницы на единице площади, нужно использовать единиц удобрений и единиц пестицидов.

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

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

Для двойственной задачи предположим, что y единиц цены для каждой из этих видов продукта (входы) представлены группой планирования. Задачей группы планирования является минимизация полной стоимости производство продукции при заданных величинах потребления ресурсов с определением стоимости единицы ресурса (выход). Это соответствует следующей задаче линейного программирования:

Минимизировать
(минимизировать полную стоимость производства продукции как «целевая функция»)
при ограничениях:
(фермер должен получить не менее S1 за единицу пшеницы)
(фермер должен получить не менее S2 за единицу ячменя)
(цены не могут быть отрицательными).

В матричной форме:

Минимизировать:
при условиях:

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

Каждой переменной в пространстве прямой задачи соответствует неравенство в пространстве двойственной задачи. Каждому неравенству в пространстве прямой задачи соответствует переменная в пространстве двойственной задачи.

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

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

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

Недопустимая задача[править | править код]

Задача линейного программирования может также быть неограниченной или недопустимой. Теория двойственности говорит нам, что:

  • Если прямая задача является неограниченной, то двойственная задача недопустима;
  • Если двойственная задача является неограниченной, то прямая задача недопустима[11].

Однако может быть, что обе задачи, как двойственная, так и прямая, недопустимы. Вот пример:

Максимизировать:
При условиях:

Приложения[править | править код]

Теорема о максимальном потоке и минимальном разрезе является специальным случаем теоремы о сильной двойственности — максимизация потока является прямой задачей линейного программирования, а минимизация разреза является двойственной задачей линейного программирования. См. теорему Форда — Фалкерсона.

Другие теоремы, связанные с графами, могут быть доказаны с помощью теоремы о сильной двойственности, в частности, теорема Кёнига[12].

Теорема о минимаксе[en] для игр с нулевой суммой может быть доказана с помощью теоремы о сильной двойственности[13].

Альтернативный алгоритм[править | править код]

Иногда можно найти более интуитивный способ получить двойственную задачу без применения матрицы задачи. Рассмотрим следующую задачу линейного программирования:

Минимизировать
при условиях

Мы имеем условий и все переменные неотрицательны. Нам нужно определить двойственных переменных: yj и si. Мы получаем:

Минимизировать
при условиях

Поскольку это задача минимизации, нам хотелось бы получить двойственную задачу, которая является нижней границей прямой задачи. Другими словами, нам хотелось бы, чтобы сумма всех правых частей ограничений была максимальной при условиях, что для каждой переменной прямой задачи сумма её коэффициентов не превосходит коэффициента в линейной функции. Например, x1 появляется в ограничениях. Если мы суммируем коэффициенты ограничения, мы получим . Эта сумма должна не превосходить c1. Как результат мы получаем:

Максимизировать
при ограничениях

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

Интерпретации в реальной жизни[править | править код]

Теорема двойственности имеет экономическую интерпретацию. Если мы интерпретируем прямую задачу линейного программирования как классическую задачу «распределения ресурсов», её двойственную задачу можно интерпретировать как задачу «оценки ресурсов»[14]. См. статью Теневая ценаruen. Об экономической интерпретации двойственной задачи можно почитать также в книге Лунгу[15].

Теорема двойственности имеет и физическую интерпретацию[16].

Примечания[править | править код]

  1. Иногда используется термин Сопряжённая задача, как, например, в книге Юдина и Гольштейна (Юдин, Гольштейн 1969, 149) или в книге Лунгу (Лунгу 2005, 67). Во второй книге прямая задача именуется также основной задачей.
  2. Gartner, Matousek, 2006, с. 81–104.
  3. Юдин, Гольштейн, 1969, с. 150-152 Пункт 5.2.
  4. Юдин, Гольштейн, 1969, с. 157-159 Пункт 5.5.
  5. Gartner, Matousek, 2006, с. 85.
  6. Доказательство очень близкого утверждения, из которого вытекает данная теорема можно найти в книге Юдина и Гольштейна (Юдин, Гольштейн 1969, 159, Лемма 5.1)
  7. Gartner, Matousek, 2006, с. 81–83.
  8. Доказательство можно найти в книге Юдина и Гольштейна, где она именуется «первой теоремой двойственности» (Юдин, Гольштейн 1969, 164, Теорема 6.1)
  9. Gartner, Matousek, 2006, с. 87–89.
  10. Gartner, Matousek, 2006, с. 81–94.
  11. Юдин, Гольштейн, 1969, с. 162, Лемма 5.3.
  12. A. A. Ahmadi Lecture 6: linear programming and matching. Princeton University (2016). Архивировано 21 сентября 2018 года.
  13. Gartner, Matousek, 2006, с. sub.8.1.
  14. В книге Юдина и Гольштейна для теневых цен используется термин предварительные оценки (факторов производства).
  15. Лунгу, 2005, с. 68 Пункт 5.4.
  16. Gartner, Matousek, 2006, с. 86–87.

Литература[править | править код]

  • Jiri Matousek, Bernd Gärtner. Understanding and Using Linear Programming. — Springer, 2006. — С. 81–104. — (Universitext).
  • Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (теория, методы и приложения). — Москва: «Наука», 1969.
  • Лунгу К.Н. Линейное программирование. Руководство к решению задач. — М.: ФИЗМАТЛИТ, 2005. — ISBN 5-9221-0631-7.