|
Подводя ито ги краткого обзора основны х методов реш ения задач дискретной оптимизации отметим, что к точны м методам реш ения (или к методам 60 9 ^ / / и / 2 / / / У1 9 ^ 9 ^ / X X X . / / 7 У2 / о / / 4 / / / 2 / / / \ / / / о / / / / У 1 Рис. 1.8. М атричны й способ вы числений решения с оценкой точности) относятся метод ветвей и границ и метод динам ического программирования. Эффективность метода ветвей и границ в сущ ественной степени зависит от точности н и ж н и х (ил и верхних) оценок оптимального решения на подмножествах реш ений. П олучение хоро ш и х оценок во м ноги х случаях по сложности сравнимо с решением исходной задачи. М етод динамического программирования, ка к уж е отмечалось выше, применим к ограниченному классу задач. Описываемый в следую щ их параграфах метод сетевого программирования с одной стороны обобщает метод динамического программирования (при сетевом представлении ти па дерева), а с другой стороны для общ его случая дает достаточно универсальный алгоритм получения н и ж н и х (верхних) оценок, что позволяет эффективно применять метод ветвей и границ. |
методам решения с оценкой точности) относятся метод ветвей и границ и метод динамического программирования. Эффективность метода ветвей и границ в существенной степени зависит от точности нижних (или верхних) оценок оптимального решения на подмножествах решений. Получение хороших оценок во многих случаях по сложности сравнимо с решением исходной задачи. Метод динамического программирования, как уже отмечалось выше, применим к ограниченному классу задач. Описываемый в следующих параграфах метод дихотомического программирования с одной стороны обобщает метод динамического программирования (при дихотомическом представлении типа дерева), а с другой стороны для общего случая дает достаточно универсальный алгоритм получения нижних (верхних) оценок, что позволяет эффективно применять метод ветвей и границ. 2.2. Дихотомическое представление функций и систем ограничений Многие задачи дискретной оптимизации сводятся к следующей постановке: определить вектор х = (Xj) с дискретными компонентами, минимизирующий аддитивную функцию П ф(х) = Е ф*(^1) (2.1) при ограничении f(x )> b . (2.2) Широкий класс функций f(x) допускает дихотомическое представление, такое что вычисление значений функции сводится к последовательному вычислению значений функций двух переменных. Так функция f(x) = f o [ f ( X , X 2) , f 2( x 2, X j ) ] допускает дихотомическое представление (рис. 2.1). При этом соответствующие функции fo, fi, fa удобно представлять в матричном виде (рис. 2.2). Такое представление широко используется в методах комплексного оценивания программ развития предприятий, регионов, результатов деятельности подразделений, уровня безопасности объектов и др. [2,3,16]. 53 |