Постановка транспортной задачи

Рассмотрим следующую задачу, называемую транспортной задачей.

Имеется m поставщиков A₁,A₂ ,..., A_m, у которых сосредоточены запасы одного и того же груза в количестве m a₁,a₂,...,a_m единиц, соответственно. Этот груз нужно доставить n потребителям B₁,B₂,..., B_n, заказавшим b₁, b₂,...,b_n единиц этого груза, соответственно. Известны также все тарифы перевозок груза c_ij (стоимость перевозок единицы груза) от поставщика A_i к потребителю B_j. Требуется составить такой план перевозок, при котором общая стоимость всех перевозок была бы минимальной.

Условие транспортной задачи удобно записать в виде следующей:

Обозначим суммарный запас груза у всех поставщиков символом a , а суммарную потребность в грузе у всех потребителей – символом b. Тогда

Транспортная задача называется закрытой, если a = b . Если же a ≠ b , то транспортная задача называется открытой. В случае открытой задачи при a < b весь груз будет вывезен, однако будут недопоставки груза экономически невыгодным потребителям. При a > b , наоборот, будут удовлетворены все потребители, но часть груза останется на складах экономически невыгодных поставщиков.

Пусть x_ij (x_ij ≥ 0) – количество груза, отправляемого поставщиком A_i потребителю B_j. Тогда суммарные затраты z на перевозки будут вычисляться по формуле:

Функция z называется целевой функцией.

Математическая формулировка транспортной задачи заключается в нахождении плана перевозок X = {x_ij}, который удовлетворяет системе ограничений

и доставляет минимум целевой функции z.

План перевозок, реализующий минимум целевой функции z , называется оптимальным.

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