ПРОГРАММИРОВАНИЕ ЦЕЛОЧИСЛЕННОЕ
— раздел программирования математического, изучающий задачи, в которых на значения всех или части переменных наложено требование целочисленности. Задача П. ц. наз. полностью целочисленной, если требование целочисленности наложено на все переменные, и частично целочисленной, если ограничение целочисленности касается лишь части переменных. Наиболее изучены задачи линейного П. ц., которые обычно записываются в виде:
целое, 
, где все 
— заданные числа, а 
переменные задачи.
Задачи П. ц. можно разделить на несколько характерных классов. 1. Задачи с неделимостями — задачи, переменные которых представляют физически неделимые величины. 2. Экстремальные комбинаторные задачи — задачи, в которых требуется найти экстремум целочисленной линейной ф-ции, заданной на конечном множестве элементов, и само подмножество элементов, на котором этот экстремум достигается. Число таких подмножеств для реальных задач, как правило, чрезвычайно велико, поэтому решение таких задач путем перебора всех вариантов связано с непреодолимыми трудностями. Эти задачи можно сформулировать в виде задачи программирования линейного, в многограннике решений которой каждой целочисленной точке соответствует определенное подмножество элементов исходной комбинаторной задачи. Решение полученной задачи имеет комбинаторный смысл лишь в случае его целочисленности. К числу наиболее известных задач этого класса относятся задачи о коммивояжере, о назначении, задачи теории расписаний и т. д. 3. Задачи с неоднородной разрывной линейной формой, т. е. задачи с линейной формой вида
где
Они сводятся к задачам линейного П. ц. путем добавления к задаче целочисленных переменных 
и ограничений 
, где 
наибольшее значение, принимаемое 
и заменой исходной линейной формы (1) на 
. Из задач этого класса наиболее известны транспортная задача с фиксированными доплатами и различные варианты задач размещения. К задачам линейного П. ц. сводится с достаточной степенью точности и задача минимизации произвольной сепарабельной функции (1) на выпуклом многограннике. 4. Задачи на неклассически? областях представляют собой задачи нахождения экстремума линейной формы на области, задаваемой, помит 
линейных неравенств, еще и логическими условиями вида «ЛИБО — ЛИБО». Такие области обычно невыпуклы или несвязны. Путем введения новых целочисленных переменных эти задачи также сводятся к задачам линейного П. ц.
Общие методы линейного программирования непосредственно к задачам линейного П. ц. применять нельзя, т. к. в большинстве случаев они дают дробные решения. Округление компонент целочисленного решения до ближайших целых чисел может не только увести от оптим. целочисленного решения, но и вывести за пределы допустимых решений. Существует класс задач П. ц., среди оптим. решений которых всегда имеется целочисленное. К этому классу относятся, напр., транспортная задача, сетевая транспортная задача, задача о назначениях, задача о кратчайшем пути и некоторые другие. Эта особенность связана с тем, что определитель произвольной квадратной подматрицы матрицы условий задачи равен нулю или ± 1. Такие задачи решают методами
линейного программирования. Однако этот класс узок и почти исчерпывается перечисленными задачами. Поэтому возникла необходимость в разработке спец. методов решения задач П. ц.
Американскими учеными Дж. Данцигом, Д. Фалкерсоном и С. Джонсоном была предложена основная идея методов отсечения для решения задач линейного П. ц. Эта идея заключается в следующем. Задача решается сначала без ограничений целочисленности. Если полученное решение целочисленно, то оно является оптим. решением задачи П. ц. В противном случае, к условиям исходной задачи добавляется линейное ограничение, которому удовлетворяют все целочисленные решения исходной задачи, но не удовлетворяет полученное нецелочисленное решение. Описанная процедура отсечения продолжается вплоть до получения на некотором шаге целочисленного оптим. решения либо до выявления неразрешимости задачи. Т. о., решение задачи П. ц. сводится к решению последовательности задач линейного программирования. Впервые правило формирования дополнительных ограничений для полностью целочисленных, а затем и частично целочисленных линейных задач П. ц. было разработано амер. ученым Р. Гомори в 1958 г. Гомори метод при достаточно естественных предположениях о задаче приводит к оптим. целочисленному решению за конечное число шагов. Известны и другие методы, использующие идею отсечения.
В комбинаторных методах для решения задач П. ц. максимально используется конечность числа допустимых решений. Эти методы характеризуются использованием направленного перебора. Важным и наиболее известным методом из этой группы является ветвей и границ метод и различные его модификации. Отличительной чертой этих методов служит макс. использование специфических особенностей задачи в процессе решения. Для некоторых классов задач П. ц. используются методы программирования динамического и последовательной оптимизации.
Методы случайного поиска (см. Численные методы) и другие приближенные методы применяются, как правило, для решения задач П. ц. большой размерности, для которых точные методы малоэффективны. Лит.: Корбут А. А., Финкельштейн Ю. Ю. Дискретное программирование. М., 1969 [библиогр. с. 358—366]: Корбут А. А., Финкельштейн Ю. Ю. Дискретные задачи математического программирования. В кн.: Итоги науки. Теория вероятностей, математическая статистика, теоретическая кибернетика. 1966. М., 1967 [библиогр. с. 97—108]; Гольштейн Б. Г., Юдин Д. В. Новые направления в линейном программировании. М., 1966 [библиогр. с. 516—520].
В. А. Грубим.
