Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 74
Текст из файла (страница 74)
Введение В гл. 19 мы рассматривали три задачи; первая из пих: максимизировать свхв + с»х» при условии Вхв + Гтх» .—. Ь, хв, х» ) 0 (целые). Выпуклая оболочка неотрицательных целочисленных точек, которые удовлетворяют ограничениям аадачи (1), обозначается через Р. Вторая задача: максимизировать свВ 'Ь вЂ” с»х» при условии х„+ В 'Хх;„.= В 'Ь, (2) х„) О, хв, х„(целые), где сЪ =.
б»В ''т) — с» ) О„а  — оптимальный базис задачи линейного программирования, соответствующеи задаче (1). Выпуклая оболочка неотрицательных целочисленных решений, которые удовлетворяют ограничениям задачи (2), обозначается через Р (В, т', Ъ). Третья задача: минимизировать Х с*(д) т(а) меч при условии Х г(а) а=-ае веч 1(д))0 (целые). Выпуклая оболочка неотрицательных целочисленных решений, удовлетворяющих ограничениям задачи (3), обозначается через Р (6, т), лр).
Было показано, что оптимальное решение задачи (3) естественным обрааом соответствует оптимальному решению задачи (2). Если ~г» ) О, то оптимальное решение аадачи (2) является 20 ь ввкдгпиг лзъ также оптимальным решением задачи (1). Многогранники Р„. (В, Х, Ь) и Р (С, т), л„) по существу одинаковы. Точка (хз, хл) является вершиной многогранника 1э,.
(В, Х, Ь), тогда и только тогда, когда 1 = Р (хв, хл) — верппша многогранника 1' (6, т), д0). Если 1(а;) = 1(а;), ~ Ф1, то либо х; = О, либо х; =- О. В этой главе мы изучим многогранник Р (6, ц, л,) независимо от минимизации целевой функции ~с* (л) 1 (л). Выпуклая оболочка 1' (6, т), л,) представляет особый интерес, поскольку все ее верпшны являются оптимальными решениями задачи (1) с некоторой достаточно болыпой правой частью Ь. Сформулируем это свойство более точно.
Если с —. (сз, сл) — некоторый вектор, где В— оптимальный невырождеппый базис задачи линейного программирования, соответствующей задаче (1), т. е. свВ 'Ь вЂ” сл = = ст ) О и В 'Ь О, то оптимальное решение х задачи (1) совпадает с оптимальным решением задачи (2), которое является вершиной многогранника Р„(В, Х, Ь), при условии, что Ь вЂ” достаточно большое. Зта вершина многогранника Р, (В, Х, Ь) может быть получена из соответствующей вершины многогранника Р (6, т), л,).
Если ч — некоторая ' вершина многогранника Р (6, т), л„), то в задаче (1) существует вектор с, оптимальный базис В н Ь, такие, что оптимальное решение задачи (1) получается из вершины ч. Другое важное свойство многогранника Р (6, ц, у„) состоит в том, что его грани являются в некотором смысле самыми сильными отсекающими плоскостями для задачи (1). В гл. 13 мы сформировали отсечение Гомори после получения оптимального решения задачи линейного программирования. Любая отсеказощая плоскость, сформированная без использования условий хв ) О, является просто яеотрицательной взвешенной комбинацией граней.
Заметим, что мпогогранпик Р (6, ц, л0) либо пустой, либо и'-мерный. Если лс не лежит в подгруппе, порожденной элементами т), то Р (6, т), л ) — пустой, или, что то же самое, задача (3) не имеет допустимых решений. Отсюда следует, что многогранник Р,.(В, Ь(, Ь) также пуст и что исходная задача целочисленного программирования (1) не имеет решения. Если Р (6, т), л~) не пуст, то пусть 1 =- (1(л ),..., 8 (лд),..., Ф (лж)) — его точка, з(Ь)— порядок группового элемента Ь, а и (Ь) есть я'- мерный вектор, такой, что 1 (Ь) = 1, а все остальные компоненты равны О.
Тогда вектор 1 + г (Ь) и (Ь) также является точкой многогранника Р (6, ц, л0), Для каждого Ь Е т) точка 1+ г(Ь) и (Ь) является допустимой. Ясно, что зти и' =- ! ц ( точек независимы; следовательно, многогранник Р (6, т), лс) — и'-мерный. Поскольку Р (6, ц, л,) — и'-мерный многогранник, будем использовать слово «грань» для обозначения (и' — 1)-мерной гиперплоскости, такой, что ГЛ.
20. ГРАНИ ПКЛОЧИСЛВННОГО МНОГОГРАННИКА 1) все точки Р (6, т[, л0) лежат по одну сторону этой гиперплоскости; 2) каждая точка гиперплоскости записывается как взвешен:ная сумма и' точек иа Р (С, ц, Р0). Паждую грань многогранника Р (С, т), 40) можно представить в виде неравенства (точки грани удовлетворяют равенству, а все точки из Р (С, т), л0) — неравенству) 2'. у(а) ~(к))у' (4) меч Докаязегн что (а) у (д) ) О н (б) у, ) О. Предположим, что в (4) имеется коэффициент у (й) ( О.
Пусть г (й) — порядок труппового элемента й. Тогда 1 + йз (й) и (й) также является решением аадачи (3) и, следовательно, принадлежит Р (С, э), д0). Так как все точки многогранника Р (6, т[, Р0) располагаются по одну сторону грани, то Х У (д') 2(а)+У (й) [Г(й)+ йз(й)))У (5) аеж а~л для любого положительного й. Однако при достаточно больших й неравенство (5) не выполняется в силу у (й) < О, Таким образом, отрицательных у (д) в соотношении (4) нет. Поскольку у (д) ) О и ~ (4) ) О, мы заключаем, что в (4) у, )~ О.
Обозначим грань ,'многогранника Р (6, э), 40) через (у, у0), где у есть и'-мерный вектор, а у,— скаляр. В х-пространстве обозначим грань многогранника Р„.(В, Х, Ь) через (ув, уаь уе). Поскольку хз = В '(Ь вЂ” Мхк), неравенство в х-пространстве эквивалентно неравенству для пебазисных переменных хи. Обозначим соответствующее неравенство для переменных хк через (О, уи, у,). Заметим, что (О, уи, у,) является (и — 1)-мерной гранью многогранника Р, (В, Х, Ь) тогда и только тогда, когда (у, у0) есть (и' — 1)-мерная грань многогранника Р (6, т), д0), где у [1 (аэ)) = =- ун Чтобьг получить грань многогранника Р„(В, Х, Ь), мы просто запишем значения компонент у (4) па всех соответствуэощих местах в уи. Неравенство ~ У(з)2(д)~)У0 (6) РЕЧ ) О, определяет ту часть ро страиства, где содерэкитси грань многогранника Р (С, э), 40).
Грань обладает следующими свойствами: 1) все точки многогранника Р (6, т[, л0) расположены по одну сторону от этой грани и 2) все точки грани могут быть ааписаны как взвешенные суми э вершин Р (С, т[, л0). 20Л. ВВЕДЕНИЕ 427 Обозначим множество неотрицательных целочисленных решений задачи (3) через Т. Легко показать, что (6) дает грань многогранника Р (6, т), лг) тогда и только тогда, когда 1') для каждого Ф с Т выполняется у1 ) у, и 2') имеется и' векторов 11 с Т, которые порожда1от гиперплоскость у 1 = у,.
Теогема 20.1. Неравенство ус ) ув ) 0 дает грань Р (С,т), яг) тогда и только тогда, когда у — базисное допустимое решение системы неравенств (7) ус ) у, (для всех ь й Т). Зта система предполагает наличие одного неравенства для каждого ь с Т. (Напомним, что базисное допустимое решение есть решение, которое удовлетворяет всем неравенствам и образует равенства на мноясестве строк ранга п'.) Доказательство. Докажем сначала, что если (у, у,) — грань, то ( у, у,) — базисное допустимое решение системы (7). Если (у уо) — грань, то из 1') следует у1)~ ув для всех $ Е Т, а из 2') следует, что имеется п' различных векторов В Е Т, которые удовлетворяют соотношени1о уВ = у, и порождают гиперплоскость у1 = у„.
Поскольку у„) О, грань пе проходит через начало координат. Отсюда заключаем, что и' векторов В линейно независимы. Следовательно, у — базисное решение системы (7). Если у — базисное допустимое решение системы неравенств (7), то у$ ) у, для всех 1 Р Т и, следовательно, 1') выполнено. Поскольку у — базисное допустимое решение, имеется и' независимых строк в (7), которые обращаются в равенства. Мы можем тогда взять эти строки в качестве векторов 11. Поскольку П линейно независимы, они дол'кпы порождать гиперплоскость у1 = уь, так что 2') также выполнено. Следовательно, (у, у,)— грань.
° Можно сделать несколько замечаний относительно теоремы 20.1. 1. В теореме 20.1 можно считать у, = 1, поскольку поло;кительные множители (у, у,) пе меняют грани. 2. Хотя имеется бесконечно много векторов 1, принадлежащих Т, все 1, для которых 7 (в) ) з (4), излишни. Следовательно, в качестве общего числа неравенств системы (7) можно.
взять И в(д). вес 3. С большим, ио конечным числом неравенств системы (7) придется иметь дело при вычислениях с помощью строка-порождающих методов, подобных описанным в работах [82) и [91[. В основном мы используем либо прямой, либо двойственный симплекс-метод, по строки порождаем только, когда это необходимо.
428 ГЛ, ЭО. ГРАНИ ЦКЛОЧИСЛКННОГО МНОГОГРАННИКА (Вычисления, проводимые для получения грани многогранника, описаны в з 20.2.) Предположим, например, что мы намереваемся получить отсекающую плоскость для задачи целочисленного программирования (2), такую, что угол между у и с минимальный. Иными словами, мы хотим минимизировать !! с )1 (( т )~ у1 )~ 70 для всех 1 б Т. при условии Твогвмл 20.2. Единственно возможными гранями (у, 70) многогранника Р (6, т~, лг) при 70 —.- 0 являются и' гиперплосксстей у = и (Ь) или, что эквивалентно, ! (и) = 0 (т.
е. гиперплоскости, содержащие координатные оси). Предположим, что мы располагаем всеми $ с Т. Тогда это задача линейного программирования со многими неравенствами, по одному неравенству для каждого Ф, принадлежащего Т. Если используется двойственный симплекс-метод, то нам надо, имея двойственное допустимое у, получить неравенство, которому текущее у не удовлетворяет. Таким образом, вычисления состоят иа двух частей, Первая часть — вычисление двоиственной допустимой симплексной таблицы для целевой функции (су)(()~ с!) )) у ~!), ограниченной подмножеством неравенств иэ (7). Вторая часть— вспомогательные вычисления (порожденных) неравенств, используемых в первой части.
Если воспользоваться текущим у в графе П (6, т), у), можно найти кратчайший путь от 0 до яг длины у~ ( 70. Тогда неравенство уФ )~ у, не выполняется. Это неравенство добавляется к неравенствам первой части. (Неравенство пеобходимо видоизменить, прежде чем записать его в конец двойственной симплексной таблицы.) Затем мы производим основной шаг двойственного си!шлаке-метода первой части и получаем новое у. Это новое у идтерпретируется как длины дуг при вспомогательных вычислениях. Если, используя у как длины дуг, мы не сможем найти кратчайшего пути от 0 до Л0 с общей длиной у1 70, то это у является такнге прямо допустимым и, следовательно, оно оптимально.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
