Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 50
Текст из файла (страница 50)
12.7, как необходима некоторая неиуловая площадь, чтобы изогпуть полосу можду отрозками рьв» и р»р,. Пусть эта верхняя граница равна й». Обычно площадь неприводимой самопересекающейся иолосъс боиьшо площади поприводи»юй полосы, по пересекающей себя, ио общий вес иорвой полосы при этом ие обязательно болыпе веса последи»и. Для некоторых весовых функций, иапримор и» (х, у) =- сопз», г-раздели»ощая полоса с мииималыигм весом должна пе быть самопоресекающейся.
Возникаот задача: найти, при каких ограничениях па весовую фуики»по г-разделяющая полоса с ми1иы1альиым весом до:1жиа но иметь сал»опересоче»сий. Пусть ()1 и ()2 — площади двух областей, имеющих пепустое пересечение. Обозначим чероз и» (()») н и» (С)2) общио веса этих ()2 областои. ) ели из условия — '- -')1 следует, что си ((),) ( си ф») 1 2 1 Г | |е. потони в нкпеге! |вней сенди то полоса с мшптмальным васам не будет иметь са>н>пересечений.
Д>тя того чтобы втаполнялось неравенство и> (~1!) ( и> ф!), пеобходих|о потребовать, чтобы и> (х, у) ) с, где с — некоторая положительная константа. В противном случае можно положить и> (х, у) — О в точках ()т, и> (х., у) ~ О и точках тт„т! тогда нарушится норавонство ю (()х) ( и> О)!).
Далое, необходимо потребовать, чтобы общий вес каждой нз областей был ограничен снерху (длн того, чтобы и> ((),) но было бы равно бесконочностн). Для того чтобы >.-разделан>щая полоса с минимальным весом не имела самонересоченнй, достаточно, чтобы весовая функция и> (х, у) удовлетворяла с;|едующим ограпнчонням: 1) функция и> (х, у) ) с, где р> Р с — поло;кительная константа; и 2) функция и> (х, у) удовлетворяет условию 2Ьшшитта с констактой К; 3) константа К должна удовлетворять условию К ( —, гдо с — положительная константа, фкгурирутощая в ограничении 1, а г — ншрина рассматриваемой полосы с минимальным весом. (Заметим, что при г->- О константа К может быть как угодно большой.) Па рис.
12.8 более детально изображена часть самопересекаюр и с. 12.8. щеися полосы, иа этом же рисунке изображена часть несамопересокающейся полосы. Область т)! зап|трнхоаана в одну сторону, а область ()> — в другук>. 11ижняя граница для ю Щ>*) достигается, если положить ш (х, у) — с на всох точках (),". Верхштно грант!ну для и> ((),;) мо>кно т|олучить, если весовой функции тс (х, у) присвоить максимальные значения во всех точках ж — 'е;и е,*). !1оиятие г-разде>мпощей полосы можно обобщить на случай, когда разде:мнотся пе дпе точки, а два множества точек.
Так, в $ 12.1 рассматривалась задача раздоления а прямоугольной области двух сторон Я н Т. Она эквивалентна задаче г-разделения в плоскости >ттм поскольку можно положить ю (.с, у) — О во всех точках Л, за пределами примоуго.иной области. (так подсказь|вает интуиция, г-разделяющни множеством в трехмерном пространстве Пз будет неттоторая поверхность тотщнны г, что приводит к задаче (!!тато. 12л.
~-глздкляюврхк хгпожкство 283 Задача!1лато заключается н нахождении поверхности наименьшей площади, ограпичсипой заданной замкнутой кривой 1Кордапа Г. С этой задачей связана другая: найти поверхность наимепьиией площади, граница (или часть границы) которой зараисо точно по опрсдолеиа, а ложит в заданпой трехмерной трубке. Можно определить весовую функции~ ю в каждой точке пространства и тогда рассматривать еще одну задачу: найти поверхность, обладакицун) минимальпыч весом и ограииченпу1о заданной замкпутой кривой Жордапа Г.
13десь под весом поверхпосги понимается интеграл от функции и~ по этой иоверхпости.) Рассмотрим, иапрпмор, задачу нахождения поверхности, обладающей минимальным весом и свободной границей. 11усть Р— поверхность, топологически эквивалентная сфере. Открытую область внутри Р обоэ~ачии буквой Ры Л О Р обозначим буквой й. На поверхности Р выделим две подповорхпости: 1', и Г,.
Определим весовую функцию па К; за пределами 1Твесовую функцию считаем равной иу:по. Будем искать поверхность с мвпимальным весом, разделяющую Г,, и Го Если Р— 1', — Г„ость некоторая кривая Г, а весовая функция является константой па Л, то задача нахождения разделяющей поверхности минимального веса превращается в задачу Плато. В соответствии с нашим сетевым подходом для решения задачи пространство Йэ можпо аппроксимировать коиечпой сетью. найти поверхность с мипимальиым весом товщкиы г, а затем г паде устремить к нулю.
ГЛАВА |З ЦИКЛИЧЕСКИЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ 13Л. Введение (Гомори [79)) Рассмотрим следук>щук> задачу линейного программирования: максимваировать ХО ПОО О0121 ОО>Х2 .. >10 при условии хи>! = о||+1. 0 ооО>, 11! и ы, зх2 ог ~1, Охл ХОМО = ОО ' |О. 0 ОО МО, !Х1 О~1>0,222 ° ° ° ПО*0|, ~Х~ х>>0 (у — -1, ..., и, >с ' 1, ..., и , 'и>). Заметим, что хеь„..., хг„— слабые переменные, а х„... ..., хп — исходные персмеппыс задачи (1). Если наряду с ограничопиями (1) потребовать, чтобы все х> (1 =- 1,..., >и) были целыми, то задача будек называться задачей >(елочиеленного программирования. Существует болыпоо количество аадач, особенно комбипатороых, которые можно сформулировать как задачи целочислоппого программирования (см. (34), (6) и з 15.3).
Ограничения (1) определяют выпуклу>о область Одк>!Ук) в и-мерном пространстве, как показано иа рис. 13.1. Узлы целочислш|пой решетки па рис. 13.1 изображены точкамп. Такие точки, росио>|ожеппые внутри области ОАЗИС>), являются допустимыми решениями задачи целочисленного программирования. Оптима,тьиые решения задачи линейного программирования всегда располагаются па границе области решений. Б данном случае граничные точки ие явля|отся даже допустимыми решениями, поскольку пи одна из пих пе цслочпслеипа. Предположим, что область допустимых ре|пепий сужена до выпуклой оболочки допусти>п»х целых точек внутри допустимой области.!(а рис.
13.1 зта выпуклая оболочка показана затененной областьв> ОЕ>г6>!". Эту затеиеппу|о область мо>кш> рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опроделя>ошей допустиму|о область ОЛ»С2), добавить ограничение 13л.
Ввкдвник 285 типа ВВ', как показано на рис. 13.1, то вновь полученная задача будот иметь ОЕ1гИ1 в качестве области допустимых решений. Такая вновь полученная область обладает двумя кажными свойствами: во-первых, опа содержит все допустимыс целочисленные точки исходной задачи линойпого программирования (поскольку она является выпуклой оболочкой этях точек), во-вторых, все крайние точки новой области — цслочнслсппы. Поэтозеу любое базисное оптимальное решение модифицированной задачи линейного програмлирвванил имеет своими компонентами целые числа н является оптимальным решением исходной задачи уело- ху численного п рог ралеми рова нин.
Именно алгоритмы целочисленного программирова- ° ° ° ° ° ння, которью будут описаны нпжс, реализуют методы систематического введения до- д полпнтельных ограничений с ° ° целью сведения исходной допустимой области к выпуклой оболочке ое допустимых целочисленных точек. Бак только это будет сделана, можно решать моди- н л' фнцировапную задачу линей- 0 Е А е ного программирования любым обычным методом, и Р и с. 15.1.
полученное базисное оптимальное репюпио автоматически будет целочисленным. Представленный виже целочисленный алгоритм обладает следующими свойствами: 1) все дояолнительпыс ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конечное число шагов создается достаточное количество дополнительных ограничений для того, чтобы оптимальное решение модифицированной задачи было целочисленным; 3) дополнительные ограничения (гипсрплоскости) проходят по крайней море через одну целочисленную точку, хотя и не обязательно паходищуюся внутри выпуклой оболочки; 4) каждое новое ограничение сокращает область допустимых решений исходной задачи целочисленного программирования.
Следует подчеркнуть, что оптимальное решение исходной задачи можот быть получено пре.кде, чем допустимая область сократится до размеров выпуклой оболочки. 11 тому же, поскольку оптимальное целочисленное решение опредолястся пересечением и гнперплоскостей, таких гиперплоскостей существует не более, чем это необходимо; некоторые из пих могут быть ограничениями исходной задачи. гл. <э. цикличвскип л:>гоеитм 286 Таблица Уб.У вЂ” х! хп= хл+! хл<л< = Обычно в ограничения задачи (1) включаются в тривиальныо соотношения ху =- — ( — ху) (у =-1, ..., и), а задача в матричной форме принимает внд х =- А( — х„), (2) где х — вектор-столбец с компонентамн хю х,,..., .тл, хл.!.„...
..., хлэ, А — соответствующая матрица размера (и + т + + 1) >< (и + 1) и ( — х,) — вектор с кохшонентами (1, — х„ — х„..., — хл), представляющими собой нобазисныо переменныо исходнои таблицы. Задачу целочисленного программирования также можно записать в виде табл. 13.1. Причины представления переменных в виде ( — х,), ( — хз),... ..., ( — хл) — чисто исторические, но это стало обычной практикои в целочисленном программировании.
Будем использовать ау (у = (), 1,..., и) для обозначения у-го столбца текущей таблицы и аы (! = О, 1,..., и + т; у .=- О, 1,..., и) для обозначения элемента >-и строки и у-го столбца таблицы. Предполагается, что все а<; в исходной таблице целые. Следовательпо, все слабые переменные хлэ„..., хле должны быть так>не неотрицательными целымп числами. При изложении алгоритма для решения цолочислснпых задач будем следовать работе Гомори !79).
Вначале задача цеж>численного программирования рассматривается как линейная программа и алгоритм решает ео с помощью прямого или двойственного симплекс->петела. В конце работы алгоритма а<л ) О (< =- 1,... ..., и -Р т) я а„у ) О (у —. 1,..., и). (Для получения исходного двойственного допустимого ре<пепия введем дополнительное ограниченно хл.> !., — — у>У вЂ” х! — хз —...
— х„) О, где М вЂ” достаточно болыпая константа, и проделаем одну итораци<о с этой строкой и лексикографическн минимальным столбцом в качестве ведущего.) Кслп а>о ) О и целыс для всех <, то получено опти- ы.>. ввкдкник 2В7 мальков решение целочисленной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
