Применение метода ветвей и границ для задач календарного планирования
Решение задачи z = 4х1 + х2 +1 ® max при ограничениях:
с помощью табличного процессора Microsoft Excel.

Приложение 3
В качестве примера применения метода ветвей и границ приведем поиск оптимального значения функции 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,5 при Х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 = 12 2/3 при X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*) = 12 2/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 «Оптимальным» будем называть план, оптимальный на данный момент решения.
2 Естественно, без введения и вычисления переменных искусственного базиса.
1 «о трех станкак».
30