Лекция: Глава 7. ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ
Целочисленное программирование (ЦП) – это наиболее важный раздел дискретного программирования. Задачи дискретного программирования отличаются тем, что на переменные накладывается требование дискретности, в частном случае – целочисленности. В качестве примеров можно привести задачи о раскрое (разд. 4.11.5), о ранце, коммивояжера и др.
Характерные источники целочисленности (дискретности):
1. неделимость объектов, представляемых переменными (например, x – число рабочих или отправляемых вагонов);
2. вариантность типа “да-нет” (например, включать или нет данный пакет в портфель ценных бумаг);
3. заданность возможных значений нормативными документами (например, сечения проводов, диаметров труб, размеров профилей и т.п.);
4. комбинаторность (например, размещение объектов, порядок обхода объектов, упорядочение);
5. логические условия (например, фиксированные затраты имеют место только при производстве продукции).
Различают задачи полностью целочисленные/дискретные и частично целочисленные (смешанные). В последних требование целочисленности накладывается не на все переменные.
Любой ряд дискретных значений может быть представлен линейной комбинацией целочисленных переменных. Поэтому дискретная задача легко сводится к целочисленной за счет значительного увеличения числа переменных.
В этой главе рассматриваются только линейные целочисленные задачи.