Задача о назначениях: различия между версиями

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


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

Версия от 17:23, 20 октября 2009

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

Литература

[Лекции],

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