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

Л емма 12.1. Пусть Pip2 и Ч\Чг — два отрезка, каждый из кото­ рых имеет длину, не большую чем г, и пусть р — точка их пере­

Л емма 12.3. Если существует г-связывающая цепь, то суще­ ствует и простая r-связывающая цепь.

Теорема 12.3. Если С — неприводимое r-разделяющее множе­ ство, то R 2 — С = А \] В (другими словами, множество D пусто).

Заметим, что теорема 12.3 очень похожа на известную теорему Жордана о замкнутой кривой, согласно которой всякая простая (не имеющая самопересечений) замкнутая кривая С разделяет точки плоскости В 2, не принадлежащие С, на такие два открытых

множества А и В, что любая пара точек в каждом из этих мно­ жеств может быть связана кривой, не пересекающейся с С. Соглас­ но теореме 12.3, всякое неприводимое г-разделяющее множество С г-разделяет плоскость В 2на такие_два открытых множества А и,В, что любая пара точек в каждом из этих множеств может быть г-связана йепыо, не имеющей общих точек с С.

Каждое из множеств А, В может состоять из нескольких односвязных открытых множеств, называемых компонентами мно­ жества А или В.

Т еорема 12.4. Каждая компонента множества А или В равно­ мерно локально связна, а граница каждой из компонент является простой кривой Жордана.

Таким образом, граница множества С является объединением простых кривых Жордана. Можно показать, что любое множество С состоит из частей следующих двух типов. Части 1-го типа — полосы ширины г (как полосы С4 и С2 на рис. 12.6). Части 2-го

типа — выпуклые многоугольники с четным числом сторон, длина каждой из которых равна г (как у многоугольника Р на рис. 12.6). Для наглядности можно представлять себе, что неприводимое множество С, частями которого является С), С2, Р, имеет вид самопересекагощейся полосы, а многоугольник Р — это как раз

280 ГЛ. 12. ПОТОКИ В НЕПРЕРЫВНОЙ СРЕДЕ

область самопересечения, добавление которой (один раз) к мно­ жествам Ci и С2 не нарушает свойства неприводимости множе­

ства С . Любое множество С является объединением множеств указанных двух типов.

Если весовая функция w (х, у) произвольна, то любое непри­ водимое r-разделяющее множество легко можно сделать разде­ ляющим множеством с минимальным весом, положив w (х, у) = г

• а

2

в этом неприводимом множестве, а за его пределами взяв w (х, у) достаточно большим.

Заметим; что на рис. 12.6 длйна отрезка р 2Рь меньше г. Поэтому области A i vi А 2 r-связаны с точкой а и А — A t [J А 2. Множество

точек В, r-связанных с точкой Ь, состоит из точек, заключенных внутри полосы. Полоса, изображенная на рис. 12.6, будет обла­ дать минимальным весом, если весовая функция достаточно велика в Л и Л, и мала внутри полосы. На рис. 12.7 изображено другое неприводимое множество, r-разделяющее точки' а и б.

на рис. 12.6 и 12.7, обладает минимальным весом? Это зависит от того, что меньше — вес полосы на рис. 1 2 .6 , заключенной меж­

ду отрезками pip4 и р 3р4, или вес области Pip4p 3p4 на рис. 12.7.

Обозначим через Q* площадь полосы, заключенной между отрез­

как необходима некоторая ненулевая площадь, чтобы изогнуть

полосу между отрезками /цр4 и р 3р4. Пусть эта верхняя граница

равна ki . Обычно площадь неприводимой самопересекающейся полосы больше площади неприводимой полосы, не пересекающей себя, но общий вес первой полосы при этом не обязательно больше веса последней.' Для некоторых весовых функций, например w (х , у) = const, r-разделяющая полоса с минимальным весом должна не быть самопересекающейся. Возникает задача: найти, при каких ограничениях на весовую функцию г-разделяющая полоса с минимальным весом должна не иметь самопересечений.

Пусть — площади двух областей, имеющих непустое пересечение. Обозначим через w (Qi) и w (Q2) общие веса этих

Задача П лато заключается в нахождении поверхности наимень­ шей площади, ограниченной заданной замкнутой кривой Жор­ дана Г. С этой задачей связана другая: найти поверхность наи­ меньшей площади, граница (или часть границы) которой заранее точно не определена, а лежит в заданной трехмерной трубке. Можно определить весовую функцию w в каждой точке простран­ ства и тогда рассматривать еще одну задачу: найти поверхность, обладающую минимальным весом и ограниченную заданной зам­ кнутой кривой Жордана Г. (Здесь под весом поверхности пони­ мается интеграл от функции w по этой поверхности.)

Рассмотрим, например, задачу нахождения поверхности, обла­ дающей минимальным весом и свободной границей. Пусть Р — поверхность, топологически эквивалентная сфере. Открытую область внутри Р обозначим буквой й, й (J Р обозначим буквой

R. На поверхности Р выделим две подповерхностп: Г8 и 1\. Опре­

делим весовую функцию на й; за пределами й весовую функцию считаем равной нулю. Будем искать поверхность с минимальным весом, разделяющую Г., и Г/. Если Р — Г8 — Г( есть некоторая

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

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

ГЛАВА 13

ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

13.1. Введение (Гомори [79])

Рассмотрим следующую задачу линейного программирования: максимизировать

ничениями (1 ) потребовать, чтобы все xj (j = 1 , . . ., т) были

целыми, то задача будет называться задачей целочисленного про­ граммирования. Существует большое количество задач, особенно комбинаторных, которые можно сформулировать как задачи цело­ численного программирования (см. [34], [6 ] и § 15.3).

Ограничения (1) определяют выпуклую область O A B C D в ге-мер-

ном пространстве, как показано на рис. 13.1. Узлы целочисленной решетки на рис. 13.1 изображены точками. Такие точки, рас­ положенные внутри области O A B C D , являются допустимыми

решениями задачи целочисленного программирования. Оптималь­ ные решения задачи линейного программирования всегда распола­ гаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна. Предположим, что область допу­ стимых решений сужена до. выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпук­ лая оболочка показана затененной областью O E F G II. Эту зате­

ненную область можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опре­ деляющей допустимую область O A B C D , добавить ограничение