Решение задачи определения оптимального маршрута доставки груза - Моделирование транспортных процессов

В качестве исходных данных берем граф:

исходный граф

Рис. 4 Исходный граф

Используя приложение "Microsoft Excel" вводим исходные данные, отражающие расстояние между пунктами сети. Данные представляем в виде таблицы.

Таблица 1

Исходные данные для расчета

№ вершины

1

2

3

4

5

6

7

8

9

10

1

0

3

0

7

0

0

0

0

9

7

2

3

0

0

0

0

4

0

0

0

0

3

0

4

0

0

0

0

3

0

0

0

4

7

0

4

0

0

0

0

2

0

0

5

0

0

0

0

0

5

0

0

2

0

6

0

4

0

0

5

0

0

0

0

3

7

0

0

3

0

0

0

0

4

5

0

8

0

0

0

2

0

0

4

0

0

0

9

9

0

0

0

2

0

5

0

0

4

10

7

0

0

0

0

3

0

0

4

0

Рассматриваем каждую вершину и определяем расстояние от начальной вершины до смежных с ней вершин. Результаты получаем в виде таблицы:

Таблица 2

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

-

7

-

-

-

-

9

7

№ предшеств. Вершины

-

1

-

1

-

-

-

-

1

1

Далее рассматриваем все остальные вершины выбирая каждую последующую по кратчайшему расстоянию от начальной вершины. Результаты получаем в виде таблиц:

Таблица 3

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

-

7

-

4

-

-

9

7

№ предшеств. Вершины

-

1

-

1

-

2

-

-

1

1

Таблица 4

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

-

4

-

9

9

7

№ предшеств. Вершины

-

1

4

1

-

2

-

4

1

1

Таблица 5

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

-

4

-

9

9

7

№ предшеств. Вершины

-

1

4

1

-

2

-

4

1

1

Таблица 6

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

14

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

9

4

1

1

Таблица 7

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

14

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

9

4

1

1

Таблица 8

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

14

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

9

4

1

1

Таблица 9

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

13

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

8

4

1

1

Таблица 10

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

13

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

8

4

1

1

Таблица 11

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

13

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

8

4

1

1

Таблица 12

Итоговая таблица

№ вершины

1

2

3

4

5

6

7

8

9

10

Расстояние до нач. вершины

-

3

11

7

11

4

13

9

9

7

№ предшеств. Вершины

-

1

4

1

9

2

8

4

1

1

Используя данные итоговой таблицы, убираем лишние связи и получаем итоговый граф:

Рис. 5 Итоговый граф

Похожие статьи




Решение задачи определения оптимального маршрута доставки груза - Моделирование транспортных процессов

Предыдущая | Следующая