Лабораторная работа №1 Основы работы в системе Mathcad арифметические вычисления 2 Символьные вычисления 4
жүктеу/скачать 5,09 Mb.
|
3.3. Решение задачи коммивояжераКоммивояжеру нужно посетить 5 городов, затраты на переход из города i в город j заданы матрицей, изображенной на рис.3.1(знак означает запрещение перехода).
Рис 3.1. Матрица затрат в задаче коммивояжера Алгоритм метода ветвей и границ применительно к задаче коммивояжера: 1. Оценка вариантов. Пусть множество всех вариантов задачи. Вычислим оценку этого множества. Рассмотрим конкретный цикл с номерами городов . Затраты в таком цикле будут следующими: . Определим числа . Эти числа представляют собой минимальные затраты на переход из города i во все другие города (рис.3.2).
Рис 3.2. Минимальные затраты на выход из города в задаче коммивояжера Так как из каждого города нужно выйти, суммарные затраты составят не меньше чем . Вычтем эти числа из каждого элемента матрицы затрат . Очевидно, что теперь суммарные затраты составят . Матрица затрат примет следующий вид:
Рис 3.3. Матрица затрат с вычетом Рассмотрим минимальные величины по столбцам , . Эти числа представляют собой минимальные затраты на вход в город j. Так как в каждый город нужно войти, есть минимальные затраты на всем пути.
Рис 3.4. Минимальные затраты на вход в города в задаче коммивояжера Матрица называется приведенной матрицей, и значение функции через элементы этой матрицы будет следующее: . Очевидно, что оценка . Матрица представлена в следующем виде:
Рис. 3.5. Приведенная матрица затрат . 2. Ветвление. Зададим множество , где - номер шага, - варианты множеств решений. 1) - множество всех маршрутов, содержащих путь из города i в город j; 2) - множество всех маршрутов, не содержащих путь из города i в город j; В группу 1) включаем такой переход, который характеризуется минимальными (нулевыми) затратами. Поскольку таких переходов несколько (в данном случае 8), то среди нулевых элементов приведенной матрицы затрат выбираем такой путь, чтобы в группу 2) попали варианты с наибольшими затратами. Тогда для этих двух множеств будут получены оценки, максимально отличающиеся друг от друга. Выбираем пару городов . Если несколько пар –определяем числа . Первое слагаемое в этом выражении характеризует минимальные затраты на выход из города r (переход из r в m запрещен), второе слагаемое – минимальные затраты на вход в город m при этом же условии. Сумма этих чисел дает минимальные затраты для множества маршрутов, не содержащих переход из r в m. Приведем результаты вычислений этих затрат:
Рис. 3.6. Минимальные затраты на выход из города Максимизация затрат по парам городов с нулевыми затратами дает в результате переход из 5-го города в 1-й город (максимальные затраты равны 4):
Рис. 3.7. Минимальные затраты на выход из города и максимальные затраты при запрещенном переходе из города в город Приведем дерево вариантов после первого шага алгоритма с оценками снизу множества решений (рис. 5). Рис. 5. Дерево вариантов после первого шага. На втором шаге развиваем множество , имеющее наименьшую оценку. На следующем шаге вычеркиваем из матрицы затрат 5-ю строку и 1-й столбец, делая невозможным обратный переход (1,5), то есть :
Рис. 3.10. матрица затрат после первого шага Повторяем определение оценки для новой матрицы:
Рис 3.11. Минимальные затраты на выход из города
Рис 3.12. Минимальные затраты на вход в города
Рис. 3.13. Числа , и максимальные затраты при запрещенном переходе из города в город Вычеркиваем 1-ю строку и 2-й столбец. Запрещаем переход .
Рис. 3.14. Приведенная матрица затрат после второго шага Ниже показано полученное дерево вариантов. Рис. 3.14. Дерево вариантов после второго шага Снова определяем оценку:
Рис. 3.15. Числа и
Рис. 3.16. . Числа , и максимальные затраты при запрещенном переходе из города в город Вычеркиваем 2-ю строку, 4-й столбец, запрещаем переход :
Рис. 3.17. Приведенная матрица затрат на последнем шаге Остается единственный вариант (стоимость - 1). Полный замкнутый путь: с затратами 3+3+4+5+10=25. Сравнивая полученное решение с оценками множеств , приходим к выводу, что лучшего решения в этих множествах нет, и они могут быть отброшены (рис. 6). Рис. 6. Дерево вариантов после третьего шага. 3. Отбрасывание вариантов. Если стоимость нашего варианта (25) оказалась бы выше стоимости какого-нибудь из «отвергнутых» вариантов (те, что справа), то пришлось бы раскрывать другой вариант. В данном случае задача решена. Ниже приведен документа MATHCAD (док. Д.6), решающего задачу коммивояжера. Здесь С – матрица затрат в задаче с 5 городами, Аtab – таблица расчетов с приведенной матрицей, p ,q – числа соответственно, Сn_1 – матрица цен для задачи на втором шаге с меньшей размерностью. Лабораторная работа №2. Задача ДП Определить оптимальные вложения ресурса в 100 ед. частями xj по 10 ед. в п=с+3 проектов с функциями прибыли жүктеу/скачать 5,09 Mb. Достарыңызбен бөлісу:
|