Многогранники на алгебраических структурах в целочисленном линейном программировании

• Автор: Шлык, Владимир Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Минск
• Количество страниц: 119 c. : ил

Посвящается моему отцу Александру Аркадьевичу Шлыку

ГЛАВА I. МНОГОГРАННИКИ НА АЛГЕБРАИЧЕСКИХ СТРУКТУРАХ

§1. Многогранники на частичной алгебре

§2. Грани многогранников Гомори на циклической

группе

§3. Субаддитивные функции

ГЛАВА 2. СПЕЦИАЛЬНЫЕ КОМБИНАТОРНЫЕ МНОГОГРАННИКИ §4. Достаточное условие разрешимости задачи

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

§5. Многогранник путей, соединяющих две вершины

графа
§6. Многогранники метрических матриц
ЛИТЕРАТУРА

Задача целочисленного линейного программирования (ЦЛП)

ГУМ* с.х. }
J-'t J J

целые,
- одна из основных задач исследования операций. Она имеет большое практическое значение, так как является универсальной формой постановки многих оптимизационных задач дискретной математики. Вследствие своей общности задача ЩШ содержит все трудности, присущие отдельным задачам комбинаторной оптимизации. Если для задачи линейного программирования Л.Г.Хачияном [£?] доказано, что она полиномиально разрешима, то задача ЦЛП является представителем класса NP -полных проблем . Надежды на построение единого эффективного алгоритма решения любой задачи ЦЛП в настоящее время сохранились лишь у тех, кто допускает, что можно опровергнуть гипотезу Р ф NP
Задача ЦЛП является объектом изучения уже более тридцати лет. Методы решения, разработанные к середине шестидесятых годов, можно разделить на две основные группы: методы отсечений и методы ветвей и границ [ £4, 25] . В последующий период число методов и алгоритмов целочисленного линейного программирования резко возросло [ ZZ} 29? ЬО} 56, £9? /44-, • Новые методы
решения разработаны Ю.И.Журавлевым [ ] , В.А.Емеличевым
[9~i2} 1S] , В.С.Михалевичем [33,39], И.В.Сергиенко [4£]. Результаты белорусских математиков занимают достойное место в

прост с порядком группы, то есть с/ = О.Н.с/. (Л 9 <2>) — і
Это предположение основано на результатах практических вычислений - для всех известных граней многогранников Гомори на группах простого порядка оно выполняется. Если оно действительно верно, то для таких групп соотношение (12) есть просто сравнение по модулю СЭ
Теорема не исключает возможности равенства с/ = для некоторых граней. Тогда соотношение (12) является сравнением по модулю I . В.Н.Шевченко и С.В.Веселов обнаружили, что такие грани на самом деле существуют, например, грань (6; 4, 2, 2, 4, 4, 4, 3, 2, 2, 2, 4, 4, 2, 6 ) многогранника P(&1S >/>*)■ Однако у этого многогранника таких граней только 2 из
Для остальных граней с((тг) і и утверждение теоремы оказывается нетривиальным.
Если для грани (Тт ' ф) выполняется сравнение (12) по модулю , то, очевидно, для этой грани выполняется
также сравнение г-5Г. a( ftwct &') по любому основанию , делящему £ . Обозначим через $~(чг) максимальное число , для которого грань (ЧГт ; w) удовлетворяет сравнению (12) по модулю (Г . Через /~^ обозначим множество тех граней (ЧГт ; ЧГ) многогранника Р( 9
S" ■= 8~(ф) . Тогда множество всех его граней П есть объединение непересекающихся подмножеств
п = и Г,
iïz> ь
по всем делителям числа "2)
Для каждой грани, принадлежащей множеству , из условия = a (nwof) следует сравнение = Uct (мсс/S~)