Введение. 
Использование методов целочисленного программирования для оптимизации решений

Большой класс задач оптимизации сводится к задачам целочисленного программирования. Общей особенностью всех этих задач является обязательность целочисленного решения. Например, физически невозможно подготовить к эксплуатации 0,3 изделия, заменить при ремонте 1,5 агрегата. Таким образом, целочисленный, дискретный характер решения определяется физическим смыслом этих задач. В соответствии с таким характером решения рассматриваемые в задачах зависимости являются дискретными и нелинейными, задачи имеют большую размерность, во многих случаях аналитические зависимости отсутствуют.

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

(0).

при ограничении.

. (1).

Особенность задачи (0), (1) заключается в том, что xj принимает только два значения 0 или 1. К задаче такого типа могут быть сведены различные задачи оптимального распределения дискретных ресурсов. Очевидно, что с помощью методов линейного программирования можно решить задачу (0), (1), округлив полученные нецелочисленные значения xj до ближайших целых чисел. Однако такой подход может привести к решению, значительно отличающемуся от оптимального.

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

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

Для решения задач целочисленного программирования разработаны две группы методов: методы отсечения и комбинированные методы.

Сущность методов отсечения состоит в следующем.

• 1. Задачу целочисленного программирования решают как задачу линейного программирования без учета условия целочисленности решения. Если полученное решение является целочисленным, то вычислительный процесс прекращают. В противном случае переходят к п. 2.
• 2. Вводят дополнительное ограничение, исключающее (отсекающее) нецелочисленное решение, и возвращаются к п. 1.

Опыт использования этого метода показал, что эффективность алгоритмов отсечения невысока. Более эффективными в общем случае являются комбинаторные методы, основанные на упорядоченном переборе наиболее перспективных вариантов.

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