Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 92 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

94
физическом плане величина
ji
c
,
означала ранее длину дуги ),(
j
i , то
теперь
ji
c
,
будет означать пропускную способность дуги ),(
j
i ,
определяемую наиболее узким местом этой дуги. Например, на участке
),(
j
i транспортной сети имеется мост через реку, способный в час
пропустить
ji
c
,
транспортных единиц. Это определяет максимальную
пропускную способность и всего участка ),(
j
i , исключающую
возможность образования очереди в этом наиболее узком месте.
Поскольку любой маршрут
lk,
μ
образуется последовательным
соединением дуг, то наибольшая пропускная способность маршрута
lk,
μ
,
исключающая образование очереди, будет равна пропускной способности
дуги, являющейся наиболее
узким участком маршрута:
lk
lk
jiji
ji
lklk
cc
,,
),(
,,
}{min)(
,
=
=
=
∈
μ
π
μ
π
,
где через
lk,
π
обозначена пропускная способность маршрута
lk,
μ
, как
минимальный элемент
ji
c
,
из всех дуг ),(
j
i , образующих маршрут
lk,
μ
;
)(
, lk
ji – критическая дуга маршрута.
Формальная постановка задачи построения маршрута (их множества),
обладающего максимальной пропускной способностью, в комбинаторном
виде запишется:
lk
lk
ij
ji
lk
c
,
,
max}{min
),(
,
μ
μ
π
→=
∈
, (6.1)
{
}
lklk ,,
μ
μ
∈
.
Из всего множества возможных маршрутов от вершины
k
A до
вершины
l
A требуется построить такой маршрут
0
,lk
μ
(оптимальный),
пропускная способность которого максимальна (6.1).
В основу метода построения оптимального маршрута и определения
соответствующей ему максимальной пропускной способности
)(
0
,
0
, lklk
μππ
= положено достаточно очевидное утверждение, вытекающее
из определения оптимального маршрута: если маршрут
0
,lk
μ
оптимален и
его пропускная способность равна
0
,lk
π
, то не существует маршрута из
пункта
k
A в пункт
l
A, имеющего бóльшую пропускную способность
)(
0
,, lklk
ππ
> .

Страницы