3.5. Задача о проектировании дороги

Условие задачи. Пункт Б (город, завод, порт, электростан­ция и т. п.) расположен на 30 км севернее и на 40 км восточнее пункта А. Между этими пунктами требуется проложить дорогу так, чтобы стоимость ее строительства была минимальной.

Стоимость строительства дороги зависит от ряда факторов: ре­льефа местности и характера грунта, удаленности места строительства от карьера, асфальтового завода и т. п. Для расчета стоимости стро­ительства были проведены специальные исследования на местности, в результате которых на карте на север и на восток от пункта А была построена условная сетка шагом 10 км, и была оценена стоимость строительства 1 км дороги между каждыми двумя смежными узлами сетки. Полученные данные приведены на рис. 3.10. Например, в со­ответствии с приведенными данными стоимость строительства 1 км дороги от точки, находящейся в 10 км восточнее и 20 км севернее пункта А, составляет в северном направлении 23, а в восточном — 16 усл. ден. ед.

Для некоторого упрощения задачи и сокращения объема вычисле­ний будем считать, что от каждого узла сетки направление строитель­ства дороги может быть выбрано только по горизонтали и по вертикали, что соответствует на местности направлениям сторон света (север, юг, восток, запад). Будем также предполагать, что дорога не может прохо­дить севернее или восточнее пункта Б и южнее или западнее пункта А. Иными словами, дорога на карте должна располагаться в прямоуголь­нике, для которого точки А и Б являются соответственно левой ниж­ней и правой верхней вершинами. Такого типа ограничения могут быть обусловлены прохождением административно-территориальных границ, расположением закрытых военных полигонов, наличием рек, озер, морей и других препятствующих строительству объектов.

Решение. Данная задача является примером общей задачи о крат­чайшем пути, в которой роль длины пути играет стоимость строитель­ства соответствующего участка дороги. Представленная на рис. 3.10

км                                                                       Б

30 • -38- • -34- • -29- • - 23 - •

І                           І             І             І                   I

29                         23           31           15              24

І І І І | 20 • -24- • -16- • -17- .-19- •

І                           І             І             І                   I

26    18            4             7            22

І      І             І             І             I

10 • -15- • -41- • - 5 - • -32- •

І                           І             І             І                   I

19                         27           25           14              12

І                           І             І             І                   I

• -11 - • -42- • -13 - • - 1 - • А          10          20      30      40 км

Восток —> Рис. 3.10

схема является взвешенным графом специального вида. Каждая вер­шина графа однозначно определяется парой координат, равных числу шагов от начальной вершины, соответствующей пункту А, на восток и на север к рассматриваемой вершине. Один шаг по схеме соответ­ствует отрезку в 10 км на местности. Например, вершины, соответ­ствующие пунктам А и Б, имеют координаты (0;0) и (4;3) (далее будем коротко говорить «вершина (0;0)» и т. д.).

Решим задачу методом ДП, проводя запись на самом графе. В соот­ветствии с этим определим функцию Ь(у) как длину кратчайшего пути от вершины у до конечной вершины Б. Выполним детально первые шаги алгоритма.

—               Полагаем Ь(Б) = £(4; 3) = 0, записываем 0 на место вершины (4;3) (см. рис. 3.11) и объявляем данную вершину занятой, а все осталь­ные — свободными.

—               Поскольку начальная вершина (0;0) не является занятой, то при­ступаем к расчету оценок незанятых вершин. Для занятой вер­шины (4;3) с уже известным значением функции Ь(у) смежными

 

Рис. 3.11

и незанятыми являются вершины (3;3) и (4;2), причем обе они являются свободными, т. е. ни для одной из них оценки еще не рас­считаны. Для вершины (3;3) имеется лишь одно ребро, идущее в восточном направлении и инцидентное вершине (4;3). Стоимость строительства всего участка дороги между этими смежными вер­шинами равна произведению стоимости строительства 1 км до­роги (23 усл. ден. ед.) на длину участка (10 км). По надлежащей формуле вычисляем оценку

Е(3; 3) = 23 • 10 + 1,(4; 3) = 230 + 0 = 230.

Ставим стрелку, идущую от (3;3) к (4;3). Аналогично, для вер­шины (4;2) получаем:

£7(4; 2) = 24 • 10 + Ц4; 3) = 240 + 0 = 240.

—               Из двух найденных оценок значение 230 является минимальным; соответствующую вершину (3;3) объявляем занятой, полагаем

Ь(3; 3) = Е(3; 3) = 230

и записываем это число на место вершины (3;3). (Проводя анало­гию с классическим методом ДП, можно сказать, что для вер­шины (3;3) восточное направление представляет собой значение условно-оптимального управления.) Таким образом, значение функ­ции Ь(у) вычислено уже для двух вершин.

—               Начальная вершина (0;0) не стала занятой, поэтому продолжаем рас­чет оценок. Занятыми являются вершины (3;3) и (4;3), а смежными с ними —вершины (2;3), (3;2) и (4;2), причем первые две —свобод­ные, а третья — пробная. Вычисляем оценки свободных вершин:

£7(2; 3) = 29 • 10 + L(3; 3) = 290 + 230 = 520, Е(3; 2) = 15 • 10 + L(3; 3) = 150 + 230 = 380.

Ставим стрелки, идущие от этих вершин к (3;3). Для вершины (4;2) имеющаяся оценка 240 не нуждается в корректировке, поскольку с момента ее вычисления не появилось новых занятых вершин, смежных с (4;2). Из трех имеющихся оценок значение 240 является минимальным; соответствующую вершину (4;2) объявляем занятой, полагаем L(4; 2) = Е(4; 2) = 240 и записываем это число на место вершины (4;2).

Начальная вершина (0;0) еще не стала занятой, поэтому расчет оце­нок продолжается. Занятыми являются вершины (3;3), (4;2) и (4;3), а смежными с ними и незанятыми — вершины (2;3), (3;2) и (4;1), при­чем первые две пробные, а третья — свободная. Вычисляем оценку свободной вершины:

£7(4; 1) = 22 • 10 + L(4; 2) = 220 + 240 = 460,

и ставим стрелку, идущую от (4;1) к (4;2). Рассмотрим пробные вершины (2;3) и (3;3). Для вершины (2;3) имеющаяся оценка 520 не нуждается в корректировке, поскольку с момента ее вычисле­ния не появилось новых занятых вершин, смежных с (2;3). Для вершины (3;2) имеющаяся оценка 380 должна быть откорректиро­вана, поскольку с момента ее вычисления появилась новая смежная с (3;2) занятая вершина (4;2). Проводим корректировку, полагая Ё{3; 2) = £7(3; 2) = 380:

£7(3; 2) = min {£"(3; 2), 19 • 10 + L(4; 2)} = min {380,430} = 380.

Значение оценки при корректировке не изменилось, так что установ­ленная ранее стрелка у вершины (3;2) остается на прежнем месте. Из трех имеющихся -оценок значение 380 является минимальным; соответствующую вершину (3;2) объявляем занятой, полагаем

L(3; 2) = £7(3; 2) = 380

и записываем это число на место вершины (3;2). Начальная вершина (0;0) по-прежнему осталась незанятой, поэтому расчеты продолжаем далее. Действуя по алгоритму, мы последова­тельно вычислим значения функции L(v) во всех вершинах графа, кроме вершины (0;3), на месте которой оставлена точка. Для этой вершины оценка имеет значение 1230, что больше значения 1220 для начальной вершины А = (0; 0) (вершина (0;3) «не. успела» стать

занятой — конечная вершина А стала занятой раньше). Расчет значе­ния Ь(А) означает завершение этапа условной оптимизации реше­ния задачи. Результаты расчетов полностью приведены на рис. 3.11.

Приступаем к этапу безусловной оптимизации, на котором и стро­ится искомый кратчайший путь. Как видно из расчетов, оптимальное значение задачи, равное минимальной стоимости строительства дороги, составляет

Ь(А) = 1,(0; 0) = 1220 усл. ден. ед.

Конфигурация дороги минимальной стоимости строится начиная с пункта А с учетом стрелок, расставленных в ходе расчетов. При этом получается следующая цепочка вершин:

(0; 0) (0; 1)- (1; 1)- (1; 2)- (2; 2)- (2; 1)- (3; 1)- (3; 2)- (3; 3)- (4; 3).

На этом решение задачи завершено. В формулировке ответа полу­ченному результату надлежит дать содержательную трактовку в тер­минах решаемой задачи.

Ответ: минимальная стоимость строительства дороги из пункта А в пункт Б равна 1220 усл. ден. ед. Дорога минимальной стои­мости должна состоять из прямолинейных отрезков, последова­тельно соединяющих на местности точки с координатами (0;0) (пункт А), (0;10), (10;10), (10;20), (20;20), (20;10), (30;10), (30;20), (30;30), (40;30) км (пункт Б).

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

Замечание 1. Задачи, подобные рассмотренной, могут возникать и в несколько ином контексте, например, при проектировании железно­дорожных линий, линий электропередачи, газо-, нефте-, водопроводов и других коммуникаций.

Замечание 2. Проанализируем полученное оптимальное решение. Прежде всего отметим, что из вершины (3;0) выходят две стрелки; это означает, что из данной вершины имеется два различных кратчайших пути в конечную вершину Б:

(3; 0) — (4; 0) — (4; 1) - (4; 2) - (4; 3),

(3; 0) — (3; 1) — (3; 2) — (3; 3) — (4; 3)

стоимостью 590 усл. ден. ед. Если бы строящийся от вершины А крат­чайший путь прошел через вершину (3;0), то существовало бы два различных оптимальных решения задачи. Но кратчайший путь про­шел мимо данной вершины, так что неоднозначности оптимального решения в данной задаче не возникло.Замечание 3. Рассмотрим некоторые числовые характеристики полученного оптимального решения. Спроектированная дорога содер­жит участок (2; 2) — (2; 1), имеющий «обратное» направление по отно­шению к общему направлению строительства от А к Б. Вследствие этого общая длина дороги составила 90 км вместо возможных 70 км при проектировании без допущения обратных направлений. Однако стоимость строительства этих более коротких дорог является более высокой (за счет неравномерности распределения стоимостей стро­ительства отдельных участков), что подтверждает известный факт: короткая дорога не всегда является самой оптимальной.

Подчеркнем, что в спроектированной дороге минимальная стои­мость строительства отрезка в 1 км равна 4 усл. ден. ед., а средняя стоимость равна

1220 : 90 и 13, 56 усл. ден. ед.,

в то время как в исходных данных задачи имеются участки стоимостью 1, 11, 12 и 13 усл. ден. ед., не вошедшие в проект. Тем самым еще раз подтверждается, что метод ДП оптимизирует не отдельные участки, а всю траекторию в целом.

Далее, средняя по всем ребрам графа стоимость строительства 1 км дороги составляет около 21,16 усл. ден. ед. (это нетрудно установить прямым подсчетом); поэтому оценка средней стоимости дороги длиной 70 км, проложенной без предварительной оптимизации, составит

21,16 • 70 = 1481,2 усл. ден. ед.,

что более чем на 20% превышает полученную минимальную стои­мость дороги длиной 90 км. (Конечно, при построении всевозможных путей ребра, инцидентные вершинам А и Б, встречаются чаще, чем ребра «внутри графа»; соответственно при строгом-вычислении сред­него значения стоимости дороги эти ребра необходимо учитывать с большим весом. Точный расчет здесь достаточно сложен и не обязате­лен, а приведенное значение 1481,2 является допустимым именно как оценка среднего значения.)

Замечание 4. Естественным и логичным обобщением рассматри­ваемой задачи является допущение строительства дороги не только в направлении сторон света, но и в северо-восточном направлении. Будем считать, что стоимость строительства 1 км дороги на северо- восток равна полусумме стоимостей 1 км на север и на восток в том же месте. Например, в соответствии с приведенными выше данными стоимость строительства 1 км дороги от точки, находящейся в 10 км восточнее и 20 км севернее пункта А, в северо-восточном направлении составляет       .„ , „„

16 + 23 _1П _

—-— = 19,5 усл. ден. ед.

При этом отрезок дороги между двумя соседними расположенными по диагонали точками имеет длину у/2 • 10 км; будем считать его приближенно равным 14 км (поскольку у/2 и 1,4142). Отметим, что в новой постановке задачи множество допустимых вариантов строи­тельства шире, чем в исходной постановке; в силу этого новая ми­нимальная стоимость дороги должна получиться не выше значения 1220 усл. ден. ед., полученного для исходной задачи.

Задание. Провести решение рассматриваемой задачи в новой по­становке методом ДП.

Замечание 5. В более сложных ситуациях могут возникать и бо­лее замысловатые конфигурации дорог минимальной стоимости. На­пример, на рис. 3.12 показан минимальный путь из пункта А в пункт Б длиной 11. Длины ребер, отмеченных стрелками, равны 1, длины остальных ребер равны 8. На практике реализация такого типа опти­мальных решений приводит к дорожному «серпантину», часто встре­чающемуся в гористой местности.