|
|
|
|
|
Основы теории принятия решениий Учебное пособие. Москва, 2002. 9.Теория графов и оптимизация Задача коммивояжера. Требуется посетить все вершины графа и вернуться в исходную вершину, минимизировав затраты на проезд (или минимизировав время). Исходные данные здесь - это граф, дугам которого приписаны положительные числа - затраты на проезд или время, необходимое для продвижения из одной вершины в другую. В общем случае граф является ориентированным, и каждые две вершины соединяют две дуги - туда и обратно. Действительно, если пункт А расположен на горе, а пункт Б - в низине, то время на проезд из А в Б, очевидно, меньше времени на обратный проезд из Б в А. Многие постановки экономического содержания сводятся к задаче коммивояжера. Например: составить наиболее выгодный маршрут обхода наладчика в цехе (контролера, охранника, милиционера), отвечающего за должное функционирование заданного множества объектов (каждый из этих объектов моделируется вершиной графа); составить наиболее выгодный маршрут доставки деталей рабочим или хлеба с хлебозавода по заданному числу булочных и других торговых точек (парковка у хлебозавода).
|
||