ЧАСТЬ I. ПРЕДМЕТ И МОДЕЛИ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ

Эта часть играет роль развернутого введения. В гл. 1 дается общая характеристика предмета дискретного программирования и разъясняются идеи, лежащие в основе важнейших численных методов этой дисциплины. Указывается схематическая классификация математических моделей и прикладных задач дискретного программирования. На основе этой классификации в гл. 2 и 3 приводятся математические формулировки наиболее типичных задач.

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

ГЛАВА 1. ВВЕДЕНИЕ

§ 1. Предмет дискретного программирования

1.1. Настоящая книга посвящена дискретным задачам математического программирования. Наиболее изученными задачами этого класса являются целочисленные задачи линейного программирования, т. е. задачи линейного программирования, в которых на все переменные (либо на их часть) наложено дополнительное требование целочисленности. В первом из этих случаев обычно говорят о полностью целочисленных, а во втором — о частично целочисленных задачах. Разумеется, аналогичным образом можно определить целочисленные (частично целочисленные) варианты и для более общих задач оптимального программирования — можно говорить, например, о задачах выпуклого целочисленного программирования и т. п.

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

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

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

1.2. Опишем теперь предмет в более формальных терминах.

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

при условиях

и

Здесь некоторая область -мерного евклидова пространства (в подавляющем большинстве случаев в качестве рассматривается неотрицательный ортант пространства так что (1.3) представляет собой попросту условие неотрицательности всех переменных). Область, определяемую условиями (1.2) и (1.3), мы будем обозначать через

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

Среди задач (1.1) — (1.3) можно выделить класс задач, которые мы назовем регулярными. Эти задачи характеризуются следующими условиями.

1. Для каждой точки можно определить некоторым образом понятие непустой окрестности

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

3. Локальный оптимум целевой функции совпадает с глобальным.

К регулярным задачам относятся, например, задачи выпуклого программирования (функция вогнута, функции выпуклы) и их частный случай — задачи линейного программирования (функции линейны, есть неотрицательный ортант).

К задачам, не являющимся регулярными, относятся, в частности, так называемые многоэкстремальные задачи, в которых глобальный экстремум может не совпадать с локальным. Многоэкстремальным задачам уделено значительное место в обзоре Д. Б. Юдина [42], [43].

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

Отсюда ясно, что в дискретных задачах область допустимых решений является невыпуклой и несвязной. Эта область определяется условиями двух типов: «регулярными» условиями (1.2) и условиями дискретности (частичной дискретности) (1.3). Характерно, что чаще всего условия дискретности (частичной дискретности) отделены от других условий и, кроме того, «отсепариро-ваны» по отдельным переменным, так что их можно записать следующим образом:

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

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

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

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

удовлетворяющих условию равно

иначе говоря, с увеличением числа переменных объем вычислительной работы растет весьма быстро. То, что при этом подсчете мы не учитывали ограничений (1.2), дела практически не меняет.

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

при условиях

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

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

Сразу же отметим, что приведенный пример порочит не саму идею регуляризации, а лишь ее чересчур прямолинейное использование. Идея регуляризации задачи лежит в основе широкого класса численных методов дискретного программирования — так называемых «методов отсечения» (см. § 4).

Все сказанное показывает, что для решения дискретных задач оптимизации необходимо создание совершенно новых методов. Классификации и краткий обзор этих методов будут приведены в § 4.