DAFTAR ISI

MASALAH TRANSPORTASI DAN PENUGASAN2PENDAHULUAN2MASALAH TRANSPORTASI2Model Masalah Transportasi2Metode Simpleks Singkat Untuk Masalah Transportasi6MASALAH PENUGASAN8Model Masalah Penugasan8Algoritma Khusus Untuk Masalah Penugasan10

MASALAH TRANSPORTASI DAN PENUGASANPENDAHULUANMetoda transportasi merupakan suatu metoda yang digunakan untuk mengatur distribusi dari sumber-sumber yang menyediakan produk yang sama, ke tempat-tempat yang membutuhkan secara optimal. Alokasi produk ini harus di atur sedemikian rupa, karena terdapat perbedaan biaya alokasi dari satu sumber ke tempat-tempat tujuan berbeda-beda, dan dari beberapa sumber ke suatu tempat tujuan juga berbeda-beda. Selain itu metoda transportasi juga dapat digunakan untuk memecahkan masalah-masalah dunia usaha lainnya, seperti masalah-masalah yang meliputi periklanan, pembelanjaan modal, dan alokasi dana untuk infestasi, analisis lokasi, keseimbangan lini perakitan dan perencanaan serta scheduling produksi.MASALAH TRANSPORTASI

(75) c1 w1 (-80)

W2 (-65)(125) c2W3 (-70)

(100) c3W4 (-85)

Dari gambar di atas tanda anak panah menunjukan rute yang mungkin terjadi. Angka pada anak panah menunjukan biaya pengiriman untuk setiap unit beban untuk rute tersebut. Kotak yang di letakkan di setiap lokasi menunjukkan jumlah beban truk yang akan dikirim keluar dari lokasi tersebut.( sehingga dinyatakan dengan bilangn negatif )Masalah diatas merupakan masalah program linear dari masalah transportasi. Untuk membuat masalah ini notasi Z digunakan untuk menyatakan biaya pengiriman total dan merupakan jumlah beban truk yang akan dikirimkan dari pabrik i ke tempat pendistribusian j. Dengan demikian, tujuannya adalah memilih nilai dari 12 variabel keputusan sehingga:Minimalkan Model Masalah TransportasiUntuk menyelesaikan model umum masalah transportasi, kita perlu menggunakan istilah khusus, secara khusus masalah transportasi memperhatikan aktivitas mendistribusikan suatu komoditi dari sekumplan pusat suplai, disebut sumber. Kebeberapa kelompok penerima disebut tujuan. Tujuan yang hendak tercapai adalah meminimalkan total biaya distribusi. Masing-masing sumber suplai unit tertentu untuk di distribusikann ke tujuan, dan masing-masing memiliki suplai unit tertentu untuk diterima dari sumber.Asumsi yang di syaratkan: masing-masing sumber memiliki suplai yang tetap untuk unit, dimana seluruh penawaran pasti didistribusikan ke tujuan. (Kita misalkan sebagai jumlah unit yang ditawarkan sumber i untuk i=1,2,...m) begitu juga masing-masing tujuan memiliki permintaan yang tetap untuk unit, dimana seluruh permintaan ini harus di terima dari sumber. (kita misalkan sebagai jumlah unit yang diterima tujuan j, untuk j=1,2,...,n)Sifat solusi layak: sebuah masalah transportasi memiliki solusi layak jika hanya jika

Tabel terminologi dalam masalah transportasiContoh prototipMasalah umum

Muatan truk berupa kacang kalengTiga pabrik pengalenganEmpat gudangOutput dari pabrik pengalengan iAlokasi untuk gudang jBiaya pengiriman permuatan truk dari i ke jUnit komoditim sumbern tujuansuplai s dari sumber ipermintaan d dari tujuan jbiaya yang didistribusikan dari i ke j

Dalam beberapa permasalahan rill suplai sebenarnya merupakan jumlah maksimum yang didistribusikan. Begitu juga dalam kasus lain, permintaan menunjukan jumlah maksimun yang di terima. permasalahn permasalahan semacam ini tidak sepenuhnya memenuhi model untuk masalah transportasi karena melanggar asumsi yang disyaratkan. Namun masalah masih bisa dirumuskan ulang sehingga cocok dengan model yang menggunakan sebuah tujuan dummy atau sumber dummy untuk mengambil slack di antara jumlah yang sebenarnya dengan jumlah maksimum yang didistribusikan.Asumsi biaya: biaya mendistribusikan dari sumber apapun ke tujuan apapun bersifat proporsional secara langsung terhadap jumlah unit yang didistribusikan. Oleh karena itu, biaya ini diperoleh dari unit biaya distribusi kali jumlah unit yang didistribusikan.Satu-satunya data yang diperlukan untuk model masalah transportasi merupakan suplai, permintaan dan unit biaya. Data-data tersebut merupakan parameter model. Semuanya dapat diringkas dengan tabel parameter sebagai berikut:

TabelsumberBiaya perunit yang didistribusikanSuplai

Tujuan

1 2 3 4

12...4 .... .... ... ... .... .... ....

...

permintaan

model: setiap masalah memenuhi model untuk masalah transportari jika bisa dideskripsikan secara lengkap dalam tabel parameter dan memenuhi asumsi yang di syaratkan dan asumsi biaya. Tujuannya adalah meminimalkan total biaya pendistribusian unit.Misalkan saja Z merupakan total biaya distribusi dan merupakan jumlah unit yang didisribusikan dari sumber i ke tujuan j. Perumusan linear masalah ini adalahMisalkan

Sesuaikan dengan untuk i=1,2,...,m, untuk j=1,2,...,n,Danuntuk semua ij.Untuk banyak aplikasi jumlah penawaran dan permintaan dalam model () memiliki nilai-nilai bilangan bulat, dan implementasinya mensyaratkan jumlah distribusi () juga memiliki nilai bilangan bulat. Sifat solusi bilangan bulat: untuk masalah transportasi dimana setiap memiliki sebuah nilai bilangan bulat, semua variabel basis dan setiap sosusi basis layak, termasuk yang optimal juga memiliki nilai-nilai bilangan bulat. Contoh dengan sebuah tujuan dummyNorthern airplane compani membangun pesawat komersial untuk beberapa maskapai di seluruh dunia. Tahap terakir dalam proses produksi adalah memproduksi mesin jet dan kemudian memasangnya dalam pesawat lengkap. Perusahaan telah bekerja berdasarkan beberapa kontrak untuk mengirimkan sejumlah pesawat dalam waktu dekat. Dan produksi mesin petunjuk ini sekarang harus dijadwalkan untuk empat bulan kedepan.Untuk mengetahui tanggal pengiriman sesuai kontrak, perusahaan harus menyediakan mesin untuk pemasangan dalam jumlah yang di tunjukan dalam tabel. Jadi jumlah komulatif yang di produksi akhir bulan 1,2,3, dan 4 masing-masing paling sedikit 10,25,50, dan 70.Data jadwal produksi untuk Northern airplane cobulanPemasangan yangDi jadwalkanProduksi maksimumUnit biaya* produksiUnit biaya* penyimpanan

123410152520253530101.081.111.101.130.0150.0150.015

Biaya dinyatakan dalam jutaan dolarTabel parameter untuk Northern airplane cosumberBiaya perunit yang didistribusikanSuplai

Tujuan

1 2 3 4

12341,080 1,095 1.110 1.125? 1,110 1.125 1.140? ? 1.100 1.115? ? ? 1.130????

permintaan10 15 25 20

Perumusan salah satu cara merumuskan model matematika untuk masalah ini adalah misalkan menjadi jumlah mesin jet yang di produksi dalam bulan j. Untuk j=1,2,3,4. Dengan hanya menggunakan empat variabel keputusan ini masalah dapat dirumuskan sebagai masalah pemrograman linear yang tidak cocok dengan jenis masalah transportasi.Di sisi lain dengan mengadopsi sudut pandang yang berbeda kita bahkan dapat merumuskan masalah sebagai masalah transportasi yang membutuhkan lebih sedikit usaha untuk menyelesaikannya. Sudut pandang ini akan menggambarkan masalah dalam hal tujuan dan sumber dan kemudian mengidentifikasikan , .Oleh karena unit yang didistribusikan merupakan mesin jet, masing-masing dijadwalkan untuk produksi dalam bulan tertentu dan kemudian dipasang dalam bulan Sumber i = produksi mesin jet dalam bulan i(i=1,2,3,4)Tujuan i = pemasangan mesin jet dalam bulan j(j=1,2,3,4) = jumlah mesin jet yang di produksi dalam bulan i untuk pemasangan dalam bulan j = biaya yang dihubungkan dengan masing-masing unit = biaya per unit untuk produksi dan setiap penyimpanan ? = ? = jumlah pemesanan terjadwal dalam bulan jOleh karena tidaklah mungkin memproduksi mesin dalam waktu satu bulan untuk pemasangan yang lebih awal, harus bernilai nol jika i > j. Oleh karena biaya ril yang bisa dihubungkan dengan . Namun, agar masalah transportasi bisa terdevinisi baik sehingga prosedur solusi. dapat digunakan beberapa nilai agar masalah nilai bisa teridentifikasi sebagai nilai tak dikenal. Kita bida menggunakan metode big m.Angka angka yang perlu dimasukan ke dalam kolom tidaklah jelas karena suplai, jumlah yang di produksi masing masng bulan, bukan merupakan jumlah yang benar namun kita perlu menugaskan beberapa angka. Namun kita perlu menugaskanbeberapa angka tetap ke setiap entri dalam tabel, termasuk entri yng terdapar dalam kolom suplai, sehingga bisa memeiliki masalah trasportasi sebuah tanda diberikan melalui fakta bahwa walaupun kendala supalai tidak berada dalam bentuk biasa, kendala kendala ini benar dan dalam bentuki atas dalam jumlah yang bisa di suplai yaitu:

Satu satunya perubahan dari model standar untuk masalah trasportasi adalah kendala kendala ini bentu pertidaksamaan, bukan persamaanUntuk mengubah pertidaksamaan menjadi persamaan sehingga meyesuaikan model trasportasi, kami menggunakan variabel slack. Dalam kontex ini, yang m menjadi variabel slack adlah lokasi pada tujuuan dummy tunggal yang menggambarkan kappasitas produksi tak terpakai dalam masing masing bulan. Perubahan ini menungkinkan penawaran dalam perumusan model trasportasi menjadi kapasitas produksi total dalam bulan tertentu. Terlebih lagi, olah karena permintaan untuk tujuan dummyadlah total kapsitas tak terpakai, permintaan ini adlah(25+25+30+10)-(10+15+25+20)=30Entri biaya yng di hubungkan dengan tujuan dummy sebaiknya bernilai nol karena tak ad biaya yang ditimbulkan oleh alokasi fiktif. (entri biaya m tak sesuai dengan kolaom ini karena kita tidak ingin memaksa nilai menjadi nol disini nilai nilai perlu dijumlahkan menjadi 30).Dengan permintaan ini, jumlah penawaran saat ini sama dengan jumlah permintaan yang syaratnya di tentukan oleh sifat solusi layak karena memiliki solusi layak.

Metode Simpleks Singkat Untuk Masalah TransportasiOleh karena masalah tranportasi hanyalah merupakan masalah pemrograman linier tipe khusus,masalah ini bisa diselesaikan dengan menggunakan metode simpleks yang dibahas dalam Bab 4. Namun,anda akan melihat dalam bagian ini bahwa beberapa jalan pintas perhitungan bias dilakukan dalam metode ini dengan memanfaatkan stuktur khusus yang terlihat dalam Tabel 8.6. kita akan menyebut prrosedur singkat ini metode simpleks transportasi.Menyusun Metode Simpleks Transportasi.Untuk menyorot penyingkatan yang dicapai dalam metode simpleks transportasi,pertama-tama mari kita lihat bagaimana metode simpleks umumnya( belum disingkat )akan menyiapkan masalah transportasi dalam bentuk tabular. Setelah menyusun tabel koefisien kendala( lihat tabel 8.6 ),mengubah fungsi tujuan ke bentuk maksimalisasi,dan menggunakan metode Big M untuk mengenalkan variable buatan ke dalam masing-masing kendala persamaan( lihat bagian 4.6 ),kolom-kolom dalam tableau simpleks akan menjadi seperti pada Tabel 8.13,dimana semua entri yang tidak terlihat dalam kolom ini adalah nol. [ satu-satunya penyesuaian yang perlu dilakukan sebelum iterasi pertama metode simpleks adalah mengeliminasi secara aljabar koefisien-koefisien bukan nol pada variable basis( buatan ) awal dalam baris 0 ].TABEL 8.13 Tableau simpleks asli sebelum menggunakan metode simpleks dalam masalah transportasiVariable BasisPersKoefisienRuas Kanan

Z

Z(0)-1MM0

(1)

(i)011

(m+j)011

(m+n)

TABEL 8.14 Baris 0 tableau simpleks setelah menggunakan metode simpleks dalam masalah transportasiVariabel BasisPersKoefisien

Z

Z(0)-1

MASALAH PENUGASANMasalah penugasan adalah masalah pemograman linier tipe khusus di mana petugas ditugaskan untuk menjalankan tugas. Dalam masalah penugasan kita akan mendelegasikan sejumlah tugas kepada sejumlah penerima tugas dalam basis satu-satu. Jadi pada masalah penugasan ini diasumsikan bahwa jumlah tugas sama dengan jumlah penerima tugas. Oleh karena itu, data pokok pertama yang harus dimiliki dalam menyelesaikan suatu masalah penugasan adalah jumlah penerima tugas dan jumlah tugasnya.Selain data jumlah petugas dan jumlah tugas yang terlibat, data lain yang biasa diperlukan adalah besar kerugian yang ditimbulkan atau besar keuntungan yang didapatkan oleh setiap penerima tugas dalam menyelesaikan setiap penugasan.Sedangkan tujuan yang ingin dicapai dalam menyelesaikan masalah ini adalah berusaha untuk menjadwalkan setiap petugas pada suatu tugas sedemikian rupa sehingga kerugian yang ditimbulkan minimal atau keuntungan yang didapatkan maksimal.Dalam hal ini, kerugian yang dimaksud adalah biaya dan waktu. Sedangkan yang termasuk keuntungan adalah pendapatan, laba dan nilai kemenangan. Dari sini terlihat bahwa secara garis besar ada dua jenis masalah penugasan, yaitu masalah minimisasi dan masalah maksimisasi.Untuk menyesuaikan definisi masalah penugasan, jenis-jenis aplikasi ini perlu dirumuskan dalam cara yang memenuhi asumsi berikut:1. Jumlah petugas dan jumlah tugas sama. (Jumlah ini dinyatakan dengan n.)2. Masing-masing petugas ditugaskan satu tugas saja.3. Masing-masing tugas dilakukan oleh satu petugas saja.4. Ada biaya cij yang dihubungkan dengan petugas i ( i = 1,2,,n).5. Tujuan penyelesaian masalah adalah menentukan bagaimana mengerjakan seluruh n penugasan untuk meminimalkan total biaya.Setiap masalah yang memenuhi semua asumsi tersebut dapat diselesaikan dengan sangat efisien menggunakan algoritma yang dirancang khusus untuk masalah penugasan.Tiga asumsi pertama bersifat membatasi. Banyak aplikasi yang berpotensi tidak sepenuhnya memenuhi asumsi-asumsi tersebut. Namun, masalah-masalah tersebut sering kali masih bisa dirumuskan ulang sebagai bentuk penyesuaian. Contohnya petugas dummy atau tugas dummy.

Model Masalah PenugasanModel matematika untuk masalah penugasan menggunakan variabel keputusan berikut:

untuk i = 1,2,,n dan j = 1,2,,n. Jadi masing-masing xij adalah variabel biner (memiliki 0 atau 1). Variabel biner berperan penting dalam OR untuk menyatakan keputusan ya/tidak. Dalam kasus ini, keputusan ya atau tidak adalah: Apakah petugas i melakukan tugas j?Misalkan Z menyatakan total biaya, maka model masalah penugasan adalah:

Sesuaikan dengan

DanXij 0,untuk semua i dan j ( xij biner, untuk semua I dan j ).Rangkaian pertama kendala fungsional menentukan bahwa masing-masing petugas hanya melakukan satu tugas, sementara rangkaian kedua mensyaratkan masing-masing tugas yang dilakukan persis oleh satu petugas. Jika kita menghapus batasan parentetik bahwa xij adalah biner, model ini jelas-jelas merupakan masalah pemograman linier tipe khusus sehingga siap diselesaikan. Masalah penugasan hanyalah masalah transportasi tipe khusus di mana yang menjadi sumber saat ini adalah petugas dan tujuan adalah tugas dan juga di manaJumlah sumber m = jumlah tujuan n.Setiap persediaan si = 1.Setiap permintaan dj = 1.Sekarang kita berfokus pada sifat solusi bilangan bulat dalam subbagian pada model masalah transportasi. Oleh karena sekarang si dan dj adalah bilangan bulat (=1), sifat ini menyatakan bahwa setiap solusi BF (termasuk yang optimal) adalah solusi bilangan bulat untuk masalah penugasan. Kendala fungsional model masalah penugasan menghalangi setiap variabel menjadi lebih besar daripada 1, dan kendala nonnegativitas menghalangi nilai lebih kecil dari 0. Oleh karena itu, dengan menghapus batasan biner yang memampukan kita menyelesaikan masalah penugasan sebagai masalah pemrograman linier, hasil solusi BF yang diperoleh (termasuk solusi optimal akhir) secara otomatis akan memenuhi batasan biner.Masalah penugasan dapat digambarkan dengan cara yang sama seperti masalah transportasi. Contohnya penempatan tenaga penjual ke area pasar dapat digambarkan sebagai berikut:

Garis tipis berhubungan dengan masalah alokasi. Garis tebal solusi dari permasalahan alokasi.

Algoritma Khusus Untuk Masalah PenugasanPada dasarnya terdapat algoritma khusus yang dirancang untuk masalah penugasan. Algoritma tersebut adalah algoritma Hungaria (metode Hungaria).Langkah Solusi Metode HungariaBerikut adalah langkah-langkah penyelesaian dengan metode Hungaria:1. Mengubah matriks awal menjadi matriks opportunity cost (reduced cost matrix/ RCM).Caranya:Pilih elemen terkecil dari setiap baris, kurangkan pada seluruh elemen baris tersebut.

2. RCM terus dikurangi untuk mendapatkan total-opportunity-cost matriks/ TOCM.Caranya:Pilih elemen terkecil dari setiap kolom pada RCM yang tidak mempunyai nilai nol, kurangkan pada seluruh elemen dalam kolom tersebut.

3. Melakukan test optimality (TOP) dengan menarik sejumlah minimum garis horisontal dan/atau vertikal untuk meliput seluruh elemen bernilai nol.Penugasan optimal adalah feasible jika:Jumlah garis=Jumlah baris atau kolom.

4. Jika belum optimal, lakukan revisi TOCM dengan memilih elemen terkecil yang belum terliput garis untuk mengurangi seluruh elemen yang belum terliput. Kemudian tambahkan jumlah yang sama pada seluruh elemen yang mempunyai dua garis yang saling bersilangan. Setelah itu lakukan kembali langkah 3, sampai solusi optimal.Contoh masalah minimisasi atau meminimumkan:Berikut adalah data lamanya waktu yang dibutuhkan (menit) oleh seorang operator menghasilkan satu unit barang dari setiap mesin dengan tipe berbeda di perusahaan tersebut:

Dengan melihat data pada tabel, tentukan operator mana yang cocok untuk setiap mesin agar waktu yang dibutuhkan untuk membuat satu barang adalah minimal!Penyelesaian:

Matrix awal:

2

Sheet1OperatorMesinIIIIIIIVA1012911B51078C12141311D815119

Sheet1OperatorMesinRCM:OperatorMesinIIIIIIIVIIIIIIIVA1012911A1302B51078B0523C12141311C1320D815119D0731RCMTOCM:OperatorMesinOperatorMesinIIIIIIIVIIIIIIIVA1302A1002B0523B0223C1320C1020D0731D0431TOPRevisi TOCMOperatorMesinOperatorMesinIIIIIIIVIIIIIIIVA1002A2002B0223B0112C1020C2020D0431D0320

Sheet1OperatorMesinSolusi:IIIIIIIVPenugasanWaktu (Menit)A2002OperatorMesinB0112AIII9C2020BI5D0320CII14DIV9TOTAL37