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