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

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

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

пятью персонажами. Режиссер решил, что каждый актёр может озвучить

не более двух персонажей. Баллы, показывающие, насколько актер соответствуют той или иной роли, занесены в следующую таблицу.

Распределить роли так, чтобы сумма баллов была максимальной. В ответе написать сумму баллов

актеров.

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. Проведём редукцию по столбцам (в каждом столбце находим наименьший элемент и вычитаем его из всех элементов этого столбца).

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

2 2 0 0
0

0 1 1 1 1
0 0 7 7 0 0
5 5 0 0 0 0
1 1 0 0 6 6
3 3 0 0 2 2

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

из NP-полных задач комбинаторной оптимизации. Название своё получила от

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

TSP) — одна из самых известных задач комбинаторной оптимизации,

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

Её можно решить как с помощью представление в виде графа, так и с помощью метода ветвей и границ.

решения задачи коммивояжера методом ветвей и границ необходимо выполнить

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

решения позволяют максимизировать производство и более грамотно вести бизнес.
Задача

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