Задание № 2. Задача о коммивояжере. Метод ветвей и границ

Исходные данные

К заданию №1.

№	C1	C2	B1	B2	A11	A12	A21	A22
						-2

К заданию №2.

С =		∞
		∞
			∞
				∞
					∞
						∞

К заданию №3.

№	A	B	α	β	γ
		0,25		1,5

К заданию №4.

№	A	B	α^2
	0,5		3/4

К заданию №5.

№	k	γ

Задание №1. Графоаналитическое решение ОЗЛП

1. Математическая постановка ОЗЛП:

φ=5x₁+x₂→max, (0)

2x₁-2x₂≤4, (1)

2x₁+6x₂≤4, (2)

x₁≥0, (3)

x₂≥0, (4)

BD: 2x₁-2x₂=4, (1’)

CD: 2x₁+6x₂=4, (2’)

AC: x₁=0, (3’)

AB: x₂=0, (4’)

2. Записываем уравнение граничных линий допустимого многоугольника (1’) - (4’).

На плоскости (x1, x2) строим граничные линии.

3. Строим линию, пересекающую область φ.

, (5)

, (6)

4. Находим градиент целевой функции:

, (7)

, (8)

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

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи φ=5x₁+x₂→max. Построим прямую, отвечающую значению функции φ=0: F=5x₁+x₂=0. Будем двигать эту прямую параллельным образом до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Из рисунка видно, что оптимальная точка D* равная , находится на пересечении линий BD и CD и ее координаты определяются путем решения одноименных уравнений (1’) и (2’).

, , (9)

, (10)

Ответ: ;

Задание № 2. Задача о коммивояжере. Метод ветвей и границ

Расстояния между пунктами заданы матрицей:

С =		∞
		∞
			∞
				∞
					∞
						∞

Решение задачи о коммивояжере методом ветвей и границ начинается с приведения матрицы (вычитания из каждой строки (столбца) матрицы C минимального элемента этой строки (столбца).

Произведем приведение матрицы C по строкам:

h_ν= min(i) h_νi

								hν
С’ =		∞
		∞
			∞
				∞
					∞
						∞

Произведем приведение матрицы C по столбцам:

g_i = min(υ) g_νi

С’ =		∞
		∞
			∞
				∞
					∞
						∞
	gi

В итоге получаем полностью приведенную (редуцированную) матрицу:

								hν
С0 =		∞
		∞
			∞
				∞
					∞
						∞
	gi

Величины h_ν и g_i называются константами приведения.

Нижняя граница цикла: d₀=8 ().

Шаг №1.

Определяем ребро ветвления и разобьем все множество допустимых значений Q⁰ относительно этого ребра на два непересекающихся подмножества () и (), т.е. , где

В приведенной матрице исследуем все нулевые переходы.

								αν
C0 =		∞	0(1)				0(0)
	0(0)	∞	0(0)
			∞	0(3)
	0(0)			∞		0(0)
			0(1)		∞
	0(0)				0(2)	∞
	βi

Наибольшая сумма констант приведения равна

υ₃₄= α₃ + β₄ =2+1=3, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

В результате получим другую сокращенную матрицу (5x5), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

							hν
		∞
			∞
C1=				∞
					∞
						∞
	gi

d₁=0

Шаг №2.

Определяем ребро ветвления и разобьем все множество допустимых значений Q¹ относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

							αν
		∞	0(1)			0(0)
		0(0)	∞	0(0)
C1=		0(0)		∞		0(0)
				0(2)	∞
		0(0)			0(2)	∞
	βi

Наибольшая сумма констант приведения равна

υ₅₃=2+0=2, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (4x4), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

						hν
C2 =		∞
		∞
				∞
	gi

d₂=0

Шаг №3.

Определяем ребро ветвления и разобьем все множество допустимых значений Q² относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

						αν
C2 =		∞	0(1)		0(0)
	0(5)	∞
	0(0)		∞	0(0)
	0(0)		0(2)	∞
	βi

Наибольшая сумма констант приведения равна

υ₂₁=5+0=5, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (3x3), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

					hν
		∞
C3 =			∞
				∞
	gi

d₃=1

Шаг №4.

Определяем ребро ветвления и разобьем все множество допустимых значений Q³ относительно этого ребра на два непересекающихся подмножества .

В приведенной матрице исследуем все нулевые переходы.

					αν
		∞		0(2)
C3 =			∞	0(4)
		0(4)	0(2)	∞
	βi

Наибольшая сумма констант приведения равна

υ₄₆=4+0=4, следовательно,

множество разбивается на два подмножества и .

Оценка длины цикла: .

Оценка на перспективном множестве:

В результате получим другую сокращенную матрицу (2x2), которая подлежит операции приведения.

После операции приведения сокращенная матрица будет иметь вид:

				hν
C4 =		∞
	gi

d₄=2

В соответствии с этой матрицей включаем в маршрут и .

Ответ: l* =C₃₄+C₄₆+C₆₂+C₂₁+C₁₅+C₅₃=1+1+3+1+3+2=11.

Дерево решения имеет следующий вид:

 

 

 

 

 

 

 

 

 

 

 

Дата добавления: 2015-11-30