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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Простейший метод решения задачи целочисленного программирования — сведение её к задаче линейного программирования с проверкой результата на целочисленность.

Булевское программирование[править | править вики-текст]

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

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

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

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