PERTEMUAN 9 MENENTUKAN SOLUSI FISIBEL BASIS AWAL
1). Metode Pojok Kiri Atas / Pojok Barat Laut (North West Corner) Metode ini mula-mula diperkenalkan
oleh
Charnes
dan Cooper kemudian
diperluas oleh Danziq. Langkah-langkah Metode Pojok Barat Laut adalah sebagai berikut 1. Dimulai dengan mengisi kotak pojok barat laut yaitu sel (1,1) sehingga X11
=
min {a1 ,b1} Terdapat 3 kemungkinan, yaitu : a. Jika a1 > b1 , maka X11 = b1 , kemudian dilanjutkan langkah mendatar yaitu : X12 = min {a1 - X11, b1 }. b. Jika a1 = b1 , maka X11 = b1 = a1, kemudian dilanjutkan langkah miring yaitu : X22 = min {a2 , b2}. c. Jika a1 < b1 , maka X11 = a1 , kemudian dilanjutkan langkah turun yaitu : X21 = min {a2 , b1 - X11}. 2. Langkah diatas diulangi sambil melangkah menuju arah tenggara atau kotak (m,n) atau ke arah pojok kanan bawah. Contoh 1: Dari 3 buah pelabuhan A1, A2 dan A3 terdapat semen sebanyak masing-masing 120 ton, 170 ton dan 160 ton. Semen tersebut akan diangkut ke kota T1 , T2 dan T3 yang masing-masing mempunyai daya tampung 150 ton, 210 ton dan 90 ton. Biaya pengiriman dari pelabuhan A1 ke kota T1 , T2 dan T3 masing-masing adalah 50, 100 dan 100 (dalam ribuan rupiah/ton). Biaya pengiriman dari pelabuhan A2 ke kota T1 , T2 dan T3 adalah 200, 300 dan 200, sedangkan biaya pengiriman dari pelabuhan A3 ke kota T1 , T2 dan T3 adalah 100, 200 dan 300. Tentukan : a). Tabel Transportasi ! b). Model Transportasi ! c). Ongkos Awal dengan Metode Pojok Kiri Atas !
C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 9.doc
Hal. 1 dari 5
Penyelesaian : a). Tabel Transportasi: T1 A1 A2 A3 bj
T2 50
T3 100
X12
X11
X13
200 X21
300 X22 200 X32
150
200 X23
100 X31
100
300 X33
210
90
ai 120 170 160 450
b). Model Transportasi: *). Fungsi Tujuan : Meminimumkan : Z = (50 X11 + 100 X12 + 100 X13 + 200 X21 + 300 X22 + 200 X23 + 100 X31 + 200 X32 + 300 X33) x Rp. 1.000,*). Fungsi Kendala: a). Keterbatasan Kapasitas Sumber ke-1 (A1): X11 + X12 + X13 = 120 b). Keterbatasan Kapasitas Sumber ke-2 (A2): X21 + X22 + X23 = 170 c). Keterbatasan Kapasitas Sumber ke-3 (A3): X31 + X32 + X33 = 160 d). Keterbatasan Kapasitas Tujuan ke-1 (T1): X11 + X21 + X31 = 150 e). Keterbatasan Kapasitas Tujuan ke-2 (T2): X12 + X22 + X32 = 210 f). Keterbatasan Kapasitas Tujuan ke-3 (T3): X13 + X23 + X33 = 160 *). Syarat Non Negatif : Xij ≥ 0, untuk i = 1, 2, 3 dan j = 1, 2, 3 c). Ongkos Awal dengan Metode Pojok Kiri Atas: Langkah-langkahnya adalah sebagai berikut: Dimulai dari sel (1,1) yaitu menentukan nilai dari X11 = min {a1 ,b1} = min{120, 150} X11 = 120. Maka A1 Habis, dilanjutkan ke bawah yaitu sel (2,1) yaitu : X21 = min {a2, b1 - X11 } = min{170,150-120} = 30 ( T1 terpenuhi ). C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 9.doc
Hal. 2 dari 5
X22 = min {a2 - X21 , b2 } = min{170-30,210} = 140 ( A2 habis ). X32 = min {a3 , b2 - X22 } = min{160,210-140} = 70 ( T2 terpenuhi ). X33 = min {a3 - X32 , b3 } = min{160 - 90, 90} = 90 ( T3 dan A3 terpenuhi ). Sehingga tabelnya menjadi: T1 A1 A2 A3 bj
T2 50
120
T3 100
x
x
200 30
300 140
100
200 x
200 70
x
100
150
300 90
210
90
ai 120 170 160 450
Jadi variabel-variabel basisnya adalah : X11 , X21 , X22 , X32 , dan X33. Sedangkan variabel-variabel non basisnya adalah : X12 , X13 , X23 , dan X31. Biaya awalnya adalah : Z = C11 X11 + C21 X21 + C22 X21 + C32 X32 + C33 X33 = (50.120 + 200.30 + 300.140 + 200.70 + 300.90) x Rp. 1.000,= (6.000 + 6.000 + 42.000 + 14.000 + 27.000) x Rp. 1.000,= Rp. 95.000.000,2). Metode Ongkos Terkecil (Least Cost) Penentuan solusi fisibel basis awal dengan menggunakan Metode Ongkos Terkecil tidak hanya mempertimbangkan barang yang harus didistribusikan saja tetapi sekaligus mempertimbangkan faktor biaya. Terdapat 2 cara dalam menentukan solusi fisibel basis
awal
dengan
menggunakan Metode Ongkos
Terkecil yaitu Metode Ongkos Baris Terkecil dan Metode Ongkos Kolom Terkecil. i). Metode Ongkos Baris Terkecil Langkah-langkah yang digunakan : Dimulai dari baris ke-1. Tentukan X1k = min { a1 , bk } dimana k = kolom pada baris ke-1 yang mempunyai ongkos terkecil. Kemungkinan-kemungkinan yang ada untuk X1k dan tindak lanjutnya adalah : 1. Jika X1k = a1 maka proses dilanjutkan ke baris ke-2, dengan memikirkan baris ke-1 telah terpenuhi. 2. Jika X1k = bk , maka lanjutkan ke
kolom
k, selanjutnya tentukan lagi
ongkos terkecil pada baris ke-1 sehingga baris ke-1 terpenuhi. C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 9.doc
Hal. 3 dari 5
3. Jika dalam proses dijumpai 2 atau lebih ongkos terkecil yang terletak pada suatu baris yang sama, dapat dipilih sembarang, demikian pula jika terdapat baris dan kolom yang tinggalkan
kolom
yang
dapat
bersangkutan
terpenuhi
secara serentak,
dan lanjutkan memilih
ongkos
terkecil (sisanya) pada baris tersebut. Sel yang memuat baris seperti diatas dinyatakan sebagai baris berharga nol. Contoh 2: Diketahui table transportasi sebagai berikut: T1 A1 A2 A3 A4 bj
T2 3
X11
1 X12
2 X21
40
4 X25
2 X34
1 X35
1 45
5
2
5
X43
ai
X15
X24
X33 3
X42
4
2
4
T5
X14
X23
X32 4
50
2
3
3
T4
X13
X22
X31 X41
T3
2 X44
1 X45
75
40
75 30 65 80 250
Tentukanlah: a). Model Transportasi ! b). Ongkos awal dengan Metode Pojok Kiri Atas ! c). Ongkos awal dengan Metode Ongkos Baris Terkecil ! d). Ongkos awal dengan Metode Ongkos Kolom Terkecil ! Akan dijawab soal c, untuk soal a, b, dan d sebagai Tugas ! Jawab: c). Ongkos awal dengan Metode Ongkos Baris Terkecil. Langkah-langkahnya adalah sebagai berikut: 1. Baris-1 Ongkos terkecil terletak pada kolom-2 yaitu 1, maka : X12 = Min{a1, b2} = Min{75, 40} = 40. Jadi kolom ke-2 ( T2 ) terpenuhi. Karena a2 belum habis (baris 1 terpenuhi), pilih ongkos terkecil berikutnya yaitu 2 yang terletah pada kolom-3, maka : X13 = Min{a1 - X12, b3} = Min{75-40, 45} = 35 dengan demikian baris-1 ( A1 ) terpenuhi. 2. Baris-2 Ongkos terkecil pada baris ke-2 terletak pada kolom-1, 3, dan 4 yaitu 2 (dapat dipilih salah 1, tetapi juga dapat menggunakan prinsip mengalokasikan komoditas sebanyak-banyaknya pada ongkos yang terkecil), sehingga dapat menggunakan cara : C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 9.doc
Hal. 4 dari 5
Max{Min(a2, b1), Min(a2, b3-X13), Min(a2, b4)} = Max{Min(30, 50), Min(30, 10), Min(30, 75)} = Max{30, 10, 30} = 30. Sehingga dapat diplih X21 atau X24 sebagai variable basis. dipilih X21 sehingga X21 = 30 sehingga baris-2 ( A2 ) terpenuhi. (Bagaimana jika dipilih X24 sebagai variable basis ?, tentukan ongkos awalnya !) 3. Baris-3 Ongkos terkecil terletak pada kolom-5 yaitu 1, maka : X35 = Min{a3 , b5} = Min {65 , 40} = 40 (kolom-5 ( T5 ) terpenuhi). Ongkos terkecil berikutnya terletak pada kolom-4 yaitu 2, maka : X34 = Min{a3−X35, b4} = Min {65−40 , 75} = 25 sehingga baris-3 ( A3 ) terpenuhi. 4. Baris-4 Ongkos terkecil terletak pada kolom-3 dan 5 yaitu 1 (pilih kolom 3, karena kolom 5 sudah terpenuhi), maka : X43 = Min{a4 , b3 − X13} = Min {80 , 45 35} = 10 sehingga kolom-3 (T3) terpenuhi, selanjutnya untuk ongkos terkecil berikutnya terletak pada kolom-4 yaitu 2, maka: X44 = Min{a4 -X43 , b4−X34} = Min{80−10, 75−25} = Min{70, 50} = 50, yang tersisa tinggal kolom-1 sehingga : X41 = Min{a4 - X43 - X44 , b1 - X21 } = Min{80-10-50, 5030} = 20, dengan demikian kolom-1 ( T1 ) dan baris-4 ( A4 ) terpenuhi. Sehingga tabelnya menjadi: T1 A1 A2 A3 A4 bj
T2 3
T3 1
40
x
4 20 50
2
40
2 50
45
1 40
1 10
4 x
25
3 X
5
2
5 x
ai
x
x
4 x
4
2 x
3
T5
x
3 X
x
2 35
2 30
T4
1 x
75
40
75 30 65 80 250
Biaya awalnya adalah : Z = C12X12 + C13X13 + C21X21 + C34X34 + C35X35 +C41X41 + C43X43 + C44X44 = 1(40) + 2(35) + 2(30) + 2(25) + 1(40) + 4(20) + 1(10) + 2(50) = 40 + 70 + 60 + 50 + 40 + 80 + 10 + 100 = 450. ii). Metode Ongkos Kolom Terkecil Langkah-langkahnya identik (sama/analog) dengan Metode Ongkos Baris Terkecil, yaitu penentuan ongkos terkecilnya berdasarkan kolom yang dimulai dari kolom ke satu, dan seterusnya. C:\Documents and Settings\Pak Yusup\My Documents\BackUp FD\Materi TRO\Modul Kuliah TRO\PERTEMUAN 9.doc
Hal. 5 dari 5
