Проиллюстрируем метод ветвей и границ на примере.

Решить задачу

Z = Зх1 + х2 — max

при ограничениях:

4xl + Зх2 < 18,

x1 + 2x2 £ 6,

0 £ x1 £ 5,

0 £ x2 £ 4,

х1, x2 — целые числа.

Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z0 = Z (0; 0) = 0.

I этап. Решая задачу симплексным методом, получим Zmax = 13 при Х1* = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х1* дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х1*, т.е. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:

Задача 2

Z=3x1+x2→max

при ограничениях:

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 4

0 £ x2 £ 4

х1, x2 — целые числа.

Задача 3

Z=3x1+x2→max

при ограничениях:

4xl + Зх2 < 18

x1 + 2x2 £ 6

5 £ x1 £ 5

0 £ x2 £ 4

х1, x2 — целые числа.

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0= 0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплексным методом.

Получим, что условия задачи 3 противоречивы.

III этап. Решаем задачу 2 симплексным методом. Получим Zmax = 14/3 при X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*) = 14/3 > Z0 = 0, по-прежнему сохраняется Z0 = 0, ибо план нецелочисленный. Так как х2* — дробное число, из области решений исключаем полосу 0 < x2 < 1 и задачу 2 разбиваем на две задачи 4 и 5.

Задача 4

Z=3x1+x2→max

при ограничениях:

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 4

0 £ x2 £ 0

х1, x2 — целые числа.

Задача 5

Z=3x1+x2→max

при ограничениях:

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 4

1 £ x2 £ 4

х1, x2 — целые числа.

Список задач: 4 и 5. Значение Z0 = 0.

IV этап. Решаем задачу 4 симплексным методом.

Получим Zmax = 12 при X4* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0 = Z(X4*) = 12, ибо план Х4* целочисленный.

V этап. Решаем задачу 5 симплексным методом.

Получим Zmax = 12,25 при X5* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не меняется, т.е. Z0 = 12, ибо план X5* нецелочисленный. Так как х1* — дробное, из области решений исключаем полосу 3<x1<4, и задача 5 разбивается на две задачи: 6 и 7.

Задача 6

Z=3x1+x2→max

при ограничениях:

4xl + Зх2 < 18

x1 + 2x2 £ 6

0 £ x1 £ 3

1 £ x2 £ 4

х1, x2 — целые числа.

Задача 7

Z=3x1+x2→max

при ограничениях:

4xl + Зх2 < 18

x1 + 2x2 £ 6

4 £ x1 £ 4

1 £ x2 £ 4

х1, x2 — целые числа.

Список задач: 6 и 7. Значение Z0 = 12.

VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.

Получим, что условия задачи 7 противоречивы.

VII этап. Решаем задачу 6 симплексным методом.

Получим Zmax = 10,5 ,при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5).

Так какZ(X6*) = 10,5 < Z0 = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X* = Х4* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax = 12

Замечание 1. Нетрудно видеть, что каждая последующая задача, составляемая в процессе применения метода ветвей и границ, отличается от предыдущей лишь одним неравенством — ограничением. Поэтому при решении каждой последующей задачи нет смысла решать ее симплексным методом с самого начала (с I шага). А целесообразнее начать решение с последнего шага (итерации) предыдущей задачи, из системы ограничений которой исключить "старые" (одно или два) уравнения — ограничения и ввести в эту систему "новые" уравнения — ограничения.

3.Применение метода ветвей и границ для задач календарного планирования

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

Рассмотрим применение разновидности метода ветвей и границ— метода «последовательного конструирования и анализа вариантов» для решения задачи календарного планирования трех станков.

Заданы п деталей di (i = 1, 2, ., n), последовательно обрабатываемых на трех станках R1, R2, R3, причем технологические маршруты всех деталей одинаковы. Обозначим ai ,bi ,ci — длительность обработки деталей di на первом, втором и третьем станках соответственно.

Определить такую очередность запуска деталей в обработку, при которой минимизируется суммарное время завершения всех работ Tц.

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

Обозначим sk = (i1, i2 , ., ik) — некоторую последовательность очередности запуска длиной k (1 £ k £ п) и A (sk), В (sk), С (sk) — время окончания обработки последовательности деталей sk на первом, втором и третьем станках соответственно.

Необходимо найти такую последовательность sопт, что

С(sопт) = min С (s).

s

Покажем, как можно рекуррентно вычислять A (sk), В (sk), С (sk). Пусть sk+1 = (sk ,ik+i), т. е. последовательность деталей sk+1 получена из деталей sk с добавлением еще одной детали ik+1. Тогда

A (sk+1) = A (sk)+,

В (sk+1) = max [A (sk+1); В (sk)] + ,

С (sk+1) = max [В (sk+1); С (sk)] +

Для задачи трех станков можно использовать следующее правило доминирования .

Если s — некоторая начальная последовательность, а — под последовательность образованная из s перестановкой некоторых символов, то вариант s доминирует над , когда выполняются следующие неравенства: