Алгебраический подход в целочисленном программировании тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

^ Л*.

АКАДЕМИЯ НАУК СССР /¿<3

ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи ШЕВЧЕНКО Валерий Николаевич

УДК 519.8

АЛГЕБРАИЧЕСКИЙ ПОДХОД В ЦЕЛОЧИСЛЕННОМ ПРОГРАММИРОВАНИИ

Специальность 01.01.09 - Математическая кибернетика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1988

Работа выполнена в Горьковском ордена Трудового Красного Знамени Государственном университете им. Н.И.Лобачевского

Официальные оппоненты: академик АН БССР, доктор физико-математических наук, профессор Д.А.СУПРУНЕНКО доктор физико-математических наук, профессор В.К.ЛЕОНТЬЕВ доктор физико-математических наук, профессор Н.З.ШЭР

Ведущая организация - Институт математики СО АН СССР

(г.Новосибирск)

Защита диссертации состоится "_"_ 198_г.

в _часов на заседании специализированного совета Д002.32.02

по присуждению учекой степени доктора физико-математических: гаук при Вычислительном центре АН СССР (117967, Москва, ул. Вавилова, 40, конференц-зал).

С диссертацией можно ознакомиться в библиотеке Математического института Академии наук СССР.

Автореферат разослан "_"_ 198_г.

Ученый секретарь специализированного совета канд.физ,-матем.наук

^/¿¿-и-г- С.М.Швартин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы. Основной предмет исследования в пред-мой работе - множество М целочисленных решений

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

Расширение области применения дискретного программирования опирается на активно разрабатываемое в Москве, Киеве, Ыинске, Ленинграде и других научных центрах соответствующее программное обеспечение, среди которого прежде всего необходимо назвать созданные в ИК АН УССР пакеты программ ДИСПРО и ВЕКТОР.

Методы точного решения задачи целочисленного линейного программирования ( ЗЦЛП ) распадаются на два класса: метода отсечений, развившиеся из работ Р.Гомори, и комбинаторные алгоритмы, связанные с перебором и анализом вариантов (последовательный анализ вариантов В.С.Михалевича и его развитие, проделанное в работах И.В.Сергиенко и их коллег; метод построения последовательности планов В.А. Емеличева; динамическое программирование; метод ветвей и границ и его варианты и др.).

Наличие большого числа различных алгоритмов ставит весьма сложную проблему их сравнения по различным критериям, важнейшим из которых является трудоемкость. В настоящее время интенсивно развивается подход к решению этой проблемы, использующий теорию сложности вычислений (С.Кук, Р.Карп, А.А.Левин, Л.Г.Хачиян, Х.Ленстра, Л.Ловас и др.).

При этом рассматриваются классы Р и Л/Р задач, которые можно решить с полиномиальной трудоемкостью на детерминированной и недетерминированной машинах Тьюринга соответственно. Оказалось, что класс А/Р содержит так называемые универсальные или Д/Р - полные задачи, к которым полиномиально сводятся все задачи из класса МР • Изложение затронутых здесь вопросов, соответствующие определения, а также весьма обширный перечень - полных задач можно

посмотреть, например, в монографии Л.Гэри и Д.Джонсона "Вычислительные машины итруднорешаемые задачи" 1982).

Болшинство специалистов считают, что РФ-МР и, следовательно, ни для одной универсальной задачи не существует полиномиального алгоритма ( хотя это и не доказано). По -видимому, впервые такая гипотеза (для задачи синтеза минимальной контактной схемы ) была высказана С.В.Яблонским.

Один из подходов в такой ситуации дают локальные алгоритмы Ю.И.Журавлева, в которых трудоемкость ограничивается некоторой величиной (связанной с порядком локальной окрестности), и среди таких алгоритмов ищется оптимальный. Сначала локальные алгоритмы применялись для построения минимальной дизъюнктивной нормальной формы (также ¡\/Р - полной задачи). Оказалось, однако, что этот путь не избавляет от экспоненциального перебора. Таким образом, локальные алгоритмы с полиномиальной трудоемкостью могут дать лишь приближенное решение, но зато с наилучшей оценкой приближения (сюда хе можно отнести работы Н.И.Глебова, М.М.Ковалева и др., посвященные анализу градиентных алгоритмов).

- 3 -

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

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

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

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

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

- выявлены условия, при которых множество не -отрицательных целочисленных решений системы Л1 линейных диофантовых уравнений можно описать одним диофантовым уравнением ( агрегирующим эту систему ) и построен класс таких систем, для которых коэффиценты любого агрегирующего уравнения растут как экспоненты от (У\ ;

- предложена общая схема построения правильных отсечений в целочисленном программировании, позволившая проанализировать существующие алгоритмы и разработать новые;

- предложен метод получения верхних оценок числа крайних точек выпуклой оболочки множества М при различных способах его задания, доказано, что в ряде важных частных случаев получаемые при этом оценки не улучшаемы по порядку;

- предложен алгоритм, описывающий множество М перечислением всех его крайних точек и граней, трудоемкость которого при любой фиксированной размерности имеет вид полинома от

- выделены новые подклассы задач целочисленного линейного программирования, имеющие полиномиальные алгоритмы.

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

Внедрение.

С 1976 года по настоящее время под научным руковод-

- 5 -

ством автора ведутся хоздоговорные работы, по которым зарегистрировано 4 отчета. Получен "Акт использования результатов научно-исследовательской работы в народном хозяйстве" о фактическом экономическом эффекте на 19434 руб.

По некоторым из методов, полученных в диссертации, под руководством автора составлены программы. Одна из них принята в Госфонд алгоритмов и программ: Шевчук А.И., Программная реализация одной модификации алгоритма Гоморн ( № гос.регистрации П 005842).

Материалы диссертации вошли в спецкурс "Дискретное программирование", разработанные и читаемый с 1970 года автором на факультете вычислительной математики и кибернетики Горьковского государственного университета. По ним издан в ГГУ цикл пособий 33 - 36 , использовавшихся также в Белорусском госуниверситете и Запорожском пединституте.

Апробация работы л публикации. По теме диссертации опубликовано более 40 печатных работ. Результаты, изложенные в диссертации, докладывались на Ш,1У,У Всесоюзных конференциях по теоретической кибернетике ( Новосибирск, 1974г., 1977г., 1980г.), на Ш Всесоюзной конференции по исследованию операций (Горький,1978г.), на П Всесоюзном симпозиуме по теории полугрупп (Свердловск, 1978г.), на У Всесоюзном семинаре по комбинаторике (Москва, МГУ,1981г.), на У Республиканской конференции математиков Белоруссии (Гродно,1980г.), на I Крымской весенней школе по дискретной оптимизации (Судак,1982г.), на П Республиканской школе-семинаре по дискретной оптимизации (Ужгород,1983г.), на

- 6 -

П Всесоюзной школе-семинаре "Дискретная оптимизация и её приложения" (Кишинев, 1983г.), на Всесоюзном семинаре по дискретной математике и её приложениям (Москва, МГУ,. 1984г.), на Республиканском семинаре по дискретной оптимизации (Ужгород, 1986г.), на научных семинарах ВЦ АН СССР, ИМ АН ЕССР, ИК АН УССР, ИМ СОАН СССР, ИММ УрНЦ и др.

Структура работы. Диссертация состоит из введения, пяти глав, содержащих 22 параграфа и двух приложений, изложенных на 225 страницах машинописного текста, включающих в себя один рисунок, 24 страницы приложений и 26 страниц списка цитированной литературы из 256 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В работе используются следующие обозначения . О- - поле рациональных чисел, Н" - кольцо целых чисел, )( ^ - подмножество неотрицательных чисел множества X « - множество /I - мерных векторов с компонентами из X » <Х/Я*/? - множество матриц с /? столбцами, принадлежащими множеству X ^ > /X / - мощность множества

X » & 1 - наибольшее целое число, не превосходящее . При ¿¿1 запись х® У

означает, что каждая компонента вектора X~У делится на с1 \ под ^ понимается .

Введение содержит обоснование актуальности направлений исследований, представленных в диссертации, цели исследований, краткое изложение основных результатов работы.

- 7 -

В первой главе рассматривается пересечение выпуклого многогранного конуса с подрешеткой Л целочисленной решетки ¿£

Рассмотрим систему

А ~ £ (I)

( 3 )

7 /я •—'я*"

где 0 £ ¿Г и Лё Л- , и порожденные столбцами матрицы Л конус ¡{(А) р {Ж*, 0 + $ , подрешетку /, (А) {Ь, * €I'П] и полугруппу 1-й] ЧА Л<£

Поставим следующий вопрос; каким условиям должен удовлетворять вектор ё , чтобы система (I) - (3) имела решение?

Поскольку

КШАйМ • (4)

то необходимые условия можно получить из того, что

ёеШ

- они имеют вид сравнений - и из того, что

- это линейные неравенства, получающиеся из векторов, порождающих конус УЙ^О , сопряженный к К [/¡) Если (4) обращается в равенство - ряд таких случаев приведен в теореме 1.1 -, то эти условия являются и достаточными .

В теореме 1.2 известный результат Д.Гильберта о конечной порожденное™ полугруппы

Лх - 0}

переносится на полугруппу

Г'-КШОи «где Л

произвольная подрешетка

г , содержащая ш .

- В -

В частности вопрос о выполнении равенства в ( 4 ) сводится (следствие 1.3) к проверке совместности конечного числа систем ( I ) - ( 3 ). Совместно с Н.Н.Ивановым показано, что для единственности неприводимого порождающего полугруппу Г множества Д необходимо и достаточно, чтобы конус ({ {/¡) был острым, то есть не содержал ненулевого подпространства. В случае, когда матрица А квадратная, Л= \htj\l У 0 и , показано, что /¡'

содержится среди векторов вида^^/л , где А г ~ Лй) I) - /... /л)

или 3 ~ , ¿т) удовлетворяет условиям

.Аг^ОСь), (5). А т), ( 6 )

Е (7)

« получены неулучшаемые верхние оценки числа векторов в

У) и их компонент.

В § 1.2 рассмотрена используемая в методах отсечений задача разбиения конуса К (4) на элементарные (т.е. такие конусы, у которых определитель порождающей матрицу равен - / ) и доказано, что для каждой матрицы У?

т 2. ^ ранга (А-^Ь (общий случай легко сводится к этому) найдутся такие унимодулярные матрицы

.что .в

случае

квадратной невырожденной матрицы А в процессе разбиения используются решения системы (5) - (7), приводящие к дереву, в котором вершина /\ -го яруса, соответствующая Д , еоединена с вершинами 1) - го яруса, соответст-

- 9 -

вуицими ненулевым значениям г?£ (\ ~ 1, ■ ■ •, /7-7) . Возникающий при этом вопрос о возможном росте элементов матриц

( в методах отсечений это коэффициенты строящихся неравенств- отсечений) решен построением примера, показывающего его экспоненциальность от Л

Если же е системе (5)-(7) условие (б) заменить условием

(/=/,...се)

то (А) представляется в виде перечечения объединений

или объединения пересечений ) не более, чем/Т)'^элементарных конусов, при этом абсолютная величина любого элемента матрицы не превосходит Д

В 5 1.3 доказано (совместно с Н.Н.Ивановым) , что абстрактная полугруппа изоморфна /"(/?) тогда и

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

В 5 1.4 для нескольких прикладных задач найдены необходимые и достаточные условия совместности системы (I). -(3), результаты одной из них, полученные совместно с В.А.Талановым, внедрены. Кроме того, совместно с Н.Н.Инановыы показано существование такого $ , при котором выполняется включение, в некотором смысле противоположное к (4):

Другой подход к описанию множества

решений системы (I) - (3) и определению её совместности проводится во второй главе.

Одному из классических результатов теории линейных

- 10 -

неравенств-теореме Фаркаша- можно придать следующий вид: система (I) совместна в О ^ тогда и только тогда, когда любая линейная комбинация уравнений этой системы имеет решение в б" . Оказалось, что это утверкдение можно

п

распространить и на случаи + , если дополнительно предположить остроту конуса К (А) , т.е. имеет место доказанный в § 2.1 дискретный аналог теоремы Фаркаша: если конус К (/}) - сстрый, то 8Рй) тогда и только тогда, когда для всякого справедливо включение

\JLle Р(иА)

. Существенность предположения об остроте [\(/1) подтверждена построением соответствующих примеров.

«

Близка к этому так называемая проблема агрегации, заключающаяся в нахождении такого линейного диофантова уравнения (называемого агрегирующим), множество неотрицательных целочисленных решений которого совпадает с множеством 771 (/!,$) . В § 2.2. показано, что а) если

¡/\[/}) - острый, то агрегирующее уравнение существует, б) если ¡*\{/)) - не острый, ранг А не меньше X и

тОМ)* 0

, то агрегирующего уравнения не существует. Все известные способы агрегации приводят к экспоненциальному от /71 росту коэффициентов агрегирующею уравения. В § 2.3 показана закономерность этого явления: для любых натуральных с/ и /77 построен класс таких систем ( I ), для которых любое агрегирующее уравнение имеет ¡И коэффициентов, не меньших, чем с[т . Это построение опирается на следующий результат: если урав-

п

п

ненией Л-о имеет в единственное реше-

)-1

ние ¡г - Г//,. - ■, рп ) » то все его коэффициенты

имеют одинаковый знак и /й-;/^ /7 (¡^ + 4) •; Л )

Центральным в диссертации является исследование пересечения выпуклого многогранного множества с целочисленной решеткой (глава 3). Из результатов М.Пресбургера о разрешимости арифметических систем следует существование таких конечных множеств &0 к Сг/ » 470 каждый / из

1П (й) ё) можно представить в параметрическом виде

Х = (8)

где и •

Н.Н.Иванов ( Иванов Н.Н. Целые точки выпуклых многогранных множеств: Автореферат дис.канд.физ.-мат.наук. Минск,ИМ АН БССР. 1976, 8с.) вывел это утверждение из теоремы 1.2, дав тем самым удобную конструкцию для построения множеств 0С и и возможность оценки их элементов.

При уточнении этого пути в § 3.1 получается оценка У -и компоненты вектора А из :

Г/Ч- о)

где 1-1^.11 , а с{ - максимум из модулей коэффициентов системы (I) - (3), являющаяся наилучшей из известных оценок такого рода.

Обозначим через ?1 (А,ь) множество крайних точек выпуклой оболочки множества (Я, &) • Доказано, что

1% и • следовательно, для каждой крайней точки

справедлива оценка (9).

- 12 -

Оказалось, что на множестве (Л, ¿>] выполняется следующее свойство разделенности: множество ТС $) не содержит двух таких различных точек и ^ , для которых [I у .

Оно играет ключевую роль при получении верхних оценок числа \Т1 (Л (>)1 крайних точек, поскольку имеет место следующий результат комбинаторного характера: если множество 01 обладает свойством разделенности и рляД-'^о" )^*)

из (X выполняются условия <5 {О, 1,. ■ ч А ] - 1}

А _

04--, я), то /7+

Отсюда и из неравенства (9) вытекает, что

¿о^тЩМ!"'* < 10 )

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

не превосходит

Если же система задана в виде

( и )

то для существования крайних точек необходимо и достаточно

и чтобы

% - Л .В этом случае число её крайних точек можно оценить величиной

Эта оценка существенно упрощается, если Л - квадратная матрица и

А \tUtA\7 0

. Систему (II) в этом случае

- 13 -

будем называть крамеровской. Рассмотрим аддитивную абеле-ву группу порядка А , её элементы )$1 > • ■ i1-} п и линейное уравнение на G

+ ' < + ( 12) .

Известно ( Gomory R. Е. On the relation between integer and non-integer solutions to linear programs. -

Proo. Hat. Acad. Sei. USA, 1965 , 53,»2 , 260-265),

как по крамеровской системе неравенств получить уравнение (12), равносильное ей в том смысле, что множество её целочисленных решений взаимно однозначно отображается на множество М (Л) неотрицательных целочисленных решений группового уравнения (12) с сохранением структуры крайних точек. Относительно обратного перехода в § 3.3 показано, что для этого необходимо и достаточно, чтобы множество элементов ,„ ^ порождало группу Cr Поскольку множество крайних точек множества Ц(А)

также обладает свойством раэделенности, то справедлива оценка

< 13)

откуда, в частности, следует, что число граней в выпуклой оболочке множества /V) (А) ограничено сверху многочленом от (Zotj, А степени /?(п - !)/£ (аналогично оценивается число граней в выпуклой оболочке множества ffl (/\ ^ ).

Упрощение соответствующей оценки сделано и для задачи о рюкзаке ( § 3.4 ), заключающейся в максимизации линейной функции СХ-C,)(ft-i С * А и на множестве

решений системы Я/Х/ - + М* ^ 0

- 14 -

где - натуральное числоth) . Пусть/V/й^-

множество крайних точек выпуклой оболочки множества ) и й = {Рц--, й>„] .Тогда

¡Ы(С1,ё)1^17 ri+&>ffft£/*jll ( 14 >

Можно дать оценку , не зависящую от $ , по-

скольку при 1) т^М^ЬпГи^У'

Упорядочим переменные так, чтобы выполнялись неравенства

и положим fftb

JVQt {Cf, ХбМ(й,#)} . Известно (Gilmore P.,

Gomory R. The theory computation of knapsack functions.JORSA,

1966, 146, . 1045-1074) что при достаточно больших значениях о - например, при

/ > с / a, tit KWLCA ,)

- фуккция является периодической.

Здесь дается граница периодичности, не зависящая от £ :

если » то ^ (Stflj) - (j. ($) . Отсюда следует,

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

По поводу достижимости верхних оценок числа крайних точек в § 3.5 построены примеры таких задач, в которых числа If/fCi^)! и Ш(&)! растут как " . Здесь же рассмотрено влияние роста порядка Д группы Сг на возможное число крайних точек

. При/7=^ обозначим через наименьшее Л , при котором найдется груп-

повое уравнение (12) такое, что

Совместно с

С.И.Веселовым показано, что &i = i} 1 ^^s-i

fS-Л, з •.< ) .и построен пример, в котором

. Наконец, С.И.Веселов, оценив снизу среднее число крайних точек, показал, что оценка (13) не улучшаема в следующем смысле: не существует такого многочлена //00 , степени которого меньше , что

á) • Аналогичный результат получен им и для задачи о рюкзаке.

Полученные в первой главе результаты о разбиении .сонуса на элементарные позволили с единой точки зрения проанализировать существующие методы отсечения в целочисленном программировании и предложить новые (глава 4 ). Выявлена роль элементарной ЗЦЛП ( в которой множество ограничений - крамеровская система неравенств), эквивалентной, как показано в § 3.3, введенной Р.Гомори задаче групповой минимизации СЗГМ) , заключающейся в минимизации некоторой линейной функции на множестве

MÍA) . Эта эквивалентность позволяет переносить методы решения каждой из них на другую и дает два естественных параметра Л и , по которым их можно сравнивать. Ориентиром здесь является основанный на динамическом программировании алгоритм, предложенный Р.Гомори для решения ЗГМ с трудоемкостью, пропорциональной Л Л .в диссертации получено несколько новых алгоритмов отсечений, в частности предложена модификация полностью целочисленного алгоритма Р.Гомори, позволяющая использовать информацию об оптимальном плане непрерывной задачи линейного программирования. На кафедре выполнена программная реализация этой модификации.

Стремление избавится от коэффициента А , появляющегося в оценках трудоемкости, привело ещё к одному алго-

- 16 -

ритму, сочетающему отсечения с методем ветвей и границ. При этом ЗЦЛП может разветвляться на две, но длина каждой ветви, приводящей к двойственно допустимой унимодуляр-ной базе, не превосходи» ¿OQ Л . Прй1енение этой идеи при позволило получить (совместно с С.И.Веселовым)

полиномиальный алгоритм, перечисляпдий множество NÍA) , который удалось использовать при выполнении хоздоговорной работы.

В связи с оценками трудоемкости методов решения элементарной ЗЦЛП важно исследовать средние значения миноров различных классов матриц, что представляет и самостоятельный интерес. В § 4.4. приводится методика, с использованием которой показано (совместно с А.П.Ильичевым и Ы.А.Рощиной), что средняя величина определителя П - го порядка из нулей и едлниц растет как экспоненте от /2 . Для (0,1) - определителей, содержащих ]С единиц в каждом столбце, аналогичный результат получен при К> 55 , показано также, что средняя величина квадрата такого определителя растет как экспонента от /1 при и стремится к нулю при

В главе 5 рассматриваются вопросы теории слсхности, связанные с ЗЦЛП. Доказано, что задача J у проверки совместности системы (I)- (3) является ЫР - полной задачей даже при /7) ~ 1 . Это позволяет в частности выбирать её в качестве тестовой при сравнении методов целочисленного программирования. Отсюда следует

ЫР

- полнота задачи о

рюкзаке, ЗГМ и элементарной ЗЦЛП. Доказано также, что проверка совместности в ¿ системы из /) неравенств от

/7 переменных является fi/P - пэлной задачей, тогда как имеется полиномиальный алгоритм нахождения целочисленного

- 17 -

решения крамеровской системы неравенств.

В ЗЦЛП оказалось полезным рассматривать трудоемкость как функцию двух параметров: и Я • М.Гэри и Д.Джонсон ввели понятие псевдополиномиального алгоритма, трудоемкость которого ограничена полиномом от ^ и /I Они показали, что динамическое программирование дае'.'

Т>

псевдополиномиальный алгоритм для решения задачи и 1 при фиксированном числе уравнений Щ и что если Pf HP, то при произвольном fT) псевдополиномиального алгоритма не существует (такие задачи называются К'Р - полными в сильном смысле).

Естественная альтернатива псевдополиномиальности -квазиполиномиальность, тэ есть полиномиальность при фиксированном Я . Х.Ленстра предложил квазиполиномиальный алгоритм решения задачи . Отсюда и из квазиполиноми-

альности оценки (10) в диссертации получен алгоритм, дающий множество всех крайних точек и граней выпуклой оболочки множества т м, g) , также имеющей ввазиполиномиальную верхную оценку трудоемкости. Отсюда, в частности вытекает квазиполиномиальный алгоритм максимизации выпуклой ограниченной сверху на ад i) функции /00 , для которой имеется квазиполиномиальный алгоритм вычисления ffÄ) для каждого Ttf/l, £) .

Ссвместно с А.Ю.Чирковым рассмотрены две классические задачи теории чисел: - нахождение последовательных

минимумов решетки, заданной своим базисом (заметим,что

Гаусс дал полиномиальный алгоритм её решения при П-JL) , ф

и' t/j - нахождение в решетке вектора, ближайшего к данному. Показано, что обе задачи МР - полны в силь-

- 18 -

ном смысле, но для каждой из них имеется квазидолиномиаль-ный алгоритм. Более того, показано, что если рост ограничен величиной, пропорциональной , то

для задачи ~ 3) имеется полиномиальный алгоритм.

Полученные результаты в § 5.5 переносятся на функции многозначной логики , принимающие два значения

О и I. Найдены условия, при которых множества нулей и единиц функции , то есть множества М\ —

(<- ~0/ 4 ) , можно описать системой линейных неравенств, и оценивается сверху число крайних точек выпуклой оболочки множества

мм о, 1) . Получен

критерий порсговости функции $" (%) и верхняя оценка числа пороговых функций.

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

Основные выводы:

I. Получен ряд общих результатов о строении множеств целочисленных точек, задаваемых системами линейных неравенств, уравнений и сравнений. Найден дискретных аналог теоремы Фаркаша и решена проблема агрегации системы линейных диофан-товых уравнений; в обоих случаях выявлена определяющая роль предположения об остроте конуса, порожденного столбцами системы. Доказано, что линейное диофантово уравнение, имеющее единственное решение в + * должно иметь достаточно большие коэффициенты. Это позволило построить класс таких систем (I) -(3), для каждой из которых коэффициенты любого агрегирующего уравнения имеют экспоненциальную от числа

- 19 -

уравнений оценку снизу.

2. С единой точки зрения проанализированы существующие методы отсечения в целочисленном программировании

и предложены новые. Даказанная эквивалентность ЗГМ и элементарной ЗЦЛП позволяет перенести методы решения какдой из нкх на другую и дает два естественных параметра, по которым из можно сравнивать: А - порядок группы и iL - размерность. Доказана blP - полнота этих задач. Выделен новый подкласс задачи о рюкзаке, для которого существует полиномиальный алгоритм.

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

о нахождении последовательных минимумов решетки и отыскания в решетке вектора, ближайшего кданному. Совместно с A.D. Чирковым показано, что они NP

- полны в сильном смысле, но если рост П. ограничен величиной, пропорциональной

(?CCj оС , то для каждой из них и для задачи определения совместности системы (I) - (о) имеется полиномиальный алгоритм.

Основные научные результаты диссертации содержатся в следующих публикациях:

I. Шевченко В.Ь. О пересечении выпуклого многогранного конуса с целочисленной решеткой//Известия ВУЗ.Радио-

- 20 -

физика.1970.Т.13.№8.С.1264-1266,

2.Шевченко В.Н. О двойственном описании конуса.целочисленного порожденного конечным множеством векторов// Математические заметки.I973.T.I4.JP 4.С.523-526.

3.Шевченко В.Н. Построение правильных отсечений в целочисленном линейном программировании/'/Труды 5. зимней школы-симпозиума по мат.программированию и смежным вопросам .M.1973.Вып.'2.С.266-272.

4.Шевченко В.Н..Ремизова О.Л. О построении правильных отсечений в целочисленном линейном программировании//Уче-ные записки//Горьк.гос.ун-т.Горький.1973.Вып.166.С.199-206.

5.Иванов H.H..Шевченко В.Н.Строение конечно-порожденной полурешетки// Докл.АН БССР.1975.Т.Х1Х.№ 9.С.773-774.

6.Шевченко В.Н..Иванов H.H. О представлении полугруппы полугруппой, порожденной конечным множеством векторов// Известия АН БССР.Сер.физ.-мат.наук.1976.№ 2.

С.98-100.

7.Шевченко В.Н. Длакретный аналог теоремы Фаркаша

и проблема агрегации системы линейных уравнений //Кибернетика .1976. № 2.С.99-101.

8.Шевченко В.Н. О строении выпуклой оболочки множества целочисленных гешений системы линейных неравенств// 4-я Всесоюзная конференция по проблемам теоретической кибернетики. Тезисы докладов. Новосибирск.1977.С.81-82.

Э.Шевченко В.Н. Полугруппы, связанные с задачами целочисленного линейного программирования// Второй Всесоюзный симпозиум по теории полугрупп. Тезисы сообщений.

- 21 -

Свердловск. 1978.СЛOl.

10.Шевченко В.Н. Оценка крайних точек в некоторых задачах целочисленного программирования// Тезисы докладов 3-й Всесоюзной конференции по исследованию операций. Горький.1978.С.248-249.

П.Веселов С.И..Шевченко В.Н. Об экспоненциальном росте коэффициентов агрегирующего уравнения// Кибернетика. 1978.№ 4.С.78-79.

12.Шевченко В.И. Выпуклые многогранные конусы, системы сравнения и правильные отсечения в целочисленном программировании// Комбинаторно-алгоритмические методы в прикладной математике: Межвуэ.тематич.сб.науч.тр./Под ред. A.A.Марко ва.Горьк.гос.ун-т.Горький.1979.С.I09-119.

13.Шевченко В.Н. О числе крайних точек в целочисленном программировании//Кибернетика.1981.№ 2.С.133-134.

14.Шевченко В.Н. О свойстве периодичности в задаче о рюкзаке// Анализ и моделирование экономических проце-сов: Межд.тематич.сб.науч.тр./Под ред.Д.И.Батищева. Горьк.гос.ун-т.Горький.1981.С.36-38.

15.Шевченко В.Н. Задача о размене,задача Фробениу-са и задача групповой минимизации// Комбинаторно-алгебраические методы в прикладной математике:Межвуэ.тематич. сб.науч.тр./Под ред.А.А.Маркова.Горьк.гос.ун.т.Горький. 1982.С.166-179.

16.Шевченко В.Н. Алгебраический подход в целочисленном программировании//Кибернетика,1984.№ 4.С.36-41.

17.Ильичев А.П.,Рощина М.А..Шевченко В.Н. О средних значениях миноров некоторых классов булевых матриц// Тезисы докладов УП Всесоюзной конференции "Проблемы тео-

- 22 -

ретической кибернетики",часть 1.Иркутск'Л985.С.82.

18.Шевченко В.Н. О некоторых функциях многозначной логики, связанных с целочисленным программированием//Мето-ды дискретного анализа-э теории графов и схем.Новоси-бирск.1985.Вып.42.С.99-108.

19.Шевченко В.Н..Чирков А.Ю. О нахождении взктора решетки,наименее уклоняющегося от нуля// Принятие оптимальных речений в экономических системах:Межвуз.тематич.• сб.науч.тр./Под.ред.Д.И.Батищева.Горьк.гос.ун-т.Горький. 1986.С.23-28.

20.Чирков А.Ю..Шевченко В.Н. О нахождении последовательных минимумов целочисленной решетки и вектора решетки,ближайшего к данному// Кибернетика.198?.№ 4.С.46-49.

Следующие публикации отражают результаты прикладного характера:

21.Шевченко В.Н. Задача оптимального календарного планирования с ограничением на число рабочих//Извёстия ВУЗ.. Радиофизика Л965.Т.8.№ З.С. 635-637.

22.Шевченко В.Н. Задача о равномерном распределении простоев (несколько смен)// Экономика и математические методы. I967.T.3.» 4.C.6I9-623.

23.Таланов В.А..Шевченко В.Н. Об одной задаче на динамической транспортной сети//Известия ВУЗ.Радиофизика. 1972.Т.15.№ 7.C.III3-III4.

24.Шевченко В.Н. Об одной модификации третьего алгоритма Гоыори// 3 Всесоюзная конференция по проблемам теоретической кибернетики. Тезисы докладов.Новосибирск. I974.C.97-99.

25.Шевченко В.Н. О решении элементарной задачи це-

- 23 -

лочисленного линейного программирования// Управляемые системы.Но восибирск. 1975.Вып.14.С.69-73.

26.Таланов В.А .Шевченко В.Н. Об одном обобщении задачи о назначениях// Комбинаторно-алгебраические методы в прикладной математике :Межвуз.тематич.сб.науч.тр./ Под.ред.А.А.Маркова. Горьк.гос.ун-т.Горький,1979.С.101-103.

27.Смирнов А.Н..Шевченко В.Н. Алгоритм Мартина и правильные отселения// Журн.вычисл.математики и матем. физики.1980.Т.20.№ 2.С.505-509.

28.Ильичев А.П..Шевченко В.Н. 0 крайних точках многогранников транспортных задач// Комбинаторно-алгебраические методы в прикладной математике:Ме:*вуз.тематич.

сб.науч.тр./Под.ред.A.A.Марко ва.Горьк.гос.университет. Горький.1981.С.66-72.

29.Веселов С.И..Шевченко В.Н. О гранях и крайних точках задач дискретного программирования//Там же. С. 39-49.

30.Потемкина A.B..Шевченко В.Н. О построении правильных отсечений в выпуклом целочисленном программировании// Экономика и математические методы.1991.ТЛ7.№ 2. С.390-394.

31.Киселев В.Ф..Веселов С.И..Ильичев А.П..Шевченко В.Н. Об одной задаче оптимального ремонтного обслуживания радиоэлектронной аппаратуры// Техника средств связи .1983.Сер.техника радиосвязи.Вып.9.С.34-37.

32.Киселев В.Ф..Шевченко В.Н. Об оптимгльном наборе радиосредств на подвижном узле связи// Там же.С.38-41,

33.Шевченко В.Н. Линейное и целочисленное програм-

мирование: Учеб.пособие/Горьк.гос.н-т.Горький,1976.70 с.

34.Шевченко В.Н. Ликейное программирование и теория линейных неравенств:Учебн.пособие/Горьк.гос.ун-т.Горький 1977.48с.

35.Таланов В.А..Шевченко В.Н. Системы уравнений транспортного типа с приложением к комбинаторике: Учеб.посо-5ие/Горьк.гос.ун-т.Горький.1987.44с.

36.Шевченко В.Н. Множества целочисленных решений квадратной системы линейных неравенств: Учеб.пособие /Горьк.гос.ун-т. Горький.1982.24с.

Шевченко Валерий Николаевич

Алгебраический подход в целочисленном про гр а ммн ров ан н а

Т-04456. Подписано в печать 18/1-88 г. Заказ 8. Тираж 100 экз. формат бумаги 60x90 1/16. Бесплатно,

Отпечатано на ротапринтах в ВЦ АН СССР Москоа, В-ЗЗЗ, ул. Ь(Шилова, 40