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

В ряде транспортных задач необходимо минимизировать время для доставки груза. В таких задачах задаются:

a_i — запасы груза пункта отправления;

b_j — потребности груза в пунктах назначения;

t_ij — время доставки груза из i-го в j-й пункт.

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

Время реализации всего плана перевозок определяется максимальным значением времени перевозки в наиболее отдаленные пункты, следовательно, если нашли N допустимых решений, то общее время перевозки. А для нахождения оптимального решения необходимо найти такое допустимое решение S, время реализации которого минимально.

Для решения этой задачи используется метод разгрузочных цепей.

Алгоритм решения состоит из следующих шагов Вносятся исходные данные a_i, b_j, t_ij в матрицу перевозок.

Находится любым методом исходное допустимое решение и заносится в матрицу перевозок. Не пишутся в матрице только нулевые базисные переменные и свободные переменные.

Определяется максимальное время реализации, записанного в матрице решения задачи, т. е. .

Исследуется клетка с максимальным временем i₁j₁ на возможность разгрузки, т. е. проверяется в матрице решение на оптимальность. Признаком оптимальности решения транспортной задачи по критерию времени является невозможность построения разгрузочной цепи для клетки с максимальным t_ij.

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

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

Пример. Исходное допустимое базисное решение, найденное, например, диагональным методом, приведено в таблице:

Таблица 10.

Далее вычеркиваем все свободные клетки с t_ij t₁₁, чтобы не использовать их для цикла переноса (это клетка t₁₄).

Пытаемся разгрузить клетку 1,1. Она имеет сейчас несколько разгрузочных цепей: а) 1,12,12,21,2; б) 1,13,13,21,2; в) 1,13,13,31,3; г) 1,14,14,31,3.

Однако ни одна из них не позволяет разгрузить клетку за один прием: вначале разгрузим ее на величину 15 по циклу (а), а затем по циклу (б) на величину 5.

В результате получим новое решение в таблице:

Таблица 11.

Для этого решения max (t_ij)=t₂₁=t₃₁=t₄₄=10. Вычерчиваем все свободные клетки с t_ij10, это 1,3; 2,3; 3,2 и, конечно, 1,1 и 2,2.

Попытаемся разгрузить клетки 2,1; 3,1; 4,4. Клетку 3,1 можно разгрузить по циклу 3,14,14,33,3. Выполним операцию сдвига на х₃₁=5 и получим решение в следующей таблице 11.

Теперь разгрузим клетку 2,1 по циклу 2,14,14,42,4, а затем клетку 4,4 по циклу 4,44,33,33,4. В результате получим решение, данное в таблице 12.

Для реализации этого решения требуется max (t_ij)=t₄₃=8.

Таблица 11.

Таблица 12.

Вычеркнем из таблицы свободные клетки с t8, (т.е. клетку 4,2). Попытаемся разгрузить клетку 4,3. Сделать этого нельзя, т.к. в 4-й строке и в 3-м столбце нет незачеркнутых свободных клеток. Следовательно, решение, записанное в таблице, является оптимальным по критерию времени и найти план, который можно реализовать за время меньше t_ij=8, невозможно.