Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


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


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


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


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

Скачать в pdf «Экстремальные модели менеджмента и экономики»