Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 59
Текст из файла (страница 59)
Условие (9) представляет собой линейное ограничение, которое должно выполняться при любом допустимом решении исходной задачи. Если аоо ~ 0 в условии (9), то можно рассматривать (9) как производящую строку и получить из пее отсечение Гомори, как зто делалось в $13.1. Если использовать отсечение Гомори как ведущую строку и произвести итерацию (линейное преобразование иебазисных переменных), то после подстановки в (7) и (8) новых иебазисных переменных получим новые ограничения и целевую функцию. Соответственно будет получена новая линейная часть в (9), которая рассматриваотся как производящая строка, если аоо в пей отрицательно. В дальнейшем будет показано, что этот процесс является копечным.
Геометрически гиперплоскость аоо — л о (х) = 0 представляет собой касательную плоскость к поверхности, определяемой ограничением (8). Этот факт оформлен в виде следующой леммы. Лемма 16.1. Гиперплоскость Т = (х ) аоо — То (х) = О) является касательной плоскостною к поверхности, образованной ограничениями (8). Она однозначно определяется как касательная плоскость, параллелън я поляре к поверхо(ости ограничения, проходящей через начало коордш(ат.
Докьзлтвльство. Поскольку условие (9) является следствием условия (8), все точки, удовлетворяющие (8), располояоены по одну сторону от гиперплоскости Т. Гиперплоскость Т является касательной к поверхности (8), так как пересечение Т и нульпрострапства Л квадратичной части из (8) непусто, т. е. Т () ТФ 8 (Ь=(х(Ь1(х)=0, ..., 7,ь(х).=0)). Тот факт, что Т П Т 4= 8, .следует из линейной независимости линейных форм л о (х),..., То (х).
В то же время не существует другой касательной плоскости, параллельной Т. В противном случае существовала бы плоскость аоо — Ьо (х) .—. у, для которой выполнялось бы условие аоо — Го (х) ( у при всех значениях х, удовлетворяющих условию (8). Последнее замечание противоречит тому, что (х (а,о —.Оо(х) (у) располоокено по одну сторону от Т, а выпуклый пемерпыи параболоид — по другую.
Поскольку Т представляет собой касательную плоскость к поверхности, определяемой условием (8), отсечение Гомори, полученное из Т, 334 ГЛ. 1О. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ отсечет некоторую часть выпуклой области (8), не содерн1ащую ни одной целочисленной точки. Для доказательства конечности допустим, что все коэффициенты в (7) и (8) целочисленны, и существует нижняя граница для допустимого решения задачи (7), (8). Будет проще обсуждать алгоритм и доказательство конечности, если обратиться к определенной таблице. Такая таблица анализируется в следующем параграфе. 16.2. Таблица Так же как и в полностью целочисленном алгоритме Гомори, предположим, что начальная таблица является двойственно допустимой, и каждое ограничение выражено через небазисные переменные, взятые со знаком минус.
В первые п строк под целевой функцией запишем соотношения х1 = — ( — х1) ~ )О. Эти строки назовем справочными строками. (Если некоторые с1 ( О, то следует ввести избыточное ограничение, как ато делалось в 3 14.1, для того чтобы начальная таблица стала двойственно допустимой.) Ограничения вида (8) записываются под справочными строками. Параболическое ограничение аоо — (ао1х, + ... + ао„х„) — Ь1 (а„х„ + ... + а, х„)1 — ... ... — Ьо (ао1 + ... + аоихи)' Ъ О записывается как показано в табл. 16.1. Таблица 1б.1 1 -л1, -хо, ..., — ла 1е.з. ПРРОВРАЗОВАние Каждое параболическое ограничение занимает й + 1 строк, обведенные в таблице двойными линиями.
Линейное ограничение записывается колодным же образом в одной строке. Точнее говоря, необходимо иметь еще одни индекс при коаффициентах в параболическом ограничении, так как таких ограничений может быть несколько. Например, максимивировать з = — Зх~ — х„ при условиях — 3 +бх1 2хв хе)~Π— 16 + 5х, + 5х, — (х~ — х,)') О, х„хе ) О (целые).
Эта задача записана в табл. 16.2. Таблица 1б.2 т -а) — ае авочные строки жняя строка предназначена отсечения Гомори, которое ет выписано позже Если все элементы нулевого столбца (столбца констант) неотрицательны, то таблица является прямо допустимой. Поскольку мы начинаем с двойственно допустимой таблицы и сохраняем двойственную допустимость всех последовательных таблиц, оптимальное решение получено, как только таблица становится прямо допустимой, 16.3. Преобразование Рассмотрим невырождснное линейное преобразование вида х, =х„ х, = ро — р~х~ — рзхз —...
+ х, —... — р„х„, хе — т» 336 г:!. во. Пивов!Ислк!и!Ое пеогелммиеовлпнг Применив зто преобразование к линейной форме аоо — аых!— — а,охо —... — аоих„, получим аоо — аовх, —... — а,„т„—... — ао,х„ где аоо = аоо -'- Роао аоу =- ао!'+ Руао (для у Ф г), (2) аов — аог. а,у=-а.у — 'а Ру (для уча г) а,„= а.„.
Или, переписав более подробно, получим — Ь,(а„х, '-... в-а,„хо-~ роа.,) =- — Ь,(анх,+ о --... —;а„,х„)' — 2Ь роа,„(а„,х, +... — 'а„х„) — Ь,(роа,„)'. (4) Уравнение (4) выражает результат преобразования (1), произведенного над одной строкой, т. е. — Ь, (Х,„(л))о. Для того чтобы выразить параболическое ограничение типа (8) в з 16.1 через новые переменные ху, воспользуемся таблицей 16.3, где а,',=аоо — ~в Ь (роа,„)', в=- ! а,'! — — аоу — 2 ~ Ь.роав„а„; (у =1, ..., и), (6) в=! а;у =аы (в, у=.1, ..., п). Таблица 1б.б Заметим, что если р; и аоу (у = О, 1, ..., и) — целые, то аоу (у=О, 1, ..., и) — тоже целые. Квадратичная форма — Ь,(а,„х,-',-...:-а,„х„)о после преобразования (1) перейдет в — Ь,(а„х, Р ...
+а,„х -'. Роав.)' где 16А. АЛГОРИТМ Заметим, что аы, задаваемые соотношениями (2) и (3), получаются в том случае, когда все строки рассматриваются как линейные ограничения. Уравнения (5) восстанавливают таблицу в стандартном виде параболических ограничений типа (8) $ 16.1. 16.4. Алгоритм Алгоритм состоит из следующих шагов. Ш а г О. Начать с двойственпо допустимой таблицы, подобной табл. 16.1. Каждое параболическое ограничение ранга й эапимает к + 1 строк, а а;о (! = 1,..., Й) равны пулю.
Такая таблица паэывается таблицей стандартного вида. Ш а г 1. Если пе существует пи одного отрицательного элемента в нулевом столбце, то текущее реп1епие, получаемое посредством приравннвания нулю всех пебааислых переменных, является оптимальным. В противном случае выбрать в нулевом столбце первый неотрицательный элемент н испольэовать строку, в которой он стоит, в качестве проиэводящей (пропзводящеи строкой может стать только линейная часть аао — Ьо (х) )~ 0 или линейное ограничение, потому что в квадратичных частях все аю = 0). Ш а г 2.
Пусть аэ, — амх, —... — а„.г, —... — а,„т„есть производящая строка. Поскольку все условия в таблице выран<оны череэ ( — л;), имеем Выбрать среди аы 0 элемент, стоящий в лексикографически минимальном столбце, н этот столбец а„сделать ведущим. Пусть /11 р! — Иаиболыпее целое число, для которого ( — 1 а~ ) а,. Н/ Определим Х=-шах(:"'~) (аэг(0). РГ Заметим, что )А>- — -1, н ведущий элемент всегда равен — 1. П!аг 3. !!олучим отсечение Гомори: г=-~ — „'~~ — ~ — А~ ~~ —... +х„—... — ~+ ) х„.-эО.
Это отсечение записать внизу таблицы в виде 22 т. ху ззэ Гл. ьь целочислвнпов пРОГРАммиРОВАнив Ш а г 4. Использовать отсечение Гоморн в качестве ведущей строки, а ведущим элементом ваять ( — 1), после чего преобраэовать все строки так, как если бы это были линейные ограничения. Для параболического ограничения получим где аш (1 = 1,..., Ь) не могут быть нулями. Ш а г 5. Восстановить таблицу в стандартном виде, используя соотношения (5) иэ э 16.3, Вернуться к шагу 1.
16.5.. Примеры Решим два числовых примера, прежде чем дать доказательство конечности. Рассмотрим эадачу максимизировать э. = — Зх~ — х, при условиях — 3 — ( — бх, + 2х,) — х,* ) (), — 16 — ( — 5х, — бхэ) — (х, — х,)э ) О, хо хэ 0 (целые). Запишем задачу в табл. 16.4 (» — и 7 обоэначают производящую строку и ведущий столбец соответственно). После преобразования получается табл. 16:5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
