Задача целочисленного линейного программирования. Метод ветвей и границ.

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

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

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) — целые числа.

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

Изложение метода Ленд-Дойга.

Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1). Если ее решение x(0;1) — целочисленный, то он же является и решением исходной ЦЗЛП. Иначе величина (0;1)=L(x(0;1)) дает нижнюю оценку (границу) целевой функции ЦЗЛП на множестве D(0;1)=D, что определяется соотношениями (13.2) (13.3).

Пусть некоторая координата x_j(0;1) (j=1...,n) решения x(0;1) не является целочисленной. В этом случае осуществляется разветвление множества D(0;1) на два подмножества D(1;1) и D(1;2) добавлениемк ограничениям, которые задают D(0;1), ограниченийx_j[x_j(0;1)] но x_j[x_j(0;1)]+1 соответственно, где [z] — целая часть числа z. Дальше Решаются новые вспомогательные ЗЛП с ограничениями, которые определяются подмножествами D(1;1) и D(1;2), находятся границе (1;1) но (1;2) и т.д.

Для последующего разветвления выбирается перспективное множество D(k;r) с наименьшей границею (k;r). Процесс продолжается до тех пор, пока не будет получено решение, которое удовлетворяет условие целочисленности и для которого выполняется признак оптимума (см. п. 4 алгоритма). В результате ограниченности допустимого множества ЗЛП (конечности допустимого множества ЦЗЛП) метод Ленд-Дойга конечный.

Алгоритм метода Ленд-Дойга.

1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления (см. пункт 5). На 0-м шаге возлагаемD(0;1)=D, гдеD задаетсяусловиями (13.2) (13.3).

2. Решаются вспомогательные ЗЛП на множествах D(k;r). Пусть x(k;r) — оптимальные решения указанных ЗЛП.

3. Вычисляются границы на множествах D(k;r) за формулой (k;r)= ]L(x(k;r))[, где ]z[ — наименьшее целое число, не меньше z.

4. Если существуют k, l такие, что x(k;l) — целочисленное решение и для всех веток r на k-у шаге выполняются соотношения

L(x(k;l))= (k;l)  (k;r)

то x* = x(k;l) — оптимальное решение ЦЗЛП.

5. Разветвление осуществляется по нецелочисленной компоненте xj(k;r) (с минимальным j) решения x(k;r), что отвечаетперспективной ветке k;r (если такихветок несколько, то выбирается ветка с минимальным r), добавлениемк D(k;r) одного из подмножеств xj[xj(k;r)] или xj[xj(k;r)]+1.

Программное обеспечение.

Обучающий модуль, с помощью которого задача целочисленного линейного программирования. Решается в диалоге с пользователем за выбранным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить методом ветвей и границ задачи целочисленного линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи (без использования программного обеспечения).

Во всех задачах выполняются условия: x_j0, x_j — целое, j=1,2.

1)	x1 + x2  max	2)		–2 x1 – x2  min	3)	6 x1 + 4 x2  min
	2 x1 + 11 x2  38			6 x1 + 4 x2  24		2 x1 + x2  3
	x1 + x2  7			x1 – x2  3		x1 – 2 x2  2
	4 x1 – 5 x2  5;			– x1 + 3 x2  3;		3x1 + 2x2  1;

4)	x1 + x2  min	5)	5 x1 + 7 x2  min	6)	2 x1 – x2  max
	– x1 – x2  – 1		– 10 x1 + x2  – 16		2 x1 + x2  8
	– 2 x1 + 2 x2  – 2		– 3 x1 – 3 x2  – 12		x1 + 3 x2  6
	– 4 x1 + 2 x2  – 1;		– 6 x1 – 2 x2  – 17		3 x1 + x2  3;

7)	x1 + 4 x2  min	8)	–5 x1 – 7 x2  max	9)	x1 + 2 x2 min
	x1 – 3 x2  –1		2 x1 + x2  3		2 x1 + 2 x2  5
	8 x1 – x2  6		20 x1 – x2  15		x1 – 3 x2  –1
	3 x1 – 11 x2  –7;		x1 – x2  –2;		x1 – x2  2.

Ответы:

1) x* = (3; 2) или x* = (2; 3), L(x*)= 5.

2) x* = (3; 1), L(x*)= –7.

3) x* = (1; 1), L(x*)= 10.

4) x* = (1; 0), L(x*)= 1.

5) x* = (4; 0), L(x*)=20.

6) x* = (3; 1), L(x*)= 5.

7) x* = (1; 1), L(x*)= 5.

8) x* = (1; 3), L(x*)= –26.

9) x* = (4; 2), L(x*)= 8.