Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Скачиваний:
48
Добавлен:
02.05.2014
Размер:
691.2 Кб
Скачать

Дискретная задача транспортного типа

Задание:

Решить задачу коммивояжера по следующим данным:

Решение:

Приведем данную матрицу по строкам и по столбцам, получим:

Сложив приведение по строкам и по столбцам, получим: 6 + 2 = 8.

Следовательно, Min оценка = 8.

1. Оценим нули в полученной матрице:

Max оценка = 5.

Разбиваем на 5,5 и not 5,5.

Минор по 5,5.

2. Оценим нули в полученной матрице:

Max оценка = 3.

Разбиваем на 1,8 и not 1,8.

Минор по 1,8.

3. Оценим нули в полученной матрице:

Max оценка = 3.

Разбиваем на 7,7 и not 7,7.

Минор по 7,7.

4. Оценим нули в полученной матрице:

Max оценка = 2.

Разбиваем на 4,3 и not 4,3.

Минор по 4,3.

5. Оценим нули в полученной матрице:

Max оценка = 5.

Разбиваем на 2,2 и not 2,2.

Минор по 2,2.

5. Оценим нули в полученной матрице:

Max оценка = 1.

Разбиваем на 8,6 и not 8,6.

Минор по 8,6.

6. Оценим нули в полученной матрице:

Max оценка = 9.

Разбиваем на 6,1.

Минор по 6,1.

В итоге получим дереве ветвлений и длин путей:

По этому дереву можно определить, что оптимальным путем является последовательность:

1  8  6  1  7  7  2  2  4  3  5  5  1 и его длинна равна 40.

Вывод:

Путь является оптимальным, по методу «ветвей и границ», в данной модели нет строгого правила: обход каждой вершины по одному разу, поэтому допускается как переход из вершины в туже вершину, так и проход через одну вершину несколько раз.

Соседние файлы в папке Задача 2