Венгерский метод

Идея метода была высказана венгерским математиком Эгервари и состоит в следующем. Строится начальный план перевозок, не удовлетворяющий в общем случае всем условиям задачи (из некоторых пунктов производства не весь продукт вывозится, потребность части пунктов потребления не полностью удовлетворена). Далее осуществляется переход к новому плану, более близкому к оптимальному. Последовательное применение этого приема за конечное число итераций приводит к решению задачи.

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X₀ (x_ij[0])_m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

, i 1, …, m; (7.30)

, j 1, …, m. (7.31)

Если эти условия являются равенствами, то матрица Х_o - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Х_k (x_ij[0])_m,n. Близость этой матрицы к решению задачи характеризует число D_k — суммарная невязка матрицы Х_k:

. (7.32)

В результате первой итерации строится матрица Х_l, состоящая из неотрицательных элементов. При этом D_l D₀. Если D_l 0, то Х_l - оптимальное решение задачи. Если D_l 0, то переходят к следующей итерации. Они проводятся до тех пор, пока D_k при некотором k не станет равным нулю. Соответствующая матрица Х_k является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D₀/2 (D₀ ‑ суммарная невязка подготовительного этапа).

Достоинством венгерского метода является возможность оценивать близость результата каждой из итераций к оптимальному плану перевозок. Это позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Данное свойство существенно для задач большой размерности.