Задача целочисленного линейного программирования

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

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

К ЗЦЛП относится большое число экономических задач. Например, распределение производственных заказов между предприятиями, оптимальный раскрой материалов, определение загрузки оборудования, распределение транспортных средств по рейсам, задачи производства и реализации неделимой продукции.

ЗЦЛП может быть сформулировано следующим образом: найти максимум или минимум функции при условиях , .

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

Для решения ЗЦЛП разработаны специальные методы: метод сечений (метод Гомори) и метод ветвей и границ.