Метод ветвей и границ

Метод ветвей и границ является одним из наиболее широко применяемых комбинаторных методов. Данный метод можно представить в виде следующих этапов:

1 этап: решение исходной задачи с ослабленными ограничениями симплекс-методом.

Пусть задана исходная задача линейного целочисленного программирования (6.1). Данная задача решается, к примеру, симплекс-методом без учета условий целочисленности проектных параметров (задача с ослабленными ограничениями).

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

Если среди найденных оптимальных значений проектных параметров, в отношении которых распространяется условие целочисленности в исходной задаче, имеются дробные значения, то переходят к следующему этапу. Для последующего сравнительного анализа введем переменную F ₀, которой условно присвоим F ₀ := – ∞ в случае максимизации целевой функции или F ₀ := + ∞ в случае минимизации целевой функции.