Комбинированные методы дискретной оптимизации

Высокая эффективность метода динамического программирования с использованием множеств Парето по сравнению с классическим алгоритмом не означает преодоления «проклятия размерности» и не должна вводить в заблуждение.

Дело в том, что, как уже отмечалось, использовать этот метод удаётся для решения далеко не всех задач динамического программирования. Примером могут служить задачи, рассмотренные в разд. 3.4.4 и 3.4.5. Но в тех случаях, когда использование нового алгоритма возможно, рост объёма вычислений с ростом размерности задачи приводит к вычислительным трудностям при существенно больших размерностях задач. Так, если в задачах распределения ресурса при использовании классического алгоритма время счёта становилось неприемлемым при числе потребителей и вариантов распределения для каждого из них в несколько десятков, то для нового алгоритма эти параметры увеличиваются на порядок. При дальнейшем увеличении размерности время счёта может достигать неприемлемых величин, особенно если задача оптимизации встроена в многократно повторяемый цикл расчётов с различными исходными данными. Отметим также и то обстоятельство, что количество отбраковываемых непаретовских состояний существенно зависит от конкретных числовых данных при одной и той же размерности задачи. Может оказаться, что таких состояний мало или вообще нет. Так в рассмотренной в разд. 4.2 однопараметрической задаче об использовании транспортных средств при численном равенстве веса каждого предмета и его стоимости все точки на всех этапах являются паретовскими, так как при переходе от одного состояния к другому увеличиваются и суммарный вес и численно равная ему стоимость, но при переходе к двухкритериальной задаче по стоимости нужен максимум, а по весу минимум.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >