Задача Записать задачу двойственную к данной решить одну из пары задач и отыскать оптимальное решение
Работа добавлена на сайт bukvasha.net: 2015-10-29Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
![](https://bukvasha.net/assets/images/emoji__ok.png)
Предоплата всего
![](https://bukvasha.net/assets/images/emoji__signature.png)
Подписываем
Министерство образования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №4
«Исследование операций»
г. Днепропетровск
2007г.
Задача
Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй
Прямая задача имеет вид:
Общая постановка двойственной задачи
Двойственная задача – это вспомогательная задача линейного программирования, она формулируется из прямой задачи.
Идея метода основана на связи между решениями прямой и двойственной задачи.
Двойственная задача формируется непосредственно из условий прямой задачи за следующими правилами:
Если прямая задача является задачей максимизации, то двойственная будет задачей минимизации;
Коэффициенты целевой функции прямой задачи С1, С2, ….,Сn становятся свободными членами ограничений двойственной задачи;
Свободные члены ограничений прямой задачи b1, b2, ….,bn становятся коэффициентами целевой функции двойственной задачи;
Матрицу ограничений двойственной задачи получают транспонированием матрицы ограничений прямой задачи;
Если прямая задача является задачей максимизации, то во всех неравенствах двойственной задачи будут стоять знаки ≥, и знаки ≤, если прямая задача является задачей минимизации.
Число ограничений прямой задачи равно числу переменных двойственной задачи.
Прямая задача в канонической форме
Двойственная к ней задача будет иметь вид
Двойственная задача решается симплекс-методом до достижения оптимального решения.
Решение прямой задачи
Все ограничения прямой задачи - это равенства с неотрицательными правыми частями, когда все переменные неотрицательны.
Приведем прямую задачу к стандартному виду:
Подставим значение в целевую функцию:
Таким образом, прямая задача в стандартной форме имеет следующий вид:
Строим симплекс таблицу:
Итерация №1
Базис | | | | | | | Решение | Оценка |
| | | 0 | 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 | 0 | | -1 | 1 | 2 | |
- ведущий столбец
- ведущая строка
Итерация №3
Базис | | | | | | | Решение | Оценка | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 0 | 0 | | | | |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 0 | 1 | | | | | | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 0 | 1 | 0
Итерация №4
Оптимальное решение прямой задачи: Решение двойственной задачи Двойственная задача имеет вид: Мы получили двойственную задачу и будем решать ее М-методом. Приведем систему линейных неравенств к стандартному виду, перед этим сделав замену: Подставим значения Таким образом, двойственная задача в стандартной форме имеет следующий вид: Симплекс-таблица, итерация 1
Симплекс-таблица, итерация 2
Симплекс-таблица, итерация 3
Оптимальное решение двойственной задачи: Ответ Оптимальное решение прямой задачи: Для двойственной задачи: 2. Реферат Дворцовые перевороты 2 3. Реферат Спор и его виды 4. Реферат Анализ финансово хозяйственной деятельности 5. Сочинение на тему Некрасов н. а. Русский народ в изображении н. а. некрасова 6. Курсовая Создание программы для определения вершин пирамиды с выпуклым основанием по данным точкам 7. Реферат на тему Розвиток соціальної політики по відношенню жінок Ірану 8. Реферат Размещение и обеспеченность природными ресурсами различных стран 9. Реферат Состояние финансового сотрудничества в странах Латинской Америки 10. Реферат на тему Video Games Essay Research Paper DNA Structure |