Задача о назначениях: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Задача о назначениях''' (''Assignment problem'') - Пусть имеется конечное множество и...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Задача о назначениях''' (''Assignment problem'') - | '''Задача о назначениях''' (''[[Assignment problem]]'') - Пусть имеется конечное множество исполнителей, каждый из которых может выполнять некоторые из имеющегося набора работ. Известна | ||
Пусть имеется конечное множество исполнителей, каждый из которых | стоимость выполнения каждой работы каждым исполнителем. Задача заключается в таком распределении исполнителей по работам, при котором суммарная стоимость выполнения всех работ была бы минимальна. | ||
может выполнять некоторые из имеющегося набора работ. Известна | Математическая постановка задачи состоит в отыскании во [[взвешенненный граф|взвешенном]] [[двудольный граф|двудольном графе]] наибольшего ''паросочетания'' с минимальным суммарным весом. | ||
стоимость выполнения каждой работы каждым исполнителем. Задача | |||
заключается в таком распределении исполнителей по работам, при котором | |||
суммарная стоимость выполнения всех работ была бы минимальна. | |||
Математическая постановка задачи состоит в отыскании во взвешенном | |||
двудольном графе наибольшего ''паросочетания'' с минимальным | |||
суммарным весом. | |||
==Литература== | ==Литература== | ||
[Лекции], | [Лекции], | ||
[Кристофидес] | [Кристофидес] | ||
Версия от 17:23, 20 октября 2009
Задача о назначениях (Assignment problem) - Пусть имеется конечное множество исполнителей, каждый из которых может выполнять некоторые из имеющегося набора работ. Известна стоимость выполнения каждой работы каждым исполнителем. Задача заключается в таком распределении исполнителей по работам, при котором суммарная стоимость выполнения всех работ была бы минимальна. Математическая постановка задачи состоит в отыскании во взвешенном двудольном графе наибольшего паросочетания с минимальным суммарным весом.
Литература
[Лекции],
[Кристофидес]