Название: Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй
Вид работы: контрольная работа
Рубрика: Математика
Размер файла: 113.87 Kb
Скачать файл: referat.me-214592.docx
Краткое описание работы: Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй
Министерствообразования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №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 | ![]() |
![]() |
![]() |
![]() |
- |
![]() |
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 | ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Оптимальное решение двойственной задачи:
,
,
,
Ответ
Оптимальное решение прямой задачи: , X = { 2 , 3 }
Для двойственной задачи: ,
,
,
Похожие работы
-
Симплекс метод 2
Симплекс-метод Симплекс-метод Текущая версия (не проверялась) Не путать с «симплекс-методом» — методом оптимизации произвольной функции. См. Метод Нелдера — Мида
-
Двойственность линейного программирования
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА Реферат по дисциплине «Математические методы принятия управленческих решений»
-
Типовой расчет по ЭМММ
Типовой расчет Решение задач по дисциплине ЭМММ Вариант №23 Выполнил: Проверил: Екатеринбург 2009 Математическая модель ЗЛП Мат. модель ЗЛП называется стандартной, если система ограничений представлена в виде неравенств, а функция минимизируется или максимизируется
-
Задача по Экономико-математическое моделирование
ФЕДЕРАЛЬНОЕ Вариант № . Нефтеперерабатывающий завод производит в месяц 1500000 л алкилата, 1200000 л крекинг - бензина и 1300000 л изопентола. В результате смешения этих компонентов в пропорциях 1:1:1 и 3:1:2 получается бензин сорта А и Б соответственно. Стоимость 1000 л бензина сорта А и Б соответственно равна 90 и 120 усл. ед..
-
Постановка задачи линейного программирования и двойственная задача линейного программирования.
Линейное программирование является составной частью раздела математики, который изучает методы нахождения условного экстремума функции многих переменных и называется математическим программированием. В классическом математическом анализе рассматривается задача отыскания условного экстремума функции.
-
Двойственный симплекс-метод и доказательство теоремы двойственности
ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ Кафедра математики КУРСОВАЯ на тему: Двойственный симплекс-метод и доказательство теоремы двойственности.
-
Задачи по Математике 3
Задача 1 Решить графическим методом задачу линейного программирования А) найти область допустимых значений многоугольник решений Б) найти оптимумы целевой функции
-
Математический расчет объема выпуска продукции
Задача №11 N=25 Завод выпускает изделия трех моделей (1, 2 и 3). Для изготовления используются 2 вида ресурсов А и В, запасы которых составляют 400 и 600 единиц. Расход ресурсов на одно изделие каждой модели приведен в таблице:
-
Математические методы методы
Общая задача линейного программирования Общей задачей линейного программирования называется задача, которая состоит в определении максимального или минимального значения функции
-
Решение задач линейного программирования в среде Maple
Предназначена библиотеки "simplex" для оптимизации линейных систем с использованием симплексного алгоритма. Построение экономико-математической модели формирования плана производства. Основные виды транспортных задач, пример и способы ее решения.