Главная /
Рефераты / МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО (ЦЕЛОЧИСЛЕННОГО) ПРОГРАММИРОВАНИЯ
МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО (ЦЕЛОЧИСЛЕННОГО) ПРОГРАММИРОВАНИЯ
Область применения. Дискретное программирование используется для решения задач с детерминированной целевой функцией при ограничениях на значения переменных.
Примерами таких задач являются: определение очередности выполнения работ, назначение ресурсов по объектам использования, выбор маршрута на сети «задача о коммивояжере».
Особенности применения. Основной особенностью является то, что все или некоторые переменные должны принимать только целочисленные (дискретные) значения. Обычно это бывает при описании неделимых объектов (людей, машин и т. п.) или при наложении жестких ограничений типа равенств.
При решении задач возникают сложности с выбором специальных дополнительных ограничений для отсечения облас-
ти решений с нецелочисленными переменными, которые часто приходится выбирать по эвристическим правилам.
Наиболее употребительные методы. Различают два класса методов: методы отсечения и комбинаторные методы.
Методы отсечений [56] используются при решении линейных целочисленных задач без булевых переменных. Их идея заключается в ослаблении ограничений (за счет отказа от требований целочисленности) и решения обычной задачи линейного программирования. Затем, если полученное оптимальное решение не удовлетворяет требованию целочисленности, вводят специальные дополнительные требования, тем самым отсекая некоторую область возможных решений, и вновь решают задачу линейного программирования с проверкой результатов на целочисленность переменных.
Процесс повторяется до выполнения требований по целочисленности. Для решения целочисленных задач используется алгоритм Гомори и алгоритм Дальтона и Ллевелина
Комбинаторные методы [43, 55] используются для решения нелинейных задач с булевыми переменными. Для таких задач используется так называемый аддитивный алгоритм, вычислительные операции в котором осуществляют вычитанием. Идея аддитивного алгоритма заключается в переборе 2 возможных решений (где N — число булевых переменных) и выбор лучшего из них.
Похожие рефераты:
