Лекция: Метод ветвей и границ. Общая схема Задача целочисленного линейного программирования

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

Метод применяют к задачам:

, (1)

для которых выполняются два предположения:

1. множество планов и любое его подмножество можно дробить (ветвить) на более мелкие, (причём дробление должно быть таким, чтобы во-первых, попарное пересечение более мелких подмножеств было пустым, а во-вторых, в объединении они должны давать дробимые подмножества).

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