Постановка задачи целочисленного программирования. В последние годы возрастает актуальность разработки алгоритмов для таких областей техники как проектирование сетей ЭВМ

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

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

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

Специфика задач целочисленного программирования заключается в том, что переменные x_j и функции f (x), g_i (x) могут принимать только дискретные значения. Специальными преобразованиями в подавляющем большинстве случаев можно свести эти дискретные значения к целочисленным.

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

где Z − множество целых чисел.

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

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

Методы целочисленной оптимизации можно разделить на три основные группы:

а) методы отсечения;

б) комбинаторные методы;

в) приближенные методы.