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

Материал из WikiGrapp
Версия от 14:49, 20 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Задача о назначениях''' (''Assignment problem'') - Пусть имеется конечное множество и...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Задача о назначениях (Assignment problem) - Пусть имеется конечное множество исполнителей, каждый из которых может выполнять некоторые из имеющегося набора работ. Известна стоимость выполнения каждой работы каждым исполнителем. Задача заключается в таком распределении исполнителей по работам, при котором суммарная стоимость выполнения всех работ была бы минимальна. Математическая постановка задачи состоит в отыскании во взвешенном двудольном графе наибольшего паросочетания с минимальным суммарным весом.

Литература

[Лекции],

[Кристофидес]