Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 31

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 25 26 27 28 29 30 < 31 > 32 33 34 35 36 37 .. 84 >> Следующая


21 = min(26 і; 22 i; 2l).

Далее разветвляем задачу с оценкой 23 по переменной г/g = 1/4. В результате ветвления получаем оценки

22 = min (^25|; 22 |; 22), 18 = min (26,5; 18; 24)

для подзадач г/g = 0 и г/g = 1 соответственно. Вершину с оценкой 18 можно отсеять по правилу отсева.
г/7 = О у% =^K

Рис. 3.5

OO

CO

Гл. 3. Метод ветвей и границ
90

Разд. II. Комбинаторные методы решения задач

После ветвления задачи с оценкой 23,5 и задачи с оценкой 23 получаем

19 < f(x°) < 22.

Перейдем к ветвлению задачи с оценкой 22 по переменной у® = і.

11

Получаем подзадачи с оценками 18 - и 18 -, которые также отсеиваем, при этом

19 < f(x°) < 21.

На данном этапе ветвления мы имеем две вершины с одинаковыми оценками 21 -. Для ветвления можно выбрать любую, например

подзадачу у® = у% =0. Произведем ветвление по переменной у® = і и получим оценки

19 \ = min (25; 19 р 21±) , 21 = min (26 |; 23 |; 2l)

для ^ = 0и^ = 1 соответственно. Вершину с оценкой 19 - можно

О

отсеять, так как во всех последующих вершинах, с ней связанных, значение целевой функции не может быть больше 19 (все Cj — целые

числа). Вернемся к подзадаче у® = 0, у% = 1 с оценкой 21 - и произведем ветвление ПО переменной Уд = і. В результате получим оценки

20 і = min (27|; 20|; 2l) , 21 = min (27; 21; 24 |)

для подзадач у^ = 0 и уд = 1 соответственно.

На данном шаге ветвления мы имеем три вершины с одинаковыми оценками 21. Для дальнейшего ветвления выбирается вершина, у которой число переменных, зафиксированных на своих значениях, больше. Выберем одну из подзадач для у® = 0, например подзадачу Уі = 1. Решение третьей линейной задачи

у0’3 = (I; 1; 0; 0; 0; 0; 0; 0; I; 1),

давшей минимальное значение целевой функции, не содержит дробных компонент, поэтому ветвление производится по переменной, соответствующей максимальному значению Cj среди незафиксированных. После ветвления этой задачи по девятой переменной получаем оценки

17 і = min (26; 20; 17 і) , 21 = min (26, 5; 22; 21)

для уд = 0 и уд = 1 соответственно. Вершину с оценкой 17 і отсеиваем

и переходим к ветвлению вершины с оценкой 21. Решение третьей линейной задачи снова не содержит дробных компонент, производим ветвление по второй переменной и получаем оценки

17 \ = min (26; 23 І; 17, 21 = min (26, 5; 22; 21).

о \ Zo/
Гл. 3. Метод ветвей и границ

91

Вершину с оценкой 17 - отсеиваем и разветвляем вершину с оценкой 21. Решение третьей линейной задачи совпадает с предыдущим, производим ветвление по шестой переменной. Задача со значениями 2/5 = у 8 = О, у I = У 2 = Vq = Vq = 1 НЄ ЯВЛЯЄТСЯ ДОПУСТИМОЙ для третьего ограничения. Для подзадачи у q = 0 получаем то же решение и оценку 21. После ветвления по седьмой переменной для подзадачи 2/7=0 получаем оценку 19,5 и отсеиваем эту вершину. Задача со значениями у® = у^ = у% = 0, у® = у® = у® = у§ = 1 не является допустимой для третьего ограничения.

Вернемся к подзадаче у® = 0, у% = yg = 1 с оценкой 21. Решение второй задачи

у0,2 = (1; 0; 0; 0; 0; 0; 0; I; 1; 0) не содержит дробных компонент, производим ветвление по первой переменной. Задача у® = 0, у® = у$ = yjj = 1 не является допустимой для третьего ограничения. Для подзадачи у° = 0 получаем оценку

19 = min ^26; 19; 24 ,

причем решение второй линейной задачи, давшей минимальной значение целевой функции, совпадает с допустимым решением всей задачи

= (0; 0; 0; 0; 0; 0; I; I; 1; 0).

Теперь вернемся к подзадаче у® = у§ = 1 с оценкой 21. Решение третьей задачи

у0'3 = (0; 1; 0; 0; I; 1; 0; 0; 1; 0) не содержит дробных компонент, поэтому производим ветвление по восьмой переменной. Задача у® = у§ = у% = 1 не является допустимой для второго ограничения. Для подзадачи у% = 0 получаем оценку

21 = min (26; 22,5; 21),

и разветвляем эту вершину по девятой переменной, соответствующей максимальному Cj из незафиксированных. Для подзадачи у^ = 0 получаем оценку 18, 5 — эту вершину можно отсеять. Для подзадачи у§ = = 0 получаем то же решение и оценку 21. После ветвления по первой переменной для подзадачи у® = 0 получаем оценку

20 = min (24, 5; 20; 21).

Задача у% = 0, у® = у® = у§ = у^ = 1 не является допустимой для третьего ограничения.

В результате выполнения ветвлений получаем

19 < f(x°) < 20.

Вернемся к вершине с оценкой 20 І. После ветвления по пере-

1 2

менной уq = - получаем вершины с оценками 19 - и 19 для подзадач

Z О

уq = 0 и уq = 1 соответственно, которые можно отсеять (для вершины
92

Разд. II. Комбинаторные методы решения задач

с оценкой 19 решение у0,2 = (1; 0; 0; 0; 0; 1; 0; 1; 0; 0) второй линейной задачи, давшей оценку, не является допустимым планом всей задачи).

После ветвления оставшейся вершины с оценкой 20 по второй переменной для подзадачи = 0 получаем вершину с оценкой 19, которую отсеиваем, так как решение второй линейной задачи

у0,2 = (0; 0; 0; 0; I; I; 1; 0; 1; 0)

не является допустимым для всей задачи. Задача у® = у $ = 0, 2/2 = = Уь = У6 = У9 = яе является допустимой для второго ограничения.
Предыдущая << 1 .. 25 26 27 28 29 30 < 31 > 32 33 34 35 36 37 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100