AGH
METODY ORGANIZACJI
PROJEKT:
OPTYMALIZACJA SIECI TRANSPORTOWEJ
POD WZGL
DEM MINIMALIZACJI
KOSZTU TRANSPORTU W
GLA
Poniższa tabela przedstawia koszt transportu tony węgla z kopalń do poszczególnych
elektrowni.
E1 E2 E3 E4 E5
K1 2,8 5,8 3,8 4,8 8,8
K2 1,8 9,8 4,8 5,8 10,8
K3 5,5 6,8 1,8 7,8 5,8
Należy obliczyć zapotrzebowanie poszczególnych elektrowni oraz zdolności produkcyjne
kopalń, które są zadane następującymi wzorami:
Zapotrzebowanie: Zdolność produkcyjna:
E1 = 80(n+g) K1 = 100(n+g)
E2 = 60(n+2g) K2 = 150(g+2n)
E3 = 70n K3 = 120(2n+g)
E4 = 50g
E5 = 90(2n+g)
n = 2
g = 1
Zapotrzebowanie: Zdolność produkcyjna:
E1 = 80(2+1) = 240 K1 = 100(2+1) = 300
E2 = 60(2+2) = 240 K2 = 150(1+4) = 750
E3 = 70*2 = 140 K3 = 120(4+1) = 600
E4 = 50*1 = 50
E5 = 90(4+1) = 450 Suma: 1650
Suma: 1120
A więc:
E1 E2 E3 E4 E5 Podaż:
K1 2,8 5,8 3,8 4,8 8,8 300
K2 1,8 9,8 4,8 5,8 10,8 750
K3 5,5 6,8 1,8 7,8 5,8 600
Popyt: 240 240 140 50 450
Ponieważ podaż nie jest równa popytowi, zadanie należy wcześniej zbilansować, poprzez
dodanie fikcyjnego odbiorcy Ef, dla którego koszty transportu będą równe 0.
Tabela zbilansowanego zadania transportowego:
E1 E2 E3 E4 E5 Ef Podaż:
K1 2,8 5,8 3,8 4,8 8,8 0 300
K2 1,8 9,8 4,8 5,8 10,8 0 750
K3 5,5 6,8 1,8 7,8 5,8 0 600
Popyt: 240 240 140 50 450 530
Teraz POPYT = PODAŻ = 1650.
Obliczanie kosztów transportu metodą minimalnego elementu macierzy kosztów.
Odejmujemy z każdego wiersza, a w razie konieczności również z poszczególnych kolumn wartość
minimalnego kosztu z tego wiersza/kolumny, w taki sposób, aby w każdym wierszu i każdej
kolumnie było min. jedno zero.
E1 E2 E3 E4 E5 Ef
K1 1,8 0 2,8 0 3,8 0
K2 0 4,8 3,8 1,8 5,8 0
K3 4,8 1,8 0 3,8 0 0
Następnie w miejsca, gdzie są zera, wstawiamy maksymalną możliwą do zrealizowania ilość
ładunku.
E1 E2 E3 E4 E5 Ef Podaż:
2,8 5,8 3,8 4,8 8,8 0
K1 300
240 50 10
9,8 4,8 5,8 10,8 0
K2 1,8 750
510
240
5,5 6,8 1,8 7,8 5,8 0
K3 600
140 450 10
Popyt: 240 240 140 50 450 530
Obecne rozwiązanie jest rozwiązaniem optymalnym, ponieważ udało się uzupełnić macierz tylko w
miejscach, gdzie są zera, a więc koszty są minimalne.
Obliczenie minimalnego kosztu transportu:
K = (240*1,8) + (240*5,8) + (140*1,8) + (50*4,8) + (450*5,8) + (530*0) =
= 432 + 1392 + 252 + 240 + 2610 = 4962 zł
Minimalny koszt transportu węgla wynosi: 4962 zł