Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 48
Текст из файла (страница 48)
Имеется прямоугольная область со сторонами А, Я, Я, Т (рис. 12.3). В этой области определена ограпичепеая непрерывная весовая функция н«(х, у) ) О. Надо найти криву«о, соединяющую стороны Л н В, такую, чтобы интеграл по этой кривой ~ и (х, у) г(с был бы минимальным. 1) Преимущества этого алгоритма не очевкдны, так как нрк «раздвоенна» узлов н дуг (см. примечание на стр. 268) число дуг становятся равным и + 2в«, но каждая дуга нросматрнваетсн только однн раз, а адесь может оказаться, что каждую дугу нонадобнтсн просмотреть 4 раза.— Прим.
перев. <".3. потоки В неппквы<тной сР<<«т< Вза задача может быть решопа обычпыни вариациопнымн методамп, осли весовая функция и (х, у) достаточно гладкая. Вак и во всох задачах варнацнонного исчисления, найденный нрн:<том минимум будот локальным и может не быть глобальным. рассматриваемая задача может нмоть следующу<о практическую нптернретацшо. 11еобходим<т найти самь<й депювый путь для автомоонля„движущегося от стороны Л к стор<ше В. Весовая функция ш (х, у) указывает количество топлива, потребляемого в точке (х, у).
Существует дш причипь<, по которым кривая с тшниъ<альным значенном ~ ш (х, у) <1с не соот- А <т ветствуот оптимальному марн<руту автомобиля. Во-первых, весовая функция ш (х, и) ьт< жег быть очеш мала на самой оптн- Т мальвой кривой, но очень велика вб;<изи нее. Поэтому если автомобиль хотя бы 1' и с. 12.3. незшого отклонится от продписапной оптимальной кривой, стоимость поездки резко возрастет. Так как авт<н<обнлем невозмо кно управлять со стопроцентной точностью, то ботюе разумно искать не криву<о, а полосу ширины е, в которой потребление топлива ~ ~ ит (х, у) <(А минимально.
Во-вторых, автомобиль продставляет собой пе точку, а матеряальпое тело. 11оэтому его траекторией является не кривая, а пекоторан полоса. Таким образом, практический ипторес продставляет следующая задача. Найти полосу заданной в<ирины е, заключенную между сторонами Л и В, таку<о, чтобы интеграл ~ ~ ш (х, у) <(Л по этой полосе был в<<<<<<<в<альп<<э<.
Бо«ее того, требуотся, чтобы этот двойной интеграл был глобальным минимумом но всем полосам пшрнпы в, закл<оченньп< можду сторопамн Л и В. 41< гко построить пример, когда оптимальная полоса заданной и<ирины е с мппнмалы<ым значением интеграла ~ ~ ш (х, у) <1Л не содержит оптимальной кривой с минимальным значением Г ) ш (х, р) <Кс. Однако если е устремить к путно, то оптима<иная полоса в пределе будет стремиться к о<ттимальной кривой. Ниже мы рассмот(<им процедуру, позволяющую найти оптимальную полосу ширины е, на которой ~ ~ ш (х, у) <(4 является глобальным минимумом, При этом если е строзштся к О, то эта полоса приближается к оптимальной кривой как к пределу. 18 т,хт 274 !'Л. 1З, ПОТОКИ В НВПРНРЫВНОЙ ОРВДН Заметим, что любая непрерывная кривая Г, идущая от стороны А к стороне В, разбивает нашу область на две части, одна из которых содержит сторону Я, а другая — сторону Т.
11рп этом любая кривая, идущая от Я к Т, пересекает криву!о Г. 11о аналогии с сетямн о конечным числом узлов прнмоугольную область можно представить как сеть со стороной Я в качество источника н стороной Т в качестве стока. Весовую функцию ш (х, у) шзжно при этом интерпретировать как функ!!н1о пропусной способности непрерывной среды в точке (х, у). Любая кривая, идущая от А к В, будет тогда соотвотствовать разрезу, а криволинейный интеграл — пропускной способности этого разреза. Если ввести поняпзе потока в непрерывной среде и найти минимальный разрез как в тооремо о максимальном потоке и минимальном разрезе, то этот минимальный разрез и будет искомой кривой, па которой ) 1Р (х, у) «с является глобальным минимумом.
Рассматриваехзый пнже подход основан на приближении непрерывной средьз конечной сетью. Конечная соть, приближа!ощая пашу прямоугольную область, состоит из узлов, каждый нз которых соответствует элементарному квадрату исходной области. Каждый узел обладает пропускной способностью, равной общему «весу» ~ ~ и (х, у) д 1 соответствующего эломентарного квадрата. В этой сети с ограниченными пропускными способностями узлов минимальным разрезом является некоторое множество узлов. й1пожество элементарных квадратов, соответствувзщих этим узлам, если рассматринаемое прибли«кение достаточно точное, по своой конфигурации доллан! походить па волосу ширины е.
Необходимо обратить ннимание па следующие три обстоятельства. Бо-первых, минимальный разрез в рассматриваемой приближазощей соти представляот собой некоторое множество узлов. Во-вторых, походная прямоугольная область разбивается на элементарные квадраты. Объодинепие элементарных квадратов, соотвотствующих узлам минимального разреза, является подобластью. В-третьих, эта подобласть !!Олнзпа по своей конфигурации приближаться к полосе Пи!РИНЫ Е. Узлы конечной сети и элементарные квадраты исходной области находятся во взаимно однозначном соответствии. В сети с ограпичонпьыш пропускными способностями узлов всегда сущоствует минимальный разрез н, следовательно, всегда мозкпо выделить множество элементарных квадратов, которые соответству1от узлам этого мнннма:1ьпого разреза.
Это множество элементарных квадратов в пределе до:!жнО п1щблнжаться к полосе ши1П1ны е, когда площадь квадратов стремится к нулю. 1З.З. ПОТОНИ В НКП!'ГРЫВНОЙ СРК.;<К Рассмотрим сначала наиболее простой и очевидный способ приближения непрерывной сроды и выясним, какие трудности при этом вознпп<ают. 1'азобьом прямоугольную область, изображонную на рнс. 12.3, на одинаковыо зломентарные квадраты со стороной 6. В центро каждого квадрата расположим узол с пропускной способностью, равной общему <свесу» этого квадрата. (Опреде<<енно сети с пропускными способностями узлов приведено Г в 4 12.2.) каждый узел соединим дугамн со всеми сосодннмн узламн, находя<цнмнсн от него на расстоянии Й.
Получается соть, изображенная на рнс. 12.4. Х 11вадратам, расположенным на грапнцо области и смежным со стороной Я, соответствук»т в х аппроксимирующей сети источники продукта с ограниченным А предло»кепнем. Величина продло- х х женка в ка»кдом источнике равна общому весу соответствующего элементарного квадрата. Аналогично квадратам, расположенным на границе области и сможным со стороной Т, соответствуют стоки с ограниченным спросом.
Оту сеть со многимн источниками и стоками Т можно преобразовать в сеть с одним источником и одним стоном, как это делалось в $ 8,3. Разрезом сети, изображенной на рис. 12.4, нвлнется множество узлов, удалонно которых вместе со вгоми инцидептными им дугами разобьет сеть на две части, од<и из которых содержит все источники, а другая — все стокк..»1нон<ество элементарных квадратов, соответствующих этому множеству узлов, по своей конфигурации должно быть подобно полосе с минимальным общим весом. 71<е<<ательно, чтобы при стремлении й к пулю зта полоса стромнлась бы к оптимальной кривой как к своому пределу.
Но, к сожаленнк1, сеть, построенная описанным простым способом, пе обладает указанп<ь<м свойством. Первая трудность, возпика<ощая прп нспользовапии построенной сети, заключается в том, что кривая, сое,'п<нн<ощая узлы минимального разреза, всегда состоит нз горнзоптальных и вертикальных отрезков н отрозков с углом наклона 415'. Одна нз таких кривых, помеченная буквой х, изображена на рис. 12.4. Следовательно, объединение элементарных квадратов, соответствующих 18» ГЛ, 12, ПОТОКИ В НВПРКРЫВНОЯ СРЕДЕ 276 узлам разреза, будет иродставлять собой полосу, состоящую ич горизонтальных, вертикальных и наклонных под углом в ь1 2 э участков.
А это нежелательно, так как нам нужно, чтобы гладкая полоса приближалась в пределе к гладкой онтнмалыюй кривой, когда Й стремитсн к нулю. Вторая трудность состоит в том, что в построенной сети общий вес множества узлов может оказаться не равным несу полосы, соответствующей этому мп1мкеству узлов. Если множество узлов Р и с, 12.51. минимального разреза целиком ло1кит на горизонтальной (нлн па вертикальной) линии, то вес этого хок1жества узлов равен васу горизонтальной (или вортикальпой) полосы ширины Й (см. рпс. 12.5 (а)). Но осли 1шожество узлов мннимальпого разреза ухо лежит целиком на линни с углом наклона йо, то общий вос этого мно кества узлов но будет равен весу полосы ширины й с углом наклона 45з (см.
рис. 12.5 (б)). Чтобы нреодолоть укаэанные трудности, рассмотрим другой способ построения аппроксимирующей сети. Прямоугольную область снова разобьем на одннаковыо эломентарные квадраты со стороной 11. В центре ка1кдого квадрата расноло1ким узел с пропускной способностью, равной общему весу:1того квадрата. Соединим теперь два узла дугой, если расстояние хи жду ними ие превышает г (г > Ь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
