§ 12. Кратчайшие системы дорог

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

Как и в §11, будем считать все населенные пункты, дома, заводы и т. п. точками, а дороги, каналы и т. п. прямыми линиями. Старайтесь находить такие решения, которые требуют поменьше средств для их реализации.

Внутри водоема правильной круглой формы расположен маленький островок. Укажите кратчайший прямой маршрут катера, соединяющий какие-нибудь точки берега и имеющий промежуточный причал у островка.

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

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

В одном населенном пункте живет больше детей, чем в другом. В каком месте следует построить школу, чтобы общие затраты на перевозку детей были минимальны, если эти затраты пропорциональны как количеству детей, так и расстоянию от населенного пункта до школы?

Для снабжения водой двух населенных пунктов, расположенных по одну сторону от канала, требуется на берегу канала построить водонапорную башню. В каком месте следует построить башню, чтобы суммарная длина труб от нее до каждого из пунктов (по прямой) была наименьшей?

Магистраль и канал пересекаются под углом меньше 45°, внутри которого расположен населенный пункт. Как проложить кратчайшую дорогу, проходящую от одного пункта сначала к берегу канала, а затем к магистрали?

Два населенных пункта расположены по разные стороны от широкого канала. Требуется построить мост через канал (перпендикулярно берегам) и проложить к нему дороги от обоих пунктов. В каком месте следует построить мост, чтобы в итоге путь между данными пунктами оказался кратчайшим?

По одну сторону от железной дороги расположены два населенных пункта. В каком месте дороги следует построить платформу заданной длины, чтобы сумма расстояний от нее до данных пунктов была наименьшей?

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

Две магистрали пересекаются под углом, внутри которого протекает речка. Где построить мост через речку, чтобы сумма расстояний от него до обеих магистралей была наименьшей?

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

В каком направлении через город должна проходить магистраль, чтобы сумма расстояний от нее до двух данных населенных пунктов была наименьшей?

Как должна проходить магистраль, чтобы сумма расстояний от нее до трех данных населенных пунктов была наименьшей?

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

Каким должен быть кратчайший замкнутый маршрут автобуса, предназначенного для развозки жителей населенного пункта по всем трем заводам?

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

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

Три населенных пункта расположены в вершинах остроугольного треугольника. Где нужно построить завод, чтобы сумма расстояний от него до всех трех данных пунктов была наименьшей?

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

Решения

12.1. Кратчайший маршрут катера совпадет с хордой АВ, перпендикулярной радиусу ОС, проходящему через островок D (если островок находится в центре круга, то все маршруты будут иметь одинаковую длину; поэтому мы рассмотрим здесь случай, когда D не совпадает с О, изображенный на рис. 27). Для доказательства этого утверждения проведем через точку D еще какую-либо хорду EF и проверим, что EF>AB. Действительно, перпендикуляр OG к хорде EF имеет меньшую длину, чем наклонная OD к этой хорде. Следовательно, EG>AD (так как в прямоугольных треугольниках OEG и OBD одинаковые гипотенузы ОЕ = ОВ, но разные катеты OG<OD), а значит, EF = 2EG>2DB = AB, т. е. хорда АВ короче любой другой хорды, проходящей через точку!).

Рис. 27

12.2. Завод нужно построить в точке Е пересечения диагоналей четырехугольника ABCD с вершинами в данных населенных пунктах (рис. 28). Докажем, что сумма расстояний от всех четырех пунктов А, В, С, D до любой точки F больше, чем до точки Е. Действительно, складывая неравенства

получаем неравенство AC + BD≤AF + BF + CF + DF, в котором равенство возможно только в случае, когда точка F лежит на обеих диагоналях АС и BD, т. е. когда F совпадает с Е. Именно это и требовалось доказать.

Рис. 28

12.3. Киоск нужно установить в любой точке, по обе стороны от которой расположено одинаковое количество домов (рис. 29). Если общее число домов нечетно, а сами дома находятся, скажем, в точках А₁, А₂, ..., A_k, О, B_k, ..., В₂, B₁, то киоск нужно поставить у дома О. Если же общее число домов четно, а сами дома находятся в точках А₁, А₂, ..., A_k, B_k, ..., В₂, B₁, то киоск можно поставить в любой точке О между домами A_k и B_k. Действительно, общая сумма расстояний от киоска до всех домов складывается из расстояния от киоска до среднего дома О (если таковой имеется) и сумм расстояний от киоска до каждой пары домов A_i и B_i, где i = 1, ..., k. При этом любая из указанных сумм не превосходит соответственно величины A_iB_i а равна ей тогда и только тогда, когда киоск находится между домами A_i, B_i. Таким образом, необходимым и достаточным условием минимальности общей суммы является принадлежность точки установки киоска каждому из отрезков А₁В₁, A₂В₂, ..., A_kB_k и, кроме того, совпадение этой точки с точкой О среднего дома, если число домов нечетно.

Рис. 29

12.4. Школу следует построить в том из населенных пунктов А или В, в котором живет больше детей. Действительно, пусть для определенности таким пунктом является пункт А. Тогда если школа расположена в некоторой точке О, то затраты на перевозку детей пропорциональны величине

которая не может быть меньше, чем b*АВ, так как а>b, ОА≥0 и ОА + ОВ≥АВ. С другой стороны, указанная величина принимает как раз значение b*АВ, но только в единственном случае - когда точка О совпадает с точкой А.

12.5. Один из двух населенных пунктов А или В, например В, отразим симметрично относительно канала (точнее, относительно его ближайшего берега). Если мы соединим отрезком полученную точку С с точкой A, то точка D пересечения этого отрезка с каналом и будет искомой точкой расположения водонапорной башни (рис. 30). В самом деле, для любой другой точки Е на том же берегу канала суммарная длина труб до точек A и В будет равна суммарной длине труб до точек A и С (в силу симметрии относительно канала имеем равенства ЕВ = ЕС и DB = DC), которая в свою очередь будет превосходить величину АС = AD + DB, что и требовалось доказать.

Рис. 30

12.6. Отразив симметрично относительно канала данный населенный пункт А, мы получим точку В, из которой достаточно теперь опустить перпендикуляр ВС к магистрали, пересекающий канал в искомой точке D (рис. 31). Для доказательства того, что кратчайший маршрут от точки А к каналу, а затем к магистрали представляет собой ломаную ADC, заметим следующее: от любой другой точки Е канала сумма расстояний до точки A и до канала будет равна сумме расстояний до точки В и до канала, которая в свою очередь будет превосходить величину BC = AD + DC.

Рис. 31

12.7. Один из двух населенных пунктов A или В, например В, перенесем мысленно по направлению к каналу на расстояние, равное ширине канала (рис. 32). Полученную точку С соединим отрезком с точкой A, тогда точка D пересечения этого отрезка с берегом канала, ближайшим к точке A, как раз и даст один из концов моста DE. Докажем, что маршрут ADEB будет кратчайшим из всех возможных. Действительно, для любого другого расположения моста FG (точка F не совпадает с точкой D, но лежит на том же берегу) имеем

т. е. другой маршрут получается только длиннее.

Рис. 32

12.8. Если проекции населенных пунктов A и B на линию железной дороги удалены друг от друга менее, чем на длину платформы, то саму платформу достаточно разместить так, чтобы обе проекции оказались на ней (сумма расстояний до платформы не может быть меньше, чем сумма расстояний до железной дороги, и этот минимум как раз реализуется в данном случае).

Если же указанные проекции удалены друг от друга более, чем на длину платформы, то сама платформа должна располагаться между этими проекциями (в противном случае ее можно передвинуть так, чтобы сумма расстояний от нее до пунктов А я В была еще меньше). Перенесем точку В на длину платформы вдоль железной дороги в сторону сближения с точкой А (рис. 33). Для полученной точки С выберем на железной дороге точку D, для которой сумма AD+CD минимальна (см. задачу 12.5). Эта точка D и будет представлять собой ближайший к точке А край платформы. Докажем, что расположение платформы DE удовлетворяет условию задачи. Действительно, для любого другого расположения FG (край F считаем ближайшим к А) платформы имеем

что и требовалось доказать.

Рис. 33

12.9. Любой (не обязательно кратчайший) маршрут разобьем на три участка: от первого населенного пункта А к точке В одной магистрали, от точки В до точки С другой магистрали и от точки С до населенного пункта D (рис. 34).

Рис. 34

Участок АВ отразим симметрично относительно первой магистрали, а участок CD - относительно второй. Тогда получим соответственно участки ЕВ и CF, причем расположение точек Е и F не зависит от самих участков, поскольку они просто симметричны точкам А и D. Итак, любой маршрут ABCD превращается в равный ему по длине маршрут EBCF с фиксированными началом Е и концом F. Следовательно, кратчайший среди маршрутов получается тогда, когда EBCF есть отрезок прямой. Этим условием точки В и С определяются однозначно: достаточно отразить симметрично точки А и D, получив точки Е и F, а затем найти точки пересечения прямой EF с магистралями. По точкам В и С, конечно, определяется и весь маршрут ABCD.

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

Рис. 35

Такими группами точек будут являться отрезки АВ прямых, перпендикулярных биссектрисе угла (рис. 35). Действительно, любую точку С отрезка АВ можно соединить с вершиной О угла, образованного магистралями, и разбить тем самым равнобедренный треугольник ОАВ на два треугольника О АС и ОВС. Тогда если х и y - расстояния от точки С до сторон О А и Об, то площадь треугольника АО В будет равна сумме площадей треугольников О АС и ОВС, т. е. величине

не зависящей от выбора точки С на отрезке АВ. Поэтому сумма x + y также не зависит от выбора этой точки, причем из соображений подобия следует, что указанная сумма будет тем меньше, чем ближе отрезок АВ расположен к вершине О. Последняя близость полностью определяется расстоянием от точки О до проекции D точки С на биссектрису угла АОВ.

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

12.11. Завод нужно построить в той из точек A, В или С пересечения магистралей, которая лежит против наибольшей стороны треугольника ABC (рис. 36). Если наибольших сторон две, то завод можно построить в любой точке меньшей стороны, а если треугольник равносторонний, то в любой точке треугольника. Действительно, считая для определенности справедливыми неравенства

и обозначая расстояния от точки D до сторон АВ, ВС и АС через х, y и z соответственно, получаем, что площадь S треугольника ABC равна сумме площадей треугольников ADB, BDC и ADC:

Рис. 36

Поэтому справедливо неравенство

в котором равенство имеет место

В соответствии с этими случаями получаем расположение точки D либо в точке С, либо на стороне АС, либо в любой точке треугольника ABC.

12.12. Магистраль должна проходить через тот из двух населенных пунктов А или В, который более удален от города С. Если же точки A и В равноудалены от точки С, то магистраль можно проводить через любую из них. Для доказательства предположим, что АС≥ВС, и рассмотрим точку D, симметричную точке В относительно точки С (рис. 37). Обозначим через х расстояние от магистрали до точки A, через y до точки В (оно же из соображений симметрии - расстояние до точки D). Магистраль пересекает либо отрезок А В в некоторой точке Е, либо отрезок AD в некоторой точке F. В первом случае площадь S треугольника ABC равна сумме площадей треугольников АЕС и ВЕС:

а во втором - площади треугольника ACD, которая равна сумме площадей треугольников AFC и DFC:

Рис. 37

Поэтому величина х + y будет тем меньше, чем больше длина отрезка СЕ пли CF соответственно, которая принимает наибольшее значение при E = F = A, если AC>BC = DC, а также еще и при Е = В (или, что то же, при F = D), если АС = BC = DC. Мы воспользовались тем фактом, что если точка Е лежит между точками A и B, то в одном из треугольников АЕС или ВЕС угол при вершине Е не является острым и против него лежит сторона АС или несоответственно, большая стороны ЕС. Аналогично, если точка F лежит между точками A и D, то сторона FC меньше хотя бы одной из сторон АС или DC. Итак, мы доказали полностью утверждение, сформулированное в начале решения.

12.13. Заметим, во-первых, что искомая магистраль должна проходить хотя бы через один из данных населенных пунктов A, B или С. Действительно, если она не проходит ни через один из этих пунктов, то ее можно параллельно перенести так, чтобы она проходила через один из пунктов, а сумма расстояний от нее до этих пунктов стала бы меньше (если все три пункта лежат по одну сторону от магистрали, то ее можно пропустить через ближайший из этих трех пунктов, а если только два пункта лежат по одну сторону от магистрали, то ее можно пропустить через ближайший из этих двух пунктов).

Во-вторых, искомая магистраль должна проходить хотя бы через два из пунктов A, В или С. Действительно, если она проходит только через один пункт, то, согласно решению задачи 12.12, ее можно повернуть вокруг этого пункта так, чтобы она прошла еще через один пункт, а сумма расстояний от нее до этих пунктов стала бы меньше.

В-третьих, из всех положений магистрали, при которых она проходит хотя бы через два пункта, наименьшая сумма расстояний, разная расстоянию до магистрали от третьего пункта, достигается тогда, когда магистраль проходит через две наиболее удаленные друг от друга точки A, В или С. В самом деле, указанное расстояние до магистрали должно быть равно наименьшей высоте треугольника ABC, которая опущена, разумеется, на наибольшую сторону. Заметим, что случай, когда точки A, В или С лежат на одной прямой, также укладывается в описанную схему, а случай равенства каких-либо сторон треугольника ABC его наибольшей стороне дает возможность проводить магистраль по любой из этих сторон.

12.14. Пусть заводы расположены в вершинах треугольника ABC, а населенный пункт - в центре О вписанной в треугольник окружности. Пусть, кроме того, стороны треугольника имеют длины а = АВ, b = АС, c = ВС и касаются окружности в точках D, Е, F соответственно (рис. 38). Обозначим x = ОС, y = OВ, z = OA и докажем, что если a>b, то a + x>b + y. Действительно, из равенств отрезков касательных имеем

и, отразив точку С симметрично относительно точки F, получаем из неравенства треугольника OBG

Рис. 38

Положим для определенности, что a>b>c, тогда

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

а все остальные маршруты получаются из перечисленных заменой направления движения на противоположное. Длины этих маршрутов равны соответственно

где принято обозначение l = a + b + c + x + y + z. Поэтому наименьшую длину будет иметь последний из перечисленных маршрутов, т. е. маршрут, не проходящий по наибольшей стороне треугольника ABC.

12.15. Заметим прежде всего, что все прямые дороги, соединяющие две данные магистрали, можно разбить на группы дорог, образующих замкнутые маршруты одинаковой длины. Такими группами будут являться группы дорог, касающихся какой-то общей окружности, вписанной в угол между магистралями (дороги должны касаться той части окружности, которая обращена к точке D пересечения магистралей; рис. 39). Действительно, любая дорога АВ, касающаяся данной окружности в токе С, будет образовывать маршрут, длина которого не зависит от точки С, так как равна сумме длин касательных DE и DF к окружности, проведенных из точки L:

Рис. 39

Последняя сумма будет тем меньше, чем ближе центр окружности расположен к точке D.

Таким образом, для проведения искомой дороги достаточно выбрать ближайшую к точке D вписанную в данный угол окружность, которая еще допускает проведение к ней касательной из данной точки С. Такая окружность просто проходит через точку С, а строится она способом, примененным нами ранее при решении задачи 11.8 (проведем какую-нибудь вписанную окружность и найдем соответствующую точку С' ее пересечения с прямой DC, тогда в силу подобия искомый отрезок АВ будет параллелен касательной, проведенной к проведенной окружности в точке С).

12.16. Пусть магистрали образуют остроугольный треугольник ABC, а на сторонах АВ, АС и ВС автобус имеет выезды в точках D, Е и F (рис. 40). Построим точки G и Н, симметричные точке D относительно сторон АС и ВС соответственно. Тогда длина ломаной DFED равна длине прямой GEFH и является наименьшей (при фиксированной точке D, а с ней и фиксированных точках G и Н), если точки Е и F лежат на прямой GH. Наконец, для нахождения точки D, при которой отрезок GH имеет наименьшую длину, заметим, что угол GCH вдвое больше фиксированного угла АСВ, так как

Рис. 40

Поэтому основание GH равнобедренного (GC = HC) треугольника GCH имеет наименьшую длину, когда его боковая сторона GC минимальна. А эта ситуация в свою очередь реализуется, когда точка G, лежащая на отрезке, симметричном отрезку А В относительно прямой АС, является основанием перпендикуляра CG к этому отрезку, т. е. когда CD - тоже перпендикуляр к стороне АВ. Итак, доказано, что точка D выезда автобуса к магистрали АВ должна быть основанием высоты треугольника ABC. Аналогично доказывается, что и другие точки Е и F также должны быть основаниями высот этого треугольника.

12.17. Пусть населенные пункты обозначены через А, В, С, а искомая точка расположения завода - через D. Повернем треугольник ACD на угол 60° вокруг точки А в направлении полуплоскости, не содержащей точку В (рис.41). Получим треугольник AEF, удовлетворяющий равенствам

так как треугольники ACD и AEF равны, а треугольник FD является равносторонним (AF = AD и ∠DAF = 60°).

Рис. 41

Сумма расстояний от точки D до точек A, В и С равна длине ломаной BDFE и, следовательно, не может оказаться меньше отрезка BE. Поэтому наименьшее значение указанной суммы будет равно длине отрезка BE, но при условии, что точку D можно подобрать так, чтобы и сама эта точка, и точка F, полученная в результате поворота, оказались лежащими на отрезке BE. Для построения такой точки достаточно провести перпендикуляр АН к отрезку BE и отложить от него угол HAD величиной 30° в направлении точки В (рис. 42). Докажите самостоятельно, что каждый из углов ADB, BDC и ADC, под которыми видны стороны треугольника ABC из искомой точки D, равен 120°.

Рис. 42

12.18. Под углом к магистрали, косинус которого равен ¹/_k, проведем луч из города А в той полуплоскости, которая не содержит населенного пункта В (рис. 43). Тогда для любой точки С магистрали, ст которой предполагается отвести проселочную дорогу СВ, имеем, что время движения транспорта по участку СА магистрали будет равно времени движения по проселочной дороге CD, перпендикулярной проведенному ранее лучу (скорости на участках ВС и CD считаем равными). Следовательно, общее время движения по ломаной ВСА пропорционально длине ломаной BCD. Так как кратчайшая такая ломаная совпадает с перпендикуляром к лучу, опущенным из точки В, то на этом перпендикуляре как раз и лежит искомая точка магистрали. Заметим, что точка В, возможно, и не проектируется на луч AD (а проектируется на его продолжение), тогда проселочную дорогу следует отвести прямо от города А.

Рис. 43