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

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


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

Навигация