Постановка и модель двойственной задачи

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

Напомним, что в основе задачи линейного программирования рассматривается предприятие, имеющее ресурсы b_i, где i = 1, 2, …, m. Оно тратит их на изготовление готовой продукции и эту продукцию реализует. При этом ставится цель — получить максимум продукции в стоимостном выражении не перерасходуя ресурсы. Модель задачи выглядит следующим образом: двойственный симплекс линейный программирование.

I) Ж = с₁х₁ + с₂х₂ + … + с_nх_n max.

II) a₁₁х₁ + а₁₂х₂ + … + а_1nх_n? b₁,.

a₂₁х₁ + а₂₂х₂ + … + а_2nх_n? b₂,.

…

a_m1х₁ + а_m2х₂ + … + а_mnх_n? b_m.

III) х_j? 0, j = 1, 2, …, n.

Предположим, что некоторое предприятие решило не тратить ресурсы на изготовление продукции, а продать эти ресурсы. Тогда возникает вопрос: по какой цене продавать ресурсы? Цена должна устраивать как продавца, так и покупателя. Интерес покупающей стороны заключается в том, чтобы заплатить за ресурсы как можно меньше, а интерес продающей стороны — в том, чтобы получить за ресурсы не меньше того, что она получила бы за реализованный готовый товар.

Тогда, в так называемой двойственной модели, целевая функция будет описывать интерес покупающей стороны, система ограничений — интерес продающей стороны (необходимо оценить ресурсы, которые пошли бы на изготовление единицы продукции и стоимость этих ресурсов ограничить ценой реализованной единицы продукции). Третье условие (неотрицательность переменных величин) будет выполняться в силу того, что цена единицы ресурса не может быть отрицательной. Введя в качестве цены единицы ресурса величину u_i0 (i = 1, 2, …, m), ее еще называют оценкой ресурса (или двойственной оценкой), получим следующую модель:

I) F = b₁u₁ + b₂u₂ + … + b_mu_m min.

II) a₁₁u₁ + a₂₁u₂ + … + a_m1u_m c₁,.

a₁₂u₁ + a₂₂u₂ + … + a_m2u_m c₂,.

…

a_1nu₁ + a_2nu₂ + … + a_mnu_m c_n.

III) u_i 0, i = 1, 2, …, m.

Сопоставим обе задачи:

• — первая — задача на максимум (zmax), вторая — на минимум (Fmin);
• — в первой система ограничений типа, во второй ;
• — в первой задаче n неизвестных и m ограничений, во второй m неизвестных и n ограничений;
• — коэффициенты в целевых функциях и величины в правых частях неравенств при переходе из одной задачи в другую меняются местами (в первой задаче c_j — коэффициенты целевой функции, во второй c_j — свободные члены; в первой задаче b_i — свободные члены, во второй b_i — коэффициенты целевой функции);
• — матрицы коэффициентов в первой и второй задаче являются транспонированными относительно друг друга (строки и столбцы поменялись местами).

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

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

• 1) тип экстремума целевой функции меняется;
• 2) каждому ограничению исходной задачи ставится в соответствие переменная двойственной задачи;
• 3) свободные члены исходной задачи становятся коэффициентами при переменных в целевой функции двойственной задачи;
• 4) каждый столбец коэффициентов в системе ограничений формирует ограничение двойственной задачи, при этом тип неравенства меняется; коэффициенты при переменных в целевой функции исходной задачи становятся свободными членами в соответствующих неравенствах двойственной задачи.

Рассмотрим конкретный пример построения двойственной модели:

исходная задача:

I) Z = 6x₁ + 4x₂ max.

II) 2x₁ +4x₂ ? 8,.

2x₁ +x₂ ? 6.

III) x₁? 0, x₂? 0.

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

I) F = 8u₁ + 6u₂ min.

II) 2u₁ + 2u₂? 6,.

4u₁ + u₂? 4.

III) u₁? 0, u₂? 0.

Следует отметить, что:

• — математические модели пары двойственных задач могут быть симметричными и несимметричными. В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной — в виде неравенств, причем в последней переменные могут быть и отрицательными. В симметричных задачах система ограничений как исходной, так и двойственной задачи задается неравенствами, причем на двойственные переменные налагается условие неотрицательности. Чаще рассматриваются симметричные взаимодвойственные задачи;
• — каждая из задач двойственной пары формально является самостоятельной задачей линейного программирования и может решаться независимо от другой. Однако, использование симплексного метода решения одной из двойственных задач двойственной пары автоматически приводит к решению другой задачи. Наглядным обоснованием данного положения может служить возможность использования двойственной симплекс-таблицы для отыскания искомых значений целевых функций.