Referat.me

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

Вид работы: контрольная работа

Рубрика: Математика

Размер файла: 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" для оптимизации линейных систем с использованием симплексного алгоритма. Построение экономико-математической модели формирования плана производства. Основные виды транспортных задач, пример и способы ее решения.