Транспортная задача с ограничениями на пропускную способность

Некоторый однородный продукт, сосредоточенный у m поставщиков A_i в количестве a_i (i = 1, 2, …, m) у каждого, необходимо доставить к потребителю B_j в количестве b_j (j = 1, 2, …, n). Известна стоимость C_ij перевозок единицы груза от i - го поставщика j - му потребителю и ограничения по пропускной способности d_ij.

Требуется составить план перевозок, позволяющий вывести все грузы от поставщиков; полностью удовлетворить потребности потребителей таким образом, чтобы этот план имел минимальную стоимость перевозок.

Математическая модель задачи такова

при ограничениях:

,

где d_ij - предельное число единиц продукции, которое может быть перевезено от i- го поставщика j – му потребителю за время, указанное в условии задачи. Такая задача называется ТЗ с ограничениями на пропускную способность (Td). Для решения таких задач может быть приспособлен любой из вычислительных алгоритмов решения обычной ТЗ, например, венгерский метод, метод потенциалов.

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

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

На подготовительном этапе строится матрица x₀ =(x_ij[0])_mn, элементы которой неотрицательны и удовлетворяют неравенствам:

.

Если эти условия являются равенствами, то матрица Х₀- решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На К- ой итерации строится матрица Х_к = (Х_ij[К])_mn, суммарная невязка которой D_К

В результате первой итерации строится матрица x₁, состоящая из неотрицательных элементов. При этом D₁ < D₀. Если D₁ = 0, то x₁ - оптимальное решение задачи. Если D₁ > 0, то переходят к следующей итерации. Они проводятся до тех пор, пока D_кпри некотором К не станет равным 0. Соответствующая матрица x_k является решением ТЗ.

Достоинством венгерского метода является возможность оценивать близость результата каждой итерации к оптимальному плану перевозок, что позволяет контролировать процесс вычислений и прекратить его при достижении определенных точностных показателей. Особенно это свойство существенно для задач большой размерности. Подробное изложение алгоритма см. в книге: Гольштейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа.- М.: Наука, 1969. - 382 с..