Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості
Моделювання потоків мінімальної вартості — це, фактично, дослідження на моделях будь-якого типу чи принципу дії усіх комунікацій, природних або штучних, якими передаються чи мають передаватися мережеві потоки таким чином, аби сукупні витрати на їхні рух енергії, коштів чи ресурсів були як найменшими...
Saved in:
| Published in: | Реєстрація, зберігання і обробка даних |
|---|---|
| Date: | 2018 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут проблем реєстрації інформації НАН України
2018
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/168771 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості / Є.О. Додонов, О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2018. — Т. 20, № 3. — С. 121–130. — Бібліогр.: 8 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-168771 |
|---|---|
| record_format |
dspace |
| spelling |
Додонов, Є.О. Додонов, О.Г. Кузьмичов, А.І. 2020-05-08T19:29:26Z 2020-05-08T19:29:26Z 2018 Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості / Є.О. Додонов, О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2018. — Т. 20, № 3. — С. 121–130. — Бібліогр.: 8 назв. — укр. 1560-9189 DOI: https://doi.org/10.35681/1560-9189.2018.20.3.158489 https://nasplib.isofts.kiev.ua/handle/123456789/168771 004.942.519.67 Моделювання потоків мінімальної вартості — це, фактично, дослідження на моделях будь-якого типу чи принципу дії усіх комунікацій, природних або штучних, якими передаються чи мають передаватися мережеві потоки таким чином, аби сукупні витрати на їхні рух енергії, коштів чи ресурсів були як найменшими. Саме тому ядром математичного і обчислювального апарату мережевої оптимізації є модель фундаментальної задачі про потоки мінімальної вартості (Minimum Cost Flow, MCF) у різноманітних її версіях, постановках і застосуваннях. Зазвичай реалізація цих моделей вимагає серйозних зусиль і витрат, що пов’язані із застосуванням спеціальних програмних і мовних засобів. Наведено приклади розв’язання узагальнених задач MSF за доступною технологією електронно-табличного оптимізаційного моделювання. Моделирование потоков минимальной стоимости — это, фактически, исследования на моделях любого типа или принципа действия всех коммуникаций, естественных или искусственных, которыми передаются или должны передаваться сетевые потоки таким образом, чтобы совокупные затраты на их передвижение энергии, средств или ресурсов, были наименьшими. Именно поэтому ядром математического и вычислительного аппарата сетевой оптимизации является модель фундаментальной задачи о потоках минимальной стоимости (Minimum Cost Flow, MCF)) в различных ее версиях, постановках и приложениях. Обычно реализация этих моделей требует серьезных усилий и затрат, связанных с применением специальных программных и языковых средств. Приведены примеры решения обобщенных задач MSF по доступной технологии электронно-таблич-ного оптимизационного моделирования. Modeling the minimal cost flows is, really, the research on the models of any type or principle of operation of all communications, natural or artificial, by which network flows are transmitted or must be transmitted in such a way that the total costs for the movement of energy, funds or resources, were the least. So the core of the mathematical and computing instruments of network optimization is the model of the fundamental problem of minimum cost flow (MCF) in its various versions, statements and applications. Usually the implementation of these models requires serious efforts and costs associated with the use of special software and language tools. Some examples of solving generalized MSF problems on accessible technology of spreadsheet op-timization modeling are given. uk Інститут проблем реєстрації інформації НАН України Реєстрація, зберігання і обробка даних Реєстрація, зберігання і обробка даних Експертні системи та підтримка прийняття рішень Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості Моделирование и визуализация обобщенных задач о потоках минимальной стоимости Modeling and visualization of generalized minimum cost flows problems Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості |
| spellingShingle |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості Додонов, Є.О. Додонов, О.Г. Кузьмичов, А.І. Експертні системи та підтримка прийняття рішень |
| title_short |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості |
| title_full |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості |
| title_fullStr |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості |
| title_full_unstemmed |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості |
| title_sort |
моделювання та візуалізація узагальнених задач про потоки мінімальної вартості |
| author |
Додонов, Є.О. Додонов, О.Г. Кузьмичов, А.І. |
| author_facet |
Додонов, Є.О. Додонов, О.Г. Кузьмичов, А.І. |
| topic |
Експертні системи та підтримка прийняття рішень |
| topic_facet |
Експертні системи та підтримка прийняття рішень |
| publishDate |
2018 |
| language |
Ukrainian |
| container_title |
Реєстрація, зберігання і обробка даних |
| publisher |
Інститут проблем реєстрації інформації НАН України |
| format |
Article |
| title_alt |
Моделирование и визуализация обобщенных задач о потоках минимальной стоимости Modeling and visualization of generalized minimum cost flows problems |
| description |
Моделювання потоків мінімальної вартості — це, фактично, дослідження на моделях будь-якого типу чи принципу дії усіх комунікацій, природних або штучних, якими передаються чи мають передаватися мережеві потоки таким чином, аби сукупні витрати на їхні рух енергії, коштів чи ресурсів були як найменшими. Саме тому ядром математичного і обчислювального апарату мережевої оптимізації є модель фундаментальної задачі про потоки мінімальної вартості (Minimum Cost Flow, MCF) у різноманітних її версіях, постановках і застосуваннях. Зазвичай реалізація цих моделей вимагає серйозних зусиль і витрат, що пов’язані із застосуванням спеціальних програмних і мовних засобів. Наведено приклади розв’язання узагальнених задач MSF за доступною технологією електронно-табличного оптимізаційного моделювання.
Моделирование потоков минимальной стоимости — это, фактически, исследования на моделях любого типа или принципа действия всех коммуникаций, естественных или искусственных, которыми передаются или должны передаваться сетевые потоки таким образом, чтобы совокупные затраты на их передвижение энергии, средств или ресурсов, были наименьшими. Именно поэтому ядром математического и вычислительного аппарата сетевой оптимизации является модель фундаментальной задачи о потоках минимальной стоимости (Minimum Cost Flow, MCF)) в различных ее версиях, постановках и приложениях. Обычно реализация этих моделей требует серьезных усилий и затрат, связанных с применением специальных программных и языковых средств. Приведены примеры решения обобщенных задач MSF по доступной технологии электронно-таблич-ного оптимизационного моделирования.
Modeling the minimal cost flows is, really, the research on the models of any type or principle of operation of all communications, natural or artificial, by which network flows are transmitted or must be transmitted in such a way that the total costs for the movement of energy, funds or resources, were the least. So the core of the mathematical and computing instruments of network optimization is the model of the fundamental problem of minimum cost flow (MCF) in its various versions, statements and applications. Usually the implementation of these models requires serious efforts and costs associated with the use of special software and language tools. Some examples of solving generalized MSF problems on accessible technology of spreadsheet op-timization modeling are given.
|
| issn |
1560-9189 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/168771 |
| citation_txt |
Моделювання та візуалізація узагальнених задач про потоки мінімальної вартості / Є.О. Додонов, О.Г. Додонов, А.І. Кузьмичов // Реєстрація, зберігання і обробка даних. — 2018. — Т. 20, № 3. — С. 121–130. — Бібліогр.: 8 назв. — укр. |
| work_keys_str_mv |
AT dodonovêo modelûvannâtavízualízacíâuzagalʹnenihzadačpropotokimínímalʹnoívartostí AT dodonovog modelûvannâtavízualízacíâuzagalʹnenihzadačpropotokimínímalʹnoívartostí AT kuzʹmičovaí modelûvannâtavízualízacíâuzagalʹnenihzadačpropotokimínímalʹnoívartostí AT dodonovêo modelirovanieivizualizaciâobobŝennyhzadačopotokahminimalʹnoistoimosti AT dodonovog modelirovanieivizualizaciâobobŝennyhzadačopotokahminimalʹnoistoimosti AT kuzʹmičovaí modelirovanieivizualizaciâobobŝennyhzadačopotokahminimalʹnoistoimosti AT dodonovêo modelingandvisualizationofgeneralizedminimumcostflowsproblems AT dodonovog modelingandvisualizationofgeneralizedminimumcostflowsproblems AT kuzʹmičovaí modelingandvisualizationofgeneralizedminimumcostflowsproblems |
| first_indexed |
2025-11-26T13:28:05Z |
| last_indexed |
2025-11-26T13:28:05Z |
| _version_ |
1850624844228460544 |
| fulltext |
ISSN 1560-9189 , , 2018, . 20, 3 121
004.942.519.87
. . , . . , . .
. . , 2, 03113 ,
— , , -
- ,
,
, -
, . -
-
(Mini-
mum Cost Flow, MCF) , -
.
, ’ -
. ’ MSF
- -
.
: , - -
, minimum cost flow problem, multicommodity
minimal cost network flows, optimization modeling with spreadsheets.
(Minimum Cost Flow, MCF) —
m n ,
, — , xij, (i,
j)- , cij.
, , (K-
, K > 1) , ’ -
, , -
’ : «k- – – – -
» ,
K
.
© . . , . . , . .
. . , . . , . .
122
K-
(N, A), N — n (nodes), A — m
(arcs). ’ xk(i, j)
— k- (i, j)- , (i, j) A.
(costs) ck(i, j) k- , (i, j)- -
, / , , /
lk(i, j)/uk(i, j) - -
: ,
, 1/0 .
1- MCF ( )
— -
, ,
m - n - , ’ « - » -
m×n, -
- -
. -
. -
/ .
:
. = {xij} ,
.
1 1
min
m n
ij ij
i j
Z c x
. :
1
( )
n
ij i
j
x p , i — - ;
1
( )
n
ij j
i
x s , sj — j- ;
.ij ij ijl x u
1.
60 , m = 20 ( 1× 20), n = 40 (s1×s40), 800 .
.
(x, y), ( -
) 20×40, -
, : 1407 .,
2145 ., :
1
n
ij i
j
x p
1
n
ij j
i
x s —
.
: 10 , 25 -
, 5 — , 800 45 -
( . 1).
ISSN 1560-9189 , , 2018, . 20, 3 123
. 1. 20 ( ) 40 (s)
1- MCF ( )
-
(transshipment problem) N A .
,
, , -
. -
.
( )
, , /
.
« - »,
’
, ’
, , -
.
- — (+ ) , (– ) , 0
.
:
. . , . . , . .
124
— , ,
;
— ,
.
:
. = {xij}, i, j N ,
.
( , )
minij ij
i j D
Z c x
. :
:( , ) :( , )
ij ji i
j i j j j i
x x p i D ( - );
ij ij ijl x u .
2.
( . 2) 18 , 5
(2, 3, 9, 14, 15) 4 (1, 5, 11, 18),
72 . -
. -
(x, y)
( ) ’ -
, -
, -
: -
38 ., 42 .
. 2.
: : 11 (13/12), 1 (15/12), 5 (5/5), 18 (9/9), -
. 3.
. 3. 1-
ISSN 1560-9189 , , 2018, . 20, 3 125
’ -
- 1, -
K- K , -
k- (k = 1, …, K) , -
, -
( ) , ,
, K- 2.
( N, A, U,
L), . k- -
( , , ) ( -
, ), — lk(i, j) uk(i, j) -
xk(i, j).
3.
18
72 , ’ .
1 2, , -
.
, ,
— :
1: 2 (+1), 3 (+4), 15 (+5), 9 (+12), 14 (+16);
1 (–15), 11 (–13), 18 (–9), 5 (–5) +38/–42;
2: 1 (+4), 5 (+5), 3 (+7), 7 (+11); 12 (–17), 10 (–9), 14 (–6), 17 (–4) +27/–36.
, , 1
5 1 2, 3 —
. : x1(i, j) + x2(i, j) u(i, j).
( 10 .) -
. 4.
. 4. : 1, 2,
1 Dantzig G., Wolfe Ph. Decomposition principle for linear program. OR, 1960 [1, . 23. -
].
2 , .
. . , . . , . .
126
. 1: 1 (–4); 2: 14 (–6, ),
17 (–3).
( )
,
cij , (i, j)- , — « »,
. - -
, - « ». , -
, , ,
/ -
. ’ , -
, , , -
,
.
« » (node splitting), , « » ,
’ , , -
« » , -
.
n- , , n n ,
(n n ) (n n ) (n n ) -
,
, , , .
-
: —
18 72 , 36 -
144 — 36 n n .
4. 1- MCF .
( . 2) 18 36 ,
5 - (2, 3, 9, 14 15) , 4 - (1, 5, 11 18)
— 9 ,
( . 5).
.
:
ISSN 1560-9189 , , 2018, . 20, 3 127
— : {1 ± 18 } {1 ± 18 }. : n —
, n — ;
— 180 4- : 1) « » (72); 2) « » (72) —
’ ; 3) « » (18); 4) « » (18) — .
( . 5).
180 13 :
7 ( 1): { 2 ,1 = 15, 3 ,5 = 4, 5 ,11 = 1, 9 ,3 = 7, 10 ,11 = 7, 14 ,15 = 16,
15 ,11 = 5};
4 ( 2): { 3 ,2 = 5, 3 ,5 = 2, 15 ,10 = 7, 15 ,18 = 9};
0 ( 3);
2 ( 4): { 5 ,5 = 1, 18 ,18 = 9}.
. 5.
. . , . . , . .
128
5. 2- MCF .
-
1 2. :
. -
.
« » .
. 6, 7.
. 6. 2-
6. 4- MCF .
-
1× 4. :
— : 1(+47/–42), 2(+59/–52), 3(+103/–106),
4(+77/–88);
— .
ISSN 1560-9189 , , 2018, . 20, 3 129
. 7. 2- ( 10 .)
« » .
( . 8).
. 8. 4-
. . , . . , . .
130
. 8 58 720 ( 3),
: 1 (16), 2 (11), 3 (17), 4 (14).
. 9 . 8.
. 7. 2 (2 2 )
-
- -
, , K- ( -
, , ) .
1. . , / . . -
: , 1966. 601 .
2. ., . / . . : ,
1984. 391 .
3. Ahuja R., Magnanti T., Orlin J. Network Flows. Theory, Algorithms, and Applications. Pren-
tice Hall, 1993. 863 p.
4. Rouse W. Modeling and Visualization of Complex Systems and Enterprises. Explorations of
Physical, Human, Economic, and Social Phenomena. Wiley, 2015. 294 p.
5. Baker K. Optimization Modeling with Spreadsheets, 3-ed. Thomson, 2015. 354 p.
6. . ., . ., . .
. , . . 2017. . 19. 4. . 16–25
7. . . . WinQSB MS
Excel. : - , 2018. 208 .
8. . ., . ., . .
. , . . 2018. . 20. 2. .
52–59.
20.08.2018
3 5000
|