ТРАНСПОРТНАЯ ЗАДАЧА

Транспортную задачу можно считать частным случаем ЗЛП. Постановка задачи: имеется некоторое количество поставщиков обладающих запасами М₁, М₂,…, М_i некоего товара, и несколько потребителей со спросами на данный товар N₁, N₂, …, N_j.

Также известны коэффициенты затрат на перевозку единицы груза для каждой пары «поставщик – потребитель» a_ij. Необходимо составить такой план перевозок при котором:

1) мощности всех поставщиков будут реализованы;

2) спрос всех потребителей удовлетворены;

3) функция суммарных затрат примет минимальное значение.

Экономико-математическая модель задачи представляется как система двух уравнений и целевой функции:

.

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

1. Проверить является ли задача закрытой (если суммарная мощность поставщиков меньше, то добавляется дополнительная строка, соответствующая «фиктивному» поставщику, если мощность поставщиков больше спроса, добавляется дополнительный столбец, соответствующий «фиктивному» потребителю).

2. Найти первоначальное распределение поставок методом наименьших затрат.

3. Посчитать функцию затрат, найти матрицу оценок свободных клеток методом потенциалов.

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

5. Повторить пункты 3 и 4.