close

Вход

Забыли?

вход по аккаунту

?

Моделирование и анализ потоковых задач с неоднородными носителями.

код для вставкиСкачать
УДК
517.518.2
В. В. СКАЛОЗУБ, Л. А. ПАНИК (ДИИТ)
МОДЕЛИРОВАНИЕ И АНАЛИЗ ПОТОКОВЬІХ ЗАДАЧ
С НЕОДНОРОДНЬІМИ НОСИТЕЛЯМИ
В представленной статье вьmолнен анализ потоков, когда единицЬІ потока имеют индивидуальНЬІе свой­
ства (неоднородности) .
У представленій статті виконаний аналіз потоків, коли одиниці потоку мають індивідуальні властивості
(неоднорідності).
The analysis of streams is executed when units of stream have individual characteristics (heterogeneity) in the
represented article.
Введение
найти максимально допустимую величину
При изучеmm характеристик транспортньІХ и
других сетей возникает необходимость в вьrчис­
леmm оrrrимального значения функции потока,
протекающего от источника
к стоку
s
t.
тах V
V,
L fif - Lfj;
такие расчеть1 проводятся в задачах, связанньІХ с
однопродуктовьrм потоком. Здесь потоки в дугах
сети
соответствуют
передаче
некоторого
бьпь сформулировань~ различнь1е задачи
кратчайшем
пути,
о
максимальном
1
одно­
мации, денежной массь1 и т. п. На сетях могуr
(о
[ 1]
(2)
при условии, что
Часто
родного продукта: злектрознергии, водь1, инфор­
V,
на основе следующего:
1
В уравнениях
=
{
i=s,
О,
i:;:.s,i=F-t,
- V, і= t.
(1)-(3)
(3)
суммирование произ­
водится по всем узлам, для которьІХ функция
f if
определена.
разрезе,
МаксимальньІЙ поток характеризует пропуск­
транспор111ая задача, и т.д.), характеризующие
ную способность сети в целом для стационарного
различнь1е аспекть1 их работь1.
режима. При зтом в классической модели
[1] от­
дельнь1е носиrели единиц потока не рассматри­
Материал и результать1 исследования
ваІОТся. Следовательно, не рассматриваются и
Рассмотрим модель задачи о максимальном
G = (N, А) -
потоке в сети. Пусть
ванная сеть, где
множество дуг, а
дуги
(i,j).
N U if -
множество узлов,
лочисленная
множестве А
t -
s
-
является ис­
стоком. Согласно
функция
,
А
пропускная способность
Считаем, что узел
точником, а узел
ориентиро-
fif ,
[1],
це­
определенная
на
назЬІвается потоком в сети
G,
(1)
j el\1
-
,
а.; - множе­
дугами, направ­
ленньІМИ в противоположную сторону. Значение
=V
назьmается величиной потока.
j
j
В задаче о максимальном потоке требуется
134
индивидуальНЬІХ
свойств.
В
[2,
З]
сформулировань1 новЬІе задачи исследования по­
токов для случаев, когда вводиrся в модель д:иф­
ференциация носиrелей потока.
В представленной статье, продолжая
[2,
З],
ка имеют индивидуальнь1е свойства. Такими их
ограничения
на
возможность
со­
вместного движения по дугам, задание опреде­
ленной последовательности движения носите­
альнь1е
узлом і дугами, напр~еШІЬІМИ к і
І fsj = І fj,
ких-ШІбо
лей, право собственности, то есть индивиду­
множество всех узлов, связанньІХ с
ство всех узлов, Свя:занньІХ с і
Такое
свойствами (неоднородностями носителей по­
fif '?:Uif '<:f(i,j)eA.
J3; -
t.
однородности носиrелей, отсутствии у них ка­
маршрутам,
L fif -LfJi=OV'ieN, i:;:.s,i:;:.t,
(1)
к
тока) могуr бьпь: перемещение по извесТНЬІм
fif '?: OV(i,j) є А,
В
s
представление соответствует предположению об
вьшолнен анализ потоков, когда единиЦЬІ пото­
если она удовлетворяет ограничениям:
jea 1
траектории носителей потока от
оценки
качества и
цели
перемещеНЮІ
носителей, и др.
С учетом индивидуальнЬІХ свойств единиц
потока будем рассматривать три задачи :
1.
Для известного потока на входе сети (из·
вестно общее число единиц потока поступаю­
щее в сеть за некоторь1й период). Для макси­
мального потока необходимо определить мно­
жество возможньІХ траектории , по которь1м мо-
дуги (і, і) на которь1х вьшолняется неравенство
rут передвигаться отдельнь1е единиць1 потока.
2.
Для обьектов с заданнь1м набором инди­
видуальньІХ
свойств
необходимо
т
It: >Иіj.
определить
максимальнь1й поток в сети.
(7)
k=l
З. На множестве оптимальньІХ траекторий
Для решение задачи
требуется также
рассчитать компромиссНЬІе варианть1 движения
единиц потока с учетом вь1бранной системь1
единиц потока по сети, общее число которьІХ
оценок.
известно (максимально). Если ограничение
Рассмотрим первую из задач. Пусть t; - ко­
личество единиц потока . с
і-м индивидуаль­
ньrм свойством, где і= 1,т. Тогда задача о тра­
екториях максимального потока имеет вид:
(4)
Здесь
V -
о,
единиц
Зная для некоторой дуги, число единиц по­
нЬІе маршруть1 для каждой единицЬІ потока на
матричного
[2,
с.
метода
представленного
в
62].
поток
в
сети,
в
зависимости
от
пропускнь1х
ItJ 5, иіj, здесь 1; 5, 1*,
пропускная способность дуги
альнь1м свойством по дуге
(i,j), k
= 1,т.
чениях,
обусловленньІХ
величинь1
индивидуальНЬІми
максимального
потока от ограниче­
ний, накладь1ваемьІХ набором индивидуальнь~х
свойств на следующих примерах. Рассмотрим
задачу о максимальном
потоке в сети с одно­
родньrми носителями (рис.
1),
и с индивидуаль­
нь1ми свойствами носителей потока (рис.
(6)
2).
Примем, что индивидуальНЬІМ свойством явля­
ется требование, согласно которому только
(i,j)
сети, fiJ* - величина потока с k-м индивиду­
(4)-(5)
меньше
(4).
величина потока. Отличие задачи
k=l
ча
проходит
свойствами носителей. Исследуем зависимость
т
UiJ -
сеть
способностей дуг при дополнительньІХ ограни­
если вьшолняется соотношение:
где
через
потока, чем согласно
s,i * t,k = 1,т (5)
-V,
i=t.
і*
от задачи
о 5,
(7)
Во второй задаче на.до найти максимальнь1й
i=s,
(1)-(3) заключается в наличии
двойной суммьr ( внуrренняя сумма берется по
величинам потока с
k -м индивидуальньrм
свойством). Задача (4)-(5) будет иметь решение,
(4)-(5)
времени
основе
при условии, что:
{
перемещения
будет вЬІполняться, то за некоторьrй период
работе
т
т
~t;1: - ~~Jj~ =
траектории
тока протекающего по ней, вьщеляем возмож­
і=І
V,
возможнЬІе
(4)-(5)
указать
Зада­
1~2~5~8~10.
Для задачи (рис .
максимальнь1й поток,
1)
рассчитаннь1й согласно
чи рис .
не имеет решения
1
носитель должен перемещаться по траектории
равен
[ 1],
8,
а для зада­
2 он равен 5.
)-~:..:.:.---=~~1~0,....___
Mмc.ммani.Jotwt\
пот<Ж" 8
Рис.
1.
МаксимальНЬІЙ поток без индивидуальнь1х свойств носителей
t--~~~~~-.;;j~ ІОІо----...;~
Максимаnьнь1У.
.rtоток
Рис.
2. МаксимальньІЙ
=s
поток с индивидуальнь1ми свойствами носителей
Найдем все траектории носителей потока,
1 сети, от источника (вершина
(вершина 10) по [2]. Присвоим зтим
траекториям числовЬІе значения, которь1е , для
заданной на рис.
определенности
І) к стоку
одной единиць1 потока (в усл. ед.) . Получим:
считаем
ценами
за
перевозку
135
1) 1424548410 цена за перевозку 7;
2) 1 4 2 4 5 41 О цена за перевозку 6;
З) 14 2 4 7 410 цена за перевозку 8;
4) 14 4 4 7 41 О цена за перевозку 5;
5) 14 44 6 4 7 410 ценазаперевозку9;
6) 1 4 4 4 6 4 9 4 1О цена за перевозку 4;
7) 14 З 4 6 4 9 410 цена за перевозку З ;
8) 14 З 4 6 4 7 4 1О цена за перевозку 1.
5) 1 4 4 4 6 4 7 41 О -
7)
8)
следующее
т2 =З
,
т3
количество
единиц
14З4647410
Тогда согласно
чика:
4
(8),
F; 1 =-;для
10
проследует
-
Найдем максиминную
=2.
имеем: для 1-го перевоз-
. ( 4
7 з)
1
Рассмотрим распределение единиц потока
s2
F(s)=maxmin(f;(s)- /;- ).
s
по траекториям той же сети:
(8)
/;+ - f;-
іє(І ,З]
2) 1 4 2 4 5 41 О -
распределение единиц потока в сети на
f; (s) -
доход
і - ого
м распределении,
перевозчика
/;+, f;- -
при
ВеЛИЧИНЬІ
f;+' f;-
щим образом. Значение
ВЬІЧИСЛЯЮТСЯ следую­
f./
З)
= 22 усл. единиц (2
по пути
14 2 4 7 4 1О , а одна единица потока
пути 1 4 2 4 5 4 1О); / 2+ = f..+- так как у
ниц потока, что и у первого; fз+
= 16 усл. еди­
1 4 2 4 7 41 О). Значение
f..- = 12 усл. единиц ( 1 единица потока просле­
дует по пути 1444649410 , вторая по
пути 1 4 З 4 6 4 9 41 О, а третья по пути
1 4 4 4 7 41 О); J;- = f..- ; fз- = 7 усл. единиц
(1 единица потока проследует по пути
1444649410 ,
вторая
по
пути
14 з 4 6 4 9 41 о).
Рассмотрим распределение единиц потока s1
по траекториям сети представленной на рис. 1:
1) 1 4 2 4 5 4 8 41 О - проследует О ед.
по
пути
2
единиць1
2) 14 2 4 5 4 lQ 14 2 4 7 41 О -
проследует
2
единиць1
проследует
2
единицЬІ
2
единиць1
потока 2-ого перевозчика;
4) 14 4 4 7 41 О -
проследует
1
1
единица
единица потока
проследует О еди­
5) 14 44 6 4 7 410 ниц потока;
6) 14 4 4 6 4 9 4 1О -
проследует
еди­
ница потока 1-ого перевозчика;
7) 1 ~ З ~ 6 ~ 9 4 1О -
проследует
1
еди­
ница потока 1-ого перевозчика;
8) 14 З 4 6 4 7 ~ 1О -
проследует О еди­
ниц потока .
Тогда согласно
F21 = О ;
(8):
для 1-ого перевозчика:
для 2-го перевозчика:
З-го
9
F22 = їQ ;
F2 (s2 ) =
для
5
перевозчика:
F23 =- ;
9
min(o.~.~) =0. .
10 9
АналоrичньІМ образом,
продолжим: перебор
друmх вариантов распределений
по траекториям
cem.
s;
единиц потока
Каждьrй из вариантов рас­
пределений формируется с помощью перестано­
вок единиц потока, участвующих в получеюm оп­
зтого получим окончательную оценку:
потока 1-ого перевозчика;
проследует
потока З-го перевозчика;
136
проследует
тимального (максимального) потока. Исходя из
потока;
З)
единиць1
2-го перевозчика;
единиць1 потока зтого перевозчика про­
следуют
14 2 4 7 410 -
4) 1 4 4 4 7 4 1О -
второго перевозчика такое же количество еди­
(2
2
потока 1-го перевозчика и
единиць1 потока зтого перевозчика проследуют
ниц
проследует
потока 2-ого перевозчика;
наибольший и
наименьший доход і - ого перевозчика.
по
проследует О еди­
ниц потока ;
потока З-го перевозчика;
рис.1,
s-
7
F; 2 =- ;
10
перевозчика:
1) 14 2 4 5 4 8 4 1О -
s-
еди­
F;Csi)=mш 10 '10'9 =з"
носителей в виде [З] (принцип га­
рантированного результата):
где
1
проследует О еди­
-
2-го перевозчика:
З-ого
для
потока:
оценку зффективности потока с собственнь1ми
свойствами
14З4649410
право собственности. Далее,
-
пусть есть три собственника, которь1м принад­
,
еди­
ниц потока.
екторий носителей, введем еще одно индивиду­
т 1 =З
1
ница потока 2-го перевозчика;
чи компромиссного вЬІбора на множествах тра­
лежит
проследует
6) 1444649410 -
ница потока 1-го перевозчика;
Для формулирования содержательной зада-
альное свойство
проследует О еди­
ниц потока;
F(s•) = max(F; (s1 ),F2 (s 2 ) " ••)
где
s· -
вида:
=.!.,
з
распределение единиц потока такого
проследует О еди­
1) 1424548410 ниц потока;
2) 1 4 2 4 5 4 1О -
проследует
единиць1
2
потока 1-го перевозчика;
З)
проследует О единиц
2) 14245410
потока;
проследует
14 2 4 7 410 -
единиць1
2
потока 2-го перевозчика;
4) 14 4 4 7 41 О -
проследует О единиц
3) 14247410
потока;
4) 1 4 4 4 7 41 О -
проследует
2
единиць1
потока 1-го перевозчика;
проследует
5) 14 4 4 6 4 7 41 О -
единиць1
2
потока 3-зго перевозчика;
проследует О еди­
ниц потока;
5) 1 4 4 4 6 4 7 4 1О -
проследует О еди­
проследует
6) 14 4 4 6 4 9 410 -
еди-
ница потока З-го перевозчика;
ниц потока;
проследует
6) 1444649410 -
1
еди­
проследует
7) 1434649410 -
1
еди­
ница потока 2-го перевозчика;
8) 14 З 4 6 4 7 4 1О -
8) 1 4 3 4 6 4 7 41 О -
проследует О еди­
еди­
проследует О еди­
Анализ примера показь1вает, что компро­
миссно-оптимальнь1е
Рассмотрим сеть на рис. 2, у которой мак­
5.
1
ниц потока.
ниц потока.
симальнь1й поток равен
проследует
7) 1434649410 -
ница потока 2-го перевозчика;
ница потока 1-го перевозчика;
Так как количество
максимальнь1е
оценки
потоков из носителей, имеющих индивидуаль­
нЬІе свойства, зависят от некоторь1х дополни­
единиц носителей у перевозчиков потока оста-
тельньІХ условий
лось то же
ками перевозок. В частности, здесь такое со­
можнь~х
(8), F(s·) будет зависеть от всевоз­
сочетаний
единиц
потока
на
опти­
.
мальнь1х траекториях Сі При зтом, если рас­
сматривать лишь 5 носителей, могут бьпь най­
лучают
Естественно,
остальнь1е
механизма распределения прибьши с учетом
8)
=З,
которь1е
носителями. Например, если возьт2
= 1,
т3
= 1 , то F (s •) = -2 ,
5
где s
•
1) 1424548410 -
проследует
1
еди­
ница потока 1-ого перевозчика;
2) 1 4 2 4 5 4 1О
проследует О единиц
потока;
14247410
интересов всех участников (перевозчиков) мо­
жет бьпь модели игр с побочньІМи платежами
[4].
ную суммарную прибьmь. Полученнь1й доход
распределяется
проследует
1
1
единица
единица потока
З-го перевозчика;
5) 14 4 4 6 4 7 4 1О -
проследует О еди­
ниц потока;
6) 1444649410 -
проследует
1
еди­
1
еди­
ница потока 1-ого перевозчика;
7) 1434649410 -
проследует
8) 14 3 4 6 4 7 41 О -
проследует О еди­
сителей по траекториям, которЬІе уменьшают
=2,
т2
=2,
Например, если мь1 возьмем
т3
=1,
то
F(s
•
1
4
)=-,где
•
s -
проследует
ница потока 2-го перевозчика;
1
за­
свойств
носителей
сущест­
венно не только значение потока, но и траекто­
рии описьmаемь1е единицами потока. С учетом
характеристик злементов потока на различнь~х
траекториях,
вьщелен
класс
новь~х
компро­
мисснь~х задач о потоках в сетях.
БІБЛІОГРАФІЧНИЙ СПИСОК
l.
Филлипс
Д.
И.
МетодЬІ
анализа
Д. И. Филлипс, А. Гарсиа-Диас.
1984. -
с.
-
сетей
І
М.: Мир,
496.
2.
Нечипуренко В . И. СтруктурнЬІй анализ систем.
З.
Гермеер Ю. Б" Введение в теорию исследова­
4.
Бутрим Б. И. ИrрЬІ
- М.:
«Советское радио».
ния операций.
- М. :
1977. -С. 212.
Наука.
N
1976. -
С.
352.
лиц с существенНЬІм мно­
жеством критериев. Журнал «Вь1числительная
распределение единиц потока такого вида:
1) 1424548410 -
участниками
Показано, что в потоковьrх задачах с учетом
индивидуальнь~х
ниц потока.
Вместе с тем могут бьпь распределения но­
всеми
Вь1водь1
ница потока 1-го перевозчика;
F(s).
между
ранее установленнь1м способом .
проследует О единиц
потока 2-го перевозчика и
значение
которь1е обеспечивают максималь­
после реализации решения (вне рамок модели)
потока;
4) 1 4 4 4 7 41 О -
Согласно нее в перевозках участвуют те
злементь1,
распределение носителей потока вида:
т1
«прибьmю>.
участники доЛЖНЬІ им компенсировать зто, пе­
редав определенную часть прибьши. В качестве
мем т 1
З)
глашение состоит в том, что некоторЬІе злемен­
ть1 не участвуют в перевозках. А значит, не по­
увеличивают
распределения,
(по всем
-
соглашений между участни­
по сравнению с задачей с однороднь1ми
день1
F(s),
-
еди­
математика и матфизика». №
2. 1980.
Поступила в редакцию О 1.11.2007.
137
Документ
Категория
Без категории
Просмотров
5
Размер файла
154 Кб
Теги
анализа, моделирование, неоднородным, потоковых, носителях, задачи
1/--страниц
Пожаловаться на содержимое документа