Математическая энциклопедия - целочисленное программирование

раздел математического программирования, в к-ром исследуется задача оптимизации (максимизации пли минимизации) функции нескольких переменных, связанных рядом уравнений и (или) неравенств и удовлетворяющих условию целочисленности (используются также термины дискретное программирование, дискретная оптимизация). Источником задач Ц. п. является техническая, экономическая и военная проблематика.

Условие целочисленности переменных формально отражает: а) физич. неделимость объектов (напр., при размещении предприятий или выборе варианта боевых действий); б) конечность множества допустимых вариантов, на к-ром проводится оптимизация (напр., множества перестановок в задачах упорядочения); в) наличие логич. условий, выполнение или невыполнение к-рых влечет изменение вида целевой функции и ограничений задачи.

Наиболее изученной и распространенной задачей Ц. п. является т. н. задача целочисленного линейного программирования: максимизировать

при условиях

j = 1, 2, . .., п, xj - целые для j = 1, ..., р, где а ij, bi, cj- заданные целые числа, xj- переменные.

Методы решения задач Ц. п. (релаксация, отсечения, динамическое программирование, метод лветви и границы

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985