Записать задачу двойственную к ней, чтобы решить одну из пары задач и найти оптимальное решение второй

Министерство образования и науки Украины

Днепропетровский Национальный Университет

Факультет электроники, телекоммуникаций и компьютерных систем

Кафедра АСОИ

Дизайн задача № 4

"Исследование операций"

Днепропетровска

2007.

Задача

Запишите задачу, двойственную к ней, чтобы решить одну из пары задач и найти оптимальное решение второй

Прямая задача имеет вид:

Общая постановка двойственной задачи

Двойственная задача – это вспомогательная задача линейного программирования, она формулируется прямо из задачи.

Идея метода основана на связи между решениями прямой и двойственной задачи.

Двойной нагрузки образуются непосредственно из условий прямой задачи по следующим правилам:

Если прямая задача является задачей максимизации, то двойственная будет задачей минимизации;

Коэффициенты целевой функции прямой задачи C1, C2, ....,Сп становятся свободными членами ограничений двойственной задачи;

Свободные члены ограничений прямой задачи b1, b2, ....,bn становятся коэффициентами целевой функции двойственной задачи;

Матрица ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;

Если прямая задача является задачей максимизации, то во всех неравенствах двойственной задачи будут стоять знаки ≥, и знаки ≤, если прямая задача является задачей минимизации.

Число ограничений прямой задачи равно числу переменных двойственной задачи.

Прямая задача в канонической форме

Двойственная к ней задача будет иметь вид < / p>

Двойная проблема будет решена симплекс-методом до достижения оптимального решения.

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

Все ограничения прямой задачи-это равенства с числами подходящих частей, когда все переменные неотрицательны.

Да прямая задача в стандартной виду:

Заменить значение в зависимости от назначения:

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

Строим таблицу симплекс:

Повторения нет. 1