|
74 Метолдинамическогопрограммирования (ветвьдерева) Метод дихотомического программирования (произвольноедерево) Рис. 2.3.5. Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот принцип оптимальности можно записать следующим образом: Фк(У)= min h (yi)+ 9 j{yj)], (ij)ep(y) где P(y) множество пар (i,j), такие что fk(yi,yj)= yРассмотрим произвольное дихотомическое представление функции Дх), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами вершины, соответствующие переменным х,, i = l,n . Рассмотрим множество конечных вершин, которые не являются висячими, то |
Xj, меньше на 2. За конечное число таких преобразований получим структуру с длиной цепи между этими вершинами либо 2 (тогда задача решена), либо 3 (тогда применяем преобразование, показанное на рис. 1.4.1в). Таким образом, имея одно представление, мы можем получить эквивалентное представление любой структуры. Таким образом, из дихотомического представления функции <р(х) мы можем получить дихотомическое представление этой же функции, но с такой же структурой, какую имеет дихотомическое представление функции f(x). Одинаковая структура дихотомического представления функции <р(х) и fl:x) позволяет применять метод дихотомического программирования. Рассмотрим произвольное дихотомическое представление функции f(x), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами вершины, соответствующие переменным Xj, i = 1,п. Рассмотрим множество конечных вершин, которые не являются висячими, то есть их степень захода больше 1. Разделим произвольным образом затраты ф,(х[) на к; частей, где к — число заходящих дуг. Фактически мы как бы разделили вершину i на к; висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина, имеющая степень захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако, это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема. Теорема 1.4.3.[6%] Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. 1.5. Существующие методы построения комплексной оценки организациопно-технологнчсскнх решений Оценка организационно-технологических решений (ОТР) строительства любого объекта является важной составляющей всего комплекса задач теории принятия решений в строительстве. В современных экономических условиях часто оказывается недостаточным только личный опыт лица, принимающего решение. Недооценка каких-либо факторов на уровне организационнотехнологического проектирования может вызвать огромные затраты, выходящие 55 ции, ветвей и границ и другие). Рассмотрим процедуру возможного решения задачи. На первом шаге строится зависимость стоимости заказа от его размера для первого предприятия поставщика. Далее получаем зависимость стоимости заказа от величины партии для первого и второго поставщика, то есть зависимость S(xb х2) и т. д. То есть в данном случае целевая функция задачи представляет собой дихотомическую функцию в виде дерева. Пример такой функции представлен на рис. 5.2.4. 195 В.Н. Бурковым и И.В. Бурковой в работе [68] для таких задач предложен метод дихотомического программирования, являющимся обобщением известного метода динамического программирования. Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот принцип оптимальности можно записать следующим образом: срк(у) = пип [ф, (У;)+ Ф](УЛ], (i.j)ep(y) где Р(у) множество пар (ij), такие что fj;(у,, у,) = у. Построим функция стоимости общего объема заказа для двух первых производителей. Данные представлены в табл. 5.2.2. |