ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ВЫБОРА.

Рассчитаем :

Рассчитаем :

Рассчитаем :

Рассчитаем :

Рассчитаем :

Все дуги по которым были получены минимальные значения должны быть на графике выделены.

Очевидно, что суммарная минимальная стоимость производства и изделий составит 70,5 д.е. Чтобы получить оптимальный вектор Х необходимо соединить в одну линию по графику начиная с узла (5,5) выделенные дуги, соединяя разрывы горизонтальными. В приведенном примере этот вектор будет иметь вид: .

Получено оптимальное решение:

Т.е., минимальные издержки производства составят 70,5 д.е., если будет изготовлено изделий 2 вида 7 штук и изделий 5 вида 11 штук.

Унификация удалась, т.е. количество типов в оптимальном решении уменьшилось с 5 до 2. при этом стоимость изготовления изделий сократилась на 15,5 д.е., что составляет 18% от первоначальной стоимости.

ПРИМЕНЕНИЕ МЕТОДА ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ВЫБОРА.

Некоторые задачи в менеджменте это задачи принятия обоснованных управленческих решений при выборе наилучшего варианта из конечного множества возможных альтернатив.

Наиболее общий метод решения таких задач это метод ветвей и границ (МВГ). Метод представляет собой последовательность действий:

1) Все множества вариантов представляется в виде дерева, конечные вершины которого соответствуют конкретным вариантам; каждая ветвь дерева отвечает подмножеству возможных вариантов.

2) На каждой ветви (подмножестве), вводится функция φ, являющаяся верхней (при поиске максимума) или нижней (при поиске минимума) границей целевой функции.

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

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

Этот метод целесообразно применять при решении таких задач как:

– Задача о ранце,

– Задача унификации,

– Задача коммивояжера,

– Задача о замене оборудования и др.