Здавалка
Главная | Обратная связь

Двойственные задачи в линейном программировании.

 

Каждой задаче линейного программирования можно поставить в соответствие другую ЗЛП, называемую двойственной.

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

Обычно говорят о паре взаимно двойственных задач ЛП.

Пара симметричных двойственных ЗЛП имеет вид:

 

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

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

Прямая задача: сколько и какой продукции надо произвести, чтобы при заданных стоимостях единицы продукции , объёмах имеющихся ресурсов и нормах расходов aij максимизировать выпуск продукции в стоимостном выражении ?

Двойственная задача: какова должна быть оценка единицы каждого из ресурсов , чтобы при заданных bi, cj, aij минимизировать общую оценку затрат на все ресурсы?

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

 

Для построения двойственной задачи к общей ЗЛП можно воспользоваться следующими правилами:

1)если прямая задача решается на максимум, то двойственная – на минимум, и наоборот;

2)в задаче на максимум ограничения–неравенства должны быть вида ≤,в задаче на минимум - ≥. Выполнение этих условий достигается умножением соответствующих ограничений на (-1);

3)каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;

4)матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;

5)свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;

6)если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение – неравенство, если же нет, то как ограничение – равенство;

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

 

Принцип двойственности (теорема о минимаксе):

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

z* = f*

Если целевая функция одной из задач двойственной пары не ограничена, то другая задача не имеет решения.

Из этой теоремы следует:

1) для разрешимости одной из двойственных задач необходимо и достаточно, чтобы каждая из задач имела хотя бы одно решение;

2) для того, чтобы планы и являлись оптимальными решениями пары двойственных зада, необходимо и достаточно, чтобы выполнялось равенство:

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

 

x1 x2 xn   xn+1 xn+2 xn+m
ym+1 ym+2 ym+n   y1 y2 ym
Δ1* Δ2* Δn*   ...

 

Отсюда имеем оптимальный план двойственной задачи. Если прямая задача решается на max, то

Если прямая задача решается на минимум, то :

 

 





©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.