Politechnika Poznańska
Badania Operacyjne
K. Kukuła (red.), Badania operacyjne w przykładach i zadaniach,
PWN, Warszawa 2004r.
S.I.Gass, Programowanie liniowe, PWN, Warszawa 1976r.
W.I.Zangwill, Programowanie nieliniowe, WNT, Warszawa 1974r.
R.G.Garfinkel, G.L.Nemhauser, Programowanie całkowitoliczbowe,
PWN, Warszawa 1978r.
Politechnika Poznańska
Badania Operacyjne
Programowanie
matematyczne
Politechnika Poznańska
Badania Operacyjne
Definicja
Na zadanie programowania matematycznego składają się następujące
składniki:
1
funkcja celu (kryterialna) z = f (x
1
, x
2
, ..., x
n
);
2
problem optymalizacyjny (np. znajdź max lub min funkcji celu);
3
ograniczenia bilansowe postaci
¬
nierówności F (x
1
, x
2
, ..., x
n
) ¬ b;
=
równania F (x
1
, x
2
, ..., x
n
) = b;
nierówności F (x
1
, x
2
, ..., x
n
) b;
4
ograniczenia brzegowe (np. x
i
0, ¬ 2, całkowite, = 0 lub 1);
5
liczba (dodatnia) stopni swobody: n − p > 0 gdzie n - ilość
zmiennych, p - ilość ograniczeń bilansowych.
Politechnika Poznańska
Badania Operacyjne
Definicja
Wektor (x
1
, x
2
, ..., x
n
) gdzie x
i
∈ R dla i = 1, 2, ..., n (program) nazywamy
programem dopuszczalnym jeżeli spełnia warunek 3 w Definicji 1.1.
Program dopuszczalny nazywamy programem optymalnym jeżeli spełnia
dodatkowo warunek 2. Zbiór programów (wektorów dopuszczalnych)
nazywamy zbiorem rozwiązań dopuszczalnych.
Politechnika Poznańska
Badania Operacyjne
Definicja
Jeżeli w Definicji 1.1 wszystkie funkcje (tzn. f oraz F ) są funkcjami
liniowymi wielu zmiennych, zadanie takie nazywamy zadaniem
programowania liniowego PL.
Przykład zadania PL
P
n
j =1
c
j
x
j
→ max( lub min);
P
n
j =1
a
ij
x
j
¬
b
i
i = 1, ..., m
1
;
P
n
j =1
a
ij
x
j
b
i
i = m
1
+ 1, ..., m
2
;
P
n
j =1
a
ij
x
j
=
b
i
i = m
2
+ 1, ..., m ;
Politechnika Poznańska
Badania Operacyjne
Wyznaczyć obszar ograniczony nierównościami
(
2y + x 12;
2y − x ¬ 2;
Politechnika Poznańska
Badania Operacyjne
y = −
x
2
+ 6
2y + x 12
2y − x ¬ 2
(
2y + x 12;
2y − x ¬ 2
y =
x
2
+ 1
Politechnika Poznańska
Badania Operacyjne
y = −
x
2
+ 6
2y + x 12
2y − x ¬ 2
(
2y + x 12;
2y − x ¬ 2
(5, 3.5)
y − x = −1.5
y − x = −5
y − x = 3
y =
x
2
+ 1
Politechnika Poznańska
Badania Operacyjne
y = −
x
2
+ 6
(5, 3.5)
2y + x 10
2y − x ¬ 2
(
2y + x 10;
2y − x ¬ 2;
y + x = 1
y + x = 4
y + x = 7
y + x = 11
y + x = 8.5
y =
x
2
+ 1
Politechnika Poznańska
Badania Operacyjne
y = −
x
2
+ 6
(5, 3.5)
2y + x ¬ 10
2y − x 2
(
2y + x ¬ 10;
2y − x 2;
y − x = 1
y − x = 5
y − x = −1.5
y + x = 1
y + x = 6
y + x = 8.5
y =
x
2
+ 1
Politechnika Poznańska
Badania Operacyjne
y = −
x
2
+ 6
(5, 3.5)
2y + x ¬ 10
2y − x 2
(
2y + x ¬ 10;
2y − x 2;
y − x = 1
y − x = 5
y − x = −1.5
y + x = 1
y + x = 6
y + x = 8.5
y =
x
2
+ 1
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
y
¬
−
x
2
+ 6;
y
¬
x
2
+ 1;
x , y
0;
10y + x
→ max;
2y + x
¬
12;
2y − x
¬
2;
10y + x + 0x
d
1
+ 0x
d
2
→ max;
2y + x + x
d
1
=
12;
2y − x + x
d
2
=
2;
x
d
1
, x
d
2
0;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
y
¬
−
x
2
+ 6;
y
¬
x
2
+ 1;
x , y
0;
10y + x
→ max;
2y + x
¬
12;
2y − x
¬
2;
10y + x + 0x
d
1
+ 0x
d
2
→ max;
2y + x + x
d
1
=
12;
2y − x + x
d
2
=
2;
x
d
1
, x
d
2
0;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
y
¬
−
x
2
+ 6;
y
¬
x
2
+ 1;
x , y
0;
10y + x
→ max;
2y + x
¬
12;
2y − x
¬
2;
10y + x + 0x
d
1
+ 0x
d
2
→ max;
2y + x + x
d
1
=
12;
2y − x + x
d
2
=
2;
x
d
1
, x
d
2
0;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
x
d
1
=
12 − (2y + x ) ;
x
d
2
=
2 − (2y − x ) ;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
x
d
1
=
12 − (2y + x ) ;
x
d
2
=
2 − (2y − x ) ;
max{10, 1} = 10
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
x
d
1
=
12 − (2y + x ) ;
x
d
2
=
2 − (2y − x ) ;
max{10, 1} = 10
12 − 2y
0;
2 − 2y
0;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
x
d
1
=
12 − (2y + x ) ;
x
d
2
=
2 − (2y − x ) ;
max{10, 1} = 10
6
y ;
1
y ;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
10y + x
→ max;
x
d
1
=
12 − (2y + x ) ;
x
d
2
=
2 − (2y − x ) ;
max{10, 1} = 10
1 y
10 − 5x
d
2
+ 6x
→ max;
x
d
1
=
10 −
−x
d
2
+ 2x
;
y
=
1 −
x
d
2
2
−
x
2
;
Politechnika Poznańska
Badania Operacyjne
Metoda simpleks
40 − 2x
d
2
− 3x
d
1
→ max;
x
=
5 −
−
x
d
2
2
+
x
d
1
2
;
y
=
1 −
x
d
2
4
+
x
d
1
4
;
Politechnika Poznańska
Badania Operacyjne
Definicja
Zadaniem PL o postaci standardowej nazywamy zadanie, w którym
wszystkie warunki ograniczające są nierównościami typu ”¬” dla zadań na
maksimum bądź nierównościami ”” dla zadań na minimum oraz
wszystkie zmienne są nieujemne.
Przykłady postaci standardowej PL
P
n
j =1
c
j
x
j
→ max;
P
n
j =1
a
ij
x
j
¬
b
i
i = 1, ..., m ;
x
1
, ..., x
n
0;
P
n
j =1
c
j
x
j
→ min;
P
n
j =1
a
ij
x
j
b
i
i = 1, ..., m ;
x
1
, ..., x
n
0;
Politechnika Poznańska
Badania Operacyjne
Przykłady postaci standardowej PL
P
n
j =1
c
j
x
j
→ max;
P
n
j =1
a
ij
x
j
¬
b
i
i = 1, ..., m ;
x
1
, ..., x
n
0;
P
n
j =1
c
j
x
j
→ min;
P
n
j =1
a
ij
x
j
b
i
i = 1, ..., m ;
x
1
, ..., x
n
0;
Przykłady postaci standardowej PL dla zapisu macierzowego
cx
→ max;
Ax
¬
b;
x
0;
cx
→ min;
Ax
b;
x
0;
Politechnika Poznańska
Badania Operacyjne
Definicja
Zadaniem PL o postaci kanonicznej nazywamy zadanie, w którym
wszystkie warunki ograniczające są równościami oraz wszystkie zmienne są
nieujemne.
Przykłady postaci kanonicznej PL
P
n
j =1
c
j
x
j
→ max(lub min);
P
n
j =1
a
ij
x
j
=
b
i
i = 1, ..., m ;
x
1
, ..., x
n
0;
cx
→ max(lub min);
Ax
=
b;
x
0;
Politechnika Poznańska
Badania Operacyjne
10y + x
→ max;
2y + x
¬
12;
2y − x
¬
2;
y , x
0
Tabela simleksowa
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
2
1
1
0
12
0
x
d
2
2
-1
0
1
2
z
j
0
0
0
0
0
c
j
− z
j
10
1
0
0
Politechnika Poznańska
Badania Operacyjne
10y + x + 0x
d
1
+ 0x
d
2
→ max;
2y + x + 1x
d
1
+ 0x
d
2
=
12;
2y − x + 0x
d
1
+ 1x
d
2
=
2;
y , x , x
1
, x
2
0
Tabela simleksowa
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
2
1
1
0
12
0
x
d
2
2
-1
0
1
2
z
j
0
0
0
0
0
c
j
− z
j
10
1
0
0
Politechnika Poznańska
Badania Operacyjne
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
2
1
1
0
12
0
x
d
2
2
-1
0
1
2
z
j
0
0
0
0
0
c
j
− z
j
10
1
0
0
max(10, 1, 0, 0) = 10 ⇒ y
Politechnika Poznańska
Badania Operacyjne
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
2
1
1
0
12
12/2
0
x
d
2
2
-1
0
1
2
2/2
z
j
0
0
0
0
0
min(6, 1) = 1 ⇒ x
d
2
c
j
− z
j
10
1
0
0
max(10, 1, 0, 0) = 10 ⇒ y
Politechnika Poznańska
Badania Operacyjne
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
2
1
1
0
12
0
x
d
2
2
-1
0
1
2
z
j
0
0
0
0
0
c
j
− z
j
10
1
0
0
Przy pomocy operacji elementarnych na wierszach macierzy, zmienimy
kolumnę y (y jest nową zmienną bazową) tak aby składała się wyłącznie z
zer, za wyjątkiem elementu leżącego aktualnie w wierszu x
d
2
(stara -
zmienna bazowa).
Politechnika Poznańska
Badania Operacyjne
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
2
1
1
0
12
0
x
d
2
2
-1
0
1
2
z
j
0
0
0
0
0
c
j
− z
j
10
1
0
0
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
0
2
1
-1
10
10
y
1
-1/2
0
1/2
1
z
j
10
-5
0
5
10
c
j
− z
j
0
6
0
-5
Politechnika Poznańska
Badania Operacyjne
y
x
x
d
1
x
d
2
c
j
10
1
0
0
0
x
d
1
0
2
1
-1
10
10
y
1
-1/2
0
1/2
1
z
j
10
-5
0
5
10
c
j
− z
j
0
6
0
-5
y
x
x
d
1
x
d
2
c
j
10
1
0
0
1
x
0
1
1/2
-1/2
5
10
y
1
0
1/4
1/4
7/2
z
j
10
1
3
2
40
c
j
− z
j
0
0
-3
-2
Politechnika Poznańska
Badania Operacyjne
Macierzowy zapis pierwszej tabeli simpleksowej
c
c
b
x
b
A
I
b
z
j
0
0
c
j
− z
j
c
Politechnika Poznańska
Badania Operacyjne
Macierzowy zapis pierwszej tabeli simpleksowej
c
c
b
x
b
A
I
b
z
j
0
0
c
j
− z
j
c
c = [10 1 0 0]
A =
"
2
1
2
−1
#
, c
b
=
"
0
0
#
, b =
"
12
2
#
Politechnika Poznańska
Badania Operacyjne
Macierzowy zapis następnych tabeli simpleksowych
c
c
b,l
x
b,l
B
−1
l
A
B
−1
l
B
−1
l
b
z
j
c
b,l
B
−1
l
A
c
b,l
B
−1
l
c
b,l
B
−1
l
b
Gdzie macierz B
l
powstaje z poprzedniej macierzy
B
l −1
przez zastąpienie kolumny zmiennej
wychodzącej z bazy przez kolumnę zmiennej
wchodzącej do bazy. Macierz B w pierwszej tabelce
jest macierzą jednostkową.
x
d
1
x
d
2
B =
"
1
0
0
1
#
Politechnika Poznańska
Badania Operacyjne
x
d
1
x
d
2
B
1
=
"
1
2
0
2
#
,
x
d
1
y
B
2
=
"
1
0
−1/2 1
#
B
−1
1
=
"
1
−1
0
1/2
#
, B
−1
2
=
"
1/2
0
1/4
1
#
y
x
B
−1
1
A =
"
0
2
1
−1/2
#
c
b,l
B
−1
l
A = [0 0], c
b,l
B
−1
l
= [0 0]
B
−1
l
b = [10 1]
T
Politechnika Poznańska
Badania Operacyjne
Analiza wrażliwości - zmiana współczynników funkcji celu
y
x
x
d
1
x
d
2
c
j
10+δ
1
0
0
1
x
0
1
1/2
-1/2
5
10+δ
y
1
0
1/4
1/4
7/2
z
j
10+δ
1
3+δ/4
2+δ/4
40+7δ/2
c
j
− z
j
0
0
-3-δ/4
-2-δ/4
−3 −
δ
4
¬ 0, −2 −
δ
4
¬ 0
−12 ¬ δ, −8 ¬ δ
δ −8
Politechnika Poznańska
Badania Operacyjne
Analiza wrażliwości - zmiana wartości wyrazów wolnych
b
0
=
"
12 + ε
1
2
#
B
−1
ostatni
b
0
0
0 ¬ B
−1
ostatni
b
0
=
"
1/2
0
1/4
1
# "
12 + ε
1
2
#
=
"
6 +
ε
1
2
5 +
ε
1
4
#
ε
1
−12
Politechnika Poznańska
Badania Operacyjne
Programowanie całkowitoliczbowe
(5, 3.5)
y − x → min
2y + x ¬ 10;
2y − x 2;
x , y ∈ N
y − x = −1.5
Politechnika Poznańska
Badania Operacyjne
Programowanie całkowitoliczbowe
y − x → min
2y + x ¬ 10;
2y − x 2;
x , y ∈ N
⇒ (5,
7
2
)
Politechnika Poznańska
Badania Operacyjne
Programowanie całkowitoliczbowe
y − x → min
2y + x ¬ 10;
2y − x 2;
x , y ∈ N
⇒ (5,
7
2
)
y
7
2
y − x → min
2y + x ¬ 10;
2y − x 2;
y 4
;
x , y ∈ N
y ¬
7
2
y − x → min
2y + x ¬ 10;
2y − x 2;
y ¬ 3
;
x , y ∈ N
Politechnika Poznańska
Badania Operacyjne
Reguła tworzenia zadania dualnego
zadanie pierwotne
P
n
j =1
c
j
x
j
→ max;
P
n
j =1
a
ij
x
j
¬
b
i
i = 1, 2, ..., m ;
x
j
0
j = 1, 2, ..., n ;
zadanie dualne
P
m
i =1
b
j
y
j
→ min;
P
m
i =1
a
ij
y
i
c
j
j = 1, 2, ..., n ;
y
i
0
i = 1, 2, ..., m ;
Politechnika Poznańska
Badania Operacyjne
Reguła tworzenia zadania dualnego - przekład
zadanie pierwotne
7x
1
+ 8x
2
− 9x
3
→ max;
2x
1
+ 4x
2
+ 3x
3
¬
13;
5x
1
− 3x
2
− 6x
3
¬
11;
x
1
, x
2
, x
3
0;
zadanie dualne
13y
1
+ 11y
2
→ min;
2y
1
+ 5y
2
7;
4y
1
− 3y
2
8;
3y
1
− 6y
2
−9;
y
1
, y
2
0;
Politechnika Poznańska
Badania Operacyjne
Twierdzenie
Jeżeli rozwiązania dopuszczalne zagadnienia pierwotnego i dualnego
istnieją to istnieje rozwiązanie optymalne każdego z nich.
Twierdzenie
Zagadnienie dualne do dualnego jest zagadnieniem pierwotnym.
Twierdzenie
Jeżeli zagadnienie pierwotne ma skończone rozwiązanie optymalne to
odpowiednie zagadnienie dualne ma też skończone rozwiązanie optymalne i
ekstrema ich są równe.
Politechnika Poznańska
Badania Operacyjne
Twierdzenie
Jeżeli zagadnienie pierwotne nie ma optymalnego rozwiązania
ograniczonego to zagadnienie dualne nie ma rozwiązania dopuszczalnego.
Twierdzenie
Dla optymalnych rozwiązań zagadnienia pierwotnego i dualnego prawdziwe
są stwierdzenia:
1
jeżeli w k-tej zależności dowolnego układu występuje nierówność
wówczas k-ta zmienna w jego układzie dualnym jest równa zero,
2
jeżeli k-ta zmienna jest dodatnia w dowolnym układzie, wówczas k-ta
zależność w jego układzie dualnym jest równością.
Politechnika Poznańska
Badania Operacyjne
Ogólny model
Zagadnienie transportowe polega na znalezieniu minimalnych kosztów
transportu jednorodnego dobra, pomiędzy każdym z R dostawców i
każdym z N odbiorców. Dane są koszty transportu c
i ,j
od każdego (i -tego)
dostawcy do każdego (j -tego) odbiorcy, oraz zapotrzebowanie odbiorców
B
j
i zapasy dostawców A
i
.
Politechnika Poznańska
Badania Operacyjne
Ogólny model
O
1
O
2
. . .
O
N
A
i
D
1
c
1,1
c
1,2
. . .
c
1,N
A
1
D
2
c
2,1
c
2,2
. . .
c
2,N
A
2
. . .
. . .
. . .
. . .
. . .
. . .
D
R
c
R,1
c
R,2
. . .
c
R,N
A
R
B
j
B
1
B
2
. . .
B
N
Politechnika Poznańska
Badania Operacyjne
Ogólny model
W przypadku gdy
R
X
i =1
A
i
=
N
X
j =1
B
j
tzn. w sytuacji gdy dostawcy wysyłają dokładnie tyle towaru ile potrzebują
odbiorcy, mamy do czynienia z zamkniętym zagadnieniem
transportowym (ZZT). Gdy zapotrzebowanie jest mniejsze z otwartym
zagadnieniem transportowym (OZT). Każde OZT można sprowadzić
do ZZT.
Politechnika Poznańska
Badania Operacyjne
Model matematyczny zamkniętego zagadnienia transportowego
D
1
:
x
1,1
+ · · · + x
1,N
= A
1
;
O
1
:
x
1,1
+ · · · + x
R,1
= B
1
;
. . .
. . . ;
. . .
. . . ;
D
R
:
x
R,1
+ · · · + x
R,N
= A
R
;
O
N
:
x
1,N
+ · · · + x
R,N
= B
N
;
c
1,1
x
1,1
+ · · · + c
1,N
x
1,N
+ · · · + c
R,1
x
R,1
+ · · · + c
R,N
x
R,N
→ min
Politechnika Poznańska
Badania Operacyjne
Zamknięte Zagadnienie Transportowe - Zadanie
Trzy magazyny M
1
, M
2
, M
3
zaopatrują trzy przedsiębiorstwa P
1
, P
2
, P
3
w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw A
i
(w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw B
j
(w tonach) podaje poniższa tablica.
P
1
P
2
P
3
A
i
M
1
90
80
30
90
M
2
70
60
70
60
M
3
40
50
30
50
B
j
80
20
100
200
X
B
j
= 80 + 20 + 100 = 200 = 90 + 60 + 50 =
X
A
i
Zatem jest to zagadnienie zamknięte.
Politechnika Poznańska
Badania Operacyjne
Model matematyczny zadania
P
1
P
2
P
3
A
j
M
1
90
80
30
90
M
2
70
60
70
60
M
3
40
50
30
50
B
i
80
20
100
200
Oznaczmy przez x
i ,j
ilość towaru który zostanie przesłany od i -tego
dostawcy do j -tego odbiorcy. Wówczas możemy wypisać
ograniczenia dostawców
x
1,1
+ x
1,2
+ x
1,3
= 90
x
2,1
+ x
2,2
+ x
2,3
= 60
x
3,1
+ x
3,2
+ x
3,3
= 50
ograniczenia odbiorców
x
1,1
+ x
2,1
+ x
3,1
= 80
x
1,2
+ x
2,2
+ x
3,2
= 20
x
1,3
+ x
2,3
+ x
3,3
= 100
Funkcja celu:
zminimalizować funkcję
90x
1,1
+ 80x
1,2
+ 30x
1,3
+ 70x
2,1
+ 60x
2,2
+ 70x
2,3
+ 40x
3,1
+ 50x
3,2
+ 30x
3,3
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
Wyjściowa tablica
P
1
P
2
P
3
A
j
M
1
90
80
30
90
M
2
70
60
70
60
M
3
40
50
30
50
B
i
80
20
100
200
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
Będziemy postępować następująco:
1
idziemy do komórki ”północno-zachodniej” tzn. (P
1
, M
1
);
2
do komórki w której jesteśmy (P
m
, M
n
) wpisujemy M = min{A
n
, B
m
};
3
od wartości A
n
oraz B
m
odejmujemy M;
4
jeżeli A
n
= 0 wówczas przesuwamy się o jedną komórkę w dół, w
przeciwnym wypadku (B
m
= 0) przesuwamy się o jedną komórkę w
prawo;
5
jeżeli nie jesteśmy w ostatniej (dolna-prawa) komórce wracamy do
punktu 2 algorytmu.
Ponieważ mamy do czynienia z ZZT więc na końcu naszego algorytmu
otrzymamy same zera w kolumnie A
i
oraz wierszu B
j
. Jeżeli tak się nie
stało szukamy błędu :-).
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
min{80, 90} = 80
P
1
P
2
P
3
M
1
80
90
—–
M
2
60
M
3
50
80
—–
20
100
10
0
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
min{10, 20} = 10
P
1
P
2
P
3
M
1
80
10
90
—–
M
2
60
M
3
50
80
—–
20
—–
100
10
—–
0
0
10
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
min{10, 60} = 10
P
1
P
2
P
3
M
1
80
10
90
—–
M
2
10
60
—–
M
3
50
80
—–
20
—–
100
10
—–
0
50
0
10
—–
0
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
min{50, 100} = 50
P
1
P
2
P
3
M
1
80
10
90
—–
M
2
10
50
60
—–
M
3
50
80
—–
20
—–
100
——
10
—–
0
50
—–
0
0
10
—–
50
0
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego
min{50, 50} = 50
P
1
P
2
P
3
M
1
80
10
90
—–
M
2
10
50
60
—–
M
3
50
50
—–
80
—–
20
—–
100
——
10
—–
0
50
—–
0
0
0
10
—–
50
—–
0
0
Politechnika Poznańska
Badania Operacyjne
Otrzymaliśmy zatem rozwiązanie naszego zadania. Metoda ta jest
niezależna od kosztów transportu, zatem wyniki które otrzymaliśmy będą
prawie zawsze dalekie od optymalności. Do znalezienia optymalnego
rozwiązania powinniśmy teraz wykorzystać algorytm transportowy. Koszt
transportu w naszym zadaniu jest następujący:
z = 80 · 90 + 10 · 80 + 10 · 60 + 50 · 70 + 50 · 30
=
7200 + 800 + 600 + 3500 + 1500
=
13600
Politechnika Poznańska
Badania Operacyjne
Metoda minimalnego elementu macierzy
Metoda ta polega na przetworzeniu poniższej tabeli
P
1
P
2
P
3
M
1
90
80
30
M
2
70
60
70
M
3
40
50
30
w następujący sposób i w podanej kolejności:
1
od każdego wiersza odjąć najmniejszy element danego wiersza;
2
od każdej kolumny odjąć najmniejszy element danej kolumny.
Wykonajmy zatem powyższe operacje.
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
M
1
90
80
30
M
2
70
60
70
M
3
40
50
30
→
P
1
P
2
P
3
M
1
60
50
0
M
2
10
0
10
M
3
10
20
0
min{90, 80, 30} = 30
min{70, 60, 70} = 60
min{40, 50, 30} = 30
min{60, 10, 10} = 10
min{20, 0, 20} = 0
min{0, 10, 0} = 0
P
1
P
2
P
3
M
1
50
50
0
M
2
0
0
10
M
3
0
20
0
Politechnika Poznańska
Badania Operacyjne
Będziemy wypełniać tabelkę która pojawi się na następnym slajdzie,
podobnie jak w Metodzie Kąta Północno-Zachodniego, z tą różnicą, że
będziemy starać się wpisywać liczby tylko do pustych kratek, czyli tych w
których pojawiły się w poprzednim kroku zera. Jeżeli uda się nam to
wykonać wówczas będzie to rozwiązanie optymalne.
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
A
j
M
1
x
x
90
M
2
x
60
M
3
x
50
B
i
80
20
100
Przeanalizujmy zatem dokładnie nasze zadanie. Warto rozpocząć algorytm
od wierszy i kolumn w których jest tylko jedno puste miejsce.
Politechnika Poznańska
Badania Operacyjne
Jedno puste miejsce jest w naszym przykładzie tylko w drugiej kolumnie
oraz w pierwszym wierszu. Zacznijmy od pierwszego wiersza (element
(P
3
, M
1
)) : min{100, 90} = 90; w drugiej kolumnie (element (P
2
, M
2
))
natomiast: min{20, 60} = 20. Zatem nowa tabelka będzie wyglądała
następująco:
P
1
P
2
P
3
A
j
M
1
x
x
90
0
M
2
20
x
40
M
3
x
50
B
i
80
0
10
Politechnika Poznańska
Badania Operacyjne
Teraz puste miejsca są w trzeciej kolumnie i w drugim wierszu. Nowa
tabelka będzie wyglądała następująco:
P
1
P
2
P
3
A
j
M
1
x
x
90
0
M
2
40
20
x
0
M
3
x
10
40
B
i
40
0
0
Politechnika Poznańska
Badania Operacyjne
Ostatnia tabela wygląda następująco:
P
1
P
2
P
3
A
j
M
1
x
x
90
0
M
2
40
20
x
0
M
3
40
x
10
0
B
i
0
0
0
Politechnika Poznańska
Badania Operacyjne
Ponieważ udało się nam wpisywać wartości liczbowe wyłącznie do pustych
komórek, jesteśmy pewni, iż rozwiązanie które otrzymaliśmy jest
rozwiązaniem optymalnym. Możemy zatem zapisać
z
min
= 90 · 30 + 40 · 70 + 20 · 60 + 40 · 40 + 10 · 30
=
2700 + 2800 + 1200 + 1600 + 300
=
8600.
Politechnika Poznańska
Badania Operacyjne
Zamknięte Zagadnienie Transportowe - blokada trasy
Trzy magazyny M
1
, M
2
, M
3
zaopatrują trzy przedsiębiorstwa P
1
, P
2
, P
3
w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw A
i
(w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw B
j
(w tonach) podaje poniższa tablica. Z
niewyjaśnionych powodów nie można z magazynu M
2
zaopatrywać
przedsiębiorstwa P
2
.
P
1
P
2
P
3
A
i
M
1
90
80
30
90
M
2
70
x
70
60
M
3
40
50
30
50
B
j
80
20
100
200
x → ∞
Politechnika Poznańska
Badania Operacyjne
Zamknięte Zagadnienie Transportowe - blokada trasy
Trzy magazyny M
1
, M
2
, M
3
zaopatrują trzy przedsiębiorstwa P
1
, P
2
, P
3
w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw A
i
(w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw B
j
(w tonach) podaje poniższa tablica. Z
niewyjaśnionych powodów wielkość dostaw z magazynu M
2
do
przedsiębiorstwa P
2
może być równa maksymalnie 5 jednostek a koszt
przewozu to 60 (zł/t).
P
1
P
2
P
3
A
i
M
1
90
80
30
90
M
2
70
60(max 5)
70
60
M
3
40
50
30
50
B
j
80
20
100
200
Politechnika Poznańska
Badania Operacyjne
Zamknięte Zagadnienie Transportowe - blokada trasy
Trzy magazyny M
1
, M
2
, M
3
zaopatrują trzy przedsiębiorstwa P
1
, P
2
, P
3
w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw A
i
(w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw B
j
(w tonach) podaje poniższa tablica. Z
niewyjaśnionych powodów wielkość dostaw z magazynu M
2
do
przedsiębiorstwa P
2
może być równa maksymalnie 5 jednostek a koszt
przewozu to 60 (zł/t).
P
1
P
I
2
P
II
2
P
3
A
i
M
1
90
80
80
30
90
M
2
70
60
x
70
60
M
3
40
50
50
30
50
B
j
80
5
15
100
200
x → ∞
Politechnika Poznańska
Badania Operacyjne
Zagadnienie przydziału
Trzy karetki pogotowia mające bazę w miastach M
1
, M
2
, M
3
”obsługują”
trzy miejscowości P
1
, P
2
, P
3
. Znaleźć najniższe koszty transportu
medycznego. Koszty transportu przedstawia tabelka.
P
1
P
2
P
3
A
i
M
1
90
80
30
M
2
70
60
70
M
3
40
50
30
B
j
Politechnika Poznańska
Badania Operacyjne
Zagadnienie przydziału
Trzy karetki pogotowia mające bazę w miastach M
1
, M
2
, M
3
”obsługują”
trzy miejscowości P
1
, P
2
, P
3
. Znaleźć najniższe koszty transportu
medycznego. Koszty transportu przedstawia tabelka.
P
1
P
2
P
3
A
i
M
1
90
80
30
1
M
2
70
60
70
1
M
3
40
50
30
1
B
j
1
1
1
Politechnika Poznańska
Badania Operacyjne
Przypadek wielu rozwiązań
P
1
P
2
P
3
A
i
M
1
90
30
10
30
M
2
40
70
50
20
B
j
10
10
30
Politechnika Poznańska
Badania Operacyjne
Przypadek wielu rozwiązań
P
1
P
2
P
3
A
i
M
1
90
30
10
30
M
2
40
70
50
20
B
j
10
10
30
Możliwe rozwiązania optymalne
R
1
P
1
P
2
P
3
M
1
–
–
30
M
2
10
10
–
R
2
P
1
P
2
P
3
M
1
–
10
20
M
2
10
–
10
10 · 40 + 10 · 70 + 30 · 10 = 10 · 40 + 10 · 30 + 20 · 10 + 10 · 50 = 1400
Politechnika Poznańska
Badania Operacyjne
Możliwe rozwiązania optymalne
R
1
P
1
P
2
P
3
M
1
–
–
30
M
2
10
10
–
R
2
P
1
P
2
P
3
M
1
–
10
20
M
2
10
–
10
Ogólne rozwiązanie optymalne
α · R
1
+ β · R
2
α + β = 1
Politechnika Poznańska
Badania Operacyjne
Możliwe rozwiązania optymalne
R
1
P
1
P
2
P
3
M
1
–
–
30
M
2
10
10
–
R
2
P
1
P
2
P
3
M
1
–
10
20
M
2
10
–
10
Ogólne rozwiązanie optymalne
α · R
1
+ β · R
2
α + β = 1
R
P
1
P
2
P
3
M
1
–
10β
30α + 20β
M
2
10α + 10β
10α
10β
α ∈ [0, 1]
Politechnika Poznańska
Badania Operacyjne
Ogólne rozwiązanie optymalne
R
P
1
P
2
P
3
M
1
–
10 − 10α
20 + 10α
M
2
10
10α
10 − 10α
α ∈ [0, 1]
Politechnika Poznańska
Badania Operacyjne
Otwarte Zagadnienie Transportowe
Trzy magazyny M
1
, M
2
, M
3
zaopatrują trzy przedsiębiorstwa P
1
, P
2
, P
3
w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw A
i
(w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw B
j
(w tonach) podaje poniższa tablica.
P
1
P
2
P
3
A
i
M
1
90
80
30
90
M
2
70
60
70
60
M
3
40
50
30
80
B
j
80
20
100
X
B
j
= 80 + 20 + 100 = 200 < 230 = 90 + 60 + 80 =
X
A
i
Zatem jest to zagadnienie otwarte.
Politechnika Poznańska
Badania Operacyjne
W przypadku (OZT) dodajemy dodatkowego fikcyjnego odbiorcę F ,
koszty transportu do odbiorcy F jest równy 0 a jego zapotrzebowanie
P
A
i
−
P
B
j
. Jest możliwe i często tak się formułuje zadania, że F jest
traktowany jak magazyn przyzakładowy a ”koszty transportu” do F są
kosztami magazynowania minimalnymi w stosunku do ”normalnych”
kosztów transportu. Tak przeformułowane zadanie jest już (ZZT), które
potrafimy już rozwiązać.
Politechnika Poznańska
Badania Operacyjne
Tablica naszego zadania
P
1
P
2
P
3
F
A
i
M
1
90
80
30
0
90
M
2
70
60
70
0
60
M
3
40
50
30
0
80
B
j
80
20
100
30
230
Politechnika Poznańska
Badania Operacyjne
Metoda kąta północno-zachodniego doprowadzi nas do następującej
tabelki,
P
1
P
2
P
3
F
A
i
M
1
80
10
0
M
2
10
50
0
M
3
50
30
0
B
j
0
0
0
0
230
dzięki której możemy odczytać wartość kosztów transportu
z = 80 · 90 + 10 · 80 + 10 · 60 + 50 · 70 + 50 · 30 + 30 · 0
=
7200 + 800 + 600 + 3500 + 1500
=
13600.
Politechnika Poznańska
Badania Operacyjne
Metoda minimalnego elementu macierzy doprowadzi nas do tabeli
P
1
P
2
P
3
F
M
1
90
M
2
20
10
30
M
3
80
Rozwiązanie które otrzymaliśmy nie musi być optymalnym, choć
prawdopodobnie lepsze od rozwiązania z poprzedniej metody
z = 80 · 40 + 20 · 60 + 90 · 30 + 10 · 70 + 30 · 0
=
3200 + 1200 + 2700 + 700 + 0 = 7800.
Politechnika Poznańska
Badania Operacyjne
Zagadnienie Lokalizacji Produkcji
Projektowana jest budowa trzech zakładów: R
1
, R
2
, R
3
, które będą
zaopatrywały trzy przedsiębiorstwa S
1
, S
2
, S
3
w pewien surowiec.
Prognozowane jednostkowe koszty transportu (w zł/t), jednostkowe koszty
produkcji p
i
, planowane miesięczne wielkości dostaw A
i
(w tonach) oraz
miesięczne zapotrzebowanie przedsiębiorstw B
j
(w tonach) podaje
poniższa tablica.
S
1
S
2
S
3
p
i
A
i
R
1
90
80
30
290
120
R
2
70
60
70
260
80
R
3
40
50
30
310
90
B
j
80
20
100
Politechnika Poznańska
Badania Operacyjne
Zagadnienie Lokalizacji Produkcji
S
1
S
2
S
3
A
i
R
1
90 + 290
80 + 290
30 + 290
120
R
2
70 + 260
60 + 260
70 + 260
80
R
3
40 + 310
50 + 310
30 + 310
90
B
j
80
20
100
Politechnika Poznańska
Badania Operacyjne
S
1
S
2
S
3
R
1
100
R
2
80
R
3
20
Zatem powinniśmy wybudować wszystkie zakłady: R
1
, R
2
, R
3
, które będą
zaopatrywać przedsiębiorstwa S
1
, S
2
, S
3
.
z
min
= 80 · 330 + 20 · 360 + 100 · 320 = 65 600
Politechnika Poznańska
Badania Operacyjne
Ale
80 · 330 + 20 · 370 + 100 · 320 = 65 800
65800 − 65600
65200
· 100% = 0, 03%
S
1
S
2
S
3
R
1
20
100
R
2
80
R
3
Politechnika Poznańska
Badania Operacyjne
Zagadnienie Transportowo-Produkcyjne
Trzech producentów R
1
, R
2
, R
3
zaopatrują trzy przedsiębiorstwa S
1
, S
2
, S
3
w pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
jednostkowe koszty produkcji p
i
, oferowane miesięczne wielkości dostaw A
i
(w tonach) oraz miesięczne zapotrzebowanie przedsiębiorstw B
j
(w
tonach) podaje poniższa tablica.
S
1
S
2
S
3
p
i
A
i
R
1
90
80
30
290
120
R
2
70
60
70
260
80
R
3
40
50
30
310
90
B
j
80
20
100
Politechnika Poznańska
Badania Operacyjne
Zagadnienie Transportowo-Produkcyjne
S
1
S
2
S
3
p
i
A
i
R
1
90
80
30
290
120
R
2
70
60
70
260
80
R
3
40
50
30
310
90
B
j
80
20
100
Dodajemy koszty produkcji p
i
do kosztów transportu ...
Politechnika Poznańska
Badania Operacyjne
S
1
S
2
S
3
A
i
R
1
380
370
320
120
R
2
330
320
330
80
R
3
350
360
340
90
B
j
80
20
100
... i liczymy jak poprzednie zadanie.
Politechnika Poznańska
Badania Operacyjne
S
1
S
2
S
3
A
i
R
1
380
370
320
120
R
2
330
320
330
80
R
3
350
360
340
90
B
j
80
20
100
Ponieważ
X
B
j
= 80 + 20 + 100 = 200 < 290 = 120 + 80 + 90 =
X
A
i
zatem jest to zagadnienie otwarte.
Politechnika Poznańska
Badania Operacyjne
Dołączamy fikcyjnego odbiorcę.
S
1
S
2
S
3
F
A
i
R
1
380
370
320
0
120
R
2
330
320
330
0
80
R
3
350
360
340
0
90
B
j
80
20
100
90
Politechnika Poznańska
Badania Operacyjne
Minimalizacja pustych przebiegów
Zminimalizować puste przebiegi samochodów o ładowności 10T,
przewożących towar pomiędzy ośmioma miastami, które stanowią układ
zamknięty. Ilość samochodów jadących z jednego miasta do drugiego w
jednostce czasu podaje tabela. Odległości pomiędzy miastami podaje
tabela druga.
Politechnika Poznańska
Badania Operacyjne
Współczynniki a
i ,j
-ilość samochodów, które wyjeżdżają z miasta M
i
do
miasta M
j
w jednostce czasu.
a
i ,j
M
1
M
2
M
3
M
4
M
5
M
6
M
7
M
8
M
1
2
3
5
8
3
6
2
1
M
2
3
4
3
3
5
3
2
1
M
3
4
4
5
2
3
1
3
4
M
4
3
3
4
5
3
2
3
4
M
5
3
4
3
5
6
7
5
2
M
6
5
1
3
2
2
3
2
1
M
7
6
1
1
1
2
2
1
2
M
8
4
1
2
1
1
2
6
2
Politechnika Poznańska
Badania Operacyjne
Odległość między miastami.
M
1
M
2
M
3
M
4
M
5
M
6
M
7
M
8
M
1
0
50
80
70
65
150
95
20
M
2
0
30
55
85
30
25
70
M
3
0
25
35
80
35
45
M
4
0
35
70
55
45
M
5
0
75
50
25
M
6
0
125
15
M
7
0
25
M
8
0
Politechnika Poznańska
Badania Operacyjne
Sumujemy, kolumny i wiersze.
a
i ,j
M
1
M
2
M
3
M
4
M
5
M
6
M
7
M
8
P
M
1
2
3
5
8
3
6
2
1
30
M
2
3
4
3
3
5
3
2
1
24
M
3
4
4
5
2
3
1
3
4
26
M
4
3
3
4
5
3
2
3
4
27
M
5
3
4
3
5
6
7
5
2
35
M
6
5
1
3
2
2
3
2
1
19
M
7
6
1
1
1
2
2
1
5
19
M
8
4
1
2
1
1
2
6
2
19
P
30
21
26
27
25
26
24
20
Politechnika Poznańska
Badania Operacyjne
ilość przyjeżdżających - ilość wyjeżdżających samochodów
M
1
:
30 − 30
=
0
M
2
:
24 − 21
=
3
M
3
:
26 − 26
=
0
M
4
:
27 − 27
=
0
M
5
:
35 − 25
=
10
M
6
:
19 − 26
=
−7
M
7
:
19 − 24
=
−5
M
8
:
19 − 20
=
−1
Politechnika Poznańska
Badania Operacyjne
ilość przyjeżdżających - ilość wyjeżdżających samochodów
M
1
:
30 − 30
=
0
M
2
:
24 − 21
=
3
M
3
:
26 − 26
=
0
M
4
:
27 − 27
=
0
M
5
:
35 − 25
=
10
M
6
:
19 − 26
=
−7
M
7
:
19 − 24
=
−5
M
8
:
19 − 20
=
−1
W mieście M
1
mamy 10 samochodów do rozdysponowania a w mieście M
2
brakuje siedmiu.
Politechnika Poznańska
Badania Operacyjne
ilość przyjeżdżających - ilość wyjeżdżających samochodów
M
1
:
30 − 30
=
0
M
2
:
24 − 21
=
3
M
3
:
26 − 26
=
0
M
4
:
27 − 27
=
0
M
5
:
35 − 25
=
10
M
6
:
19 − 26
=
−7
M
7
:
19 − 24
=
−5
M
8
:
19 − 20
=
−1
Aby zbilansować ilości samochodów w poszczególnych miastach,
będziemy je wysyłać z miast M
2
i M
5
do miast M
6
,M
7
oraz M
8
.
Politechnika Poznańska
Badania Operacyjne
Częściowa tabelka zagadnienia transportowego
M
6
M
7
M
8
A
i
M
2
3
M
5
10
B
j
7
5
1
Politechnika Poznańska
Badania Operacyjne
Zagadnienie sprowadzone do Zamkniętego Zagadnienia Transportowego
M
6
M
7
M
8
A
i
M
2
30
25
70
3
M
5
75
50
25
10
B
j
7
5
1
Politechnika Poznańska
Badania Operacyjne
M
6
M
7
M
8
M
2
3
M
5
4
5
1
z
min
= 3 · 30 + 4 · 75 + 3 · 50 + 1 · 25 = 415
Politechnika Poznańska
Badania Operacyjne
Algorytm Transportowy
1
Wyznaczamy rozwiązanie dopuszczalne składające się z n + m − 1
węzłów, węzłów bazowych.
2
Odejmując odpowiednie wartości od kolumn i wierszy zerujemy koszty
w węzłach bazowych.
3
Jeżeli koszty we wszystkich węzłach są nieujemne - znaleziono
rozwiązanie optymalne. W przeciwnym wypadku istnieje przynajmniej
jeden węzeł z ujemnym kosztem.
4
Wybieramy węzeł z najmniejszym ujemnym kosztem. Będzie on
wprowadzony do nowej bazy. Jest on pierwszym węzłem cyklu,
zbudowanego na węzłach bazowych.
5
Najmniejszy przepływ półcyklu ujemnego odejmujemy od każdego
przepływu węzła półcyklu ujemnego i dodajemy do przepływu
każdego węzła półcyklu dodatniego. Wyprowadzamy z bazy jeden z
węzłów w którym wyzerowaliśmy przepływ. powracamy do punktu 2.
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
A
i
M
1
50
40
10
60
M
2
20
30
20
40
M
3
10
20
40
20
B
j
50
40
30
120
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
A
i
M
1
50
50
40
10
10
—
60
M
2
20
—
30
30
20
10
40
M
3
10
—
20
—
40
20
20
B
j
50
40
30
120
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
A
i
M
1
50
50
40
10
10
—
60
M
2
20
—
30
30
20
10
40
M
3
10
—
20
—
40
20
20
B
j
50
40
30
120
3 + 3 − 1 = 5
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
20
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
20
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
20
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
20
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
20
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
20
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
0
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
10
30
20
0
10
-40
10
-30
—
20
-20
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
0
30
20
0
10
-40
10
-30
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
30
10
10
10
—
-20
20
0
—
30
0
30
20
0
10
-40
10
-30
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
0
10
10
-20
—
-20
20
0
—
30
0
30
20
0
10
-40
10
-30
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
20
50
40
0
10
10
-20
—
-20
20
0
—
30
0
30
20
0
10
-40
10
-30
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
-20
-10
-0
-30
50
0
50
40
0
10
10
-20
—
-20
20
-20
—
30
0
30
20
0
10
-40
10
-50
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
”Definicja:”
Cyklem nazywamy taką drogę zamkniętą, w której:
w każdym wierszu i kolumnie występują 0 lub 2 węzły,
węzły połączone są liniami pionowymi lub poziomymi.
Interesują nas cykle w których tylko jeden wierzchołek nie należy bazy.
Politechnika Poznańska
Badania Operacyjne
50
0
50
40
0
10
10
-20
—
20
-20
—
30
0
30
20
0
10
10
-50
+
20
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
50
0
-
20
50
40
0
10
10
-20
—
20
-20
—
30
0
30
20
0
10
10
-50
+
20
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
50
0
-
20
50
40
0
+
20
10
10
-20
—
20
-20
—
30
0
30
20
0
10
10
-50
+
20
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
50
0
-
20
50
40
0
+
20
10
10
-20
—
20
-20
—
30
0
-
20
30
20
0
10
10
-50
+
20
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
50
0
-
20
50
40
0
+
20
10
10
-20
—
20
-20
—
30
0
-
20
30
20
0
+
20
10
10
-50
+
20
—
20
-30
—
40
0
20
Politechnika Poznańska
Badania Operacyjne
50
0
-
20
50
40
0
+
20
10
10
-20
—
20
-20
—
30
0
-
20
30
20
0
+
20
10
10
-50
+
20
—
20
-30
—
40
0
-
20
20
Politechnika Poznańska
Badania Operacyjne
50
0
-
20
50
40
0
+
20
10
10
-20
—
20
-20
—
30
0
-
20
30
20
0
+
20
10
10
-50
+
20
—
20
-30
—
40
0
-
20
20
min{50, 30, 20} = 20
Politechnika Poznańska
Badania Operacyjne
50
0
-20
50
40
0
+20
10
10
-20
—
20
-20
—
30
0
-20
30
20
0
+20
10
10
-50
+20
—
20
-30
—
40
0
-20
20
Politechnika Poznańska
Badania Operacyjne
50
0
-20
30
40
0
+20
30
10
-20
—
20
-20
—
30
0
-20
10
20
0
+20
30
10
-50
+20
20
20
-30
20
40
0
-20
—
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
A
i
M
1
50
—
40
30
10
30
60
M
2
20
30
30
10
20
—
40
M
3
10
20
20
—
40
—
20
B
j
50
40
30
120
Politechnika Poznańska
Badania Operacyjne
P
1
P
2
P
3
A
i
M
1
50
—
40
30
10
30
60
M
2
20
30
30
10
20
—
40
M
3
10
20
20
—
40
—
20
B
j
50
40
30
120
40 · 30 + 10 · 30 + 20 · 30 + 30 · 10 + 10 · 20 = 2600
Politechnika Poznańska
Badania Operacyjne
Definicja
Siecią transportową nazywamy graf zorientowany (P, U), gdzie P jest
zbiorem wierzchołków grafu natomiast U zbiorem łuków (zbiorem par
uporządkowanych), bez pętli, w którym określone są trzy funkcje:
funkcja pojemności:
k : U → R
+
∪ {0}, k((p
i
, p
j
)) = k
i ,j
0, maksymalna
ilość tego, co może być przesłane łukiem (p
i
, p
j
).
funkcja kosztów:
l : U → R, k((p
i
, p
j
)) = k
i ,j
, koszt przesłania jednostki
łukiem, czas przebycia łuku, długość łuku (p
i
, p
j
).
funkcja zapotrzebowania:
d : P → R.
Politechnika Poznańska
Badania Operacyjne
Niech p
i
∈ P wówczas, jeżeli
d (p
i
) > 0:
wówczas, p
i
nazywamy wyjściem, punktem docelowym,
natomiast d (p
i
) nazywamy zapotrzebowaniem w punkcie p
i
.
d (p
i
) = 0:
wówczas, p
i
nazywamy punktem tranzytowym.
d (p
i
) < 0:
wówczas, p
i
nazywamy wejściem, punktem początkowym,
natomiast d (p
i
) nazywamy zapasem w punkcie p
i
.
Politechnika Poznańska
Badania Operacyjne
Zbiór wyjść oznaczamy przez S , zbiór wejść E .
Politechnika Poznańska
Badania Operacyjne
Definicja
Siecią zredukowaną nazywamy sieć która ma tylko jedno wejście p
0
i
jedno wyjście p
n
.
Twierdzenie
Dla każdej sieci transportowej można zdefiniować sieć zredukowaną,
równoważną wyjściowej.
Politechnika Poznańska
Badania Operacyjne
Zagadnienie znajdowania najkrótszej drogi w grafie - algorytm Forda
Łuk będzie reprezentował drogę pomiędzy wierzchołkami grafu. Wartość
nad łukiem (p
i
, p
j
) będzie oznaczała długość drogi pomiędzy
wierzchołkami p
i
oraz p
j
.
Politechnika Poznańska
Badania Operacyjne
Algorytm Forda I
1
Każdemu wierzchołkowi p
i
przyporządkować wartość u
i
następująco:
u
0
= 0, oraz
u
i
= −∞, dla i = 1, 2, 3, . . . , n.
2
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez u
i
− l
i ,j
.
3
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p
i
, p
j
) ∈ U mamy u
i
− u
j
¬ l
i ,j
oraz dla każdego wierzchołka
p
k
i
6= p
0
istnieje co najmniej jeden wierzchołek p
k
j
taki, że
(p
k
j
, p
k
i
) ∈ U oraz
u
k
j
− u
k
i
= l
k
j
,k
i
.
(1)
Politechnika Poznańska
Badania Operacyjne
Algorytm Forda II
4
Zaczynając od p
n
wyznaczyć ciąg
α = [p
n
, p
k
1
, . . . , p
k
l
, p
0
],
który wskazuje najkrótszą drogę, a dla każdego łuku tej drogi
zachodzi (1). Dodając równania (1) odpowiadające łukom z drogi α
otrzymamy
0 − u
n
= l
0,k
l
+ l
k
l
,k
l −1
+ · · · + l
k
1
,n
= l (α).
Najkrótsza droga α ma długość, która wynosi −u
n
.
Politechnika Poznańska
Badania Operacyjne
Redukcja sieci - algorytm Forda
p
1
5
p
2
7
3
p
3
9
p
4
p
5
d (p
1
) < 0, d (p
2
) < 0, d (p
3
) < 0
d (p
4
) > 0, d (p
5
) > 0
Politechnika Poznańska
Badania Operacyjne
Redukcja sieci - algorytm Forda
p
0
0
0
0
p
1
5
p
2
7
3
p
3
9
p
4
p
5
d (p
0
) < 0, d (p
1
) = 0, d (p
2
) = 0, d (p
3
) = 0
Politechnika Poznańska
Badania Operacyjne
Redukcja sieci - algorytm Forda
p
0
0
0
0
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
0
0
d (p
0
) < 0, d (p
1
) = 0, d (p
2
) = 0, d (p
3
) = 0
d (p
6
) > 0, d (p
4
) = 0, d (p
5
) = 0
Politechnika Poznańska
Badania Operacyjne
Zadanie
Znaleźć najkrótszą drogę w grafie, leżeli długości łuków są równe:
l
0,1
= 5
l
1,4
= 5
l
3,5
= 9
l
0,2
= 2
l
2,4
= 7
l
4,6
= 4
l
0,3
= 1
l
2,5
= 3
l
5,6
= 1
Politechnika Poznańska
Badania Operacyjne
Zadanie
p
0
5
2
1
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
4
1
Politechnika Poznańska
Badania Operacyjne
p
1
p
2
p
3
p
4
p
5
u
0
0
0
u
1
−∞
− 5
u
2
−∞
− 2
u
3
−∞
− 1
u
4
−∞
− 10
u
5
−∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
1
p
2
p
3
p
4
p
5
u
0
0
0
u
1
−∞
− 5
u
2
−∞
− 2
u
3
−∞
− 1
u
4
−∞
− 10
u
5
−∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
p
0
5
2
1
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
4
1
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
u
1
−∞
− 5
u
2
−∞
− 2
u
3
−∞
− 1
u
4
−∞
− 10
u
5
−∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
u
1
−∞
− 5
u
2
−∞
− 2
u
3
−∞
− 1
u
4
−∞
− 10
u
5
−∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez
u
i
− l
i ,j
.
(p
0
, p
1
)
(p
0
, p
2
)
(p
0
, p
3
)
u
0
= 0
u
0
= 0
u
0
= 0
u
1
= −∞
u
2
= −∞
u
3
= −∞
l
0,1
= 5
l
0,2
= 2
l
0,3
= 1
u
0
− u
1
> l
0,1
u
0
− u
2
> l
0,2
u
0
− u
3
> l
0,3
0 − (−∞) > 5
0 − (−∞) > 2
0 − (−∞) > 1
TAK
TAK
TAK
u
1
= u
0
− l
0,1
u
2
= u
0
− l
0,2
u
3
= u
0
− l
0,3
u
1
= 0 − 5
u
2
= 0 − 2
u
3
= 0 − 1
u
1
= −5
u
2
= −2
u
3
= −1
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
p
0
5
2
1
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
4
1
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez
u
i
− l
i ,j
.
(p
1
, p
4
)
u
1
= −5
u
4
= −∞
l
1,4
= 5
u
1
− u
4
> l
1,4
0 − (−∞) > 5
TAK
u
4
= u
1
− l
1,4
u
4
= −5 − 5
u
4
= −10
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
p
0
5
2
1
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
4
1
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
u
1
−∞
− 5
− 5
u
2
−∞
− 2
− 2
u
3
−∞
− 1
− 1
u
4
−∞
− ∞
− 10
u
5
−∞
− ∞
− ∞
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez
u
i
− l
i ,j
.
(p
2
, p
4
)
(p
2
, p
5
)
u
2
= −2
u
2
= −2
u
4
= −10
u
5
= −∞
l
2,4
= 7
l
2,5
= 3
u
2
− u
4
> l
2,4
u
2
− u
5
> l
2,5
−2 − (−10) > 7
−2 − (−∞) > 3
TAK
TAK
u
4
= u
2
− l
2,4
u
5
= u
2
− l
2,5
u
4
= −2 − 7
u
5
= −2 − 3
u
4
= −9
u
5
= −5
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
u
5
−∞
− ∞
− ∞
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
u
5
−∞
− ∞
− ∞
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez
u
i
− l
i ,j
.
(p
3
, p
5
)
u
3
= −1
u
5
= −5
l
3,5
= 9
u
3
− u
5
> l
3,5
−1 − (−5) > 9
NIE
p
0
5
2
1
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
4
1
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
− 9
u
5
−∞
− ∞
− ∞
− 5
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
− 9
u
5
−∞
− ∞
− ∞
− 5
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez
u
i
− l
i ,j
.
(p
4
, p
6
)
u
4
= −9
u
6
= −∞
l
4,6
= 4
u
4
− u
6
> l
4,6
−9 − (−∞) > 4
TAK
u
6
= u
4
− l
4,6
u
6
= −9 − 4
u
6
= −13
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
− 9
− 9
u
5
−∞
− ∞
− ∞
− 5
− 5
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
− 9
− 9
u
5
−∞
− ∞
− ∞
− 5
− 5
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
2011-10-29
Zagadnienie znajdowania najkrótszej drogi w grafie
Dla każdego łuku (p
i
, p
j
) ∈ U, dla którego u
i
− u
j
> l
i ,j
zastąpić u
j
przez
u
i
− l
i ,j
.
(p
5
, p
6
)
u
5
= −5
u
6
= −14
l
5,6
= 1
u
5
− u
6
> l
5,6
−5 − (−14) > 1
TAK
u
6
= u
5
− l
5,6
u
6
= −5 − 1
u
6
= −6
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
u
0
0
0
0
0
0
0
0
u
1
−∞
− 5
− 5
− 5
− 5
− 5
− 5
u
2
−∞
− 2
− 2
− 2
− 2
− 2
− 2
u
3
−∞
− 1
− 1
− 1
− 1
− 1
− 1
u
4
−∞
− ∞
− 10
− 9
− 9
− 9
− 9
u
5
−∞
− ∞
− ∞
− 5
− 5
− 5
− 5
u
6
−∞
− ∞
− ∞
− ∞
− ∞
− 13
− 6
Politechnika Poznańska
Badania Operacyjne
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p
i
, p
j
) ∈ U mamy u
i
− u
j
¬ l
i ,j
oraz dla każdego wierzchołka p
k
i
6= p
0
istnieje co najmniej jeden wierzchołek p
k
j
taki, że (p
k
j
, p
k
i
) ∈ U oraz
u
k
j
− u
k
i
= l
k
j
,k
i
.
p
0
, 0
p
1
, −5
5
p
2
, −2
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
Politechnika Poznańska
Badania Operacyjne
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p
i
, p
j
) ∈ U mamy u
i
− u
j
¬ l
i ,j
oraz dla każdego wierzchołka p
k
i
6= p
0
istnieje co najmniej jeden wierzchołek p
k
j
taki, że (p
k
j
, p
k
i
) ∈ U oraz
u
k
j
− u
k
i
= l
k
j
,k
i
.
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(p
i
, p
j
) ∈ U mamy u
i
− u
j
¬ l
i ,j
oraz dla każdego wierzchołka p
k
i
6= p
0
istnieje co najmniej jeden wierzchołek p
k
j
taki, że (p
k
j
, p
k
i
) ∈ U oraz
u
k
j
− u
k
i
= l
k
j
,k
i
.
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Zaczynając od p
n
wyznaczyć ciąg α = [p
n
, p
k
1
, . . . , p
k
l
, p
0
], który wskazuje
najkrótszą drogę, a dla każdego łuku tej drogi zachodzi (1). Dodając
równania (1) odpowiadające łukom z drogi α otrzymamy
0 − u
n
= l
0,k
l
+ l
k
l
,k
l −1
+ · · · + l
k
1
,n
= l (α).
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Zaczynając od p
n
wyznaczyć ciąg α = [p
n
, p
k
1
, . . . , p
k
l
, p
0
], który wskazuje
najkrótszą drogę, a dla każdego łuku tej drogi zachodzi (1). Dodając
równania (1) odpowiadające łukom z drogi α otrzymamy
0 − u
n
= l
0,k
l
+ l
k
l
,k
l −1
+ · · · + l
k
1
,n
= l (α).
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Zaczynając od p
n
wyznaczyć ciąg α = [p
n
, p
k
1
, . . . , p
k
l
, p
0
], który wskazuje
najkrótszą drogę, a dla każdego łuku tej drogi zachodzi (1). Dodając
równania (1) odpowiadające łukom z drogi α otrzymamy
0 − u
n
= l
0,k
l
+ l
k
l
,k
l −1
+ · · · + l
k
1
,n
= l (α).
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Zaczynając od p
n
wyznaczyć ciąg α = [p
n
, p
k
1
, . . . , p
k
l
, p
0
], który wskazuje
najkrótszą drogę, a dla każdego łuku tej drogi zachodzi (1). Dodając
równania (1) odpowiadające łukom z drogi α otrzymamy
0 − u
n
= l
0,k
l
+ l
k
l
,k
l −1
+ · · · + l
k
1
,n
= l (α).
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Zaczynając od p
n
wyznaczyć ciąg α = [p
n
, p
k
1
, . . . , p
k
l
, p
0
], który wskazuje
najkrótszą drogę, a dla każdego łuku tej drogi zachodzi (1). Dodając
równania (1) odpowiadające łukom z drogi α otrzymamy
0 − u
n
= l
0,k
l
+ l
k
l
,k
l −1
+ · · · + l
k
1
,n
= l (α).
p
0
, 0
5
2
1
p
1
, −5
5
p
2
, −2
7
3
p
3
, −1
9
p
4
, −9
p
5
, −5
p
6
, −6
4
1
Politechnika Poznańska
Badania Operacyjne
Zagadnienie znajdowania maksymalnego przepływu w grafie
Wartość nad łukiem (p
i
, p
j
) będzie oznaczała ilość jednostek które można
przesłać w jednostce czasu pomiędzy wierzchołkami p
i
oraz p
j
.
Politechnika Poznańska
Badania Operacyjne
Redukcja sieci - algorytm Forda-Fulkersona
p
1
5
p
2
7
3
p
3
9
p
4
p
5
d (p
1
) < 0, d (p
2
) < 0, d (p
3
) < 0
d (p
4
) > 0, d (p
5
) > 0
Politechnika Poznańska
Badania Operacyjne
Redukcja sieci - algorytm Forda-Fulkersona
p
0
∞
∞
∞
p
1
5
p
2
7
3
p
3
9
p
4
p
5
d (p
0
) < 0, d (p
1
) = 0, d (p
2
) = 0, d (p
3
) = 0
Politechnika Poznańska
Badania Operacyjne
Redukcja sieci - algorytm Forda-Fulkersona
p
0
∞
∞
∞
p
1
5
p
2
7
3
p
3
9
p
4
p
5
p
6
∞
∞
d (p
0
) < 0, d (p
1
) = 0, d (p
2
) = 0, d (p
3
) = 0
d (p
6
) > 0, d (p
4
) = 0, d (p
5
) = 0
Politechnika Poznańska
Badania Operacyjne
Znaleźć maksymalny przepływ w sieci zredukowanej (P, U).
1
Przyporządkować wierzchołkowi p
0
znak (−, ∞).
2
Wziąć pod uwagę dowolny z zaznaczonych już wierzchołków p
i
o
znaku (p
l
, α
i
). Każdemu wierzchołkowi p
j
, który jeszcze nie został
zaznaczony i dla którego r
i ,j
> 0 oraz [p
i
, p
j
] ∈ U przypisać znak
(p
i
, α
j
), gdzie α
j
= min{α
i
, r
i ,j
}. Jeżeli wierzchołkowi p
j
można
przypisać różne znaki, to wybrać dowolną z możliwości (najlepiej tą,
dla której wartość α
j
jest największa). Kontynuować znakowanie aż
do chwili, gdy:
1
otrzymuje wierzchołek p
n
, wówczas przechodzimy do punktu 3;
2
wierzchołek p
n
nie ma znaku i nie można już przyporządkować znaku
żadnemu innemu wierzchołkowi, wówczas przechodzimy do punktu 4.
Politechnika Poznańska
Badania Operacyjne
3
Zmienić przepływ następująco: zaczynając od p
n
wyznaczyć ciąg
σ = [p
0
, . . . , p
n
], w którym każdy wierzchołek jest znakiem dla
następnego. Pomniejszyć o α
n
pojemności rezydualne r
i ,j
łuków
(p
i
, p
j
) ∈ σ oraz powiększyć o α
n
pojemności rezydualne r
j ,i
. Wrócić
do punktu 1.
4
Układ wartości r
i ,j
dla (p
i
, p
j
) ∈ U stanowi przepływ maksymalny.
Politechnika Poznańska
Badania Operacyjne
Znaleźć maksymalny przepływ w sieci poniżej.
p
0
8
9
3
p
1
9
p
2
9
8
p
5
4
p
4
p
3
p
6
9
15
Politechnika Poznańska
Badania Operacyjne
Przyporządkować wierzchołkowi p
0
znak (−, ∞).
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
1
x
.9
2
x
.8
.9
3
x
.15
4
x
.9
5
.4
x
6
x
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
2
x
.8
.9
3
x
.15
4
x
.9
5
.4
x
6
x
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
2
x
.8
.9
3
x
.15
4
x
.9
5
.4
x
6
x
2011-10-29
Zagadnienie znajdowania maksymalnego przepływu w grafie
Wziąć pod uwagę dowolny z zaznaczonych już wierzchołków p
i
o znaku
(p
l
, α
i
). Każdemu wierzchołkowi p
j
, który jeszcze nie został zaznaczony i
dla którego r
i ,j
> 0 oraz [p
i
, p
j
] ∈ U przypisać znak (p
i
, α
j
), gdzie
α
j
= min{α
i
, r
i ,j
}.
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.
8
.9
.3
(−,
∞
)
1
x
.9
(p
0
, 8)
2
x
.8
.9
3
x
.15
4
x
.9
5
.4
x
6
x
min{8, ∞} = 8
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.
9
.3
(−,
∞
)
1
x
.9
(p
0
, 8)
2
x
.8
.9
(p
0
, 9)
3
x
.15
4
x
.9
5
.4
x
6
x
min{9, ∞} = 9
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.
8
.9
(p
0
,
9
)
3
x
.15
(p
2
, 8)
4
x
.9
5
.4
x
6
x
min{8, 9} = 8
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.8
.
9
(p
0
,
9
)
3
x
.15
(p
2
, 8)
4
x
.9
(p
2
, 9)
5
.4
x
6
x
z p
1
: min{9, 8} = 8
z p
2
: min{9, 9} = 9
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.
3
(−,
∞
)
1
x
.9
(p
0
, 8)
2
x
.8
.9
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
x
.9
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
x
min{3, ∞} = 3
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.8
.9
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
x
.
9
(p
2
,
9
)
5
.4
x
(p
0
, 3)
6
x
(p
4
, 9)
z p
3
: min{15, 8} = 8
z p
4
: min{9, 9} = 9
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.8
.9
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
x
.9
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
x
(p
4
,
9
)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.8
.9
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
x
.9
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
x
(p
4
, 9)
[p
0
, p
2
, p
4
, p
6
]
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.8
.9
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
x
.9 0
/
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
[p
0
, p
2
,
p
4
,
p
6
]
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
x
.8
.9 0
/
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
9
x
.9 0
/
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
[p
0
,
p
2
,
p
4
, p
6
]
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.9 0
/
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
9
x
.8
.9 0
/
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
9
x
.9 0
/
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
[
p
0
,
p
2
, p
4
, p
6
]
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
1
x
.9
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
9
x
.0
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
9
x
.0
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
3
x
.15
(p
2
, 8)
4
9
x
.0
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-,
3
x
.15
(p
2
, 8)
4
9
x
.0
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-,
3
x
.15
(p
2
, 8)
-,
4
9
x
.0
(p
2
, 9)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-,
3
x
.15
(p
2
, 8)
-,
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-,
3
x
.15
(p
2
, 8)
-,
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
9
x
(p
4
, 9)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-,
3
x
.15
(p
2
, 8)
-,
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
9
x
(p
4
, 9)
-,
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-, (p
4
, 8)
3
x
.15
(p
2
, 8)
-,
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
9
x
(p
4
, 9)
-,
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-, (p
4
, 8)
3
x
.15
(p
2
, 8)
-, (p
2
, 8)
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
9
x
(p
4
, 9)
-,
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-, (p
4
, 8)
3
x
.15
(p
2
, 8)
-, (p
2
, 8)
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
9
x
(p
4
, 9)
-, (p
3
, 8)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-, (p
4
, 8)
3
x
.15
(p
2
, 8)
-, (p
2
, 8)
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
9
x
(p
4
, 9)
-, (p
3
, 8)
[p
0
, p
1
, p
4
, p
2
, p
3
, p
6
]
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8
.0
(p
0
, 9)
-, (p
4
, 8)
3
x
.15 7
/
(p
2
, 8)
-, (p
2
, 8)
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
8
9
x
(p
4
, 9)
-, (p
3
, 8)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8 0
/
.0
(p
0
, 9)
-, (p
4
, 8)
3
8
x
.15 7
/
(p
2
, 8)
-, (p
2
, 8)
4
9
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
8
9
x
(p
4
, 9)
-, (p
3
, 8)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9
(p
0
, 8)
(p
0
, 8)
2
9
x
.8 0
/
.0 8
/
(p
0
, 9)
-, (p
4
, 8)
3
8
x
.15 7
/
(p
2
, 8)
-, (p
2
, 8)
4
9 1
/
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
8
9
x
(p
4
, 9)
-, (p
3
, 8)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8
.0
.3
(−, ∞)
(−, ∞)
1
x
.9 1
/
(p
0
, 8)
(p
0
, 8)
2
9
x
.8 0
/
.0 8
/
(p
0
, 9)
-, (p
4
, 8)
3
8
x
.15 7
/
(p
2
, 8)
-, (p
2
, 8)
4
8
9 1
/
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
8
9
x
(p
4
, 9)
-, (p
3
, 8)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.8 0
/
.0
.3
(−, ∞)
(−, ∞)
1
8
x
.9 1
/
(p
0
, 8)
(p
0
, 8)
2
9
x
.8 0
/
.0 8
/
(p
0
, 9)
-, (p
4
, 8)
3
8
x
.15 7
/
(p
2
, 8)
-, (p
2
, 8)
4
8
9 1
/
x
.0
(p
2
, 9)
(p
1
, 8)
5
.4
x
(p
0
, 3)
(p
0
, 3)
6
8
9
x
(p
4
, 9)
-, (p
3
, 8)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.0
.0
.1
(−, ∞)
(−, ∞)
1
8
x
.1
-
2
9
x
.0
.8
-
3
8
x
4
.3
(p
5
, 1)
4
8
1
x
.0
-
5
2
.0
x
(p
0
, 2)
6
12
9
x
(p
3
, 1)
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.0
.0
.1
(−, ∞)
(−, ∞)
1
8
x
.1
-
-,
2
9
x
.0
.8
-
-,
3
8
x
4
.3
(p
5
, 1)
-,
4
8
1
x
.0
-
-,
5
2
.0
x
(p
0
, 2)
(p
0
, 1)
6
12
9
x
(p
3
, 1)
-,
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.0
.0
.1
(−, ∞)
(−, ∞)
1
8
x
.1
-
-,-,
2
9
x
.0
.8
-
-,-,
3
8
x
4
.3
(p
5
, 1)
-,-,
4
8
1
x
.0
-
-,-,
5
2
.0
x
(p
0
, 2)
(p
0
, 1)
6
12
9
x
(p
3
, 1)
-,-,
Politechnika Poznańska
Badania Operacyjne
p
0
p
1
p
2
p
3
p
4
p
5
p
6
0
x
.0
.0
.1
(−, ∞)
(−, ∞)
1
8
x
.1
-
-,-,
2
9
x
.0
.8
-
-,-,
3
8
x
4
.3
(p
5
, 1)
-,-,
4
8
1
x
.0
-
-,-,
5
2
.0
x
(p
0
, 2)
(p
0
, 1)
6
12
9
x
(p
3
, 1)
-,-,
9 + 8 + 1 + 1 + 1 = 20
Politechnika Poznańska
Badania Operacyjne
Realizacja maksymalnego przepływu.
p
0
8
9
3
p
1
8
p
2
1
8
p
5
3
p
4
p
3
p
6
9
11
Wyszukiwarka
Podobne podstrony:
wyklad 2 Prezentacja danych PL
BO WYKLAD 03 2
Wyklad I prezentacja
BO I WYKLAD 01 3 2011 02 21
Finanse przedsiębiorstw wykłady (prezentacje + testy) FP testy
Wykłady (z prezentacji) Ronikier
Chemia analityczna wykład prezentacja
MNUM wykład1 prezentacja
Wykłady Prezentacja
Wykład V prezentacja
BO I WYKLAD 01 1 2011 02 21
BO wyklad2
Koordynacja planu z profilem, BUDOWNICTWO - STUDIA, Budownictwo komunikacyjne, Wykłady - prezentacje
Bo wyklady 15 godz. 2012, Zarządzanie, II rok, ćwiczenia(2)
ZIP BO wyklad2
Bo wykłady
AS-1, Inżynieria Środowiska, mgr 2 semestr, Analiza systemowa, wykłady, prezentacje
więcej podobnych podstron