Program Linear-Masalah Transportasi [PDF]

Citation preview

1 MASALAH TRANSPORTASI Pendahuluan Masalah transportasi merupakan kasus khusus dari masalah program-linear dengan tujuan untuk "mengangkut" barang tunggal dari berbagai asal (origin) ke berbagai tujuan (destination), dengan biaya angkut serendah mungkin. Banyaknya barang yang tersedia di berbagai asal dan jumlah barang yang diminta oleh berbagai tempat tujuan tersirat dalan masalah yang harus ditangani. Diberikan juga biaya pengangkutan dari satu unit barang yang diangkut dari suatu asal tertentu sampai ke tempat tujuan tertentu. Harap diingat bahwa semua hubungan adalah linear. Dilengkapi dengan informasi tentang jumlah kapasitas dari tiap-tiap asal, permintaan total dari masing-masing tempat tujuan, dan biaya pengiriman per unit barang untuk lintasan yang dimungkinkan, maka model transportasi digunakan untuk menentukan program pengiriman optimal yang menghasilkan biaya pengiriman total yang minimum. Karena masalah transportasi adalah kasus khusus dari masalah program linear, maka akan selalu dapat diselesaikan dengan metode simpleks. Tetapi "algoritma", yang akan dikembangkan dalam bagian ini, menyajikan suatu cara yang lebih efisien untuk menangani masalah tersebut. 2. Analisis Masalah Transportasi Telah dijelaskan bahwa masalah transportasi adalah suatu kasus khusus dari masalah perogram linear, maka berarti masalah transportasi akan memiliki ciri-ciri khas yang dimiliki pula oleh masalah program linear, yaitu: 1) Fungsi obyektif yang linear. f ( x)  c1 x1  c2 x2  c3 x3    cn xn



2) Struktur persyaratan Linear Setiap masalah program linear memiliki sekumpulan persyaratan linear. Ini adalah: n



m



 a j 1 i 1



ij



i  1, 2,, m x j  bi   j  1, 2,, n



dengan aij merupakan koefisien struktural yang mencerminkan spesifikasi teknik dari masalah yang dibahas, dan ia tampil sebagai koefisien dari variabel struktural dalam persyaratan-persyaratan struktural. Sedangkan bi adalah sekumpulan konstanta yang menggambarkan kapasitas maksimin atau minimum dari fasilitas-fasilitas yang ada maupun sumber-sumber yang tersedia. Bentuk persyaratan struktural yang linear dituliskan secara lengkap sebagai berikut:



2 a11 x1  a12 x2    a1n xn  b1



a21 x1  a22 x2    a2 n xn  b2



……………………………… am1 x1  am 2 x2    amn xn  bm



3) Persyaratan Tidak Negatif Variabel struktural, variabel slack, variabel slack buatan dari masalah program linear terbatas pada nilai-nilai tidak negatif, ditulis; x j  0 , j = 1, 2, 3, …, n.



Si  0 , i = 1, 2, 3, …, m.



Ai  0



Khususnya, masalah program linear dapat susut menjadi masalah "transportasi" jika: (1) koefisien dari variabel struktural, yaitu terbatas pada nilai-nilai 0 atau 1. (2) terdapat adanya kehomogenan antara unit-unit dalan persyaratan. Untuk memberikan gambaran yang jelas tentang model transportasi akan kita tampilkan sebuah contoh masalah. Contoh 1: Sebuah perusahaan memiliki tiga pabrik di tiga kota yang berlainan, dan ketiga-tiganya menghasilkan barang yang sama. Hasil produksi dari 3 pabrik ini diserap oleh empat toko penjualan. Tiga pabrik kita tandai dengan O1 , O2 , dan O3 dan toko sebagai pelanggan ditandai dengan D1 , D2 , D3 , dan D4 . Data relevan tentang kapasitas pabrik maupun permintaan pelanggan dan biaya pengiriman untuk tiap-tiap rute, tercantun pada tabel berikut. Sebagai tercantun pada tabel maka rnatriks dari masalah transpotasi memiliki 3 baris dan 4 kolom sehingga tidak merupakan matriks buj sangkar. Ini memberikan kesan bahwa dalam masalah transportasi, suatu asal tertentu dapat secara simultan mengirimkan barang kepada lebih dari satu tempat tujuan.



Tabel 1



3



cij = biaya pengangkutan satu unit barang dari asal i ke tujuan j. xij



Misalkan



= banyak unit barang yang diangkut dari asal i ke tujuan j.



b



i



=



d



j



Harap diperhatikan bahwa subskrip pertama di setiap simbol menunjukkan asal tertentu dan subskrip kedua menunjukkan tujuan tertentu. Misalnya c12 adalah biaya pengangkutan 1 unit barang dari O1 ke D2 , dan variabel x24 ialah banyaknya unit barang yang diangkut dari O2 ke D4 . Kapasitas tempat asal (origin) dan permintaan tempat tujuan diberikan di tepi tabel dan lazimnya disebut "rim requirement" atau "persyaratan samping" Masalah yang kita hadapi ialah memiliki siasat pengiriman (pengangkutan) yang akan memenuhi persyaratan samping dengan biaya total yang minimun. Analisis Masalah Masalah transportasi, seperti halnya masalah program linear, terdiri atas, tiga kamponen: Pertama, kita dapat merumuskan suatu fungsi obyektif yang linear, yang harus ditentukan nilai minimumnya. Fungsi ini akan mewakili biaya total pengiriman dari semua barang yang harus dikirim dari tempat-tempat asal ke tempat-tempat tujuan. Kedua, kita dapat menulis sekumpulan persyaratan struktural yang linear. Masalah ini memiliki tujuh persyaratan, tiga di antaranya (satu untuk setiap baris) memberikan hubungan antara kapasitas-kapasitas tempat asal dan barang-barang yang harus diterima oleh berbagai tempat tujuan. Ini disebut "persyaratan kapasitas". Empat persyaratan lainnya (satu untuk setiap kolom) menunjukkan hubungan antara permintaan berbagai tempat tujuan dan barangbarang yang akan dikirim oleh berbagai tempat asal. Ini disebut "persyaratan permintaan".



4 Ketiga, kita dapat menentukan persyaratan tidak negatif untuk variabel-variabel struktural xij . Pernyataan ini menandakan bahwa pengiriman negatif tidak dapat dibenarkan. Ketiga komponen dari masalah transportasi ditampilkan sebagai berikut. Minimunkan: f ( x )  c11 x11  c12 x12  c13 x13  c14 x14  c21 x21  c22 x22  c23 x23  c24 x24  c31 x31  c32 x32  c33 x33  c34 x34



Syarat:



Secara mudah dan sederhana, masalah ini dapat diselesaikan dengan "Model Transportasi". Sebelum kita uraikan metode transporasi, marilah kita bahas beberapa karakteristik tertentu dari masalah transportasi beserta penyelesaiannya. Melihat kenyataan akan harus dipenuhinya pernyataan-pernyataan bahwa jumlah kapasitas tempat asal harus sama dengan jumlah permintaan, ditulis: 3



4



i 1



j 1



 bi   d j maka setiap penyelesaian yang menenuhi enam dari tujuh persyaratan dengan sendirinya akan memenuhi persyaratan terakhir. Karena itu, jika m adalah jumlah baris dan n adalah jumlah kolom dalam suatu masalah transportasi, kita dapat menyatakan masalah secara lengkap dengan m + n  1 persamaan. Ini berarti bahwa suatu penyelesaian dasar yang memenuhi persyaratan dari suatu masalah transportasi hanya memiliki m + n  1 komponen-komponen positif. 3. Metode Penyelesaian Masalah Transportasi Jika persyaratan jumlah kapasitas tempat asal dan jumlah permintaan tempat tujuan dipenuhi, maka akan selalu mungkin untuk menyusun suatu solusi dasar yang awal dan mamenuhi persyaratan sedemikian rupa hingga semua persyaratan tepi (RIM) dipenuhi. Ini dapat dilakukan dengan metode-metode yang telah disiapkan untuk keperluan tersebut, yaitu: (1) aturan NWC (North West Corner) (2) metode pendekatan VOGEL



5 (3) metode INSPEKSI (4) metode Steppingstone (5) metode MODI Pendekatan Metode Transportasi Metode transportasi terdiri atas tiga langkah dasar. Langkah pertama, melibatkan penentuan pengiriman awal, sedamikian rupa sehingga diperoleh solusi dasar yang menenuhi syarat. Ini berarti bahwa (m + n 1) sel atau rute dari matriks transformasi digunakan untuk tujuan pengangkutan. Sel yang digunakan untuk pengangkutan disebut "sel yang ditempati", sedang sel lainnya dari matriks transportasi akan disebut "sel kosong". Langkah kedua, bertujuan menentukan biaya "kesempatan" (opportunity) yang berkaitan dengan sel kosong. Biaya "kesempatan" dari sel kosong dapat dihitung untuk tiap-tiap sel kosong tersendiri, atau dihitung untuk semua sel kosong secara keseluruhan. Jika biaya "kesempatan dari senua sel kosong tidak positif. maka solusi optimal telah diperoleh. Di lain pihak, jika hanya satu sel saja memiliki biaya kesampatan "bernilai positif", solusi pasti belum optimal dan kita harus melangkah ke langkah tiga. Langkah tiga, melibatkan penentuan solusi dasar yang memenuhi syarat, baru dan lebih baik. Sekali solusi dasar yang baru dan mamenuhi syarat telah dicapai, kita ulangi langkah 2 dan langkah 3 sampai suatu solusi optimal telah ditentukan. Langkah Pertama Metode Transportasi Langkah pertama dalam metode transportasi terdiri atas penentuan penempatan awal dari program pengangkutan ini, sedemikian rupa sehingga tercapai suatu solusi dasar yang memenuhi syarat (jumlah sel yang terisi m + n  1). Tersedia berbagai metode untuk menentukan program awal tersebut. Akan kita bicarakan lima metode dalam penanganan langkah pertama dalam masalah transportasi. (1) Aturan NWC (North West Corner) Sesuai nama aturan ini, maka penempatan pertama dilakukan di sel paling kiri dan paling atas (northwest) dari matriks. Besar alokasi ini akan mencukupi salah satu, kapasitas tempat asal dari baris pertama atau permintaan tempat tujuan dari kolom pertama atau kedua-duanya. Jika kapasitas dari tempat asal di baris pertama terpenuhi kita bergerak ke bawah menyusur kolom pertama dan menentukan lain yang akan mencukupi atau kapasitas tempat asal dari baris kedua atau mencukupi tujuan yang masih kurang dari kolom pertama. Di lain pihak, jika alokasi pertama memenuhi permintaan tempat tujuan di kolom pertama, kita bergerak ke kanan di baris pertama dan kemudian menentukan alokasi kedua yang atau memenuhi kapasitas tersisa dari baris satu atau memenuhi permintaan tujuan dari kolom 2, seterusnya. Dengan cara ini, dimulai dari sudut paling kiri dan paling atas dari matriks transportasi, memenuhi permintaan tujuan dan kapasitas tempat asal sekaligus, kita bergerak ke sel sebelah kanan yang lebih rendah sehingga tercapai persyaratan "RIM",



6 Harap diperhatikan bahwa jika kita ikuti aturan NWC, kita tidak menaruh perhatian terhadap biaya relevan dari tiap-tiap rute waktu kita menentukan program awal. Untuk dapat menghayati penggunaan aturan NWC kita berikan matriks transportasi yang tertera di Tabel 2. Tabel 2 D E ST I NAT I O N ORIGIN O1



D1



D4



D5



4



9



5



9



8



1



6



6



7



1



12



4



7



7



10



15



6



9



1



O3



PERMINTAAN TUJUAN PER PERODE WAKTU



D3



12



O2



O4



D2



40



20



50



30



40



KAPASITAS ORIGIN PER PERODE WAKTU 55 45 30 50 180



180



Penggunaan aturan NWC mengharuskan kita mengisi sel O1 D1 , yang terletak di sudut kiri atas. Alokasi ditetapkan x11 = 40 untuk memenuhi permintaan tujuan yang ternyata lebih kecil dari kapasitas O1 . Ini berarti bahwa permintaan tujuan D1 = 40 dipenuhi, tetapi O1 masih memiliki (55-40) = 15 unit kapasitas yang belum disalurkan.



7 Tabel 3 D E ST I NAT I O N ORIGIN O1 O2



D1



D2



12 40 8



4 15 1 5 12



1



O3



10



O4



PERMINTAAN TUJUAN PER PERODE WAKTU



40



15



20



D3



D4



D5



9



5



9



6 40 4 10 6



6



7



7



7



9 10



1 40



30



40



50



KAPASITAS ORIGIN PER PERODE WAKTU 55 45 30



20



50 180



180



Maka kita bergerak kekanan ke O1 D2 di baris pertama. Kita ketahui bahwa 15 unit dari kapasitas O1 , belum terpakai, maka 15 unit kita kirimkan seluruhnya ke D2 , sehingga sel O1 D2 diisi 15 unit. Kapasitas O1 habis terangkut, tetapi kolom D2 masih memerlukan 5 unit (20-15) untuk memenuhi kebutuhannya. Kita bergerak ke bawah menyusur kolom D2 dan melengkapi 5 unit ini dari kapasitas O2 , dan letakkan 5 unit di O2 D2 .



Ini mengakibatkan 40 unit dari kapasitas O2 yang belum terpakai dan kita bergerak ke D3 , dan letakkan 40 di sel O2 D3 . Permintaan 10 unit (50-10) untuk D3 dipenuhi dari O3 ,



letakknn 10 unit di sel O3 D3 . Kapasitas O3 masih tersisa 30-10 = 20 unit dan ini diangkut ke D4 , letakkan 20 unit di sel O3 D4 . Keperluan D4 masih kurang 10 unit dan ini diambil dari kapasitas O4 . Kapasitas O4 masih tersisa 50-10 = 10 unit dan ini diletakkan di sel O4 D5 .



Program awal sudah selesai ditentukan, tetapi kita masih perlu menguji apakah memenuhi persyaratan bahwa m + n − 1 sel harus terisi. m+n−1=4+5–1=8 Dari Tabel 3 terlihat bahwa ada 8 sel yang terisi, maka solusi tidak "merosot". Biaya total dari penmpatan ini adalah 40(12) + 15(4) + 5(1) + 40(6) + 10(4) + 20(7) + 10(9) + 40(1) = 1095 Sebuah solusi dasar yang memenuhi syarat dan tidak merosot telah diperoleh dengan biaya transportasi sejumlah $1095,-



8 Tetapi biaya ini belum tentu optimal, dan untuk menentukan biaya optimal diperlukan langkah dua yang masih harus dipelajari. (2) METODE VAM (Vogel Approximation METHOD) Metode ini didasarkan atas suatu "beda kolom" dan suatu "beda baris” yang menentukan beda antara dua ongkos termurah dalam satu kolom atau satu baris. Setiap "beda" dapat dianggap sebagai "penalti" karena tidak menggunakan rute termurah. Setelah dilakukan perhitungan penalti sesuai metode VAM, ditentukan penalti tertinggi. Baris atau kolom berkaitan dengan "penalti tertinggi" merupakan baris atau kolom yang akan diberi alokasi pertama. Alokasi pertama ditempatkan pada sel dengan biaya termurah yang terdapat di baris atau kolom yang berkaitan dengan "penalti tertinggi". Alokasi pertama ini atau menghabiskan kapasitas tempat asal atau menghabiskan permintaan tujuan, atau kedua-duanya. Baris atau kolom khusus yang telah dipenuhi keperluannya, dihapus dari matriks transportasi. Proses ini diulang-ulang hingga diperoleh program awal yang menggunakan m + n − 1 route. Metode ini memiliki sifat yang merugikan karena banyaknya perhitungan-perhitungan yang harus dilakukan, sebelum dicapai suatu solusi dasar yang memenuhi syarat. Walaupun demikian, penggunaan VAM menghasilkan biaya pengangkutan yang jauh lebih murah dari apa yang diperoleh dengan metode NWC. Untuk memberikan penjelasan lebih lanjut tentang metode VAM akan kita gunakan tabel yang sama, yaitu Tabel 2 yang telah digunakan untuk uraian terhadap metode NWC. Tabel 4 ORIGIN



D E ST I NAT I O N D1



O1 O2



O3 O4



Beda Baris



7



D2



D3



D4



D5



12



4



9



5



9



8



1



6



6



7



1



12



4



7



7



10



15



6



9



1



3



2



1



6



Beda Kolom 1 5 3 5



9



Tabel 5 D E ST I NAT I O N ORIGIN



D1



PERMINTAAN TUJUAN PER PERODE WAKTU



D4



D5



4



9



5



9



8



1



6



6



7



1



12



4



7



7



30 10



15



6



9



1



O2



O4



D3



12



O1



O3



D2



40 10



20



50



30



KAPASITAS ORIGIN PER PERODE WAKTU 55 45 30 0 50



40



Tabel 6



ORIGIN



D E ST I NAT I O N D1



O1



Beda Baris



D3



D4



D5



12



4



9



5



9



8



1



6



6



7



10



15



6



9



1



O2 O4



D2



2



3



0



1



Beda Kolom 1 5 5



6



Tabel 7 D E ST I NAT I O N ORIGIN O1



D1



PERMINTAAN TUJUAN PER PERODE WAKTU



D3



D4



D5



12



4



9



5



9



8



1



6



6



7



10



15



6



9



1 40



O2 O4



D2



10



20



50



30



40 0



KAPASITAS ORIGIN PER PERODE WAKTU 55 45 50 10



10 Tabel 8 D E ST I NAT I O N



ORIGIN



D1



O1



Beda Baris



Beda Kolom



D4



12



4



9



5



8



1



6



6



10



15



6



9



O2 O4



D3



D2



2



3



0



1 5 3



1



Tabel 9 D E ST I NAT I O N ORIGIN O1



D1



4



9



5



8



1 20 15



6



6



6



9



10



PERMINTAAN TUJUAN PER PERODE WAKTU



D4



12



O2 O4



D3



D2



10



20 0



50



KAPASITAS ORIGIN PER PERODE WAKTU 55 45 25 10



30



Tabel 10



ORIGIN O1



D E S T I NAT I O N D1



Beda Baris



D4



12



9



5



8



6



6



10



6



9



O2 O4



D3



2



0



1



Beda Kolom 4 0 3



11 Tabel 11 D E S T I NAT I O N ORIGIN



D3



D1



12



O1



KAPASITAS ORIGIN PER PERODE WAKTU



D4



9



5



55 25



30



O2 O4



PERMINTAAN TUJUAN PER PERODE WAKTU



8



6



6



10



6



9



10



50



25 10



30 0



Tabel 12



ORIGIN



DESTINATION



O1 O2 O4



Beda Baris



D3



D1



12



9



8



6



10



6



2



Beda Kolom 3 2 4



0



Tabel 13 DESTINATION ORIGIN O1



D1



12



9



8



6



O2 O4



PERMINTAAN TUJUAN PER PERODE WAKTU



D3



10



6 10



10



50 40



KAPASITAS ORIGIN PER PERODE WAKTU 25 25 10 0



12 Tabel 14



ORIGIN



DESTINATION D3



D1



O1 O2



Beda Baris



12



9



8



6



4



Beda Kolom 3 2



3



Tabel 15 DESTINATION ORIGIN O1 O2



D3



D1



12



9



8



6



KAPASITAS ORIGIN PER PERODE WAKTU 25 25 15



10



PERMINTAAN TUJUAN PER PERODE WAKTU



10 0



40



Tabel 16



ORIGIN O1 O2



PERMINTAAN TUJUAN PER PERODE WAKTU



D3



9 25 6 15 40



KAPASITAS ORIGIN PER PERODE WAKTU 25 15



13 Tabel 17 ORIGIN O1 O2



O3 O4 PERMINTAAN TUJUAN PER PERODE WAKTU



D E ST I NAT I O N D1



12 8



D2



4



1



1 20 12



30 10



15



10



40



20



D3



9 25 6 15 4



D4



5



9



6



7



7



7



9



1 40



KAPASITAS ORIGIN PER PERODE WAKTU



55



30



6 10 50



D5



30



40



45 30 50 180



180



Jumlah sel yang terisi m + n − l = 4 + 5 − 1 = 8. Dari tabel di atas terlihat bahwa kita peroleh 8 sel yang terisi. Ini berarti bahwa solusi awal adalah solusi dasar yang memenuhi syarat, dan masalahnya tidak merosot. Biaya total = 9(25) + 5(30) + 8(10) + 1(20) + 6(15) + 1(30) + 6(10) + 1 (40) = $ 695 Jelas terlihat bahwa biaya total yang diperoleh dengan metode VAM jauh lebih rendah daripada yang diperoleh dengan metode NWC. (3) Metode Inspeksi ( c ij Terkecil) Dalam penyelesaian masalah transportasi, tanpa ragu-ragu kita perlukan inspeksi dan pertimbangan. Untuk masalah transportasi berdimensi kecil hal ini akan memberikan pengurangan terhadap waktu. Alokasi pertama dibuat terhadap sel yang berkaitan dengan biaya pengangkutan terendah. Sel dengan ongkos terendah ini diisi sebanyak mungkin dengan mengingat persyaratan kapasitas origin maupun permintaan tempat tujuan. Kemudian kita beralih ke sel termurah berikutnya dan mengadakan alokasi dengan meraperhatikan kapasitas yang tersisa dan permintaan baris dan kolomnya. Jika terdapat adanya "ikatan" antara sel-sel termurah, kita dapat mematahkan ikatan tersebut, atau memilih sebarang sel untuk diisi. Banyaknya sel yang terisi harus sedemikian hingga diperoleh m+n-1 sel yang terisi. Secara sebarang kita pilih sel O3 D1 untuk diisi dengan 30 unit. Ini berarti bahwa kapasitas O3 telah diangkut seluruhnya, dan baris O3 dapat dihapus dari matriks transportasi.. Untuk alokasi kedua kita lihat adanya keterkaitan antara sel O2 D2 dan sel O4 D5 . Kita pilih sebarang dan O4 D5 kita isi dengan 40 unit, ini sepenuhnya mencukupi permintaan D5 , hingga kolom D5 dapat dicoret.



14 Untuk alokasi ketiga, kita mencatat bahwa sel O2 D2 adalah sel termurah, dan kita berii alokasi 20 unit, sehingga kolom D2 dapat dihapus. Dari sel yang masih tersisa, sel O1 D4 merupakan sel termurah dan diberi alokasi 30 unit sehingga kolom D4 dapat dihapus,



kemudian kita perhatikan adanya "keterikatan" antara sel O2 D3



dan sel O4 D3 , untuk



alokasi kelima. Secara sebarang kita pilih O4 D3 dan kita isi dengan 10 unit, dan baris O4 dapat dihapus. Kemudian sel O2 D3 adalah sel termurah dan kita alokasikan dengan 25 unit, kemudian baris O2 dicoret. Masih tersisa 25 unit di O1 sedangkan D1 dan D2 masih memerlukan 10 dan 15 unit masing-masing. Maka kita angkut 10 unit melalui O1 D1 dan 15 unit melalui O1 D3 . Semua persyaratan "RIM" telah dipenuhi sekarang dan kita peroleh penentuan awal disajikan pada tabel di atas. Banyaknya sel yang terisi ada 8, adalah m  n  1 = 4+5-1 = 8. Biaya total $705. Tabel 18 D E ST I NAT I O N ORIGIN O1 O2



O3 O4



PERMINTAAN TUJUAN PER PERODE WAKTU



D1



12 10 8 1 30 10



D2



4 1 20 12 15



40 10 0



20 0



ke-8



ke-3



D3



9 15 6 25 4 6 10 50 40 15 0 ke-7



D4



D5



5



9



6



7



7



7



9 30 0



1 40 40 0



ke-4



ke-2



KAPASITAS ORIGIN PER PERODE WAKTU 55 25 0



30 45 25 0 ke-6 30 0 ke-1 50 10 0 ke-5



Biaya total ini hendaknya Anda bandingkan dengan biaya total yang dicapai dengan menggunakan metode NWC ($ 1905) dan metode VAM ($ 695). Akan kita rangkuro kerabali bahwa pendekatan metode transportaai didasarkan atas tiga langkah: (1) menentukan "program awal" untuk mencapai solusi dasar yang memenuhi syarat. (2) menentukan “biaya kesempatan" dari setiap sel kosong. (3) memperbaiki program yang sedang berjalan untuk memperoleh program yang lebih baik, hingga akhirnya mencapai solusi optimal. Aplikasi dari langkah (2) dan (3) akan kami uraikan di pembahasan berikutnya. Terdapat adanya dua metode untuk mengembangkan langkah (2) dan (3). Satu disebut metode steppingstone sedang satunya disebut metode Modified-Distribution.



15 (4) Metode Steppingstone Untuk memberikan gambaran yang jelas tentang metode Steppingstone pertama-tama akan kita selesaikan suatu masalah transportasi yang sangat sederhana. Kemudian cara ini digunakan untuk menurunkan solusi optimal dari suatu masalah yang lebih kompleks. Tujuan penyelesaian masalah sederhana berikut ini ialah untuk mambiasakan pembaca dengan istilah dan dasar pemikiran yang terkandung dalam metode Steppingstone. Tabel 19 ORIGIN O1 O2



Permintaan



DESTINATION D1



D2



2



2



1



2



900



Persediaan 1000 600



700 Tabel 20



ORIGIN O1 O2



Permintaan



DESTINATION D1



D2



2 900 1



2 100 2 600



900



700



Persediaan 1000 600



Mengikuti aturan NWC, kita peroleh program awal sebagai tertera pada Tabel 20. Program awal ini tidak merosot karena memiliki sel terisi sejunlah m+n-1 = 2+2-1 = 3. Progran awal ini juga telah menenuhi semua persyaratan "RIM". Menentukan opportunity cost dari “sel kosong” Apakah progran awal yang diperoleh seperti Tabel 20 sudah optimal? Untuk menjawab pertanyaan ini, kita harus melakukan langkah dua, yaitu menentukan opportunity cost atau biaya kesempatan dari sel kosong. Sebagai kita maklumi, model transportasi melibatkan pengambilan keputusan dengan kepastian, maka kita sadari bahwa suatu solusi optimal tidak akan menimbulkan suatu biaya kesempatan yang positif. Maka untuk menentukan apakah terdapat adanya suatu biaya kesempatan yang bernilai positif dalam suatu program, kita harus menyelidiki setiap sel kosong (sel yang tidak ikut dalam jalur pengangkutan). Jika semua sel kosong telah memiliki opportunity cost yang tidak positif, maka progran telah optimal. Sebaliknya jika satu sel kosong saja maniliki biaya kesempatan yang positif, maka program belum optimal hingga perlu diperbaiki.



16 Marilah kita lakukan pengujian terhadap progran yang kita peroleh sebagai berikut. Tabel 21 DESTINATION



ORIGIN



D1



D2



2



O1



-1



O2



2 +1



1 +1



2 -1



Ambillah 1 unit dari O2 D2 : −1 Tambahkan 1 unit ke O2 D1 : +1 Ambillah 1 unit dari O1 D1 : −1 Tambahkan 1 unit ke O1 D2 : +1 Dalam program ini jelas bahwa sel O2 D1 kosong, dan kita ingin menentukan apakah ada biaya kesempatan berkaitan dengan sel ini. Ini dilakukan dengan memindahkan 1 unit barang ke sel O2 D1 , yang mengakibatkan penggeseran lainnya untuk memenuhi persyaratan RIM, kemudian kita tentukan biaya berkaitan dengan penindahan ini. Marilah kita geser 1 unit dari sel O2 D2 ke sel O2 D1 . Penggeseran ini mengakibatkan perubahan-perubahan untuk mempertahankan persyaratan RIM. Perubahanperubahan ini berkaitan dengan biaya berikut ini −2 + 1 − 2 + 2 = −1 dollar Kenyataan bahwa pemindahan 1 unit ke sel O2 D1 menghasilkan perubahan biaya -1 dollar, menunjukkan bahwa opportunity cost karena tidak mengikut-sertakan sel O2 D1 di program pertama adalah +1 dollar per unit pengiriman. Sel kosong O2 D1 harus diikutsertakan dalam program baru yang diperbaiki . Memperbaiki Program Tabel 22: Program pertama DESTINATION



ORIGIN



D1



2 O1



−



900 1



O2



+



D2



2 + 100 −2



17



600 Tabel 23: Program Perbaikan dengan 1 Pemindahan ORIGIN O1



O2



DESTINATION D1



D2



2 899



2 101



1



2 599



1



Menyadari bahwa opportunity cost dari sel O2 D1 adalah positif, maka program ini harus diperbaiki untuk memperoleh solusi dasar baru yang manenuhi syarat. Ini dilakukan dengan merancang program perbaikan di mana sel O2 D1 diikutsertakan dalam strategi pengangkutan. Marilah kita adakan peningkatan dengan mengangkut 1 unit dari sel O2 D2 ke sel O2 D1 . Program yang telah diperbaiki terlihat pada tabel program perbaikan. Pergeseran 1 unit dari sel O2 D2 ke sel O2 D1 berarti bahwa tersisa 599 unit di sel O2 D2 , tetapi pergeseran apapun yang dilakukan tetap tidak boleh melanggar persyaratan RIM. Setelah pergeseran maka sel O2 D1 terisi 1 unit dan sel O2 D2 hanya berisi 599 unit. Untuk manenuhi persyaratan RIM, maka dari sel O1 D1 digeser 1 unit ke sel O1 D2 , sehingga dalam program perbaikan menunjukkan bahwa sel O1 D1 berisi 899 unit dan sel O1 D2 berisi 101 unit. Perubahan dalam program yang dipengaruhi oleh pergeseran 1 unit ke sel O2 D1 ' menurunkan biaya pengangkutan sebanyak $1. Selanjutnya, karena pergeseran 1 unit dari sel O2 D2 ke O2 D1 memberikan keuntungan $1, kita harus menggeser sebanyak mungkin



unit dari sel O2 D2 ke O2 D1 . Mengamati data yang ada, kita tidak dapat menggeser lebih dari 600 unit ke O2 D1 tanpa melanggar persyaratan RIM. Tabel 24



ORIGIN O1



DESTINATION D1



D2



2 300



2 700



Persediaan 1000



18



O2



1 600



Permintaan



900



2



600



700



Pergeseran 600 unit ke O2 D1 menghasilkan Tabel 24, yang merupakan solusi dasar yang lebih baik. Apakah program ini sudah optimal? Untuk mengetahui jawaban atas pertanyaan ini harus kita selidiki opportunity cost dari sel kosong O2 D2 . Pergeseran 1 unit ke sel O2 D2 dengan pengambilan dari O1 D2 mengakibatkan perubahan ongkos sebesar +2 − 1+2 − 2 = +1 Opportunity cost karena tidak melewatkan melalui sel O2 D2 adalah −1. Maka Tabel 24 adalah optimal dengan biaya pengangkutan 300(2) + 700(2) + 600(1) = $ 2600.Tidak ada program lain kecuali program Tabel 24 dapat memberikan biaya pengangkutan lebih murah dari program ini. Marilah kita rekapitulasi kembali metode penyelesaian masalah transportasi. Pertama : kita susun suatu solusi dasar yang memenuhi syarat dengan menerapkan salah satu metode dalam langkah satu, yaitu NWC, VAM, atau Inspeksi. Kedua : setelah memperoleh solusi dasar yang memenuhi syarat, kita melangkah untuk menentukan opportunity cost dari sel-sel kosong. Ketiga : kalau tidak ada sel kosong satu pun yang memiliki opportunity cost positif, maka program sudah optimal. Kalau masih ada sel kosong yang memiliki opportunity cost yang positif, program belum optimal, dan perbaikan harus diadakan dengan mengikut-sertakan sel kosong dengan opportunity cost tertinggi ke dalam program perbaikan. Prosedur yang diuraikan di atas merupakan inti dari Metode Steppingstone. Walaupun masalah transportasi yang telah kita selesaikan diwakili hanya oleh sebuah matriks 2×2, Metode Steppingstone dapat digunakan untuk setiap matriks berukuran m×n. Andaikan kita harus menangani masalah transportasi berukuran 4×5, berarti memiliki 20 sel. Untuk program awal yang memenuhi syarat, akan dijumpai 8 sel terisi, sedang 12 sel lainnya kosong. Jika program awal perlu diperbaiki, kita perbaiki program dengan mengikut sertakan sel kosong yang memiliki biaya kesempatan tertinggi, hanya satu sel diikutsertakan dalam program baru, setiap kali program harus diperbaiki.



19 Untuk memperoleh gambaran yang lebih jelas tentang metode steppingstone akan kita tunjukkan penerapannya pada suatu masalah yang lebih besar. Langkah 1: Mempeholeh Solusi Awal yang Memenuhi Syarat Suatu solusi awal yang memenuhi syarat untuk suatu masalah transportasi dapat diperoleh dengan menggunakan aturan NWC, metode VAM atau metode Inspeksi yang sederhana. Akan kita tampilkan kembali suatu masalah transportasi yang telah Anda kerjakan di bagian awal, sehingga Anda telah mengenal tabelnya yang diberikan berikut ketiga program awal yang diperoleh dengan metode NWC, metode VAM maupun metode Inspeksi. Kita gunakan masalah yang memiliki data sebagai tertera pada Tabel 2. Di antara tiga program awal yang telah diperoleh kita pilih program awal yang diperoleh metode Inspeksi. Tabel 25 ORIGIN O1 O2



O3 O4



PERMINTAAN



D E ST I NAT I O N D1



12 10 8



D2



4



1



1 20 12



30 10



15



40



20



D3



9 15 6 25 4



D4



5



9



6



7



7



7



9



1 40



55



30



6 10 50



KAPASITAS



D5



30



40



45 30 50 180



180



Bermula dari Tabel 25 ini ingin kita peroleh solusi optimal dengan menggunakan steppingstone. Jumlah sel isi seharusnya ada m+n-1 = 4+5-1 = 8. Memang ada 8 sel terisi isi, berarti solusi awal tersebut memenuhi persyaratan. Langkah 2: Menentukan Opportunity Cost dari Sel-sel Kosong. Dalam metode steppingstone sebuah Loop tertutup dilengkapi dengan tanda “+” dan “−“ harus ditentukan untuk setiap sel kosong sebelum opportunity cost bersangkutan dihitung. Program awal kita memiliki 12 sel kosong, maka harus digambar 12 loop tertutup yang berbeda Opportunity cost berkaitan dengan setiap sel kosong dihitung, dan hasilnya tertera pada Tabel 26.



20 Ternyata sel O2 D1 merupakan satu-satunya sel kosong dengan opportunity cost positif. Maka sel O2 D1 harus diikut sertakan dalam program perbaikan.



Langkah 3: Memperbaiki suatu Program Program awal belum optimal karena masih memiliki sel kosong O2 D1 yang memiliki opportunity cost bernilai positif. Sekarang kita perbaiki program dengan mengikut sertakan O2 D1 dalam program baru. Tidak diperlukan adanya pemilihan karena sel O2 D1 adalah



satu-satunya sel dengan opportunity cost bernilai positif. Perbaikan program awal diarahkan oleh loop tertutup dari sel kosong. Karena 10 adalah bilangan terkecil dalam sel bertanda negatif dalam loop, maka sebanyak 10 unit ditambahkan pada sel bertanda positif dan dikurangkan dari sel bertanda negatif. Sel Kosong



Loop Tertutup



Perubahan Biaya



Opportunity Cost



Tindakan



O1 D2 O1 D2  O1 D3  O2 D3  O2 D2



+4-9+6-1= 0



0



Tak berpengaruh



O1 D5 O1 D5  O4 D5  O4 D3  O1 D3



+9-1+6-9=+5



-5



Tak ikut dalam perbaikan



O2 D1 O2 D1  O1 D1  O1 D3  O2 D3



+8-12+9-6=-1



+1



Hrs ikut dalam perbaikan



O2 D4 O2 D4  O1 D4  O1 D3  O2 D3



+6-5+9-6=+4



-4



Tak berpengaruh



O2 D5 O2 D5  O2 D3  O4 D3  O4 D5



+7-6+6-1=+6



-6



Tak berpengaruh



O3 D2 O3 D2  O3 D1  O1 D1  O1 D3  O2 D3 +12-1+12-9+6-1=+19  O2 D2



-19



Tak berpengaruh



O3 D3 O3 D3  O1 D3  O1 D1  O3 D1



+4-9+12-1=+6



-6



Tak berpengaruh



O3 D4 O3 D4  O1 D4  O1 D1  O3 D1



+7-5+12-1=+13



-13



Tak berpengaruh



O3 D5 O3 D5  O4 D5  O4 D3  O1 D3  O1 D1+7-1+6-9+12-1=+14  O3 D1



-14



Tak berpengaruh



O4 D1 O4 D1  O1 D1  O1 D3  O4 D3



+10-12+9-6=+1



-1



Tak berpengaruh



O4 D2 O4 D2  O2 D2  O2 D3  O4 D3



+15-1+6-6=+14



-14



Tak berpengaruh



O4 D4 O4 D4  O4 D3  O1 D3  O1 D4



+9-6+9-5=+7



-7



Tak berpengaruh



21 Tabel 26 Program Awal D E ST I NAT I O N



ORIGIN



D1



12



D2



4



−



10



O2



1 20



+



PERMINTAAN



9



5



KAPASITAS



D5



9 55



15 + 8



O4



D4



30



O1



O3



D3



1 30 10 40



12 15 20



6



6



45



25 − 4 6 10 50



7



7



7



9



1 40



30



40



30 50 180



180



Tabel 27 Program Perbaikan ORIGIN O1 O2



O3 O4



PERMINTAAN



D E ST I NAT I O N D1



12 8 10 1 30 10 40



D2



4 1 20 12 15 20



D3



9 25 6 15 4



D4



5



9



6



7



7



7



9



1 40



55



30



6 10 50



KAPASITAS



D5



30



40



45 30 50 180



180



Pertanyaan berikutnya: Apakah program perbaikan merupakan soluai optimal? Untuk menjawab pertanyaan ini kita harus raengulangi Langkah 2, sebagai dijelaakan sebelumnya. Jika seandainya Langkah 2 menunjukkan solusi yang belum optimal, kita harus raengulangi Langkah 3, yaitu memperbaiki program. Program dichek kembali dan seterusnya hingga akhirnya tercapai suatu aolusi optimal.



22 (5) Metode “ MODI” Modified distribution method, dikenal sebagai rnetode MODI, sangat mirip dengan metode steppingstone kecuali bahwa ia menyajikan cara yang lebih efisien uituk menghitung tanda-tanda peningkatan dari sel-sel yang kosong. Perbedaan utama antara dua metode ini menyangkut langkah dalam penyelesaian masalah, di mana diperlukan adannya suatu lintasan tertutup. Untuk menghitung penunjuk peningkatan suatu solusi khusus, maka dalam metode steppingstone perlu digambar suatu lintasan tertutup untuk setiap sel kosong. Ditentukan sel kosong dengan opportunity cost tertinggi, kemudian dipilih untuk ikut dalam program perbaikan berikutnya. Dalam metode MODI penunjuk peningkatan dapat dihitung tanpa menggambar lintasan tertutup. Dalam kenyataannya metode MODI memerlukan hanya satu lintasan tertutup.. Lintasan ini digambar setelah sel kosong yang memiliki opportunity cost tertinggi positif diketemukan. Seperti dalam metode steppingstone. Kegunaan lintasan ini ialah untuk menentukan jumlah unit maksimum yang dapat dipindahkan ke sel kosong dalam program perbaikan berikutnya. Maka, prosedur untuk menghitung opportunity cost dari sel kosong dalam MODI tidak tergantung pada lintasan loop tersebut. Mekanisme dan kerangka pemikiran metode MODI akan kita gambarkan dengan penyelesaian masalah transportasi yang sederhana sederhana sebagai berikut: Tabel 28 ORIGIN O1 O2



Permintaan



DESTINATION D1



D2



2



2



1



2



900



Persediaan 1000 600



700 Tabel 29



ORIGIN O1 O2



Permintaan



DESTINATION D1



D2



2 900 1



2 100 2 600



900



700



Persediaan 1000 600



23 Melakukan langkah pertama menggunakan NWC diperoleh solusi awal tertera pada Tabel 29. Penggunaan steppingstone untuk menguji keoptimalan program awal sesuai Tabel 29 menunjukkan bahwa kosong O2 D1 memiliki opportunity cost +1, sehingga program masih memerlukan perbaikan. Metode lain untuk mencapai kesimpulan yang sama ialah melalui penentuan tentang apa yang disebut implied cost dari sel kosong. Pengertian dari implied cost akan kita jelaskan dengan kaitannya dengan masalah transportasi. Dalam program awal ini sel O2 D1 adalah satu-satunya sel kosong. Kita dapat menghitung perubahan harga karena pengangkutan 1 unit barang melalui sel kosong sebagai berikut: O2 D1 − O1 D1 + O1 D2 − O2 D2 = O2 D1 − 2 + 2 − 2 = O2 D1 − 2



Berapapun biaya pengangkutan per unit barang melalui sel kosong O2 D1 , adalah jelas bahwa pergeseran tersebut diinginkan hanya jika perubahan biaya total ( O2 D1 − 2) adalah negatif. Nilai ini akan negatif selama biaya sebenarnya dari O2 D1 kurang dari 2. Biaya limit atas yang telah dihitung dari sel O2 D1 (dalam program ini adalah 2), yang jika melebihi limit, maka keikutsertaan sel O2 D1 dalam program perbaikan tidak diinginkan. Dengan perkataan lain, jika biaya pengangkutan sebenarnya yang melalui O2 D1 lebih besar dari $2 per unit, pergeseran tersebut tidak diinginkan. Sebaliknya, jika biaya pengangkutan sebenarnya kurang dari $2 per unit, pergeseran diinginkan dan sel O2 D1 harus diikut sertakan dalam program berikutnya. Implied cost dari sel kosong O2 D1 adalah $2 per unit. Sebagai telah kita ketahui terlebih dahulu, negatif dari perubahan biaya total diakibatkan karena pergeseran 1 unit barang ke sel kosong memberikan opportunity cost berkaitan dengan sel kosong tersebut. Untuk sel O2 D1 , Opportunity cost = − (perubahan biaya total) = − ( O2 D1 − 2) = 2 − O2 D1 dengan O2 D1 adalah biaya sebenarnya dari pengiriman per init barang melalui sel O2 D1 . Tetapi, seperti baru saja kita hitung, implied cost karena tidak menggunakan sel O2 D1 adalah $2 per unit. Opportunity cost = implied cost - biaya sebenarnya



24 Substitusi dari biaya pengiriman sebenarnya melalui sel O2 D1 , yaitu $1 dan implied cost yang telah dihitung dari sel O2 D1



ke dalam pernyataan di atas menghasilkan 2-1 = +1



dollar. Nilai ini sama dengan opportunity cost dan sel O2 D1 yang telah kita ketemukan dengan observasi langsung dari perubahan biaya yang disebabkan oleh pergeseran 1 unit barang ke dalam sel kosong O2 D1 . Kesamaan ini berlaku untuk setiap sel kosong, dan kita nyatakan kembali: Opportunity cost = implied cost - ongkos sebenarnya. Pertanyaan berikutnya ialah: Dapatkah kita menentukan implied cost dari sebuah sel kosong tanpa menggambarkan lintasan loop terlebih dahulu? Jika seandainya ini mungkin, kita akan menyusun kerangka utama dari metode MODI, karena kemudian kita dapat mengurangkan biaya sebenarnya dari implied cost sel kosong yang telah dihitung tanpa menggambar lintasan loop tersebut dahulu. Marilah kita perhatikan kembali program awal Tabel 29 yang memenuhi syarat. Dalam program ini ada 3 sel terisi. Dalam istilah program linear, ini berarti bahwa tiga variabel ( x11 , x12 , x 22 ) dari empat variabel adalah variabel basis. Dapat diingat kembali dari metode



simpleks bahwa opportunity cost dari variabel basis dalam program awal adalah nol. Sesuai itu dapat ditunjukkan bahwa dalam kasus masalah transportasi, opportunity dari setiap sel terisi (sel berisi variabel basis} adalah nol. Dengan perkataan lain, jika variabel basis tidak akan diubah, maka pemasukan dan pemindahan 1 unit di sebarang sel terisi tidak akan mengakibatkan perubahan biaya. Sekarang, kita tentukan sekumpulan bilangan baris (ditempatkan di sebelah paling kanan) dan sekunpulan bilangan kolom (ditempatkan di bawah setiap kolom dari tabel) sedemikian rupa sehingga biaya pengangkutan per unit dari setiap sel terisi sama dengan jumlah dari bilangan baris dan bilangan kolom. Selanjutnya, karena jumlah bilangan baris dan bilangan kolom dari sebarang sel terisi sama dengan biaya dari sel tersebut (suatu variabel basis), maka jumlah bilangan baris dan bilangan kolom dari setiap sel kosong memberikan implied cost dari sel kosong tersebut. Maka implied cost dari sebarang sel kosong diberikan oleh Implied cost = bilangan baris + bilangan kolom = ui  v j Maka dengan menentukan bilangan baris dan bilangan kolom secara lengkap, kita dapat menghitung implied cost untuk setiap sel kosong tanpa menggambar lintasan loop, Jelas, sekarang harus kita tanggulangi masalah penentuan bilangan baris dan bilangan kolom.



25 Untuk setiap sel terisi, kita harus memilih ui (bilangan baris) dan v j (bilangan kolom) sehingga cij (biaya pengangkutan sebenarnya per unit di sel terisi) sama dengan jumlah dari u i dan v j . Misalkan untuk sel terisi yang terletak di baris 1 dan kolom 1, maka c11  u1  v1



dan c12  u1  v2 dan seterusnya. Proses ini harus dilakukan untuk setiap sel terisi. Tetapi harap disadari bahwa walaupun solusi dasar yang memenuhi syarat dalam suatu model transportasi terdiri atas m + n − 1 variabel (dengan perkataan lain, terdapat m + n − 1 sel terisi), kita harus menentukan m + n nilai untuk memperoleh sekumpulan bilangan baris dan kolom yang lengkap. Maka, untuk menentukan semua bilangan baris dan kolom, harus dipilih satu bilangan sebarang yang mewakili suatu baris atau suatu kolom. Sekali suatu bilangan baris atau kolom telah dipilih secara sebarang, bilangan baris dan bilangam kolom lainnya dapat ditentukan oleh hubungan cij = ui + v j . Hubungan ini harus berlaku untuk semua sel yang terisi. Karena sebarang bilangan dapat dipilih untuk mewakili salah satu dari ui atau v j , kita akan mengikuti secara praktis dengan memisalkan u1 = 0. Prosedur ini dapat langsung diterapkan pada Tabel 29 dan diperoleh Tabel 30 sebagai berikut: Tabel 30 DESTINATION



ORIGIN O1 O2



=



2 = c12



=



u1 v1



+



0



+



v1



u1 v2



=



2 =



2 900 1



2 100 2 600



2



2



u2 v2



Bilangan Baris 0 0



 v1 = 2



+



2 = 0 + v2 c 22



D2



2



Bilangan Kolom



c11



D1



 v2 = 2



+



u2 + 2



 u2 = 0



Sekarang akan kita hitung opportunity cost dari sel kosong O2 D1 .



26 Opportunity cost = implied cost - biaya sebenarnya = (ui  v j )  cij Untuk sel O2 D1 berlaku Opportunity cost = (u 2  v1 )  c21 = (0 + 2) – 1 = +1 dollar. Program ini belum optimal karena sel kosong O2 D1 masih memiliki opportunity cost yang bernilai positif. Proses yang telah kita lakukan akan kita rangkum untuk dapat memberikan gambaran yang lebih jelas tentang apa yang telah kita kerjakan. Tabel 31 Implied cost



Biaya Sebenarnya



Tindakan



ui  v j



>



cij



Sel kosong ini dapat diikutsertakan dalam program



ui  v j



=



cij



Tidak berpengaruh



ui  v j