BADANIA OPERACYJNE
BADANIA OPERACYJNE
BADANIA OPERACYJNE
BADANIA OPERACYJNE
ZAGADNIENIE
ZAGADNIENIE
TRANSPORTOWE
TRANSPORTOWE
Zagadnienie transportowe jest szczególnym przypadkiem
zagadnienia
programowania
liniowego,
jednakże
przedstawione dotychczas metody rozwiązani programowania
liniowego są małe efektywne w zastosowaniu do zagadnienia
transportowego.
Model transportowy
1. Macierz kolumnowa dostawców
2. Macierz wierszowa odbiorców
3. Macierz prostokątna jednostkowych kosztów transportu
m
a
a
a
D
2
1
n
b
b
b
B
2
1
mn
m
m
n
n
c
c
c
c
c
c
c
c
c
C
2
1
2
22
21
1
12
11
Wprowadzamy zmienne decyzyjne oznaczające
liczbę jednostek produktu P dostarczanych (przewożonych)
do i-tego dostawcy do k-tego odbiorcy
mn
m
m
n
n
x
x
x
x
x
x
x
x
x
X
2
1
2
22
21
1
12
11
0
ik
x
Zagadnienie transportowe polega na wyznaczeniu
optymalnego planu przewozów X, który minimalizuje
następującą funkcję T całkowitych kosztów transportu
m
i
n
k
ik
ik
x
c
T
1 1
przy warunkach ograniczających
,...
3
,
2
,
1
,
1
k
b
x
k
m
i
ik
,...
3
,
2
,
1
,
1
i
c
x
i
n
i
ik
.
0
dla
ij
x
Tak sformułowane zagadnienie transportowe nazywa
się zbilansowanym lub zamkniętym, gdyż
czyli
Wzór powyższy mówi, iż podaż jest równa popytowi.
W przypadku gdy tej równowagi nie ma nazywamy
zagadnieniem
transportowym otwartym
. Zagadnienie to
można zbilansować
zbilansować
przez wprowadzenie sztucznego odbiorcy
lub dostawcy.
m
i
n
k
m
i
ik
n
k
ik
x
x
1
1 1
1
.
1
1
n
k
k
m
i
i
b
a
Zbilansowane zagadnienie transportowe posiada skończone rozwiązanie
optymalne oraz dla jego współczynników całkowitych optymalny plan
transportowy zbudowany jest z liczb naturalnych
Twierdzenie
Rozwiązanie zagadnienia transportowego
1. Wyznaczenie pierwszego dopuszczalnego rozwiązania bazowego, czyli
planu przewozów stosując jedną z metod
(a) metoda kąta północno-zachodniego
(a) metoda kąta północno-zachodniego
(b) metoda najmniejszych elementów macierzy kosztów
(b) metoda najmniejszych elementów macierzy kosztów
(c) metoda aproksymacyjna VAM
(c) metoda aproksymacyjna VAM
2. Ocena optymalności przyjętego pierwszego planu transportowego przy
pomocy tzw. potencjałów.
3. Modyfikacja planu nieoptymalnego metodą cykli zamkniętych. Metoda
polega na wyznaczeniu następnego lepszego planu przewozowego.
Metoda kąta północno-zachodniego
Metoda kąta północno-zachodniego
Budujemy wpisujemy do tabelki wartości kosztów jednostkowych c
ki
małymi
cyframi w prawych górnym rogach poszczególnych kratek na wpisanie
odpowiednich wartości zmiennych decyzyjnych x
ik.
W metodzie tej zawsze rozpoczynamy od wierzchołka północno-zachodniego
wpisując
1
1
11
,b
a
in
m
x
Od zajętej już klatki (1,1) przesuwamy się o jedną klatkę
1
1
11
1
2
21
1
1
2
11
1
12
gdy
,
,
lub
gdy
,
,
b
a
x
b
a
in
m
x
b
a
b
x
a
in
m
x
Postępujemy analogicznie wypełniając w stosunku do następnych klatek
1. Macierz kolumnowa dostawców
2. Macierz wierszowa odbiorców
3. Macierz prostokątna jednostkowych kosztów transportu
m
a
a
a
D
2
1
n
b
b
b
B
2
1
mn
m
m
n
n
c
c
c
c
c
c
c
c
c
C
2
1
2
22
21
1
12
11
Metoda kąta północno-zachodniego
Metoda kąta północno-zachodniego
Budujemy wpisujemy do tabelki wartości kosztów jednostkowych c
ki
małymi
cyframi w prawych górnym rogach poszczególnych kratek na wpisanie
odpowiednich wartości zmiennych decyzyjnych x
ik.
W metodzie tej zawsze rozpoczynamy od wierzchołka północno-zachodniego
wpisując
1
1
11
,b
a
in
m
x
Od zajętej już klatki (1,1) przesuwamy się o jedną klatkę
1
1
11
1
2
21
1
1
2
11
1
12
gdy
,
,
lub
gdy
,
,
b
a
x
b
a
in
m
x
b
a
b
x
a
in
m
x
Postępujemy analogicznie wypełniając w stosunku do następnych klatek
Przykład
Przykład
Dane są macierze:
dostawcy
odbiorcy
oraz jednostkowych kosztów transportu
70
40
90
D
50
30
90
30
B
12
3
1
16
1
5
8
10
2
13
7
6
C
Rozwiązanie
Mamy tutaj
200
4
1
3
1
k
k
i
i
b
a
30
30
,
90
,
1
1
11
in
m
b
a
in
m
x
Od zajętej już klatki (1,1) przesuwamy się o jedną klatkę
.
50
,
10
,
30
30
90
gdyż
,
60
,
30
90
,
34
23
22
2
11
1
12
x
x
x
in
m
b
x
a
in
m
x
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
13
2
90
2
10
8
5
1
40
3
16
1
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
13
2
90
2
10
-----
8
5
1
40
3
16
-----
1
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
60
13
-----
2
-----
90
2
10
-----
8
5
1
40
3
16
-----
1
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
60
13
-----
2
-----
90
2
10
-----
8
30
5
1
40
3
16
-----
1
-----
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
60
13
-----
2
-----
90
2
10
-----
8
30
5
10
1
-----
40
3
16
-----
1
-----
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
60
13
-----
2
-----
90
2
10
-----
8
30
5
10
1
-----
40
3
16
-----
1
-----
3
20
12
50
70
b
k
30
90
30
50 200
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
60
13
-----
2
-----
90
2
10
-----
8
30
5
10
1
-----
40
3
16
-----
1
-----
3
20
12
50
70
b
k
30
90
30
50 200
1550
12
50
3
20
5
10
8
30
7
60
6
30
1
T
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
7
13
2
90
2
10
8
5
1
40
3
16
1
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
Metoda najmniejszych elementów macierzy kosztów
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
7
13
2
90
2
10
8
5
1
40
3
16
1
70
3
12
70
b
k
30
90
30
50 200
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
Metoda najmniejszych elementów macierzy kosztów
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
7
13
2
90
2
10
8
5
1
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
Metoda najmniejszych elementów macierzy kosztów
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
7
13
2
90
2
10
8
5
1
40
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
Metoda najmniejszych elementów macierzy kosztów
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
7
13
2
90
2
10
-----
8
----
5
-----
1
40
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
Metoda najmniejszych elementów macierzy kosztów
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
7
13
2
10
90
2
10
-----
8
----
5
-----
1
40
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
Metoda najmniejszych elementów macierzy kosztów
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
13
2
10
90
2
10
-----
8
----
5
-----
1
40
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
Metoda najmniejszych elementów macierzy kosztów
50
30
90
30
B
70
40
90
D
12
3
1
16
1
5
8
10
2
13
7
6
C
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
20
13
2
10
90
2
10
-----
8
----
5
-----
1
40
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
Metoda najmniejszych elementów macierzy kosztów
O D B I O R C Y
D
O
S
T
A
W
C
Y
i
k
1
2
3
4
a
i
1
6
30
7
20
13
30
2
10
90
2
10
-----
8
----
5
-----
1
40
40
3
16
-----
1
70
3
----
12
----
70
b
k
30
90
30
50 200
840
1
70
1
40
2
10
13
30
7
20
6
30
1
T
Przykład
Przykład
W trzech wytwórniach wytwarzane jest wino. Owoce potrzebne do jego produkcji
pozyskuje się z plantacji znajdujące się przy wytwórniach oraz od prywatnych
dostawców D
1
, D
2
, D
3
, D
4
, D
5
, D
6
. W tabeli zostały podane jednostkowe koszty
przewozu owoców (w zł za 100 kg) od każdego z dostawców do poszczególnych
wytwórni oraz zapotrzebowanie każdej wytwórni i możliwości wytwórcze
dostawców.
DOSTAWCY
W
Y
T
W
Ó
R
N
I
E
i k
D
1
D
2
D
3
D
4
D
5
D
6
Popy
t
W
1
14
10
11
7
8
9
150
W
2
7
13
10
11
12
15
150
W
3
12
6
8
13
9
6
150
Poda
ż
60
70
50
90
80 100 450
