Файл: Экономика практические задачи и решения.pdf

37
дующей итерации.
Итерация 4.
Ккольцевому маршруту № 1 – 0-5-8-3-0 (750 шт.) присоединяем радиаль- ный маршрут 0-12-0 (150 шт.). При этом пункт 12 присоединяем к пункту 3, в результате че- го получаем новую структуру кольцевого маршрута 0-5-8-3-12-0 (1300 шт.). Суммарный пробег автотранспорта сокращается на 14,6 км.
Итерация 5.
Пункты 12 и 8 не объединяем, поскольку они уже входят в состав кольце- вого маршрута 1 (нарушается условие 1).
Итерация 6.
Объединяем два радиальных маршрута: 0-11-0 (475 шт.) и 0-1-0 (450 шт.) в общий кольцевой маршрут (под № 2) 0-11-1-0 (925 шт.). При этом суммарный пробег авто- транспорта сокращается на 13,4 км.
Итерация 7.
Пункты 3 и 6 нельзя объединить по причине нарушения условия 2. Пункт
3 входит в состав кольцевого маршрута 1, и в этом маршруте он занимает «промежуточное» положение, то есть он связан с пунктами 8 и 12: 0-5-8-3-12-0. Радиальный маршрут 0-6-0 можно было бы присоединить к кольцевому маршруту 1 со стороны его «крайних» пунктов –
5 или 12, но к «промежуточным» пунктам 3 и 8 его присоединить нельзя.
Итерации с 8 по 20
повторяют ту же логику рассуждений, что и в предыдущих 7 ите- рациях. Отметим только, что на итерациях 9, 11, 12, 16 и 18 объединение не производится только по причине нарушения условия q
1
+ q
2
≤ c.
Итерации с 21 по 60
уже не имеют смысла, поскольку их выполнение уже не повлечет за собой изменение плана развозки.
Суммарный километровый выигрыш за 20 итераций составляет:
S = 23,0 + 21,4 + 14,6 + 13,4 + 8,8 + 8,3 + 7,9 + 7,8 = 105,3 км а общий пробег автотранспорта, соответственно:
L
1
= L
0
– S = 195 –105,3 = 89,7 км
Графически оптимальная схема развозки представлена на рис. 6. Как видно, оптималь- ная схема развозки включает в себя четыре кольцевых маршрута (вместо первоначальных 12 радиальных маршрутов). Суммарный пробег автотранспорта можно также определить по следующей формуле:
∑
=
=
r
i
i
L
L
1
, где L
i
– протяженность i-го маршрута, км; r – количество маршрутов.
Рассмотрим, например, кольцевой маршрут 0-3-8-5-12-0. Протяженность маршрута оп- ределяется по формуле (см. табл. 4):
L
1
= d
0,12
+ d
12,3
+ d
3,8
+ d
8,5
+ d
5,0
= 7,3 + 5,1 + 4,1 + 5,4 + 12,0 = 33,9 км.
Аналогично рассчитываем протяженность остальных маршрутов. Результаты расчетов сведены в таблицу 6:
Таблица 3.5
Результат решения задачи развозки
№ п/п
Маршрут
Объем поставки, шт Пробег, км
1 0-12-3-8-5-0 1300 33,9 2 0-1-11-0 925 19,0 3 0-9-4-0 650 16,0 4 0-2-7-10-6-0 1400 20,8
Итого 4275
89,7

38 3.2. Методы расчета расстояний на сети
Методы, рассмотренные в предыдущем пункте, можно использовать для расчета рас- стояний как для пары объектов, так и внутри целого множества объектов. Результатом таких расчетов является матрица расстояний между объектами. Однако перечисленные методы не всегда обеспечивают требуемую точность расчетов. Методы базируются на предположении, что расстояние между объектами пропорционально расстоянию между объектами по прямой.
Иными словами, в их основе лежит принцип аппроксимации расстояний. Вместе с тем доро- ги «по прямой» практически никогда не строят. По разным причинам они отклоняются от прямой линии – из-за особенностей местности, ландшафта, из-за особенностей транспортной сети. Довольно часто путь из города в город лежит через целую сеть промежуточных насе- ленных пунктов. Маршрут может поменяться из-за качества дороги и по другим причинам.
Все эти особенности требуют новых, более точных методов расчета расстояний.
Рассматриваемые в данном пункте методы расчета расстояний на сети позволяют учесть все вышеперечисленные факторы и обеспечить высокую точность расчетов. Можно с уверенностью утверждать, что точность расчетов на сети напрямую зависит от точности расчетов на отдельных участках сети.
Результатом расчетов расстояний являются две матрицы – матрица расстояний и
матрица указателей
. Для разъяснения сущности и назначения второй матрицы рассмотрим следующий пример.
Пример
Рассмотрим транспортную сеть, которая состоит из девяти пунктов. Расстояний между пунктами представлены на рисунке 3.7, а под ним приведены матрица расстояний и матрица указателей.
Представим, что схема транс- портной сети – это карта, на которой в одном из пунктов располагается иг- ральная фишка, например, в пункте
A. Необходимо передвинуть фишку из пункта 1 в пункт 7. Поставим два вопроса:
1)
Какой путь должна пройти фишка?
2)
Какой маршрут для фишки является оптимальным?
Ответы на эти вопросы легко найти самостоятельно, поскольку сеть маленькая и решение определяется элементарным подсчетом. Однако для сетей больших размеров, в которых представлено 20,
30, 50, 100 и более пунктов решение уже не представляется таким легким. В этом случае и применяется матрица расстояний и матрица указателей, которые для рассматриваемого слу- чая представлены в следующих таблицах 3.6 и 3.7.
Расстояние от пункта 1 до пункта 7 находится из матрицы расстояний – это ячейка, ко- торая располагается на пересечении строки 1 и столбца 7. Расстояние это составляет 31 км.
Для поиска оптимального маршрута используется матрица указателей. Находим ячейку на пересечении строки 1 и столбца 7. В найденной ячейке указан пункт 3. Перемещаем фиш- ку в пункт 3 и ставим новый вопрос: как добраться из пункта 3 в пункт 7? Находим ячейку на пересечении строки 3 и столбца 7, где указан новый пункт 8. Перемещаем фишку в пункт 8 и формулируем вопрос: как добраться из пункта 8 в пункт 7? На пересечении строки 8 и столбца 7 указан пункт 6. Перемещаем фишку в пункт 6. На пересечении строки 6 и столбца
Рис. 3.6. Транспортная сеть

39 7 стоит число 7. Перемещаем фишку в пункт 7. Оптимальный маршрут найден: 1 – 3 – 8 – 6 –
7.
1
7 9 14 20 24 31 16 5 1
2 3 3 2 3 3 3 9 7
2
16 20 13 31 25 23 8 1 2
1 5 5 1 5 1 9 9 16 3
5 12 15 22 7 8 1 1 3
4 4 8 8 8 9 14 20 5 4
7 14 19 6 13 3 5 3 4
5 8 5 8 3 20 13 12 7 5
19 12 13 20 2 2 4 4 5
7 7 4 4 24 31 15 14 19 6
7 8 23 8 8 8 8 7 6
7 8 8 31 25 22 19 12 7 7
15 30 6 5 6 5 5 6 7
6 6 16 23 7 6 13 8 15 8
15 3 3 3 4 4 6 6 8
3 5 8 8 13 20 23 30 15 9
1 2 3 3 3 3 3 3 9
Протяженность оптимального маршрута определяется как сумма длины отдельных участков маршрута, например: d(1,7) = d(1,3) + d(3,8) + d(8,6) + d(6,7) = 9 + 7 + 8 + 7 = 31 км.
Следует отметить, что матрица указателей носит только вспомогательный характер. Ее удобно использовать при работе на больших сетях, а также при программной реализации ниже приводимых алгоритмов, когда при распечатке компьютерного решения какой-либо задачи желательно указать оптимальный маршрут движения транспортного средства по сети.
Задание
Используя рисунок, постарайтесь самостоятельно составить матрицу расстояний и ука- зателей. Используйте для расчетов калькулятор. В конце сравните полученный Вами резуль- тат с данными матрицы расстояний и указателей, представленных в табл. 3.6 и 3.7.
Когда Вы выполните задание, то Вы убедитесь, что составление матрицы расстояний и указателей вручную даже для такой простой сети – задача довольно сложная и трудоемкая.
Поэтому для расчетов используются специальные методы, которые позволяют автоматизи- ровать этот процесс. В данном разделе мы рассмотрим только два метода расчетов: метод потенциалов, метод «мельницы».
3.2.1. Метод потенциалов
Метод потенциалов рассмотрим на конкретном примере. В качестве исходных данных будем использовать транспортную сеть, представленную на рисунке … . Требуется рассчи- тать матрицу расстояний и матрицу указателей для данной транспортной сети. Ниже приво- дится один цикл расчетов (одна итерация), а затем приводится обобщенное описание алго- ритма метода потенциалов.
Один цикл расчетов позволяет нам рассчитать значения для одной строки матрицы рас- стояний и матрицы указателей. Поскольку транспортная сеть содержит в себе 9 пунктов, а матрицы, соответственно, 9 строк и 9 столбцов, для полного заполнения матриц требуемыми данными необходимо выполнить 9 циклов расчета. Начнем первый цикл, в ходе которого рассчитаем требуемые значения для второго пункта, т.е. для второй строки матрицы рас- стояний и матрицы указателей. При этом будем использовать следующие обозначения: v(i) – значение потенциала i-ой вершины;
Таблица 3.6
Матрица расстояний
Таблица 3.7
Матрица указателей

40
w(i) – значение указателя i-й вершины; c(i,j) – длина звена, связующего i-ю и j-ю вершины.
На рисунке значение потенциала i-й вершины указывается над самой i-й вершиной, а радом в скобках обозначается значение указателя i-й вершины. Например, вершина 4: v(4) = 20, w(4) = 5. Значение длины связую- щего звена указывается рядом со звеном с добавлением знака «+», например, c(3,4) = 5.
1.
Выберем в качестве начальной
вершины
– вершину 2. Начальной вершине присвоим следующие значения: v(2) = 0, w(2) =
2. Иными словами, начальная вершина обладает нулевым потенциалом и нулевым указателем.
2.
Все вершины сети распределя-
ем по уровням
, как показано на рисунке … .
Распределение производится следующим об- разом:
1) первый уровень включает в себя только одну начальную вершину;
2) второй уровень включает вершины, которые имеют связующие звенья с вер- шиной первого уровня, т.е. вершины 9, 1 и 5;
3) третий уровень включает вершины, которые имеют связующие звенья с вер- шинами второго уровня, т.е. вершины 3, 4 и 7;
4) четвертый уровень включает вершины, которые имеют связующие звенья с вершинами третьего уровня, т.е. вершины 8 и 6.
3.
Вводим такие понятия, как ведущий и ведомый уровни: ведущий уровень – это последний по счету уровень, у которого определены значе- ния потенциалов и указателей; ведомый уровень – это уровень, у которого не определены значения потенциалов и указателей и который следует сразу за ведущим уровнем.
Множество вершин ведущего уровня будем обозначать множеством X, множество вершин ведомого уровня – множеством Y.
Определяем ведущий и ведомый уровни.
На данном этапе расчетов ведущим являет- ся первый уровень, т.е. X = {2}, а ведомым, соответственно, второй уровень, т.е. Y = {1, 5,
9}.
4.
Известно, что вершины ведомого уровня связаны с начальной вершиной. Дли- ны связующих звеньев: c(2,9) = 8, c(2,1) = 7, c(2,5) = 13. Тогда определяем потенциалы и
указатели
вершин ведомого второго уровня по следующей схеме: v(j) = v(i) + c(i,j) = c(i,j), i
∈X, j∈Y w(j) = j, j
∈Y
В результате получаем:
1) вершина 9: v(9) = c(2,9) = 8, w(9) = 9;
2) вершина 1: v(1) = c(2,1) = 7, w(1) = 1;
3) вершина 5: v(5) = c(2,5) = 13, w(5) = 5.
5.
Производим проверку на разность потенциалов вершин ведомого уровня.
Находим вершины ведомого уровня, которые имеют между собой связующее звено. Такими вершинами на втором уровне являются вершины 1 и 9: c(1,9) = 5. Известно, что v(1) = 7 и v(9) = 8. Проверка разности потенциалов состоит в проверке выполнения следующего усло- вия:
Рис. 3.7. Пример расчета потенциалов и
указателей на транспортной сети

41
v(i) – v(j)
≤ c(i,j), i,j∈Y, v(i) ≥ v(j), то есть, применительно к вершинам 1 и 9: v(9) – v(1)
≤ c(1,9) → 8 – 7 ≤ 5 (выполняется).
Поскольку условие выполняется, то объявляется, что проверка на разность потенциалов пройдена успешно. В этом случае никаких действий по пересчету значений потенциалов и указателей вершин 1 и 9 не производится.
6.
После проверки на разность потенциалов переопределяем ведущий и ведо-
мый уровни
сети. Первый уровень теряет статус ведущего. Ведущим уровнем объявляется второй уровень, т.е. X = {9, 1, 5}, а ведомым уровнем, соответственно, третий уровень, т.е. Y
= {3, 4, 7}.
7.
Известна длина связующих звеньев между вершинами ведущего и ведомого уровней: c(9,3) = 8, c(1,3) = 9, c(5,4) = 7, c(5,7) = 12. Определяем потенциалы и указатели вершин ведомого третьего уровня по следующей схеме: v(j) = min{v(i) + c(i,j) | i
∈X}, j∈Y, т.е. путь к вершине j проводим через такую вер- шину i, которая обеспечивает вершине j минимальное значение потенциала; w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | i
∈X}, i*∈X, j∈Y, т.е. указатель j-й вершины полагается равной указателю той i-й вершины ведущего уровня, которая обеспечи- вает j-й вершине минимальное значение потенциала.
Таким образом, получаем: вершина 3: v(3) = min{v(9)+c(9,3); v(1)+ c(1,3)} = min{8 + 8 = 16; 7 + 9 = 16} = 16, w(3) = w(9) = 9 или w(3) = w(1) = 1. В данном случае складывается ситуация, когда из пункта
2 в пункт 3 можно проехать либо через пункт 9, либо через пункт 1. И в том, и в другом слу- чае длина пути будет одинаковая – 16 км. Поскольку все равно, через какой пункт добирать- ся, то можно выбрать любой, например, w(3) = w(1) = 1; вершина 4: v(4) = v(5) + c(5,4) = 13 + 7 = 20, w(4) = w(5) = 5; вершина 7: v(7) = v(5) + c(5,7) = 13 + 12 = 25, w(7) = w(5) = 5.
8.
Производим проверку на разность потенциалов вершин ведомого уровня.
Между вершинами 3 и 4 существует связующее звено: c(3,4) = 5 при 3, 4
∈Y. Известны по- тенциалы: v(3) = 16, v(4) = 20. Проверяем на выполнение условие: v(4) – v(3)
≤ c(3,4) → 20 – 16 ≤ 5 (выполняется).
Проверка пройдена, никаких действий не производим.
9.
После проверки на разность потенциалов переопределяем ведущий и ведо-
мый уровни
сети. Второй уровень теряет статус ведущего. Ведущим уровнем объявляется третий уровень, т.е. X = {3, 4, 7}, а ведомым уровнем, соответственно, четвертый уровень, т.е. Y = {8, 6}.
10.
Известна длина связующих звеньев между вершинами ведущего и ведомого уровней: c(3,8) = 7, c(4,8) = 6, c(7,6) = 7. Определяем потенциалы и указатели вершин ве- домого четвертого уровня по известной уже схеме: v(j) = min{v(i) + c(i,j) | i
∈X}, j∈Y; w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | i
∈X}, i*∈X, j∈Y.
Таким образом, получаем: вершина 3: v(8) = min{v(3)+c(3,8); v(4)+ c(4,8)} = min{16 + 7 = 23; 20 + 6 = 26} = 23, w(8) = w(3) = 1. В данном случае минимальное значение потенциала вершины 8 обеспечива- ется при движении через вершину 3. Поэтому указатель вершины 8 полагается равным ука- зателю вершины 3; вершина 6: v(6) = v(7) + c(7,6) = 25 + 7 = 32, w(6) = w(7) = 5.
11.
Производим проверку на разность потенциалов вершин ведомого уровня.
Между вершинами 8 и 6 существует связующее звено: c(8,6) = 8 при 8, 6
∈Y. Известны по- тенциалы: v(8) = 23, v(6) = 32. Проверяем на выполнение условие: v(6) – v(8)
≤ c(6,8) → 32 – 23 ≤ 8 (не выполняется).

42
Условие нарушает, проверка на разность потенциалов объявляется не пройденной. То- гда производится перерасчет значений потенциала и указателя для вершины, которая обла- дает большим потенциалом по следующей схеме: v(i) = v(j) + c(i,j) и w(i) = w(j).
Применительно к вершинам 6 и 8 получаем: вершина 6: v(6) = v(8) + c(8,6) = 23 + 8 = 31, w(6) = w(8) = 1.
Данные расчеты означают, что из пункта 2 в пункт 6 следует ехать через пункт 8, а не пункт 7, поскольку в первом случае длина пути составит 31 км против 32 км во втором слу- чае.
12.
Четвертый уровень является последним по счету, а потому цикл расчета можно считать завершенным. Полученные значения потенциалов и указателей заносим во вторую строку матрицы расстояний и матрицы указателей, как показано в таблице:
Таблица 3.8
Вершины сети
Матрица
1
2
3
4
5
6
7
8
9
Расстояний 7
0 16 20 13 31 25 23 8
Указателей 1
0
1 5 5 1 5 1 9
Полученные данные можно сравнить с данными второй строки матрицы расстояний и матрицы указателей ( табл. 3.6 и 3.7).
По окончании первого цикла расчета начинаются новые циклы, в которых в качестве начальной вершины выбираются вершины 1, 3, 4, …, 9.
Те шаги, которые были выполнены в ходе реализации рассмотренного одного цикла расчетов, можно свести в единый общий алгоритм. Ниже приводится краткое описание дан- ного алгоритма:
Шаг 1.
Определяется начальная вершина сети.
Шаг 2.
Все множество вершин сети разбивается по уровням. При этом первый уровень включает в себя одну начальную вершину, а все прочие вершины распределяются по уров- ням таким образом, чтобы: вершины (k-1)-го уровня имели связующие звенья с вершинами k-го уровня; вершины k-го уровня имели связующие звенья с вершинами (k+1)-го уровня; вершины (k-1)-го уровня не имели связующих звеньев с вершинами (k+1)-го уровня.
Шаг 3.
Первый уровень объявляется ведущим уровнем, а второй уровень – ведомым.
Шаг 4.
Определяются значения потенциалов и указателей вершин ведомого уровня.
Если ведомым является второй уровень сети, то значения определяются по формулам: v(j) = v(i) + c(i,j) = c(i,j), i
∈X, j∈Y w(j) = j, j
∈Y где X – множество вершин ведущего уровня, Y – множество вершин ведомого уровня.
Если ведомым является третий, четвертый и остальные уровни сети, то значения опре- деляются по формулам: v(j) = min{v(i) + c(i,j) | i
∈X}, j∈Y; w(j) = w(i*) : v(i*) + c(i*,j) = min{v(i) + c(i,j) | i
∈X}, i*∈X, j∈Y.
Шаг 5.
Производится проверка на разность потенциалов среди вершин ведомого уров- ня, которые имеют между собой связующие звенья. При этом проверяется выполнение следующего условия: v(i) – v(j)
≤ c(i,j), i,j∈Y, v(i) ≥ v(j).