Презентация на тему "Задачи о назначениях. Задача о ранце и Задача коммивояжера."

Содержание

• 
  Слайд 1

  Задачи о назначениях. Задача о ранце и Задача коммивояжера.

  Подготовил студент группы Р05-206: Коломин Андрей.

• 
  Слайд 2

  Задачи о назначениях.

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

• 
  Слайд 3

  Пример задачи о назначениях.

  Три актёра озвучивают мультфильм с пятью персонажами. Режиссер решил, что каждый актёр может озвучить не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу. Распределить роли так, чтобы сумма баллов была максимальной. В ответе написать сумму баллов

• 
  Слайд 4

  Решение.

  Решение. Добавим фиктивный персонаж и продублируем столбцы всех актеров.

• 
  Слайд 5
  

  Получаем матрицу соответствия. 6 6 4 4 8 8 10 10 6 6 8 8 10 10 0 0 9 9 0 0 2 2 4 4 6 6 4 4 0 0 0 0 0 0 0 0 1. Находим максимальный элемент в матрице и вычитаем из него все элементы. 4 4 6 6 2 2 0 0 4 4 2 2 0 0 10 10 1 1 10 10 8 8 6 6 4 4 6 6 10 10 10 10 10 10 10 10 2. Проведём редукцию по столбцам (в каждом столбце находим наименьший элемент и вычитаем его из всех элементов этого столбца).

• 
  Слайд 6
  

  4 4 2 2 1 1 0 0 0 0 1 1 0 0 6 6 0 0 10 10 4 4 5 5 4 4 2 2 9 9 10 10 6 6 9 9 3. Проведем редукцию по строкам (в каждой строке находим наименьший элемент и вычитаем его из всех элементов этой строки). 3 3 1 1 0 0 0 0 0 0 1 1 0 0 6 6 0 0 6 6 0 0 1 1 2 2 0 0 7 7 4 4 0 0 3 3 4. Далее вычёркиваем все строки и столбцы, содержащие 0 и среди оставшихся находим наименьший элемент. Его мы складываем с элементами на перекрестье. 3 3 1 1 0 0 0 0 0 0 1 1 0 0 6 6 0 0 6 6 0 0 1 1 2 2 0 0 7 7 4 4 0 0 3 3

• 
  Слайд 7
  

  После всех проведённых преобразований получим матрицу: 3 3 2 2 0 0 0 0 1 1 1 1 00 7 7 00 5 5 00 00 1 1 00 6 6 3 3 00 2 2 Таким образом получаем, что Сидоров может играть роли № 1, №3, №4. Петров может играть роли №4, №5, фиктивную роль. Иванов может играть роли №2, №3. Далее рассматриваем исходную таблицу и определяем наилучший вариант распределения. Ответ: 1. Иванов → персонажи 2 и 3. 2. Петров → персонаж 5 3. Сидорова → персонажи 1 и 4. Z = 8 + 10 + 10 + 4 + 4 = 36

• 
  Слайд 8

  Задача о ранце.

  Задача о ранце (рюкзаке) — одна из NP-полных задач комбинаторной оптимизации. Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в рюкзак при условии, что общий объём (или вес) всех предметов, способных поместиться в рюкзак, ограничен. Если говорить более простым языком, то в наиболее общей форме задача формулируется следующим образом: из заданного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

• 
  Слайд 9

  Пример задачи о ранце.

  Вместимость рюкзака равна 14.

• 
  Слайд 10

  Решение.

• 
  Слайд 11

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

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

• 
  Слайд 12

  Общий план решения методом ветвей и границ.

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

• 
  Слайд 13

  Практическое применение данных задач.

  Данные задачи и методы их решения позволяют максимизировать производствои более грамотно вести бизнес. Задача о назначениях позволяет грамотно распределить рабочую силу. Задача о ранце позволяет найти такое решение, при котором находится максимальная выгода при определённых ограничениях. Задача коммивояжера позволяет наладить логистику в компании, что существенно сократит расходы на перевозку продукции.

• 
  Слайд 14

  Спасибо за внимание.