Transcription

SEMINAR MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2017T - 35Metode Perbaikan ASMpada Masalah Transportasi Tak SeimbangSolikhinDepartemen Matematika FSM Universitas Diponegorosoli [email protected]—Masalah transportasi adalah masalah pendistribusian barang dari beberapasumber ke beberapa tujuan dengan tujuan untuk meminimumkan biaya pengiriman.Salah satu metode langsung untuk menyelesaikan masalah transportasi adalah metodeASM. Metode ini menitikberatkan pada sel biaya tereduksi yang bernilai 0 denganindeks terkecil. Telah ditunjukkan bahwa metode ASM memberikan solusi optimaluntuk masalah transportasi seimbang, akan tetapi untuk masalah transportasi takseimbang tidak selalu memberikan solusi optimal. Oleh karena itu, perlu adanyaperbaikan. Paper ini mengkaji perbaikan dari metode ASM untuk menyelesaikanmasalah transportasi tak seimbang dan menunjukkan keoptimalan solusi yangdihasilkan. Diperoleh hasil bahwa solusi yang diperoleh dengan metode perbaikanASM pada masalah transportasi tak seimbang merupakan solusi optimal.Kata kunci: Transportasi Tak Seimbang, Metode Perbaikan ASMI.PENDAHULUANMasalah transportasi merupakan masalah pendistribusian barang dari beberapa sumber (persediaan atausupply) ke beberapa tujuan (permintaan atau demand) dengan tujuan untuk meminimumkan biayatransportasi atau memaksimumkan keuntungan [1]. Tujuan utama transportasi adalah menentukanbanyaknya barang yang optimal yang akan diangkut dari beberapa sumber ke beberapa tujuan sehinggameminimumkan total biaya transportasi.Seiring perkembangan, metode untuk mencari solusi masalah transportasi menjadi beragam. Mulai darimetode mencari solusi fisibel awal, yaitu metode Pojok Barat Laut, metode Biaya Terkecil, dan metodeVAM dengan dilanjutkan mencari solusi optimal akhir menggunakan metode Stepping Stone atau metodeMODI [1,2] hingga metode langsung tanpa mencari solusi fisibel awal.Beberapa metode langsung yang berhasil dikembangkan diantaranya Metode Zero Neigbourning [3],Metode Zero Suffix [4], Metode Zero Point [5], Metode Exponential Approach [6], Metode ASM [7] dansebagainya. Karakteristik dari beberapa metode ini menitikberatkan pada biaya hasil reduksi yang bernilainol. Pada metode Zero Neigbourning dan Zero Suffix dihitung nilai rata-rata sekitar angka 0 yang bukanbernilai 0, kemudian pengalokasian bergantung pada nilai rata-rata terbesar. Sedangkan pada metode ZeroPoint diperhatikan permintaan dan persediaan pada sel dengan biaya tereduksi 0 yang bersangkutan.Berbeda dengan metode Exponential Approach, metode ini menetapkan penalti eksponensial pada setiapsel biaya yang bernilai 0. Penalti eksponensial adalah banyaknya angka 0 pada baris ke-i dan kolom ke-jselain angka 0 yang terpilih. Pengalokasian pada sel dengan penalti eksponensial terkecil. Jika terdapatpenalti ekponensial terkecil yang sama, maka pengalokasian bergantung pada rata-rata permintaan danpersediaan terkecil untuk sel yang bersesuaian. Hampir serupa dengan metode Exponential Approach,metode ASM yang diperkenalkan oleh Abdul Quddoos, Dr. Shakeel Javaid, dan Prof. Mohd MasoodKhalid juga menetapkan indeks penalti e untuk setiap sel- ij yang bernilai 0, yang mana indeks penalti eadalah banyaknya angka 0 pada baris ke- i dan kolom ke- j dan tidak termasuk angka 0 yang terpilih padasel- ij . Pengalokasian pada sel dengan indeks penalti terkecil. Jika terdapat indeks penalti terkecil yangsama, maka pengalokasian bergantung pada hasil penjumlahan dari biaya tereduksi pada baris ke-i dankolom ke-j dari sel- ij yang bersangkutan dengan hasil penjumlahan terbesar. Jika masih terjadi kesamaan,maka memilih sel- ij (sel yang memiliki indek e terkecil yang sama) yang memiliki rata-rata persediaandan permintaan terkecil.PT-249

ISBN. 978-602-73403-2-9 (Cetak)978-602-73403-3-6 (On-line)Sebagian besar beberapa metode langsung tersebut telah berhasil memberikan solusi optimal padamasalah transportasi seimbang, sedangkan untuk masalah transportasi tak seimbang belum tentumenghasilkan solusi optimal. Untuk memperbaiki kelemahan ini telah dikembangkan metode perbaikannyaseperti metode improved Zero Neigbourning [8], metode improved zero point [9], metode improved zerosuffix [10], metode improved exponential approach [11]. Metode-metode ini mampu menyelesaikanmasalah transportasi tak seimbang.Pada [7] dibahas metode ASM untuk menyelesaikan masalah transportasi pada kasus meminimumkanbiaya. Kemudian eksistensi keoptimalannya telah ditunjukkan untuk masalah transportasi seimbang danalgoritmanya diperluas untuk transportasi kasus maksimum [12]. Hal yang sama, metode ASM juga belumtentu memberikan solusi optimal untuk masalah transportasi tak seimbang. Oleh karena itu, perlu dikajiperbaikan dari metode ASM sedemikian hingga dapat memberikan solusi optimal untuk masalahtransportasi tak seimbang. Diselidiki keoptimalan dari metode perbaikan ASM dan diterapkan pada contohsimulasi.II.HASIL DAN PEMBAHASANBagian ini menyajikan masalah transportasi baik transportasi seimbang maupun transportasi takseimbang. Metode yang digunakan untuk menyelesaikan masalah transportasi adalah metode perbaikanASM yang merupakan perbaikan atau modifikasi dari metode ASM [7]. Kemudian ditunjukkan bahwametode perbaikan ASM memberikan solusi optimal untuk masalah transportasi tak seimbang. Metode inidapat digunakan untuk menyelesaikan masalah transportasi baik seimbang maupun tak seimbang baikuntuk kasus meminimumkan biaya atau memaksimumkan keuntungan.A. Masalah TransportasiMisalkan terdapat m sumber dan n tujuan. Suatu barang x akan diangkut dari sumber i 1, 2,., mke tujuan j 1,2,., n dengan biaya angkut per unit sebesar cij , maka jumlah barang sebesar xijdikirimkan dari pusat sumber ai ke pusat tujuan b j . Model transportasi secara umum sebagai berikut:mnMin z cij xiji 1 j 1dengan kendalamn xij ai , i 1, 2,., m ; xij b j , j 1, 2,., n ; xij 0, i 1, 2,., m; j 1, 2,., n .i 1j 1Masalah transportasi dikatakan seimbang (balanced) apabila jumlah persediaan sama dengan jumlahmpermintaan , yaitun a bii 1jdan jika tidak maka dikatakan tidak seimbang.j 1Pada transportasi tak seimbang dapat diseimbangkan dengan cara menambahkan dummy sebesarmnn a bii 1jatauj 1m b ajj 1i.i 1Definisi 1. [13] Himpunan xij 0, i 1, 2,., m; j 1, 2,., n yang memenuhi kendala pada masalahtransportasi disebut solusi fisibel.Definisi 2. [13] Solusi fisibel dikatakan solusi optimal jika meminimumkan total biaya transportasi.Untuk menjamin masalah transportasi mempunyai solusi fisibel maka transportasinya harus seimbang,seperti diberikan teorema berikut ini.Teorema 3. (Eksistensi) [13] Masalah transportasi memiliki solusi fisibel jika dan hanya jika merupakanmmasalah transportasi seimbang, yaituii 1Bukti:( )Diketahuin a bmasalahj.j 1transportasimemilikisolusifisibel.x { xij 0 i 1, 2,., m; j 1, 2,., n} solusi fisibel dari masalah transportasi, maka memenuhiPT-250Misalkan

SEMINAR MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2017mn x x ai , i 1, 2,., m ;ijijj 1mniji 1 j 1mmn x aOleh karena itu diperolehJadi, b j , j 1, 2,., n ; xij 0 , i 1, 2,., m; j 1, 2,., n .i 1imn x bdaniji 1j 1 i 1.jj 1n a bii 1j.j 1( ) Diketahuimn a bmasalah transportasi seimbang, yaituii 1Misalkan xij λi b j 0 , dengan ߣ jj 1adalah faktor proporsional untuk sumber i dan supply harus didistribusikan semuanya. Karena xij λi b jmnaimaka xij λi b j , lebih lanjut xij λi b j i 1 bj 1bj .njj 1Oleh karena itu, diperolehnnaxij ( n i b j ) ai , i 1, 2,., m dan j 1j 1 bjmm x (iji 1i 1j 1aib j ) b j , j 1, 2,., n .n bjj 1Jadi ada x { xij 0 i 1, 2,., m; j 1, 2,., n} merupakan solusi fisibel masalah transportasi. Jadi masalah transportasi seimbang memiliki solusi fisibel.mnmn( P1 ) min z* ( cij ui v j )xij( P ) min z cij xiji 1 j 1i 1 j 1dengan kendaladengan kendalann xij x ai , i 1, 2,., m ai , i 1, 2,., mijj 1j 1mm xij x b j , j 1, 2,., n b j , j 1, 2,., niji 1i 1xij 0 , i 1, 2,., m; j 1, 2,., nxij 0 , i 1, 2,., m; j 1, 2,., ndimana ui , v j bilangan riil.Untuk menjamin setiap masalah transportasi memiliki solusi optimal, diberikan teorema berikut ini.Teorema 4. [14] Sebarang solusi optimal masalah transportasi ( P1 ) merupakan solusi optimal darimasalah transportasi ( P ) .Bukti: Diambil sebarang x* { xij* 0 i 1, 2,., m; j 1, 2,., n} solusi optimal dari ( P1 ) maka,mnmnmni 1j 1nmmnj 1i 1i 1j 1z * ( cij ui v j )xij* cij xij* ui xij* v j xij* z ui ai v j b j .i 1 j 1mKarena u ai ii 1 j 1ndani 1transportasi ( P) . v bj*j*tidak bergantung pada x , maka x juga solusi optimal untuk masalahj 1 Teorema 5. [14] Jika { xij0 0 i 1, 2,., m; j 1, 2,., n} solusi fisibel dari masalah transportasi ( P) dan(cij ui v j ) 0 , untuk semua i dan j, dimana ݑ dan ݒ adalah bilangan riil sedemikian sehinggaminimum dari masalah transportasi ( P1 ) bernilai 0, maka { xij0 0 i 1, 2,., m; j 1, 2,., n} adalah solusioptimal dari masalah transportasi ( P) .Bukti: Diambil sebarang { xij0 0 i 1, 2,., m; j 1, 2,., n} solusi fisibel dari ( P) , makaPT-251

ISBN. 978-602-73403-2-9 (Cetak)978-602-73403-3-6 (On-line)nm x0ij ai , i 1, 2,., m danj 1 x0ij b j , j 1, 2,., n .i 1(m)nKarena cij ui v j 0 , i, j dan min z * ( cij ui v j )xij 0 , makai 1 j 1mnmnmni 1j 1min ( cij ui v j )xij 0 min z cij xij ai ui b j v ji 1 j 1i 1 j 1dan memenuhimn xij ai , i 1, 2,., m ;j 1 xij b j , j 1, 2,., n ; xij 0 , i 1, 2,., m; j 1, 2,., n .i 1mnmnKarena z cij xij0 ai ui b j v ji 1 j 1i 1j 1dan memenuhin x0ijm ai , i 1, 2,., m ;j 1 x0ij b j , j 1, 2,., n ; xij 0 , i 1, 2,., m; j 1, 2,., n ,i 1maka ini berarti { xij0 0 i 1, 2,., m; j 1, 2,., n} solusi optimal dari ሺܲଵ ሻ. Berdasarkan Teorema 4,maka { xij0 0 i 1, 2,., m; j 1, 2,., n} solusi optimal dari ሺܲሻ. B. Metode Perbaikan ASMMetode Perbaikan ASM merupakan metode langsung yang merupakan perbaikan dari metode ASM.Kelebihan dari metode ini adalah dapat digunakan untuk menyelesaikan masalah transportasi tak seimbangdan memberikan solusi optimal. Metode ini juga dapat digunakan baik untuk kasus minimum maupunkasus maksimum.mnLemma 6. Diberikan z cij xij , cij 0, xij 0, i, j , maka maks z min ( z ) .i 1 j 1Bukti: Misalkan maks z a . maks z a maks z a a x, x z a x, x z a x, x z a y, y z a min ( z ) .Jadi, maks z min ( z ) . Langkah-langkah atau algoritma metode Perbaikan ASM. Algoritma ini mengacu pada [7], [9], dan[11].1.Membentuk Tabel Transportasi SeimbangUntuk masalah transportasi kasus minimum biaya cij tetap, sedangkan kasus maksimum diubahmenjadi cij . Membuat tabel transportasi seimbang dengan menambahkan dummy pada baris atau2.3.4.5.kolom dengan biaya awal 0.Reduksi Tabel Transportasi dengan dummyJika baris dummy yang ditambahkan, maka ke langkah ke-3. Kemudian mengganti biaya dummydengan biaya terbesar dari hasil reduksi baris. Selanjutnya ke langkah ke-4 kemudian langkah ke-3.Jika kolom dummy yang ditambahkan, maka ke langkah ke-4. Kemudian mengganti dummy denganbiaya terbesar dari hasil reduksi kolom. Selanjutnya ke langkah ke-3 kemudian langkah ke-4.Reduksi BarisMengurangi setiap entri baris dengan masing-masing biaya terkecilnya, yaitu cij ui .Reduksi KolomMengurangi setiap entri kolom dengan masing-masing biaya terkecilnya, yaitu cij ui v j .Mengecek Baris Persediaan dan Kolom PermintaanMengecek apakah setiap b j ai pada kolom dan apakah setiap ai b j pada baris yang biayatereduksinya 0 ( cij ui v j 0 ) . Jika kondisi terpenuhi ke langkah ke-8. Jika tidak ke langkah ke-6.PT-252

SEMINAR MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 20176.Membuat Garis Horisontal dan VertikalMembuat garis horisontal dan vertikal seminimum mungkin pada baris dan kolom yang bernilai 0sedemikian sehingga biaya yang tidak memenuhi pada langkah ke-5 tidak tertutup.Revisi Angka Nol pada Garis Horisontal dan VertikalMemilih biaya terkecil pada sel yang tidak terlewati garis. Mengurangi semua biaya pada sel yangtidak terlewati garis dengan biaya terpilih terkecil dan menambahkan dengan biaya terpilih terkecilpada setiap sel yang terlewati dua garis. Kembali ke langkah ke-5.Penetapan indeksMenetapkan indeks e untuk setiap sel- ij yang bernilai 0, yang mana indeks e adalah banyaknyaangka 0 pada baris ke- i dan kolom ke- j dan tidak termasuk angka 0 yang terpilih pada sel- ij .PengalokasianMemilih angka nol dengan indeks e terkecil dan mengalokasikan sel dengan jumlah terbesar yangmungkin dengan melihat persediaan dan permintaan sel yang yang bersangkutan. Jika terdapat indekse terkecil yang sama (lebih dari satu), maka menghitung masing-masing jumlah cij' cij ui v j7.8.9.pada baris ke- i dan kolom ke- j dari sel- ij yang bersangkutan (sel yang memiliki indek e terkecilyang sama) dan mengalokasikan sebesar mungkin pada sel dengan hasil penjumlahan terbesar. Jikamasih terjadi kesamaan, maka memilih sel- ij (sel yang memiliki indek e terkecil yang sama) yangmemiliki rata-rata persediaan dan permintaan terkecil.10. Perbaikan Tabel TransportasiMembuat tabel transportasi baru untuk perhitungan selanjutnya dengan mengabaikan baris ataukolom yang permintaan atau persediaannya telah terpenuhi. Mengecek apakah tabel transportasi barumemiliki paling sedikit satu angka 0 pada setiap baris dan kolom.Jika tidak, kembali ke langkah ke-3 dan ke-4 kemudian ke langkah ke-5.11. Mengulangi langkah ke-8 sampai langkah ke-10 sedemikian sehingga semua permintaan terpenuhidan semua persediaan habis.Diberikan masalah transportasi tak seimbang.mn( P2 ) min z cij xiji 1 j 1dengan kendalamn xij x ai , i 1, 2,., m ;ijj 1mn a b b j , j 1, 2,., n ;ii 1i 1j; xij 0 ,j 1i 1, 2,., m; j 1, 2,., nTeorema 7. Solusi yang diperoleh dengan metode perbaikan ASM untuk sebarang masalah transportasitak seimbang ( P2 ) merupakan solusi optimal.Bukti: Diberikan sebarang masalah transportasi tak seimbangmn(kasus minimum dengann a bii 1( P2 )j). Hal ini berarti penambahan baris dummy sebesarj 1m b ajj 1i, sehingga diperolehi 1masalah transportasi seimbang ( P ) . Misalkan ui nilai terkecil dari baris ke-݅ dan v j nilai terkecil darikolom ke- j (kecuali baris dummy). Reduksi baris-kolom diperoleh cij ui v j 0 , untuk semua i danj . Menetapkan indeks pada setiap sel bernilai 0 dan mengalokasikan sebesar mungkin pada indeksterkecil. Diperoleh solusi{xij 0 i 1, 2,., m; j 1, 2,., n} untuk masalah transportasi yang matriksbiayanya, dengan xij 0 untuk cij ui v j 0 dan xij 0 untuk cij ui v j 0 . Oleh karenamnmin z * ( cij ui v j )xij 0danmemenuhikendala( P1 )makamenuruti 1 j 1{xij 0 i 1, 2,., m; j 1, 2,., n} solusi optimal dari masalah transportasi ሺܲሻ. PT-253Teorema5,

ISBN. 978-602-73403-2-9 (Cetak)978-602-73403-3-6 (On-line)C. Simulasi NumerikDiberikan contoh penggunaan metode perbaikan ASM pada transportasi tak seimbang dengan kasusdemand lebih besar atau sama dengan supply.Conto Masalah Transportasi Tak SeimbangSumberATujuan (dalam ribuan rupiah)PQ580 ݔ 12 ݔ 13 ݔ ଶଵ41 ݔ ଶଶ ݔ ଶଷ9CDemand11supplyS ݔ 1110BR276 ݔ ଷଶ ݔ ଷଷ ݔ 4035170Tujuan (dalam 660Dummy00005Demand70254035170Tujuan (dalam aris ketiga juga tidakb j ai danmemenuhi ai b j . Sehingga membuatgaris horizontal dan vertikal.supplyPQRSA580260B930645C6803SumberTujuan (dalam y00005Demand70254035170Penggantian biaya dummy dengan biayatereduksi baris terbesar.Tujuan (dalam ribuanrupiah)DummyDemandKolomReduksi ASumberACRPTujuan (dalam ribuanrupiah)PQReduksi barisPenambahan dummy pada barisSumberTujuan (dalam ribuanrupiah)P45 ݔ ଶସ ݔ ଷଵSumber60 ݔ 143Reduksi kolomDummy02535Demand70254035170Revisi angka nolsupplySumberTujuan (dalam my036352540Diperolehmemenuhi.PT-254supplyPb j ai35dan170ai b j

SEMINAR MATEMATIKA DAN PENDIDIKAN MATEMATIKA UNY 2017Penentuan indeksSumberTujuan (dalam ribuanrupiah)SumberTujuan (dalam galokasian ke indeks terkecil danpenentuan indeks kembali.SumberTujuan (dalam 102015653200360Demand6354035170SumberTujuan (dalam nd702035170SumberTujuan (dalam oleh solusi optimal dengan biaya totalz 735 . Jika diselesaikan dengan programPOM for Windows.supplyR2060B6004600Tujuan (dalam ribuanrupiah)PsupplyCPersediaanPengalokasian ke indeks terkecil dandiperoleh solusi optimal.Pengalokasian ke indeks terkecil danpenentuan indeks kembali.Sumber0201C0120STujuan (dalam ribuanrupiah)60032502BDummyR02PsupplyQPT-255

ISBN. 978-602-73403-2-9 (Cetak)978-602-73403-3-6 (On-line)III.SIMPULAN DAN SARANMetode perbaikan ASM merupakan perbaikan atau pengembangan dari metode ASM yang dapatdigunakan untuk menyelesaikan masalah transportasi tak seimbang baik pada kasus meminimumkan biayamaupun memaksimumkan keuntungan. Metode ini memberikan solusi optimal untuk masalah transportasitak seimbang. Metode perbaikan ASM cukup sederhana dan mudah untuk diaplikasikan.DAFTAR Siswanto, Operation Research. Jakarta: Erlangga, 2016.W. L. Winston, Operations Research Applications and Algoritms, 4th ed., New York : Duxbury, 2004.K. Thiagarajan, H. Saravanan, and P. Natarajan, “Finding on Optimal Solution for Transportation Problem- ZeroNeighbouring Method,” Ultra Scientis, vol. 25A, pp. 281–284, July 2013.M. R. Fegade, V. A. Jadhav, and A. A. Muley, “Solving Fuzzy Transportation Problem Using Zero Suffix and Robust RankingMethodology,” IOSR Journal of Engineering (IOSRJEN), vol. 2, pp. 36–39, July 2012.Gaurav Sharma, S. H. Abbas, and V. K. Gupta, “Optimum Solution of Transportation problem with the help of Zero PointMethod,” International Journal of Engineering Research & Technology (IJERT), vol. 1, pp. 1–6, July 2012.S. Ezhil Vannan and S. Rekha, “A New Method for Obtaining an Optimal Solution for Transportation Problem,” InternationalJournal of Engineering and Advanced Technology (IJEAT), vol. 2, pp. 369–371, June 2013.A. Quddoos, S. Javaid, and M. M. Khalid, “A New Method for Finding an Optimal Solution for Transportation Problems,”International Journal on Computer Science and Engineering (IJCSE), vol. 4, pp. 1271–1274, July 2012.D. Nofita S., “Metode Improved Zero Neighbouring pada Masalah Transportasi,” Skripsi, Semarang: Universitas Diponegoro,2016.A. Edward Samuel, “Improved Zero Point Method (IZPM) for the Transportation Problems,” Applied Mathematical Sciences,vol. 6, pp. 5421-5426, May 2012.P. Jayaraman and R. Jahirhussian, “Fuzzy Optimal Transportation Problems by Improved Zero Suffix Method via RobustRank Techniques,” International Journal of Fuzzy Mathematics and Systems, vol. 3, pp. 303 - 311, July 2013.D. A. Hidayat, “Metode Improved Exponential Approach dalam Menentukan Solusi Optimum pada Masalah Transportasi,”Skripsi, Semarang: Universitas Diponegoro, 2016.A. R. Septiana, “Metode ASM dalam Menentukan Solusi Optimal pada Masalah Transportasi,” Skripsi, Semarang: UniversitasDiponegoro, 2017.S. Mohanaselvi and K. Ganesan,”Fuzzy Optimal Solution to Fuzzy Transportation Problem: A New Approach,” InternationalJournal on Computer Science and Engineering (IJCSE), vol. 4, pp. 367–375, March 2012.[14] P. Pandian and G. Natarajan, “A New Algorithm for Finding a Fuzzy Optimal Solution for Fuzzy Transportation Problems, “Applied Mathematical Sciences, vol. 4, pp. 79–90, May 2010.PT-256

metode mencari solusi fisibel awal, yaitu metode Pojok Barat Laut, metode Biaya Terkecil, dan metode VAM dengan dilanjutkan mencari solusi optimal akhir menggunakan metode Stepping Stone atau metode MODI [1,2] hingga me