4.1. Постановка задачи целочисленной оптимизации (иногда его называют также дискретным программированием)
Под задачей целочисленного программирования понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Если требование целочисленности распространяется на часть неизвестных величин задачи, то такая задача называется частично целочисленной. Целочисленное программирование возникло в 50–60-е годы XX века из нужд практики – главным образом в работах американских математиков Дж. Данцига и Р. Гомори. Первоначально целочисленное программирование развивалось независимо от геометрии чисел на основе теории и методов математической оптимизации, прежде всего, линейного программирования. Однако в последнее время исследования в этом направлении все чаще проводятся средствами математики целых чисел. Задачи такого типа весьма актуальны, так как к их решению сводится анализ разнообразных ситуаций, возникающих в экономике, технике, военном деле и других областях. С появлением ЭВМ, ростом их производительности повысился интерес к задачам такого типа и к математике в целом.
Целочисленным (иногда его называют также дискретным) программированием называется раздел математического программи рования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит целочисленный характер, что связано, как правило, с физической недели мостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом, с последующим округлением до целых чисел. Однако такой подход оправдан, когда отдельная единица составляет очень малую часть всего объема (например, товарных запасов); в противном случае он может внести значительные искажения в действительно оптимальное решение Большинство целочисленных задач, таких как задача с неделимостями, принадлежит к разряду так называемых трудно решаемых. Это означает, что вычислительная сложность алгоритма их точного решения сравнима по трудоемкости с полным перебором вариантов. Получение их точного решения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие на ходить точное решение даже при больших размерностях.
Для решения целочисленных задач используются следующие методы:
1) симплекс-метод (для транспортных задач, задач о назначениях);
2) метод отсечения (метод Гомори);
3) метод ветвей и границ (в общем случае не обеспечивает получения
точного решения);
4) эвристические методы (не обеспечивают получения точного решения).
Последняя группа методов может использоваться в случаях, когда применение предыдущих методов невозможно или не приводит к успеху.
Кроме того, эвристические методы можно использовать для решения задач любой сложности.
Математическая модель задачи целочисленного программирования представлена в виде:
(4.1.)
(4.2.)
(4.3.)
(4.4.)
Ограничения (4.2) определяют выпуклую область OABCD в n-мерном пространстве, как показано на рисунке 4.1.
Рисунок 4.1. – ОДР задачи целочисленного программирования
Узлы целочисленной решетки на рисунке 4.1 изображены точками.
Такие точки, расположенные внутри области OABCD, являются допустимыми решениями задачи целочисленного программирования. Ее оптимальные решения всегда располагаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленная. Предположим, что область допустимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рисунке 4.1 эта выпуклая оболочка показана затененной областью OEFGH. Эту затененную область можно рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, определяющей допустимую область OABCD, добавить ограничение типа RR’, как показано на рисунке 4.1, то вновь полученная задача будет иметь OEFGH в качестве области допустимых решений. Такая вновь полученная область обладает двумя важными свойствами: во-первых, она содержит все допустимые целочисленные точки исходной задачи линейного программирования (поскольку она является выпуклой оболочкой этих точек), во-вторых, все крайние точки новой области – целочисленные. Поэтому любое базисное оптимальное решение модифицированной задачи линейного программирования имеет своими компонентами целые числа и является оптимальным решением исходной задачи целочисленного программирования.
Именно алгоритм целочисленного программирования, который будет описан ниже, реализует методы систематического введения дополнительных ограничений с целью сведения исходной допустимой области к выпуклой оболочке ее допустимых целочисленных точек.