|
Здесь Х2 соответствует значению Х2в левой нижней матрице, а Х22в правой нижней матрице. Поскольку оба значения Х21 = 2, Х22= 2 вошли в оптимальное решение модифицированной задачи, то полученное решение является допустимым для исходной задачи, а значит, мы получили оптимальное решение исходной задачи. Другая ситуация возникает в случае ^ = 3. Оптимальное решение модифицированной задачи имеет вид: XI = 1, Х21 = 2, Х22= 3, х3= 2 с величиной затрат фо= 28. Это решение не является допустимым для исходной задачи, поэтому значение фо= 28 является нижней оценкой минимальных затрат для исходной задачи. Здесь возможны два варианта действий. Первый заключается в попытке улучшить нижнюю оценку, изменяя разбиение затрат С2= Ф2(*2) на две части С21 и С22. Очевидно, что для улучшения оценки следует часть С21 увеличить, а часть С22уменьшить. Возьмем, например, С21 = 10, а С22= 2. В этом случае оптимальное решение модифицированной задачи будет иметь вид: Х1 = 1, Х21 = 2, Х22= 2, х3= 3 с затратами ф0= 31. Это решение является допустимым для исходной задачи, а значит, оптимальным. Однако изменение разбиения затрат на части может и не привести к получению допустимого решениядля исходной задачи. Второй вариант состоит в применении метода ветвей и границ. Разобьем множество всех решений исходной задачи на два подмножества. В первом из них Х2^ 2, а во втором Х2= 3, и применим описанный выше алгоритм. Получим оценку снизу для первого подмножества. Получаем следующее решение: X] = 1, Х21 =2, Х22=2, х3= 3 с затратами фо= 31. Получим оценку снизу для второго подмножества. Оптимальное решение модифицированной задачи имеет вид: XI 1, Х2= 3, х3= 2 с величиной затрат фо—32. Выбираем первое подмножество с минимальной оценкой. Поскольку полученное решение модифицированной задачи является допустимым для исходной задачи, тооно оптимально. 50 |
мальное решение модифицированной задачи, то полученное решение является допустимым для исходной задачи, а значит, мы получили оптимальное решение исходной задачи. 3 / / 2 0 2 / / 2 7 2 X / 2 9 3 / / 3 7 2 / / 1 1 / 4 > / 4 ) 1 / / 9 % 1 / / 1 8 2 / / 2 6 л / / Уг 1 / / 7 2 / / 9 3 / / 1 7 3 28 2 20 1 16 Гг 3 / / 1 5 2 / / 1 9 3 / / 21 3 / / 2 5 3 / / 10 X % 3 / / 2 4 2 / / ю 1 / / 1 А 2 / / 1 6 / 4 > 2 / / б 2 / / ® 2 / / 1 3 3 / / 2 0 1 / / 5 1 / / ® % > / й 1 / / 4 1 / / О ) X 2 X / l 8 х ' / / Х2 1 / / А 2 / / 6 3 / / ю XI / / Xi 1 / / з 2 / / 7 3 / / 1 4 Рис. 2.6. Решение оценочной задачи методом сетевого программирования Другая ситуация возникает в случае f0= 3. Оптимальное решение модифицированной задачи имеет вид: Х = 1, х21 = 2, х22= 3, Хз = 2 с величиной затрат сро= 28. Это решение не является допустимым для исходной задачи, поэтому значение фо —28 является нижней оценкой минимальных затрат для исходной задачи. Здесь возможны два варианта действий. Первый заключается в попытке улучшить нижнюю оценку, изменяя разбиение затрат с2= Фг(х2) на две части c2i и с22. Очевидно, что для улучшения оценки следует часть c2i увеличить, а часть си уменьшить. Возьмем, например, c2i = 10, а с22= 2. В этом случае оптимальное решение модифицированной задачи будет иметь вид: xi = l, x2i = 2, Х22= 2, Хз = 3 с затратами фо = 31. Это решение является допустимым для исходной задачи, а значит, оптимальным. Однако изменение разбиения затрат на части может и не привести к получению допустимого решения для исходной задачи. Второй вариант состоит в применении метода ветвей и границ. Разобьем множество всех решений исходной задачи на два подмножества. В первом из них х2 < 2, а во втором х2= 3, и применим описанный выше алгоритм. Получим 93 оценку снизу для первого подмножества. Получаем следующее решение: Xi = 1, Х21= 2, Х22—2, Х3= 3 с затратами фо = 31. Получим оценку снизу для второго подмножества. Оптимальное решение модифицированной задачи имеет вид: х, = 1,х2= 3, х3= 2 с величиной затрат фо = 32. Выбираем первое подмножество с минимальной оценкой. Поскольку полученное решение модифицированной задачи является допустимым для исходной задачи, то оно оптимально. Рассмотрим на ряде задач построение оценочной задачи и метод ветвей и границ на основе полученной оценки. Задача целочисленного линейного программирования Рассмотрим следующую постановку задачи целочисленного линейного программирования. Определить целочисленный неотрицательный вектор х “ {xi, Х2.......Х4}, максимизирующий функцию ф(х) = £ с , х, (2.4) i-l при ограничениях X a ijx i ^ b j> J = 1»m (2-5) Для построения оценочной задачи разделим Cj на ш частей Sy так, что 5 > и= с р i = 1,п (2.6) j и рассмотрим ш задач целочисленного линейного программирования следующего вида: определить целочисленный вектор х, максимизирующий функцию sj(x ) = E s ex > (2 *7) i при ограничениях X a ijxi bj. (2.8) i Обозначим через Oj(Sj) оптимальное решение j -й задачи (Sj = {sy}). Согласно теореме, величина Ф О О = 2 > , У (2 .9 ) i-i 94 |