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

Содержание

• 
  Слайд 1

  Задачи теории расписаний

• 
  Слайд 2

  Теория расписаний

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

• 
  Слайд 3
  

  Через шлюз последовательно должны пройти N судов. Известно время прохождения каждого судна – ti и ущерб от 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

  Математический анализ:

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

• 
  Слайд 6

  Решение в электронных таблицах

  Задача. Пять судов выстроились в очередь к шлюзу в порядке их прибытия Общий ущерб от простоя: =U2·t1+U3·(t1+t2)+U4·(t1+t2+t3)+U5· (t1+t2+t3+t4) S=1942 усл.ден.ед.(≠min) С помощью MS Excel найти оптимальный порядок шлюзования судов, обеспечивающий минимальный ущерб от простоя

• 
  Слайд 7

  Задача о двух станках

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

• 
  Слайд 8
  

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

• 
  Слайд 9

  Алгоритм решения задачи

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

• 
  Слайд 10
  

  Шаг 1 Шаг 2 Шаг 3 Шаг 4 Шаг 5

• 
  Слайд 11

  Результат работы алгоритма Джонсона:

  Задание: реализовать алгоритм Джонсона в среде программирования Паскаль (учебник, стр. 259)

• 
  Слайд 12

  Задача коммивояжера

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

• 
  Слайд 13

  Постановка задачи коммивояжера

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

• 
  Слайд 14
  

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