Цель работы: построение самой дешевой из всех возможных сетей дорог, соединяющих города Дано: а) вершина графа

		Экономика
		Решение задачи
		18 февраля 2021
		Выполнен, номер заказа №17177
		Прошла проверку преподавателем МГУ
		245 руб.

Цель работы: построение самой дешевой из всех возможных сетей дорог, соединяющих города Дано: а) вершина графа (города) i=1,2,…7 б) стоимость Sij тыс. руб.(i,j=1,2,…7) строительства дорог между городами (вершинами графа), которые определяются формулами: Sij=a{7b-|i-j|}|i-j| где а=15, b=3

РЕШЕНИЕ

Определим стоимость каждой дороги  тыс. руб. 570 тыс. руб. и т.д. Сформируем по исходным данным стоимость строительства дорог

1. Выбираем два города (две вершины) с наименьшей стоимостью (1,2), S12=300 тыс. руб.

2. Среди дорог, ведущих к городам 1 и 2 выбираем кратчайшую – это дорога, соединяющая города 2 и 3, S23=300 тыс. руб. На данном этапе в сеть соединены города (1,2,3), стоимость сети дорог S123=300+300=600 тыс. руб.

3. Среди дорог, ведущих к городам 1,2,3 выбираем кратчайшую – это дорога, соединяющая города 3 и 4, S34=300 тыс. руб. На данном этапе в сеть соединены города (1,2,3,4) , стоимость сети дорог S1234=600+300=900 тыс. руб.

4. Среди дорог, ведущих к городам 1,2,3,4 выбираем кратчайшую – это дорога, соединяющая города 4 и 5, S45=300 тыс. руб. На данном этапе в сеть соединены города (1,2,3,4,5) , стоимость сети дорог S12345=900+300=1200 тыс. руб.

5. Среди дорог, ведущих к городам 1,2,3,4,5 выбираем кратчайшую – это дорога, соединяющая города 5 и 6, S56=300 тыс. руб. На данном этапе в сеть соединены города (1,2,3,4,5,6) , стоимость сети дорог S123456=1200+300=1500 тыс. руб.

6. Среди дорог, ведущих к городам 1,2,3,4,5,6 выбираем кратчайшую до города 7 – это дорога, соединяющая города 6 и 7, S67=300 тыс. руб. Все города соединены, сеть построена, стоимость сети дорог S1234567=1500+300=1800 тыс. руб. Последовательность поиска минимальной сети представлена в таблице 5