33
V – номер уровня ветвления,
mv ,0
. При v=0 имеем все множество решений V,
а при v=m подмножество решений, представляющее отдельную перестановку u
всех m пунктов. Во-вторых, связанное с первым правило оценки каждого из
подмножеств и исключения из рассмотрения неперспективных. В качестве
оценки используется значение нижней (верхней) границы целевой функции, ко-
торое заведомо не меньше (не больше) минимального (максимального) из воз-
можных значений целевой функции анализируемого подмножества вариантов
[21].
Вычислительная схема метода ветвей и границ с учетом приведенных
правил выглядит следующим образом.
Положим v=0 и вычислим оценку ω(v
0
) целевой функции. Если после
этого удастся найти такое решение
u
, что
)()(
0
vu
, то
u
- оптимальное ре-
шение, в противном случае
)(u
=R, где R – наилучшее, достигнутое на рас-
сматриваемом этапе, значение целевой функции. Значение R принято называть
рекордом, а соответствующую R перестановку u - решением задачи. В боль-
шинстве случаев при оптимизации МВГ на нулевом уровне не представляется
возможным определить оптимальное решение. Тогда для сокращения объема
вычислений целесообразно найти приближенное (по возможности близкое к
оптимальному) решение и приравнять его к рекорду.
Если оптимального решения при v=0 не найдено, то полагаем v=1 и по
некоторому правилу разбиваем (ветвим) V на конечное число непересекающих-
ся подмножеств первого уровня разбиения.
V=V
1
’
V
2
’
…
V
s
’, (6)
причем каждое из них характеризуется тем свойством, что включает в
себя все возможные варианты решения с одинаковым началом
i
u
, имеющим
общий элемент,
si ,1
, где s – число анализируемых подмножеств.
Требование к условию непересекаемости подмножеств классически
упоминается во всех описаниях сущности МВГ. Однако, требование это не яв-
ляется принципиальным и может быть игнорировано с учетом выполнения
34
процедуры удаления всех пересекающихся подмножеств за исключением под-
множества с наибольшим уровнем информативности.
Таким образом, основными шагами метода ветвей и границ являются:
Шаг 1. Определение целевой функции для произвольного варианта рас-
пределения продукции. Объявление этого значения рекордом F=R.
Шаг 2. Разбиение множества возможных решений на непересекающиеся
подмножества.
Шаг 3. Определение нижних границ для каждого из подмножеств уровня
ветвления. Удаление неперспективных подмножеств (с НГ≥R).
Шаг 4. Выбор наиболее перспективного подмножества (с минимальной
нижней границей). Разбиение этого подмножества на подмножества следующе-
го уровня ветвления.
Шаг 5. Определение целевой функции. Если F
i
<R – переназначение ре-
корда R=F
i
, иначе – переход к шагу 3.
При невозможности определения – переход к шагу 3.
Шаг 6. Если все подмножества вычеркнуты – вывод результата с F=R.
Одним из основных преимуществ описанного метода является его уни-
версальность применительно к классу задач комбинаторного типа, однако свой-
ственны ему и некоторые недостатки. Во-первых, при реализации описанной
схемы применительно к конкретным задачам, исходя из особенностей, необхо-
димо конкретизировать правила разбиения множества вариантов решений на
подмножества и построить алгоритм вычисления границ, что зачастую практи-
чески сложно[31]. Во-вторых, особую трудность иногда вызывает программная
реализация разработанных на основе МВГ алгоритмов.
Метод Дийкстры
Пусть дан граф G = (X, Г), дугам которого приписаны веса (стоимо-
сти), задаваемые матрицей С = [c
jj
].
Пусть l(x
i
) – пометка вершины x
i
.
Присвоение начальных значений
35
Шаг 1. Положить l(s) = 0 и считать эту пометку постоянной. Положить
l(x
i
)=∞ для всех x
i
≠s и считать эти пометки временными. Положить p=s.
Обновление пометок
Шаг 2. Для всех
)( pÃx
i
, пометки которых временные, изменить по-
метки в соответствии со следующим выражением:
)].,()(),(min[)(
iii
xpcplxlxl
(7)
Превращение пометки в постоянную
Шаг 3. Среди всех вершин с временными пометками найти такую, для
которой
)].(min[)(
*
i
i
xlxl
(8)
Шаг 4. Считать пометку вершины x
i
* постоянной и положить р = x
i
*.
Шаг 5. (i) Если р=t, то l(р) является длиной кратчайшего пути. Оста-
нов.
Если р≠t, перейти к шагу 2.
Если все вершины отмечены как постоянные, то эти пометки дают
длины кратчайших путей. Останов. Если, некоторые пометки являются вре-
менными, перейти к шагу 2.
Результаты дополнительно проведённого уточняющего SWOT – анализа
показывают, что самой значимой проблемой в области распределения товара,
по мнению экспертов, является разработка оптимальных маршрутов доставки.
Так как аптечные пункты расположены в разных частях города, неэф-
фективность доставки влечет за собой отсутствие нужного отвара и, как след-
ствие, потерю постоянных покупателей.
Изменение маршрутов распределения и контроль за исполнением до-
ставки, несомненно, приведет к бездефектному наличию лекарственных препа-
ратов в пунктах доставки и оптимизации расходов ГСМ.
Следовательно, интересы потребителей транспортных услуг будут со-
блюдены на основе минимизации транспортных расходов обеих компаний.
36
2.3 Оптимизация маршрутов движения
Произведем расчет кратчайших маршрутов и выявим оптимальные схе-
мы распределения.
ИП Коновалова М.Б. устойчиво сотрудничает в плане обеспечения
транспортными услугами сети аптек г. Ростова.
Наибольшие объёмы перевозок связаны с сеть аптек ООО «Валентина».
В настоящее время сеть аптек ООО «Валентина» включает центральную
аптеку и 8 аптек периферийного значения.
Центральная аптека – ул. Волкова 7/5;
аптека №1 – ул. Фурмановская 117;
аптека №2 – ул. Волкова 23;
аптека №3 – пр. Космонавтов 16;
аптека №4 – пр. Нагибина 55;
аптека №5 – ул. Ларина 43;
аптека №6 – ул. Белорусская 140;
аптека №7 - ул. Казахская 74;
аптека №8 – пер. Сальский 35.
Зная адреса аптечных пунктов, можно для каждой пары аптек с привяз-
кой к реальной местности построить граф сети.
При этом исходный и конечный пункты определяются непосредственно
из пунктов пары аптек, а промежуточными пунктами будут выступать различ-
ного рода перекрестки дорог на пути следования.
Кратчайшим путем между двумя точками на плоскости является прямая.
Однако применительно к дорожной сети не всегда два пункта связаны
прямой. Кроме того, на практике не всегда кратчайший по расстоянию маршрут
является оптимальным. Это может объясняться и качеством дорог и интенсив-
ностью загруженности и т.п.
Для приближения задачи поиска кратчайших маршрутов к реальной си-
туации введем поправочные коэффициенты для дорог различного качества и в
37
зависимости от усредненной интенсивности движения по этим дорогам (коэф-
фициенты могут формироваться методом экспертного оценивания)[34].
Примем следующие поправочные коэффициенты:
1 –для дорог с асфальтным покрытием и двумя рядами движения в каж-
дом направлении;
1,1 –для дорог с асфальтным покрытием и одним рядом движения в
каждом направлении;
1,5 –для дорог с гравийным покрытием;
1 – для дорог со слабой интенсивностью движения;
1,2 – для дорог со средней интенсивностью;
1,5 – для дорог с интенсивным движением.
Применительно к представленным допущениям синтезируем матрицу
кратчайших маршрутов на примере одного из них, связывающего центральную
аптеку, расположенную по адресу: г. Ростов-на-Дону, ул. Волкова 12, и аптеку
№8, расположенную по адресу г. Ростов-на-Дону, пр. 40 лет Победы 39/В.
Граф дорожной сети, связывающей эти аптеки имеет следующий вид,
рисунок 8.
Расстояния между каждой парой вершин представленного графа приве-
дены с учетом введенных поправочных коэффициентов и указаны в виде весов
дуг в метрах (значения округлены до десятков).
В результате проведенных расчетов, матрица протяженностей кратчай-
ших маршрутов имеет следующий вид в таблице 7.
Задача поиска оптимального по критерию минимума суммарного рас-
стояния варианта объезда из исходного аптечного пункта (на ул. Волкова 12)
подразумевает n! Альтернатив. Для приведенного случая это значение превы-
шает 40000 вариантов. Без сомнения перебирать такое множество вариантов не
представляется целесообразным.
Таблица 7
Матрица протяженностей кратчайших маршрутов
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
38
S
0
2370
1380
1440
1780
3200
2760
2110
3250
S
1
-
1750
2080
1130
4230
3130
1160
3050
S
2
1750
-
970
3770
2300
640
1900
2400
S
3
2120
970
-
1410
2250
3980
4100
2900
S
4
1150
3800
1410
-
970
1460
700
1740
S
5
4290
2300
2250
970
-
1230
1990
4350
S
6
3130
640
3970
1460
1220
-
2550
720
S
7
1160
1810
4020
730
2010
2500
-
1550
S
8
3100
2340
2840
1670
4320
720
1540
-
В процессе исследований разработан алгоритм поиска оптимального ва-
рианта с использованием метода ветвей и границ.
Шаг 1. Найдем произвольный вариант объезда, определим суммарное
расстояние, соответствующее этому варианту.
Пусть это будет вариант 0-3-2-6-8-7-1-4-5. Такому варианту соответ-
ствует суммарное расстояние
f=1440+970+640+720+1540+1160+1130+970=8570 м.
Поскольку решение единственное, то соответствующее ему значение
целевой функции F назовем рекордом R=f.
Шаг 2. Разобьем все множество решений на непересекающиеся подмно-
жества.
Находясь в исходном пункте S
0
, доставщик фармацевтической продук-
ции может отправиться по своему выбору в любой из 8 пунктов, там выгрузить
часть продукции и продолжить объезд.
При этом объезд будет продолжаться, пока доставщик не объедет все
аптеки сети и не выгрузит весь товар.
Оформим это положение в виде дерева решений, рисунок 16.
39
Ω
1
2
3
4
5
6
7
8
Рисунок 16 Разбиение множества решений на подмножества
первого уровня
Шаг 3. Определим нижние границы (наилучшие теоретически достижи-
мые оценки) для каждого подмножества для выбора наиболее перспективного.
Для этого:
1. Вычеркнем нулевую строку (т.к. из пункта S
0
мы уже выехали и тот
один из восьми столбцов, в который уже приехали) – таблица 8.
Таблица 8
Упрощенная таблица для нулевого подмножества
2. Определим значение нижней границы путем сложения минималь-
ных элементов, стоящих в столбцах невычеркнутой части матрицы и уже со-
вершённого переезда 2370.
G
1
=(640+970+730+970+640+700+720)+2370=7740.
Аналогичным образом определим все нижние границы первого
уровня разбиения.
G
2
=5880+1380=7260;
1
750
2
080
1
130
4
230
3
130
1
160
3
050
-
970
3770
2300
640
1900
2400
970
-
1410
2250
3980
4100
2900
3800
1410
-
970
1460
700
1740
2300
2250
970
-
1230
1990
4350
640
3970
1460
1220
-
2550
720
1810
4020
730
2010
2500
-
1550
2340
2840
1670
4320
720
1540
-
40
G
3
=5630+1440=7070;
G
4
=5870+1780=7650;
G
5
=5630+3200=8830;
G
6
=5880+2760=8640;
G
7
=5820+2110=7930;
G
8
=5800+3250=9050.
Шаг 4. Удаление неперспективных подмножеств (тех подмножеств. У
которых значение нижней границы больше или равняется значению рекорда).
Таким образом, из дальнейшего рассмотрения удаляются подмножества
с G
5
, G
6
, G
8
, т.к. имеют границу, большую, чем 8570 м.
Наиболее перспективным является подмножество 3 с наименьшей ниж-
ней границей G
3
=7070. Разветвим это подмножество и определим нижние гра-
ницы рисунок 17.
Ω
1
2
4
5
6
7
8
3
7070
1
2
4
5
6
7
8
7320
7740
7260
7650
7930
8040
7750
8350
Рисунок 17 Разветвление подмножества 0-3
Для этого из исходной матрицы удалим нулевую строку, третий столбец,
третью строку и последовательно будем вычеркивать столбцы таблица 9.
Таблица 9
Упрощенная таблица для подмножества 0-3
41
-
1750
1130
4230
3130
1160
3050
1750
-
3770
2300
640
1900
2400
1150
3800
-
970
1460
700
1740
4290
2300
970
-
1230
1990
4350
3130
640
1460
1220
-
2550
720
1160
1810
730
2010
2500
-
1550
3100
2340
1670
4320
720
1540
-
G
1
=1440+2120+4480=8040;
G
2
=1440+970+4910=7320;
G
4
=1440+1410+4900=7750;
G
5
=1440+2250+4660=8350;
G
6
=1440+3980+4910=10330;
G
7
=1440+4100+4930=10470;
G
8
=1440+2900+4950=9290.
Удалению подлежат подмножества №6, 7, 8. Наиболее перспективным
на этом этапе становится второе подмножество первого уровня разбиения с
G
2
=7260. На одном из этапов разветвления дерево поиска оптимального реше-
ния выглядит следующим образом отображены на рисунке 18. К этому этапу
процедура удаления подмножеств применена к 43 подмножествам. Перспек-
тивными остаются 16 подмножеств.
42
Ω
1
4
7
3
2
7930
4
7
8140
8200
1
3
6
1
4
8
8310
8310
8020
8530
1
2
4
5
1
5
8280
8040
8350
8040
1
6
5
8
7
4
7750
8040
8400
8260
8160
Рисунок 18 Дерево поиска оптимального решения
Шаги 5, 6. Аналогичным способом рассмотрев еще 26 подмножеств и
удалив 68 заведомо неоптимальных вариантов, пришли к выводу о том, что по-
лученное произвольное решение 0-3-2-6-8-7-1-4-5 со значением суммарного
расстояния 8570 является оптимальным (таблица 20). Все оставшиеся решения
имеют значения целевой функции, превышающие значение 8570.
Таблица 20
Длины подмаршрутов кратчайшего маршрута
S
1
S
2
S
3
S
4
S
5
S
6
S
7
S
8
S
0
2370
1380
1440
1780
3200
2760
2110
3250
S
1
-
1750
2080
1130
4230
3130
1160
3050
S
2
1750
-
970
3770
2300
640
1900
2400
S
3
2120
970
-
1410
2250
3980
4100
2900