Задачи теории расписаний
презентация к уроку по информатике и икт (11 класс) на тему

Слайд 1

Слайд 2

Теория расписаний – это раздел исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений. Модели теории расписаний позволяют найти: Наиболее дешевый порядок выполнения работы Наиболее быстрый порядок выполнения работы Задача о шлюзах Задача о станках Задача о коммивояжере

Слайд 3

Через шлюз последовательно должны пройти N судов. Известно время прохождения каждого судна – t i и ущерб от 1 часа простоя в очереди – в денежных единицах. ( i - порядковый номер судна в очереди) Обозначения: T1 – время шлюзования 1-ого судна T2 – время шлюзования 2-ого судна U2 – стоимость 1 часа простоя в ожидании своей очереди 2-ого судна U4 = t1+t2+t3– время простоя 4-ого судна U4 ·( t1+t2+t3 ) – материальный ущерб от простоя 4-ого судна

Слайд 4

Показатель экономической эффективности работы шлюза связан с суммарным ущербом от простоя судов в ожидании своей очереди Пример: К шлюзу одновременно подошли 4 судна, т.е. суммарный ущерб от простоя в очереди ( S ) : S=U2 · t1+ U3 ·( t1+t2 ) + U4 ·( t1+t2+t3 ) Задача состоит в том, чтобы определить такой порядок пропуска судов через шлюз, при котором величина S будет минимальной.

Слайд 5

Математический анализ: S min достигается в том случае, если судна пропускаются в порядке убывания величины Если T1= T2 , U1≠U2 , то пропускается вперед судно с более дорогим простоем Если U1=U2 , T1≠T2 , то пропускается вперед судно с более быстрым шлюзованием Критерий убывания величины ≡ Критерию возрастания величины

Слайд 6

Решение в электронных таблицах Задача. Пять судов выстроились в очередь к шлюзу в порядке их прибытия № судна 1 2 3 4 5 Время шлюзования( усл . время) 45 36 28 24 72 Ущерб от простоя(у. е.) 5 12 7 4 3 Общий ущерб от простоя: = U2 · t1+U3 ·( t1+t2 )+ U4 ·( t1+t2+t3 )+ U 5· ( t1+t2+t3 + t 4) S=1942 усл.ден.ед .( ≠min ) С помощью MS Excel найти оптимальный порядок шлюзования судов, обеспечивающий минимальный ущерб от простоя

Слайд 7

Задача о двух станках Имеются два обрабатывающих станка (токарный и шлифовальный). Требуется изготовить детали, каждая из которых сначала обрабатывается на первом станке, а затем на втором. Время обработки i - й детали на j- м станке известно и равно t ij . Необходимо выбрать такой порядок обработки(расписание работы станков), чтобы полное время Т общ , затраченное на изготовление всех деталей, было минимальным. Постановка задачи:

Слайд 8

Требуется изготовить 5 деталей, обрабатывая каждую поочередно на двух станках. Расчет полного времени обработки на двух станках № детали Время вытачивания Время шлифовки 1 3 6 2 7 2 3 4 7 4 5 3 5 7 4 № детали Время окончания вытачивания детали Время окончания шлифовки детали Время простоя 2-го станка 1 3 3+6=9 3 2 3+7=10 10+2=12 1 3 10+4=14 14+7=21 2 4 14+5=19 21+3=24 0 5 19+7=26 26+4=30 2 Итого: 30 8

Слайд 9

Алгоритм решения задачи Алгоритм Джонсона: расставить очередность обработки деталей так, чтобы минимизировать время простоя 2-го станка: Среди всех времен t ij выбрать минимальное значение(если их несколько- взять любое). Если это время обработки на 1-м станке, то переместить запись в начало списка, иначе – в конец списка. Исключить эту деталь из рассмотрения и повторить действия 1 и 2 с оставшимися деталями. После m шагов будет получен оптимальный порядок обработки деталей.

Слайд 10

№ детали 1-й станок 2-й станок 1 3 6 2 7 2 3 4 7 4 5 3 5 7 4 № детали 1-й станок 2-й станок 1 3 6 3 4 7 4 5 3 5 7 4 2 7 2 № детали 1-й станок 2-й станок 1 3 6 2 4 7 4 5 3 5 7 4 2 7 2 Шаг 1 Шаг 2 № детали 1-й станок 2-й станок 1 3 6 3 4 7 5 7 4 4 5 3 2 7 2 № детали 1-й станок 2-й станок 1 3 6 3 4 7 5 7 4 4 5 3 2 7 2 № детали 1-й станок 2-й станок 1 3 6 3 4 7 5 7 4 4 5 3 2 7 2 Шаг 3 Шаг 4 Шаг 5

Слайд 11

Результат работы алгоритма Джонсона: № детали Время окончания вытачивания детали Время окончания шлифовки детали Время простоя 2-го станка 1 3 3+6=9 3 3 3+4=7 9+7=16 0 5 7+7=14 16+4=20 0 4 14+5=19 20+3=23 0 2 19+7=26 26+2=28 3 Итого: 28 6 Задание: реализовать алгоритм Джонсона в среде программирования Паскаль (учебник, стр. 259)

Слайд 12

Задача коммивояжера На плоскости (в пространстве) расположены N городов, заданы расстояния между каждой парой городов. Требуется найти маршрут минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку. В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода. В 1859 г. У. Гамильтон придумал игру «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (города, пункты назначения) графа, чтобы посетить каждую вершину однократно и возвратиться в исходную. Пути, обладающие таким свойством, называются гамильтоновыми циклами.

Слайд 13

Постановка задачи коммивояжера Задача коммивояжера была поставлена в 1934 году. Ее сущность заключается в поиске оптимального маршрута движения при необходимости посетить все запланированные объекты с наименьшими финансовыми и временными издержками. Как правило, речь идет о простом перемещении по заданным точкам, либо с перевозкой груза небольшого формата на транспортном средстве. Задача коммивояжера является одной из знаменитых задач теории комбинаторики и пользуется популярностью благодаря тому, что к ней сводится большое количество практических задач. Среди современных практических приложений задачи можно выделить: доставку продуктов в магазин со склада, работу почтальона по разноске корреспонденции, мониторинг объектов (нефтяные вышки, базовые станции сотовых операторов), изготовление отверстий на специализированном станке.

Слайд 14

Сотруднику компании ООО «Новые технологии» Петрову Н.И. необходимо обновить программный продукт автоматизированного учета в пяти организациях: А, Б, В, Г и Д. Он решил начать свой обход с организации «А», так как она находится на первом этаже дома, в котором проживает Петров. Сотруднику необходимо, спланировать свой маршрут таким образом, чтобы к концу рабочего дня обойти все организации в определенном порядке и выполнив свою работу, вернутся домой (в пункт «А»). В каком порядке Петрову следует обходить организации, чтобы его замкнутый тур был кратчайшим? Расстояния между каждой парой организаций заданы следующей квадратной матрицей (5x5): 7 2 9 7 5 3 9 1 4 8 5 3 5 6 4 7 7 6 3 7