|
42 существенной степени зависит от точности нижних (или верхних) оценок оптимального решения на подмножествах решений. Получение хороших оценок во многих случаях по сложности сравнимо с решением исходной задачи. Метод динамического программирования, как уже отмечалось выше, применим к ограниченному классу задач. Описываемый в следующих параграфах метод дихотомического программирования с одной стороны обобщает метод динамического программирования (при дихотомическом представлении типа дерева), а с другой стороны для общего случая даетдостаточно универсальный алгоритм получения нижних (верхних) оценок, что позволяет эффективно применять метод ветвей и границ.X X 0 У / о 0/ У 0 2 / / 3 Х>У о У / о х У X X X X X X / 2 X 4 У / 6 % X X X X X У2 10 10. 14 12 11 10 Рис. 1.4.8 1.5. Методы сетевого и дихотомического программирования Многие задачи дискретной оптимизации сводятся к следующей постановке: определить вектор х= {х\} с дискретными компонентами, минимизирующий аддитивную функцию ф(х)=Еф ,(х) (1.5.1) ¿•1 |
т порционально п, что свидетельствует о высокой эффективности метода. К сожалению, метод динамического программирования применим к ограниченному классу задач. оу / 5 3X / 5 X XX X XXо / о / X У 1х X 4 / / о / о W / 2 / 6 X XX 0X X о 0X Х о XуУ / х З jоу Х о ЗУ X 4 У2 щ / / 9 6Х / 9 \ у Х 4 X X 9X Л .2 4X Хб 4X /6 8X Л \ X X 7у Хо X X 6X X 8 X X X ° х Хо ° х Хо X уУ / х 4 о/ Хо 0 / X 5 10^ 1 4 '1 2 11 10 Рис. 1.8. Подводя итоги краткого обзора основных методов решения задач дискретной оптимизации отметим, что к точным методам решения (или к методам решения с оценкой точности) относятся метод ветвей и границ и метод динамического программирования. Эффективность метода ветвей и границ в существенной степени зависит от точности нижних (или верхних) оценок оптимального решения на подмножествах решений. Получение хороших оценок во многих случаях по сложности сравнимо с решением исходной задачи. Метод динамического программирования, как уже отмечалось выше, применим к ограниченному классу задач. Описываемый в следующих параграфах метод сетевого программирования с одной стороны обобщает метод динамического программирования (при сетевом представлении типа дерева), а с другой стороны для общего случая дает достаточно универсальный алгоритм получения нижних (верхних) оценок, что позволяет эффективно применять метод ветвей и границ. 86 |