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


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



ЗНАЕТЕ ЛИ ВЫ?

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



 

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

при

(),

().

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

Прямая задача на максимум, значит неравенства должны быть ≤. Умножим второе неравенство на (-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; просмотров: 579; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

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