КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Решить задачу Джонсона для двух станков, построить график Ганта для оптимального расписания
Решение задачи коммивояжера с использованием рекуррентных соотношений динамического программирования Рассмотрим задачу коммивояжера с матрицей расстояний 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. Построенные расписания наглядно отображаются с помощью так называемых графиков Ганта или Гант-карт. График Ганта - это графическое отображения расписания, в котором каждому станку соответствует своя ось времени. Пусть матрица времен выполнения работ на станках имеет вид:
Здесь A(j) и B(j), соответственно, времена обработки детали с номером j на первом и втором станке. Оптимальное расписание определяется перестановкой r =(1,4,7,8,5,3,6). График Ганта имеет вид:
Длина оптимального расписания F(r)=22.
Задача 3.1.
Задача 3.2.
Задача 3.3.
Задача 3.4.
Задача 3.5.
Задача 3.6.
Задача 3.7.
Задача 3.8.
Задача 3.9.
Задача 3.10.
Дата добавления: 2017-02-01; Просмотров: 190; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |