На этом занятии мы построим сетевую модель реальной экономической задачи. Введем сначала некоторые определения.
Циклом называется путь в сети, у которого начальная и конечная вершины пути совпадают.
Цикл называется простым, если в цикле не повторяются вершины и ребра.
Весом цикла назовем сумму весов ребер, входящих в цикл.
Простой цикл в сети, содержащий все вершины сети, называется ГАМИЛЬТОНОВЫМ циклом.
Задача о построении гамильтонова цикла минимального веса для заданной сети называется задачей КОММИВОЯЖЕРА.
Решение задачи коммивояжера является трудной задачей так, как все известные алгоритмы решения имеют экспоненциальную оценку сложности, т.е. они имеют сложность порядка O(en). Такие задачи получили название NP-полных задач. Известные алгоритмы решения таких задач являются алгоритмами полного перебора всех вариантов и не являются эффективными.
Алгоритмы построения цикла минимального веса в сети подробно разбирался на лекции. На этом занятии мы используем процедуру, реализующую такой алгоритм, для решения задачи выбора маршрута зарубежного путешествия.
1. Постановка задачи, создание мат. модели задачи. (40 мин.)
1.1 Математическое моделирование задачи о выборе маршрута зарубежного путешествия.
Прочитайте внимательно следующую задачу и постройте для нее сетевую модель - сеть с именем Trv<Номер группы><Ваш порядковый номер> (Например, Trv20202).
Задача 1.
Студент 4-ого курса Саратовского университета после
успешной сдачи сессии решил попутешествовать по свету. Он решил посетить
несколько городов. Вооружившись справочниками по маршрутам воздушного
сообщения различных авиакомпаний, он занес в Таблицу 1 стоимости полета из
одного города в другой. Виза, которую получил студент не позволяет повторно
возвращаться в уже посещенный город. После составления этой таблицы, он понял,
что необходимо так выбрать маршрут своего
путешествия, чтобы сумма, потраченная на билеты была минимальной и, чтобы не
приходилось посещать один город два раза.
Предложите такой маршрут.
Таблица 1.