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

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта.A_i в пункт В_j, i 1, …, m; j 1, ..., n. Предположим, что

(7.24)

т. е. общий объем производства равен общему объему потребления. Требуется составить такой план перевозок (откуда, куда и сколько единиц продукта везти), чтобы удовлетворить спрос всех пунктов потребления за счет реализации всего продукта, произведенного всеми пунктами производства, при минимальной общей стоимости всех перевозок. Приведенная формулировка транспортной задачи называется замкнутой транспортной моделью. Формализуем эту задачу.

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j. Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

(7.25)

Суммарное количество продукта, направляемого из каждого пункта отправления во все пункты назначения, должно быть равно запасу продукта в данном пункте. Формально это означает, что

, i 1, …, m. (7.26)

Суммарное количество груза, доставляемого в каждый пункт назначения из всех пунктов отправления, должно быть равно потребности. Это условие полного удовлетворения спроса:

, j 1, …, n (7.27)

Объемы перевозок ‑ неотрицательные числа, так как перевозки из пунктов потребления в пункты производства исключены:

x_ij 0, i 1, ..., m; j 1, ..., n.(7.28)

Транспортная задача сводится, таким образом, к минимизации суммарных затрат при выполнении условий полного удовлетворения спроса и равенства вывозимого количества продукта запасам его в пунктах отправления.

В ряде случаев не требуется, чтобы весь произведенный продукт в каждом пункте производства был реализован. В таких случаях баланс производства и потребления может быть нарушен:

, i 1, ..., m.(7.29)

Введение этого условия приводит к открытой транспортной модели.

Задачи транспортного типа широко распространены в практике. Кроме того, к ним сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

Как одна из задач линейного программирования транспортная задача принципиально может быть решена универсальным методом решения любой задачи линейного программирования, но этот метод не учитывает специфики условий транспортной задачи. Поэтому решение ее симплекс-методом оказывается слишком громоздким.

Структура ограничений задачи учитывается в ряде специальных вычислительных методов ее решения. Рассмотрим некоторые из них. Предварительно сделаем следующее замечание. Открытая транспортная модель может быть приведена к замкнутой модели добавлением фиктивного пункта отправления (потребления), от которого поступает весь недостающий продукт или в который свозится весь избыточный запас. Стоимость перевозок между реальными пунктами и фиктивным принимается равной нулю. Вследствие простоты перехода от открытой модели к замкнутой в дальнейшем рассматриваются методы решения замкнутой модели транспортной задачи.

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

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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица 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₀ ‑ суммарная невязка подготовительного этапа).

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