Методы оптимальных решений
Знакомство с особенностями метода полного исключения неизвестных. Анализ этапов постройки двойственной задачи. Общая характеристика методов оптимальных решений. Способы нахождения оптимального плана двойственной задачи из графического решения прямой.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 07.10.2013 |
| Размер файла | 2,1 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Методы оптимальных решений
оптимальный решение двойственный задача
Задача 1
Необходимо, применяя метод полного исключения неизвестных (Жордана-Гаусса), найти любое общее и три базисных решения системы. Сделать проверку. Решение рекомендуется представить в виде таблицы.
Таблица. Решение:
Общее решение:
Xбаз1 = .
Проверка:
Таблица
xбаз2 = .
Проверка:
Таблица
xбаз3 = .
Проверка:
Задача 2
Необходимо последовательно выполнить следующие задания.
1. Задачу решить графическим методом.
2. Применяя симплекс-метод, решить задачу или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.
3. Построить двойственную задачу. Если вектор найден, вычислить оптимальный план двойственной задачи, используя первую теорему двойственности . Вычислить значение функции .
4. Провести анализ полученного решения, применяя условия дополняющей нежесткости.
Если , то . Если , то .
Таблица
|
2 |
-1 |
8 |
15 |
24 |
min |
|
|
4 |
2 |
9 |
12 |
13 |
64 |
|
|
3 |
8 |
5 |
11 |
10 |
56 |
|
|
2 |
6 |
8 |
7 |
7 |
38 |
Решение:
1. Рассмотрим каноническую задачу
Таблица
Получаем общее решение:
Т.к. , то
,
Строим граничные прямые
(1)
(2)
(3)
Рис.
Область решений 4-х угольник АВСД
Функция достигает минимума в точке А.
,
2. Решим задачу симплекс методом
Таблица
Двойственная задача
Проведем анализ полученного решения
Задача 3
1. Найти оптимальный план прямой задачи графическим методом.
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план прямой задачи симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
5. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи. Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
6. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, полученный графическим методом.
Решение:
1. Решим задачу графическим методом
Строим граничные прямые
(1)
(2)
(3)
Рис.
Область решений - выпуклый 6-тиугольник ABCDEF
Функция достигает максимума в точке Д.
- оптимальный план прямой задачи
2. Построим двойственную задачу.
Для этого умножим 2-ое неравенство системы ограничений исходной задачи на (-1).
3. Условие дополняющей нежесткости
Граничные прямые (2) и (3) не проходят через оптимальную точку, следовательно,
Получим систему уравнений
- оптимальный план двойственной задачи
=
Найдем оптимальный план прямой задачи симплекс-методом
Каноническая задача:
Расширенная задача
Таблица
- оптимальный план прямой задачи,
4. Оптимальное решение двойственно задачи определим из соотношения:
- оптимальный план двойственной задачи
=
Т.е., целевые функции совпадают.
5. Решим двойственную задачу симплекс-методом
Каноническая задача
,
Расширенная задача:
,
Таблица
- оптимальный план двойственной задачи
=
Найдем оптимальный план прямой задачи по I теореме двойственности:
- оптимальный план прямой задачи
Этот результат совпадает с результатом, который был получен графическим методом.
Задача 4
Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности - снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.
Рис.
Решение:
1. Метод северо-западного узла
Рис
Рис.
Рис
Рис.
Рис.
Рис.
Рис.
Рис
Рис.
2. Метод минимального элемента
Рис
Рис
Рис.
Рис.
Рис.
Рис.
Рис.
Рис.
Задача 5
Задача изображена в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей , на вершинах (в кружках) - значения запасов-потребностей . Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
Рис.
Решение:
Процесс решения задачи начинается с построения опорного плана и проверки оптимальности методом потенциалов
Рис.
Число вершин = 13, число ребер=20, число базисных ребер=13-1=12.
Рис.
Рис.
Задача 6
Таблица, в клетках которой проставлены элементы матрицы эффективностей задачи о разборчивой невесте. Необходимо найти оптимальный вариант выбора, при котором средняя продолжительность семейной жизни каждой семьи будет наибольшей. Решить задачу методом потенциалов и венгерским методом.
Таблица
|
51 |
47 |
10 |
30 |
44 |
22 |
38 |
|
|
29 |
21 |
22 |
27 |
10 |
43 |
3 |
|
|
6 |
42 |
35 |
39 |
34 |
45 |
26 |
|
|
25 |
14 |
18 |
21 |
23 |
47 |
15 |
|
|
4 |
36 |
21 |
36 |
31 |
13 |
41 |
|
|
40 |
11 |
33 |
7 |
35 |
37 |
19 |
|
|
9 |
20 |
50 |
45 |
46 |
48 |
53 |
Решение:
Таблица. Венгерский метод
|
51 |
47 |
10 |
30 |
44 |
22 |
38 |
|
|
29 |
21 |
22 |
27 |
10 |
43 |
3 |
|
|
6 |
42 |
35 |
39 |
34 |
45 |
26 |
|
|
25 |
14 |
18 |
21 |
23 |
47 |
15 |
|
|
4 |
36 |
21 |
36 |
31 |
13 |
41 |
|
|
40 |
11 |
33 |
7 |
35 |
37 |
19 |
|
|
9 |
20 |
50 |
45 |
46 |
48 |
53 |
Таблица
|
0 |
0 |
40 |
15 |
2 |
26 |
15 |
|
|
22 |
26 |
28 |
18 |
36 |
5 |
50 |
|
|
45 |
5 |
15 |
6 |
12 |
3 |
27 |
|
|
26 |
33 |
32 |
24 |
23 |
1 |
38 |
|
|
47 |
11 |
29 |
9 |
15 |
35 |
12 |
|
|
11 |
36 |
17 |
38 |
11 |
11 |
34 |
|
|
42 |
27 |
0 |
0 |
0 |
0 |
0 |
Таблица
|
+ |
+ |
+ |
+ |
+ |
||||
|
01 |
0* |
40 |
15 |
2 |
26 |
15 |
+ |
|
|
17 |
21 |
23 |
13 |
31 |
0 |
45 |
||
|
42 |
2 |
12 |
3 |
9 |
0 |
24 |
||
|
25 |
32 |
31 |
23 |
22 |
0* |
37 |
||
|
38 |
2 |
20 |
0* |
6 |
26 |
3 |
||
|
0* |
25 |
6 |
27 |
01 |
0 |
23 |
+ |
|
|
42 |
27 |
01 |
0 |
0 |
0 |
0* |
+ |
Рис.
Рис.
2. Метод потенциалов
Рис.
Рис.
Размещено на Allbest.ru
...Подобные документы
Геометрический смысл решений неравенств, уравнений и их систем. Определение понятия двойственности с помощью преобразования Лежандра. Разбор примеров нахождения переменных или коэффициентов при неизвестных в целевой функции двойственной задачи.
дипломная работа [2,6 M], добавлен 30.04.2011Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Описание метода потенциалов Математическая постановка задачи об оптимальных перевозках. Метод решения задачи об оптимальных перевозках средствами Ms Excel. Постановка параметрической транспортной задачи, ее математическое и компьютерное моделирование.
курсовая работа [802,5 K], добавлен 21.10.2014Поиск оптимальных значений некоторых параметров в процессе решения задачи оптимизации. Сравнение двух альтернативных решений с помощью целевой функции. Теорема Вейерштрасса. Численные методы поиска экстремальных значений функций. Погрешность решения.
презентация [80,6 K], добавлен 18.04.2013Сущность графического метода нахождения оптимального значения целевой функции. Особенности и этапы симплексного метода решения задачи линейного программирования, понятие базисных и небазисных переменных, сравнение численных значений результатов.
задача [394,9 K], добавлен 21.08.2010Графическое решение задачи линейного программирования. Общая постановка и решение двойственной задачи (как вспомогательной) М-методом, правила ее формирования из условий прямой задачи. Прямая задача в стандартной форме. Построение симплекс таблицы.
задача [165,3 K], добавлен 21.08.2010Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.
контрольная работа [333,3 K], добавлен 27.11.2011Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.
задача [656,1 K], добавлен 01.06.2016Общая характеристика примеров нахождения точки пересечения двух прямых. Знакомство с условиями параллельности и перпендикулярности прямых, рассмотрение особенностей решения уравнений. Анализ способов нахождения углового коэффициента искомой прямой.
презентация [97,6 K], добавлен 21.09.2013Структура текстовой задачи. Условия и требования задач и отношения между ними. Методы и способы решения задач. Основные этапы решения задач. Поиск и составление плана решения. Осуществление плана решения. Моделирование в процессе решения задачи.
презентация [247,7 K], добавлен 20.02.2015Теория игр – раздел математики, предметом которого является изучение математических моделей принятия оптимальных решений в условиях конфликта. Итеративный метод Брауна-Робинсона. Монотонный итеративный алгоритм решения матричных игр.
дипломная работа [81,0 K], добавлен 08.08.2007Двойственные задачи в линейном программировании. Симметричные и несимметричные двойственные задачи. Связь исходной и двойственной задач. Анализ моделируемой ситуации (моделируемого объекта). Реализация двойственности на Visual Basic for Application.
курсовая работа [703,5 K], добавлен 14.10.2011Задачи с параметрами и методы их решений. Использование свойств функций, параметра как равноправной переменной, симметрии аналитических выражений, "каркаса" квадратичной функции, теоремы Виета. Трансцендентные уравнения с параметром и методы их решений.
дипломная работа [3,2 M], добавлен 06.11.2013Изучение прямых методов решения вариационных и краевых задач математического анализа. Основные идеи методов Ритца и Галеркина для нахождения приближенного обобщенного решения задачи минимизации функционала. Особенности, сходство и отличие данных методов.
презентация [187,9 K], добавлен 30.10.2013Характеристика уравнений с разделяющимися переменными. Сущность метода Бернулли и метода Лагранжа, задачи Коша. Решение линейных уравнений n-го порядка. Фундаментальная система решений - набор линейно независимых решений однородной системы уравнений.
контрольная работа [355,9 K], добавлен 28.02.2011Основные положения теории принятия решений, разработанной на основе математических методов и формальной логики, классификация управленческих решений. Некорректно поставленные задачи и регуляризирующие (робастные) алгоритмы: адаптивные, инвариантные.
курсовая работа [1,1 M], добавлен 23.11.2010Применение метода дискретной регуляризации Тихонова А.Н. для нахождения решения обратной задачи для однородного бигармонического уравнения в круге. Сведение дифференциальной задачи к интегральному уравнению; корректно и некорректно поставленные задачи.
курсовая работа [280,2 K], добавлен 20.10.2011Анализ особенностей разработки вычислительной программы. Общая характеристика метода простых итераций. Знакомство с основными способами решения нелинейного алгебраического уравнения. Рассмотрение этапов решения уравнения методом половинного деления.
лабораторная работа [463,7 K], добавлен 28.06.2013Развитие численных линейных методов решения задач линейного программирования. Знакомство с методами поиска целевой функции: равномерный симплекс, методы Коши, Ньютона, сопряжённого градиенты, квазиньютоновский метод. Алгоритмы нахождения экстремума.
курсовая работа [716,1 K], добавлен 12.07.2012
