Проверяемый текст
Буркова, Ирина Владимировна; Метод дихотомического программирования в задачах управления проектами (Диссертация 2004)
[стр. 66]

66 Рис.
2.5.
И ллю страция методов программирования: а динамического (ветвь дерева); б дихотом ического (произвольное дерево).
Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве.
Соответственно, принцип оптимальности в методе дихотом ического
программирования м ож но сформулировать следующ им образом: любое поддерево оптимального дерева должно быть оптимальным.
Формально этот п р ш щ и п оптимальности м ож но записать следую щ им образом: где р(у) множество пар (i, j) , та ки х что (yi, y j) = у.
О б щ и й с л у ч а й Рассмотрим произвольное
сетевое представление ф ункции f(x), задаваемое сетью, выходом которой является верш ина, соответствующ ая ф ункции f(x), а выходами верш ины, соответствующ ие переменным Xj, i = l, n .
Рассмотрим множество конечны х верш ин, которы е не являются висячими,
т.е.
и х степени захода больше 1.
Разделим произвольным образом затраты ф(хО на
ki частей, где ki число заходящ их д уг.
Ф актически м ы ка к бы разделили верш ину i на ki висячих верш ин с соответствующ ей частью затрат.
Далее применяем описан
[стр. 57]

функций ф(х1) и ф2(хг) для соответствующих значений Х и хг.
Так, например, клетке (xi,X2) = (3,2) соответствует сумма Ф1(3) + Ф2(2) = 2 0 + 10 = 30.
Далее будем называть эту сумму затратами на достижение соответствующего состояния.
2 шаг.
Из всех элементов матрицы имеющих одно и то же значение y = fi(Xi,X2) выбираем элемент с минимальной сытимой Ф(х1)+ср2(х2).
Минимальную сумму записываем в нижнюю половину клетки, соответствующей этому значению у в верхней матрице.
Так, например, значению у = 3 соответствуют 5 ‘элементов нижней матрицы: (3;2), (4;2), (3;3), (4;3) и (2;4).
Из них элемент (3;2) имеет минимальную сумму 30 (это число записано в нижней половине соответствующей клетки).
Поэтому в верхней матрице значению у = 3 соответствует число 30, записанное в нижней половине соответствующей клетки.
Далее шаги 1и 2 повторяются для верхней матрицы.
В результате для каждого значения f(x) мы получаем минимальную величину ф(х).
Несложно обобщить описанный алгоритм на случай производльного дихотомического представления функции f(x) в виде дерева.
Шаги 1 и 2 алгоритма повторяются, начиная с висячих вершин дерева дихотомического представления.
Заметим, что дихотомическое представление Рис.
3.1 имеет тип ветви дерева.
В этом случае метод дихотомического программирования переходит в метод динамического программирования.
Таким образом, метод дихотомического программирования в случае, когда дихотомическое представление имеет вид дерева, является обобщением метода динамического программирования, распгаряя круг задач, решаемых на основе данного подхода (Рис.
3.2).
Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве.
Соответственно, принцип оптимальности в методе дихотомического
программи57

[стр.,58]

рования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным.
Метод динамического программирования (ветвь дерева) Метод дихотомического программирования (произвольное дерево) Рис.
3.2.
Формально этот принцип оптимальности можно записать следующим образом: Ф к(у)= min [ф( (yi)+= У2.4.
Общий случай Рассмотрим произвольное дихотомическое представление функции f(x), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами — вершины, соответствующие переменным Xj, i = I,n .
Рассмотрим множество конечных вершин, которые не являются висячими,
то есть их степень захода больше 1.
Разделим произвольным образом затраты ф](Х) на
kj частей, где kj число заходящих дуг.
Фактиче58

[Back]