Определение кратчайших расстояний между пунктами транспортной сети

 

Практическая  работа 1.

Определение кратчайших расстояний между пунктами транспортной сети.

 

Цель выполнения данной практической работы состоит  в следующем:

• Найти кратчайшие расстояния между пунктами транспортной сети и заполнить ими соответствующую таблицу;
• Найти кратчайшие пути проезда между пунктами и отразить их на соответствующем рисунке.

 

Исходными данными для  выполнения данной практической работы является транспортная сеть из индивидуального  задания (рис.1)

 

 

Рисунок 1 – Транспортная сеть.

 

 

 

 Для выполнения практической работы воспользуемся методом потенциалов. Сущность его состоит в следующем. Потенциал одной из вершин (назовем ее исходной, например, вершины А) принимаем за 0, то есть РА = 0. Далее по формуле(1) определяются потенциалы всех вершин, непосредственно связанных с ней:

                                         

                                                 (1)

где i,j – текущие индексы  соответственно исходной и непосредственно  связанной с ней вершин;

      Рi – потенциал исходной вершины, км;

      Рj – потенциал вершины, непосредственно связанной с исходной, км;

      ℓij – длина звена между исходной и непосредственно связанной с ней вершинами, км.

 Из всех рассчитанных таким образом потенциалов выбираем наименьший, его значение записываем в таблицу 1 кратчайших расстояний, а соответствующее звено на рисунке 2 отмечается стрелкой. Далее вершина с наименьшим потенциалом принимается за исходную, от неё вновь определяются потенциалы всех вершин, непосредственно связанных с ней. Просматриваются все известные к этому моменту потенциалы (определенные как на предыдущем, так и на данном этапе), из них вновь выбирается наименьший, его значение заносится в эту же таблицу, а соответствующее звено на рисунке отмечается стрелкой. Таким образом, расчеты повторяются до полного заполнения таблицы 1 и рисунка 2.

  Рассмотрим метод потенциалов на примере рис. 1.

Примем РА = 0.

С вершиной А непосредственно связанны вершины Г, В, Б,Н. Их потенциалы:

Р_Г= Р_А+ ℓ_АГ= 0 + 7 =7км

Р_В= Р_А+ ℓ_АВ= 0 + 6 = 6км

Р_Б = Р_А+ ℓ_АБ= 0 + 2 =2км

Р_Н= Р_А+ ℓ_АН= 0 + 8 =8км

 

 Отсюда в строке А и столбце Б таб.1 проставляем минимальное расстояние 2, а звено АГ на рис.2 отмечаем стрелкой. Вершину Б принимаем за исходную.

С вершиной Б непосредственно связаны Н, В.

Р_Н= Р_Б+ ℓ_БН= 2 +3=5км

Р_В= Р_Б+ ℓ_БВ= 2 + 4 = 6км

 

 Из известных (Р_Н=8, Р_Н=5, Р_В=6), минимальное расстояние Р_Н=5, заносим в строку А и столбец Н таб.1, а звено БН на рис.2 отмечаем стрелкой. Вершину Н принимаем за исходную. С ней непосредственно связаны М, Л, Г. Расстояние до А (Р_Н=8) уже известно ее из расчета выпускаем.

Р_М= Р_Н+ ℓ_НМ= 5+ 7=12км

Р_Л = Р_Н+ ℓ_НЛ= 5 + 4 =9км

Р_Г = Р_Н+ ℓ_НГ= 5 + 10=15км

 

  Выбираем минимальное  значение Р_Л = 9 и отмечаем звено НЛ стрелкой. Вершину Л принимаем за исходную , с ней связаны вершины М, К, Г.

Р_М = Р_Л+ ℓ_ЛМ= 9 + 9 =18км

Р_К = Р_Л+ ℓ_ЛК = 9 + 3 =12км

Р_Г = Р_Л+ ℓ_ЛГ = 9 + 7 =16км

 

  Минимальное значение  Р_К= 12 , отрезок ЛК отмечаем стрелкой, расстояние АК заносим в таблицу.

  Потенциалы вершины  М:

Р_М = Р_Н+ ℓ_НМ= 12км

Р_М= Р_Л+ ℓ_МЛ= 18км

Р_М = Р_К+ ℓ_КМ= 14 + 6 =20км

 

  Минимальное значение  Р_М= 12, отрезок НМ отмечаем стрелкой и расстояние заносим в таблицу.

  Потенциалы вершин  Г и В нам известны, отмечаем  отрезки АГ и АВ стрелками,  проставляем расстояния в таблицу, принимаем эти вершины за исходные.

  С вершиной Г  связаны вершины И, Ж, Д. Вершины Н и Л в расчёт не берём, так как расстояния до них известны.

Р_И = Р_Г+ ℓ_ГИ = 7 + 9 =16км

Р_Ж = Р_Г+ ℓ_ГЖ = 7 + 4 =11км

Р_Д = Р_Г+ ℓ_ГД  = 7 + 8 =15км

 

  Минимальное  значение  Р_Ж =11. Отрезок ГЖ отмечаем стрелкой, а данные заносим в таблицу. Вершину Ж принимаем за исходную.

  С вершиной Ж  связаны вершины З, И, Е, Д.

Р_З= 11 + 5 =16км

Р_И= 11 + 6 = 17км

Р_Е = 11 + 9 =20км

Р_Д= 11 + 10 =21км

 

  Минимальное  значение  Р_З =16.

Р_И(ГИ) =16км

Р_И(ЖИ) =11+6=17км

Р_И(ЗИ) =16+3=19км

Р_И(КИ) =14+12=26км

 

  Минимальное значение  Р_И(ГИ) =16. Отмечаем этот отрезок и заносим значение в таблицу.

  С вершиной В  (Р_В =6) связаны вершины Е и Д.

Р_Е =  6 + 3 =9км

Р_Д=  6 + 5 =11км

 

  Так как эти  значения минимальны для этих вершин, заносим в таблице в строку А и столбцы Е и Д соответствующие значения, а отрезки отмечаем стрелками.

  Таким образом,  выбирая на каждом этапе минимальный  потенциал, можно с абсолютной  уверенностью гарантировать определение  кратчайших расстояний и путей проезда от вершины А до всех остальных вершин данной транспортной сети. Расчеты повторяются до тех пор, пока все клетки в строке А таб.1 не будут заполнены расстояниями. При этом на рис.2 у каждой вершины должна быть обозначена хотя бы одна стрелка ( кроме вершины А, поскольку это исходная вершина с потенциалом Р_А=0).

  Далее потенциал  следующей вершины (например, Б)  принимаем за 0 и все расчеты  повторяются аналогично.

 Следует обратить  внимание на то, что на данной  транспортной сети нет никаких ограничений по организации дорожного движения, то есть расстояние,  скажем, между пунктами А и И равно расстоянию между пунктами И и А. Таким образом, матрица кратчайших расстояний будет симметрична относительно диагонали и можно заполнять только одну ее часть.

 

 

 

Рисунок 2 – Кратчайшие пути проезда от вершины А.

 

 

Таблица 1 – Матрица кратчайших расстояний между пунктами транспортной сети.

	А	Б	В	Г	Д	Е	Ж	З	И	К	Л	М	Н
А		2	6	7	11	9	11	16	16	12	9	12	5
Б	2		4	9	9	7	13	21	18	10	7	10	3
В	6	4		13	5	3	12	20	21	23	18	21	7
Г	7	9	13		8	12	4	9	9	12	7	16	10
Д	11	9	5	8		4	10	15	16	20	15	24	18
Е	9	7	3	12	4		9	14	15	24	19	28	17
Ж	11	13	12	4	10	9		5	6	14	11	20	14
З	16	21	20	9	15	14	5		3	9	14	15	16
И	16	18	21	9	16	15	6	3		12	16	18	19
К	12	10	23	12	20	24	14	9	12		3	6	9
Л	9	7	18	7	15	19	11	14	16	3		9	4
М	12	10	21	16	24	28	20	15	18	6	9		7
Н	5	3	7	10	18	17	14	16	19	9	4	7

 

 

 

Вывод:

• Нашли кратчайшие расстояния между пунктами транспортной сети и заполнили ими соответствующую таблицу;
• Нашли кратчайшие пути проезда между пунктами и отразили их на соответствующем рисунке.

Практическая  работа 2

Закрепление потребителей однородного груза за поставщиками

 

 Цель работы заключается  в построении такого плана  перевозок щебня, который обеспечивал бы минимальное значение транспортной работы (грузооборот).

 Задача закрепления  потребителя однородного груза  за поставщиками заключается  в построении такого плана  перевозок, который обеспечит  минимальное значение критерия  оптимальности, которым в данном случае будет грузооборот. Исходные данные для данной практической работы представлены на рис.1, в таб.1 и таб.2 Задания. Их необходимо свести в таб.2.

Расстояние между поставщиками и потребителями проставляют  в правом верхнем углу каждой клетки (из таблицы 1 в практической работе 1)

 

Таблица 2. Исходные данные для решения задачи оптимизации закрепления потребителя за поставщиками.

Поставщики		Потребители					Объём производства, т.
		В	И	Л	Ж	З
		VВ= 2	VИ= 16	VЛ= 0	VЖ= 9	VЗ= 14
А	UА= 0	*        6	16   140	9	11	16	140
Б	UБ= 2	**       4   180	18   30	7	13	21	210
Г	UГ= -5	13	*        9   0	7	**       4   100	*         9   0	100
Н	UН= 4	7	19	**       4   120	14	16   80	200
Объём потребления, т.		180	170	120	100	80	650

 

 Задача оптимизации  закрепления потребителей однородного  груза за поставщиками может  быть решена методом МОДИ. Сущность  его состоит в следующем. Вначале строится какой-либо план перевозок, который по специальным правилам проверяется на оптимальность. Если он не оптимален, то строится новый улучшенный план. Таким образом, за конечное число шагов может быть получен искомый оптимальный план.

 Первоначальный (опорный) план  целесообразно получить методом  «двойного предпочтения». Для этого по каждой строке и по каждому столбцу отмечается  знаком * клетка с минимальным расстоянием. В таблице 2 клетки БВ, ГЖ, НЛ имеют одновременно два знака **. Их загружают в  первую очередь. Далее проставляем загрузку в клетки, имеющие одну         

отметку. Оставшуюся загрузку распределяем по свободным клеткам. Таким образом, в полученном опорном плане от всех поставщиков имеющийся груз вывезен, всем потребителям завезено все, что им требуется. При этом опорный план должен удовлетворять два условия:

1. Ацикличность, то есть в таблице нельзя построить замкнутый цикл, все вершины которого лежат в загруженных клетках.
2. Число загруженных клеток должно быть равно:

                m + n – 1,

           где  m – число поставщиков;

                  n – число потребителей.

 Опорный план, представленный в таблице 2, второму условию не удовлетворяет, значит подставляем нулевые загрузки в клетки ГИ и ГЗ.

Подсчитаем для опорного плана значения грузооборота по формуле (3)

                   

 

                                                                            (3)

где i, j – текущий индекс соответственно поставщика и потребителя;

       Р  – грузооборот, ткм;

       Q_ij – объем перевозок между i-ым поставщиком и j-ым потребителем, т;

        ℓ_ij – расстояние между i-ым поставщиком и j-ым потребителем, км.

Р=140×16+180×4+30×18+120×4+100×4+80×18=5820 ткм.

 Для проверки на оптимальность  по методу МОДИ определим вспомогательные величины u_i (для строк) и v_j (столбцов), называемые потенциалами. Для этого потенциал одного из поставщиков, в данном случае А примем равным нулю. Тогда оставшиеся потенциалы определим по формуле (4)

                                                       (4)

 Учитывая, что в  загруженных клетках d_ij =0, определим потенциал строк и столбцов для таблицы 2. В строке А одна загруженная клетка АИ.      Отсюда потенциал столбца И равен:

   u_A= 0;                    v_И= ℓ_АИ – u_A= 16 – 0 = 16

Далее по загруженной  клетки БИ определим потенциал строки Б,