2015-03-07
468
Рассмотрим задачу: определить наикратчайший путь между вершиной 1 и вершиной 7 на графе, представленном на рис. 8.
Рис. 8. Исходные данные задачи
Для решения задачи в MathCad представим ее как транспортную задачу с промежуточными пунктами. Будем считать, что транспортные расходы при перевозке одной единицы груза равны (в условных единицах) расстояниям между вершинами. Одна единица груза отправляется из вершины 1 (исходный пункт) и должна прибыть в вершину 7 (пункт назначения). Вершины 2, 3, 4, 5, 6 рассматриваются как промежуточные пункты, которые являются одновременно и исходными пунктами и пунктами назначения.
Требуется определить такую последовательность вершин, по которым должна перемещаться единица груза, отправленная из вершины 1, при которой стоимость транспортных расходов будет минимальна и груз попадет в вершину 7.
