 |
Несимметричные двойственные задачи
|
|
|
|
Пуст ЗЛП задана в каноническом виде:
при
(
),
(
).
Переведем данную задачу в симметричную форму:
Прямая задача на максимум, значит неравенства должны быть ≤. Умножим второе неравенство на (-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)
|
|
|
Виды организаций и задачи, их классификации.
Допустимые и оптимальные решения задачи математического программирования.
Задачи изучения дисциплины.
Задачи стратегического управления и его этапы.
Задачи теории массового обслуживания. Классификация систем массового обслуживания
Запишите уравнения Беллмана для общей задачи динамического программирования. Поясните обозначения. В каком порядке их решают?
Индикаторы региональных интересов. Цели и задачи регионального развития
Матрица БКГ: вид, основные стратегические задачи и недостатки модели.
Метод потенциалов решения транспортной задачи. Вырожденная транспортная задача.
Методы нахождения начального допустимого базисного решения транспортной задачи: метод «северо-западного угла», метод минимального элемента, метод Фогеля.
