Транспортная задача

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

Имеется m пунктов производства однородного продукта с объемами производства и n пунктов потребления с объемами потребления . Известна стоимость перевозки единицы продукта от каждого пункта производства до каждого пункта потребления: ,

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

Объемы потребления Объемы поставок ai	b1	b2	…	bn	Потенциалы ui
а1	c11	c12	…	c1n	u1=0
a2	c21	c22	…	c2n	u2
…			…		…
am	cm1	cm2	…	cmn	um
Потенциалы vj	v1	v2	…	vn

Различают два типа транспортных задач. Если суммарные запасы продукта поставщиков равны суммарным объемам потребления

,

то это задача закрытого типа. В противном случае задачу называют задачей открытого типа.

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

Решение транспортной задачи начинают с нахождения первоначального плана поставок. Наиболее часто для этих целей применяют метод «минимального тарифа». Суть метода в следующем.

Распределение поставок начинается с клеток, в которых тариф перевозок c_ij наименьший. В эти клетки помещаются наибольшие возможные необходимые поставки. Далее поставки распределяются по возрастанию тарифов по свободным клеткам с учетом запасов производителей и нужд потребителей.

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

1. Найти первоначальное опорное решение (распределение поставок), например, методом «минимального тарифа».

2. Проверить решение на оптимальность методом потенциалов.Для этого найти потенциалы для каждой строки и столбца из условия

u_i + v_j = c_ij,

справедливого для занятых клеток. Первоначально положить u₁=0.

3. Для всех свободных клеток рассчитать оценки D_ij= u_i + v_j - c_ij.

Если все D_ij£0, то найденное решение оптимально.

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

4. Если решение не оптимально, необходимо перейти к новому опорному решению (новому плану поставок), которое ближе к оптимальному, чем предыдущее. Необходимо ввести в базис свободную переменную имеющую наибольшую положительную оценку. Для этого построить цикл для соответствующей этой переменной клетки. Цикл строится по занятым клеткам и имеет прямоугольную конфигурацию. Вершины цикла занумеровать, начиная со свободной клетки. Среди клеток с четными номерами найти наименьший объем поставок l и перераспределить его по циклу: в клетки с нечетными номерами его надо прибавить к поставке, в клетки с четными номерами вычесть. Выписать новое решение и значение целевой функции.

5. Переход в п. 2.

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

При нарушении баланса между объемами производства и потребления в алгоритм решения транспортной задачи вносятся следующие дополнения.

Если суммарные поставки меньше суммарных потребностей, т.е.

,

то вводят фиктивный пункт производства с объемом

.

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

Если суммарные поставки больше суммарных потребностей, т.е.

,

то вводят фиктивный пункт потребления с объемом

.

При этом в таблице появляется дополнительный столбец. Тарифы в клетках этого столбца выбираются аналогично предыдущему правилу.

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

Вырожденность и альтернативный оптимум в транспортных задачах

Если в процессе решения транспортной задачи получено решение, в котором количество занятых клеток меньше m+n-1, то это решение называется вырожденным. Расчет потенциалов выполнить невозможно. В этом случае недостающее число занятых клеток восполняется путем введения нулевых поставок в некоторые клетки (их выбор определяется возможностью расстановки потенциалов). Далее такие клетки считаются занятыми, и решение продолжается обычным образом.

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

Если два решения и являются оптимальными, то множество всех оптимальных решений имеет вид:

, где .

Если оптимальных решений более двух, то множество всех оптимальных решений является множеством выпуклых линейных комбинаций этих оптимальных решений, т.е. ответ следует записать в виде:

, где