Целочисленное Линейное Программирование

— раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности.

К частному случаю задачи целочисленного линейного программирования относятся задачи, где переменные X могут принимать всего лишь два значения — 0 и 1. Соответствующие задачи часто называют задачами булевского программирования. Наиболее известные из этих задач — задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т. д. Целочисленное программирование применяется при решении задачи оптимизации развития компании, в которой 0 или 1 означают покупку какого-либо оборудования.

Для решения задач этого типа разрабатываются специфические алгоритмы, основанные на комбинаторике, графах и т. д.

• Карманов В. Г. Математическое программирование. — Наука, 1986. — 288 с.
• Balinski, M. L. Integer Programming: Methods, Uses, Computations (англ.) // Management Science. — 1965. — Vol. 12, no. 3. — P. 253-313. — DOI:10.1287/mnsc.12.3.253.

• Двойственность в Линейном Программировании
• Линейное и Нелинейное Программирование
• Решение Задачи Линейного Программирования