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

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

Если условие целочисленности наложено на все переменные, то задача является полностью целочисленной; когда это условие относится лишь к некоторым переменным, задача является частично целочисленной.

Если целевая функция и функции, входящие в ограничения, линейные, то задача является линейной целочисленной.

Линейные полностью целочисленные задачи

Такие задачи формулируются следующим образом:

найти минимальное значение линейной функции

при ограничениях , , целые.

Примерами задач ЦЧП являются задачи раскроя материалов, загрузки оборудования, распределения судов по линиям, самолётов по рейсам, а также задачи по производству неделимой продукции.

Геометрическая интерпретация ЗЦЧП

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

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

Методы решения ЗЦЧП

Задачи целочисленного программирования нельзя решать путём простого округления значений переменных, полученных при решении задачи без учёта требования целочисленности. Найденное таким образом решение может даже не удовлетворять ограничениям задачи, а если и будет удовлетворять, то может быть совсем не оптимальным.

Методы решения ЗЦЧП подразделяются на:

1. методы отсечений;

2. комбинаторные методы.

При решении задач методами отсечений сначала находят оптимальное решение задачи, которая получается из исходной, если отбросить требование целочисленности. Затем вводят специальные дополнительные ограничения (по одному на каждой итерации). Эти дополнительные ограничения учитывают требования целочисленности. Они деформируют многоугольник решений задачи до тех пор, пока координаты оптимального решения не станут целыми.

Одним из наиболее широко используемых методов отсечений является метод Гóмори (метод отсекающих плоскостей). Название «метод отсекающих плоскостей» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) области многоугольника (многогранника) решений, в которых отсутствуют точки с целочисленными координатами.

В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, перебирать все решения очень сложно и долго, поэтому разработаны тестовые процедуры, позволяющие непосредственно рассматривать лишь относительно небольшую часть решений, а остальные – учитывать некоторым косвенным образом.

Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи без учёта требования целочисленности. Далее из рассматриваемой задачи получаются две подзадачи путём специального разбиения пространства решений и отбрасывания областей, не содержащих допустимых целочисленных решений.