Глава 7. Целочисленное программирование

Целочисленное программирование (ЦП) – это наиболее важный раздел дискретного программирования. Задачи дискретного программирования отличаются тем, что на переменные накладывается требование дискретности, в частном случае – целочисленности. В качестве примеров можно привести задачи о раскрое (разд. 4.11.5), о ранце, коммивояжера и др.

Характерные источники целочисленности (дискретности):

1. неделимость объектов, представляемых переменными (например, x – число рабочих или отправляемых вагонов);

2. вариантность типа “да-нет” (например, включать или нет данный пакет в портфель ценных бумаг);

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

4. комбинаторность (например, размещение объектов, порядок обхода объектов, упорядочение);

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

Различают задачи полностью целочисленные/дискретные и частично целочисленные (смешанные). В последних требование целочисленности накладывается не на все переменные.

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

В этой главе рассматриваются только линейные целочисленные задачи.