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

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

Рассмотрим задачу коммивояжера с матрицей расстояний 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.

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

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

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

Задача 2.1.

	-
		-
			-
				-
					-

Задача 2.2.

	-
		-
			-
				-
					-

Задача 2.3.

	-
		-
			-
				-
					-

Задача 2.4.

	-
		-
			-
				-
					-

Задача 2.5.

	-
		-
			-
				-
					-

Задача 2.6.

	-
		-
			-
				-
					-

Задача 2.7.

	-
		-
			-
				-
					-

Задача 2.8.

	-
		-
			-
				-
					-

Задача 2.9.

	-
		-
			-
				-
					-

Задача 2.10.

	-
		-
			-
				-
					-

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

Шаг 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).

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

ст1

ст2

Длина оптимального расписания 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)

Дата добавления: 2017-02-01