Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

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

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

потребляемого в точке (х, у). Существует две причины, по которым кривая с мини­

мальным значением | w (х, у) dc не соот­

ветствует оптимальному маршруту авто­ мобиля.

Во-первых, весовая функция w (х, у) может быть очень мала на самой опти­ мальной кривой, но очень велика вблизи нее. Поэтому если автомобиль хотя бы немного отклонится от предписанной

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

потребление топлива j j w (х, у) .dA минимально.

Во-вторых, автомобиль представляет собой не точку, а мате­ риальное тело. Поэтому его траекторией является не кривая, а некоторая полоса.

Таким образом, практический интерес представляет следую­ щая задача. Найти полосу заданной ширины е, заключенную

между сторонами А и В, такую, чтобы интеграл j ^ w (х, у) dA

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

Легко построить пример, когда оптимальная полоса заданной

ширины е с минимальным значением интеграла j ^ w (х, у) dA

полоса в. пределе будет стремиться к оптимальной кривой. Ниже мы рассмотрим процедуру, позволяющую найти оптимальную

полосу, ширины е, на которой j ^ w (х, у) dA является глобаль­

ным минимумом. При этом если е стремится к 0, то эта полоса приближается к оптимальной кривой как к пределу.

18 т. ху

По аналогии с сетями с конечным числом узлов прямоугольную область можно представить как сеть со стороной S в качестве источника и стороной Т в качестве стока. Весовую функцию w (х, у) можно при этом интерпретировать как функцию пропусной способности непрерывной среды в точке (х, у).

Любая кривая, идущая от Л к В, будет тогда соответствовать разрезу, а криволинейный интеграл — пропускной способности этого разреза. Если ввести понятие потока в непрерывной среде и найти минимальный разрез как в теореме о максимальном

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

пускной способностью, равной общему «весу»

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

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

из горизонтальных, вертикальных и наклонных под углом в 45° участков. А это нежелательно, так как нам нужно, чтобы гладкая полоса приближалась в пределе к гладкой оптимальной кривой, когда h стремится к нулю.

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

Р и cs 12.5.

минимального разреза целиком лежит на горизонтальной (или на вертикальной) линии, то вес этого множества узлов равен весу горизонтальной (или вертикальной) полосы ширины h (см. рис. 12.5 (а)). Но если множество узлов минимального разреза лежит целиком на линии с углом наклона 45°, то общий вес этого множества узлов не будет равен весу полосы ширины h с углом наклона 45° (см. рис. 12.5 (б)).

Чтобы преодолеть указанные трудности, рассмотрим другой способ построения аппроксимирующей сети. Прямоугольную

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

В построенлой r-связиой сети удаление всех узлов из некото­ рого горизонтального ряда не разобьет сеть на две части, так как в сети найдется пара узлов, лежащих по разные стороны от этого горизонтального ряда и связанных дугой. Чтобы прервать

поток из S в Т, нужно, например, удалить все узлы из j-^-Г гори­

зонтальных рядов, гдеJ — ближайшее слева к Y целое число.

Метод расстановки пометок для сети с пропускными способ­ ностями узлов позволяет найти множество узлов, образующих минимальный разрез. Если этот минимальный разрез удалить из сети, то сеть будет разбита на две части. (В силу минимальности разреза никакое его собственное подмножество не обладает этим свойством.)

Элементарные квадраты области находятся во взаимно одно­ значном соответствии с узлами сети, поэтому подобласть, являю­ щаяся объединением элементарных квадратов, соответствующих минимальному разрезу, должна иметь свойства, аналогичные свойствам минимального разреза. А именно, эта подобласть r-разбивает прямоугольную область на две части, причем удаление хотя бы одного элементарного квадрата из этой области нарушает это свойство. Здесь под r-разбиением области понимается сле­ дующее. Область считается г-разбипгой на две части, если не существует пары элементарных квадратов, лежащих в разных

ная между сторонами А и В области.

Так как г значительно больше, чем h, то квадратов, лежащих целиком внутри полосы ширины г, будет значительно больше, чем квадратов, лежащих лишь частично внутри нее. Квадраты, лежащие целиком внутри полосы, будем называть внутренними, а квадраты, лежащие лишь частично внутри полосы,— гранич­ ными. Если весовая функция обладает свойствами, сформулиро­ ванными ниже в § 12.4, то общий вес внутренних квадратов на порядок превышает общий вес граничных квадратов, и .при

12.4./--разделяющее множество

Вэтом параграфе обсуждаются некоторые свойства непрерыв­ ных минимальных разрезов (Гомори, Ху [92]). Заметим прежде всего, что мы ограничимся рассмотрением точек двумерной проек­ тивной плоскости R 2. Две точки а и Ъ из множества Р будем называть r-связанными, если существует конечная последователь­

в R 2 — С.

Более точно будем говорить, что множество С cz Л 2 является r-разделяющим точки а и Ъ, если

При таком определении любое достаточно большое множество будет r-разделяющим. Однако если потребовать, чтобы множество С было неприводимым, т. е. таким, что его собственные подмно­ жества уже не являются r-разделяющими, то множество С будет обладать вполне определенной структурой. В дальнейшем симво­ лом С мы будем обозначать неприводимое r-разделяющее множе­ ство. Заметим, что неприводимое r-разделяющее множество ана­ логично разрезу в непрерывной среде, а точки а и b аналогичны источнику и стоку.

Сформулируем несколько теорем, касающихся неприводимых r-разделяющих множеств. Доказательство их можно найти в рабо­ те Гомори и Ху [92]. Будем использовать следующие обозначения:

С — неприводимое r-разделяющее множество (оно замкнуто по определению);

А — множество точек, r-связанных с точкой а (это открытое множество);

В — множество точек, r-связанных с точкой b (это также откры­