Модели
относятся (требование целочисленности переменных в них в явном виде не накладывается), но которые при целочисленных исходных данных всегда обладают целочисленным планом.
Этим свойством обладают транспортная задача и различные ее варианты (задача о назначениях).Первоначальным стимулом к изучению целочисленных и дискретных задач явилось рассмотрение задач линейного программирования, в которых переменные представляли физически неделимые величины (скажем, количество единиц продукции разных видов). Для характеристики этого класса моделей используется термин «задачи с неделимостями».
Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремальным комбинаторным задачам, для решения которых приходится вводить булевы переменные, носящие логический характер (х = 1 или х = 0).
К целочисленным (точнее, частично целочисленным) задачам линейного программирования удается свести также ряд задач, в которых явное требование целочисленности отсутствует, зато имеются некоторые особенности, выводящие их за рамки линейного программирования. Эти особенности могут относиться либо к целевой функции, либо к области допустимых решений.
Итак, можно выделить следующие основные классы задач дискретного программирования:
транспортная задача (см. главу 5) и ее варианты;
задачи с неделимостями;
экстремальные комбинаторные задачи;
задачи с неоднородной разрывной целевой функцией (см. транспортную задачу с фиксированными доплатами в главе 5);
задачи на неклассических областях (см. модель оптимального размера заказа с количественными скидками в главе 12).