|
приведено решение соответствую щ ей задачи. Затраты фгСхг) разделены на две части, поскольку переменная Хз используется при вы числении ф ункций и fi, и 13. В данном случае общ ие затраты, равные 8 , 12 и 20 п р и значениях переменной Х2, равных 1, 2 и 3, соответственно, поделены пополам. В каждой матрице кр уж ка м и выделены клетки, соответствую щ ие м и н и мальным затратам на получение того или иного значения ф ункций fj, f2 и fo. В результате получены минимальные затраты ф(fo), требуемые для получения значений ф ункции fo. Е сли f o = l , то ф (1 )= 1 6 , если fo = 2, то ф(2) = 20, если fo = 3,To ф(3) = 28. Рассмотрим случай fo = 2. Е м у соответствует оптимальное решение м одифицированзюй задачи: x i = 1 , X2j = 2 , Х22 = 2 , хз = 1 . Здесь Х21 соответствует значению хт в левой ниж ней матрице, а X22 —в правой ниж ней хматрице. П оско л ьку оба значения Х21 —2, Х22 = 2 вош ли в оптимальное решение модиф ицированной задачи, то полученное решение является допустимы м для исходной задачи, а значит, м ы получили оптимальное решение исходной задачи. Д ругая ситуация возникает в случае fo = 3. О птимальное решение модиф ицированной задачи имеет вид: Х] = 1, X2i = 2, Х22 = 3, Х3 ==2 с величиной затрат Фо = 28. Это решение не является допустимы м для исходной задачи, поэтому значение (ро = 28 является ниж ней оценкой м иним альны х затрат для исходной задачи. Здесь возможны два варианта действий. П ервы й заключается в попы тке улучш ить н и ж н ю ю оценку, изменяя разбиение затрат сг = (рзСхз) на две части — С21 и С22Очевидно, что для улучш ения оценки следует часть С21 увеличить, а часть С22 уменьш ить. Возьмем, например, С 21 = 10, а С22 ==2. В этом случае оптихмальное решение модиф ицированной задачи будет иметь вид: X = 1 , Х21 = 2 , Х22 = 2, Хз = 3 с затратами фо = 31. Это решение является допустим ы м для и сходной задачи, а значит, оптимальным. О днако изменение разбиения затрат на части может и не привести к получению допустихмого реш ения для исходной задачи. 68 |
ски мы как бы разделили вершину 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 3 / / 2 0 2 / / 2 1 2 / / 2 9 3 / / 3 7 2 / / и 1 / / l 8 / / 1 / / 9 % 1 / /1 8 2 / /2 6 у / / I / / 7 2 / / 9 3 / /1 7 3 28 2 20 1 16 fl 3 / / 5 2 / /1 9 3 / /2 1 3 / /гъ 3 / /1 0 2 / / з 3 / /2 4 2 / /1 0 1/ /1 4 2 / / б /4 ) 2 / / 6 2 / У® 2 У / з 3 / /2 0 1 / / 5 1 / У ® 2 / / 5 1 / / 4 1 / У® 1 / / и 2 / / l 8 х / / *2 I / / 4 2 / / 6 3 / / ю х / / Хз 1 / / з 2 / / 7 3 / / 4 Рис. 4.1. Другая ситуация возникает в случае fo = 3. Оптимальное решение модифицированной задачи имеет вид: ^1 “ 1»Х21 = 2, Х22= 3, Хз = 2 с величиной затрат фо = 28. Это решение не является допустимым для исходной задачи, поэтому фо= 28 является нижней оценкой минимальных затрат для исходной задачи. Здесь возможны два варианта действий. Первый заключается в попытке улучшить нижнюю оценку, изменяя разбиение затрат С2= фг(х2) на две части С21 и С22. Очевидно, что для улучшения оценки следует С21увеличить, а С22уменьшить. Возьмем, например, С21= 10, а С22= 2. В этом случае оптимальное решение модифицированной задачи будет иметь вид: X l= 1,Х21 = 2 , Х22 = 2, Хз = 3 С величиной затрат фо = 31. Эго решение является допустимым для исход60 ной задачи, а значит оптимальным. Однако, изменение разбиения затрат на части может и не привести к получению допустимого решения для исходной задачи. Второй вариант состоит в применении метода ветвей и границ. Разобьем множество всех решений исходной задачи на два подмножества. В первом Х2^ 2, а во втором хг = 3 и применим описанный выше алгоритм. Получим оценку снизу для первого подмножества. Получаем следующее решение: Х = 1,Х2 = 2, Х22 = 2, Х з = 3 с величиной затрат фо“ 31. Получим оценку снизу для второго подмножества. Оптимальное решение модифицированной задачи имеет вид: X, = 1,X2 = 3 ,X j = 2 с величиной затрат фо= 32. Выбираем первое подмножество с минимальной оценкой. Поскольку полученное решение модифицированной задачи является допустимым для исходной задачи, то оно является оптимальным. Рассмотрим на ряде задач построение оценочной задачи и метод ветвей и границ на основе полученной оценки. 2.5. Задача целочисленного линейного программирования Рассмотрим следующую постановку задачи целочисленного линейного профаммирования. Определить целочисленный неотрицательный вектор X = {x i,Х2, ....Х4} максимизирующий 9 (x ) = 2]ciX i (5.1) i=I При ограничениях ^ a jjX i^ b j, j = l,m (5.2) i Для построения оценочной задачи разделим Ciна m частей Sjj, так что (5.3) 61 |