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

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


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

Навигация