2. Метод ветвей и границ

Для иллюстрации основных принципов этого метода рассмотрим следующую задачу ЦЛП:

Пример 2.18:

Найти max

1. Решим эту задачу, отбросив условие целочисленности, любым методом линейного программирования.

Обозначим эту задачу ЛП-1

Так как х₂– не целочисленно, решение не является решением исходной задачи, но представляет собой верхнюю границу оптимального целочисленного решения, то есть при достижении целочисленности х₂значения целевой функции может лишь ухудшиться.

Из условия не целочисленности х₂переходим к следующему шагу, который состоит в просмотре целочисленных значений х₂, больших или меньших полученного оптимального значения, путем добавления к задаче ЛП-1 нового ограничения, полученного округлением не целочисленного оптимального значения в большую или меньшую сторону.

В нашем случае вводиться ограничение х₂1 или х₂2.

Таким образом, из задачи ЛП-1 получается две задачи

ЗЛП-2

ЗЛП-3

Для ЗЛП-2 оптимальное решение:

Для ЗЛП-3 оптимальное решение

Оптимальное решение ЗЛП-3 больше, чем ЗЛП-2, однако условие целочисленности выполняется только во второй задаче, следовательно, оптимальное решение ЗЛП-2 можно считать нижней границей оптимального целочисленного решения.

То есть, если будут найдены другие целочисленные решения, значение функции которых будет меньше этой нижней границы (то есть = 8), то такие решения не будут оптимальными, их необходимо исключать из дальнейшего рассмотрения.

Так как верхняя граница = 9, а решение задачи ЛП-3 находится внутри диапазона от нижней до верхней границы, то нельзя утверждать, что ЛП-2 оптимальна для исходной задачи, следовательно, необходимо проанализировать задачу ЛП-3.

Так как в ЗЛП-3 х₁имеет не целочисленное значение, то в ЗЛП-3 необходимо добавить ограничения

ЗЛП-4

ЗЛП-5

Решение ЗЛП-4:

Полученное решение не превосходит нижней границы из ЛП-2 (= 8), следовательно, дальнейшее исследование данной ветви прекращаем.

ЗЛП-5 не имеет допустимых решений, следовательно, решение задачи ЛП-2, то есть

- является оптимальным для исходной задачи.

Последовательность задач ЛП, возникающих при использовании процедуры ветвей и границ удобно представить в виде дерева следующего вида:

Рис. 2. 14

Пример 2.19:

Найти решение ЗЦЛП методом ветвей и границ.

Исходная ЗЛП выглядит следующим образом:

- канонический вид.

			х2
						(1)
							(4)
				(3)
					(2)
							х1

Рис. 2.16

Решение:

Так как х₁и х₂ - нецелые, данное решение не является решением исходной задачи.

Из условия нецелочисленности х₁и х₂переходим к следующему шагу, который состоит в просмотре целочисленных значений х₁и х₂, больших или меньших полученного оптимального значения, путем добавления к задаче ЛП-1 нового ограничения, полученного округлением нецелочисленного оптимального значения в большую или меньшую сторону.

Таким образом, из задачи ЛП-1 получается четыре задачи.

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

1. Дополнительное ограничение:

В каноническом виде:

			х2
				(5)
				(3)		(1)
							(4)
							(2)
							х1

Рис. 2.17

Итерация №0 Таблица 2.57

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	4	-1	1	1	0	0	0	0
x4	21	-1	3	0	1	0	0	0
x5	43	3	1	0	0	1	0	0
x6	44	4	-3	0	0	0	1	0
x7	10	1	0	0	0	0	0	1
f (x)	0	-2	-1	0	0	0	0	0

Переменную x₁вводим в число базисных вместо переменнойx₇

Ведущий элемент равен 1.

Итерация №1 Таблица 2.58

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	14	0	1	1	0	0	0	1
x4	31	0	3	0	1	0	0	1
x5	13	0	1	0	0	1	0	-3
x6	4	0	-3	0	0	0	1	-4
x1	10	1	0	0	0	0	0	1
f (x)	20	0	-1	0	0	0	0	2

Переменную x₂вводим в число базисных вместо переменнойx₄

Ведущий элемент равен 3.

Итерация №2 Таблица 2.59

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	11/3	0	0	1	-1/3	0	0	2/3
x2	31/3	0	1	0	1/3	0	0	1/3
x5	8/3	0	0	0	-1/3	1	0	-10/3
x6	35	0	0	0	1	0	1	-3
x1	10	1	0	0	0	0	0	1
f (x)	91/3	0	0	0	1/3	0	0	7/3

Ответ:

2. Дополнительное ограничение:

В каноническом виде:

			х2
				(5)		(1)
				(3)
							(4)
						(2)
							х1

Рис. 2.18

Итерация №0 Таблица 2.60

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	4	-1	1	1	0	0	0	0
x4	21	-1	3	0	1	0	0	0
x5	43	3	1	0	0	1	0	0
x6	44	4	-3	0	0	0	1	0
x7	-11	-1	0	0	0	0	0	1
f (x)	0	-2	-1	0	0	0	0	0

Переменную x₁вводим в число базисных вместо переменнойx₆

Ведущий элемент равен 4.

Итерация №1 Таблица 2.61

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	15	0	1/4	1	0	0	1/4	0
x4	32	0	9/4	0	1	0	1/4	0
x5	10	0	13/4	0	0	1	-3/4	0
x1	11	1	-3/4	0	0	0	1/4	0
x7	0	0	-3/4	0	0	0	1/4	1
f (x)	22	0	-5/2	0	0	0	1/2	0

Переменную x₂вводим в число базисных вместо переменнойx₅

Ведущий элемент равен 13/4.

Итерация №3 Таблица 2.62

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	185/13	0	0	1	0	-1/13	4/13	0
x4	326/13	0	0	0	1	-9/13	10/13	0
x2	40/13	0	1	0	0	4/13	-3/13	0
x1	173/13	1	0	0	0	3/13	1/13	0
x7	30/13	0	0	0	0	3/13	1/13	1
f (x)	386/13	0	0	0	0	10/13	-1/13	0

Переменную x₆вводим в число базисных вместо переменнойx₇

Ведущий элемент равен 1/13.

Итерация №4 Таблица 2.63

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	5	0	0	1	0	-1	0	-4
x4	2	0	0	0	1	-3	0	-10
x2	10	0	1	0	0	1	0	3
x1	11	1	0	0	0	0	0	0
x6	30	0	0	0	0	3	1	13
f (x)	32	0	0	0	0	1	0	1

Ответ:

3. Дополнительное ограничение:

В каноническом виде:

			х2
						(1)
				(3)
							(4)
							(2)
						(5)
							х1

Рис. 2.19

Итерация №0 Таблица 2.64

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	4	-1	1	1	0	0	0	0
x4	21	-1	3	0	1	0	0	0
x5	43	3	1	0	0	1	0	0
x6	44	4	-3	0	0	0	1	0
x7	10	0	1	0	0	0	0	1
f (x)	0	-2	-1	0	0	0	0	0

Переменную x₁вводим в число базисных вместо переменнойx₆

Ведущий элемент равен 4.

Итерация №1 Таблица 2.65

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	15	0	1/4	1	0	0	1/4	0
x4	32	0	9/4	0	1	0	1/4	0
x5	10	0	13/4	0	0	1	-3/4	0
x1	11	1	-3/4	0	0	0	1/4	0
x7	10	0	1	0	0	0	0	1
f (x)	22	0	-5/2	0	0	0	1/2	0

Переменную x₂вводим в число базисных вместо переменнойx₅

Ведущий элемент равен 13/4.

Итерация №2 Таблица 2.66

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	185/13	0	0	1	0	-1/13	4/13	0
x4	326/13	0	0	0	1	-9/13	10/13	0
x2	40/13	0	1	0	0	4/13	-3/13	0
x1	173/13	1	0	0	0	3/13	1/13	0
x7	90/13	0	0	0	0	-4/13	3/13	1
f (x)	386/13	0	0	0	0	10/13	-1/13	0

Переменную x₆вводим в число базисных вместо переменнойx₇

Ведущий элемент равен 3/13.

Итерация №3 Таблица 2.67

базис	значение	x1	x2	x3	x4	x5	x6	x7
x3	5	0	0	1	0	1/3	0	-4/3
x4	2	0	0	0	1	1/3	0	-10/3
x2	10	0	1	0	0	0	0	1
x1	11	1	0	0	0	1/3	0	-1/3
x6	30	0	0	0	0	-4/3	1	13/3
f (x)	32	0	0	0	0	2/3	0	1/3

Ответ:

4. Дополнительное ограничение:

В каноническом виде:

			х2
						(1)
				(3)			(4)
						(2)
							(5)
							х1

Рис. 2.20

Ответ: нет допустимых решений

Так как в решении ЗЛП-2 х₂ - нецелое, данное решение не является решением исходной задачи.

Из условия нецелочисленности х₂переходим к следующему шагу, который состоит в просмотре целочисленных значений х₂, больших или меньших полученного оптимального значения, путем добавления к задаче ЛП-2 нового ограничения, полученного округлением нецелочисленного оптимального значения в большую или меньшую сторону.

Таким образом, из задачи ЛП-2 получается еще две задачи.

Решим каждую из полученных ЗЛП обычным симплекс-методом.

1. Дополнительное ограничение:

В каноническом виде:

			х2
				(5)		(1)
				(3)			(4)
							(2)
						(6)
								х1

Рис. 2.21

Итерация №0 Таблица 2.68

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	4	-1	1	1	0	0	0	0	0
x4	21	-1	3	0	1	0	0	0	0
x5	43	3	1	0	0	1	0	0	0
x6	44	4	-3	0	0	0	1	0	0
x7	10	1	0	0	0	0	0	1	0
x8	10	0	1	0	0	0	0	0	1
f (x)	0	-2	-1	0	0	0	0	0	0

Переменную x₁вводим в число базисных вместо переменнойx₇

Ведущий элемент равен 1.

Итерация №1 Таблица 2.69

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	14	0	1	1	0	0	0	1	0
x4	31	0	3	0	1	0	0	1	0
x5	13	0	1	0	0	1	0	-3	0
x6	4	0	-3	0	0	0	1	-4	0
x1	10	1	0	0	0	0	0	1	0
x8	10	0	1	0	0	0	0	0	1
f (x)	20	0	-1	0	0	0	0	2	0

Переменную x₂вводим в число базисных вместо переменнойx₈

Ведущий элемент равен 1.

Итерация №2 Таблица 2.70

базис	значение	x1	x2	x3	x4	x5	x6	x7	x8
x3	4	0	0	1	0	0	0	1	-1
x4	1	0	0	0	1	0	0	1	-3
x5	3	0	0	0	0	1	0	-3	-1
x6	34	0	0	0	0	0	1	-4	3
x1	10	1	0	0	0	0	0	1	0
x2	10	0	1	0	0	0	0	0	1
f (x)	30	0	0	0	0	0	0	2	1

Ответ:

2. Дополнительное ограничение:

В каноническом виде:

х2
				(5)
				(3)	(1)
							(4)
							(2)
						(6)
							х1

Рис. 2.22

Ответ: нет допустимых решений

Последовательность ЗЛП, возникающих при использовании метода ветвей и границ удобно представить в виде дерева:

Рис. 2.23

Ответ (решение ЗЦЛП):

Оглавление

68