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

Раздел математического программирования, в к-ром исследуется задача оптимизации (максимизации пли минимизации) функции нескольких переменных, связанных рядом уравнений и (или) неравенств и удовлетворяющих условию целочисленности (используются также термины дискретное программирование, дискретная оптимизация). Источником задач Ц. п. является техническая, экономическая и военная проблематика. Условие целочисленности переменных формально отражает: а) физич. неделимость объектов (напр., при размещении предприятий или выборе варианта боевых действий); б) конечность множества допустимых вариантов, на к-ром проводится оптимизация (напр., множества перестановок в задачах упорядочения); в) наличие логич. условий, выполнение или невыполнение к-рых влечет изменение вида целевой функции и ограничений задачи. Наиболее изученной и распространенной задачей Ц. п. является т. н. задача целочисленного линейного программирования: максимизировать при условиях j = 1, 2, . .., п, xj — целые для j = 1, ..., р, где а ij, bi, cj- заданные целые числа, xj- переменные. Методы решения задач Ц. п. (релаксация, отсечения, динамическое программирование, метод лветви и границы