- •Содержание
- •7. Задача об оптимальном назначении 38
- •Методы оптимизации
- •1. Основные понятия линейного программирования
- •Рассмотрим правила перехода от одной модели к другой.
- •1.1 Переход от стандартной модели злп к канонической
- •1.2. Переход от канонической модели задачи лп к стандартной
- •1.3. Переход от основной модели задачи лп к канонической
- •2. Геометрическая иллюстрация решения задач лп
- •3. Двойственность в задачах линейного программирования
- •3.1. Построение двойственных моделей
- •Правило построения двойственной модели:
- •3.2. Теоремы двойственности
- •3.3. Экономическая интерпретация переменных двойственной задачи
- •4. Симплекс-метод в задачах лп
- •4.1. Основные положения симплекс-метода
- •4.2. Правило преобразования симплекс-таблиц
- •4.3. Геометрическая интерпретация симплекс-метода
- •5. Метод искусственного базиса
- •5.1. Постановка задачи
- •5.2. Теоремы метода
- •Замечания к теоремам
- •5.3. Примеры решения задач
- •Индивидуальные задания Задание 1
- •6. Транспортная задача линейного программирования
- •6.1. Транспортная задача линейного программирования
- •6.1.1. Постановка задачи
- •6.1.2. Математическая модель
- •Функция цели задачи по критерию минимума суммарных затрат –
- •6.2. Методы определения начального опорного плана
- •6.2.1. Метод северо-западного угла
- •6.2.2. Метод наименьшей стоимости
- •6.2.3. Метод двойного предпочтения
- •6.3. Метод потенциалов
- •6.4. Построение цикла и определение величины перераспределения груза
- •6.5. Открытая транспортная задача
- •6.6. Проблема вырожденного плана задачи
- •Индивидуальные задания
- •7. Задача об оптимальном назначении
- •7.1. Постановка задачи
- •7.2. Математическая модель
- •7.3. Решение задачи о назначениях венгерским методом
- •7.4. Решение задачи максимизации
- •Индивидуальные задания
- •Библиографический список
- •Линейное программирование
- •620034 ,Екатеринбург, ул. Колмогорова 66, УрГупс
3. Двойственность в задачах линейного программирования
3.1. Построение двойственных моделей
Двойственная задача – это вспомогательная задача ЛП, формулируемая с помощью определенного правила непосредственно из условия исходной задачи. Заметим, что для разных моделей исходной задачи правила построения двойственных моделей отличаются.
Рассмотрим правило построения двойственной модели, если исходная задача задана в виде стандартной модели:
(3.1)
(3.2)
Правило построения двойственной модели:
1. Надо проверить, отвечает ли исходная модель двум требованиям:
а) все неравенства в системе (3.1) имеют одинаковый знак « » или (« »).
б) если целевая функция ЗЛП максимизируется, то знак в неравенствах должен быть «», а если целевая функция минимизируется, то знак должен быть «». В нашей модели это требование выполнено.
2. Каждому i-тому ограничению исходной задачи соответствует j-тое неизвестное в двойственной задаче: так, неравенству соответствует
3. Каждому неизвестному исходной модели соответствует ограничение двойственной модели. Матрица коэффициентов при неизвестных двойственной задачи является транспонированной матрицей исходной задачи. Неравенства ограничения имеют противоположный смысл неравенствам исходной задачи. Правые части ограничений равны коэффициентам функции цели прямой задачи. Таким образом, для i-ой переменной получим
4. Целевая функция двойственной модели имеет вид:
,
и решается задача минимизации. Запишем модели по соответствию:
Такие модели задачи ЛП называются симметричными. Заметим, что для полученной двойственной модели можно также построить по тем же првилам двойственную модель, которая будет представлять исходную модель ЗЛП.
В случае если исходная задача ЛП − основная задача минимизации, то двойственная ей стандартная задача максимизации. Пара таких задач имеет вид:
при этом переменные второй задачи могут иметь любой знак.
Для двойственных задач справедливы следующие теоремы двойственности.
3.2. Теоремы двойственности
Теорема 1. Если X – любое опорное решение исходной задачи, а Y – любое опорное решение соответствующей ей двойственной задачи, то .
Теорема 2. Если одна из взаимно двойственных задач имеет оптимальное решение, то и другая тоже имеет оптимальное решение, причем оптимальные значения целевых функций равны между собой .
Теорема 3. Если одна из взаимодвойственных моделей не имеет оптимального решения (например, целевая функция неограниченна), то и другая не имеет допустимых решений, то есть система ограничений в ней – несовместна.
Теорема 4. Пусть одна из взаимно двойственных задач имеет оптимальное решение. Тогда для неизвестных и ограничений выполняются следующие условия:
1) если координата хj оптимального плана исходной модели строго положительна, то соответствующее ограничение выполняется при подстановке в него координат оптимального решения, как уравнение;
2) если при подстановке Xопт в какое-либо ограничение исходной задачи оно выполняется как строгое неравенство, то соответствующая ему переменная уi равна нулю.
Теорема 5. Для того, чтобы два допустимых решения Х* и Y* пары двойственных задач были оптимальными решениями, необходимо и достаточно, чтобы они удовлетворяли системе уравнений:
Зная оптимальное решение одной из двойственных задач, можно, используя теоремы двойственности, найти оптимальное решение другой. Рассмотрим пример.
Пример. Вернемся к задаче, решение которой мы получили в п.2. Построим для заданной модели двойственную и решим ее с помощью теорем двойственности:
1 2x1+4x2 ≤ 300, y1 ≥ 0,
4x1+4x2 ≤ 120, y2 ≥ 0,
3x1+12x2 ≤ 252, y3 ≥ 0,
x1 ≥ 0, 12y1 +4y2+3y3 ≥ 30,
x2 ≥ 0, 4y1+4y2+12y3 ≥ 40,
f(x) = 30x1 + 40 x2 → max. q(y) = 300 y1 + 120y2 + 252y3 →min.
Двойственная модель задача ЛП построена по правилу, изложенному ранее.
Нам известно, что исходная задача имеет оптимальное решение:
Xmax = (12, 18), fmax = f (Xmax) = 1080.
Воспользуемся первой теоремой двойственности. Двойственная модель тоже имеет оптимальное решение, причем оптимальное значение целевой функции q(y) тоже равно 1080, то есть q(Ymin) = 1080.
Далее, будем использовать теорему 4. Начнем с 1-ой части:
x1 = 12 > 0 12y1+4y2+3y3 = 30,
x2 = 18 > 0 4y1+4y2+12y3 = 40.
Подставим оптимальное решение xmax в ограничения задачи:
144 + 72 = 216 < 300 у1 = 0,
48 + 72 = 120 = 120 у2 > 0,
36 + 216 = 252 = 252 у3 > 0.
Получим систему уравнений для определения оптимального решения двойственной модели:
Получим: , ,
Проверим расчет: .
Задача решена.