Введение к работе
Актуальность темы. Основной предмет исследования в пред-
мой работе - множество г) целочисленных решений систем линейных неравенств и уравнений и его выпуклая оболочка. Такие математические объекты естественно возни-вают в целочисленном программировании, являющемся достаточно универсальным языком дискретной оптимизации, имеющей большую и все расширяющуюся сферу приложений в математической кибернетике, экономике и других областях.
Расширение области применения дискретного программирования опирается неактивно разрабатываемое в Москве, Киеве, Минске, Ленинграде и других научных центрах соответствующее программное обеспечение, среди которого прежде всего необходимо назвать созданные в ИК АН УССР пакеты программ ДИСПРО и ВЕКТОР.
Методы точного решения задачи целочисленного линейного программирования ( ЗЦЛП ) распадаются на два класса: методы отсечений, развившиеся из работ Р.Гомори, и комбинаторные алгоритмы, связанные с перебором и анализом вариантов (последовательный анализ вариантов В.СМихалевича и его развитие, проделанное в работах И.В.Сергиенко и их коллег; метод построения последовательности планов В.А. Емеличева; динамическое программирование; метод ветвей и границ и его варианты и др.).
Наличие большого числа различных алгоритмов ставит весьма сложную проблему их сравнения по различным критериям, важнейшим из которых является трудоемкость. В настоящее время интенсивно развивается подход к решению этой проблемы, использующий теорию сложности вычислений (С.Кук, Р.Карп, А.А.Левин, Л.Г.Хачиян, Х.Ленстра, Л.Ловас и др.).
- 2 -При этом рассматриваются классы г и Nг задач, которые можно решить с полиномиальной трудоемкостью на детерминированной и недетерминированной машинах Тьюринга соответственно. Оказалось, что класс Nr содержит так называемые универсальные или Д/Р - полные задачи, к которым полиномиально сводятся все задачи из класса Nr . Изложение затронутых здесь вопросов, соответствующие определения, а также весьма обширный перечень Р/Р - полных задач можно посмотреть, например, в монографии Л.Гэри и Д.Джонсона "Вычислительные машины итруднорешаемые задачи" (M.:Uup, 1982).
Болшинство специалистов считают, что рФр/г и, следовательно, ни для одной универсальной задачи не существует полиномиального алгоритма ( хотя это и не доказано). По -видимому, впервые такая гипотеза (для задачи синтеза минимальной контактной схемы ) была высказана С.В.Яблонским.
Один из подходов в такой ситуации дают локальные алгоритмы Ю.И.Журавлева, в которых трудоемкость ограничивается некоторой величиной (связанной с порядком локальной окрестности), и среди таких алгоритмов ищется оптимальный. Сначала локальные алгоритмы применялись для построения минимальной дизъюнктивной нормальной формы (также J\/Р - полной задачи). Оказалось, однако, что этот путь не избавляет от экспоненциального перебора. Таким образом, локальные алгоритмы с полиномиальной трудоемкостью могут дать лишь приближенное решение, но зато с наилучшей оценкой приближения (сюда же можно отнести работы Н.И.Глебова, М.М.Ковалева и др., посвященные анализу градиентных алгоритмов).
Итак, альтернатива точным методам-методы приближенные. Разумеется, они расширяют круг эффективно решаемых задач, если довольствоваться их приближенным решением с гарантированной оценкой приближения, однако некоторые задачи остались }/Р - полны и при такой переформулировке.
Наличие большого числа отрицательных результатов свидетельствует, по-видимому, о том, что существующий подход, при котором трудоемкость рассматривается как функция только одного параметра-длины входа, является слишком общим. В целочисленном линейном программированиии имеются два параметра ( 1Ъ - размерность и
Цель работы - получение описания множества М и нахождение необходимых и достаточных условий его непустоты, анализ и оценка трудоемкости существующих и получение новых алгоритмов целочисленного программирования.
Методика исследования - опирается на использование методов алгебры, линейного и целочисленного программирования, теории линейных неравенств и теории сложности.
Научная новизна. В диссертации предложен ряд результатов о пересечении выпуклого многогранного конуса с целочисленной рещеткой, позволяющих получать необходимые и достаточные условия совместности системы линейных уравнений в неотрицательных целых числах, в частности, найден дискретный аналог теоремы Фаркаша;
- 4 -- выявлены условия, при которых множество не -отрицательных целочисленных решений системы Л1 линейных диофантовых уравнений можно описать одним диофантовым уравнением ( агрегирующим эту систему ) и построен класс таких систем, для которых коэффиценты любого агрегирующего уравнения растут как экспоненты от ff\ \
предложена общая схема построения правильных отсечений в целочисленном программировании, позволившая проанализировать существующие алгоритмы и разработать новые;
предложен метод получения верхних оценок числа крайних точек выпуклой оболочки множества М при различных способах его задания, доказано, что в ряде важных частных случаев получаемые при этом оценки не улучшаемы по порядку;
предложен алгоритм, описывающий множество М перечислением всех его крайних точек и граней, трудоемкость которого при любой фиксированной размерности имеет вид полинома от
выделены новые подклассы задач целочисленного линейного программирования, имеющие полиномиальные алгоритмы.
Полученные результаты позволяют говорить о новом научном направлении в дискретной оптимизации алгебраически-сложном подходе к задачам целочисленного программирования.
Внедрение.
С 1976 года по настоящее время под научным руковод-
- 5 -ством автора ведутся хоздоговорные работы, по которым зарегистрировано 4 отчета. Получен "Акт использования результатов научно-исследовательской работы в народном хозяйстве" о фактическом экономическом эффекте на 19434 руб.
По некоторым из методов, полученных в диссертации, под руководством автора составлены программы. Одна из них принята в Госфонд алгоритмов и программ: Шевчук А.И., Программная реализация одной модификации алгоритма Гоморн ( № гос.регистрации П 005842).
Материалы диссертации вошли в спецкурс "Дискретное программирование", разработанные и читаемый с 1970 года автором на факультете вычислительной математики и кибернетики Горьковского государственного университета. По ним издан в ГГУ цикл пособий 33-36 , использовавшихся также в Белорусском госуниверситете и Запорожском пединституте.
Апробация pf-боты л публикации. По теме диссертации опубликовано более 40 печатных работ. Результаты, изложенные в диссертации, докладывались на Ш,1У,У Всесоюзных конференциях по теоретической кибернетике ( Новосибирск, 1974г., 1977г., 1980г.), на Ш Всесоюзное конференции по исследованию операций (Горький,І978г.), на П Всесоюзном симпозиуме по теории полугрупп (Свердловек,1978г.), на У Всесоюзном семинаре по комбинаторике (Москва, МГУ,1981г.), на У Республиканской конференции математиков Белоруссии (Гродно,1980г.), на I Крымской весенней школе по дискретной оптимизации (Судак,1982г.), на П Республиканской школе--семинаре по дискретной оптимизации (Ужгород,1983г.), на
П Всесоюзной школе-семинаре "Дискретная оптимизация и её приложения" (Кишинев, 1983г.), на Всесоюзном семинаре по дискретной математике и её приложениям (Москва, МГУ,. 1984г.), на Республиканском семинаре по дискретной оптимизации (Ужгород, 1986г.), на научных семинарах ВЦ АН СССР, ИМ АН ЕССР, ИК АН УССР, ИМ СОАН СССР, ИММ УрНЦ и др.
Структура работы. Диссертация состоит из введения, пяти глав, содержащих 22 параграфа и двух приложений, изложенных на 225 страницах машинописного текста, включающих в себя один рисунок, 24 страницы приложений и 26 страниц списка цитированной литературы из 256 наименований.