Пример использования метода ветвей и границ

В качестве примера к методу ветвей и границ рассмотрим функцию z=4х1+х2+1®max (7) при ограничениях:

(8). x1, x2 Î Z, (9).

Пусть Х0 = (0; 0), z0 = 1 - «оптимальное» решение (10). Выполним 1-й этап общего алгоритма и найдем с помощью симплекс-метода, а затем и двойственного симплекс-метода (см. Приложение 1) X1, исходя из ограничений (8). Итак, X1 = (3; 0,5; 0; 1; 0; 2,5), z1 = 13,5 (11). Так как z1 дробное, то «оптимальным» так и остается план Х0,

Согласно 2-му пункту нашего плана, составим 2 новых системы ограничений для (7):

(12) и (13).

Выполним 3-й пункт алгоритма. Для начала, решим задачу (7), (12) с помощью табличного процессора Microsoft Excel (см. Приложение 2) и получим X2 = (2; 1), z2 = 10 (14). Так как z2 ≥ z0, «оптимальным» становится план Х0.

Решим задачу (7), (13). Из последнего уравнения очевидно, что x2 = 0. Отсюда следует, что x1 = 3 (максимально возможное). Тогда Х3 = (3; 0), z3 = 13 (15), а следовательно, данный план является оптимальным (теперь уже без кавычек).

Нам не пришлось выполнять 4-й пункт нашего алгоритма в связи с тем, что оптимальное решение найдено, переменные целочисленные. К тому же, все необходимые моменты решения уже были показаны в пунктах 1-3.

Пример, в котором всё складывается не так просто, приведен в Приложении 3.

календарное планирование программирование