Комбинаторные методы: метод ветвей и границ

, где - конечное множество

- оценка функции :

Если - оптимальное решение задачи. В противном случае возможно разбиение (ветвление) множества на конечное число непересекающихся подмножеств : и вычисление оценки . Способ ветвления определяется спецификой задачи.

; - оценка функции

;

; - max (min)

;

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

; - оценка

;

; - max (min)

;

;

;

; - max (min)

;

Пример 4: Контейнер объёмом 5 помещён на контейнеровоз грузоподъёмностью 12 . Контейнеровоз требуется заполнить грузом двух наименований. Масса единицы груза (в тоннах), объём груза (в , стоимость (в ден. Ед.) приведен в таблице:

j
1	3	1	10
2	1	2	12

Требуется загрузить контейнер таким образом, чтобы стоимость перевозимого груза была максимальной.

, разбивают D на и (D= ):

,

Линии разбиения:

Для определения и решают две ЗЛП:

;

удовлетворяет условиям задачи; для него выполняется условие:

. План - оптимальный.

Аналитическое решение ЗЦП (метод Гомори):

Б		10	12	0	0	max
						B
	0	3	1	1	0	12	4	12
	0	1	2	0	1	5	5	2,5
		-10	-12	0	0	0	40	30
	10	1			0	4	-	12
	0	0			1	1	-
		0			0	40	-
	10	1	0
	12	0	1
		0	0			45

порождающая строка

, точка О;

, точка C;

, точка B;

, точка F;

Б		10	12	0	0	0	B	[ ]
	10	1	0			0		3
	12	0	1			0
	0	0	0					отсечение Гомори
		0	0			0	45
	10	1			-1	1	3
	12	0			1		1
	0	0	0	1	2		2
		0			2	4	42

+ + … + +…+ =

(1+ 0) + ([ ] + ) + … + ([ ] + ) + … +([ ] + ) = [ ] +

• [ 0 + + … + + … + ] + = -

(не является допустимым решением)