8. Пример выполнения расчетной части проекта

8.5. Пример решения задачи
оптимизации прокладки дороги

Пусть имеется план местности, изображенной на рис. 8.10.

Рис. 8.10. Карта местности

Планируется проложить дорогу от центральной усадьбы до нового выпаса. Для упрощения задачи принимаем, что прокладка дороги может производиться только в направлениях Ю – С и З – В (юг-север и запад-восток). При более точных направлениях прокладки дороги (юг – сев.-зап., зап. – сев.-вост. и пр.) суть задачи не меняется, только резко увеличивается ее размерность.

Известна стоимость прокладки дороги между каждыми соседними участками, что отражено в примере на рис. 8.11 над горизонтальными и справа от вертикальных линий. Эта стоимость определяется рельефом местности.

Рис. 8.11. Пример исходных данных задачи оптимизации прокладки дороги

В конечное состояние система может перейти с запада из состояния 23 или с юга из состояния 18. Для этого потребуется 11 или 14 у.е. соответственно. Ставим эти числа над кружками на рис. 8.12. В конечное состояние система может перейти с запада из состояния 22 через состояние 23 (для этого потребуется 11+10=21 у.е. стоимости) или с юга из состояния 12 (для этого потребуется 12+14=26 у.е. стоимости). Ставим 21 и 26 над соответствующими кружками.

Рис. 8.12. Пример решения задачи оптимизации прокладки дороги

В конечное состояние система может перейти и из состояния 17. Причем здесь появляется два альтернативных варианта: или через состояние 23 (на север), или через 18 (на запад). В первом случае суммарные затраты составят 26 у.е., а во втором – 31 у.е. Над кружком 17 ставим наименьшее из полученных чисел и стрелку направляем в состояние 23, обеспечивающее минимум затрат на прокладку пути на этом этапе.

Из состояния 16 в конечный пункт можно попасть через 22 и 23. Для этого потребуется 21+4=25 у.е. Но из пункта 16 можно двигаться и через 17 и 23 (по стрелкам). В этом случае понадобится 26+10=36 у.е. Над кружком 16 ставим наименьшее из чисел.

В дальнейшем процесс решения разворачивается аналогично.

Результатом решения оказывается оптимальная траектория прокладки дороги, обеспечивающая минимум затрат: С–В–С–В–В–С–В–В. При этом минимально возможные суммарные затраты на прокладку пути составят – 77 у.е.