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

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

Основы дуализма

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

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

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

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

Прямая задача

Максимизировать: c 1 x 1 + c 2 x 2 + ... + c n x n
При условии: a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
             a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2
             ,
             a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m

             x 1 , x 2 , ..., x n ≥ 0

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

Минимизировать: b 1 y 1 + b 2 y 2 + ... + b m y m
При условии: a 11 y 1 + a 21 y 2 + ... + a m1 y m ≥ c 1
             a 12 y 1 + a 22 y 2 + ... + a m2 y m ≥ c 2
             ,
             a 1n y 1 + a 2n y 2 + ... + a mn y m ≥ c n

             y 1 , y 2 , ..., y m ≥ 0

Интерпретация и экономическое значение

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

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

Геометрическая интерпретация

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

Принцип дополнительной вальяжности

Неотъемлемой частью, связывающей прямую и двойственную формулировки, является концепция дополнительной вальяжности. Она состоит из условий, которые должны выполняться, если и прямая, и ее двойственная задачи имеют оптимальные решения. Для каждой пары ограничений прямой и двойственной задач должны выполняться условия дополнительной вальяжности:

Если x j > 0, то j -е условия двойственности строгие;
Если бинарное ограничение i ослабляется, то i-я основная переменная равна нулю.

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

Пример дуализма

Простой элементарный пример

Максимизировать z = 2x 1 + 3x 2
субъект до
             x 1 + 2x 2 ≤ 10
             2x 1 + x 2 ≤ 8
             x 1 , x 2 ≥ 0

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

Минимизировать w = 10y 1 + 8y 2
субъект до
             y 1 + 2y 2 ≥ 2
             2y 1 + y 2 ≥ 3
             y 1 , y 2 ≥ 0

Применение и значение

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

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

Заключение

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

комментарии