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

,
а также стоимость единицы продукции каждого вида c₁, c₂,…c_n. Требуется организовать производство так, чтобы предприятию А была обеспечена максимальная прибыль. Задача сводится к нахождению неотрицательных переменных x₁, x₂,…,x_n, при которых расход ресурсов не превышает заданного их количества, а стоимость всей продукции достигнет максимума. В математической форме задача записывается следующем виде:

L = c₁x₁ + c₂x₂ +…+c_nx_n → max (1)

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

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

L = b₁y₁+b₂y₂ + ... + b_my_m → min (3)

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

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

максимизировать сTx при условиях:
Ax≤b;
x≥0;

минимизировать bTy при условиях:
A^Ty≥c;
y≥0.

Переменные y₁,y₂,…,y_m двойственной задачи иногда называют теневыми ценами.

Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений (m > n).

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

• число переменных одной задачи равно числу ограничений другой задачи;
• в одной задаче ищется максимум целевой функции, в другой – минимум;
• коэффициенты при переменных в целевой функции одной задачи являются свободными членами системы ограничений другой задачи;
• в каждой задаче система ограничений задается в виде неравенств, причем, в задаче на отыскание максимум, все неравенства вида «≤», а в задаче на отыскание минимума, все неравенства вида «≥»;
• матрица коэффициентов системы ограничений получается одна из другой путем транспонирования;
• условия неотрицательности переменных сохраняются в обеих задачах.

Пример. По исходной задаче требуется построить двойственную.
Исходная задача: L = 10x₁ + 6x₂ – 4x₃ →min

Приведем все неравенства системы ограничений исходной задачи к одному знаку:

Двойственная задача. L=2y₁+3y₂ → max

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

• ограничения задачи выражены уравнениями вместо неравенств;
• в двойственной задаче отсутствуют условия неотрицательности переменных y_i, i=1...m.

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

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

Число переменных в задачах одинаково и равно m + n. В исходной задаче базисными переменными являются вспомогательные неотрицательные переменные x_n+1, x_n+2,…,x_n+m, а в двойственной задаче – вспомогательные неотрицательные переменные y_m+1. y_m+2,…, y_m+n. Можно показать, что базисным переменным одной задачи соответствуют свободные переменные другой задачи, и наоборот, то есть:

Установив соответствие между переменными пары двойственных задач, и решив одну из них табличным симплексным методом, можно получить решение другой задачи. Значения базисных переменных исходной задачи определяются L строкой оптимальной симплексной таблицы двойственной задачи, и, наоборот, значения базисных переменных двойственной задачи определяются L строкой оптимальной симплексной таблицы исходной задачи.
Пример 1. Найти решение пары двойственных задач.
Исходная задача: Двойственная задача:
L = 4x₁ + 6x₂ → max L = y₁ + 2y₂ + 3y₃ → min

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

Пример 2. Для исходной задачи составить двойственную и найти решение пары двойственных задач.

L = 3x₁ – x₂ + x₃ + 9 → max

Приведем данную задачу линейного программирования к виду, допускающему применение симплексного метода. Для этого, используя метод Жордана-Гаусса, приведем ЗЛП к единичному базису.

или

L = 4x₁ – 4x₂ + 15 → max

Для данной исходной задачи линейного программирования двой­ственная будет иметь вид: L = 9y₁+3y₂+6y₃+15 → min

Установим связь между переменными прямой и двойственной задачами

Решим исходную задачу линейного программирования табличным симплексным методом и найдем решение обеих задач. Результирующая таблица Жордана-Гаусса совпадает с исходной симплексной таблицей, определяющей первое допустимое решение X=(0;0;6;3;9), L=15. Это решение не является оптимальным, поскольку в строке L имеется отрицательная оценка. Используя алгоритм симплексного метода, улучшим данное решение.

Пример 3. Для исходной задачи составить двойственную. Решить обе задачи симплексным методом или двойственным симплексным методом и по решению каждой из них найти решение другой. Одну из задач решить графическим методом.

L = x₁ + x₂ → min

В случае нахождения минимума целевой функции система ограничений должна иметь знак «≥». Исходная ЗЛП примет вид:

L = x₁ + x₂ → min

Соответствующая ей двойственная задача запишется в виде:
L = -8y₁+4y₂+6y₃ → max

Исходную ЗЛП решим двойственным симплексным методом и графическим методом, а двойственную ЗЛП решим табличным симплексным методом и сравним решения.
Для решения исходной задачи двойственным симплексным методом
приведем ее к виду: L – x₁ – x₂ = 0

Используя алгоритм двойственного симплексного метода, найдем решение исходной ЗЛП.

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

Найдем координаты точки A_min, решив систему уравнений
Итак, A_min = (14/3; 2/3), L = 16/3.