2. Metode MODI (Modified Distribution) / Faktor Pengali (Multiplier) Metode MODI disebut juga metode Faktor Pengali atau Multiplier. Cara iterasinya sama seperti Metode Batu Loncatan. Perbedaan utama terjadi pada cara pengevaluasian variabel non basis, atau penentuan penurunan ongkos transport per unit untuk tiap variabel. Cara ini dikembangkan berdasarkan teori dualitas. Untuk setiap baris ke-i dari tabel transportasi dikenal suatu bilangan baris (multiplier ui ) dan untuk setiap kolom ke-j disebut bilangan kolom (multiplier vj ) sehingga untuk tiap variabel basis Xij diperoleh persamaan : ui + vj = Cij
(i)
Cara pengisiannya ditentukan terlebih dahulu salah satu ui atau vj secara sembarang misalnya u1 = 0, dengan demikian dengan menggunakan persamaan (i) dapat diperoleh nilai ui dan vj yang lain. Setelah ui dan vj terisi semua maka untuk semua variabel non basis dapat dihitung : Zij -Cij = ui + vj - Cij
(ii)
Akan diperoleh tabel optimal jika semua
Zij -Cij ≤ 0 (semua negatif atau nol).
Jika tabel belum optimal cara menentukan variabel yang masuk menjadi basis (Entering Variable) dan variabel yang keluar basis (Leaving Variable) caranya sama seperti Metode Batu Loncatan.
Contoh Soal: Diketahui table Transportasi sebagai berikut: T1 A1 A2 A3 bj Tentukan :
T2 50
X11
T3 100
X12 200
X21
X13 300
X22 100
X31
200 X23
200 X32
150
100
300 X33
210
90
ai 120 170 160 450
a). Ongkos Awal dengan Metode Ongkos Kolom Terkecil ! b). Jawab Optimal dengan Metode MODI !
C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 1 dari 7
Jawab: a). Ongkos Awal dengan Metode Ongkos Kolom Terkecil : T1 A1 A2 A3
T2 50
T3 100
x
120
300
80 200
150
300 x
130
bj
200
90
100
30
100 x
200 x
ai
210
90
120 170 160 450
Zawal = 50.120 + 300.80 + 200.90 + 100.30 + 200.130 = 77.000 b). Jawab Optimal dengan Metode MODI : 1). Evaluasi dari variable basis dengan memisalkan salah satu nilai dari ui atau vj dengan sebarang bilangan bulat tertentu, misalkan : u1 = 0 (tidak harus u1 yang dimisalkan dan tidak harus nol bilangannya), sehingga dapat dihitung: C11 = u1 + v1 50 = 0 + v1 v1 = 50. C31 = u3 + v1 100 = u3 + 50 u3 = 50. C32 = u3 + v2 200 = 50 + v2 v2 = 150. C22 = u2 + v2 300 = u2 + 150 u2 = 150. C23 = u2 + v3 200 = 150 + v3 v3 = 50. T1 A1 A2 A3
T2 50
T3 100
x
120
x
200 x
300
80
200
90
100
30
100
200
130
300 x
bj
150
210
90
vj
v1 = 50
v2 = 150
v3 = 50
ai
ui
120
u1 = 0
170
u2 = 150
160
u3 = 50
450
2). Evaluasi dari variable non basis dengan menghitung nilai dari Zij −Cij = ui + vj - Cij , sehingga diperoleh: Z12 −C12 = u1 + v2 - C12 = 0 + 150 – 100 = 50 C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 2 dari 7
Z13 −C13 = u1 + v3 - C13 = 0 + 50 – 100 = –50 Z21 −C21 = u2 + v1 - C21 = 150 + 50 – 200 = 0 Z33 −C33 = u3 + v3 - C33 = 50 + 50 – 300 = –200 3). Karena masih ada nilai dari Zij−Cij yang positif (Zij−Cij > 0) maka table belum Optimal. 4). Menentukan Variabel yang masuk menjadi basis dengan memilih nilai Max { Zij−Cij } = 50 yaitu nilai dari Z12−C12, maka X12 masuk menjadi basis. 5). Menentukan Variabel yang keluar dari basis dengan cara : *) Buat loop yang melalui variable yang baru masuk menjadi basis (X12) : X11 – X31 + X32 – X12 *) Variabel yang keluar basis adalah : Min {X11 , X32} = Min {120, 130} = 120, yang merupakan nilai dari X11, maka X11 keluar basis. *). Penyesuaian nilai variable dalam basis: X11 = Keluar Basis
X31 = 30 + 120 = 150
X32 = 130 – 120 = 10
X12 = 120 (masuk jadi basis).
Sehingga tabelnya berubah seperti berikut ini: T1 A1 A2 A3
T2 50
x
T3 100 x
120 200
x
300
80 100
150
100 200
90 200
300 x
10
bj
150
210
90
vj
v1 = 0
v2 = 100
v3 = 0
ai
ui
120
u1 = 0
170
u2 = 200
160
u3 = 100
450
Dengan memisalkan : u1 = 0, maka : C12 = u1 + v2 100 = 0 + v2 v2 = 100. C22 = u2 + v2 300 = u2 + 100 u2 = 200. C23 = u2 + v3 200 = 200 + v3 v3 = 0. C32 = u3 + v2 200 = u3 + 100 u3 = 100. C31 = u3 + v1 100 = 100 + v1 v1 = 0. (seperti terlihat pada table di atas). Total Ongkosnya adalah : Z1 = 100.120 + 300.80 + 200.90 + 100.150 + 200.10 = 71.000 atau Z1 = Zawal – (50 x 120) = 77.000 – 6.000 = 71.000. C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 3 dari 7
3). Evaluasi dari variable non basis dengan menghitung nilai dari Zij −Cij = ui + vj - Cij , sehingga diperoleh: Z11 −C11 = u1 + v1 - C11 = 0 + 0 – 50 = –50 Z13 −C13 = u1 + v3 - C13 = 0 + 0 – 100 = –100 Z21 −C21 = u2 + v1 - C21 = 200 + 0 – 200 = 0 Z33 −C33 = u3 + v3 - C33 = 100 + 0 – 300 = –200 4). Karena semua nilai dari Zij−Cij ≤ 0 maka table sudah Optimal (minimum) dengan total ongkos minimum 71.000. Soal di atas jika diselesaikan dengan LINDO diperoleh hasil sebagai berikut: MIN
50 X11 + 100 X12 + 100 X13 + 200 X21 + 300 X22 + 200 X23 + 100 X31 + 200 X32 + 300 X33 SUBJECT TO 2) X11 + X12 + X13 = 120 3) X21 + X22 + X23 = 170 4) X31 + X32 + X33 = 160 5) X11 + X21 + X31 = 150 6) X12 + X22 + X32 = 210 7) X13 + X23 + X33 = 90 END
LP OPTIMUM FOUND AT STEP
7
OBJECTIVE FUNCTION VALUE 1) VARIABLE X11 X12 X13 X21 X22 X23 X31 X32 X33 ROW 2) 3) 4) 5) 6) 7)
71000.00 VALUE 0.000000 120.000000 0.000000 0.000000 80.000000 90.000000 150.000000 10.000000 0.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
REDUCED COST 50.000000 0.000000 100.000000 0.000000 0.000000 0.000000 0.000000 0.000000 200.000000 DUAL PRICES 200.000000 0.000000 100.000000 -200.000000 -300.000000 -200.000000
C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 4 dari 7
NO. ITERATIONS=
7
RANGES IN WHICH THE BASIS IS UNCHANGED:
VARIABLE X11 X12 X13 X21 X22 X23 X31 X32 X33
ROW 2 3 4 5 6 7
CURRENT COEF 50.000000 100.000000 100.000000 200.000000 300.000000 200.000000 100.000000 200.000000 300.000000
OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 50.000000 50.000000 INFINITY INFINITY 100.000000 INFINITY 0.000000 0.000000 100.000000 100.000000 INFINITY 0.000000 INFINITY 200.000000 0.000000 INFINITY 200.000000
CURRENT RHS 120.000000 170.000000 160.000000 150.000000 210.000000 90.000000
RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
ALLOWABLE DECREASE 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
Hasil tersebut jika dinyatakan dalam table transportasi adalah sebagai berikut: T1 50
A1
bj
T3 100
100
300
200
120 200
A2 A3
T2
80
90
100
150 150
200
300
10 210
90
ai 120 170 160 450
Dengan Total Ongkosnya adalah : ZMin = 100.120 + 300.80 + 200.90 + 100.150 + 200.10 = 71.000.
C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 5 dari 7
Masalah Transportasi Tidak Seimbang Suatu permasalahan
transprotasi
dikatakan
seimbang (balanced transportation
model) jika total penawaran (kapasitas sumber) atau total supply
sama dengan total n
m
permintaan (kapasitas tujuan) atau total demand, dengan kata lain :
∑b
∑ ai =
j
j =1
i =1
Dalam persoalan yang sebenarnya, batasan ini tidak selalu dipenuhi, atau dengan kata lain jumlah supply yang tersedia mungkin lebih besar atau lebih kecil dari jumlah yang diminta, jika hal ini terjadi disebut dengan model transprotasi tidak seimbang (unbalanced). Namun setiap persoalan transportasi selalu dapat dibuat menjadi seimbang dengan memasukkan variabel semu (artificial variable). Jika jumlah demand melebihi jumlah supply, maka dibuat suatu sumber dummy yang akan mensupply kekurangan tersebut, yaitu n
m
∑ b j − ∑ ai .
sebanyak :
j =1
i =1
Sebaliknya, jika jumlah supply melebihi jumlah demand, maka dibuat suatu tujuan n
m
dummy yang akan menyerap kelebihan tersebut, yaitu sebanyak
∑a
i
i =1
−
∑b
j
j =1
Ongkos transportasi per-unit (Cij) dari sumber dummy keseluruh tujuan adalah nol. Hal ini dapat dipahami karena pada pada kenyataannya dari sumber dummy tidak terjadi pengiriman. Atau dengan kata lain masalah transportasi tidak seimbang dapat diselesaikan jika diubah menjadi bentuk yang seimbang dengan cara menambah daerah sumber atau daerah tujuan semu dimana ongkos transportasi per-unit (Cij) dari daerah sumber atau ke daerah tujuan semu semuanya nol dan kapasitas sumber atau tujuan semu merupakan selisih n
m
antara
∑a
i
i =1
dengan
∑b
j
.
j =1
C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 6 dari 7
Contoh Soal: Diketahui table Transportasi sebagai berikut: T1 A1 A2 A3 bj
T2
T3
50
100
100
200
300
200
100
200
300
150
200
ai 120 170 160
90
Dari contoh di atas merupakan masalah transportasi tidak seimbang karena total kapasitas n
m
sumber (
∑ ai = 450 ) lebih banyak dari pada total kapasitas tujuan ( i =1
∑b
j
= 440) . Agar dapat
j =1
diselesaikan, maka persoalan di atas harus diubah menjadi bentuk yang seimbang dengan cara menambah daerah tujuan semu (Dummy), sehingga akan menghasilkan table yang seimbang sebagai berikut: T1 A1 A2 A3 bj
T2
T3
Dummy
50
100
100
0
200
300
200
0
100
200
300
0
150
200
90
10
ai 120 170 160 450
C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 11.doc
Hal. 7 dari 7