|
67 ный выше алгоритм. П ри этом каж ды й раз, когда встречается верш ина со степенью захода больше 1, мы делим затраты на соответствующ ее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. О днако это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая Т еорем а. Полученное с пом ощ ью выш еописанного алгоритма решение дает н и ж н ю ю оценку оптимального реш ения исходной задачи. Д оказа т е л ьст во . Заметим, что множество реш ений модиф ицированной сети содержит все реш ения исходной задачи. Э ти реш ения им ею т следую щ ий вид. Если в вершину, соответствую щ ую переменной Xjk, заходит хотя бы одна дуга полученного решения, то все д уги, заходящие в эту верш ину, такж е п р и надлежат полученному реш ению . О тсюда следует, что полученное оптимальное решение модиф ицированной задачи дает н и ж н ю ю оценку для оптимального решения исходной задачи. П р и м е р . Рассмотрим сеть, представленную на рис. 2.1 и 2.2. Н а рис. 2.6 /, 15 10 '19 '14 У ® 3 / / 2 0 2 / / 2 9 / 2 / / 1 1 / 4 1 / / 9 ^ /4 ) 1/ " / 1 8 2 У / 2 6 X \ / / 7 2 У / 9 © /о 3 28 2 20 16 '21 16 '25 15 у у у © 2 у /®у 3 у / 2 0 У 1 / /®у 2 у / 4 8 у у у X Рис. 2.6. Решение оценочной задачи методом сетевого проф аммирования |
ски мы как бы разделили вершину i на к; висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина, имеющая степень захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако, это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема. Теорема 4.1. Полученное с помощью вышеописанного алгоритма решение дает нижнюю оценку оптимального решения исходной задачи. Доказательство. Заметим, что множество решений модифицированной сети содержит все решения исходной задачи. Эти решения имеют следующий вид. Если в вершину, соответствующую переменной Хк заходит хотя бы одна дуга полученного решения, то все дуги, заходящие в эту вершину, также принадлежат полученному решению. Отсюда следует, что полученное оптимальное решение модифицированной задачи дает нижнюю оценку для оптимального решения исходной задачи. Пример 4.1. Рассмотрим сеть рис. 2.1, 2.2. На рис. 4.1 приведено решение задачи. При этом затраты ф2(хг) разделены на две части, поскольку переменная Х2 используется и при вычислении fi, и при вычислении Гг. В данном случае общие затраты, равные 8, 12 и 20 при значениях переменной Х2равной 1,2 и 3, соответственно, поделены пополам. В каждой матрице выделены клетки, соответствующие минимальным затратам на получение того или иного значения функций (fi, Гг и Го). В результате получены минимальные затраты ф(Го), требуемые для получения значений функции fo. Если Го= 1, то ф(1) = 16, если Го= 2, то ф(2) = 20, если Го= 3, то ф(3) = 28. Рассмотрим случай Го= 2. Ему соответствует оптимальное решение модифицированной задачи: xj = 1, X21= 2, Х22= 2, хз = 1. Здесь Х21соответствует значению Хг в левой нижней матрице, а X22в правой нижней матрице. Поскольку оба значения Х21= 2, Х22= 2 вошли в оптимальное решение модифицированной задачи, то полученное решение является допустимым для исходной задачи, а значит мы получили оптимальное решение исходной задачи. 59 |