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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Задача о назначениях''' (''[[Assignment problem]]'') — Пусть имеется конечное множество исполнителей, каждый из которых может выполнять некоторые из имеющегося набора работ. Известна
'''Задача о назначениях''' (''[[Assignment problem]]'') — Пусть имеется конечное множество исполнителей, каждый из которых может выполнять некоторые из имеющегося набора работ. Известна
стоимость выполнения каждой работы каждым исполнителем. Задача заключается в таком распределении исполнителей по работам, при котором суммарная стоимость выполнения всех работ была бы минимальна.
стоимость выполнения каждой работы каждым исполнителем. Задача заключается в таком распределении исполнителей по работам, при котором суммарная стоимость выполнения всех работ была бы минимальна.
Математическая постановка задачи состоит в отыскании во [[взвешенный граф|взвешенном]] [[двудольный граф|двудольном графе]] наибольшего ''паросочетания'' с минимальным суммарным весом.
Математическая постановка задачи состоит в отыскании во [[взвешенный граф|взвешенном]] [[двудольный граф|двудольном графе]] наибольшего [[паросочетание|''паросочетания'']] с минимальным суммарным [[вес ребра|весом]].
==Литература==
==Литература==
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
* Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
   
   
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

Текущая версия от 15:27, 11 февраля 2011

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

Литература

  • Кристофидес Н. Теория графов. Алгоритмический подход. — М.: Мир, 1978.
  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.