Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


В нашем случае маршрут может быть замкнут, при этом оценки всех нулей 0j будут тоже нулевыми. Это значит, что продолжать ветвление будем по той же ветви, так как среди концевых вершин оценка 83 наименьшая. Это ветвление представлено на рис. 3.18.

Маршрут замкнулся: 1 — 6 — 4 — 3 — 5 — 2 — 1. Стоимость оптимального маршрута составила 83


ух.


Проверить стоимость маршрута можно по начальной матрице стоимостей (см. табл. 3.2):


^1-6-4-з-5-2-1 = 12 + 25 + 9 + 11 + 4 + 22 = 83 у.е.


Рассмотренный пример — пример ветвления с возвращением с одной ветви графа на другую, что достаточно редко встречается при решении экономических задач на практике. Как правило, оптимальный маршрут формируется по правой ветви дерева.


Вопросы для самопроверки


1.    К каким методам относят метод ветвей и границ? В чем заключается основная идея этих методов?


2.    Опишите условия и цель «задачи о коммивояжере». Какова математическая модель задачи?


3.    Опишите общую схему и алгоритм метода ветвей и границ, применимый к решению «задачи о коммивояжере».


4.    Какова цель приведения матрицы? Каков смысл константы приведения матрицы? Каков смысл оценки 0,-,?


5.    Может ли в задаче о коммивояжере существовать альтернативный оптимальный маршрут? Что может указывать на наличие альтернативного маршрута?

4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ


Классические методы нахождения экстремумов функций многих переменных в задачах дискретной оптимизации часто оказываются неприменимы из-за большого числа параметров, от которых зависит решение. Одним из наиболее популярных методов решения таких задач является метод динамического программирования. Лежащий в его основе принцип оптимальности впервые был сформулирован Р. Беллманом. Суть принципа такова: какова бы ни была предыстория управляемого процесса, приведшего систему в рассматриваемое состояние, последующие решения по отношению к этому состоянию должны быть оптимальными. Иными словами этот принцип можно сформулировать так: отрезок оптимального процесса от любой его точки до конца процесса сам является оптимальным процессом с началом в данной точке.

Скачать в pdf «Экстремальные модели менеджмента и экономики»