Двойственные задачи в линейном программировании.
Каждой задаче линейного программирования можно поставить в соответствие другую ЗЛП, называемую двойственной. Первоначальная задача называется прямой или исходной. Обычно говорят о паре взаимно двойственных задач ЛП. Пара симметричных двойственных ЗЛП имеет вид:
Рассмотренная пара взаимно двойственных задач может быть экономически интерпретирована, например, так. Прямая задача: сколько и какой продукции надо произвести, чтобы при заданных стоимостях единицы продукции , объёмах имеющихся ресурсов и нормах расходов aij максимизировать выпуск продукции в стоимостном выражении ? Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных bi, cj, aij минимизировать общую оценку затрат на все ресурсы? {Т.е., предположим, что некоторая организация может закупить все ресурсы, которыми располагает предприятие. Необходимо определить оптимальные цены yi на эти ресурсы исходя условий, что покупающая организация стремится минимизировать общую оценку ресурсов и при этом за ресурсы покупающая организация должна уплатить сумму, не меньшую той, которую может выручить предприятие при организации собственно производства продукции.}
Для построения двойственной задачи к общей ЗЛП можно воспользоваться следующими правилами: 1)если прямая задача решается на максимум, то двойственная – на минимум, и наоборот; 2)в задаче на максимум ограничения–неравенства должны быть вида ≤,в задаче на минимум - ≥. Выполнение этих условий достигается умножением соответствующих ограничений на (-1); 3)каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи; 4)матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием; 5)свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот; 6)если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение – неравенство, если же нет, то как ограничение – равенство; 7)если какое – либо ограничение прямой задачи записывается как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.
Принцип двойственности (теорема о минимаксе): Если одна из двойственных задач имеет оптимальное решение , то и другая имеет оптимальное решение При этом экстремальные значения целевых функций задач совпадают, т.е. z* = f* Если целевая функция одной из задач двойственной пары не ограничена, то другая задача не имеет решения. Из этой теоремы следует: 1) для разрешимости одной из двойственных задач необходимо и достаточно, чтобы каждая из задач имела хотя бы одно решение; 2) для того, чтобы планы и являлись оптимальными решениями пары двойственных зада, необходимо и достаточно, чтобы выполнялось равенство: Связь между задачами двойственной пары глубже, чем указано в формулировке теоремы: решая симплексным методом одну из них, автоматически получаем решение другой. Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач и оценок в последней симплексной таблице:
Отсюда имеем оптимальный план двойственной задачи. Если прямая задача решается на max, то Если прямая задача решается на минимум, то :
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|