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
Document Outline
- Slide 1
- Slide 2
- Slide 3
- Slide 4
- Slide 5
- Slide 6
- Slide 7
- Slide 8
- Slide 9
- Slide 10
- Slide 11
- Slide 12
- Slide 13
- Slide 14
- Slide 15
- Slide 16
- Slide 17
- Slide 18
- Slide 19
- Slide 20
- Slide 21
- Slide 22
- Slide 23
- Slide 24
- Slide 25
- Slide 26
- Slide 27
- Slide 28
- Slide 29
- Slide 30
- Slide 31
- Slide 32
- Slide 33
Wyszukiwarka
Podobne podstrony:
badania operacyjne metoda simplex[1]
badania operacyjne metoda simplex(1)
Zagadnienia transportowe, EXCEL, SOLVER
badania operacyjne, Metoda iteracji prostej Gaussa, Metoda iteracji prostej Gaussa-Jordana
EXCEL 28,11
wyklad 2 (28.11.2010), Zarządzanie, sem VI marketing, Zarządzanie projektami, wykłady
organizacja uslug w gastronomii wyklad 2 28 11 2010
Prawo europejskie (5) 27-28.11.2010, Prawo europejskie
28 11 2010 kpa łaszczyca wykład
PRAWO NOTATKI 28.11.2010 moje !!, Prawo
badania operacyjne, w5 Metoda Simpleks
BO, bo zagadnienie transportowe, Badania operacyjne - wprowadzenie
Dwuetapowe zagadnienia transportowe MSU, WSL POZNAŃ, Badania operacyjne
Jadczak R Badania operacyjne, wyklad zagadnienia transportowe i przydziału
Badania operacyjne zagadnienie transportowe lista 4
badania operacyjne, w6 Metoda Simpleks 2
więcej podobnych podstron