Задача коммивояжера. Дискретная задача транспортного типа
Решения задачи коммивояжера. Сущность метода прямого перебора. Построение дерева ветвлений и нахождение длины путей. Решение дискретной задачи транспортного типа. Сущность метода "ветвей и границ". Приведение задачи максимизации к задаче минимизации.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 19.04.2013 |
| Размер файла | 358,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru
Уфимский Государственный Авиационный Технический Университет
Кафедра АСУ
Расчетная работа
по дисциплине
«Системный анализ и исследование операций»
Вариант 18
Выполнила: ст. гр. АСОИ-325
Шакирова Л.Р.
Принял: Бабак С.Ф.
Уфа 2005
Задача коммивояжера
Задание:
Решить задачу коммивояжера по следующим данным:
|
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
- |
50 |
33 |
18 |
5 |
44 |
|
|
2 |
51 |
- |
19 |
24 |
20 |
32 |
|
|
3 |
19 |
23 |
- |
42 |
14 |
25 |
|
|
4 |
42 |
53 |
2 |
- |
48 |
5 |
|
|
5 |
27 |
28 |
31 |
33 |
- |
1 |
|
|
6 |
12 |
37 |
60 |
21 |
21 |
- |
Решение:
Приведем данную матрицу по строкам и по столбцам, получим:
Сложив приведение по строкам и по столбцам, получим: 53 + 14 = 67.
Следовательно, Min оценка = 67.
Оценим нули в полученной матрице:
Max оценка = 21.
Разбиваем на 5,6 и not 5,6.
Минор по 5,6.
Вводим запрет на 6,5.
Оценим нули в полученной матрице:
Max оценка = 40.
Разбиваем на 4,3 и not 4,3.
Минор по 4,3.
Вводим запрет на 3,4.
Оценим нули в полученной матрице:
Max оценка = 16.
Разбиваем на 3,2 и not 3,2.
Минор по 3,2.
Вводим запрет на 2,4.
Приводим матрицу по 2 строке и 4 столбцу.
Оценим нули в полученной матрице:
Max оценка = 31.
Разбиваем на 6,1 и not 6,1.
Минор по 6,1.
Вводим запрет на 1,5.
Приводим матрицу по 4 столбцу.
В итоге получим дереве ветвлений и длин путей:
По этому дереву можно определить, что оптимальным путем является последовательность:
5 6 4 3 2 1 5 и его длина равна 76.
Вывод:
Путь является оптимальным, по данному методу, но является и наикротчайшим (в соответствии с методом прямого перебора).
Дискретная задача транспортного типа
Задание:
Решить транспортную задачу по следующим данным:
Задача максимизации.
Решение:
Приведем задачу максимизации к задаче минимизации:
Приведем данную матрицу по строкам и по столбцам, получим:
Сложив приведение по строкам и по столбцам, получим: -75 + 6 = -69.
Следовательно, Min оценка = -69.
1. Оценим нули в полученной матрице:
Max оценка = 9.
Разбиваем на 7,4 и not 7,4.
Минор по 7,4. коммивояжер задача транспортный дискретный
2. Оценим нули в полученной матрице:
Max оценка = 2.
Разбиваем на 2,3 и not 2,3.
Минор по 2,3.
3. Оценим нули в полученной матрице:
Max оценка = 5.
Разбиваем на 4,1 и not 4,1.
Минор по 4,1.
4. Оценим нули в полученной матрице:
Max оценка = 1.
Разбиваем на 5,7 и not 5,7.
Минор по 5,7.
5. Оценим нули в полученной матрице:
Max оценка = 1.
Разбиваем на 3,2 и not 3,2.
Минор по 3,2.
6. Завершаем цикл:
Вводим недостающие ребра: 6,6 и 1,5.
В итоге получим дерево ветвлений и длин путей:
По этому дереву можно определить, что оптимальным путем является последовательность:
7 4 1 5 2 3 6 5 и его длина равна (при переходе к задаче максимизации домножаем на -1).
Вывод:
Путь является оптимальным, по методу «ветвей и границ», в данной модели нет строгого правила: обход каждой вершины по одному разу, поэтому допускается как переход из вершины в туже вершину, так и проход через одну вершину несколько раз. Однако для данной постановки задачи наиболее удачным является гамильтонов цикл.
Размещено на Allbest.ru
Подобные документы
Сущность и содержание, основные понятия и критерии теории графов. Понятие и общее представление о задаче коммивояжера. Описание метода ветвей и границ, практическое применение. Пример использования данного метода ветвей для решения задачи коммивояжера.
контрольная работа [253,0 K], добавлен 07.06.2011Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
курсовая работа [393,2 K], добавлен 18.06.2011Формирование нижних и верхних оценок целевой функции. Алгоритм метода ветвей и границ, решение задач с его помощью. Решение задачи коммивояжера методом ветвей и границ. Математическая модель исследуемой задачи, принципы ее формирования и порядок решения.
курсовая работа [153,2 K], добавлен 25.11.2011Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.
курсовая работа [118,7 K], добавлен 30.04.2011Методика решения задач высшей математики с помощью теории графов, ее сущность и порядок разрешения. Основная идея метода ветвей и границ, ее практическое применение к задаче. Разбиение множества маршрутов на подмножества и его графическое представление.
задача [53,0 K], добавлен 24.07.2009Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.
курсовая работа [541,3 K], добавлен 08.10.2015Сущность методов сведения краевой задачи к задаче Коши и алгоритмы их реализации на ПЭВМ. Применение метода стрельбы (пристрелки) для линейной краевой задачи, определение погрешности вычислений. Решение уравнения сшивания для нелинейной краевой задачи.
методичка [335,0 K], добавлен 02.03.2010Составление математической модели задачи. Приведение ее к стандартной транспортной задаче с балансом запасов и потребностей. Построение начального опорного плана задачи методом минимального элемента, решение методом потенциалов. Анализ результатов.
задача [58,6 K], добавлен 16.02.2016Последовательность решения линейной краевой задачи. Особенности метода прогонки. Алгоритм метода конечных разностей: построение сетки в заданной области, замена дифференциального оператора. Решение СЛАУ методом Гаусса, конечно-разностные уравнения.
контрольная работа [366,5 K], добавлен 28.07.2013Математическое моделирование и особенности задачи распределения. Обоснование и выбор метода решения. Ручное решение задачи (венгерский метод), а также с использованием компьютера. Формулировка полученного результата в сопоставлении с условием задачи.
курсовая работа [383,9 K], добавлен 26.05.2010
