Презентация на тему Задача о назначениях. Алгоритмы

Содержание

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

Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической оптимизации или исследовании операций. Задача состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.В наиболее общей форме задача формулируется следующим образом:Имеется некоторое число

Главная
Математика
Задача о назначениях. Алгоритмы

Задача о назначенияхВыполнил студент 306 группы специальности «Бизнес-информатика» Князев Д.А

Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области математической

АлгоритмыВенгерский алгоритм.Метод исчерпывающего перебора.

Венгерский методЗАДАНИЕ. Решить задачу об оптимальном назначении с матрицей эффективностей A .

Этап 1. В каждой строке ищем минимальный элемент (выделяем жирным в таблице)

Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой стоимостью.Этап

Временная сложность оригинального Венгерского алгоритма была O(n^4), однако Эдмондс (англ.) и Карп

В данном примере задания следует распределить так: первому работнику – 2 задание,

Задача о назначениях используется для количественного анализа ситуаций, когда менеджер должен назначить

Слайды презентации

Слайд 2
Задача о назначениях — одна из фундаментальных задач комбинаторной

Задача о назначениях — одна из фундаментальных задач комбинаторной оптимизации в области

оптимизации в области математической оптимизации или исследовании операций. Задача

состоит в поиске минимальной суммы дуг во взвешенном двудольном графе.

В наиболее общей форме задача формулируется следующим образом:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой (но только одной) работы, но с неодинаковыми затратами. Нужно распределить работы так, чтобы выполнить работы с минимальными затратами.

Если число работ и исполнителей совпадает, то задача называется линейной задачей о назначениях. Обычно, если говорят о задаче о назначениях без дополнительных условий, имеют в виду линейную задачу о назначениях.

Слайд 3 Алгоритмы
Венгерский алгоритм.
Метод исчерпывающего перебора.

Слайд 4 Венгерский метод
ЗАДАНИЕ. Решить задачу об оптимальном назначении с

матрицей эффективностей A .
( 2

4 1 3 3)
( 1 5 4 1 2 )
A = ( 3 5 2 2 4 )
( 1 4 3 1 4 )
( 3 2 5 3 5 )

РЕШЕНИЕ. Поскольку не указано, будем решать задачу на минимум (стандартная постановка). Решение будем искать венгерским методом.
Составляем исходную таблицу (матрицу):

Слайд 5 Этап 1. В каждой строке ищем минимальный элемент

Этап 1. В каждой строке ищем минимальный элемент (выделяем жирным в

(выделяем жирным в таблице) и отнимаем от всех элементов

строки. Получим:

Теперь проводим аналогичную процедуру для всех столбцов: ищем наименьший элемент по столбцу и отнимаем его из всех элементов столбца. Получим:

Слайд 6 Задачей является распределение всех подлежащих назначению единиц в

Задачей является распределение всех подлежащих назначению единиц в клетки с нулевой

клетки с нулевой стоимостью.

Этап 2. Выбираем строку с одним

нулем (строка №1), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №3).
Выбираем строку с одним нулевым значением (строка №5), выделяем нуль.
Выбираем строку с одним нулем (строка №3), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №4).
Выбираем строку с одним нулем (строка №4), выделяем нуль жирным и зачеркиваем (выделено серым) оставшиеся нулевые значения этого столбца (столбца №1). Выбираем строку с одним нулевым значением (строка №2), выделяем нуль.

Получаем оптимальную матрицу назначений:

Минимальное значение целевой функции: 1+2+2+1+2=8.