Лубенцова В.С. Математические модели и методы в логистике

Подождите немного. Документ загружается.

110

Если суммарный запас груза совпадает с суммарным спросом, то

есть

∑∑

, (6.12)

то задачу называют закрытой, в противном случае – открытой.

Составим математическую модель задачи. Обозначим через

количество груза, планируемое к перевозке из i-го пункта поставки в

j-ый пункт потребления. Через t – время наиболее продолжительной

перевозки. Оптимальным будет план

(

)

1112

,,...,

xxx

, самая продол-

жительная перевозка которого минимизируется. Модель закрытой

задачи имеет вид

min max

, (6.13)

{

, (6.14)

iji

∑

= , (6.15)

ijj

∑

= , (6.16)

≥

. (6.17)

Как видно, целевая функция является нелинейной. Обратные пе-

ревозки не предполагаются.

Решаем задачу сведением ее к задаче о максимальном потоке.

Для этого строится сеть с m+n+2 вершинами, из которых m вер-

шин соответствуют поставщикам A

, а n – потребителям B

, две ос-

тавшиеся соответствуют истоку I и стоку S.

Пропускные способности ребер полагают равными:

IAi

BSj

ijji

ABBA

==∞

. (6.18)

У ребер

(

)

проставляют времена

доставки груза. Время

доставки по ребрам

(

)

(

)

считаются равными нулю:

IABS

. Граф транспортной сети приведен на рис. 6.7.

111

После построения сети отыскивается поток заданной мощности:

max

fab

∑∑

, (6.19)

при котором

max

достигает минимальной величины. В процессе

этого поиска при наличии альтернативы исключаются из рассмотре-

ния маршруты с более продолжительными поставками. Решение за-

канчивается, когда замена более продолжительных маршрутов менее

продолжительными невозможна.

Другими приложениями задачи о максимальном потоке являют-

ся:

– задача определения максимальной пропускной способности

трубопровода для транспортировки груза угольной пульпы от уголь-

ных шахт к электростанциям;

– определение максимальной пропускной способности (макси-

мального потока) сети трубопроводов для транспортировки сырой

нефти от буровых скважин до нефтеперегонных заводов и целый ряд

других задач.

ЛЕКЦИЯ 13

6.8. Задача нахождения кратчайшего пути

Задача состоит в нахождении связанных между собой дорог на

транспортной сети, которые в совокупности имеют минимальную

длину от исходного пункта до пункта назначения.

Введем обозначения:

– расстояние на сети между смежными

∑

,0)

Р и с. 6.7. Граф транспортной сети

112

узлами

;

– кратчайшее расстояние между узлами

;

Формула для вычисления

( )

кратчайшее растояние

до предыдущего узла

minmin

плюс расстояние между

узлом и предыдущим узлом

jiij

Uud





==+







Из этой формулы следует, что кратчайшее расстояние

до уз-

ла

можно вычислить лишь после того, как определено кратчайшее

расстояние до каждого предыдущего узла, соединенного дугой с уз-

лом

. Процедура завершается, когда получено

последнего звена.

Пример. Рассмотрим граф, представленный на рис. 6.8.

Определить кратчайшее расстояние между узлами 1 и 7.

Решение. Найдем минимальные расстояния:

3112

022

uud

=+=+=

3113

044

uud

=+=+=

{

}

{

}

4114224334

min;;min010;211;437

uududud

=+++=+++=

{

}

{

}

5225445

min;min25;787

uudud

=++=++=

{

}

{

}

6336446

min;min41;775

uudud

=++=++=

{

}

{

}

7556667

min;min76;5913

uudud

=++=++=

Минимальное расстояние между узлами 1 и 7 равно 13, а соот-

2 5

3 6

Р и с. 6.8

113

ветствующий маршрут содержит узлы 1–2–5–7.

К такой задаче сводится целый ряд задач, таких как:

– задача о замене оборудования;

– построение критического пути в сетевых графиках;

– построение сетей максимальной надежности;

– рациональное размещение пунктов обслуживания и т.д.

Существует ряд алгоритмов нахождения кратчайшего пути. Из

них самыми известными являются:

– алгоритм Дейкстры;

– алгоритм Флойда;

– алгоритм Форда-Фалкерсона.

Алгоритм Дейкстры разработан для нахождения кратчайшего

пути между заданным исходным узлом и любым другим узлом сети.

Алгоритм Флойда более общий, поскольку он позволяет одно-

временно найти минимальные пути между любыми двумя узлами

сети.

6.9. Решение задачи методом Форда-Фалкерсона

Остановимся подробнее на алгоритме Форда-Фалкерсона.

Алгоритм может быть использован для нахождения кратчайших

путей на графах, если вести поиск от некоторой вершины до всех

остальных вершин. Алгоритм относится к числу итерационных.

При расчете графов на ЭВМ информацию о графе удобно хра-

нить в матричном виде. Граф обычно задается с указанием длин дуг,

поэтому записывается матрица весов дуг. Такая матрица квадратная

с числом строк (столбцов), равным числу вершин графа. На пересе-

чении i-ой строки и j-го столбца в ней ставится:

– 0, если

(либо это отсутствующая петля, либо длина дуги

равна 0);

–

, если имеется связь

(

)

uij

из вершины

в вершину

, где

– длина дуги из

;

–

∞

, если нет связи из

При практической реализации на ЭВМ вместо

∞

можно исполь-

зовать достаточно большое число.

В качестве примера рассмотрим граф, изображенный на рис. 6.9.

114

Здесь матрица смежности вершин имеет вид

01100

00100

00010

00001

01100







матрица весов дуг –

[ ]

min

054710

0147

8036

5503

2360





∞



∞



∞



∞



а матрица кратчайших путей –

[ ]

min

054

250

∞∞





∞∞∞



∞∞∞



∞∞∞



∞∞



6.10. Нахождение общей медианы графа

Обозначим через

– числовую характеристику – вес вершин

графа.

Р и с. 6.9

115

Пусть граф является, например, моделью процесса транспорти-

ровки деталей между станками механического участка. Тогда под

весами вершин можно понимать производительность станка (число

обработанных деталей в ед. времени) или пропускную способность

железнодорожного узла.

Внешним передаточным числом

вершины с номером 1 графа

называется результат выражения:

(

)

(

)

(

)

1min1min2min

1,11,2...1,

WCqCqCkq

=+++ , (6.20)

где

– число вершин графа,

(

)

min

– элементы 1-ой строки мат-

рицы кратчайших путей

[

]

min

C .

Если внешние передаточные числа всех вершин графа записать в

виде вектор-столбца

[

]

, а веса вершин в виде вектор-столбца

[

]

то

[

]

[

]

[

]

min

WCq

=⋅

. (6.21)

Внешней медианой графа будем называть вершину графа, для

которой внешнее передаточное число минимально.

Внутренним передаточным числом

вершины с номером 1 гра-

фа называется результат выражения:

(

)

(

)

(

)

1min1min2min

1,12,1...,1

tCqCqCkq

=+++ . (6.22)

Если внутренние передаточные числа всех вершин графа запи-

саны в виде вектор-столбца

[

]

, то можно записать:

[

]

[

]

[

]

min

tCq

=⋅

, (6.23)

где

[

]

min

C – транспонированная матрица

[

]

min

C .

Внутренней медианой графа называется вершина, для которой

внутреннее передаточное число минимально.

Если сложить два вектора

[

]

[

]

, получим новый вектор:

[

]

[

]

[

]

fWt

. (6.24)

Минимальный элемент вектора

[

]

указывает своим индексом

на номер вершины, которую называют общей медианой графа

Таким образом, общая медиана графа характеризуется мини-

мальной суммой внутреннего и внешнего передаточных чисел.

Пример. В цехе имеются 5 участков, объединенных в сеть по-

средством транспортных связей. Каждый участок производит неко-

116

торую продукцию и нуждается в обслуживании (настройке) инстру-

ментом. Инструмент доставляется на участок настройки немедленно

после обнаружения погрешности. Сведения об относительной произ-

водительности участков

[

]

и расстояниях между ними даны на гра-

фе (рис. 6.10). Где следует выбрать место для участка настройки,

чтобы временные затраты на транспортировку были минимальными?

Требуется выбрать из 5 участков один, для которого транспор-

тировка от него и обратно наиболее выгодна. Относительная потреб-

ность в настройке будет считаться пропорциональной производи-

тельности.

Матрица весов дуг графа – модели механического цеха, имеет

вид:

[ ]

0310

305

100615

5604

∞∞





∞∞



∞



∞



∞∞∞



Матрица кратчайших путей –

[ ]

0310812

301159

10110610

85604

1291040







;

матрица весов вершин –

Р и с. 6.10

117

[]







;

матрица внешних передаточных чисел –

[ ] [ ][]

min

910403695

611252769

20333030113

161561249

2427102081

WCq

+++





+++



=⋅==

+++



+++



+++



;

матрица внутренних передаточных чисел –

[]

0310812295

301159369

101106101113

85604549

1291040384





=⋅=





Тогда вектор-столбец

задается в виде:

[ ] []

190

138

226

162

fwt





=+=





Минимальный элемент вектора

равен 98, поэтому необходимым

свойством будет обладать участок 4 (рис. 6.10), которому в модели

на графе соответствует общая медиана.

6.11. Расчет надежности сетей

При решении этой задачи на графе каждой дуге ставится в соот-

ветствие надежность перемещения груза по дуге сети (т.е. вероят-

ность безотказной работы).

Рассмотрим пример. Исследуется система перемещения груза по

118

городским улицам. Служба движения располагает статистическими

данными о вероятности безаварийного проезда автотранспорта по

той или иной улице в том или ином направлении.

Задача моделируется графом (рис. 6.11), вершины которого –

перекрестки (или характерные объекты, с помощью которых можно

описать путь перемещения грузов).

Веса дуг – вероятности безаварийного проезда.

Требуется определить вероятности безаварийного проезда по

тому или иному пути, т.е.вероятность безопасного перемещения по

пути (см. рис. 6.11), которая определяется произведением вероятно-

стей

123

PPPP

=⋅⋅

. (6.25)

Учитывая, что нас интересует максимально безопасный путь,

потребуем, чтобы

max

Прологарифмируем выражение (6.25):

(

)

(

)

(

)

(

)

123

lnlnlnln

PPPP

=++. (6.26)

С учетом того, что вероятности безопасного проезда находятся в

интервале от 0 до 1,

(

)

ln0

Путь с вероятностью безопасного проезда близкой к 1 имеет от-

рицательный, близкий к 0, логарифм.

Наоборот, если путь отличается малой вероятностью безаварий-

ного проезда, логарифм его отрицателен и близок к бесконечности.

Если же все значения логарифмов вероятностей безаварийного про-

езда умножить на (–1), тогда путь с малой вероятностью безаварий-

ного проезда будет иметь очень большую положительную величину

(на графе –

∞

), а путь с высокой вероятностью безаварийности бу-

дет характеризоваться малой положительной величиной.

Следовательно, для поиска пути с максимальной безаварийно-

стью можно применить алгоритм поиска кратчайшего пути на задан-

ном графе.

Дуги такого графа будут характеризоваться логарифмами веро-

ятностей безотказного проезда, умноженными на (–1).

Проиллюстрируем вышеизложенное.

Р и с. 6.11

119

Пример. Исследуется система перемещения груза по городским

улицам. Имеются статистические данные о вероятности безаварий-

ного проезда автотранспорта по той или иной улице в том или ином

направлении.

Задача моделируется графом (рис. 6.12), вершины которого –

перекрестки или характерные объекты, с помощью которых можно

описать пути перемещения грузов. Веса дуг – вероятности безава-

рийного проезда.

Требуется определить вероятности безаварийного проезда по

тому или иному пути.

Решение.

Составим матрицу

[

]

[ ]

10,40,80,70

010,300,5

00100,9

00010,5

00001







Проведем нижеследующие вычисления:

0,4

0,5

0,8

0,7

0,5

0,9

Р и с. 6.12