ПРЕДИСЛОВИЕ РЕДАКТОРА

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

Формальные модели, отвечающие всем этим разнообразным по своему содержанию задачам, мало

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

Задачи и методы, относящиеся к перечисленному кругу вопросов, различные авторы именуют по-разному. Наибольшее распространение получил термин целочисленное программирование. По-видимому, это связано с большим впечатлением, которое произвела фундаментальная работа Гомори. В литературе встречаются, однако, и другие термины: дискретное программирование и реже комбинаторное или диофантово программирование.

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

Несмотря на кажущуюся простоту постановки задач дискретного программирования, математические трудности, возникающие при их анализе, могут быть весьма значительны. Чтобы дать представление о сложности теоретических и вычислительных проблем дискретного программирования, достаточно указать, что так называемая «великая теорема Ферма» может быть сформулирована как следующая задача целочисленного программирования:

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

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

Предлагаемая вниманию читателя монография А. А. Корбута (Ленинград) и Ю. Ю. Финкельштейна (Москва) «Дискретное программирование» является первым в отечественной и, по-видимому, в мировой литературе сводным и достаточно полным изложением предмета.

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

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

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

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

Можно ожидать, что монография А. А. Корбута и Ю. Ю. Финкелыитейна будет с удовлетворением встречена математиками, экономистами, инженерами, научными работниками, аспирантами и студентами многих специальностей, связанных с вычислительными методами, вычислительной техникой и различными задачами регулирования и управления.

Д. Юдин

Май 1968 г.

ПРЕДИСЛОВИЕ АВТОРОВ

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

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

Книга состоит из пяти частей. Каждая часть делится на главы; главы делятся на параграфы, а параграфы обычно разбиваются на пункты. Часть I является вводной; в ней дается общая характеристика предмета дискретного программирования (включая численные методы) и формулируются наиболее типичные

математические модели. Части II, III, IV посвящены численным методам. В них рассмотрены соответственно методы отсечения, комбинаторные методы и приближенные методы. В части V излагаются вопросы, представляющие значительный теоретический интерес, но непосредственно не относящиеся к численным методам (характеризация целочисленных многогранников, роль двойственных оценок в целочисленных линейных задачах).

Часть материала (например, гл. 8, § 1 из гл. 12, алгоритм проверки Т-матриц на унимодулярность из гл. 17) публикуется здесь впервые.

Приложенный к книге список литературы отнюдь не претендует на полноту и ограничивается в основном цитированными источниками. Более подробный список литературы (225 названий), а также некоторые дополнительные исторические сведения можно найти в обзорной статье авторов [15].

Для читателя весьма желательным является свободное владение основными понятиями математического программирования. Необходимые сведения из линейного программирования (систематически используемые в части II, а также в гл. 17) суммированы в гл. 4.

Авторы выражают искреннюю признательность профессору Д. Б. Юдину, взявшему на себя нелегкий труд редактирования этой книги.

Авторы, Апрель 1968 г.