МЕТОД ВЕТВЕЙ И ГРАНИЦ.

Постановка целочисленной задачи линейного программирования (ЦЗЛП).

Найти вектор x=(x₁...,xn), что минимизирует целевую функцию

L(x)= c₁x₁ + ... + c_nx_n (13.1)

и удовлетворяет систему ограничений

a₁₁x₁ + . . . + a_1n x_n R₁ a10

. . . . . . . . . . . . . . . . . . . . . . . (13.2)

a_m1x₁ + . . . + a_mnx_n R_m am0

x_j³0, j=1...,n (13.3)

x_j — цели, j=1...,n. (13.4)

где символ Ri (i=1...,m) заменяет один из знаков: £, =, ³.

Считается также, что многогранное множество, которое определяется соотношениями (13.2)–(13.3), ограниченная, а коэффициенты c_j целевой функции (13.1) — целые числа.

Дальше приводится алгоритм метода Ленд-Дойг, который представляет собой реализацию метода ветвей и границ для сформулированной выше задачи.