264
правки
Изменения
Нет описания правки
===Пример 3===
Пусть у нас есть три задания, и каждое из них имеет время появления <tex>r_i = 0.</tex> Заданы функции <tex>f_i</tex>:
<tex>f_1(t) = t^2 </tex>
<tex>f_2(t) = t^3 </tex>
<tex>f_3(t) = 3 ^ t </tex>
Поступить как в предыдущем примере и просто отсортировать работы мы теперь не можем {{---}} не понятно, в каком порядке сортировать задания с одинаковым временем появления.
Тогда нучно по приведенному в начале алгоритму посчитать времена, когда мы можем начать выполнять задания. В результате получим: <tex>t_1 = 0, t_2 = 1, t_3 = 2</tex>.
Тогда, согласно алгоритму, задача сведется к следующей задаче о назначениях:
<tex>
\begin{tabular}{c||ccc}
$t_i$ $\backslash$ i & 1 & 2 & 3 \\
\hline
\hline
0 & 1 & $\mathbf{1}$ & 3 \\
1 & 4 & 8 & $\mathbf{9}$ \\
2 & $\mathbf{9}$ & 27 & 27\\
\hline
\end{tabular}
</tex>
В результате будет работы Венгерского алгоритма будет выбран порядок работ <tex>2, 3, 1</tex>, что даст лучший результат {{---}} <tex>19</tex>.
На этом примере хорошо видно, что решение, выбирающие в каждый момент времени <tex>t_i</tex> несделанную работу с минимальным значением f_i(t_i + 1) будет давать плохой результат.
== См. также ==
