Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования.

Рассмотрим задачу коммивояжера с матрицей расстояний R, элементы которой r(i, j) приведены в таблице:


-
	-
		-
			-
				-

Пусть G = {1, 2, 3, 4, 5} - множество городов.

Обозначим через W(G’, i) - расстояние, которое пройдет коммивояжер из города с номером i через все города множества G’ в начальный город с номером 1, G’ G, i G\G’ при оптимальном выборе маршрута (с точки зрения критерия задачи коммивояжера). Тогда

W(G’, i) = min [ r(i, j) + W(G’\{i}, j)], (1)

где минимум берется по всем городам с номерами j G’.

Рекуррентные соотношения (1), используя граничные условия:

W(G’, i) = r(i, 1), если G’ - пустое множество, (2)

могут быть использованы для решения задачи коммивояжера.

W({2, 3, 4, 5}, 1)= min[4+ W({3, 4, 5}, 2), 3+ W({2, 4, 5}, 3), 2+ W({2, 3, 5}, 4), 4+ W({2, 3, 4}, 5)].

W({3, 4, 5}, 2)= min[2+ W({4, 5}, 3), 3+ W({3, 5}, 4), 2+ W({3, 4}, 5)]=min[2+8, 3+7, 2+7)=9(2, 5, 4, 3, 1).

W({2, 4, 5}, 3)=min[3+ W({4, 5}, 2), 3+ W({2, 5}, 4), 2+ W({2, 4}, 5)]=min[3+8, 3+6, 2+7]=9(3, 4, 2, 5, 1; 3, 5, 4, 2, 1).

W({2, 3, 5}, 4)=min [1+ W({3, 5}, 2), 2+ W({2, 5}, 3), 3+ W({2, 3}, 5)]=min[1+6, 2+8, 3+ 8]=7(4, 2, 5, 3, 1).

W({2, 3, 4}, 5)=min[4+ W({3, 4}, 5), 2+ W({2, 4}, 3), 3+ W({2, 3}, 4)]=min[4+7, 2+7, 3+5]=8(5, 4, 2, 3, 1).

Отсюда получаем:

W({2, 3, 4, 5}, 1)=min[4+9, 3+9, 2+7, 4+8]=9(1, 4, 2, 5, 3, 1).

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

x’(1, 4)=1, x’(4, 2)=1, x’(2, 5)=1, x’(5, 3)=1, x’(3, 1)=1.

Остальные значения переменных в оптимальном решении равны нулю.

Значение оптимума задачи F(X’)=9.

Решить задачи коммивояжера:

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

б)Методом динамического программирования.

Задача 2.1.


-
	-
		-
			-
				-

Задача 2.2.


-
	-
		-
			-
				-

Задача 2.3.


-
	-
		-
			-
				-

Задача 2.4.


-
	-
		-
			-
				-

Задача 2.5.


-
	-
		-
			-
				-

Задача 2.6.


-
	-
		-
			-
				-

Задача 2.7.


-
	-
		-
			-
				-

Задача 2.8.


-
	-
		-
			-
				-

Задача 2.9.


-
	-
		-
			-
				-

Задача 2.10.


-
	-
		-
			-
				-

3. Решить задачу Джонсона для двух станков. Построить график Ганта для оптимального расписания.

Алгоритм Джонсона построения оптимального расписания выполнения работ на двух станках включает в себя следующие шаги:

Шаг 1. Найти минимальную величину среди A(j) и B(j), j=1, 2,..., n.

Шаг 2. Если минимум достигается на A(j), то деталь с номером j ставится на обработку самой первой, если на B(j), то деталь с номером j ставится на обработку последней, деталь с номером j исключается из рассмотрения, и процесс построения расписания продолжается с шага 1.

Построенные расписания наглядно отображаются с помощью так называемых графиков Ганта или Гант-карт.

График Ганта - это графическое отображения расписания, в котором каждому станку соответствует своя ось времени.

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

j	A(j)	B(j)

Здесь A(j) и B(j), соответственно, времена обработки детали с номером j на первом и втором станке.

Оптимальное расписание определяется перестановкой r =(1, 4, 7, 8, 5, 3, 6).

График Ганта имеет вид:

ст

Длина оптимального расписания F( r )=22.

Задача 3.1.

j	A(j)	B(j)

Задача 3.2.

j	A(j)	B(j)

Задача 3.3.

j	A(j)	B(j)

Задача 3.4.

j	A(j)	B(j)

Задача 3.5.

j	A(j)	B(j)

Задача 3.6.

j	A(j)	B(j)

Задача 3.7.

j	A(j)	B(j)

Задача 3.8.

j	A(j)	B(j)

Задача 3.9.

j	A(j)	B(j)

Задача 3.10.

j	A(j)	B(j)

⇐ Предыдущая 1 2 3 4 5 678 Следующая ⇒