§ 2. Классификация математических моделей

2.1. Дискретные (целочисленные) задачи математического программирования могут возникать различными путями. Прежде всего отметим, что существуют задачи линейного программирования, которые формально к целочисленным не относятся (требование целочисленности переменных в них в явном виде не накладывается), но которые при целочисленных исходных данных всегда обладают целочисленным планом. Этим свойством обладает транспортная задача и различные ее варианты (задача о назначениях, задачи о потоках в сетях). Указанное обстоятельство легко понять, вспомнив, что численные методы решения транспортной задачи требуют применения к исходным данным лишь действий сложения и вычитания. Внутренние же причины его гораздо глубже; они заключаются в некоторых специфических свойствах матрицы ограничений транспортной задачи. Здесь мы не будем более останавливаться на этом вопросе, отложив изучение соответствующего класса задач (так называемых «унимодулярных задач») до гл. 17.

2.2. Первоначальным и наиболее естественным стимулом к изучению целочисленных и дискретных задач в собственном смысле слова явилось рассмотрение задач линейного программирования, в которых переменные представляли физически неделимые величины (скажем, количества единиц продукции разных видов). Ясно, что это требование возникает во многих прикладных моделях; первая известная по литературе модель такого рода будет описана в § 2 гл. 2. Для характеристики этого

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

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

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

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

К задачам типа а) относятся задачи минимизации неоднородной функции на выпуклом многограннике. Под неоднородной разрывной линейной функцией мы понимаем функцию

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

Подобные «неклассические» задачи будут рассматриваться в §§ 4—5 гл. 2. Сейчас мы отметим лишь, что введением дополнительных целочисленных переменных они сводятся к задачам целочисленного линейного программирования.

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

1. Задачи с неделимостями.

2. Экстремальные комбинаторные задачи.

3. Задачи с неоднородной разрывной целевой функцией.

4. Задачи на неклассических областях.

5. Некоторые многоэкстремальные задачи.

6. Дискретные задачи в узком смысле слова (нахождение экстремумов на конечных множествах).