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

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

Транспортная задача – одна из распространенных задач линейного программирования

Цель транспортной задачи – разработка наиболее рациональных путей и способов транспортировки товаров.

Формулировка транспортной задачи:

В m пунктах производства А₁, А₂, …А_m имеется однородный груз в количествах соответственно а₁…а_m. Этот груз необходимо доставить в пункты назначения В₁, В₂, …Вn в количествах b₁,..b_n соответственно. Стоимость перевозки 1 ед. груза (тариф) из пункта А_i в пункт В_j равна C_ij

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

Обозначим x_ij -количество груза, перевозимого из пункта А_i в пункт В_j. Тогда математическая модель закрытой транспортной задачи имеет вид

Оптимальным решением является матрица Хmxn, удовлетворяющая системе ограничений и доставляющая минимум целевой функции L(X).

Для решения транспортной задачи разработан специальный метод, называемый методом потенциалов. Метод аналогичен симплекс методу и имеет следующие три этапа:

· Нахождение исходного опорного решения

· Проверка этого решения на оптимальность

· Переход от одного опорного решения к другому

Условия задачи и ее исходное опорное решение заносят в специальную таблицу, в распределительную таблицу. Клетки, в которые размещаются грузы, называют занятыми, им соответствуют базисные переменные опорного плана, незанятым клеткам соответствуют свободные переменные.

Для нахождения исходного опорного плана часто применяется метод минимального тарифа.

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