- Целочисленное программирование
-
Целочисленное программирование — раздел математического программирования, в котором на все или некоторые переменные дополнительно накладывается ограничение целочисленности[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
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 15 мая 2011.Категории:- Исследование операций
- Оптимизация
Wikimedia Foundation. 2010.