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