Исследование полиэдральных характеристик задач комбинаторной оптимизации тема диссертации и автореферата по ВАК РФ 00.00.00, доктор наук Николаев Андрей Валерьевич

• Николаев Андрей Валерьевич
• доктор наук
• 2024

Оглавление диссертации доктор наук Николаев Андрей Валерьевич

1.6 Число фасет

1.7 Размер коэффициентов

1.8 Сложность расширения

1.9 Целочисленное программирование

1.9.1 Постановка задачи

1.9.2 Релаксация линейного программирования

1.9.3 Модели целочисленного программирования

1.10 Аппроксимационные алгоритмы и разрыв целочисленности

1.11 Полиэдральные графы

1.11.1 Смежность вершин и симплекс-подобные алгоритмы

1.11.2 Диаметр графа

1.11.3 Кликовое число и конусные разбиения пространства

2 Релаксационные многогранники

2.1 Релаксации разрезного и булева квадратичного многогранников

2.1.1 Многогранник задачи о разрезе

2.1.2 Булев квадратичный многогранник и ковариантное отображение

2.1.3 Канонический вид и блочная матрица

2.1.4 Некоторые свойства релаксационного многогранника BQP¿p(п)

2.1.5 Ориентированный максимальный разрез

2.1.6 Минорные характеристики матрицы

корневого полуметрического многогранника

2.1.7 Метрический многогранник и графические вершины

2.1.8 Алгоритм генерации графических

вершин метрического многогранника

2.1.9 Знаменатели дробных вершин метрического

многогранника и гипотеза Поляка-Туза

2.1.10 Задача распознавания целочисленности

2.1.11 Распознавание целочисленности

на метрическом многограннике BQP¿p (п, 3)

2.1.12 Неинвертируемые гиперграфы

2.1.13 Гиперграфы точек метрического многогранника

2.1.14 Последовательность релаксаций BQPLP (п,к)

2.1.15 Релаксация BQPLp(п, 4)

2.1.16 Релаксация BQPLP(п, 5)

2.1.17 Релаксация BQPLP(п, 6)

2.1.18 Трёхмерная структура координат метрического многогранника

2.2 Многогранник задачи 3-выполнимость

2.2.1 Определение многогранника

2.2.2 Постановка задач о 3-выполнимости специального вида

в форме распознавание целочисленности

2.2.3 Нецелочисленные вершины

2.2.4 Задача целочисленного программирования на SATPLp(т,п)

2.2.5 Полиномиально разрешимые подзадачи распознавания целочисленности на SATPLP (т,п)

2.2.6 Задача о 2-3 раскраске двудольного графа

с ограничениями по рёбрам

2.3 Итоги главы

2.3.1 Булев квадратичный многогранник

2.3.2 Многогранник задачи 3-выполнимость

3 Полиэдральные графы

3.1 Задача о разрезе

3.1.1 Введение

3.1.2 Многогранник и конусные разбиения для задачи о разрезе

3.1.3 Критерии смежности в графах

конусных разбиений задачи о разрезе

3.1.4 Кликовое число

3.1.5 Диаметр графа

3.1.6 Степени вершин

3.1.7 Результаты

3.2 Точки на сфере с центром в начале координат

3.3 Остовные деревья с ограничением на число листьев и диаметр

3.3.1 Введение

3.3.2 Многогранник задачи об остовном дереве

3.3.3 Остовное дерево с ограничением на число висячих вершин

3.3.4 Остовное дерево ограниченной степени

3.3.5 Результаты

3.4 Сбалансированный и несбалансированный двудольный подграфы

3.4.1 Введение

3.4.2 Сбалансированный полный двудольный подграф

3.4.3 Максимальный полный двудольный подграф

3.4.4 Минимальный полный двудольный подграф

3.4.5 Результаты

3.5 Многогранник задачи 3-выполнимость

3.5.1 Смежность вершин

3.5.2 Диаметр и кликовое число

3.5.3 Свойство Трубина

3.5.4 Результаты

3.6 Пирамидальные циклы

3.6.1 Введение

3.6.2 Многогранник пирамидальных циклов

3.6.3 Граф многогранника пирамидальных циклов

3.6.4 Диаметр и кликовое число графа

многогранника пирамидальных циклов

3.7 Пирамидальные туры с шагами назад

3.7.1 Введение

3.7.2 Пирамидальные туры с шагами назад

3.7.3 Вспомогательные утверждения

3.7.4 Необходимое и достаточное условие смежности

3.7.5 Алгоритм проверки смежности

3.7.6 Диаметр графа

3.7.7 Кликовое число

3.7.8 Результаты

3.8 Итоги главы

4 Гамильтоново разложение 4-регулярного мультиграфа

4.1 Многогранник коммивояжёра

4.2 Постановка задачи

4.3 Модели целочисленного линейного программирования

4.3.1 Модель Данцига-Фалкерсона-Джонсона

4.3.2 Модель Миллера-Такера-Землина

4.3.3 Другие модели

4.4 Поиск с возвратом

4.4.1 Алгоритм поиска с возвратом на основе построения простого пути

4.4.2 Алгоритм поиска с возвратом

на основе цепного фиксирования рёбер

4.5 Алгоритм имитации отжига

4.5.1 Общая схема

4.5.2 Множество допустимых решений

4.5.3 Функции энергии и план охлаждения

4.5.4 Построение соседнего решения

4.6 Поиск с чередующимися окрестностями

4.6.1 Множество допустимых решений

4.6.2 Целевая функция

4.6.3 Цепное фиксирование рёбер

4.6.4 Локальный поиск для ориентированных графов

4.6.5 Спуск с чередующимися окрестностями

для неориентированных графов

4.6.6 Итоговый алгоритм

4.7 Вычислительные эксперименты

4.8 Итоги главы

Заключение

Список литературы

Статьи в изданиях, рекомендованных ВАК

Свидетельства о регистрации программ для ЭВМ

Другие публикации автора

Введение диссертации (часть автореферата) на тему «Исследование полиэдральных характеристик задач комбинаторной оптимизации»

Введение

Актуальность работы. Особое значение в прикладной математике и теоретической информатике играет теория сложности комбинаторных задач и разработка эффективных алгоритмов их решения, в частности задача соотношения классов сложности Г и ЫР, включенная в список 7 задач тысячелетия по версии математического института Кл-эя [69]. Полиэдральная комбинаторика и исследование свойств многогранников, ассоциированных с задачами комбинаторной оптимизации, предлагают перспективный подход к анализу сложности задач и разработке новых эффективных алгоритмов, которые могут быть применены в широком диапазоне прикладных областей.

Комбинаторная оптимизация как целостная математическая дисциплина относительно молода. Исторически можно проследить, как возникали независимые направления исследований, которые по отдельности рассматривали такие задачи как оптимальные назначения (Кёниг [169] и Эгервари [93]), остовные деревья (Борувка [45]), транспортные задачи (Толстой [291]) и задача коммивояжёра (Менгер [188]). Только в 1950-х годах, когда появился объединяющий инструмент линейного и целочисленного программирования, а также значительно повысился интерес к области исследования операций, задачи комбинаторной оптимизации были собраны в единую структуру, и установлены связи между ними.

Таким образом, линейное программирование (ЛП) является поворотным моментом в истории комбинаторной оптимизации. Первоначальная теория линейного программирования Канторовича [285] и Купманса [2] была мотивирована именно комбинаторными приложениями, в частности, транспортной задачей. А после появления в 1947 году симплекс-метода Данцига [72] любую задачу комбинаторной оптимизации пытаются прежде всего решать с помощью методов линейного программирования, часто очень успешно. Отдельно следует отметить одну из основополагающих работ в полиэдральном подходе к комбинаторной оптимизации — статью Данцига, Фалкерсона и Джонсона 1954 года [71] о решении задачи коммивояжёра на 49 городах с помощью линейного программирования. В этой статье были представлены несколько новых методов решения задачи, которые сейчас являются базовыми в комбинаторной оптимизации. В частности, Данциг, Фалкерсон и Джонсон продемонстрировали важность отсекающих гиперплоскостей. Более подробно о становлении теории и задач комбинаторной оптимизации можно прочитать в обзорной статье Схрейвера [235].

Отцом-основателем теории линейного программирования считается советский матема-

тик Леонид Канторович, который в 1939 году описал общую постановку задачи линейного программирования и предложил метод для её решения [285]. Примерно в то же время экономист Тьяллинг Купманс переформулировал классические экономические задачи в форме задач линейного программирования [2]. В 1975 году Канторович и Купманс разделили Нобелевскую премию по экономике за эти труды. В 1941 году Фрэнк Хичкок также разработал модели линейного программирования для ряда транспортных задач [138]. Эти работы сыграли особенно значимую роль в военной логистике во время Второй мировой войны. К сожалению, Хичкок скончался в 1957 и не смог разделить Нобелевскую премию вместе с Канторовичем и Купмансом. В 1946-1947 годах Джордж Данциг независимо разработал общую постановку линейного программирования для решения задач планирования ВВС США. В 1947 году Данциг представил симплекс-метод [72], первый алгоритм, который успешно и быстро решал задачу линейного программирования в большинстве случаев. Более подробно об истории становления линейного программирования можно прочитать в мемуарных статьях Джорджа Данцига «Reminiscences about the origins of linear programming» [74] и «Origins of the Simplex Method» [73].

Симплекс-метод Данцига оказался чрезвычайно эффективным на практике и с годами был значительно дополнен и улучшен различными модификациями, например методом исключения переменных Фурье-Моцкина [236]. Однако, в 1972 году Виктор Кли и Джордж Минти [167] построили особый многогранник в евклидовом пространстве Rd с 2d гипергранями и 2d вершинами:

xi < 5, 4xi + x2 < 25, 8xi + 4x2 + x3 < 125,

2dxi + 2d-1x2 + ■ ■ ■ + 4xd-i + xd < 5d, x1 > 0, ..., xd > 0,

получивший название куб Кли-Минти.

Рассмотрим на кубе Кли-Минти задачу линейного программирования с целевой функцией

2d-1xi + 2d-2x2 + ■ ■ ■ + 2xd-i + xd,

тогда симплекс-метод, выбирающий в качестве начальной вершины точку (0, 0,... , 0), последовательно посетит все 2d вершин многогранника, пока не достигнет оптимального решения (0, 0,..., 5d).

Таким образом, симплекс-метод можно обмануть, превратив его в алгоритм полного перебора вершин, что приводит к экспоненциальной в худшем случае трудоёмкости. В последующих работах почти для каждого варианта симплекс-метода было доказано, что существует семейство линейных программ, для которых алгоритм работает плохо (см.

обзор Терлаки и Чжан [245]). Существование версии симплекс-метода с полиномиальным гарантированным временем работы остаётся открытым вопросом.

С другой стороны, практические наблюдения показали, что симплекс-метод необычайно эффективен на реальных задачах, несмотря на его экспоненциальную сложность в худшем случае. Этот факт привёл теорию анализа алгоритмов к разработке других мер оценки сложности. В частности, симплекс-метод имеет полиномиальное в среднем время работы при различных распределениях вероятностей, при этом точная производительность алгоритма зависит от выбора распределения для случайных матриц на входе (см. Схрейвер [236]).

Важный теоретический прорыв случился в 1979 году, когда Леонид Хачиян модифицировал метод эллипсоидов Шора для решения задачи линейного программирования [294]. Получившийся алгоритм в худшем случае требовал O(d6L) операций с числами длины O(L) бит, что давало общую трудоёмкость O(d6L2 log L log log L) битовых операций. Таким образом, это был первый полиномиальный в худшем случае алгоритм для задачи линейного программирования. В 1982 году Хачияну была присуждена премия Фалкерсо-на за выдающуюся работу в области дискретной математики.

К сожалению, метод эллипсоидов оказался мало применим на практике из-за очень высокой степени многочлена в оценке времени работы, проигрывая симплекс-методу на большинстве задач. Однако этот результат показал принципиальную возможность разработки полиномиальных алгоритмов для задачи линейного программирования, отличных от симплекс-метода, что дало толчок к интенсивному поиску новых алгоритмов. И уже в 1984 году Нарендра Кармаркар [158] представил свой полиномиальный алгоритм из класса методов внутренней точки с трудоёмкостью O(d3'5L2 log L log log L) битовых операций, что позволяло применять алгоритм для решения практических задач. В последующие годы алгоритм Кармаркара был значительно модифицирован и улучшен. Современные коммерческие библиотеки для решения задач линейного программирования, такие как Gurobi [132], включают в себя и симплекс-метод и методы внутренней точки, которые дают преимущество в разных ситуациях и на разных типах задач.

В постановке задачи линейного программирования предполагается, что переменные и, соответственно, решение принимают непрерывные значения. Для таких задач как поиск максимального потока в транспортной сети — это допустимо. Однако многие задачи комбинаторной оптимизации не предполагают дробных решений. В таком случае классической моделью выступает задача целочисленного линейного программирования (ЦЛП), которая заключается в оптимизации линейной целевой функции на множестве целочисленных решений системы линейных неравенств:

т

минимизировать c x, при условиях Ax < b, x е Zd.

Так как различные NP-трудные комбинаторные задачи, например задача коммивояжё-

ра и вершинное покрытие, сводятся к задаче ЦЛП, то та, в свою очередь, также является NP-трудной. В частности, задача 0-1 целочисленного линейного программирования, в которой переменные ограничены значениями 0 и 1, входит в список 21-й основной NP-полной задачи Карпа [159].

Одним из первых алгоритмов для задачи целочисленного линейного программирования был метод отсекающих плоскостей, предложенный Ральфом Гомори в конце 50-х [119; 120]. Алгоритм Гомори основан на построении релаксации линейного программирования, которая получается если в модели ЦЛП снять ограничения целочисленности переменных, и решении соответствующей нецелочисленной задачи методами ЛП. По основной теореме линейного программирования оптимальное решение релаксационной задачи достигается в вершине полиэдра / выпуклого многогранника. Если эта вершина целочисленная, то решение задачи ЦЛП найдено. В противном случае, гарантированно существует гиперплоскость, отделяющая найденное дробное решение от множества целочисленных решений задачи. Соответствующее гиперплоскости линейное неравенство добавляется в модель, отсекая текущее нецелочисленное решение. Процесс повторяется до тех пор, пока не найдено оптимальное целочисленное решение. Ключевым вкладом Гомори была простая процедура построения отсекающих гиперплоскостей. Однако большинство экспертов, включая самого Гомори, посчитали данную процедуру непрактичной из-за вычислительной нестабильности и непредсказуемого числа итераций до получения решения.

Долгие годы основным методом решения задачи ЦЛП был метод ветвей и границ, предложенный Эйлсой Лэнд и Элисон Дойг в 1960 году [175]. В его основе вновь лежали релаксации линейного программирования, которые позволяли легко строить оценки на подмножества целочисленных решений, что в свою очередь позволяло отсекать эти решения и значительно упрощать перебор. В дальнейшем метод ветвей и границ был перенесён с задачи ЦЛП на другие комбинаторные задачи. Например, отметим алгоритм Литтла для задачи коммивояжёра [9].

В 1991 году Падберг и Ринальди [209] переработали классический алгоритм Лэнд и Дойг, применив отсекающие плоскости для усиления релаксации линейного программирования. Алгоритм получил название «метода ветвей и отсечений». Падберг и Ринальди применили алгоритм ветвей и отсечений для задачи коммивояжёра и нашли оптимальные решения вплоть до 2 392 городов, что являлось абсолютным рекордом на тот момент.

Наибольший интерес здесь представляет тот факт, что многие годы исследования полиэдральных характеристик задачи коммивояжёра не пропали даром. Хотя полного описания многогранника коммивояжёра для 11 и более городов не известно, были построены различные классы линейных неравенств, определяющие фасеты многогранника: неравенства 2-паросочетания, неравенства деревьев клик, неравенства гребней и др. (см. обзор Грётчела и Падберга [128]) Метод ветвей и отсечений позволял использовать любой из классов неравенств в описании многогранника для усиления релаксации и получения лучших практических результатов. На основе метода ветвей и отсечений Апплгейт и соавторы разработали программу «Concorde TSP Solver» [66], которая успешно решила все экзем-

пляры задачи коммивояжёра из библиотеки «TSPLIB» [228], объединяющей в себе примеры задачи коммивояжёра и связанных задач из различных источников. Например, задачу pla85900 на 85 900 городах, возникающую при проектировании интегральных схем (VLSI) и поставленную Джонсоном во время работы в AT&T Labs [205]. Более подробно с данным алгоритмом можно ознакомиться в монографии «The Traveling Salesman Problem. A computational study» [247].

Наконец, в середине 90-х Жерар Корнюэльс и соавторы [121] восстановили репутацию отсечений Гомори, показав, что те очень эффективны в методе ветвей и отсечений. В настоящее время все коммерческие решатели задачи целочисленного линейного программирования (например, Gurobi [132]) так или иначе используют отсечения Гомори. Дело в том, что отсечения Гомори легко генерируются из симплекс-таблицы, тогда как многие другие типы отсечений являются либо слишком трудозатратными, либо вовсе NP-трудными для построения. История вопроса изложена в работе Корнюэльса [70].

Таким образом, хотя в общем случае задача целочисленного программирования является NP-трудной, для неё известны относительно эффективные с практической точки зрения алгоритмы. Благодаря этому формулировка комбинаторных задач в виде моделей целочисленного программирования является одним из основных подходов рамках парадигмы «преобразуй и властвуй».

Отметим, что релаксации линейного программирования, которые получается при снятии ограничений целочисленности в моделях ЦЛП, и соответствующие релаксационные многогранники задач являются важным инструментом разработки и анализа комбинаторных алгоритмов. В частности, на различных релаксациях разрезного многогранника основаны алгоритм Барахоны для задачи о максимальном разрезе в графе не содержащем K5 в качестве миноров [27], алгоритм Поляка для задачи характеризации слабо двудольных графов [221], алгоритм Бондаренко для задачи об ориентированном максимальном разрезе [38; 271], а также многие другие.

Два ключевых направления при работе с релаксациями линейного программирования: построение отсекающих гиперплоскостей, которые разделяют целые и дробные вершины многогранника, а также описание структуры множества нецелочисленных вершин. Отсекающие гиперплоскости непосредственно применяются при решении задачи с помощью модели целочисленного линейного программирования и метода ветвей и отсечений Пад-берга и Ринальди [209]. Огромное число работ посвящено построению различных классов линейных неравенств, определяющих фасеты целочисленных многогранников. Например, гиперметрические неравенства, клико-паутинные неравенства, неравенства букета циклов, неравенства циркулянта, парашютные неравенства и др. для задачи о разрезе (см. монографию Деза и Лоран [83]).

С другой стороны, структура множества нецелочисленных вершин релаксационного многогранника играет особую роль в разработке аппроксимационных алгоритмов на основе техники ЛП-округления: найти оптимальное дробное решение релаксационной задачи, а затем округлить дробное решение до целочисленного. Ключевым понятием здесь

выступает разрыв целочисленности (для задачи на минимум) — точная верхняя грань отношения между оптимальным решением для целочисленной задачи и дробным решением релаксационной задачи по всем возможным экземплярам I:

OPT IG = ^p FRAC •

Для задачи на максимум точная верхняя грань заменяется на точную нижнюю.

Так как оптимальное решение задачи обычно не известно, то разрыв целочисленно-сти оценивают сверху как отношение дробного решения релаксационной задачи и его округления. Например, Немхаузер и Троттер [198] доказали, что все вершины релаксационного многогранника задачи о вершинном покрытии являются полуцелыми, т. е. их координаты принимают значения только из множества {0, |, 1}. Знание структуры нецелочисленных вершин релаксации линейного программирования помогает оценить разрыв целочисленности и, соответственно, точность аппроксимации. Действительно, если знаменатели координат всех дробных вершин релаксационного многогранника ограничены некоторой константой q, то разрыв целочисленности не превосходит q. Полуцелые вершины релаксационного многогранника задачи о вершинном покрытии гарантируют, что разрыв целочисленности не превосходит двух, а простое округление вверх даёт нам 2-аппроксимационный алгоритм.

На этом подходе основаны, например, (2 — |)-аппроксимационный алгоритм Хохбау-ма [140] для задачи о вершинном покрытии в k-раскрашиваемом графе, (log п)-аппроксима-ционный алгоритм Вазирани [255] для задачи о покрытии множества, 3/4-аппроксимацион-ный алгоритм Яннакакиса для задачи MAX-2SAT [259], полиномиальная приближённая схема Ленстры, Шмойса и Тардос для задачи составления расписания несвязанных параллельных машин [178], (3 — 1 )-аппроксимационный алгоритм Кэлинеску, Карлоффа и Рабани для задачи о множественном разрезе [50] и многие другие. Кроме того, нецелочисленные решения релаксационных задач важны для техники вероятностного округления, когда дробные координаты рассматриваются как вероятности и округляются соответственно. Более подробно с аппроксимационными алгоритмами на основе линейного программирования можно ознакомиться в монографии Вазирани [255].

К сожалению, не всегда дробные вершины релаксаций линейного программирования обладают хорошими свойствами. Например, Моник Лоран [177] описала особый класс графических дробных вершин метрического многогранника (наиболее простой релаксации разрезного многогранника, определяемой ограничениями вида неравенств треугольника), знаменатели которых растут с линейной по размеру задачи скоростью. Прямым следствием является тот факт, что знаменатели дробных координат релаксации могут принимать любые целочисленные значения. Аналогичные результаты о быстром росте знаменателей дробных координат вершин релаксационных многогранников было получены для задачи о трёхмерном сочетании (Ильичев и Шевченко [284]), многоиндексной аксиальной задачи о назначениях (Кравцов [172; 287]), совершенном паросочетании в гиперграфе (Беккен-бах [29]) и ряда других.

Алгоритм симплекс-метода Данцига для задачи линейного программирования быстро обрёл популярность за счёт своей простоты и эффективности, в основе которой лежат свойства полиэдрального графа многогранника, т. е. графа, вершинами которого являются вершины многогранника, а рёбрами — геометрические рёбра (одномерные грани). С геометрической точки зрения, симплекс-метод перебирает решения задачи, переходя от одной вершины многогранника к другой по рёбрам полиэдрального графа в направлении увеличения (для задачи на максимум) значения линейной целевой функции. Когда среди смежных не найдётся лучшей вершины, выпуклость множества допустимых решений гарантирует, что найден глобальный максимум.

Эффективность симплекс-метода мотивировала исследователей на создание целого класса симплекс-подобных алгоритмов комбинаторной оптимизации, которые переходят от одного допустимого решения к другому по рёбрам полиэдрального графа. К этому классу, в частности, относятся: алгоритм Эдмондса для задачи о наибольшем паросоче-тании [92], алгоритм Баласа и Падберга для задачи о покрытии множества [20], алгоритм Балински для задачи о назначениях [22], алгоритм Икуры и Немхаузера для задачи об упаковки множества [144] и ряд других.

Ключевым вопросом при разработке симплекс-подобных алгоритмов и работе с полиэдральными графами является задача проверки смежности/несмежности вершин: для заданного многогранника Р и двух его вершин х и у определить, существует ли ребро между вершинами х и у в полиэдральном графе многогранника Р?

Для некоторых многогранников задач описаны легко проверяемые необходимые и достаточные критерии смежности вершин полиэдральных графов. В частности, покрытие множества (Балас и Падберг [21]), задача о назначениях (Балинский и Русакофф [23]), независимое множество (Хватал [61]), вершинное покрытие, разбиение и частичный порядок (Хаусманн и Корте [136]), полиматроиды (Топкис [249]), упаковка множества (Агиле-ра, Кац и Толомей [4]) и ряд других.

К сожалению, в общем случае задача проверки смежности вершин в полиэдральном графе многогранника является сложной. Первым подобный результат получил в 1978 году Христос Пападимитриу, доказав, что проверка несмежности вершин в многогранниках симметричной и асимметричной задач коммивояжёра КР-полна.

В дальнейшем аналогичные результаты об КР-полноте проверки несмежности вершин были получены и для других комбинаторных задач, в частности: 0-1 рюкзак (Гейст и Родин [114]), покрытие множества и целочисленное программирование (Мацуи [185]), кубический подграф (Бондаренко и Юров [41]), частичный порядок (Фиорини [101]), связные к-факторы (Симанчёв [290]).

Особое внимание исследователей в области комбинаторной оптимизации всегда привлекала задача коммивояжёра. Пусть х = (V, Ех) и у = (У,Еу) — два гамильтоновых цикла на множестве вершин V. Обозначим через х и у 4-регулярный мультиграф (V, Ех и Еу), который содержит копию каждого ребра х и у. Отметим, что если два цикла содержат одно и то же ребро е, то в мультиграф х и у добавляются обе копии ребра.

В 1969 году Катта Мурти [196] предложил необходимое и достаточное условие проверки несмежности вершин в полиэдральном графе коммивояжёра: две вершины у(х) и у(у) многогранника коммивояжёра Х8Г(п) не смежны тогда и только тогда, когда мультиграф х и у содержит третий гамильтонов цикл г, отличный от х и у. На основе критерия смежности Мурти предложил симплекс-подобный алгоритм для задачи коммивояжёра [195;

Критерий Мурти был основан на следующей вспомогательной лемме: если из рёбер двух гамильтоновых циклов х и у можно собрать третий гамильтонов цикл г, то все оставшиеся рёбра т = (х и у)\г также образуют гамильтонов цикл [196].

Однако, в 1976 году Раммохан Рао [226] доказал, что это утверждение неверно, построив простой контр-пример

х = (1, 4, 5, 3, 2, 6), у = (1, 2, 6,4, 3, 5), г = (1, 4, 6, 2, 3, 5),

при котором все рёбра мультиграфа х и у не попавшие в гамильтонов цикл г разбиваются на 2 цикла (1, 2,6) и (3,4, 5).

Рао исправил критерий Мурти и предложил новые условия несмежности в полиэдральном графе многогранника коммивояжёра. Достаточное условие несмежности Рао утверждает, что если мультиграф х и у содержит два гамильтоновых цикла г и т без общих рёбер, отличных от х и у, то соответствующие вершины у(х) и у(у) многогранника коммивояжёра не смежны. С другой стороны, по необходимому условию несмежности Рао, если вершины у(х) и у(у) многогранника коммивояжёра не смежны, то мультиграф х и у содержит как минимум два гамильтоновых цикла, отличных от х и у (см. [226]).

К сожалению, проверка необходимого и достаточного условий Рао — это сложная комбинаторная задача. В частности, Пападимитриу [211] доказал, что уже вопрос содержит ли мультиграф объединения х и у третий гамильтонов цикл г является КР-полной задачей.

Отметим, что задача построения гамильтонова разложения регулярного графа, т. е. разбиение множества рёбер на гамильтоновы циклы имеет приложения за пределами полиэдральной комбинаторики и проверки несмежности вершин в полиэдральном графе многогранника коммивояжёра. Например, при проектировании сетей связи в модели широковещательной передачи, когда каждый узел посылает и принимает сообщения от всех соседних узлов, если граф сети допускает разложение на гамильтоновы циклы без общих рёбер, то трафик можно равномерно распределить по всем каналам связи (Роули и Боз [230], Хунг [143]). Среди других практических приложений отметим разработку самокорректирующих кодов (Бейли [19]), распределенный анализ данных с сохранением конфиденциальности (Клифтон и др. [248], Донг и Кресман [88]) и задачу о нескольких коммивояжёрах (Краруп [171], де Корт [76], Гимади и др. [12; 279]). С точки зрения вычислительной сложности, проверка содержит ли заданный граф гамильтоново разложение является КР-полной задачей уже для 4-регулярных неориентированных и 2-регулярных ориентированных графов (Перош [216]).

Хотя Кли и Минти доказали, что в худшем случае симплекс-метод вырождается в полный перебор [167], время работы алгоритма в среднем на практике близко к лучшему, а

не худшему случаю. Причины такого поведения кроются в полиэдральной основе алгоритма. Очевидной нижней оценкой на число итераций симплекс-метода является диаметр ¿(Р) полиэдрального графа, т. е. наибольшее расстояние между всеми парами вершин. Действительно, пусть кратчайшее расстояние между парой вершин и и V многогранника Р составляет ¿(Р) рёбер. Если симплекс-метод выбирает в качестве начального решения и, а оптимальное решение достигается в V, то как бы удачно симплекс-метод не выбирал очередную вершину, алгоритм не сможет выполнить меньше итераций, чем ¿(Р) (см., например, Данцига [75]).

В 1957 году Уоррен Хирш в письме Джорджу Данцигу высказал гипотезу [75] о том, что для <-мерного выпуклого многогранника Р с п гипергранями диаметр полиэдрального графа не превосходит следующей линейной оценки:

¿(Р) < п - 1.

Гипотеза Хирша была доказана для многих классов выпуклых многогранников. В частности, Денис Наддеф [197] доказал, что гипотеза Хирша верна для 0/1-многогранников, т. е. многогранников координаты вершин которых имеют значения только 0 и 1. Этот случай особенно важен, так как к 0/1-многогранникам относятся большинство комбинаторных многогранников, возникающих из моделей линейного и целочисленного программирова-

Гипотеза Хирша долгое время оставалась открытой, пока в 2011 году Франсиско Сан-тос не привёл контрпример 43-мерного многогранника с 86 гипергранями и диаметром 44 [232]. Однако, даже контрпример Сантоса показывает, что диаметр полиэдрального графа комбинаторного многогранника не бывает очень большим, и между любой парой вершин, как правило, существует достаточно короткий путь. Это объясняет почему в подавляющем большинстве случаев, кроме специально сконструированных примеров, симплекс-метод оказывается необычайно эффективен на практике. В частности, для многих комбинаторных задач найдены точные значения диаметра полиэдрального графа: задача о назначениях (Балинский и Русакофф [23]), задача о разрезе (Барахона и Махджуб [25]), транспортная задача (Брайтвелл, ван ден Хьювел и Стоуги [48]), задача о стабильных браках (Эйринакис, Магос и Муртос [94]), задача коммивояжёра (Падберг и Рао [210]) и многих других. Полиномиальная версия гипотезы Хирша о том, что для всех многогранников Р с п гипергранями ¿(Р) = 0(пк), где к — некоторое целое число, остаётся открытой.

Список литературы диссертационного исследования доктор наук Николаев Андрей Валерьевич, 2024 год

- - - -

9,1 + + б 0 8,1 + + б 0

0 г, 2 б 0 4,2 б

- - - -

В варианте 3(е)п требуется модификация столбца I, который следует рассмотреть подобно столбцу ] и т. д.

На некотором шаге эта процедура закончится ввиду конечности координатной матрицы и невозможности повторной модификации блоков. Без ограничения общности положим, что при построении точки V все строки из блоков точки и были изменены (не модифицированные строки можно просто временно не учитывать). Причем в каждой строке первый столбец в блоках был увеличен на е, второй столбец уменьшен на е.

Покажем, что такое построение точки V корректно. Предположим противное. Тогда найдётся некоторый столбец, пусть для определенности это будет столбец ], в блоках которого были изменены разные строки. Всего блоков рассматриваемого вида (с нулевой координатой в каждой строке, но без нулевого столбца) 6 типов (табл. 2.52).

Таблица 2.52. Шесть типов блоков рассматриваемого вида

X1'1 0

0 X2'2

0 X3'2

0 X1'2

X2'1 0

0 X3'2

0 X1'2

0 X2'2

X3'1 0

0 X1'2

X2'1 0

X3'1 0

X1'1 0

0 X2'2

X3'1 0

X1'1 0

X2'1 0

0 X3'2

Нетрудно проверить, что любые два блока, стоящих в одном столбце и не подпадающих под условие теоремы, не образуют противоречия, и в них можно выбрать две одинаковых строки для модификации (табл. 2.53). В то же время, любые три не одинаковых блока подпадают под условие теоремы, что противоречит исходному предположению (табл. 2.54).

Таблица 2.53. Любые два блока не образуют противоречия

1'1 + 0

0 2'2 Xi'j

0 3'2 ij е

1'1 + xk'j + е 0

2'1 xk'j 0

0 3'2 Xk'j е

Таким образом, при исходном предположении, операция построения точки V корректна и будет выполнена. Точка V существует и принадлежит многограннику ЯАТРрр(т,п).

Аналогично строится точка w Е ЯАТРрр(т,п), но увеличивается второй столбец ¿-й строки из блоков. При этом:

и = + w), (V = w).

Откуда, и — середина отрезка, соединяющего точки V и w многогранника ЯАТРрр (т, п). Противоречие, и не является вершиной. □

Применим лемму 2.2.10 для описания полиномиально разрешимых подзадач целочисленного программирования на многограннике ЯАТРрр(т,п).

Таблица 2.54. Любые три блока подпадают под условие теоремы

1,1 0

0 2,2

0 3,2

1,1 0

2,1 хк,з 0

0 3,2 Х к,л

1,1 х • Р, 0

0 2,2 хр,3

3,1 хр,з 0

Теорема 2.2.11. Если вектор с € Е6тга имеет вид

V? € Н„, За,,в,,7,- € {-1,1}, Уг € :

/ 1,1 . 2,2ч \ С 1,2 , 2,1\

в, (с1,, + С3,, ) — (с1,, + С3,, ),

/ 2,1 , 3,2\ \ / 2,2 , 3,1\ 7, (сг,,' + , — 7, (сг,,' +

то на многограннике ЯАТРрр(т, п) линейная целевая функция f (х) = стх достигает максимума в целой вершине. Если в ограничениях на вектор с все неравенства заменить на строгие, то среди вершин многогранника ЯАТРрр(т, п), на которых целевая функция f (х) = стх принимает максимальное значение, не будет ни одной нецелочисленной.

Доказательство. Часть 1. Начнем доказательство теоремы со второго утверждения. Рассмотрим вектор с, удовлетворяющий следующим ограничениям:

У? € Н„, За,,в,,7, € {-1,1}, Уг € :

1,1 2,2 1,2 2,1

а, (Я', + Я', ) > а, (Я', + Я,

1,1 3,2 1,2 3,1

2,1 3,2 2,2 3,1

7, (сг,,- + , > 7, (сг:, + ,

Предположим противное, а именно: целевая функция f (х) = стх достигает своего максимума в дробной вершине и многогранника ЯАТР^р (т, п).

По необходимому условию для нецелочисленных вершин (лемма 2.2.10) в координатной матрице точки и найдутся блоки г,? и к,?, координаты которых приведены в табл. 2.55. Обратимся к ?-му столбцу целевого вектора с:

За, € {-1,1}, Ур € :

( д,1 , г,2) > ( 9,2 , г,1) (Ср,, + Ср,, ) > а, (Ср,, + Ср,, ^

Таблица 2.55. Столбец ] координатной матрицы вершины и многогранника ЯАТР^р (т, п)

д,1 0

0 г,2

- -

0 д,2

г,1 0

- -

Если а = 1, то для р = к имеет место

д,1 + г,2 > д,2 , г,1

Ск,.7 + > + Я,.? •

Построим точку V по вершине и, заменив блок к, на блок, форма которого приведена в табл. 2.56.

Таблица 2.56. Координатный блок к, ] точки V

е д,2 е

г,1 е е

- -

Значение е выберем меньше тт{ж|'2, }. Точка V удовлетворяет системе (2.57)-(2.60) и принадлежит многограннику ЯАТРрр(т,п).

Оценим значение целевой функции / в точке V:

/(v) = f (и) - е ■ (сЙ + сЙ) + е ■ + ск;2),

С д,1 + г,2 > д,2 , г,1

С : + > + ,

е . (с9,1 + ^ — С^2 — СГ;1) > 0 е (ск,7 + 4,2 4,2) >

/(V) > /(и).

При переходе к точке V целевая функция уменьшается по переменным с^2 и с^* на е, но увеличится по с^* и ск; также на е. Так как для целевой функции / выполняется неравенство

д, 1 + г,2 > д,2 , г, 1 Ск , 2 + Ск ,2 > Ск ,2 + Ск , 2,

её значение только увеличится. Противоречие, дробная вершина и релаксационного многогранника ЯАТР^р(т, п) не является точкой максимума целевой функции. Теперь рассмотрим вариант а = — 1. Тогда для р = г имеет место

-(^ + сй) > — (сд,22 +

д,1 , г,2 < д,2 , г,1 Сг,2 + Сг,2 < Сг,2 + Сг,2 ,

д,2 . г,1 > д,1 . г,2

Построим точку V по вершине и, заменив блок г,? на блок, форма которого приведена в табл. 2.57.

Таблица 2.57. Координатный блок г, ? точки V

9,1 е е

е г, 2 е

- -

Значение е выберем меньше жГ.2}. Точка V удовлетворяет системе (2.57)-(2.60)

и принадлежит многограннику ЯАТР^р(т,п).

Оценим значение целевой функции f в точке V:

f (V) = f (и) - е ■ ^ + с. + е ■ (с9;2 + .

, 9,2 , г,1 > 9,1 , Г;2

С • Я. + Я. > Я. + Я. ,

е ' (Я.7 + Я.1 Я. Я. ) > 0, f (V) > f (и).

При переходе к точке V целевая функция уменьшается по переменным с9',1 и с['2 на

Г;2

г.

г.

е, но увеличится по с9'2 и сГ', также на е. Так как для целевой функции f выполняется

Г;1

г,.

г,.

неравенство

9,2 + г,1 > 9,1 . г,2

Я. + Я. > Я. + Я. ,

ее значение только увеличится. Противоречие, дробная вершина и релаксационного многогранника ЯАТР^р(т, п) не является точкой максимума целевой функции.

Таким образом, при любом выборе а. максимум целевой функции f (х) = стх не может быть достигнут в нецелочисленной вершине многогранника ЯАТРрр (т, п), что и требовалось доказать.

Часть 2. Теперь покажем, что имеет место первое утверждение. Рассмотрим такой вектор с, что

V? е Нга, За.,7. е {-1,1}, Уг е •

1,1 2,2 1,2 2,1 а. (Я. + Сг.) > а. (Я. + Я. ) ,

о / 1,1 , 3,24 ^ а/- 1,2 , 3,14

(Я. + . > (Я. + ЯД

2,1 3,2 2,2 3,1

7.(Я. + Я.) ^ 7.(Я. + ..

Максимум целевой функции f (х) = стх может достигаться и в нецелочисленной вершине. Однако, из доказательства случая со строгими неравенствами прямо следует, что такая вершина не может быть единственной точкой максимума целевой функции. Решением задачи оптимизации будет целая вершина релаксационного многогранника ЯАТР^р (т, п) или некоторая грань ненулевой размерности. Докажем, что эта грань обязательно содержит хотя бы одну целую вершину.

Пусть целевая функция f достигает максимума в некоторой точке и многогранника ЯАТР^р (т, п). Покажем, что можно ограничиться рассмотрением точек многогранника ЯАТР^р (т, п), у которых все координаты ж1'.1 положительны.

Очевидно, что в общем случае точка и не удовлетворяет этому условию, и в координатной матрице может найтись такой блок г,], что ж1'.1 = 0. Однако, это утверждение будет верным с точностью до переобозначения координат. Действительно, всегда можно переименовать переменные-координаты внутри одной строки или столбца из блоков. Например, изменим обозначения для координат г-го столбца координатной матрицы точки и следующим образом:

V] е Нга, Уз е N3, VI е N2 : Ж*. = х^-1.

Фактически, речь идет о перестановке столбцов в г-й строке из блоков (табл. 2.58).

Таблица 2.58. Блоки г-й строки в новых координатах

1 ,1 Ж г , . 1,2 Ж г.

2 ,1 Ж г,. 2,2 Ж г,.

3,1 3,2

/1,2 /1,1

/2,2 /2,1

/3,2 /3,1

В дальнейших рассуждениях при замене координат будем сохранять старые обозначения (Жг. = Жг.) и говорить просто о перестановке строк и столбцов внутри блоков.

Переименуем координаты (переставим строки в каждом столбце из блоков) так, чтобы в каждом блоке сумма координат по строкам убывала от первой строки к третьей:

1,1 , 1,2 \ 2,1 . 2,2 ^ 3,1 . 3,2 Ж г,. + Ж г,. — Хг,. + Жг. — Жг,. + Жг. .

Нетрудно проверить, что ограничения на целевую функцию в общем виде при этом не изменятся. Поменяются лишь значения а., в. и 7..

Если найдётся такая строка из блоков г, что первый столбец координат равен нулю:

VI- 1,1 I 2,1 , 3,1 п

V] : Ж А + Ж А + Ж А = °

то меняем местами все столбцы г-й строки из блоков. Получаем, что V] : Ж У > 0.

Предположим, что после проведенных замен найдётся такой блок координат г,], что г1,,.1 = 0. Так как

1,1 + 2,1 + 3,1 > о

Ж г. + Ж г,. + Ж г. > 0,

2,1 3,1 т-г

то как минимум одна из координат г,. и г,. положительна. Поменяв местами строки

внутри блоков ]-го столбца, можно добиться, что Ж. > 0. Однако, при этом первая координата может обнулиться в другом блоке ]-го столбца. Действительно, если

Зг, к, / : Ж 1. Ж к. Ж 3. 0,

то никакой перестановкой строк ]-го столбца нельзя добиться, чтобы Уг : Ж1 ^ > 0. Рассмотрим возможные варианты выбора номеров строк г, к,/.

1. Все три номера равны (г = к = /). Блок г,] имеет вид, приведенный в табл. 2.59, что противоречит сделанным ранее заменам.

Таблица 2.59. Блок г,координатной матрицы для варианта 1

0 -

0 -

0 -

2. Два из трёх номеров равны. Без ограничения общности положим г = к (этого можно добиться простой заменой координат в ]-м столбце). Соответствующие блоки г,и приведены в табл. 2.60.

Таблица 2.60. Блоки г,] и /,] координатной матрицы для варианта 2

0 -

0 -

- -

- -

- -

0 -

Рассмотрим блок г,:

1,1 , 2,1 , 3,1 > 0

Х г,] + Х г,] + Х г,] > 0,

1,1 = 2,1 = 0 . 3,1 > 0 Х г,] Х г,] 0 ^ Х г,] > 0-

Тогда в блоке

Более того,

3,2 = 3,1 , 3,2 > 0 хI,] X г,] + X г,] > 0-

1,1 2,1

X,] + хи >0.

Без ограничения общности положим координату х1]1 положительной. Тогда

1,2 = 1,1 + 1,2 > 0

Х г,] = х1,] + х1,] > 0-

Уточнённый вид блоков г,] и /, приведен в табл. 2.61. Для целевого вектора с

За е {-1,1}, е N

1,1 2,2 1,2 2,1 а(сЛ- + 4,0 > а(с1,;. + С2,;.).

2,2

1,2

2,1

Таблица 2.61. Блоки г,] и /, ] для варианта 2, уточнённый вид

0 1,2 Хг,3

0 -

3,1 Хг,3 -

1,1 Х 1,3 -

- -

0 3,2 Х1,3

Таблица 2.62. Блоки г,] и I,] точки V

б 1,2 Хг,3 б

0 -

3,1 Хг,3 б 3,2 , Хг,3 + б

1,1 Х1,3 -

- -

0 3,2 Х1,3

Если а3- = 1, то аналогично доказательству для строгих неравенств можно без уменьшения значения целевой функции перейти к такой точке V многогранника ЯАТР^р (т, п), что координата я^1 положительна (табл. 2.62).

Если а3- = — 1, то без уменьшения значения целевой функции можно перейти к такой точке V многогранника ЯАТРрр(т, п), что координата Х3 положительна, после чего достаточно переименовать координаты, что соответствует перестановке строк в ]-м столбце (табл. 2.63).

Таблица 2.63. Переход к точке точки V и замена координат

0 1,2 Хг,3

0 -

3,1 Хг,з -

1,1 Х 1,3 б 1,2 , Х1,3 + б

- -

б 3,2 Х 1,3 б

3,1 Хг,3 -

0 -

0 1,2 Хг,3

б 3,2 Х1,3 б

- -

1,1 Х 1,3 б 1,2 , Хи + б

3. Номера строк г, к и I не равны. Этот случай рассматривается полностью аналогично

варианту 2. Соответствующие блоки приведены в табл. 2.64.

Отметим, что в первом столбце каждого из рассматриваемых блоков стоят две ненулевых координаты, иначе вариант 3 сводится к варианту 2.

Нетрудно проверить, что без уменьшения значения целевой функции можно перейти

Таблица 2.64. Столбец з из блоков для варианта 3

0 1,2

х2'1 -

3,1 хг,.7 -

1,1 хк,.7 -

0 2,2

3,1 хк,.7 -

1,1 хи -

2,1 х и -

0 3,2 хи

к точке V, в которой после замены координат

Уг Е : х И > 0.

Таким образом, без ограничения общности, можно считать, что максимум целевой функции f (х) достигается в точке и, для которой

Уг Е Нт, V? Е N : хИ > 0.

Точку и можно представить в виде

и = 6Б + (1 — б)я,

где 0 < е < 1, б — целая вершина, у которой все хг,. = 1 и координаты q равны соответственно

х = 1,1 ^ (и) — е хЬ2Ы = 1,2 хгИ (и)

1 — е , 1 — е

х УЫ = 2,1 хгИ (и) 1 — е , хЬ2Ы = 2,2 ^ (и) 1 — е

х УЫ = 3,2 ^ (и) 1-е , х3;2Ы = 3,2 ^ (и) 1 - е

Построенная данным образом точка q принадлежит релаксационному многограннику ЯАТРрр(т,п), и её можно разложить по вершинам ЯАТРрр(т,п). Точка и представляет собой выпуклую комбинацию вершин многогранника ЯАТРрр(т,п), среди которых есть хотя бы одна целая (вершина б). Максимум рассматриваемой целевой функции f (х) достигается на грани релаксационного многогранника ЯАТРрр(т,п), содержащей целую вершину, которая является одной из точек максимума. □

2.2.5 Полиномиально разрешимые подзадачи распознавания целочисленности на 8АТР^Р(т,п)

Напомним постановку задачи распознавания целочисленности.

"у

2

1

x

1

2

3

Рис. 2.19. Дополнительные ограничения отсекают нецелочисленные грани многогранника, на которых целевая функция достигает максимума

Задача распознавания цЕлочислЕнности

УСЛОВИЕ. Заданы многогранник Р и линейная целевая функция f (х). Вопрос. Верно ли, что

достигается в целой вершине многогранника Р?

Известно, что для класса корневых полуметрических многогранников задача распознавания целочисленности полиномиально разрешима (утверждение 2.1.18). Этот факт был установлен Бондаренко и Урываевым в работе [40; 277], там же был впервые описан релаксационный многогранник задачи 3-выполнимость, как более общий многогранник, для которого свойство полиномиальной разрешимости задачи распознавания цело-численности не сохраняется. В частности, к задаче распознавания целочисленности на многограннике ЯАТРрр (т, п) сводятся задачи 3-выполнимость при различных литералах и 3-выполнимость при одном истинном литерале (см. раздел 2.2.2). Таким образом, задача распознавания целочисленности полиномиально разрешима для грани многогранника ЯАТР^р (т, п), но на всём многограннике является КР-полной.

Отметим, что для целевых функций, удовлетворяющих теореме 2.2.11, задача распознавания целочисленности вырождена. Действительно, по условию теоремы всегда найдётся целая вершина многогранника ЯАТР^р (т, п), в которой функция достигает максимума. Однако, теорема 2.2.11 обладает одним существенным недостатком, а именно: ограничения накладываются на все переменные целевой функции. В работе [303] были сформулированы более гибкие ограничения на целевые векторы для эффективного решения задачи распознавания целочисленности.

Идея заключается в том, что мы умеем отсекать некоторые нецелочисленные грани релаксации ЯАТРрр, и знаем линейные целевые функции, которые достигают максимума или в целой точке или на этих гранях (см. рис. 2.19).

шах^(х) | х € Р}

Рассмотрим вектор с Е М6тга, такой что

У? Е Нга, За, Ь Е {1, 2, 3} (а = Ь), Уг Е :

Я.1 + Я'2 = Я. + Я^, (2.74)

и соответствующую линейную целевую функцию

/с (х) = сТ х.

Теорема 2.2.12. Для целевых функций вида /с(х) задача распознавания целочисленно-сти на релаксационном многограннике ЯАТРрр (т, п) полиномиально разрешима.

Доказательство. Без ограничения общности, будем считать, что вектор с имеет следующий вид

: я.1 + я'.2 = я.2 +я.1. (2.75)

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

Чтобы освободить место для надстрочных индексов, введем новое обозначение координат многогранника ЯАТРрр (т, п):

1,1 = Х г,., 1,2 = Уг,., 2,1

2,2 — ¿г,., 3,1 - , 3,2 =

Построим новый многогранник ЯАТР|Р(т, п), удовлетворяющий системе (2.57)-(2.60) и дополнительным ограничениям

+ V , г + Хк + ¿к + ^ + Хк ' I + ¿к ' г + ^ , г < 3, (2.76)

Уг,. + ^ + Иг,. + + + «¿,1 + Хк,. + У;,.,- + + + + < 3, (2.77)

для всех г, к Е (г = к) и I Е N (? = /).

Все целочисленные векторы ЯАТР(т,п) удовлетворяют неравенствам (2.76)-(2.77), следовательно,

ЯАТР|Р (т,п) также является релаксацией многогранника ЯАТР(т,п). Отметим, что общее число дополнительных ограничений не превосходит 0(т2п2). Пусть целевая функция /с(х) достигает максимума на

ЯАТР|Р (т,п) в некоторой точке w. Покажем, что в таком случае найдётся точка '* Е ЯАТР^р(т,п), для которой

/с(') = /с('*) и Уг,? : х™ > 0,

с точностью до переименования координат. Другими словами, мы хотим доказать, что максимум линейной целевой функции на многограннике достигается в точке, для которой в каждом блоке координаты положительны.

Построим точку '* по точке ' за несколько последовательных итераций.

Таблица 2.65. Перестановка столбцов в г-й строке из блоков на шаге 1

0 У? 0 уг,1

0 у? уг,3 0 Ъг,1

0 V? 1,3 0 V?

Хг,3 = У?3 0 X?* хг,1 = У? = уг,1 0

гг,3 у? = Уг,3 0 ~и>* гг,1 ? = Ъг,1 0

и?,3 — V? г,з 0 и?* = vWl 0

1. Если найдётся такая строка из блоков г, что

^3 • + г1,з + и1,з 0,

тогда построим точку w*, поменяв местами столбцы во всех блоках г-й строки (таблица 2.65).

Как следствие симметрии системы (2.57)-(2.60), (2.76), (2.77) и ограничений на целевой вектор (2.75), построенная таким образом точка принадлежит многограннику ЯАТР |Р (т,п) и имеет то же значение целевой функции. Действительно, мы просто переименовали некоторые координаты.

Так как значения целевой функции /с^*) и /с^) совпадают, переобозначим новую точку w* как w и продолжим процедуру. Теперь, по построению,

Уг,з • X] + г? + К>,3 > 0.

2. Если найдётся такой столбец из блоков 3, что

г? + ^ = 0 и и?] + VI > 0,

тогда построим точку w*, поменяв местами вторую и третью строки во всех блоках 3-го столбца (табл. 2.66).

Таблица 2.66. Перестановка строк в 3-м столбце из блоков на шаге 2

- -

0 0

и?,з V? г,з

- -

0 0

и'к,з о,?

- -

— и? г,3 г,3 у?* — vш г,3 г,3

0 0

- -

к,з к,з у?* - ук,з = ик,з

0 0

Вновь, построенная таким образом точка w* принадлежит многограннику ЯАТР|Р(т, п) и имеет то же значение целевой функции /с = /c(w). Переобозначим w* как w и продолжим процедуру. Теперь, по построению,

Уг,з • г? + > 0.

3. Предположим, что найдётся такой столбец из блоков ], что

хг,2 + у2,2 0

По результатам шагов 1 и 2, для точки w имеет место

Уг : г' + ^ > 0, г' + п' > 0.

Следовательно, если для некоторого г. = 0, то > 0 и п^ > 0.

Построим новую точку w*, как показано в табл. 2.67. Назовём эту операцию е-процедурои.

Таблица 2.67. Построение блока г,] точки w* на шаге 3 (е-процедура)

- -

0 42

пг,2 г' 2,2

0 0

г'* = е /Ш* = /Ш _ е 2,2 2,2

<* = <2 - е 2 г' + е

Так как координаты и п™^ строго положительны, а координата г^ < 1, мы можем выбрать достаточно маленькое положительное значение е, при котором точка w* не нарушает ограничений системы (2.57)-(2.60), (2.76), (2.77) и принадлежит многограннику ЯАТР|Р (ш,и).

Оценим значение целевой функции:

г / *\ с / \ , 2,1 , 3 , 2 2 , 2 3 ,1 /с^ ) = /c(w) + еЯ,,- + еС32 - ^ -

( / N. / 2,1 , 3,2 2,2 3,1\

= ЛЫ + е(сг,2 + Я2 - Сг,2 - Сг,2 )

= /c(w),

по условию (2.75) на координаты целевого вектора. Теперь, без ограничения общности, положим, что г™ > 0.

Поменяем местами строки во всех блоках ^-го столбца, как показано в табл. 2.68. Таблица 2.68. Перестановка строк в ]-м столбце из блоков на шаге 3

0 0

г2,2 12,2

п2,2 2,2

ХШ* _ Х г2,2 у = ¿2,2

г'* = п' +'* — 1 = г2,2

0 0

По построению, в ^'-м столбце из блоков все координаты ж™2- строго положительны. Без ограничения общности, будем считать, что шаг 3 был применён к первым d столбцам из блоков.

Здесь нужно действовать очень аккуратно. Если просто поменять строки в ]-м столбце из блоков таким образом, то точка w * может не принадлежать многограннику

ЯАТР|Р (т,п) или иметь отличное от w значение целевой функции. Поэтому, мы просто переобозначим координаты в первых й столбцах из блоков точки w и, соответственно, в целевом векторе (2.75) и ограничениях (2.76)-(2.77).

Строго говоря, мы построили такую точку w, что в одних столбцах из блоков

Хъ,3 + уг,з > 0,

а в других столбцах (без ограничения общности, первых й столбцах)

гъ,3 + Уъ,3 >

Однако, для упрощения дальнейших построений, мы переобозначили координаты таким образом, чтобы в каждом столбце из блоков именно первая строка была положительной.

4. Найдём самый левый и самый верхний блок г, 3, для которого х?* — 0. По построению, координата у?] строго положительна. При этом, если гЦ* — 0, то обе координаты У?* и и?з строго положительны. Следовательно, мы может повторить е-процедуру из шага 3 (табл. 2.67) и построить точку w*, для которой г?* > 0.

Далее идея заключается в том, чтобы построить точку w* с тем же значением целевой функции, что и w, сохраняя положительные координаты х слева и сверху от блока г, 3.

5. Следующий шаг зависит от формы г-й строки из блоков.

(a) Если для всех I < 3 • у?* > 0, то мы поменяем столбцы в блоках г-й строки как на шаге 1 (табл. 2.65). В результате получим х?* > 0 для всех I < 3.

(b) Предположим, что найдётся такой столбец из блоков I (й < I < 3), что у— 0. Тогда хстрого положительна, и если У?* — 0, то обе координаты г'!?* и у?* строго положительны. В таком случае, мы можем построить точку w*, для которой У?* > 0, и значение целевой функции не меняется, по схеме аналогичной е-процедуре из таблицы 2.67. Таким образом, без ограничения общности положим, что для точки w координата У?* строго положительна (табл. 2.69).

(c) Предположим, что найдётся такой столбец из блоков в (в < й < 3), что у?,, — 0. Так как в < й, то координаты в в-м столбце были переименованы на шаге 3. Следовательно, если координата У?8 > 0, то мы можем, применяя е-процедуру (табл. 2.67) на переименованных координатах, построить такую точку w* многогранника ЯАТР|р(т, п), что у?* > 0. Таким образом, без ограничения общности, положим — 0, откуда координаты г"!?* и vfs строго положительны (табл. 2.69).

6. Теперь рассмотрим 3 -й столбец из блоков.

Таблица 2.69. Фрагмент блочной матрицы точки w

xi,s 0 xi,i 0 0 Vi,j

zi,s 0 - ti,i zi,j -

- Vi,s - - - -

xk,s - xk,i - xk,j -

- - - - 0 tk,j

- - - - 0 -

(a) Если для всех строк k: z'Wj > 0, то переставим строки в блоках j-го столбца также как на шаге 3 (табл. 2.68). В результате получим, что координата xfj > 0 по всем строкам j-го столбца из блоков. Затем переименовываем координаты таким образом, чтобы j-й столбец стал (d + 1)-м столбцом, и увеличим значение d на единицу.

(b) Предположим, что найдётся такая строка k, что координата zWj = 0. Тогда координата tWj строго положительна, так как zi¡"j > 0. Без ограничения общности, положим uWj = 0 (табл. 2.69). В противном случае, по е-процедуре (табл. 2.67) можно не изменяя значения целевой функции построить точку w *, для которой координата z^j строго положительна.

Для точки w из табл. 2.69 мы не сможем построить соответствующую точку w *, для которой координата x™j строго положительна.

Проверим, принадлежит ли точка w многограннику SATP^p(m,n), подставив её координаты в неравенство (2.76):

(*) = Vi, j + zi, j + Ui , j + Xi , i + ti, i + Vi ,1 + + xk,j + tk,j + vk,j + xk,i + tk,1 + vk,i < 3, (Vi ,j = xk,j + Vk,j, xk,j + Vk,j + tk,j + Vk,j = 1), (*) = 1 + zi,j + Ui,j + xi,i + ti,i + Vi,i + xk,j + xk,l + tk,l + Vk,l < 3,

(zi,j + Ui,j = xi,i + zi,i + Ui,j, xi,i + zi,i + ti,i + Ui,i + Vi,i = 1), (*) = 2 + xi,i + xk,j + xk,i + tk,i + Vk,i < 3, (xi,l = xk,l + Vk,l, xk,j = xk,l + zk,l + Uk,l, xk,l + Vk,l + zk,l + tk,l + Uk,l + Vk,l =1), (*) = 3 + 2xk,i < 3.

По построению, для всех столбцов из блоков I < j координата x'Wi строго положительна. Следовательно, точка w с такими блоками i,j,k,l не может принадлежать многограннику SATP|P(m, n).

Теперь проверим неравенство (2.77) для блоков i,j, k, s. Отметим, что s < d, и s-

й столбец из блоков был модифицирован на шаге 3. Следовательно, неравенство примет вид:

(**) — + ¿¿3 + «¿,3 + + + +

+ Хк,з + Ьк,3 + Ук,3 + Хк,. + гк,з + ^к,. < 3 (Уг,з — Хк,з + Ук,3, Хк,] + Ук,3 + tk,j + — 1), (**) — 1 + ¿¿,3 + Пъз + Хг,8 + + У^ + Хк,3 + Хк,8 + ¿к,. + ^к,. < 3

(г^г,8 + + ^¿,3, У%3 + ¿¿3 + + «¿3 + ^¿,3 1),

(**) — 2 + Х*,. + + Хк,3 + Хк,5 + ¿к,. + Ук,8 < 3

(х1,з Хк,в + yk,s, 5 ^к,« + Ьк,в1 Хк,3 Хк,в + ^к,« + ик,в1

Хк,8 + У к,. + ¿к,. + Ьк,5 + «к,. + — 1), (**) — 3 + 2(хк,. + ¿к,.) < 3.

Поскольку . > 0, точка w с такими блоками г], к, в не принадлежит многограннику ЯАТР |Р (т,п).

Следовательно, комбинация 5 (5Ь или 5с) и 6Ь невозможна, и мы можем повторять шаги 4-6, пока для всех г,] не получим х™ ^ > 0.

Таким образом, для любой точки w, максимизирующей целевую функцию /с(х) на многограннике ЯАТР|Р (т,п), можно построить такую точку w* Е ЯАТР|р (т,п), что х™ ^ > 0 для всех г,], вплоть до переименования координат, и /с— /с^*). Точка w* может быть разложена в выпуклую комбинацию

w* — ея + (1 — б)Ь,

где 0 < б < 1, я — целочисленная вершина ЯАТР^Р(т,п) с х1 — 1 для всех г,], а точка

Уг 3 ^ 1 — б , (w*) 1 — б ,

Чз ^ 1 — б .

Точка Ь удовлетворяет системе (2.57)-(2.60), следовательно, я и Ь принадлежат многограннику ЯАТР^Р (т,п).

Алгоритм для задачи распознавания целочисленности на многограннике ЯАТР^р (т, п) аналогичен алгоритму для корневого полуметрического многогранника (утверждение 2.1.18)

Ь имеет следующие координаты:

ху (Ь) — Х" <"*) — б, Уь3(Ь)

¿¿3 (Ь) — * ^ , (Ь)

из(Ь) — , 1 — б (Ь)

если

тах /с (х) > тах /с(х),

х€8ЛТРЬр (т,п) х€8ЛТР^р (т,п)

то максимум достигается на нецелочисленной грани SATPpp(m,n), так как многогранники SATPlp(m, n) и SATPLp (m, n) имеют одинаковый набор целых вершин, и задача распознавания целочисленного имеет ответ «нет»;

• если

max fc (x) = max fc(x),