OPTYMALIZACJ
A PRZEPŁYWU
W SIECIACH
OPTYMALIZACJ
A PRZEPŁYWU
W SIECIACH
W porównaniu od klasycznych
zadań transportowych,
problemy
przepływów w sieciach
(które są
uogólnieniem zadań
transportowych)
dopuszczają
możliwość występowania w sieci
oprócz węzłów:
A
+
(dostawców) i
A
-
(odbiorców)
również węzłów oznaczonych jako
A
0
, które traktujemy jako
węzły
tranzytowe
lub
przeładunkowe
.
W zadaniach
przepływów w sieciach
można zrezygnować z:
• ograniczeń dotyczących
występowania (bądź też braku)
tras (łuków) łączących dane
węzły.
• Można również dodatkowo
uwzględnić
ograniczenia
przepustowości
(przepływu) na
poszczególnych łukach (trasach) i
to zarówno z dołu, jak i z góry.
W zadaniach
przepływów w sieciach
stosuje się najczęściej terminologię
zaczerpniętą z
hydrauliki
• węzły reprezentujące dostawców to
źródła
,
• węzły reprezentujące odbiorców to
ujścia
,
• wielkości podaży dostawców to
potencjały
źródeł
(czyli wg przyjętych wcześniej
oznaczeń
a
i
to potencjał i-tego źródła),
• wielkości popytu odbiorców to
potencjały
ujść
(czyli wg przyjętych wcześniej oznaczeń
b
j
to potencjał j-tego ujścia),
• konkretne przewozy to
przepływy
,
• węzeł tranzytowy (przeładunkowy) to taki
węzeł, w którym potok cieczy wpływającej do
niego jest równy potokowi cieczy
wypływającej z tego węzła.
Przy określaniu poszczególnych warunków
ograniczających dla węzłów można
wszystkie ich typy: dla
źródeł
,
ujść
i
punktów tranzytowych potraktować
jednolicie wykorzystując nierówność (a):
potok wypływający – potok wpływający <
potencjał węzła
przy założeniu, że:
potencjał źródła jest
dodatni
,
potencjał ujścia jest
ujemny
,
a węzła potencjał tranzytowego równy
zeru.
Oto przykład
źródła
(o numerze
k = 1
) i
budowa odpowiednich
warunków
ograniczających
przyjmując jako
k
oznaczenie numeru węzła.
Ogólny warunek ograniczający na
podstawie (a)
dla źródła jest następujący
potok wypływający – potok wpływający <
potencjał źródła
co dla naszego węzła źródła
k = 1
jest równoważne
nierówności:
Rozpatrzmy przykład
ujścia
(o numerze k =
5) i budowę odpowiednich
warunków
ograniczających
:
Ogólny warunek ograniczający na
podstawie (a)
dla ujścia jest następujący
potok wypływający – potok wpływający < -
potencjał ujścia
co dla naszego węzła ujścia
k = 5
jest równoważne
nierówności:
W węźle tranzytowym (przeładunkowym)
potok cieczy wpływającej do niego jest
równy potokowi cieczy wypływającej z tego
węzła.
Zrównoważenie potoków
wpływającego i wypływającego w
węźle tranzytowym:
potok wypływający – potok wpływający
= 0
co dla węzła tranzytowego
k = 3 jest równoważne
następującej równości:
Oto cała sieć wraz ze wszystkimi warunkami
ograniczającymi, przy czym numer warunku
odpowiada numerowi węzła sieci. Wstępnie
założono, że
węzłami źródłowymi są węzły 1 i 2,
natomiast
ujściami węzły o numerach 4, 5, 6 i 7.
Dodatkowo dochodzą
jeszcze warunki
ograniczające związane z
łukami sieci, gdyż na
każdym z tych łuków
przepływ musi być liczbą
dodatnią lub równą zeru,
czyli:
x
ij
ł
0
Oprócz tego przepływy te
mogą być ograniczone na
danym łuku (i,j) z
dołu (d
ij
)
i z
góry (g
ij
),
czyli:
d
ij
Ł x
ij
Ł
g
ij
Każde wartości
x
ij
będące rozwiązaniem
podanych
warunków ograniczających
dla
węzłów stanowią tzw.
przepływ
dopuszczalny
, który zaspokaja popyt
odbiorców (
ujść
) w ramach istniejącej
podaży dostawców (
źródeł
) i konkretnych
możliwości przewozowych.
W porównaniu do klasycznych
zagadnień transportowych, w których
rozwiązanie (czyli przepływ
dopuszczalny)
zawsze istnieje
w
zagadnieniach przepływu w sieciach
zdarza się, że przepływ dopuszczalny
nie istnieje (nie potrafimy wskazać
rozwiązania).
W ramach
przepływów dopuszczalnych
w
zagadnieniach przepływu w sieciach
rozpatrujemy dwa problemy:
1. Wyznaczamy wartości przepływów
dopuszczalnych aby uzyskać najniższy
koszt przepływu
K
p
, mając dane koszty
jednostkowe
h
ij
przepływów na
poszczególnych łukach sieci
(i,j)
należących do zbioru łuków sieci
Q
.
Ponieważ
całkowity koszt przepływu
jest
sumą iloczynów kosztów jednostkowych
h
ij
i odpowiadających im wielkości
przepływów
x
ij
(
zmiennych decyzyjnych
)
na poszczególnych łukach sieci
(i,j),
więc
rozwiązanie optymalne uzyskamy
opierając się na zadaniu optymalizacji
liniowej
W ramach
przepływów dopuszczalnych
w
zagadnieniach przepływu w sieciach
rozpatrujemy dwa problemy:
2.
Określamy dla jakich wartości
przepływów dopuszczalnych uzyskamy
największą wartość przepływu
W
p
,
przez którą rozumiemy sumę masy
towarów transportowanych od
dostawców (źródeł)
do
odbiorców
(ujść).
Rozwiązanie optymalne uzyskamy
opierając się na zadaniu optymalizacji
liniowej:
Można zauważyć, że wartość przepływu jest sumą
wszystkich lewych stron warunków
ograniczających dotyczących
źródeł.
Czyli dla
naszej sieci:
Przykład:
Zadanie przepływu w
sieciach
wielkości popytu w tonach (czyli
potencjały ujść),
Dla sieci o strukturze przedstawionej powyżej,
biorąc pod uwagę podane wielkości podaży w
tonach (czyli
potencjały źródeł
),
oraz jednostkowe koszty przepływu
h
ij
(zł/tonę)
wynoszące:
2
6
2
5
3
4
1
9
3
8
1
1
4
8
5
5
4
2
2
9
4
1
5
1
Dodatkowo mamy następujące ograniczenia:
2
6
2
5
3
4
1
9
3
8
1
1
4
8
5
5
4
2
2
9
4
1
5
1
na łuku
13
przepływ powinien być nie mniejszy niż
500 ton, lecz nie większy niż 700 ton,
na łuku
15
przepływ powinien być nie mniejszy niż
300 ton,
na łuku
23
przepływ powinien być nie większy niż
600 ton
Mamy następujące warunki
ograniczające:
W8: x
13
>
500
W1
:
W2
:
W2
:
W4
:
W5
:
W6
:
W7
:
W9: x
13
<
700
W10: x
15
>
300
W11: x
23
<
600
Wprowadzamy dane do EXCELA:
Do bloku komórek G5:G11 wprowadzamy numery
węzłów wraz z opisem ich rodzaju oraz wielkości
podaży węzłów źródłowych (do bloku I5:I6) i
popytu węzłów ujścia (do bloku J8:J11).
Wprowadzamy dane dotyczące wielkości
potencjałów poszczególnych węzłów.
Do bloku komórek
H5:H11
wprowadzamy formuły ujmujące lewe strony
pierwszych siedmiu (W1:W7)
warunków
ograniczających
, i tak:
=B10+B13-
B16
do komórki H5 wprowadzamy
formułę dotyczącą lewej
strony warunku (W1), czyli:
=B5+B6+B7-B8
itd.
W zadaniu postawimy sobie dwie funkcje
celu.
Pierwsza z nich będzie minimalizować ogólny
koszt przepływu
K
p
i zgodnie ze wzorem
wpiszemy do komórki H13 formułę
=SUMA.ILOCZYNÓW(
B5:B16
;
C5:C16
),
Druga funkcja celu ma za zadanie
zmaksymalizować wielkość przepływu
W
p
do
komórki H15 wpiszemy formułę =H5+H6.
W pierwszej kolejności
dokonamy optymalizacji
wielkości przewozów pod
kątem minimalizacji
ogólnego kosztu przepływu
K
p
Oto rozwiązanie optymalne wielkości
przewozów pod kątem minimalizacji
ogólnego kosztu przepływu
K
p
1
2
3
4
5
6
7
b
5
= 1600
1600
a
1
= 3000
a
2
= 4000
b
4
= 1300
b
6
= 2000
b
7
= 1100
1100
1300
2000
600
500
400
900
W drugiej kolejności dokonamy
optymalizacji wielkości przewozów
pod kątem
maksymalizacji
wielkości przepływu
W
p
Oto rozwiązanie optymalne wielkości
przewozów pod kątem maksymalizacji
wielkości przepływu
W
p
1
2
3
4
5
6
7
b
5
= 1600
900
a
1
= 3000
a
2
= 4000
b
4
= 1300
b
6
= 2000
b
7
= 1100
3100
2300
2000
900
700
700
1
2
3
4
5
6
7
b
5
= 1600
1600
a
1
= 3000
a
2
= 4000
b
4
= 1300
b
6
= 2000
b
7
= 1100
1100
1300
2000
600
500
400
900
Często ograniczenia przepustowości (najczęściej
z góry) dotyczą również poszczególnych węzłów
sieci.
Gdyby np. w rozwiązywanym przez nas
przypadku węzeł
tranzytowy nr 3
miał
ograniczoną górną granicę przepustowości do
wartości
600
ton, to uzyskane przez nas
rozwiązania przepływów są niedopuszczalne.
1
2
3
4
5
6
7
b
5
= 1600
900
a
1
= 3000
a
2
= 4000
b
4
= 1300
b
6
= 2000
b
7
= 1100
3100
2300
2000
900
700
700
Aby rozwiązać ten problem, do istniejących
warunków ograniczających
dodajemy
warunek:
x
13
+x
23
< 600
i rozwiązujemy to
zadanie ponownie.
(8):
x
13
+x
23
< 600
Lewą stronę tego warunku umieszczamy w
komórce
H12
, a cały warunek dodajemy do
warunków ograniczających w oknie dialogowym
Solver-Parametry.
Oto rozwiązanie optymalne poprzedniego
zadania po dodaniu warunku ograniczającego
przepustowość węzła nr 3 do górnej granicy
600
ton pod kątem
minimalnego kosztu przepływu
Oto rozwiązanie optymalne poprzedniego
zadania po dodaniu warunku ograniczającego
przepustowość węzła nr 3 do górnej granicy
600
ton pod kątem
maksymalnej wielkości przepływu
Innym sposobem ujęcia warunku
ograniczonej przepustowości dla węzła nr 3
jest wprowadzenie dodatkowego łuku
reprezentującego ten węzeł i przyjęcie na tym
właśnie łuku ograniczonej przepustowości.
Rozwiązując problemy przepływu w
sieciach możemy również uwzględniać
wzmacnianie
lub
osłabianie
przepływu
na łukach sieci.
Dotychczas rozpatrywaliśmy sieci, w
których dany przepływ
x
ij
na każdym
łuku (i,j) był taki sam na wejściu i na
wyjściu tego łuku.
Jeśli jednak weźmiemy pod uwagę
przesył energii elektrycznej w sieciach
energetycznych, to musimy uwzględnić
tendencję do zanikania wielkości prądu.
Z kolei w sieciach telekomunikacyjnych,
gdzie sygnały są wzmacniane, musimy
uwzględnić wielkości tego wzmocnienia.
W przypadku np.
osłabienia
przepływu
na łukach 54 i 56, odpowiednio, o 5% i
10% warunek (W5) dla węzła nr 5
przedstawiałby się następująco:
x
15
+ x
35
– 0,95x
54
– 0,9x
56
> 1600.