книги из ГПНТБ / Большие системы и управление

I l f k ( y ) q ( x ) ^

E f k( y ) q k { x ) ,

(5)

к

к

в каждом пункте:

для пунктов отправления i^(

1 , 2 , . . . ,

т)*

для пунктов назначения t - ( ] = I ,

2, . . . , л ) , для

промежуточных пунк­

тов t к ( к -

1 ,2 ,

...,/7*) и вероят­

ности потери грузов соответственно

P'L

tPj $ РК* сводится путем некоторо­

го преобразования к случаю, когда

заданы только характеристики участ­

ков транспортной сети. Это возмож­

но только тогда, когда транспорт­

ной сети можно соотнести ориенти­

рованный граф 6 ' ( w ,U). Считаем,

что время пребывания в пункте и

Рис.18. Сеть до преоб­

вероятность его

потери не зависят

разования

от количества груза.

Преобразование заключается в следующем. Для ориентирован­

ного графа

Построится эквивалентный граф G (W* и*) следую­

щим образом

[б ]. Каждому узлу иге W поставим в

соответствие

два узла иг‘и ш Л

Если дуга (иг, ц )

€ U (це WJ»

то

U *

и

(иг] urf)eU*

а

если ( q*, ьу)<ьУ, то (ц1, ш 1)е U* для каждого

В И Т

~

С р = t ( u r , q ) •

На рис. 18 изображена часть транспортной сети до преобра­

зования, а

на рис.19 -

после преобразования.

Аналогично соотносятся заданные вероятности потери груза

в исходном

и преобразованном графах. Однако заметим еще раз,

есть

последовательность

участков ui0iluiji2- • -ui

j 0> т0

вРемя

прохождения этого маршрута составит

h 0i =

ц

P = о

P

o i 0

r e ( t 0 , j 0 )

В пунктах

,

Cti

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

= -~ г

где

/^ - фронт погрузки

(количество

транспортов,

нагружаемых

Рг

. = m in . 47 -

Т 1 Р г У г Ыв) П

Р а а

(7)

K L o t < t o J

9= о

>

где рг-

вероятность непотери груза

на участке г ;

pq -

вероятность непотери груза

в пункте ср.

Количество различных

путей между фиксированными пунктами

ший"

маршрут,

В качестве одного из приближенных методов можно использо­

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

которого изображена на рис.20.

Блок I

означает начало

цикла

по числу испытаний, блок 2

содер­

жит оператор А ,((ц ^)которы й

организует

процедуру^одучайного

поиска маршрута от

пункта

I

до

пункта j .

В блоке 3 осуществля­

ется

расчет

времени следования

по маршруту

Блок 4 осущест­

вляет проверку на допустимость

м а р ш р у т а В

блоке 5

опера-

Az(Pmin ( ( Ч ) $ ) ) шб*Р а е *

маршрут, для которого вероятность

потери минимальна. Блок 6 прове­

ряет

конец цикла по испытаниям.

Данный метод позволяет

получить

оптимальный маршрут с

наперед

заданной вероятностно.

Время

счета определяется числом испы­

таний.

Если в

качестве оптимальных

путей принять кратчайшие,

то

можно воспользоваться методом

Форда [2 ].

Сущность алгоритма

нахождения кратчайшего пути за­

ключается в

следующем [7 ].

Счи­

тается заданным граф G(W, U )7

Рис.20. Укрупненная блок-

соответствующий транспортной се­

ти,

связывающей между

собой пунк­

схема машинного алгоритма

отыскания оптимального

ты отправления, назначения и про­

маршрута методом стати­

межуточные пункты. Для каждого

стических испытаний

ребра (участка сети) ие U

задана длина соответствующая сред-

нему времени пробега участка

t ц ,

Временем пребывания груза в узлах пренебрегаем. Каждому

пункту присваивается некоторый индекс

Л р ( р = I , 2 f . . . , / 77+/7t//J.

Для пункта

10 (от

которого

определяем кратчайше маршруты до

d<W o)= n

( ; - p j (о^ />«,- 1) ,

(Ю)

U^'Lo/io)

где

ри - вероятность потери груза

на

участке

и .

Определить наиболее надежный путь от пункта

i 0 до пункта

jo

- это значит найти такой

путь (lorj 0) * , для которого вели­

чина

d u ° 7* o) имела бы максимальное

значение*

Отыскание

m ax

m a x

T l { 1 - p u )

(«•o ,io)

можно заменить нахождением максимума

In П О - P J = £

l n ( 1 ~p u)

( ID

U£(Wo)

“ e(Wo)

или минимума £

- In ( 1~pa)t где

- l n ( / - p < J ^ 0

. З д е с ь

we^io)

множество различных путей

от времени

i 0

до верши­

ны

.

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

значение - I n

р и и опре­

делить между пунктами б0 и j 0 путь минимальной длины, то этот

путь

будет также наиболее надежным от

пункта

i 0 до

пункта j 0.

Если

^

Ha минимального пути,

то е х р

j

есть максимальная надежность маршрута от пункта

10до пункта j D

Таким образе»!,

если вероятность потери’ груза

на

участке

постоянна, то между каждой парой пунктов

отправления и назна­

матрицу

||

Л по следующему правилу:

1-

^0 »Jo)*.

, е с ли

Т*

6: i

е х р ( - L ( o^ oh)

Ч

г

4>><io)

i 3on

R ,

бели T *

V 3on

(L * ia) *

димых постоянных,

а также исходных данных [графа 6(W7U ),длин

участков, данных,

необходимых для вычисления P(i^) , tj доп] *

десятичную. Елок 2 -

блок начала цикла (ВЦ) по числу пунктов

отправления.

В блоке

3 оператор

А1(Пр) осуществляет запомина­

ние регистра

адреса,

величине

присваивается значение "О",

а величине

значение

R (большое число). Оператор

мена ориентации производилась, то осуществляется переход к

бло­

ку 9, в противном случае - к блоку 8.

Блок 8 осуществляет перемену направления перевозки. В бло­

ке 9 проверяется конец цикла (КЦ) по

г (по числу участков).

Оператор А3(£71})(блок II) формирует кратчайшие маршруты от

i3ad

до всех пунктов назначения. Оператор

( P(i,j)) вычисляет

ве­

роятность потери груза на маршруте (/,^) . Оператор

их протяженности и вероятности потери груза. В блоке 15

опера­

тор

А 5 ( I

•||)

вычисляет матрицы || (= - 1| , оператор

п 2(

1 М

выдает на

печать матрицу | | ^ | | .

Программа, составленная согласно описанному алгоритму для

ЦВМ М-20,

занимает 0472 ячейки (восьмеричная система счисле­

ния).

Настройка программы производится по трем параметрам:

-

номеру ячейки, с которой начинается ввод исходных дан­

ных

н

;

-

числу

пунктов на сети ( п = т + п + n f)

-

чисду

участков сети

N .

Если принять во внимание количество ячеек, которое занима­

ет программа,

стандартные

подпрограммы к поле, отведенное для

путей,

то

п

и

А/ должны удовлетворять соотношению

п + N ~ 1536.

129

(16)

i i * i l

J-iTim

В (п+

1)-й столбец матрицы

'У заносим разности:

^ '< b

“ Sij,

=

A / n + i

5 • • • ’

(17)

%mjm= A rnn<-i ■

Аналогично заполняется (m + D -я строка.

Находим

т 1 Ф ; / } = f c V - • ■ >’ т 1 п { ^ Л

(18)

- К » ’

L

1

i

т М * г £ , } =

■■ 5

т .1 п { ^ п }

(19)

1 1сФ 1*1

В строку (/77+ I)

заносятся следующие разности:

7

^ /

~ А т-ы /’ •••’ $1'/7

^ п

£t"П л—

1 ~

L.1

п

i'f,n~

3.

Отыскиваем

а)

если а; >6;,

то x-L :=6j, а вместо а;о записывается

столбец j 0 вычеркивается0^

в дальнейших расчетах не участвует;

в)

если Of <6^*о л£

g

а вместо

to ставится Ъ; - а;

строка вычеркивается;

0

с)

если

а-. =6;

,то ос-

;• :—О; = 6; э

• L0 <Г0

L0(j 0

Lo to

и столбец

in