Раздел 6. Задачи скалярной оптимизации, линейные, нелинейные, дискретные
6.5 Целочисленное программирование
Целочисленное программирование (ЦП) — это наиболее важный раз дел дискретного программирования. Задачи дискретного программирования отличаются от рассмотренных тем, что на переменные накладывается требование дискретности, в частном случае - целочисленности. В качестве примера можно привести задачу о ранце, о выборе оборудования и др.
Характерными источниками целочисленности (дискретности) являются:
1)неделимость объектов, представляемых переменными (например,
х- число рабочих или отправляемых вагонов);
2)вариантность типа “да-нет” (например, включать или нет данный пакет в портфель ценных бумаг);
3)заданность возможных значений нормативными документами (на пример, сечения проводов, диаметров труб, размеров профилей и т.п.);
4)комбинаторность (например, размещение объектов, порядок обхода объектов, упорядочение объектов);
5)логические условия (например, фиксированные затраты имеют ме
сто только при производстве продукции).
Различают задачи полностью целочисленные/дискретные и частично целочисленные (смешанные). В последних требование целочисленности накладывается не на все переменные.
Любой ряд дискретных значений может быть представлен линейной комбинацией целочисленных переменных. Поэтому дискретная задача легко сводится к целочисленной за счет значительного увеличения числа переменных.