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

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

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

Формирование двойственной задачи начинается с записи прямой задачи в канонической форме. Рассмотрим пример задачи максимизации:

• Целевая функция: максимизировать c₁x₁ + c₂x₂ + ... + c_nx_n
• Ограничения: a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁
• ...
• a_m1x₁ + a_m2x₂ + ... + a_mnx_n ≤ b_m
• Все x_i ≥ 0

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

• Целевая функция: минимизировать b₁y₁ + b₂y₂ + ... + b_my_m
• Ограничения: a₁₁y₁ + a₂₁y₂ + ... + a_m1y_m ≥ c₁
• ...
• a_1ny₁ + a_2ny₂ + ... + a_mny_m ≥ c_n
• Все y_j ≥ 0

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

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

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

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