Для решения ЗЛЦП существует 3 группы методов:

1) Методы отсечения или отсекающих плоскостей

2) Комбинаторные методы

3) Эвристические методы

Познакомимся с одним из универсальных и наиболее эффективных методов 2-ой группы – методом ветвей и границ. Комбинаторные методы – это методы целенаправленного упорядоченного перебора. Общая идея методов заключается в замене полного перебора всех возможных вариантов частичными переборами значительно меньших объемов. Комбинаторные методы эффективны при решении ЗЛП, ЗЛЦП, динамического программирования, нелинейного программирования и др. Наиболее эффективным и распространенным методом является метод ветвей и границ.

Идею метода рассмотрим на примере мешка с монетами, в котором есть одна фальшивая, отличающаяся большим весом. Рассмотрим задачу дискретного программирования в общем виде. Для функции необходимо найти max при условии , где D⁽¹⁾ – некоторое конечное или счетное множество, f – функция любого вида. Часто удается найти верхнею границу или оценку целевой функцию Z на множестве D⁽¹⁾ . Эту оценку будем обозначать j( D⁽¹⁾) и называть оценкой множества D⁽¹⁾. Она будет удовлетворять условию:

Рассмотрим схему метода ветвей и границ по шагам:

Исходный, или нулевой шаг

Находим оценку j( D⁽¹⁾). Если при этом удалось найти такой план и для которого , то — оптимальный план. Если оптимальный план не найден, то переходим к 1 шагу.

Множество D⁽¹⁾ некоторым образом разбиваем на конечное число непересекающихся подмножеств в D_i⁽¹⁾, таких что и . Затем вычисляем верхние границы или оценки этих подмножеств.

Если при этом удалось найти такой план , где r=[1,r], который удовлетворяет условиям: , то план является оптимальным.

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

Пусть это будет подмножество D_n⁽¹⁾ и для него j( D_n⁽¹⁾) j( D_i⁽¹⁾)

— — — — — — — — — — — — —

К шаг (К=2, 3,…..)

" К=2 D_n⁽¹⁾ некоторым образом разбивают на конечное число непересекающихся подмножеств D_n,i⁽¹⁾, и затем все неподвергающиеся делению подмножества переобозначаем:

На К – ом шаге будем иметь конечное число неподвергающихся делению подмножеств . Вычислим оценки этих подмножеств j( D_i^(К)). Если при этом удалось найти такой план , что , то – оптимальный план.

и т. д.

Схематически процесс нахождения оптимального плана можно изобразить в виде графа:

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

Авторами метода ветвей и границ является 4 американских математика: Литл, Мурти, Суини и Кэрол, которые разработали его в 1963 г. при решении задачи Комивояжора.