Главная Учебники - Разные Лекции (разные) - часть 51
Министерствообразования и науки Украины Днепропетровский Национальный Университет Факультет электроники, телекоммуникаций и компьютерных систем Кафедра АСОИ Расчётная задача №4 «Исследование операций» г. Днепропетровск 2007г. Задача Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй Прямая задача имеет вид: Общая постановка двойственной задачи Двойственная задача – это вспомогательная задача линейного программирования, она формулируется из прямой задачи. Идея метода основана на связи между решениями прямой и двойственной задачи. Двойственная задача формируется непосредственно из условий прямой задачи за следующими правилами: Если прямая задача является задачей максимизации, то двойственная будет задачей минимизации; Коэффициенты целевой функции прямой задачи С1, С2, ….,Сn становятся свободными членами ограничений двойственной задачи; Свободные члены ограничений прямой задачи b1, b2, ….,bn становятся коэффициентами целевой функции двойственной задачи; Матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи; Если прямая задача является задачей максимизации, то во всех неравенствах двойственной задачи будут стоять знаки ≥, и знаки ≤, если прямая задача является задачей минимизации. Число ограничений прямой задачи равно числу переменных двойственной задачи. Прямая задача в канонической форме Двойственная к ней задача будет иметь вид Двойственная задача решается симплекс-методом до достижения оптимального решения. Решение прямой задачи Все ограничения прямой задачи - это равенства с неотрицательными правыми частями, когда все переменные неотрицательны. Приведем прямую задачу к стандартному виду: Подставим значение Таким образом, прямая задача в стандартной форме имеет следующий вид: Строим симплекс таблицу: Итерация №1
Итерация №2
Итерация №3
Итерация №4
Оптимальное решение прямой задачи: Решение двойственной задачи Двойственная задача имеет вид: Мы получили двойственную задачу и будем решать ее М-методом. Приведем систему линейных неравенств к стандартному виду, перед этим сделав замену: Подставим значения Таким образом, двойственная задача в стандартной форме имеет следующий вид: Симплекс-таблица, итерация 1
Симплекс-таблица, итерация 2
Симплекс-таблица, итерация 3
Оптимальное решение двойственной задачи: Ответ Оптимальное решение прямой задачи: Для двойственной задачи:
|