Persoalan Transportasi 1

BAB 4Persoalan Transportasi 4.1 PENDAHULUAN •

Persoalan transportasi merupakan persoalan linear programming.

•

Bahkan aplikasi dari teknik linear programming pertama kali ialah dalam merumuskan persoalan transportasi dan memecahkannya.

•

Persoalan transportasi yang dasar pada mulanya dikembangkan oleh F.L. Hitchcock pada tahun 1941 dalam studinya yang berjudul: The distribution of a product from several sources to numerous locations.

•

Ini merupakan gizi dari persoalan transportasi yaitu mengangkut sejenis produk tertentu katakan beras, minyak, daging, telur, tekstil, pupuk dan jenis produk lainnya dari beberapa daerah asal (pusat produksi, depot minyak, gudang barang) ke beberapa daerah tujuan (pasar, tempat proyek, tempat permukiman, daerah transmigrasi), pengaturan harus dilakukan sedemikian rupa agar jumlah biaya transportasi minimum.

•

Pada tahun 1947, TC Koopmans secara terpisah menerbitkan suatu hasil studi mengenai: Optimum utilization of the transportation system.

•

Selanjutnya, perumusan persoalan LP, dan cara pemecahan yang sistematis dikembangkan oleh Prof. George Danzig yang sering disebut bapak linear programming. Prosedur pemecahan yang sistematis tersebut disebut metode simpleks.

4.2 PERUMUSAN PERSOALAN TRANSPORTASI SECARA UMUM •

Misalkan suatu jenis barang diangkut dari beberapa daerah asal ke beberapa daerah tujuan. Misalnya ada m daerah asal: A1, A2, ..., Ai, ...,Am dan n daerah tujuan: T1, T2 ,..., Tj ,..., Tn

•

Di daerah asal Ai tersedia barang yang akan diangkut (supply) sebanyak S. dan di tempat tujuan barang tersebut diminta sebanyak d (demand).

•

xij= jumlah barang yang diangkut (dalam satuan) dari Ai ke Tj

•

cij= besarnya biaya untuk 1 unit barang tersebut dari Ai ke Tj

•

Dengan demikian untuk mengangkut xij unit diperlukan biaya cijxij

•

Jumlah permintaan (total demand) = jumlah penawaran (total supply).

•

Perhatikan tabel berikut yang menggambarkan permintaan dari setiap tempat tujuan dan penawaran/persediaan dari setiap tempat asal, juga besarnya biaya cij dengan tanda kurung buka.

Perumusan persoalan LP menjadi:

Contoh: Misalnya ada 2 gudang untuk menyimpan barang dan ada 3 toserba ke mana barang-barang dari gudang diangkut akan dijual. Bentuk tabel menjadi:

Perumusan persoalan LP menjadi:

Setelah dijabarkan menjadi:

4.3 METODE UNTUK MEMPEROLEH PERMULAAN YANG FISIBEL

PEMECAHAN

•

Salah satu cara untuk memperoleh pemecahan ialah apa yang disebut Vogel's Approximation Method yang disingkat dengan VAM.

•

Penerapan metode ini walaupun tidak selalu menghasilkan pemecahan optimum akan tetapi bisa juga memberikan pemecahan yang optimal. Perhatikan llustrasi berikut.

•

Perusahaan "A" mempunyai 3 pabrik sebagai daerah asal barang dan 5 gudang untuk menyimpan barang hasil produksi pabriknya. Barang harus diangkat dari pabrik ke gudang untuk disimpan. Barang yang diangkut jumlahnya tidak melebihi produksi yang ada sedangkan jumlah barang yang disimpan di gudang harus ditentukan jumlah minimumnya agar gudang tidak kosong, sayang karena sudah disewa. Data yang ada seperti terlihat dalam tabel berikut menunjukkan jumlah produksi yang paling banyak bisa diangkut, jumlah minimum yang harus disimpan di gudang dan biaya angkut per unit barang dalam satuan mata uang (smu).

Perumusan persoalan LP menjadi

Prosedur pemecahan permulaan yang fisibel dengan VAM. (1)Hitung perbedaan antara dua biaya terkecil dari setiap baris dan kolom. Nilai perbedaan

(selisih) ditulis di samping/di pinggiran dan disebut hukuman baris/kolom (row/column penalty). (2)Pilihlah baris atau kolom dengan nilai hukuman terbesar. Kemudian beri tanda kurung buka dan tutup. Dalam hal ada dua nilai terbesar yang sama, pilih baris/kolom yang dapat memindahkan barang terbanyak. (3)Dari baris/kolom yang terpilih dari (2), tentukan jumlah barang yang bisa diangkut dengan memperhatikan pembatasan yang ber- laku bagi baris dan bagi kolom serta cel dengan biaya terkecil. Cel atau kotak adalah tempat perpotongan garis dan kolom. (4)Hapus baris dan kolom yang sudah memenulii syarat sebelumnya, artinya suplai sudah habis atau permintaan sudah dipenuhi. (5)Ulangi langkah (1) sampai dengan (4) sehingga semua alokasi sudah dilakukan.

•

Nilai hukuman baris terbesar = 20 dan untuk kolom = 30 (lebih besar), maka kolom 2 dihapus. Karena biaya terkecil = 40, berada pada kotak atau cel (3,2), maka x32 = 400 dan kotak lainnya pada kolom (2) semuanya nol, artinya x12 = x22 = 0. Permintaan G2 sudah dipenuhi. Di P3 masih ada sisa persediaan 700 (1100-400).

•

Nilai hukuman baris terbesar 20, untuk kolom 10, pilih baris pertama yang dihapus, permintaan sebesar 800 langsung dipenuhi x]5= 800, nilai untuk kotak lainnya pada baris pertama nol, artinya x11 = x12 = x13 = 0. Karena permintaan pada G5 sudah dipenuhi, maka G5 juga dihapus.

•

Nilai hukuman baris terbesar 20, untuk kolom 40, kolom pertama dihapus, x11 = 400, nilai kotak lainnya pada kolom 1, semuanya nol, artinya x21 = 0.

•

Nilai hukuman baris terbesar 10, untuk kolom juga 10, kolom ketiga (G3) dihapus, x33 = 500, nilai kotak lainnya nol, yaitu x23 = 0. Di P3 masih sisa 200. Nilai x24 = 200, sebab nilai hukuman terbesar. Sisanya untuk x34 = 200. Kita peroleh pemecahan pertama yang fisibel sebagai berikut:

Ilustrasi 2 Ada 4 daerah asal (A1 ,A2, ,A3 ,A4) dan 5 daerah tujuan (T1, T2, T3 T 4 , T 5 ). Suatu jenis barang akan diangkut dari 4 daerah asal ke 5 daerah tujuan. Suplai dari daerah asal dan permintaan dari daerah tujuan serta biaya angkut per unit barang dapat dilihat dalam tabel berikut:

•

Nilai hukuman baris terbesar = 3 dan untuk kolom 19, lebih besar, kolom 4 dihapus, x44 = 40, sebab kotak (4,4) biayanya 0, terkecil. Nilai di kotak lainnya untuk kolom 4 semuanya nol, yaitu x14 = x24 = x34= 0, sebab semua permintaan sudah dipenuhi. Ini merupakan tahap 1, Suplai baris 4 tinggal 10.

•

N ilai

hukuman baris terbesar = 3 dan untuk kolom = 16, lebih besar, x45 = 10. Karena suplai A4 habis, maka nilai di kotak lainnya untuk baris 4 semuanya nol, yaitu x41 , x42 , x43 = 0. Permintaan di T5 masih ada 50 (= 60-10) yang belum dipenuhi.

•

Nilai hukuman baris terbesar 3 dan untuk kolom 4, lebih besar, kolom T2 dihapus x32 = 40. Permintaan di T2 sudah terpenuhi, x12 = x22 = 0. Di A3 masih tersedia 50 (= 90-40).

•

Nilai hukuman baris terbesar 2 dan untuk kolom 3, lebih besar, kolom T1 dihapus. Kotak (2,1) biayanya 15 terkecil, maka x21 = 30. Permintaan di T1 sudah dipenuhi, jadi x21 = 30 dan x11 = x31 = 0. Di A2 masih tersisa 30 (= 60-30).

Catatan: M merupakan suatu nilai yang besar sekali apabila dibandingkan dengan nilai lainnya yang menunjukkan biaya. Dengan demikian nilai hukuman baris A merupakan yang terbesar. Baris A3 dihapus, X33 = 50. sebab kotak (3, 3) dengan biaya 18, terkecil di baris A3 Permintaan di baris A3 sudah dipenuhi, X35 = 0. Permintaan di T 3 masih 20 yang belum dipenuhi.

•

Nilai hukuman pada baris terbesar 3 dan pada kolom 1, hukuman pada baris lebih besar, x23

= 20. Permintaan pada kolom T3 sudah dipenuhi, sehingga x13 Masih ada sisa 10 pada A2

= 0 dan T3 dihapus.

•

Nilai 10 untuk kotak (2, 5) dan nilai 40 untuk kotak (1,5), artinya x15= 40 dan x25= 10. Suplai dari daerah asal sudah habis dan permintaan dari daerah tujuan sudah terpenuhi. Pemecahan fisibel yang pertama sudah selesai. Ternyata metode VAM ini cukup panjang. Walaupun demikian pengalaman praktik menunjukkan bahwa hasil pemecahan fisibel pertama dari VAM sudah mendekati pemecahan optimum.

•

Hasil pemecahan fisibel yang pertama menurut VAM adalah sebagai berikut:

Catatan:

VAM tidak menjamin suatu penyelesaian yang optimum, akan tetapi sangat berguna karena alasan berikut ini. (1)Sering menghasilkan pemecahan optimum. (2)Dapat menghasilkan penyelesaian yang mendekati optimal dengan usaha yang tidak banyak, sehingga dapat dipergunakan untuk melangkah menuju kc pemecahan yang optimal. Cara yang kedua disebut north west corner rule yang selanjutnya disebut metode WCR, dengan prosedur sebagai berikut: (1)Pengisian eel atau kotak dimulai dari ujung kiri sebelah atas (north west corner). (2)Alokasikan jumlah maksimum (terbesar) sesuai dengan syaratnya, sehingga fisibel, untuk memenuhi permintaan. (3)Bergerak ke kotak sebelah kanan apabila masih terdapat suplai yang cukup. Apabila tidak cukup, bergerak ke kotak di bawahnya.Bergerak terus sampai suplai habis dan semua permintaan sudah dipenuhi.

Pemecahan Fisibel

•

x11 = 8, T1 sudah terpenuhi. Baris pertama sisa 1 (= 9 - 8), ini merupakan nilai x12 untuk memenuhi T2 sebesar 6, jadi masih kurang 5, dengan demikian x22 = 5. T2 sudah terpenuhi.

•

Ada sisa 1 (= 6-5), ini merupakan nilai x23 untuk memenuhi T3 sebesar 6. Di T3 masih kekurangan 5, dengan demikian x33 = 5. T1 sudah dipenuhi. Suplai habis dan semua permintaan sudah dipenuhi. Pemecahan fisibel yang pertama sudah didapat. Akan tetapi ini belum merupakan pemecahan yang optimum.

•

x11 = 400 (pilih yang terkecil antara nilai pada P] dan G1 yaitu antara 400 dan 800)

•

G1 sudah dipenuhi. Di P1 masih sisa 400 (= 800-400), untuk memenuhi G2 jadi x 1 2 = 400.

•

G2 sudah dipenuhi dan P2, sudah habis persediaannya.

•

Permintaan di G3 sebesar 500, dipenuhi dari P2 yang tersedia 600, jadi x23 = 500.

•

Di P2 masih ada sisa 100, ini untuk memenuhi permintaan G4 sebesar 400, nilai x24 = 100.

•

Persediaan P2 sudah habis. Permintaan di G4 masih kurang 300, ini diambil dari P3 jadi x34 = 300.

•

Permintaan di G4 sudah terpenuhi. Di P3 masih ada sisa sebesar 800 dan ini untuk memenuhi G5 jadi x35 = 800.

•

Karena semua syarat sudah dipenuhi maka pemecahan fisibel yang pertama sudah diperoleh.

•

Cell basis diberi tanda kurung buka dan kurung tutup. yaitu ( ). Banyaknya cell basis harus m+n-l, kalau tidak harus ada cell bukan basis yang harus diberi (0), nol kurung buka dan kurung tutup. Pemecahan ini belum optimum, masih perlu dilanjutkan.

•

Secara sepintas lalu, metode VAM lebih panjang dari NWCR, akan tetapi di atas sudah disebutkan bahwa VAM akan memberikan hasil yang sudah mendekati optimum, bahkan sering kali memberikan hasil yang optimum.

•

Ada dua cara untuk memperoleh pemecahan yang optimum yaitu: (1). Metode batu loncatan (stepping stone method) dan (2). Modified distribution method (MODI).