Применение метода ветвей и границ для задач календарного планирования (стр. 3 из 3)
Тогда
∆ (s = 0) = max {17, 17,14} = 17.
2) Первый шаг. Конструируем все возможные последовательности длиной 1
s1(1) = 1; s2(1) = 2; s3(1) = 3; s4(1) = 4; s5(1) = 5.
Находим:
dA(1) = A1 +
+ 
= 14 + 3 = 17;dB(1) = В1 +
+ 
= 5 + 12 + 2 = 19;dC(1) = С1 +
= 9 + 10 = 19 .Откуда ∆ (1) = max {17, 19, 19} = 19.
Аналогично определяем ∆ (2), ∆ (3), ∆ (4), ∆ (5).
3) Второй шаг. Среди множества подпоследовательностей длиной 1, s1(1) = 1, s2(1) = 2,..., s5(1)= 5 выбираем наиболее перспективную s = 1, для которой величина оценки-прогноза ∆ (s) оказывается наименьшей. Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2), (1.3), (1.4), (1.5).
Для каждого из этих вариантов вновь определяем оценки по формулам (21) — (24).
Процесс вычислений продолжаем аналогично.
Процесс построения дерева вариантов приведен на рис. 1.
Рисунок 1
Каждой конечной вершине дерева вариантов будет отвечать полная последовательность s = i1,i2,,.in. Если для некоторой такой вершины величина оценки ∆ (s) не превосходит величины оценок для всех остальных вершин, то эта оценка определяет искомый оптимальный вариант. В противном случае разбиваем более перспективный вариант с наилучшей оценкой.
Конечная вершина определяет вариант (последовательность)
= 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:
.1. Акулич И.Л. Математическое программирование в примерах и задачах. М., Высшая школа, 1993.
2. Гончаренко В.М. «Математические методы и модели операций. Руководство к решению задач». М., Финансовая Академия, 2006.
3. Зайченко Ю.П. Исследование операций. Киев, Высшая школа, 1975.
4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М., Высшая школа, 1980.
5. Шкурба В.В. Задача трех станков. М., Наука, 1976.
Решение задачи
z = 4х1 + х2 +1 ® max при ограничениях:
симплекс-методом:
| базис | bi | x1 | x2 | x3 | x4 | x5 | x6 |
| x3 | 4 | 1 | 2 | 1 | 0 | 0 | 0 |
| x4 | 12 | 3 | 2 | 0 | 1 | 0 | 0 |
| x5 | 3 | 1 | 0 | 0 | 0 | 1 | 0 |
| x6 | 3 | 0 | 1 | 0 | 1 | 0 | 1 |
| z | 1 | -4 | -1 | 0 | 0 | 0 | 0 |
| x2 | 2 | 0,5 | 1 | 0,5 | 0 | 0 | 0 |
| x4 | 8 | 2 | 0 | -1 | 1 | 0 | 0 |
| x5 | 3 | 1 | 0 | 0 | 0 | 1 | 0 |
| x6 | 1 | -0,5 | 0 | -0,5 | 0 | 0 | 1 |
| z | 3 | -3,5 | 0 | 1 | 0 | 0 | 0 |
| x1 | 4 | 1 | 2 | 1 | 0 | 0 | 0 |
| x4 | 0 | 0 | -2 | -2 | 1 | 0 | 0 |
| x5 | -1 | 0 | -2 | -1 | 0 | 1 | 0 |
| x6 | 3 | 0 | 1 | 0 | 0 | 0 | 1 |
| z | 17 | 0 | 7 | 4,5 | 0 | 0 | 0 |
| x1 | 3 | 1 | 0 | 0 | 0 | 1 | 0 |
| x4 | 1 | 0 | 0 | -1 | 1 | -1 | 0 |
| X2 | 0,5 | 0 | 1 | 0,5 | 0 | -0,5 | 0 |
| x6 | 2,5 | 0 | 0 | -0,5 | 0 | 0,5 | 1 |
| z | 3,5 | 0 | 0 | 1,5 | 0 | 3,5 | 0 |
z*=13,5,Х1*=(3;0,5;0;1;0;2,5).
Решение задачи z = 4х1 + х2 +1 ® max при ограничениях:
с помощью табличного процессора MicrosoftExcel.
Приложение 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 < 18x1 + 2x2£ 6
0 £ x1£ 4
0 £ x2£ 0
х1, x2 — целые числа.
Задача 5
Z=3x1+x2→max
при ограничениях:
4xl + Зх2 < 18x1 + 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]Естественно, без введения и вычисления переменных искусственного базиса.
[3]«о трех станкак».