8.6. Доставка груза в кратчайший срок
Для решения подобных задач рассмотренный ранее метод потенциалов непригоден. Эти задачи решаются с помощью специального алгоритма.
Любым способом строим один из опорных планов.
Определяем наибольший элемент /' из всех і у, соответствующих занятым клеткам, и все клетки с элементами ty > Ґ (это могут быть лишь свободные клетки) вычеркиваются.
Начиная с клетки с наибольшим временем доставки /', строим разгрузочный цикл так, чтобы клетки с нечетными номерами (считая первой разгружаемую клетку с элементом /') были заняты-ми. Одна из вершин разгрузочного цикла будет свободной. В общем случае построение разгрузочного цикла неоднозначно.
Сделав в свободную вершину цикла поставку р, проводим компенсации по вершинам цикла, определяем величину р (так же, как в методе потенциалов), строим новый план.
Переходим ко второму пункту алгоритма, естественно, не учитывая ранее вычеркнутые клетки.
Алгоритмом пользуемся до тех пор, пока построение разгрузочного цикла становится невозможным.
Последний полученный план является оптимальным, наибольшее время, соответствующее занятой клетке в этом плане, определяет наименьшее время по доставке грузов всем потребителям.
Пример 8.4.
Определить оптимальный план перевозок из условия доставки груза в кратчайший срок. Известны ресурсы а;. 30; 35; 40, потребности вк: 20; 34; 16; 10; 25 и матрица
7
10
НЫ1= 15 6 9 ^3416
где tik — время, затрачиваемое на перевозку груза из /-го пункта отправления в к-н пункт назначения.
(2 6 3 4
Решение
Запишем в виде таблицы исходную информацию и внесем в нее один из опорных планов (пункт 1 алгоритма).
Таблица 8.13
Исходная информация и опорный план Поставщики Потребители Запасы, т Вх В2 Вз в4 В5 Лу 2
20 6
10 3 4 8 30 Аг 1 5
24 6
И -р 9 7
Р 35 Аз 3 4 і
5 + P 6
10 10
25 — р 40 Потребность, т 20 34 16 10 25 105
Согласно пункту 2 алгоритма Ґ = t35 = 10 строим цикл перерасчета (3-й пункт). В свободную вершину цикла (2,5) делаем поставку р и проводим компенсации по вершинам цикла, затем определяем величину р:
р=11.
Строим новый план и переходим к пункту 2 алгоритма (табл.
8.14).Таблица 8.14
Промежуточный план распределения Поставщики Потребители Запасы, т Вх Вг Вз В, В5 Ах 2
20 -р 6
10 + р 3 4 8 30 а2 і 5
24 — р 6 9 7
И + р 35 Аз 3
Р 4 1
16 6
10 1
И-Ро 40 Потребность, т 20 34 16 10 25 105
В новой таблице Ґ = = 10 (клетка 3,5 оказалась не полностью разгруженной). Из анализа нового цикла пересчета заключаем: р = 14; строим новый план (табл. 8.15).
Таблица 8.15
Оптимальный план Поставщики Потребители Запасы, т Вх в2 Вз В4 В5 А, 2
6 6
24 3 4 X 30 а2 I 5
10 6 7
25 35 Аз 3
14 4 1
16 6
10 40 Потребность, т 20 34 16 10 25 105 8.1.
Ґ = /25 - 7, вычеркиваем все свободные клетки, ДЛЯ которых tjj > 7. Для дальнейшего улучшения плана необходимо разгрузить клетку (2,5), но построение разгрузочного цикла для этой клетки невозможно. На основании этого заключаем, что решение, полученное в последней таблице, является оптимальным, обеспечивающим перевозки за время /min = 7.