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