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





Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



 

Пуст ЗЛП задана в каноническом виде:

при

( ),

( ).

Переведем данную задачу в симметричную форму:

Прямая задача на максимум, значит неравенства должны быть ≤. Умножим второе неравенство на (-1). Получим:

Составим двойственную задачу для полученной симметричной. Для этого введем двойственные переменные и . Получим:

при ограничениях:

Преобразуем систему ограничений следующим образом:

Обозначим y разность . и положительны, но их разность может быть как положительна, так и отрицательна.

В результате получим двойственную задачу вида:

при

Подводя итоги вышеизложенному, опишем прямую и двойственную задачу для ЗЛП в общем случае:

при ( ), ( ), ( ), – любого знака ( ). при ( ), ( ), ( ), – любого знака ( ).

Таким образом, двойственная задача со смешанными ограничениями составляется с соблюдением следующих дополнительных правил:

1. Если на переменную прямой задачи наложено условие неотрицательности, то j-тое условие системы ограничений двойственной задачи в виде неравенств и наоборот.

2. Если на переменную прямой задачи не наложено условие неотрицательности, то j-тое ограничение двойственной задачи записывается в виде строго равенства.

3. Если в прямой задачи имеются ограничения равенства, то на соответствующие переменные двойственной задачи не налагается условие неотрицительности.

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

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

Теорема 1: (об основном неравенстве двойственности) Для любых допустимых планов X= и Y= прямой и двойственной задачи линейного программирования справедливо неравенство:

.

Экономическое содержание основного неравенства двойственности состоит в том, что для любого допустимого плана производства Х и любого вектора оценок ресурсов Y общая созданная стоимость не превосходит суммарной оценки ресурсов.

Теорема 2: (критерий оптимальности Канторовича) Если для некоторых допустимых планов и пары двойственных задач выполняется равенство z( )=f( ), то и являются оптимальными планами соответствующих задач.

Экономическое содержание теоремы состоит в том, что план производства Х и вектор оценок ресурсов Y является оптимальным, если цена всей произведенной продукции и суммарная оценка ресурсов совпадают.

Теорема 3: (малая теорема двойственности) Для существования оптимального плана любой из пары двойственных задач необходимо и достаточно существование допустимого плана для каждой из них.

Теорема 4: Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций равны: z( )=f( ). Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых планов, то система ограничений другой – противоречива.

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

Пример 1: Решить исходную задачу линейного программирования, исходя из решения двойственной:

при

Решение.

Преобразуем систему ограничений следующим образом:

Составим двойственную задачу для данной:

при

Решим полученную задачу симплексным методом. Преобразуем систему ограничений следующим образом:

Для полученной М-задачи составим симплексную таблицу.

БП СБ А
-4 -6 M M M
M -1 -1 -1
M -1 -1
M -1
M -1 -1 -1
св. член -8
-1 -1 -1  
M -1
M -1
M -1 -1  
св. член -4 -2 -8
-1 -1/2 -1/2    
-4 1/2 -1/2
M 1/2 1/2 -1
M 1/2 1/2 -1    
св. член -2 -6
-1  
-4 1/2 -1/2
-6 1/2 1/2 -1
  -5 -1 -2

Полученный план оптимальный.

f=10 в (2, 0, 1, 0, 0, 0, 0)

Найдем решение прямой задачи.

Z=10 в (5, 1, 2)

 





Последнее изменение этой страницы: 2016-06-07; просмотров: 300; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.87.33.97 (0.009 с.)