|
дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот принцип оптимальности можно записать следующим образом: фк(у)=(Л>У?у)[ф;(у*)+ф j(уi)]’ где р(у) множество пар (i,j), таких что (yj, yj)= у. Рассмотрим произвольное сетевое представление функции f(x), задаваемое сетью, выходом которой является вершина, соответствующая функции f(x), а выходами вершины, соответствующие переменным xj, i= l,n. Рассмотрим множество конечных вершин, которые не являются висячими, т.е. их степени захода больше 1. Разделим произвольным образом затраты cpi(Xf) на kjчастей, где к,*число заходящихдуг. Фактически мы как бы разделили вершину i на к; висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина со степеньюзахода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема: Теорема. Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. Доказательство. Заметим, что множество решений модифицированной сети содержит все решения исходной задачи. Эти решения имеют следующий вид. Если в вершину, соответствующую переменной х*, заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также принадлежат полученному решению. Отсюда следует, что полученное оптимальное решение модифицированной задачи дает нижнюю оценку для оптимального решения исходной задачи. 48 |
Несложно обобщить описанный метод на случай произвольного сетевого представления функции f(x) в виде дерева. Главное, чтобы задачи, соответствующие каждой вершине сетевого представления имели эффективные методы решения. В случае дихотомического представления это всегда имеет место. Заметим, что дихотомическое представление (см. рис. 2.4) имеет структуру в виде ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае дихотомического представления в виде дерева, является обобщением метода динамического программирования, расширяя круг задач, решаемых на основе данного подхода (Рис. 2.5). Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот принцип оптимальности можно записать следующим образом: а. Рис. 2.5. Иллюстрация методов программирования: а —динамического (ветвь дерева); б дихотомического (произвольное дерево). где р(у) множество пар (i, j), таких что fk(у*, yj) = у. 91 Общий случай Рассмотрим произвольное сетевое представление функции f(x), задаваемое сетью, выходом которой является вершина, соответствующая функции f(x), а выходами вершины, соответствующие переменным Xj, i = l,n . Рассмотрим ^ множество конечных вершин, которые не являются висячими, т.е. их степени захода больше 1. Разделим произвольным образом затраты (pi(Xj) на ki частей, где kj число заходящих дуг. Фактически мы как бы разделили вершину i на к; висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина со степенью захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая Теорема. Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. Доказательство. Заметим, что множество решений модифицированной сети содержит все решения исходной задачи. Эти решения имеют следующий # вид. Если в вершину, соответствующую переменной xik, заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также принадлежат полученному решению. Отсюда следует, что полученное оптимальное решение модифицированной задачи дает нижнюю оценку для оптимального решения исходной задачи. Пример. Рассмотрим сеть, представленную на рис. 2.1 и 2.2. На рис. 2.6 приведено решение соответствующей задачи. Затраты ф2(х2) разделены на две части, поскольку переменная х2 используется при вычислении функций и fj, и f2. В данном случае общие затраты, равные 8, 12 и 20 при значениях переменной х2, равных 1, 2 и 3, соответственно, поделены пополам. В каждой матрице кружками выделены клетки, соответствующие минимальным затратам на получение того или иного значения функций f(>f2и fo. В результате получены минимальные затраты (p(f0), требуемые для получения значений функции fo. Если fo= 1, то ср(1) = 16, если fo = 2, то ф(2) = 20, если fo = 3 , T O ф(3) = 28. Рассмотрим случай fo = 2. Ему соответствует оптимальное решение модифицированной задачи: xi = 1, x2i = 2, х22= 2, хз = 1. Здесь x2i соответствует значению Х2 в левой нижней матрице, а х22—в правой нижней матрице. Поскольку оба значения x2i = 2, х22= 2 вошли в опти92 |