Изменения

Перейти к: навигация, поиск

Участник:Dominica

24 байта убрано, 19:58, 12 мая 2016
Решение
Эта задача может быть решена сведением к решению [[Венгерский алгоритм решения задачи о назначениях | задачи о назначениях]].
А именно, покажем, что решение задачи состоит в сопоставлении <tex>n</tex> различным заданиям различных времен начала выполнения работы. Если сопоставляем работе <tex>i</tex> время <tex>t</tex>, то вклад в целевую функцию будет <tex> f_i(t + 1) </tex>.
Далее будет показано, что при построении оптимального расписания нам нужно будет рассмотреть всего <tex>n</tex> различных времен начала работ. Следовательно, подобная задача может быть решена за <tex>O(n^3)</tex>.
Для того, чтобы найти оптимальное расписание, построим полный двудольный граф, в котором будут доли <tex>V_1, V_2</tex> и ребра <tex>c_{ij}</tex> между ними: <tex>V_1=\left \{ 1,\ldots,n \right\}</tex> <tex>и V_2=\left \{ t_1,\ldots,t_n \right\}</tex> и ребра <tex>c_{ij}</tex> между ними:
<p>
<tex>
264
правки

Навигация