Metode Batu Loncatan

BAB 4 4.1 METODE BATU LONCATAN •

Kita anggap bahwa pemecahan fisibel yang pertama sudah diperoleh.

•

Kemudian kotak yang terisi kita sebut kotak basis, nilainya kita beri tanda kurung buka dan tutup seperti (x ij), kalau baris i dan kolom j terisi.

•

Kotak yang tidak terisi kita sebut kotak bukan basis (nonbasis cell).

•

Ingat, semua kotak memuat biaya angkut per unit barang sebesar cij kalau 1 unit barang diangkut dari tempat asal A ke tempat tujuan T S. = Suplai atau persediaan barang di A. d = Permintaan barang dari T Z = ΣCijXij = jumlah biaya angkut yang harus dibuat minimum.

•

Agar label tidak ruwet, nilai yang menunjukkan biaya angkut tidak dicantumkan dalam tabel. Sekarang perhatikan ilustrasi berikut:

Ilustrasi 1. •

Semen diangkut dari 3 pabrik yang berlokasi di A1,A2 dan A3 ke 4 lokasi proyek yang memang membutuhkan semen. Pabrik 1, 2, dan 3 masing-masing menghasilkan semen sebanyak 6 ribu ton, 8 ribu ton, dan 10 ribu ton. Lokasi proyek 1, 2, 3 dan 4 masing-masing minta semen sebanyak 4 ribu ton, 6 ribu ton, 8 ribu ton, dan 6 ribu ton. Biaya angkut dalam ratusan ribu rupiah dapat dilihat dalam tabel berikut:

•

Pemecahan fisibel yang pertama dengan menggunakan NWCR.

•

Permintaan T1 sebesar 4 unit, dipenuhi oleh A1 yang tersedia 6 unit, jadi masih sisa 2 unit. T1, sudah terpenuhi x11 = (4). Permintaan T2 sebesar 6 unit, dipenuhi sisa dari A 1 sebesar 2 unit

x 12 = (2). Suplai A1 sudah habis. Permintaan T2, masih kurang 4 diambil dari A2, yang tersedia 8 unit. •

Jadi x22 = (4). T2, sudah dipenuhi. Permintaan T3 sebesar 8 unit, dipenuhi oleh sisa dari A2 sebanyak 4 unit, x23 = (4).

•

Persediaan di A2 sudah habis. Permintaan di T3 masih kurang 4 unit, dipenuhi dari A3 yang tersedia 10 unit, jadi x33 = (4). T3 sudah dipenuhi.

•

Di A3 masih ada sisa sebanyak 6 unit dan ini untuk memenuhi T4, jadi x34 = 6. Pemecahan fisibel yang pertama sudah diperoleh dengan nilai x 11, = 4, x 12 = 2, x 22 = 4, x 23 = 4, x 33 = 4 dan x 34 = 6.

•

Kotak yang ada nilai dengan tanda ( ), disebut kotak dalam basis sebanyak m+n-l = 3+4-1 = 6 kotak dan yang tidak memuat nilai disebut nonbasis.

•

Jumlah biaya transpor:

•

Apakah Z1 sudah minimum?

•

Untuk menjawab ini harus kita hitung semua nilai Z ij-Cij sebagai uji optimalitas untuk cell atau kotak bukan basis, kalau ternyata semua nilai Zij – Cij ≤ 0, maka pemecahan sudah minimum, kalau tidak maka pemecahan dilanjutkan sampai semua Z ij - C ij ≤ 0.

•

Nilai Zij - Cij merupakan besarnya penurunan biaya angkut yang terjadi kalau ada 1 unit barang diangkut dari Ai ke Tj disebut indeks perbaikan (improvement index). Cara menghitung Zij C ij kita harus membuat jalur atau lintasan tertutup (closed loop) mulai dari kotak nonbasis yang akan dihitung nilai (z ij - c ij )-nya.

•

Penarikan garis lurus bisa menurut baris (horizontal) atau menurut kolom (vertikal). Menurut baris, bisa bergerak ke kiri atau ke kanan, sedangkan kalau menurut kolom bisa bergerak ke atas atau ke bawah.

•

Di dalam proses penarikan garis lurus dilakukan penjumlahan (+) dan pengurangan (-) biaya dari cell yang dilalui garis lurus, dimulai dengan (+) diakhiri dengan (-) lihat contoh z 31-c 31.

•

Dari suatu kotak nonbasis (i, j) ditarik garis lurus ke kotak basis yang terdekat (dari baris atau kolom yang sama), dengan syarat bahwa kotak yang dihubungi mempunyai pasangan (partner) di kolom (baris) yang sama, kalau tidak harus dilewati atau diloncati, maksudnya agar

garis bisa terus disambung, kemudian dapat kembali ke tempat asal atau semula dengan meninggalkan cell basis terdekat. Misalnya akan dihitung z31-c31, lihat Tabel 1. •

Dari kotak (3,1), kita menuju ke kotak (3,3), terus ke kotak (2,3), dalam kolom yang sama, kemudian menuju ke kotak (2,2) dari baris yang sama, terus menghubungi kotak (1,2), dalam kolom yang sama, melanjutkan ke kotak (1,1) dan akhirnya kembali ke tempat asal yaitu kotak (3,1).

•

z31-c31 = c33 - c23 + c22 – c12 + c11 - c31, dimulai dengan tanda (+) kemudian (-) dan seterusnya berganti-ganti dari (+) ke (-). Kemudian kita masukkan nilainya.

•

Z31-c31 = 2 - 2 + 3 - 2 + 1 - 0 = 2. Nilai ini kita masukan ke kotak (3,1) lihat tanda bintang (*) pada Tabel 1. Kalau tadi bergerak ke kanan dalam baris yang sama, kita juga bisa bergerak ke atas dalam kolom yang sama dan hasilnya akan sama.

•

z31-c31 = c11 – c12 + c22 – c23 + c33 - c31 = 1 - 2 + 3 - 2 + 2 – 0 = 2

•

Dengan jalan yang sama, semua nilai zij - cij. kita hitung, kemudian nilainya kita masukkan dalam tabel.

•

Ternyata tidak semua nilai zij - cij ≤ 0, masih ada yang positif dan lebih besar dari nol, jadi pemecahan belum optimum. Nilai z1 belum minimum masih bisa diperkecil lagi.

•

Sekarang kita harus memilih kotak yang harus masuk basis sehingga terisi (memuat nilai) dan kotak yang harus keluar atau meninggalkan basis. Kriterianya sebagai berikut: o

Kotak dengan nilai zij - cij. positif terbesar harus masuk basis.

o

Kalau ada lebih dari satu kotak pilih saja salah satu, sembarangan.

Dalam soal ini, kotak (3,1) harus masuk basis sebab z31 - c31 terbesar dan positif. • Cara menentukan kotak yang harus keluar basis. Tulis kembali cara memperoleh nilai z31 – c31 = c33-c23 + c22 – c12 + c11-c31 • Perhatikan biaya dengan tanda plus (+), yaitu c33, c22, c11, dengan variabel x33, x22 , x11. Dari variabelvariabel ini kita cari yang nilainya terkecil. Kotak dengan nilai variabel terkecil ini yang harus keluar dari basis. • Min (x33, x22 , x11) = min (4, 4, 4). Karena semua nilainya sama, kita pilih salah satu, misalnya x11 = 4 = minimum. Kotak yang masuk basis ialah kotak (3, 1), dengan variabel x31. Nilai variabel ini sama dengan nilai minimum yang baru saja kita pilih, dalam hal ini, x3l = x11 = 4, di mana x3l = nilai x31 yang baru untuk diisikan dalam kotak tabel berikutnya. • Nilai variabel dari cell lainnya yang terlibat dalam pembentukan jalur/lintas (loop) diperoleh dengan aturan berikut: 1. Kalau tanda biaya +, nilai variabel baru = nilai variabel lama - nilai minimum. o

Kalau tanda biaya -, nilai variabel baru = nilai variabel lama + nilai minimum.

2.

Jadi, x’33 = x33 - 4 = 4 - 4 = 0 x’23 = x23 + 4 = 4 + 4 = 0 x’22 = x22 - 4 = 4 + 4 = 0 x’12 = x12 + 4 = 2 + 4 = 6 x’11 = x11 - 4 = 4 - 4 = 0 , keluar basis, tidak perlu ditulis •

Nilai variabel dalam kotak basis di luar lintasan atau yang tidak terlibat dalam pembentukan lintasan tidak mengalami perubahan, misalnya x’34 = x34 = 6 .

Catatan:

Angka nol untuk nilai variabel dalam kotak basis harus ditulis.

Masih ada 2 kotak yang nilainya positif, yaitu kotak (3,2) dan (2,4) di mana z32 – c32 = z24 - c24 = 1. Kita pilih kotak (2,4) yang harus masuk basis. Min (x.23, x34) = min (8, 6) = 6, kotak (3,4) yang memberikan nilai minimum dan harus keluar basis. x’24 = x34 = 6; x’23 = x23 - 6 = 8 - 6 = 2 x’33 - x33 + 6 = 0 + 6 = 6 . Nilai dari kotak lainnya yang tidak terlibat dalam pembentukan jalur,

tetap.

Ternyata masih ada satu kotak dengan nilai zij-cij positif, yaitu kotak (3,2), z32 – c32 = 1. Kotak ini hams masuk basis. Min (x 33, x22) = min (6,0) = 0, berarti kotak (2,2) harus keluar basis.

Karena semua nilai zij - cij < 0, maka pemecahan sudah optimum berarti jumlah biaya angkutan sudah minimum.

Jumlah biaya angkutan (transport) yang minimum Rp 28 ratusan ribu rupiah (= Rp 2.800.000). Suplai A1 sebanyak 6 ribu ton untuk memenuhi T2, suplai A2 sebanyak 8 ribu ton untuk memenuhi T2, sebanyak 2 ribu ton dan T4 sebanyak 6 ribu ton, suplai A3 sebanyak 10 ton, untuk memenuhi T1 sebanyak 4 ribu ton, T3 sebanyak 6 ribu ton. Nilai nol pada kotak (3,2) hanya mempunyai nilai matematis teoretis akan tetapi tidak mempunyai arti secara praktis. Pemecahan ini memerlukan 4 tabel, berarti ada 4 alternatif pemecahan, akan tetapi hanya tabel yang ke-4 merupakan pemecahan optimum. Kalau kita perhatikan setiap tabel memberikan nilai z = fungsi objektif yang semakin menurun sehingga tercapai nilai z yang minimum

Secara keseluruhan Z 1 ≥ Z 2 ≥ Z 3 ≥ Z 4 apabila ada k tabel, maka hasilnya akan seperti berikut: Z 1 ≥ Z 2 ≥ Z 3 … Zk, yang terakhir Zk = Zmin, nilainya terkecil (minimum).

Angka dalam kurung tutup, biaya angkut per unit barang dari daerah asal ke tempat tujuan, dalam satuan mata uang (smu).

Karena semua nilai z i j -c i j ≤ 0, maka pemecahan sudah optimum ZMIN = Z2 = 8. Suplai A 1 sebanyak 1 untuk memenuhi T 1 Suplai A2, sebanyak 2 untuk memenuhi T 2 Suplai A3 sebanyak 3 untuk memenuhi T1 sebanyak 1, T2 sebanyak 1 dan T3 sebanyak 1.