Sumber : http://www.belajar-informatika.net/index.php?id_bab=12&id_materi=30
Untuk mendapat gambaran yang jelas tentang metode ini kita langsung masuk ke contoh kasus.
Sebuah perusahaan saat ini beoperasi dengan 3 buah pabrik yang memiliki kapasitas masing-masing sebagai berikut :
Saat ini ada kebutuhan dari tiga kota besar yang harus dipenuhi, dengan besaran permintaan masing-masing kota dapat dilihat di tabel di atas.
Perhatikan ! bahwa antara kapasitas pabrik/sumber daya perusahaan dan kebutuhan masing-masing kota adalah sama, yakni sebesar 200 ton. Apabila dijumpai kasus semacam ini, maka kasus yang sedang dihadapi adalah normal.
Perkiraan biaya transportasi dari setiap pabrik ke masing-masing kota adalah :
Dari pabrik 1 ke kota A = 20 Dari pabrik 3 ke kota A = 25
Dari pabrik 1 ke kota B = 5 Dari pabrik 3 ke kota A = 10
Dari pabrik 1 ke kota C = 8 Dari pabrik 3 ke kota A = 19
Dari pabrik 2 ke kota A = 15
Dari pabrik 2 ke kota B = 20
Dari pabrik 2 ke kota C = 10
Pertanyaannya adalah :
1. Bagaimana distribusi sumber daya atau kapasitas perusahaan yang paling optimal, guna memenuhi kebutuhan dari ketiga kota besar tersebut ?
2. Berapakan total biaya optimal yang harus dikeluarkan perusahaan dalam memenuhi kebutuhan ketiga kota tersebut ?
1. Bagaimana distribusi sumber daya atau kapasitas perusahaan yang paling optimal, guna memenuhi kebutuhan dari ketiga kota besar tersebut ?
2. Berapakan total biaya optimal yang harus dikeluarkan perusahaan dalam memenuhi kebutuhan ketiga kota tersebut ?
SOLUSI:
Sebelumnya, masalah atau kasus di atas perlu disederhanakan terlebih dahulu dalam tabel transportasi, seperti terlihat di bawah ini :
Perhatikan, bahwa :
1. Selanjutnya tabel di atas akan disebut dengan tabel transportasi
2. Kolom, umumnya mewakili daerah atau tempat tujuan distribusi
3. Baris, umumnya mewakili sumber daya yang dimiliki perusahaan
4. Selanjutnya yang dimaksud dengan sel C11 adalah baris 1 (pabrik 1) dan kolom 1 (kota A), sel C12 adalah baris 1 (pabrik 1) dan kolom 2 (kota B), dst.
5. Angka yang terdapat pada pojok kanan atas setiap sel menunjukkan biaya transportasi di sel tersebut.
2. Kolom, umumnya mewakili daerah atau tempat tujuan distribusi
3. Baris, umumnya mewakili sumber daya yang dimiliki perusahaan
4. Selanjutnya yang dimaksud dengan sel C11 adalah baris 1 (pabrik 1) dan kolom 1 (kota A), sel C12 adalah baris 1 (pabrik 1) dan kolom 2 (kota B), dst.
5. Angka yang terdapat pada pojok kanan atas setiap sel menunjukkan biaya transportasi di sel tersebut.
1. METODE NORTH WEST CORNER
Penggunaan metode NWC, sesuai namanya North West Corner penyelesaian selalu akan dimulai dari pojok kiri atas (north west) dari tabel transportasi. Dengan demikian hasil dari metode ini berturut-turut sebagai berikut :
Prinsipnya, sebelum kebutuhan kota A ‘beres’ jangan memenuhi kebutuhan kota B, dst. Sebelum kapasitas Pabrik 1 habis, jangan gunakan kapasitas dari Pabrik 2, dst.
Langkah 1 : Penuhi kebutuhan kota A (50) dengan kapasitas dari Pabrik 1 (90, sisa 40)
Langkah 2 : Lanjutkan dengan memenuhi kebutuhan kota B (110) dengan sisa kapasitas Pabrik 1 (yang sebelumnya/pada langkah 1 masih sisa 40) à masih kurang 70
Langkah 3 : Lanjutkan memenuhi kebutuhan kota B (masik kurang 70) dengan menggunakan kapasitas dari Pabrik 2 (60), karena sebelumnya hanya dipenuhi dengan sisa kapasitas Pabrik 1 sebesar 40. → inipun masih kurang 10
Langkah 4 : Penuhi kekurangan kebutuhan kota B (kurang 10) dengan menggunakan kapasitas dari Pabrik 3 sebanyak 10 → kapasitas Pabrik 3 tinggal 40
Langkah 5 : Karena kebutuhan kota B sudah ‘beres’, gunakan sisa kapasitas Pabrik 3 untuk memenuhi kebutuhan kota C yang kebetulan juga sebesar 40 → sama persis dengan kapasitas yang tersisa di Pabrik 3
Perhatikan tabel transportasi pada langkah ke-5 di atas. Dengan menggunakan metode NWC, yang dimulai dari pojok kiri atas, saat ini kebutuha semua kota dan kapasitas semua pabrik telah terpenuhi dan habis. Dari tebel tersebut alokasi atau pendistribusian yang terjadi adalah :
Pabrik 1 akan melayani/mengirim ke kota A sebanyak 50 ton dan kota B sebanyak 40 ton
Pabrik 2 hanya akan melayani/mengirim ke kota B sebanyak 60 ton
Pabrik 3 akan melayani/mengirim ke kota B sebanya 10 ton dan kota C sebanyak 40 ton
Pabrik 2 hanya akan melayani/mengirim ke kota B sebanyak 60 ton
Pabrik 3 akan melayani/mengirim ke kota B sebanya 10 ton dan kota C sebanyak 40 ton
Pertanyaan yang muncul adalah :
1. Sudah benarkah tabel yang dihasilkan sampai dengan langkah ke-5 tersebut ? → untuk memastikannya, perlu dicek kembali :
a). Apakah semua alokasi kalau dijumlah ke bawah dan kesamping sudah cocok dengan kebutuhan setiap kota dan jumlah kapasitas yang tersedia ?
b). Apakah jumlah sel yang terisi sudah memenuhi syarat yang ada (m+n)-1, atau (jumlah kolom+jumlah baris) – 1 = (3+3) – 1 = 5 sel terisi ?
c). Jika jawaban dari keduanya adalah ‘ya’ maka tabel tersebut sedah benar.
b). Apakah jumlah sel yang terisi sudah memenuhi syarat yang ada (m+n)-1, atau (jumlah kolom+jumlah baris) – 1 = (3+3) – 1 = 5 sel terisi ?
c). Jika jawaban dari keduanya adalah ‘ya’ maka tabel tersebut sedah benar.
2. Dari pendistribusi produk perusahaan tersebut, apakah biaya transportasi yang dikeluarkan perusahaan sudah optimal, dalam arti sudah paling minimal ?
Untuk mengetahuinya, dicoba hitung masing-masing biaya pendistribusian tersebut yakni:
Biaya mengirim 50 ton dari P1 ke kota A = 50 x 20 = 1000
Biaya mengirim 50 ton dari P1 ke kota B = 40 x 5 = 200
Biaya mengirim 50 ton dari P2 ke kota B = 60 x 20 = 1200
Biaya mengirim 50 ton dari P1 ke kota A = 10 x 10 = 100
Biaya mengirim 50 ton dari P1 ke kota A = 40 x 19 = 760
------------------------------------------------------------------------ +
Total biaya pengirimannya = 3260
Sudahkah biaya sebesar Rp 3260 tersebut optimal (paling kecil ?) Untuk mengetahuinya perlu dilakukan pengujian terhadap alokasi distribusi seperti pada langkah 5 sebelumnya. Mungkinkah dengan menggeser alokasi, biaya bisa diturunkan lagi ?
2. METODE STEPPING STONE
Atau
Langkah Pengujian :
Langkah 1 :
Menguji sel-sel yang masih kosong, apakah masih bisa memiliki nilai negatif atau tidak, artinya masih bisa menurunkan biaya transportasi atau tidak.
Sel yang diuji adalah : Sel C13, C21, C23, dan C31. Pengujian dilakukan pada setiap sel kosong tersebut dengan menggunakan metode Stepping Stone. Pada metode ini, pengujian dilakukan mulai dari sel kosong tersebut, selanjutnya bergerak (boleh searah jarum jam dan boleh berlawanan) secara lurus/tidak boleh diagonal, ke arah sel yang telah terisi dengan alokasi, begitu seterusnya sampai kembali ke sel kosong tersebut. Setiap pergerakan ini akan mengurangi dan menambah secara bergantian biaya pada sel kosog tersebut. Perhatikan tanda panah dan tanda (+)/(-) nya !!!
Untuk lebih jelasnya perhatikan contoh berikut ini.
Untuk pengujian sel C13 = biayanya 8, bergerak ke sel C33 (bisa juga ke C12, tapi tidak bisa ke C11), sehingga dikurangi 19, bergerak lagi ke C32, sehingga ditambah 10, bergerak langsung ke C12, sehingga dikurangi 5 (tidak perlu ke C22, karena bisa langsung ke C12), sehingga hasil akhirnya adalah 8 – 19 + 10 – 5 = - 6
Untuk pengujian sel C13 = biayanya 8, bergerak ke sel C33 (bisa juga ke C12, tapi tidak bisa ke C11), sehingga dikurangi 19, bergerak lagi ke C32, sehingga ditambah 10, bergerak langsung ke C12, sehingga dikurangi 5 (tidak perlu ke C22, karena bisa langsung ke C12), sehingga hasil akhirnya adalah 8 – 19 + 10 – 5 = - 6
Pengujian
Sel C13 = 8 – 19 + 10 – 5 = - 6
Sel C21 = 15 – 20 + 5 -20 = -20
Sel C23 = 10 – 19 + 10 – 20 = -19
Sel C31 = 25 – 20 + 5 – 10 = 0
Sel C13 = 8 – 19 + 10 – 5 = - 6
Sel C21 = 15 – 20 + 5 -20 = -20
Sel C23 = 10 – 19 + 10 – 20 = -19
Sel C31 = 25 – 20 + 5 – 10 = 0
Dari pengujian empat sel tersebut dapat dilihat bahwa masih ada tiga sel yang menghasilkan nilai negatif, dan sel C21 yang memberikan negatif paling besar. Artinya dengan menggeser pengiriman ke sel tersebut, biaya akan dapat diturnkan sebesar Rp 20 (karena -20) per ton-nya.
Dengan demikian perlu dilakukan perubahan alokasi pengiriman dengan langkah 2 selanjutnya :
Dengan demikian perlu dilakukan perubahan alokasi pengiriman dengan langkah 2 selanjutnya :
Langkah 2
Merubah alokasi pengiriman ke sel C21, yang pengujian sebelumnya memiliki pergerakan :
Merubah alokasi pengiriman ke sel C21, yang pengujian sebelumnya memiliki pergerakan :
Dari pergerakan dan tanda +/- yang ada, perhatikan sel yang bertanda minus saja, yakni sel C11 dan sel C22. Dari kedua sel bertanda pergerakan minus ini, pilih sel yang alokasi pengiriman sebelumnya memiliki alokasi paling kecil. Dan ternyata sel C11, dengan alokasi sebelumnya 50 ton, dan ini lebih kecil dari alokasi sel C22 yang 60 ton.
Selanjutnya angka 50 ton di sel C11 tersebut digunakan untuk mengurangi atau menambah alokasi yang ada selama pengujian (sesuai tanda pada pergerakan pengujian). Dengan demikian dapat dihasilkan tabel transportasi sebagai berikut :
Perhatikan !!!
Sel C11 menjadi 0 karena 50 – 50 = 0
Sel C12 menjadi 90 karena 40 + 50 = 90
Sel C22 menjadi 10 karena 60 – 50 = 10
Sel C21 menjadi 50 karena 0 + 50 = 50
Sel C11 menjadi 0 karena 50 – 50 = 0
Sel C12 menjadi 90 karena 40 + 50 = 90
Sel C22 menjadi 10 karena 60 – 50 = 10
Sel C21 menjadi 50 karena 0 + 50 = 50
Nilai alokasi pada sel C32 dan C33 tidak mengalami perubahan karena tida termasuk dalam pergerakan pengujian sel C21 tersebut.
Sekali lagi lakukan pengecekan :
- Apakah semua alokasi kalau dijumlah ke bawah dan kesamping sudah cocok dengan kebutuhan setiap kota dan jumlah kapasitas yang tersedia ?
- Apakah jumlah sel yang terisi sudah memenuhi syarat yang ada (m+n)-1, atau (jumlah kolom+jumlah baris) – 1 = (3+3) – 1 = 5 sel terisi ?
- Jika jawaban dari keduanya adalah ‘ya’ maka tabel tersebut sedah benar.
Sudahkah alokasi menajadi optimal ?
Untuk mengetahuinya, perlu kembali dilakukan pengecekan terhadap sel-sel yang masih kosong, apakah masih ada yang bernailai negatif atau tidak.
Dari tabel di atas, sel yang masih kosong adalah sel C11, C13, 23, dan C31. Pengujian terhadap sel-sel kosong tersebut dilakukan dengan cara yang sama seperti pengujian sel kosong sebelumnya, sehingga diperoleh hasil pengecekan sebagai berikut :
Dari tabel di atas, sel yang masih kosong adalah sel C11, C13, 23, dan C31. Pengujian terhadap sel-sel kosong tersebut dilakukan dengan cara yang sama seperti pengujian sel kosong sebelumnya, sehingga diperoleh hasil pengecekan sebagai berikut :
Pengujian
Sel C11 = 20 – 5 + 20 – 15 = 20 à (menjadi lebih mahal 20/ton)
Sel C13 = 8 – 19 + 10 – 5 = - 6
Sel C23 = 10 – 19 + 10 – 20 = -19
Sel C31 = 25 – 15 + 20 – 10 = 20 à (menjadi lebih mahal 20/ton)
Sel C11 = 20 – 5 + 20 – 15 = 20 à (menjadi lebih mahal 20/ton)
Sel C13 = 8 – 19 + 10 – 5 = - 6
Sel C23 = 10 – 19 + 10 – 20 = -19
Sel C31 = 25 – 15 + 20 – 10 = 20 à (menjadi lebih mahal 20/ton)
Dari hasil pengujian tersebut, ternyata sel C23 masih dapat memberikan penurunan biaya sebesar RP 19/ton. Dengan demikian memang perlu dilakukan perubahan alokasi pengiriman, dengan mencoba mengalokasikan pengiriman ke sel C23 dengan langkah :
Langkah 3
Merubah alokasi pengiriman ke sel C23, yang pengujian sebelumnya memiliki pergerakan :
Merubah alokasi pengiriman ke sel C23, yang pengujian sebelumnya memiliki pergerakan :
Dari pergerakan dan tanda +/- yang ada, perhatikan sel yang bertanda minus saja, yakni sel C22 dan sel C33. Dari kedua sel bertanda pergerakan minus ini, pilih sel yang alokasi pengiriman sebelumnya memiliki alokasi paling kecil. Dan ternyata sel C22, dengan alokasi sebelumnya 10 ton, dan ini lebih kecil dari alokasi sel C22 yang 40 ton.
Selanjutnya angka 10 ton di sel C22 tersebut digunakan untuk mengurangi atau menambah alokasi yang ada selama pengujian (sesuai tanda pada pergerakan pengujian). Dengan demikian dapat dihasilkan tabel transportasi sebagai berikut :
Perhatikan !!!
Sel C22 menjadi 0 karena 10 – 10 = 0
Sel C23 menjadi 90 karena 0 + 10 = 10
Sel C32 menjadi 20 karena 10 + 10 = 20
Sel C33 menjadi 50 karena 40 - 10 = 30
Sel C22 menjadi 0 karena 10 – 10 = 0
Sel C23 menjadi 90 karena 0 + 10 = 10
Sel C32 menjadi 20 karena 10 + 10 = 20
Sel C33 menjadi 50 karena 40 - 10 = 30
Nilai alokasi pada sel C12 dan C21 tidak mengalami perubahan karena tida termasuk dalam pergerakan pengujian sel C23 tersebut.
Sekali lagi lakukan pengecekan :
- Apakah semua alokasi kalau dijumlah ke bawah dan kesamping sudah cocok dengan kebutuhan setiap kota dan jumlah kapasitas yang tersedia ?
- Apakah jumlah sel yang terisi sudah memenuhi syarat yang ada (m+n)-1, atau (jumlah kolom+jumlah baris) – 1 = (3+3) – 1 = 5 sel terisi ?
- Jika jawaban dari keduanya adalah ‘ya’ maka tabel tersebut sedah benar.
Sudahkah alokasi menajadi optimal ?
Untuk mengetahuinya, perlu kembali dilakukan pengecekan terhadap sel-sel yang masih kosong, apakah masih ada yang bernailai negatif atau tidak.
Dari tabel di atas, sel yang masih kosong adalah sel C11, C13, C22 dan C31. Pengujian terhadap sel-sel kosong tersebut dilakukan dengan cara yang sama seperti pengujian sel kosong sebelumnya, sehingga diperoleh hasil pengecekan sebagai berikut :
Pengujian
Sel C11 = 20 – 5 + 10 – 19 + 10 - 15 = 1 à (menjadi lebih mahal 1/ton)
Sel C13 = 8 – 19 + 10 – 5 = - 6
Sel C22 = 20 – 10 + 19 – 10 = 19 à (lebih mahal 20/ton)
Sel C31 = 25 – 15 + 10 – 19 = 1 à (menjadi lebih mahal 1/ton)
Sel C11 = 20 – 5 + 10 – 19 + 10 - 15 = 1 à (menjadi lebih mahal 1/ton)
Sel C13 = 8 – 19 + 10 – 5 = - 6
Sel C22 = 20 – 10 + 19 – 10 = 19 à (lebih mahal 20/ton)
Sel C31 = 25 – 15 + 10 – 19 = 1 à (menjadi lebih mahal 1/ton)
Dari hasil pengujian tersebut, ternyata sel C13 masih dapat memberikan penurunan biaya sebesar RP 6/ton. Dengan demikian memang perlu dilakukan perubahan alokasi pengiriman, dengan mencoba mengalokasikan pengiriman ke sel C13 dengan langkah :
Langkah 4
Merubah alokasi pengiriman ke sel C13, yang pengujian sebelumnya memiliki pergerakan :
Merubah alokasi pengiriman ke sel C13, yang pengujian sebelumnya memiliki pergerakan :
Dari pergerakan dan tanda +/- yang ada, perhatikan sel yang bertanda minus saja, yakni sel C12 dan sel C33. Dari kedua sel bertanda pergerakan minus ini, pilih sel yang alokasi pengiriman sebelumnya memiliki alokasi paling kecil. Dan ternyata sel C33, dengan alokasi sebelumnya 30 ton, dan ini lebih kecil dari alokasi sel C12 yang 90 ton.
Selanjutnya angka 30 ton di sel C33 tersebut digunakan untuk mengurangi atau menambah alokasi yang ada selama pengujian (sesuai tanda pada pergerakan pengujian). Dengan demikian dapat dihasilkan tabel transportasi sebagai berikut :
Perhatikan !!!
Sel C12 menjadi 60 karena 90 – 30 = 60
Sel C13 menjadi 30 karena 0 + 30 = 30
Sel C32 menjadi 50 karena 20 + 30 = 50
Sel C33 menjadi 0 karena 30 - 30 = 0
Sel C12 menjadi 60 karena 90 – 30 = 60
Sel C13 menjadi 30 karena 0 + 30 = 30
Sel C32 menjadi 50 karena 20 + 30 = 50
Sel C33 menjadi 0 karena 30 - 30 = 0
Nilai alokasi pada sel C21 dan C23 tidak mengalami perubahan karena tida termasuk dalam pergerakan pengujian sel C13 tersebut.
Sekali lagi lakukan pengecekan :
- Apakah semua alokasi kalau dijumlah ke bawah dan kesamping sudah cocok dengan kebutuhan setiap kota dan jumlah kapasitas yang tersedia ?
- Apakah jumlah sel yang terisi sudah memenuhi syarat yang ada (m+n)-1, atau (jumlah kolom+jumlah baris) – 1 = (3+3) – 1 = 5 sel terisi ?
- Jika jawaban dari keduanya adalah ‘ya’ maka tabel tersebut sedah benar.
Sudahkah alokasi menajadi optimal ?
Untuk mengetahuinya, perlu kembali dilakukan pengecekan terhadap sel-sel yang masih kosong, apakah masih ada yang bernailai negatif atau tidak.
Dari tabel di atas, sel yang masih kosong adalah sel C11, C22, C31 dan C33. Pengujian terhadap sel-sel kosong tersebut dilakukan dengan cara yang sama seperti pengujian sel kosong sebelumnya, sehingga diperoleh hasil pengecekan sebagai berikut :
Pengujian
Sel C11 = 20 – 8 + 10 – 15 = 7 → (menjadi lebih mahal 7/ton)
Sel C22 = 20 – 5 + 8 – 10 = 13 → (menjadi lebih mahal 13/ton)
Sel C31 = 25 – 15 + 10 – 8 + 5 - 10 = 7 → (lebih mahal 7/ton)
Sel C33 = 19 – 10 + 5 – 8 = 6 → (menjadi lebih mahal 6/ton)
Sel C11 = 20 – 8 + 10 – 15 = 7 → (menjadi lebih mahal 7/ton)
Sel C22 = 20 – 5 + 8 – 10 = 13 → (menjadi lebih mahal 13/ton)
Sel C31 = 25 – 15 + 10 – 8 + 5 - 10 = 7 → (lebih mahal 7/ton)
Sel C33 = 19 – 10 + 5 – 8 = 6 → (menjadi lebih mahal 6/ton)
Dari hasil pengujian tersebut, ternyata semua sel sudah tidak ada yang bernilai negatif lagi, atau dengan kata lain semua sel sudah tidak dapat memberikan penurunan biaya lagi, sehingga dengan demikian dapat dikatakan kasus telah optimal, dengan total biaya :
Biaya mengirim 60 ton dari P1 ke kota B = 60 x 5 = 300
Biaya mengirim 30 ton dari P1 ke kota C = 30 x 8 = 240
Biaya mengirim 50 ton dari P2 ke kota A = 50 x 15 = 750
Biaya mengirim 10 ton dari P2 ke kota C = 10 x 10 = 100
Biaya mengirim 50 ton dari P3 ke kota B = 50 x 10 = 500
-------------------------------------------------------- +
Total biaya pengirimannya = 1890
Biaya mengirim 30 ton dari P1 ke kota C = 30 x 8 = 240
Biaya mengirim 50 ton dari P2 ke kota A = 50 x 15 = 750
Biaya mengirim 10 ton dari P2 ke kota C = 10 x 10 = 100
Biaya mengirim 50 ton dari P3 ke kota B = 50 x 10 = 500
-------------------------------------------------------- +
Total biaya pengirimannya = 1890
Sumber Referensi :
http://www.belajar-informatika.net/index.php?id_bab=12&id_materi=30
No comments:
Post a Comment