Решение транспортной задачи

Пример

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

Поставщики       \Потребители					Запасы товаров,
	7	20	3	15	225
	3	14	10	20	250
	15	25	11	19	125
	11	12	18	6	100
Заявки на закупку товаров,	120	150	110	235

Решение

Экономико-математическая модель задачи

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

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:   

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

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

В нашем случае:

Модель транспортной задачи открытая. Вводим фиктивного потребителя, которому требуется  85 единиц груза.

Правило минимального элемента

Заполняем таблицу по правилу минимального элемента.

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту , поэтому в клетку помещаем . В этом случае 5-й столбец в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьшие тарифы имеют клетки  и

Далее действуя по аналогичной схеме:

Число занятых клеток должно быть .

Решение транспортной задачи методом потенциалов

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

Найдем оценки свободных клеток:

Для клетки ( 3, 5) строим цикл.

Найдем оценки свободных клеток:

Для клетки ( 1, 1) строим цикл.

Найдем оценки свободных клеток:

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

Минимальные транспортные издержки оптимального плана:

При реализации оптимального плана у поставщика  останется нереализованный товар в размере 85 ед.