Реферат: Применение метода ветвей и границ для задач календарного планирования
2°. Составляют дополнительные ограничения для одной из пере-менных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
3°. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
4°. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(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 при Х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 симплексным методом.