Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй
Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
| Рубрика | Математика |
| Вид | задача |
| Язык | русский |
| Дата добавления | 21.08.2010 |
| Размер файла | 165,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
7
Министерство образования и науки Украины
Днепропетровский Национальный Университет
Факультет электроники, телекоммуникаций и компьютерных систем
Кафедра АСОИ
Расчётная задача №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 }
Для двойственной задачи: , , ,
Подобные документы
Понятие линейного программирования и его основные методы. Формулировка задачи линейного программирования в матричной форме и ее решение различными методами: графическим, табличным, искусственного базиса. Особенности решения данной задачи симплекс-методом.
курсовая работа [65,3 K], добавлен 30.11.2010Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.
курсовая работа [219,4 K], добавлен 17.04.2013Решение систем уравнений по правилу Крамера, матричным способом, с использованием метода Гаусса. Графическое решение задачи линейного программирования. Составление математической модели закрытой транспортной задачи, решение задачи средствами Excel.
контрольная работа [551,9 K], добавлен 27.08.2009Составление математической модели задачи. Определение всевозможных способов распила 5-метровых бревен на брусья 1,5, 2,4, 3,2 в отношении 1:2:3 так, чтобы минимизировать общую величину отходов. Решение задачи линейного программирования симплекс-методом.
задача [26,1 K], добавлен 27.11.2015Основные сведения о симплекс-методе, оценка его роли и значения в линейном программировании. Геометрическая интерпретация и алгебраический смысл. Отыскание максимума и минимума линейной функции, особые случаи. Решение задачи матричным симплекс-методом.
дипломная работа [351,2 K], добавлен 01.06.2015Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ.
курсовая работа [132,2 K], добавлен 25.11.2011Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Теоретические положения симплекс-метода и постоптимального анализа. Построение математической модели задачи. Нахождение ценностей ресурсов. Определение относительных и абсолютных диапазонов изменения уровней запасов дефицитных и недефицитных ресурсов.
курсовая работа [86,7 K], добавлен 19.11.2010Форма для ввода целевой функции и ограничений. Характеристика симплекс-метода. Процесс решения задачи линейного программирования. Математическое описание алгоритма симплекс-метода. Решение задачи ручным способом. Описание схемы алгоритма программы.
контрольная работа [66,3 K], добавлен 06.04.2012