264
правки
Изменения
Нет описания правки
Отсортируем задания по неубыванию <tex>r_i</tex>, а дальше будем выполнять задания по мере появления. В полученном расписании работы будут идти в порядке <tex>4, 2, 1, 3</tex> и давать в ответе <tex>2^{1 + 1} + (2 + 1)^2 + 5(3 + 1) + (4 + 1) + 4 = 42 </tex>, что является оптимальным результатом.
==Пример 2==
Пусть у нас есть три задания, и каждое из них имеет время появления <tex>r_i = 0.</tex> Заданы функции <tex>f_i</tex>:
<tex>f_2(t) = t^3 </tex>
<tex>f_3(t) = \mathrm{e} 3 ^ t </tex>
Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем {{---}} не понятно, в каком порядке сортировать задания с одинаковым временем появления.
Тогда нучно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим: <tex>t_1 = 0, t2 = 1, t3 = 2</tex>.
Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях:
\hline
\hline
0 & 1 & 1 & $\mathrmmathbf{e1}$ & 3 \\1 & 4 & 8 & $\mathrmmathbf{e9} ^ 2$ \\2 & 9 & 27 & $\mathrmmathbf{e9} ^ 3$& 27 & 27\\
\hline
\end{tabular}
</tex>
В результате будет выбрано расписаниеработы Венгерского алгоритма будет выбран порядок работ <tex>2, в котором сначала будет идти третья3, затем вторая1</tex>, а затем первая работачто даст лучший результат {{---}} <tex>19</tex>.==Пример 3==
== См. также ==
