Politechnika Poznańska Badania Operacyjne
Badania
Operacyjne
studia zaoczne
1/213
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.
2/213
Politechnika Poznańska Badania Operacyjne
Programowanie
matematyczne
Programowanie matematyczne Podstawy 3/213
Politechnika Poznańska Badania Operacyjne
Definicja
Na zadanie programowania matematycznego składają się następujące
składniki:
1
funkcja celu (kryterialna) z = f (x1, x2, ..., xn);
2
problem optymalizacyjny (np. znajdz
max lub min funkcji celu);
3
ograniczenia bilansowe postaci
nierówności F (x1, x2, ..., xn) b;
= równania F (x1, x2, ..., xn) = b;
nierówności F (x1, x2, ..., xn) b;
4
ograniczenia brzegowe (np. xi 0, 2, całkowite, = 0 lub 1);
5
liczba (dodatnia) stopni swobody: n - p > 0 gdzie n - ilość
zmiennych, p - ilość ograniczeń bilansowych.
Programowanie matematyczne Podstawy 4/213
Politechnika Poznańska Badania Operacyjne
Definicja
Wektor (x1, x2, ..., xn) gdzie xi " 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.
Programowanie matematyczne Podstawy 5/213
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
n
cjxj max( lub min);
nj=1
aijxj bi
j=1
i = 1, ..., m1 ;
n
aijxj bi
j=1
i = m1 + 1, ..., m2 ;
n
aijxj = bi
j=1
i = m2 + 1, ..., m ;
Programowanie matematyczne Programowanie liniowe 6/213
Politechnika Poznańska Badania Operacyjne
Wyznaczyć obszar ograniczony nierównościami

2y + x 12;
2y - x 2;
Programowanie matematyczne Programowanie liniowe 7/213
Politechnika Poznańska Badania Operacyjne
y = -x + 6
2
2y + x 12

2y + x 12;
2y - x 2
x
y = + 1 - x 2
2y
2
Programowanie matematyczne Programowanie liniowe 8/213
Politechnika Poznańska Badania Operacyjne
y = -x + 6
2
2y + x 12

2y + x 12;
2y - x 2
y - x = 3
(5, 3.5)
x
y = + 1 - x 2
2y
2
y - x = -1.5 y - x = -5
Programowanie matematyczne Programowanie liniowe 9/213
Politechnika Poznańska Badania Operacyjne
y + x = 8.5
y + x = 11
y = -x + 6
2
2y + x 10

2y + x 10;
2y - x 2;
(5, 3.5)
x
y = + 1 - x 2
2y
2
y + x = 1 y + x = 4 y + x = 7
Programowanie matematyczne Programowanie liniowe 10/213
Politechnika Poznańska Badania Operacyjne
y + x = 6 y - x = 5 y - x = 1
y = -x + 6
2
y + x = 8.5
2y - x 2

2y + x 10;
2y - x 2;
(5, 3.5)
x
y = + 1 2y + x 10
2
y - x = -1.5
y + x = 1
Programowanie matematyczne Programowanie liniowe 11/213
Politechnika Poznańska Badania Operacyjne
y + x = 6 y - x = 5 y - x = 1
y = -x + 6
2
y + x = 8.5
2y - x 2

2y + x 10;
2y - x 2;
(5, 3.5)
x
y = + 1 2y + x 10
2
y - x = -1.5
y + x = 1
Programowanie matematyczne Programowanie liniowe 12/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
y -x + 6;
2
x
y + 1;
2
x, y 0;
10y + x max;
2y + x 12;
2y - x 2;
d d
10y + x + 0x1 + 0x2 max;
d
2y + x + x1 = 12;
d
2y - x + x2 = 2;
d d
x1 , x2 0;
Programowanie matematyczne Algorytm simpleks 13/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
y -x + 6;
2
x
y + 1;
2
x, y 0;
10y + x max;
2y + x 12;
2y - x 2;
d d
10y + x + 0x1 + 0x2 max;
d
2y + x + x1 = 12;
d
2y - x + x2 = 2;
d d
x1 , x2 0;
Programowanie matematyczne Algorytm simpleks 14/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
y -x + 6;
2
x
y + 1;
2
x, y 0;
10y + x max;
2y + x 12;
2y - x 2;
d d
10y + x + 0x1 + 0x2 max;
d
2y + x + x1 = 12;
d
2y - x + x2 = 2;
d d
x1 , x2 0;
Programowanie matematyczne Algorytm simpleks 15/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
d
x1 = 12 - (2y + x) ;
d
x2 = 2 - (2y - x) ;
Programowanie matematyczne Algorytm simpleks 16/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
d
x1 = 12 - (2y + x) ;
d
x2 = 2 - (2y - x) ;
max{10, 1} = 10
Programowanie matematyczne Algorytm simpleks 17/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
d
x1 = 12 - (2y + x) ;
d
x2 = 2 - (2y - x) ;
max{10, 1} = 10
12 - 2y 0;
2 - 2y 0;
Programowanie matematyczne Algorytm simpleks 18/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
d
x1 = 12 - (2y + x) ;
d
x2 = 2 - (2y - x) ;
max{10, 1} = 10
6 y;
1 y;
Programowanie matematyczne Algorytm simpleks 19/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
10y + x max;
d
x1 = 12 - (2y + x) ;
d
x2 = 2 - (2y - x) ;
max{10, 1} = 10
1 y
d
10 - 5x2 + 6x max;

d d
x1 = 10 - -x2 + 2x ;

d
x2 x
y = 1 - - ;
2 2
Programowanie matematyczne Algorytm simpleks 20/213
Politechnika Poznańska Badania Operacyjne
Metoda simpleks
d d
40 - 2x2 - 3x1 max;

d d
x1
x = 5 - -x2 + ;
2 2

d d
x2 x1
y = 1 - + ;
4 4
Programowanie matematyczne Algorytm simpleks 21/213
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Ä…dz
nierównościami   dla zadań na minimum oraz
wszystkie zmienne sÄ… nieujemne.
Przykłady postaci standardowej PL
n n
cjxj max; cjxj min;
j=1
nj=1 n
aijxj bi aijxj bi
j=1 j=1
i = 1, ..., m ; i = 1, ..., m ;
x1, ..., xn 0; x1, ..., xn 0;
Programowanie matematyczne Algorytm simpleks 22/213
Politechnika Poznańska Badania Operacyjne
Przykłady postaci standardowej PL
n n
cjxj max; cjxj min;
j=1
nj=1 n
aijxj bi aijxj bi
j=1 j=1
i = 1, ..., m ; i = 1, ..., m ;
x1, ..., xn 0; x1, ..., xn 0;
Przykłady postaci standardowej PL dla zapisu macierzowego
cx max; cx min;
Ax b; Ax b;
x 0; x 0;
Programowanie matematyczne Algorytm simpleks 23/213
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
n
cjxj max(lub min);
cx max(lub min);
j=1
n
aijxj = bi
Ax = b;
j=1
i = 1, ..., m ;
x 0;
x1, ..., xn 0;
Programowanie matematyczne Algorytm simpleks 24/213
Politechnika Poznańska Badania Operacyjne
10y + x max;
2y + x 12;
2y - x 2;
y, x 0
Tabela simleksowa
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 2 1 1 0 12
d
0 x2 2 -1 0 1 2
zj 0 0 0 0 0
cj - zj 10 1 0 0
Programowanie matematyczne Algorytm simpleks 25/213
Politechnika Poznańska Badania Operacyjne
d d
10y + x + 0x1 + 0x2 max;
d d
2y + x + 1x1 + 0x2 = 12;
d d
2y - x + 0x1 + 1x2 = 2;
y, x, x1, x2 0
Tabela simleksowa
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 2 1 1 0 12
d
0 x2 2 -1 0 1 2
zj 0 0 0 0 0
cj - zj 10 1 0 0
Programowanie matematyczne Algorytm simpleks 26/213
Politechnika Poznańska Badania Operacyjne
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 2 1 1 0 12
d
0 x2 2 -1 0 1 2
zj 0 0 0 0 0
cj - zj 10 1 0 0
max(10, 1, 0, 0) = 10 Ò! y
Programowanie matematyczne Algorytm simpleks 27/213
Politechnika Poznańska Badania Operacyjne
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 2 1 1 0 12 12/2
d
0 x2 2 -1 0 1 2 2/2
d
zj 0 0 0 0 0 min(6, 1) = 1 Ò! x2
cj - zj 10 1 0 0
max(10, 1, 0, 0) = 10 Ò! y
Programowanie matematyczne Algorytm simpleks 28/213
Politechnika Poznańska Badania Operacyjne
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 2 1 1 0 12
d
0 x2 2 -1 0 1 2
zj 0 0 0 0 0
cj - zj 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
d
zer, za wyjątkiem elementu leżącego aktualnie w wierszu x2 (stara -
zmienna bazowa).
Programowanie matematyczne Algorytm simpleks 29/213
Politechnika Poznańska Badania Operacyjne
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 2 1 1 0 12
d
0 x2 2 -1 0 1 2
zj 0 0 0 0 0
cj - zj 10 1 0 0
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 0 2 1 -1 10
10 y 1 -1/2 0 1/2 1
zj 10 -5 0 5 10
cj - zj 0 6 0 -5
Programowanie matematyczne Algorytm simpleks 30/213
Politechnika Poznańska Badania Operacyjne
d d
y x x1 x2
cj 10 1 0 0
d
0 x1 0 2 1 -1 10
10 y 1 -1/2 0 1/2 1
zj 10 -5 0 5 10
cj - zj 0 6 0 -5
d d
y x x1 x2
cj 10 1 0 0
1 x 0 1 1/2 -1/2 5
10 y 1 0 1/4 1/4 7/2
zj 10 1 3 2 40
cj - zj 0 0 -3 -2
Programowanie matematyczne Algorytm simpleks 31/213
Politechnika Poznańska Badania Operacyjne
Macierzowy zapis pierwszej tabeli simpleksowej
c
cb xb A I b
zj 0 0
cj - zj c
Programowanie matematyczne Algorytm simpleks 32/213
Politechnika Poznańska Badania Operacyjne
Macierzowy zapis pierwszej tabeli simpleksowej
c
cb xb A I b
zj 0 0
cj - zj c
c = [10 1 0 0]

2 1 0 12
A = , cb = , b =
2 -1 0 2
Programowanie matematyczne Algorytm simpleks 33/213
Politechnika Poznańska Badania Operacyjne
Macierzowy zapis następnych tabeli simpleksowych
c
cb,l xb,l Bl-1A Bl-1 Bl-1b
zj cb,lBl-1A cb,lBl-1 cb,lBl-1b
Gdzie macierz Bl powstaje z poprzedniej macierzy
Bl-1 przez zastÄ…pienie kolumny zmiennej
d d
x1 x2

wychodzÄ…cej z bazy przez kolumnÄ™ zmiennej
1 0
B =
wchodzÄ…cej do bazy. Macierz B w pierwszej tabelce
0 1
jest macierzÄ… jednostkowÄ….
Programowanie matematyczne Algorytm simpleks 34/213
Politechnika Poznańska Badania Operacyjne
d d d
x1 x2 x1 y

1 2 , 1 0
B1 = B2 =
0 2 -1/2 1

1 -1 1/2 0
-1 -1
B1 = , B2 =
0 1/2 1/4 1
y x

0 2
-1
B1 A =
1 -1/2
cb,lBl-1A = [0 0], cb,lBl-1 = [0 0]
Bl-1b = [10 1]T
Programowanie matematyczne Algorytm simpleks 35/213
Politechnika Poznańska Badania Operacyjne
Analiza wrażliwości - zmiana współczynników funkcji celu
d d
y x x1 x2
cj 10+´ 1 0 0
1 x 0 1 1/2 -1/2 5
10+´ y 1 0 1/4 1/4 7/2
zj 10+´ 1 3+´/4 2+´/4 40+7´/2
cj - zj 0 0 -3-´/4 -2-´/4
´ ´
-3 - 0, -2 - 0
4 4
-12 ´, -8 ´
´ -8
Programowanie matematyczne Analiza wrażliwości 36/213
Politechnika Poznańska Badania Operacyjne
Analiza wrażliwości - zmiana wartości wyrazów wolnych

12 + µ1
b =
2
-1
Bostatnib 0

µ1
1/2 0 12 + µ1 6 +
-1
2
0 Bostatnib = =
µ1
1/4 1 2 5 +
4
µ1 -12
Programowanie matematyczne Analiza wrażliwości 37/213
Politechnika Poznańska Badania Operacyjne
Programowanie całkowitoliczbowe
y - x min
2y + x 10;
2y - x 2;
(5, 3.5)
x, y " N
y - x = -1.5
Programowanie matematyczne Analiza wrażliwości 38/213
Politechnika Poznańska Badania Operacyjne
Programowanie całkowitoliczbowe
y - x min
7
2y + x 10;
Ò! (5, )
2y - x 2;
2
x, y " N
Programowanie matematyczne Analiza wrażliwości 39/213
Politechnika Poznańska Badania Operacyjne
Programowanie całkowitoliczbowe
y - x min
7
2y + x 10;
Ò! (5, )
2y - x 2;
2
x, y " N
7 7
y y
2 2
y - x min y - x min
2y + x 10; 2y + x 10;
2y - x 2; 2y - x 2;
y 4; y 3;
x, y " N x, y " N
Programowanie matematyczne Analiza wrażliwości 40/213
Politechnika Poznańska Badania Operacyjne
Reguła tworzenia zadania dualnego
zadanie pierwotne
zadanie dualne
n m
cjxj max; bjyj min;
i=1
nj=1 m
aijxj bi aijyi cj
j=1 i=1
j = 1, 2, ..., n ;
i = 1, 2, ..., m ;
yi 0
xj 0
i = 1, 2, ..., m ;
j = 1, 2, ..., n ;
Programowanie matematyczne Analiza wrażliwości 41/213
Politechnika Poznańska Badania Operacyjne
Reguła tworzenia zadania dualnego - przekład
zadanie dualne
zadanie pierwotne
13y1 + 11y2 min;
7x1 + 8x2 - 9x3 max;
2y1 + 5y2 7;
2x1 + 4x2 + 3x3 13;
4y1 - 3y2 8;
5x1 - 3x2 - 6x3 11;
3y1 - 6y2 -9;
x1, x2, x3 0;
y1, y2 0;
Programowanie matematyczne Analiza wrażliwości 42/213
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.
Programowanie matematyczne Zagadnienie dualne 43/213
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ą.
Programowanie matematyczne Zagadnienie dualne 44/213
Politechnika Poznańska Badania Operacyjne
Zagadnienia transportowe
Zagadnienia transportowe 45/213
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 ci,j od każdego (i-tego)
dostawcy do każdego (j-tego) odbiorcy, oraz zapotrzebowanie odbiorców
Bj i zapasy dostawców Ai.
Zagadnienia transportowe 46/213
Politechnika Poznańska Badania Operacyjne
Ogólny model
O1 O2 . . . ON Ai
D1 c1,1 c1,2 . . . c1,N A1
D2 c2,1 c2,2 . . . c2,N A2
. . . . . . . . . . . . . . . . . .
DR cR,1 cR,2 . . . cR,N AR
Bj B1 B2 . . . BN
Zagadnienia transportowe 47/213
Politechnika Poznańska Badania Operacyjne
Ogólny model
W przypadku gdy
R N

Ai = Bj
i=1 j=1
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.
Zagadnienia transportowe 48/213
Politechnika Poznańska Badania Operacyjne
Model matematyczny zamkniętego zagadnienia transportowego
D1 : x1,1 + · · · + x1,N = A1; O1 : x1,1 + · · · + xR,1 = B1;
. . . . . . ; . . . . . . ;
DR : xR,1 + · · · + xR,N = AR; ON : x1,N + · · · + xR,N = BN;
c1,1x1,1 + · · · + c1,Nx1,N + · · · + cR,1xR,1 + · · · + cR,NxR,N min
Zagadnienia transportowe 49/213
Politechnika Poznańska Badania Operacyjne
Zamknięte Zagadnienie Transportowe - Zadanie
Trzy magazyny M1, M2, M3 zaopatrują trzy przedsiębiorstwa P1, P2, P3 w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw Ai (w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw Bj (w tonach) podaje poniższa tablica.
P1 P2 P3 Ai
M1 90 80 30 90
M2 70 60 70 60
M3 40 50 30 50
Bj 80 20 100 200

Bj = 80 + 20 + 100 = 200 = 90 + 60 + 50 = Ai
Zatem jest to zagadnienie zamknięte.
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 50/213
Politechnika Poznańska Badania Operacyjne
Model matematyczny zadania
P1 P2 P3 Aj
M1 90 80 30 90
M2 70 60 70 60
M3 40 50 30 50
Bi 80 20 100 200
Oznaczmy przez xi,j ilość towaru który zostanie przesłany od i-tego
dostawcy do j-tego odbiorcy. Wówczas możemy wypisać
ograniczenia dostawców ograniczenia odbiorców
x1,1 + x1,2 + x1,3 = 90 x1,1 + x2,1 + x3,1 = 80
Funkcja celu:
x2,1 + x2,2 + x2,3 = 60 x1,2 + x2,2 + x3,2 = 20
x3,1 + x3,2 + x3,3 = 50 x1,3 + x2,3 + x3,3 = 100
zminimalizować funkcję
90x1,1 + 80x1,2 + 30x1,3 + 70x2,1 + 60x2,2 + 70x2,3 + 40x3,1 + 50x3,2 + 30x3,3
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 51/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego
Wyjściowa tablica
P1 P2 P3 Aj
M1 90 80 30 90
M2 70 60 70 60
M3 40 50 30 50
Bi 80 20 100 200
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 52/213
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. (P1, M1);
2
do komórki w której jesteśmy (Pm, Mn) wpisujemy M = min{An, Bm};
3
od wartości An oraz Bm odejmujemy M;
4
jeżeli An = 0 wówczas przesuwamy się o jedną komórkę w dół, w
przeciwnym wypadku (Bm = 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 Ai oraz wierszu Bj. Jeżeli tak się nie
stało szukamy błędu :-).
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 53/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego
min{80, 90} = 80
P1 P2 P3
M1 80  
90
10
M2 60
M3 50
  20 100
80
0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 54/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego
min{10, 20} = 10
P1 P2 P3
M1 80 10  
90
  0
10
M2 60
M3 50
    100
80 20
0 10
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 55/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego
min{10, 60} = 10
P1 P2 P3
M1 80 10  
90
  0
10
M2 10   50
60
M3 50
    100
80 20
0  
10
0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 56/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego
min{50, 100} = 50
P1 P2 P3
M1 80 10  
90
  0
10
M2 10 50     0
60
50
M3 50
     
80 20 100
0   50
10
0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 57/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego
min{50, 50} = 50
P1 P2 P3
M1 80 10  
90
  0
10
M2 10 50     0
60
50
M3 50   0
50
     
80 20 100
0    
10 50
0 0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 58/213
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
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 59/213
Politechnika Poznańska Badania Operacyjne
Metoda minimalnego elementu macierzy
Metoda ta polega na przetworzeniu poniższej tabeli
P1 P2 P3
M1 90 80 30
M2 70 60 70
M3 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.
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 60/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 P1 P2 P3
M1 90 80 30 M1 60 50 0

M2 70 60 70 M2 10 0 10
M3 40 50 30 M3 10 20 0
min{90, 80, 30} = 30 min{60, 10, 10} = 10
min{70, 60, 70} = 60 min{20, 0, 20} = 0
min{40, 50, 30} = 30 min{0, 10, 0} = 0
P1 P2 P3
M1 50 50 0
M2 0 0 10
M3 0 20 0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 61/213
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.
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 62/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 Aj
M1 x x 90
M2 x 60
M3 x 50
Bi 80 20 100
Przeanalizujmy zatem dokładnie nasze zadanie. Warto rozpocząć algorytm
od wierszy i kolumn w których jest tylko jedno puste miejsce.
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 63/213
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
(P3, M1)) : min{100, 90} = 90; w drugiej kolumnie (element (P2, M2))
natomiast: min{20, 60} = 20. Zatem nowa tabelka będzie wyglądała
następująco:
P1 P2 P3 Aj
M1 x x 90 0
M2 20 x 40
M3 x 50
Bi 80 0 10
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 64/213
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:
P1 P2 P3 Aj
M1 x x 90 0
M2 40 20 x 0
M3 x 10 40
Bi 40 0 0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 65/213
Politechnika Poznańska Badania Operacyjne
Ostatnia tabela wygląda następująco:
P1 P2 P3 Aj
M1 x x 90 0
M2 40 20 x 0
M3 40 x 10 0
Bi 0 0 0
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 66/213
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ć
zmin = 90 · 30 + 40 · 70 + 20 · 60 + 40 · 40 + 10 · 30 =
2700 + 2800 + 1200 + 1600 + 300 = 8600.
Zagadnienia transportowe Zamknięte Zagadnienie Transportowe 67/213
Politechnika Poznańska Badania Operacyjne
Zamknięte Zagadnienie Transportowe - blokada trasy
Trzy magazyny M1, M2, M3 zaopatrują trzy przedsiębiorstwa P1, P2, P3 w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw Ai (w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw Bj (w tonach) podaje poniższa tablica. Z
niewyjaśnionych powodów nie można z magazynu M2 zaopatrywać
przedsiębiorstwa P2.
P1 P2 P3 Ai
M1 90 80 30 90
M2 70 x 70 60
M3 40 50 30 50
Bj 80 20 100 200
x "
Zagadnienia transportowe Blokada trasy 68/213
Politechnika Poznańska Badania Operacyjne
Zamknięte Zagadnienie Transportowe - blokada trasy
Trzy magazyny M1, M2, M3 zaopatrują trzy przedsiębiorstwa P1, P2, P3 w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw Ai (w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw Bj (w tonach) podaje poniższa tablica. Z
niewyjaśnionych powodów wielkość dostaw z magazynu M2 do
przedsiębiorstwa P2 może być równa maksymalnie 5 jednostek a koszt
przewozu to 60 (zł/t).
P1 P2 P3 Ai
M1 90 80 30 90
M2 70 60(max 5) 70 60
M3 40 50 30 50
Bj 80 20 100 200
Zagadnienia transportowe Blokada trasy 69/213
Politechnika Poznańska Badania Operacyjne
Zamknięte Zagadnienie Transportowe - blokada trasy
Trzy magazyny M1, M2, M3 zaopatrują trzy przedsiębiorstwa P1, P2, P3 w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw Ai (w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw Bj (w tonach) podaje poniższa tablica. Z
niewyjaśnionych powodów wielkość dostaw z magazynu M2 do
przedsiębiorstwa P2 może być równa maksymalnie 5 jednostek a koszt
przewozu to 60 (zł/t).
I I
P1 P2 P2I P3 Ai
M1 90 80 80 30 90
M2 70 60 x 70 60
M3 40 50 50 30 50
Bj 80 5 15 100 200
x "
Zagadnienia transportowe Blokada trasy 70/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie przydziału
Trzy karetki pogotowia mające bazę w miastach M1, M2, M3  obsługują
trzy miejscowości P1, P2, P3. Znalez
ć najniższe koszty transportu
medycznego. Koszty transportu przedstawia tabelka.
P1 P2 P3 Ai
M1 90 80 30
M2 70 60 70
M3 40 50 30
Bj
Zagadnienia transportowe Zagadnienie przydziału 71/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie przydziału
Trzy karetki pogotowia mające bazę w miastach M1, M2, M3  obsługują
trzy miejscowości P1, P2, P3. Znalez
ć najniższe koszty transportu
medycznego. Koszty transportu przedstawia tabelka.
P1 P2 P3 Ai
M1 90 80 30 1
M2 70 60 70 1
M3 40 50 30 1
Bj 1 1 1
Zagadnienia transportowe Zagadnienie przydziału 72/213
Politechnika Poznańska Badania Operacyjne
Przypadek wielu rozwiązań
P1 P2 P3 Ai
M1 90 30 10 30
M2 40 70 50 20
Bj 10 10 30
Zagadnienia transportowe Przypadek wielu rozwiązań 73/213
Politechnika Poznańska Badania Operacyjne
Przypadek wielu rozwiązań
P1 P2 P3 Ai
M1 90 30 10 30
M2 40 70 50 20
Bj 10 10 30
Możliwe rozwiązania optymalne
R1 P1 P2 P3 R2 P1 P2 P3
M1   30 M1  10 20
M2 10 10  M2 10  10
10 · 40 + 10 · 70 + 30 · 10 = 10 · 40 + 10 · 30 + 20 · 10 + 10 · 50 = 1400
Zagadnienia transportowe Przypadek wielu rozwiązań 74/213
Politechnika Poznańska Badania Operacyjne
Możliwe rozwiązania optymalne
R1 P1 P2 P3 R2 P1 P2 P3
M1   30 M1  10 20
M2 10 10  M2 10  10
Ogólne rozwiązanie optymalne
Ä… · R1 + ² · R2
Ä… + ² = 1
Zagadnienia transportowe Przypadek wielu rozwiązań 75/213
Politechnika Poznańska Badania Operacyjne
Możliwe rozwiązania optymalne
R1 P1 P2 P3 R2 P1 P2 P3
M1   30 M1  10 20
M2 10 10  M2 10  10
Ogólne rozwiązanie optymalne
Ä… · R1 + ² · R2
Ä… + ² = 1
R P1 P2 P3
M1  10² 30Ä… + 20²
M2 10Ä… + 10² 10Ä… 10²
Ä… " [0, 1]
Zagadnienia transportowe Przypadek wielu rozwiązań 76/213
Politechnika Poznańska Badania Operacyjne
Ogólne rozwiązanie optymalne
R P1 P2 P3
M1  10 - 10Ä… 20 + 10Ä…
M2 10 10Ä… 10 - 10Ä…
Ä… " [0, 1]
Zagadnienia transportowe Przypadek wielu rozwiązań 77/213
Politechnika Poznańska Badania Operacyjne
Otwarte Zagadnienie Transportowe
Trzy magazyny M1, M2, M3 zaopatrują trzy przedsiębiorstwa P1, P2, P3 w
pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
oferowane miesięczne wielkości dostaw Ai (w tonach) oraz miesięczne
zapotrzebowanie przedsiębiorstw Bj (w tonach) podaje poniższa tablica.
P1 P2 P3 Ai
M1 90 80 30 90
M2 70 60 70 60
M3 40 50 30 80
Bj 80 20 100

Bj = 80 + 20 + 100 = 200 < 230 = 90 + 60 + 80 = Ai
Zatem jest to zagadnienie otwarte.
Zagadnienia transportowe Otwarte Zagadnienie Transportowe 78/213
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

Ai - Bj. 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ć.
Zagadnienia transportowe Otwarte Zagadnienie Transportowe 79/213
Politechnika Poznańska Badania Operacyjne
Tablica naszego zadania
P1 P2 P3 F Ai
M1 90 80 30 0 90
M2 70 60 70 0 60
M3 40 50 30 0 80
Bj 80 20 100 30 230
Zagadnienia transportowe Otwarte Zagadnienie Transportowe 80/213
Politechnika Poznańska Badania Operacyjne
Metoda kąta północno-zachodniego doprowadzi nas do następującej
tabelki,
P1 P2 P3 F Ai
M1 80 10 0
M2 10 50 0
M3 50 30 0
Bj 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.
Zagadnienia transportowe Otwarte Zagadnienie Transportowe 81/213
Politechnika Poznańska Badania Operacyjne
Metoda minimalnego elementu macierzy doprowadzi nas do tabeli
P1 P2 P3 F
M1 90
M2 20 10 30
M3 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.
Zagadnienia transportowe Otwarte Zagadnienie Transportowe 82/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie Lokalizacji Produkcji
Projektowana jest budowa trzech zakładów: R1, R2, R3, które będą
zaopatrywały trzy przedsiębiorstwa S1, S2, S3 w pewien surowiec.
Prognozowane jednostkowe koszty transportu (w zł/t), jednostkowe koszty
produkcji pi, planowane miesięczne wielkości dostaw Ai (w tonach) oraz
miesięczne zapotrzebowanie przedsiębiorstw Bj (w tonach) podaje
poniższa tablica.
S1 S2 S3 pi Ai
R1 90 80 30 290 120
R2 70 60 70 260 80
R3 40 50 30 310 90
Bj 80 20 100
Zagadnienia transportowe Zagadnienie lokalizacji produkcji 83/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie Lokalizacji Produkcji
S1 S2 S3 Ai
R1 90 + 290 80 + 290 30 + 290 120
R2 70 + 260 60 + 260 70 + 260 80
R3 40 + 310 50 + 310 30 + 310 90
Bj 80 20 100
Zagadnienia transportowe Zagadnienie lokalizacji produkcji 84/213
Politechnika Poznańska Badania Operacyjne
S1 S2 S3
R1 100
R2 80
R3 20
Zatem powinniśmy wybudować wszystkie zakłady: R1, R2, R3, które będą
zaopatrywać przedsiębiorstwa S1, S2, S3.
zmin = 80 · 330 + 20 · 360 + 100 · 320 = 65 600
Zagadnienia transportowe Zagadnienie lokalizacji produkcji 85/213
Politechnika Poznańska Badania Operacyjne
Ale
80 · 330 + 20 · 370 + 100 · 320 = 65 800
65800 - 65600
· 100% = 0, 03%
65200
S1 S2 S3
R1 20 100
R2 80
R3
Zagadnienia transportowe Zagadnienie lokalizacji produkcji 86/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie Transportowo-Produkcyjne
Trzech producentów R1, R2, R3 zaopatrują trzy przedsiębiorstwa S1, S2, S3
w pewien surowiec do produkcji. Jednostkowe koszty transportu (w zł/t),
jednostkowe koszty produkcji pi, oferowane miesięczne wielkości dostaw Ai
(w tonach) oraz miesięczne zapotrzebowanie przedsiębiorstw Bj (w
tonach) podaje poniższa tablica.
S1 S2 S3 pi Ai
R1 90 80 30 290 120
R2 70 60 70 260 80
R3 40 50 30 310 90
Bj 80 20 100
Zagadnienia transportowe Zagadnienie Transportowo-Produkcyjne 87/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie Transportowo-Produkcyjne
S1 S2 S3 pi Ai
R1 90 80 30 290 120
R2 70 60 70 260 80
R3 40 50 30 310 90
Bj 80 20 100
Dodajemy koszty produkcji pi do kosztów transportu ...
Zagadnienia transportowe Zagadnienie Transportowo-Produkcyjne 88/213
Politechnika Poznańska Badania Operacyjne
S1 S2 S3 Ai
R1 380 370 320 120
R2 330 320 330 80
R3 350 360 340 90
Bj 80 20 100
... i liczymy jak poprzednie zadanie.
Zagadnienia transportowe Zagadnienie Transportowo-Produkcyjne 89/213
Politechnika Poznańska Badania Operacyjne
S1 S2 S3 Ai
R1 380 370 320 120
R2 330 320 330 80
R3 350 360 340 90
Bj 80 20 100
Ponieważ

Bj = 80 + 20 + 100 = 200 < 290 = 120 + 80 + 90 = Ai
zatem jest to zagadnienie otwarte.
Zagadnienia transportowe Zagadnienie Transportowo-Produkcyjne 90/213
Politechnika Poznańska Badania Operacyjne
Dołączamy fikcyjnego odbiorcę.
S1 S2 S3 F Ai
R1 380 370 320 0 120
R2 330 320 330 0 80
R3 350 360 340 0 90
Bj 80 20 100 90
Zagadnienia transportowe Zagadnienie Transportowo-Produkcyjne 91/213
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.
Zagadnienia transportowe Minimalizacja pustych przebiegów 92/213
Politechnika Poznańska Badania Operacyjne
Współczynniki ai,j-ilość samochodów, które wyjeżdżają z miasta Mi do
miasta Mj w jednostce czasu.
ai,j M1 M2 M3 M4 M5 M6 M7 M8
M1 2 3 5 8 3 6 2 1
M2 3 4 3 3 5 3 2 1
M3 4 4 5 2 3 1 3 4
M4 3 3 4 5 3 2 3 4
M5 3 4 3 5 6 7 5 2
M6 5 1 3 2 2 3 2 1
M7 6 1 1 1 2 2 1 2
M8 4 1 2 1 1 2 6 2
Zagadnienia transportowe Minimalizacja pustych przebiegów 93/213
Politechnika Poznańska Badania Operacyjne
Odległość między miastami.
M1 M2 M3 M4 M5 M6 M7 M8
M1 0 50 80 70 65 150 95 20
M2 0 30 55 85 30 25 70
M3 0 25 35 80 35 45
M4 0 35 70 55 45
M5 0 75 50 25
M6 0 125 15
M7 0 25
M8 0
Zagadnienia transportowe Minimalizacja pustych przebiegów 94/213
Politechnika Poznańska Badania Operacyjne
Sumujemy, kolumny i wiersze.

ai,j M1 M2 M3 M4 M5 M6 M7 M8
M1 2 3 5 8 3 6 2 1 30
M2 3 4 3 3 5 3 2 1 24
M3 4 4 5 2 3 1 3 4 26
M4 3 3 4 5 3 2 3 4 27
M5 3 4 3 5 6 7 5 2 35
M6 5 1 3 2 2 3 2 1 19
M7 6 1 1 1 2 2 1 5 19
M8 4 1 2 1 1 2 6 2 19

30 21 26 27 25 26 24 20
Zagadnienia transportowe Minimalizacja pustych przebiegów 95/213
Politechnika Poznańska Badania Operacyjne
ilość przyjeżdżających - ilość wyjeżdżających samochodów
M1 : 30 - 30 = 0 M2 : 24 - 21 = 3
M3 : 26 - 26 = 0 M4 : 27 - 27 = 0
M5 : 35 - 25 = 10 M6 : 19 - 26 = -7
M7 : 19 - 24 = -5 M8 : 19 - 20 = -1
Zagadnienia transportowe Minimalizacja pustych przebiegów 96/213
Politechnika Poznańska Badania Operacyjne
ilość przyjeżdżających - ilość wyjeżdżających samochodów
M1 : 30 - 30 = 0 M2 : 24 - 21 = 3
M3 : 26 - 26 = 0 M4 : 27 - 27 = 0
M5 : 35 - 25 = 10 M6 : 19 - 26 = -7
M7 : 19 - 24 = -5 M8 : 19 - 20 = -1
W mieście M1 mamy 10 samochodów do rozdysponowania a w mieście M2
brakuje siedmiu.
Zagadnienia transportowe Minimalizacja pustych przebiegów 97/213
Politechnika Poznańska Badania Operacyjne
ilość przyjeżdżających - ilość wyjeżdżających samochodów
M1 : 30 - 30 = 0 M2 : 24 - 21 = 3
M3 : 26 - 26 = 0 M4 : 27 - 27 = 0
M5 : 35 - 25 = 10 M6 : 19 - 26 = -7
M7 : 19 - 24 = -5 M8 : 19 - 20 = -1
Aby zbilansować ilości samochodów w poszczególnych miastach,
będziemy je wysyłać z miast M2 i M5 do miast M6,M7 oraz M8.
Zagadnienia transportowe Minimalizacja pustych przebiegów 98/213
Politechnika Poznańska Badania Operacyjne
Częściowa tabelka zagadnienia transportowego
M6 M7 M8 Ai
M2 3
M5 10
Bj 7 5 1
Zagadnienia transportowe Minimalizacja pustych przebiegów 99/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie sprowadzone do Zamkniętego Zagadnienia Transportowego
M6 M7 M8 Ai
M2 30 25 70 3
M5 75 50 25 10
Bj 7 5 1
Zagadnienia transportowe Minimalizacja pustych przebiegów 100/213
Politechnika Poznańska Badania Operacyjne
M6 M7 M8
M2 3
M5 4 5 1
zmin = 3 · 30 + 4 · 75 + 3 · 50 + 1 · 25 = 415
Zagadnienia transportowe Minimalizacja pustych przebiegów 101/213
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.
Zagadnienia transportowe Algorytm Transportowy 102/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 Ai
M1 50 40 10 60
M2 20 30 20 40
M3 10 20 40 20
Bj 50 40 30 120
Zagadnienia transportowe Algorytm Transportowy 103/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 Ai
M1 50 40 10 60

50 10
M2 20 30 20 40

30 10
M3 10 20 40 20
 
20
Bj 50 40 30 120
Zagadnienia transportowe Algorytm Transportowy 104/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 Ai
M1 50 40 10 60

50 10
M2 20 30 20 40

30 10
M3 10 20 40 20
 
20
Bj 50 40 30 120
3 + 3 - 1 = 5
Zagadnienia transportowe Algorytm Transportowy 105/213
Politechnika Poznańska Badania Operacyjne
50 40 10
50 10 
20 30 20
 30 10
10 20 40
  20
Zagadnienia transportowe Algorytm Transportowy 106/213
Politechnika Poznańska Badania Operacyjne
50 40 10
50 10 
20 30 20
 30 10
-40 10 20 40
  20
Zagadnienia transportowe Algorytm Transportowy 107/213
Politechnika Poznańska Badania Operacyjne
50 40 10
50 10 
20 30 20
 30 10
-40 10 -30 20 -20 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 108/213
Politechnika Poznańska Badania Operacyjne
-0
50 40 10
50 10 
20 30 20
 30 10
-40 10 -30 20 -20 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 109/213
Politechnika Poznańska Badania Operacyjne
-0
50 40 10 10
50 10 
20 30 20 20
 30 10
-40 10 -30 20 -20 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 110/213
Politechnika Poznańska Badania Operacyjne
-0
50 40 10 10
50 10 
-20 20 30 20 20
 30 10
-40 10 -30 20 -20 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 111/213
Politechnika Poznańska Badania Operacyjne
-0
50 40 10 10
50 10 
-20 20 0 30 10 20 0
 30 10
-40 10 -30 20 -20 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 112/213
Politechnika Poznańska Badania Operacyjne
-10 -0
50 40 10 10
50 10 
-20 20 0 30 10 20 0
 30 10
-40 10 -30 20 -20 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 113/213
Politechnika Poznańska Badania Operacyjne
-10 -0
50 40 30 10 10
50 10 
-20 20 0 30 0 20 0
 30 10
-40 10 -30 20 -30 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 114/213
Politechnika Poznańska Badania Operacyjne
-10 -0
-30 50 40 30 10 10
50 10 
-20 20 0 30 0 20 0
 30 10
-40 10 -30 20 -30 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 115/213
Politechnika Poznańska Badania Operacyjne
-10 -0
-30 50 20 40 0 10 -20
50 10 
-20 20 0 30 0 20 0
 30 10
-40 10 -30 20 -30 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 116/213
Politechnika Poznańska Badania Operacyjne
-20 -10 -0
-30 50 20 40 0 10 -20
50 10 
-20 20 0 30 0 20 0
 30 10
-40 10 -30 20 -30 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 117/213
Politechnika Poznańska Badania Operacyjne
-20 -10 -0
-30 50 0 40 0 10 -20
50 10 
-20 20 -20 30 0 20 0
 30 10
-40 10 -50 20 -30 40 0
  20
Zagadnienia transportowe Algorytm Transportowy 118/213
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.
Zagadnienia transportowe Algorytm Transportowy 119/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
50 10 
20 -20 30 0 20 0
 30 10
10 -50 20 -30 40 0
+   20
Zagadnienia transportowe Algorytm Transportowy 120/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
- 50 10 
20 -20 30 0 20 0
 30 10
10 -50 20 -30 40 0
+   20
Zagadnienia transportowe Algorytm Transportowy 121/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
- 50 + 10 
20 -20 30 0 20 0
 30 10
10 -50 20 -30 40 0
+   20
Zagadnienia transportowe Algorytm Transportowy 122/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
- 50 + 10 
20 -20 30 0 20 0
 - 30 10
10 -50 20 -30 40 0
+   20
Zagadnienia transportowe Algorytm Transportowy 123/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
- 50 + 10 
20 -20 30 0 20 0
 - 30 + 10
10 -50 20 -30 40 0
+   20
Zagadnienia transportowe Algorytm Transportowy 124/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
- 50 + 10 
20 -20 30 0 20 0
 - 30 + 10
10 -50 20 -30 40 0
+   - 20
Zagadnienia transportowe Algorytm Transportowy 125/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
- 50 + 10 
20 -20 30 0 20 0
 - 30 + 10
10 -50 20 -30 40 0
+   - 20
min{50, 30, 20} = 20
Zagadnienia transportowe Algorytm Transportowy 126/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
-20 50 +20 10 
20 -20 30 0 20 0
 -20 30 +20 10
10 -50 20 -30 40 0
+20   -20 20
Zagadnienia transportowe Algorytm Transportowy 127/213
Politechnika Poznańska Badania Operacyjne
50 0 40 0 10 -20
-20 30 +20 30 
20 -20 30 0 20 0
 -20 10 +20 30
10 -50 20 -30 40 0
[phone] 
Zagadnienia transportowe Algorytm Transportowy 128/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 Ai
M1 50 40 10 60
 30 30
M2 20 30 20 40
30 10 
M3 10 20 40 20
20  
Bj 50 40 30 120
Zagadnienia transportowe Algorytm Transportowy 129/213
Politechnika Poznańska Badania Operacyjne
P1 P2 P3 Ai
M1 50 40 10 60
 30 30
M2 20 30 20 40
30 10 
M3 10 20 40 20
20  
Bj 50 40 30 120
40 · 30 + 10 · 30 + 20 · 30 + 30 · 10 + 10 · 20 = 2600
Zagadnienia transportowe Algorytm Transportowy 130/213
Politechnika Poznańska Badania Operacyjne
Sieci
Sieci transportowe 131/213
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((pi, pj)) = ki,j 0, maksymalna
ilość tego, co może być przesłane łukiem (pi, pj).
funkcja kosztów: l : U R, k((pi, pj)) = ki,j, koszt przesłania jednostki
łukiem, czas przebycia łuku, długość łuku (pi, pj).
funkcja zapotrzebowania: d : P R.
Sieci transportowe 132/213
Politechnika Poznańska Badania Operacyjne
Niech pi " P wówczas, jeżeli
d(pi) > 0: wówczas, pi nazywamy wyjściem, punktem docelowym,
natomiast d(pi) nazywamy zapotrzebowaniem w punkcie pi.
d(pi) = 0: wówczas, pi nazywamy punktem tranzytowym.
d(pi) < 0: wówczas, pi nazywamy wejściem, punktem początkowym,
natomiast d(pi) nazywamy zapasem w punkcie pi.
Sieci transportowe 133/213
Politechnika Poznańska Badania Operacyjne
Zbiór wyjść oznaczamy przez S, zbiór wejść E.
Sieci transportowe 134/213
Politechnika Poznańska Badania Operacyjne
Definicja
Siecią zredukowaną nazywamy sieć która ma tylko jedno wejście p0 i
jedno wyjście pn.
Twierdzenie
Dla każdej sieci transportowej można zdefiniować sieć zredukowaną,
równoważną wyjściowej.
Sieci transportowe 135/213
Politechnika Poznańska Badania Operacyjne
Zagadnienie znajdowania najkrótszej drogi w grafie - algorytm Forda
A
uk będzie reprezentował drogę pomiędzy wierzchołkami grafu. Wartość
nad łukiem (pi, pj) będzie oznaczała długość drogi pomiędzy
wierzchołkami pi oraz pj.
Zagadnienie znajdowania najkrótszej drogi w grafie 136/213
Politechnika Poznańska Badania Operacyjne
Algorytm Forda I
1
Każdemu wierzchołkowi pi przyporządkować wartość ui następująco:
u0 = 0, oraz ui = -", dla i = 1, 2, 3, . . . , n.
2
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj
przez ui - li,j.
3
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(pi, pj) " U mamy ui - uj li,j oraz dla każdego wierzchołka
pki = p0 istnieje co najmniej jeden wierzchołek pkj taki, że

(pkj , pki ) " U oraz
ukj - uki = lkj ,ki . (1)
Zagadnienie znajdowania najkrótszej drogi w grafie 137/213
Politechnika Poznańska Badania Operacyjne
Algorytm Forda II
4
Zaczynając od pn wyznaczyć ciąg
Ä… = [pn, pk1, . . . , pkl , p0],
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 - un = l0,kl + lkl ,kl-1 + · · · + lk1,n = l(Ä…).
Najkrótsza droga ą ma długość, która wynosi -un.
Zagadnienie znajdowania najkrótszej drogi w grafie 138/213
Politechnika Poznańska Badania Operacyjne
Redukcja sieci - algorytm Forda
p1
p4
p2
p5
p3
d(p1) < 0, d(p2) < 0, d(p3) < 0
d(p4) > 0, d(p5) > 0
Zagadnienie znajdowania najkrótszej drogi w grafie 139/213
5
7
3
9
Politechnika Poznańska Badania Operacyjne
Redukcja sieci - algorytm Forda
p1
p4
0
p0 p2
p5
p3
d(p0) < 0, d(p1) = 0, d(p2) = 0, d(p3) = 0
Zagadnienie znajdowania najkrótszej drogi w grafie 140/213
5
0
7
3
0
9
Politechnika Poznańska Badania Operacyjne
Redukcja sieci - algorytm Forda
p1
p4
0
p0 p2 p6
p5
p3
d(p0) < 0, d(p1) = 0, d(p2) = 0, d(p3) = 0
d(p6) > 0, d(p4) = 0, d(p5) = 0
Zagadnienie znajdowania najkrótszej drogi w grafie 141/213
5
0
0
7
3
0
0
9
Politechnika Poznańska Badania Operacyjne
Zadanie
Znalez
ć najkrótszą drogę w grafie, leżeli długości łuków są równe:
l0,1 = 5 l1,4 = 5 l3,5 = 9
l0,2 = 2 l2,4 = 7 l4,6 = 4
l0,3 = 1 l2,5 = 3 l5,6 = 1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 142/213
Politechnika Poznańska Badania Operacyjne
Zadanie
p1
p4
2
p0 p2 p6
p5
p3
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 143/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
u0 0
u1 -"
u2 -"
u3 -"
u4 -"
u5 -"
u6 -"
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 144/213
Badania Operacyjne
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0
u1 -"
u2 -"
u3 -"
Zadanie
u4 -"
u5 -"
u6 -"
p1
p4
2
p0 p2 p6
p5
p3
2011-10-29
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
p0
u0 0
u1 -"
u2 -"
u3 -"
u4 -"
u5 -"
u6 -"
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 146/213
Badania Operacyjne
p0
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0
u1 -"
u2 -"
u3 -"
Zadanie
u4 -"
u5 -"
u6 -"
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj przez
ui - li,j.
(p0, p1) (p0, p2) (p0, p3)
u0 = 0 u0 = 0 u0 = 0
u1 = -" u2 = -" u3 = -"
l0,1 = 5 l0,2 = 2 l0,3 = 1
u0 - u1 > l0,1 u0 - u2 > l0,2 u0 - u3 > l0,3
0 - (-") > 5 0 - (-") > 2 0 - (-") > 1
TAK TAK TAK
u1 = u0 - l0,1 u2 = u0 - l0,2 u3 = u0 - l0,3
u1 = 0 - 5 u2 = 0 - 2 u3 = 0 - 1
u1 = -5 u2 = -2 u3 = -1
2011-10-29
Politechnika Poznańska Badania Operacyjne
p0 p1
u0 0 0
u1 -" - 5
u2 -" - 2
u3 -" - 1
u4 -" - "
u5 -" - "
u6 -" - "
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 148/213
Badania Operacyjne
p0 p1
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0
u1 -" - 5
u2 -" - 2
u3 -" - 1
Zadanie
u4 -" - "
u5 -" - "
u6 -" - "
p1
p4
2
p0 p2 p6
p5
p3
2011-10-29
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
p0 p1
u0 0 0
u1 -" - 5
u2 -" - 2
u3 -" - 1
u4 -" - "
u5 -" - "
u6 -" - "
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 150/213
Badania Operacyjne
p0 p1
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0
u1 -" - 5
u2 -" - 2
u3 -" - 1
Zadanie
u4 -" - "
u5 -" - "
u6 -" - "
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj przez
ui - li,j.
(p1, p4)
u1 = -5
u4 = -"
l1,4 = 5
u1 - u4 > l1,4
0 - (-") > 5
TAK
u4 = u1 - l1,4
u4 = -5 - 5
u4 = -10
2011-10-29
Politechnika Poznańska Badania Operacyjne
p0 p1 p2
u0 0 0 0
u1 -" - 5 - 5
u2 -" - 2 - 2
u3 -" - 1 - 1
u4 -" - " - 10
u5 -" - " - "
u6 -" - " - "
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 152/213
Badania Operacyjne
p0 p1 p2
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0 0
u1 -" - 5 - 5
u2 -" - 2 - 2
u3 -" - 1 - 1
Zadanie
u4 -" - " - 10
u5 -" - " - "
u6 -" - " - "
p1
p4
2
p0 p2 p6
p5
p3
2011-10-29
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
p0 p1 p2
u0 0 0 0
u1 -" - 5 - 5
u2 -" - 2 - 2
u3 -" - 1 - 1
u4 -" - " - 10
u5 -" - " - "
u6 -" - " - "
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 154/213
Badania Operacyjne
p0 p1 p2
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0 0
u1 -" - 5 - 5
u2 -" - 2 - 2
u3 -" - 1 - 1
Zadanie
u4 -" - " - 10
u5 -" - " - "
u6 -" - " - "
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj przez
ui - li,j.
(p2, p4) (p2, p5)
u2 = -2 u2 = -2
u4 = -10 u5 = -"
l2,4 = 7 l2,5 = 3
u2 - u4 > l2,4 u2 - u5 > l2,5
-2 - (-10) > 7 -2 - (-") > 3
TAK TAK
u4 = u2 - l2,4 u5 = u2 - l2,5
u4 = -2 - 7 u5 = -2 - 3
u4 = -9 u5 = -5
2011-10-29
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3
u0 0 0 0 0
u1 -" - 5 - 5 - 5
u2 -" - 2 - 2 - 2
u3 -" - 1 - 1 - 1
u4 -" - " - 10 - 9
u5 -" - " - " - 5
u6 -" - " - " - "
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 156/213
Badania Operacyjne
p0 p1 p2 p3
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0 0 0
u1 -" - 5 - 5 - 5
u2 -" - 2 - 2 - 2
u3 -" - 1 - 1 - 1
Zadanie
u4 -" - " - 10 - 9
u5 -" - " - " - 5
u6 -" - " - " - "
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj przez
ui - li,j.
p1
p4
2
p0 p2 p6
(p3, p5)
u3 = -1
p5
u5 = -5
p3
l3,5 = 9
u3 - u5 > l3,5
-1 - (-5) > 9
NIE
2011-10-29
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4
u0 0 0 0 0 0
u1 -" - 5 - 5 - 5 - 5
u2 -" - 2 - 2 - 2 - 2
u3 -" - 1 - 1 - 1 - 1
u4 -" - " - 10 - 9 - 9
u5 -" - " - " - 5 - 5
u6 -" - " - " - " - "
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 158/213
Badania Operacyjne
p0 p1 p2 p3 p4
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0 0 0 0
u1 -" - 5 - 5 - 5 - 5
u2 -" - 2 - 2 - 2 - 2
u3 -" - 1 - 1 - 1 - 1
Zadanie
u4 -" - " - 10 - 9 - 9
u5 -" - " - " - 5 - 5
u6 -" - " - " - " - "
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj przez
ui - li,j.
(p4, p6)
u4 = -9
u6 = -"
l4,6 = 4
u4 - u6 > l4,6
-9 - (-") > 4
TAK
u6 = u4 - l4,6
u6 = -9 - 4
u6 = -13
2011-10-29
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5
u0 0 0 0 0 0 0
u1 -" - 5 - 5 - 5 - 5 - 5
u2 -" - 2 - 2 - 2 - 2 - 2
u3 -" - 1 - 1 - 1 - 1 - 1
u4 -" - " - 10 - 9 - 9 - 9
u5 -" - " - " - 5 - 5 - 5
u6 -" - " - " - " - " - 13
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 160/213
Badania Operacyjne
p0 p1 p2 p3 p4 p5
Zagadnienie znajdowania najkrótszej drogi w grafie
u0 0 0 0 0 0 0
u1 -" - 5 - 5 - 5 - 5 - 5
u2 -" - 2 - 2 - 2 - 2 - 2
u3 -" - 1 - 1 - 1 - 1 - 1
Zadanie
u4 -" - " - 10 - 9 - 9 - 9
u5 -" - " - " - 5 - 5 - 5
u6 -" - " - " - " - " - 13
Dla każdego łuku (pi, pj) " U, dla którego ui - uj > li,j zastąpić uj przez
ui - li,j.
(p5, p6)
u5 = -5
u6 = -14
l5,6 = 1
u5 - u6 > l5,6
-5 - (-14) > 1
TAK
u6 = u5 - l5,6
u6 = -5 - 1
u6 = -6
2011-10-29
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5
u0 0 0 0 0 0 0 0
u1 -" - 5 - 5 - 5 - 5 - 5 - 5
u2 -" - 2 - 2 - 2 - 2 - 2 - 2
u3 -" - 1 - 1 - 1 - 1 - 1 - 1
u4 -" - " - 10 - 9 - 9 - 9 - 9
u5 -" - " - " - 5 - 5 - 5 - 5
u6 -" - " - " - " - " - 13 - 6
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 162/213
Politechnika Poznańska Badania Operacyjne
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(pi, pj) " U mamy ui - uj li,j oraz dla każdego wierzchołka pki = p0

istnieje co najmniej jeden wierzchołek pkj taki, że (pkj , pki ) " U oraz
ukj - uki = lkj ,ki .
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 163/213
Politechnika Poznańska Badania Operacyjne
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(pi, pj) " U mamy ui - uj li,j oraz dla każdego wierzchołka pki = p0

istnieje co najmniej jeden wierzchołek pkj taki, że (pkj , pki ) " U oraz
ukj - uki = lkj ,ki .
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 164/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Gdy żadna modyfikacja nie jest już możliwa, to dla każdego łuku
(pi, pj) " U mamy ui - uj li,j oraz dla każdego wierzchołka pki = p0

istnieje co najmniej jeden wierzchołek pkj taki, że (pkj , pki ) " U oraz
ukj - uki = lkj ,ki .
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 165/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Zaczynając od pn wyznaczyć ciąg ą = [pn, pk1, . . . , pkl , p0], 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 - un = l0,kl + lkl ,kl-1 + · · · + lk1,n = l(Ä…).
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 166/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Zaczynając od pn wyznaczyć ciąg ą = [pn, pk1, . . . , pkl , p0], 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 - un = l0,kl + lkl ,kl-1 + · · · + lk1,n = l(Ä…).
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 167/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Zaczynając od pn wyznaczyć ciąg ą = [pn, pk1, . . . , pkl , p0], 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 - un = l0,kl + lkl ,kl-1 + · · · + lk1,n = l(Ä…).
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 168/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Zaczynając od pn wyznaczyć ciąg ą = [pn, pk1, . . . , pkl , p0], 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 - un = l0,kl + lkl ,kl-1 + · · · + lk1,n = l(Ä…).
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 169/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Zaczynając od pn wyznaczyć ciąg ą = [pn, pk1, . . . , pkl , p0], 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 - un = l0,kl + lkl ,kl-1 + · · · + lk1,n = l(Ä…).
p1, -5
p4, -9
2
p0, 0 p2, -2 p6, -6
p5, -5
p3, -1
Zagadnienie znajdowania najkrótszej drogi w grafie Zadanie 170/213
5
5
4
7
3
1
1
9
Politechnika Poznańska Badania Operacyjne
Zagadnienie znajdowania maksymalnego przepływu w grafie
Wartość nad łukiem (pi, pj) będzie oznaczała ilość jednostek które można
przesłać w jednostce czasu pomiędzy wierzchołkami pi oraz pj.
Zagadnienie znajdowania maksymalnego przepływu w grafie 171/213
Politechnika Poznańska Badania Operacyjne
Redukcja sieci - algorytm Forda-Fulkersona
p1
p4
p2
p5
p3
d(p1) < 0, d(p2) < 0, d(p3) < 0
d(p4) > 0, d(p5) > 0
Zagadnienie znajdowania maksymalnego przepływu w grafie 172/213
5
7
3
9
Politechnika Poznańska Badania Operacyjne
Redukcja sieci - algorytm Forda-Fulkersona
p1
p4
"
p0 p2
p5
p3
d(p0) < 0, d(p1) = 0, d(p2) = 0, d(p3) = 0
Zagadnienie znajdowania maksymalnego przepływu w grafie 173/213
5
"
7
3
"
9
Politechnika Poznańska Badania Operacyjne
Redukcja sieci - algorytm Forda-Fulkersona
p1
p4
"
p0 p2 p6
p5
p3
d(p0) < 0, d(p1) = 0, d(p2) = 0, d(p3) = 0
d(p6) > 0, d(p4) = 0, d(p5) = 0
Zagadnienie znajdowania maksymalnego przepływu w grafie 174/213
5
"
"
7
3
"
"
9
Politechnika Poznańska Badania Operacyjne
Znalez
ć maksymalny przepływ w sieci zredukowanej (P, U).
1
Przyporządkować wierzchołkowi p0 znak (-, ").
2
Wziąć pod uwagę dowolny z zaznaczonych już wierzchołków pi o
znaku (pl, ąi). Każdemu wierzchołkowi pj, który jeszcze nie został
zaznaczony i dla którego ri,j > 0 oraz [pi, pj] " U przypisać znak
(pi, ąj), gdzie ąj = min{ąi, ri,j}. Jeżeli wierzchołkowi pj 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 pn, wówczas przechodzimy do punktu 3;
2 wierzchołek pn nie ma znaku i nie można już przyporządkować znaku
żadnemu innemu wierzchołkowi, wówczas przechodzimy do punktu 4.
Zagadnienie znajdowania maksymalnego przepływu w grafie 175/213
Politechnika Poznańska Badania Operacyjne
3
Zmienić przepływ następująco: zaczynając od pn wyznaczyć ciąg
à = [p0, . . . , pn], w którym każdy wierzchoÅ‚ek jest znakiem dla
następnego. Pomniejszyć o ąn pojemności rezydualne ri,j łuków
(pi, pj) " à oraz powiÄ™kszyć o Ä…n pojemnoÅ›ci rezydualne rj,i. Wrócić
do punktu 1.
4
Układ wartości ri,j dla (pi, pj) " U stanowi przepływ maksymalny.
Zagadnienie znajdowania maksymalnego przepływu w grafie 176/213
Politechnika Poznańska Badania Operacyjne
Znalez
ć maksymalny przepływ w sieci poniżej.
p1
p4
9
p0 p2 p6
p3
p5
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 177/213
9
8
9
9
8
15
3
4
Politechnika Poznańska Badania Operacyjne
Przyporządkować wierzchołkowi p0 znak (-, ").
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3
1 x .9
2 x .8 .9
3 x .15
4 x .9
5 .4 x
6 x
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 178/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9
2 x .8 .9
3 x .15
4 x .9
5 .4 x
6 x
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 179/213
Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
Zagadnienie znajdowania maksymalnego przepływu w grafie
0 x .8 .9 .3 (-, ")
1 x .9
2 x .8 .9
Zadanie 3 x .15
4 x .9
5 .4 x
6 x
Wziąć pod uwagę dowolny z zaznaczonych już wierzchołków pi o znaku
(pl, ąi). Każdemu wierzchołkowi pj, który jeszcze nie został zaznaczony i
dla którego ri,j > 0 oraz [pi , pj] " U przypisać znak (pi , ąj), gdzie
Ä…j = min{Ä…i , ri,j}.
2011-10-29
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9
3 x .15
4 x .9
5 .4 x
6 x
min{8, "} = 8
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 181/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15
4 x .9
5 .4 x
6 x
min{9, "} = 9
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 182/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9
5 .4 x
6 x
min{8, 9} = 8
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 183/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9 (p2, 9)
5 .4 x
6 x
z p1: min{9, 8} = 8
z p2: min{9, 9} = 9
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 184/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9 (p2, 9)
5 .4 x (p0, 3)
6 x
min{3, "} = 3
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 185/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9 (p2, 9)
5 .4 x (p0, 3)
6 x (p4, 9)
z p3: min{15, 8} = 8
z p4: min{9, 9} = 9
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 186/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9 (p2, 9)
5 .4 x (p0, 3)
6 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 187/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9 (p2, 9)
5 .4 x (p0, 3)
6 x (p4, 9)
[p0, p2, p4, p6]
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 188/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 (p0, 9)
3 x .15 (p2, 8)
4 x .9 0 (p2, 9)
/
5 .4 x (p0, 3)
6 9 x (p4, 9)
[p0, p2, p4, p6]
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 189/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 .3 (-, ")
1 x .9 (p0, 8)
2 x .8 .9 0 (p0, 9)
/
3 x .15 (p2, 8)
4 9 x .9 0 (p2, 9)
/
5 .4 x (p0, 3)
6 9 x (p4, 9)
[p0, p2, p4, p6]
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 190/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .9 0 .3 (-, ")
/
1 x .9 (p0, 8)
2 9 x .8 .9 0 (p0, 9)
/
3 x .15 (p2, 8)
4 9 x .9 0 (p2, 9)
/
5 .4 x (p0, 3)
6 9 x (p4, 9)
[p0, p2, p4, p6]
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 191/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ")
1 x .9 (p0, 8)
2 9 x .8 .0 (p0, 9)
3 x .15 (p2, 8)
4 9 x .0 (p2, 9)
5 .4 x (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 192/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8)
2 9 x .8 .0 (p0, 9)
3 x .15 (p2, 8)
4 9 x .0 (p2, 9)
5 .4 x (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 193/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9)
3 x .15 (p2, 8)
4 9 x .0 (p2, 9)
5 .4 x (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 194/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -,
3 x .15 (p2, 8)
4 9 x .0 (p2, 9)
5 .4 x (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 195/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -,
3 x .15 (p2, 8) -,
4 9 x .0 (p2, 9)
5 .4 x (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 196/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -,
3 x .15 (p2, 8) -,
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 197/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -,
3 x .15 (p2, 8) -,
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 9 x (p4, 9)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 198/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -,
3 x .15 (p2, 8) -,
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 9 x (p4, 9) -,
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 199/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -, (p4, 8)
3 x .15 (p2, 8) -,
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 9 x (p4, 9) -,
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 200/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -, (p4, 8)
3 x .15 (p2, 8) -, (p2, 8)
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 9 x (p4, 9) -,
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 201/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -, (p4, 8)
3 x .15 (p2, 8) -, (p2, 8)
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 9 x (p4, 9) -, (p3, 8)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 202/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -, (p4, 8)
3 x .15 (p2, 8) -, (p2, 8)
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 9 x (p4, 9) -, (p3, 8)
[p0, p1, p4, p2, p3, p6]
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 203/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 .0 (p0, 9) -, (p4, 8)
3 x .15 7 (p2, 8) -, (p2, 8)
/
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 8 9 x (p4, 9) -, (p3, 8)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 204/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 0 .0 (p0, 9) -, (p4, 8)
/
3 8 x .15 7 (p2, 8) -, (p2, 8)
/
4 9 x .0 (p2, 9) (p1, 8)
5 .4 x (p0, 3) (p0, 3)
6 8 9 x (p4, 9) -, (p3, 8)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 205/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 (p0, 8) (p0, 8)
2 9 x .8 0 .0 8 (p0, 9) -, (p4, 8)
/ /
3 8 x .15 7 (p2, 8) -, (p2, 8)
/
4 9 1 x .0 (p2, 9) (p1, 8)
/
5 .4 x (p0, 3) (p0, 3)
6 8 9 x (p4, 9) -, (p3, 8)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 206/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 .0 .3 (-, ") (-, ")
1 x .9 1 (p0, 8) (p0, 8)
/
2 9 x .8 0 .0 8 (p0, 9) -, (p4, 8)
/ /
3 8 x .15 7 (p2, 8) -, (p2, 8)
/
4 8 9 1 x .0 (p2, 9) (p1, 8)
/
5 .4 x (p0, 3) (p0, 3)
6 8 9 x (p4, 9) -, (p3, 8)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 207/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .8 0 .0 .3 (-, ") (-, ")
/
1 8 x .9 1 (p0, 8) (p0, 8)
/
2 9 x .8 0 .0 8 (p0, 9) -, (p4, 8)
/ /
3 8 x .15 7 (p2, 8) -, (p2, 8)
/
4 8 9 1 x .0 (p2, 9) (p1, 8)
/
5 .4 x (p0, 3) (p0, 3)
6 8 9 x (p4, 9) -, (p3, 8)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 208/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .0 .0 .1 (-, ") (-, ")
1 8 x .1 -
2 9 x .0 .8 -
3 8 x 4 .3 (p5, 1)
4 8 1 x .0 -
5 2 .0 x (p0, 2)
6 12 9 x (p3, 1)
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 209/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .0 .0 .1 (-, ") (-, ")
1 8 x .1 - -,
2 9 x .0 .8 - -,
3 8 x 4 .3 (p5, 1) -,
4 8 1 x .0 - -,
5 2 .0 x (p0, 2) (p0, 1)
6 12 9 x (p3, 1) -,
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 210/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .0 .0 .1 (-, ") (-, ")
1 8 x .1 - -,-,
2 9 x .0 .8 - -,-,
3 8 x 4 .3 (p5, 1) -,-,
4 8 1 x .0 - -,-,
5 2 .0 x (p0, 2) (p0, 1)
6 12 9 x (p3, 1) -,-,
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 211/213
Politechnika Poznańska Badania Operacyjne
p0 p1 p2 p3 p4 p5 p6
0 x .0 .0 .1 (-, ") (-, ")
1 8 x .1 - -,-,
2 9 x .0 .8 - -,-,
3 8 x 4 .3 (p5, 1) -,-,
4 8 1 x .0 - -,-,
5 2 .0 x (p0, 2) (p0, 1)
6 12 9 x (p3, 1) -,-,
9 + 8 + 1 + 1 + 1 = 20
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 212/213
Politechnika Poznańska Badania Operacyjne
Realizacja maksymalnego przepływu.
p1
p4
9
p0 p2 p6
p3
p5
Zagadnienie znajdowania maksymalnego przepływu w grafie Zadanie 213/213
8
8
9
1
8
11
3
3