В2 Целочисленное программирование. Метод Гомори решения задач целочисленного программирования.

Под задачей целочисленного программирования понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. Если требование целочисленности распространяется на часть неизвестных величин задачи, то такая задача называется частично целочисленной. Целочисленным программированием называется раздел математического программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условие целочисленности, а область допустимых решений конечна. Огромное количество экономических задач носит целочисленный характер, что связано, как правило, с физической неделимостью многих элементов расчета: например, нельзя построить два с половиной завода, купить полтора автомобиля и т.д. В ряде случаев такие задачи решаются обычными методами, например, симплексным методом. Однако большинство целочисленных задач, таких как задача с неделимостями, принадлежит к разряду так называемых трудно решаемых. Получение их точного решения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие находить точное решение даже при больших размерностях. Математическая модель задачи целочисленного программирования представлена в виде: (2.1) ;(2.2) ;(2.3) -целые. Метод Гомори основан на применении симплекс-метода и метода отсечения. Идея его достаточно проста и заключается в следующем. Сначала находится оптимальное решение задачи целочисленного программирования симплекс-методом. Если полученное решение целочисленное, то цель достигнута. Если же оптимальное решение не является целочисленным, то в условия задачи вводится дополнительное ограничение, которое отсекает от области допустимых решений полученное нецелочисленное решение и не отсекает от нее ни одной точки с целочисленными координатами. Далее симплекс-методом решается расширенная задача, т.е. находится ее опорное и оптимальное решение. Если новое решение не будет целочисленным, то вводится еще одно дополнительное ограничение. Процесс построения дополнительных ограничений и решения задачи симплекс-методом продолжается до тех пор, пока не будет найдено оптимальное целочисленное решение или не будет установлено, что его не существует Приведем алгоритм метода Гомори. 1.Симплекс-методом находят оптимальный план задачи 2.1-2.3(таблица 2.1). Если в таблице 2.1 все свободные члены целые, то план является оптимальным и для исходной задачи (2.1)–(2.4). Если задача (2.1)–(2.3) неразрешима, то и задача (2.1)–(2.4) неразрешима. Если среди свободных членов есть нецелые, то переходят к пункту 2 алгоритма.

2. Среди нецелых свободных членов выбирают, например, тот, который имеет наибольшую дробную часть. Пусть в нашем случае таковым является . По строке формируют правильное отсечение в виде неравенства (2.5)

. 3. Неравенство (2.5) введением дополнительной неотрицательной целочисленной переменной преобразовывают в эквивалентное уравнение (2.6) 4. Расширяют таблицу 1 за счет включения в нее дополнительной стро-ки для составленного уравнения (2.6) (таблица 2.2), получая тем самым симплексную таблицу для расширенной задачи.

5. Составленную расширенную задачу вновь решают симплекс-методом. Если оптимальный план будет целочисленным, то он и станет решением исходной задачи (2.1)–(2.4). В противном случае возвращаются к пункту 2 алгоритма. Если задача разрешима в целых числах, то через конечное число итераций оптимальный целочисленный план будет найден. Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах В качестве преимуществ метода Гомори можно рассматривать его эффективность и точность, т.к. в результате решения получается наиболее оптимальное значение задачи. К недостаткам метода можно отнести: 1 трудоемкость (в некоторых задачах необходимо производить множество расчетов); 2. громоздкость (решение достаточно объемно, т.к. приходится искать оптимальные значения сначала симплекс-методом, а затем методом отсе-чения, который также может применяться несколько раз); 3.малая применимость (метод применяется для задач с небольшим ко-личеством переменных, т.к. при увеличении их числа происходит значи-тельное увеличение трудоемкости вычислений).