3.2.2. Метод «мельницы»

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

Шаг 0. Определяются значения матрицы расстояний D = [dij] и матрицы указателей L = [lij]. Если dij>0, то lij=j, i?j.

Шаг 1. Выбираются пара вершин данной сети (i, j), i?j.

Шаг 2. Выбирается вершина k данной сети, k?i, k?j.

Шаг 3. Если значение d(i,j) не определено, а значения d(i,k) и d(k,j) определены, или если определены все три значения d(i,j), d(i,k), d(k,j), но при этом выполняется условие d(i,j)>d(i,k)+d(k,j), то d(i,j):=d(i,k)+d(k,j), lij=lik.

Шаг 4. Повторять шаги 2-3 до тех пор, пока не будут перебраны все вершины k данной сети.

Шаг 5. Повторять шаги 1-4 до тех пор, пока не будут перебраны все пары вершин (i,j) данной сети.

Шаг 6. Процесс решения (цикл) повторяется до тех пор, пока в ходе очередного решения не будет изменено ни одно значение d(i,j). % Вопросы для проверки знаний

1. Дайте своими словами определение задачи развозки

2. Опишите, что такое радиальный и кольцевой маршруты

3. В чем заключаются основные особенности метода Кларка-Райта?

4. Каким целям служат матрица расстояний и матрица указателей? O Задачи для самостоятельного решения Задача 3.1. Задача развозки

Известно, что складской комплекс располагается в пункте с координатами [25, 25]. В распоряжении администрации складского комплекса имеется четыре машины грузовместимостью 1500 шт. Требуется составить оптимальную схему развозки грузов, если известны координаты местоположения и объем спроса следующих получателей:

Задача 3.2. Расчет расстояний на сети

Рассчитайте матрицу расстояний и матрицу указателей при следующих исходных данных:

Вариант 1 Вариант 2

Вариант 3 Вариант 4