Транспортная задача. Метод потенциалов.

Обозначим A₁, A₂, …, A_m - поставщики, В₁, В₂, …, В_n – потребители.

Объем потребления в j-м пункте (j=1, 2, …, n) обезначим b_j. Расходы на перевозку еденицы продукта из пункта А_i в пункт В_j это C_ij. Матрицу С=(С_ij) называют матрицей транспортных расходов. Требуется составить план перевозок при котором весь продукт вывозится из пунктов А_i в пункты В_j в соответствии с потребностью причем общая величина транспортных издержек при этом минимально.

Обозначим через x_ij – количество продуктов перевозимых из пункта Аi в пункт Вj.

(1)

(2)

Если выполняется условие (2), то транспортная задача является закрытой.

Рассмотрим метод потенциалов, т.е. каждому i-му поставщику поставим в соответствие величину ui называется потенциалом. И каждому j-му потребителю поставим в соответствие потенциал v_j.

u_i – цена продукта у i-го поставщика; v_j – цена продукта н j-го потребителя. v_j=u_i+c_ij (3)

Алгоритм решения транспортной задачи:

1) Строится начальный план перевозок;

2) Находим потенциалы u_i и v_j и анализируем полученный результат.

3) Если план не является оптимальным, то производим перераспределение начального плана и переходим к пункту 2.

Таблица 1.

Применяется метод северо-западного угла и метод наименьшей стоимости. Базис будет содержать m+n-1 переменных.