Pemrograman Dinamis dan Contoh Studi Kasus (2) Mundur (Backward)

PT. Bangkrut Abadi yang menjual pakan ternak ingin memasarkan produknya ke wilayah Bogor dari lokasi pabrik yang terletak di Bekasi. Perencanaan rutenya mencakup Cileungsi, Jalur alternatif Cibubur, Jakarta, Citeurup, Karanggan, Depok, Cibinong dan Sentul. Dia ingin meminimalkan biaya operasional yang timbul untuk distribusi koran tersebut meliputi biaya bahan bakar kendaraan, biaya loper koran, dan operasional kendaraan lainnya, hal ini disebabkan loper koran tersebut harus melewati banyak pilihan rute untuk dapat mendistribusikan koran. Apabila rute yang dilalui semakin panjang maka biaya yang timbul akan semakin besar, maka keuntungannya pun semakin sedikit. Oleh karena itu, PT. Bangkrut Abadi ingin mengetahui rute terdekat untuk dapat meminimalisir biaya operasional agar mendapat keuntungan lebih besar. Berikut adalah rute yang dapat diambil.

Graf Lintasan Distribusi Produk

 Keterangan :

1 : Bekasi                                            5 : Karanggan                            9 : Cibinong

2 : Jalur Alternatif Cibubur                 6 : Citeureup                           10 : Bogor

3 : Cileungsi                                        7 : Depok

4 : Jakarta                                            8 : Sentul

Berdasarkan rute diatas, jalur manakah yang optimal untuk dapat meminimalisir biaya operasional PT. Bangkrut Abadi.

Penyelesaian dengan cara manual pada studi kasus pendekatan mundur, tahap pertama dimulai dari ujung permasalahan. Misalkan x₁, x₂, x_3, x₄ adalah simpul-simpul yang dikunjungi pada tahap k (k = 1, 2, 3, 4). Rute yang dilalui adalah 1x₁x₂x₃x₄ , yang dalam hal ini x₄ = 10. Persoalan ini,

1.      Tahap (k) adalah proses memilih node tujuan berikutnya (ada 4 tahap).

2.      Status (s) yang berhubungan dengan masing-masing tahap adalah simpul-simpul di dalam graf.

Tujuan program dinamis mundur: mendapatkan f₁(1) dengan cara mencari f₄(s), f₃(s), f₂(s) terlebih dahulu. Setelah itu akan didapat solusi optimum dari kasus tersebut.

 

Langkah pertama pada studi kasus pendekatan mundur, yaitu memulai dari tahap 4. Tahap 4 dengan proses seperti dibawah ini.

Tahap 4: 

Tabel Pendekatan Mundur

x4 S	f4(s)	x4*
	10
8	3	10
9	3	10

Nilai minimum pada tahap empat adalah 3 yang dimiliki node 8 dan 9. Peubah keputusan pada tahap ke 4 adalah node tujuan yaitu node 10. Langkah kedua pada studi kasus pendekatan mundur, yaitu memulai dari tahap 3. Tahap 4 dengan proses seperti dibawah ini.

Tahap 3: 

Tabel Pendekatan Mundur

			Solusi Optimum
	8	9
5	4 + 3 = 7	2 + 3 = 5	2	9
6	3 + 3 = 6	3 + 3 = 6	3	8
7	5 + 3 = 8	7 + 3 = 10	8	8

 

 

 

 

                          

                       Graf Lintasan Distribusi Produk

Nilai pada tahap ini adalah nilai node yang bersangkutan ditambah dengan nilai node untuk mencapai nilai tujuan (node 10) contohnya nilai pada node 5 – 8 ditambahkan pula nilai pada node 8 – 10 agar dicapi nilai keseluruhan sehingga dapat diambil nilai terminimum, jadi nilai node 5 - 8  adalah 7. Tahap ini didapat pula nilai minimumnya yaitu untuk node tujuan ke 8 yaitu 6 (node 6 – 8) dan untuk node tujuan ke 9 yaitu 5 (node 5 – 9). Karena yang dicari adalah nilai minimum maka dipilihlah nilai 5 yaitu nilai dari node 5 – 9. Langkah ketiga pada studi kasus pendekatan mundur, yaitu memulai dari tahap 2. Tahap 2 dengan proses seperti dibawah ini.

Tahap 2: 

Tabel Pendekatan Mundur

				Solusi Optimum
	5	6	7
2	5 + 5 = 10	8 + 6 = 14	5 + 8 = 13	5	5
3	5 + 5 = 10	5 + 6 = 11	6 + 8 = 13	5	5
4	9 + 5 = 14	8 + 6 = 14	6 + 8 = 13	6	7

 

 

 

 

 

  

                                          Graf Lintasan Distribusi Produk

Sama dengan tahap sebelumnya yaitu mencari nilai minimum dengan menambahka nilai node yang ada dengan nilai node minimum untuk sampai ke nilai tujuan akhir (node 10). Cara itu didapatlah hasil paling minimum yaitu node 2 – 5 dengan nilai 5 dan node 3 – 5 dengan nilai 5. Dengan begitu maka ada 2 nilai minimum, untuk menemukan nilai mana yang akan dipilih maka akan ditentukan pada tahap berikutnya. Langkah terakir pada studi kasus pendekatan mundur, yaitu memulai dari tahap 1. Tahap 1 dengan proses seperti dibawah ini.

Tahap 1:  

Tabel 4.4 Tabel Pendekatan Mundur

				Solusi Optimum
	2	3	4
1	3 + 10 = 13	4 + 10 = 14	3 + 13 = 16	3	2

 

                                                           Graf Lintasan Distribusi Produk

Tahap ini adalah tahap akhir untuk menentukan nilai minimum untuk melakukan pendistribusian. Menentukan nilai masih sama dengan tahap sebelumnya yaitu nilai node yang ada ditambahkan nilai node minimum untuk mencapai nilai node akhit (node 10), maka didapatlah hasil yaitu node 1 – 2 dengan nilai 3. Kesimpulannya lintasan terpendek yang dapat ditempuh untuk pendistribusian pakan yang dapat menekan biaya operasional yang minimum adalah rute : 1 (Bekasi) 2 (Jalur Alternatif Cibubur) 5 (Karanggan) 9 (Cibinong) 10 (Bogor), yang mana total panjang lintasan tersebut adalah 13.

 Studi kasus untuk pendekatan mundur telah disebutkan bahwa PT. Bangkrut Abadi yang menjual pakan ternak ingin memasarkan produknya ke wilayah Bogor dari lokasi pabrik yang terletak di Bekasi.  Terdapat 10 tempat persimpangan yang dibagi menjadi 4 area untuk mencapai daerah tujuan (Bogor). Masing masing area tersebut memiliki nilai masing masing. Berdasarkan pembahasan terhadap masalah tersebut, maka rute yang didapat adalah 1 ® 2 ® 5 ® 9 ® 10 dengan panjang lintasan sepanjang 13. Hasil tersebut didapatkan dari penyelesaian tiap tiap area pendistribusian. Hasil ini dapat diketahui bahwa dengan mengikuti urutan rute yang telah didapat, maka PT Bangkrut Abadi tidak kesulitan dalam pendistribusian produk karna telah mengetahui jalur yang membuat biaya oprasional dapat ditekan seminimum mungkin. Hasil tersebut yaitu nilai 13 dapat diartikan bahwa PT. Bangkrut Abadi mendapat angka untuk solusi maksimal untuk menekan biaya distribusi produk dari Bogor ke Bekasi. 

Nah selain perhitungan manual, akan disajikan juga perhitungan software, berikut perhitungannya. Langkah pertama dalam melakukan perhitungan software yaitu membuka dahulu software qm.exe. Muncul tampilan seperti yang terlihat pada gambar 4.4.

Gambar 4.4 Tampilan Software Qm

            Ketik huruf M untuk menjalankan perhitungan Dynamic Programming. Muncul tampilan seperti yang terlihat pada gambar 4.5.

Gambar 4.5 Tampilan Software Qm dari Dynamic Programming

Ketik huruf A untuk menjalankan perhitungan Dynamic Programming. Muncul tampilan seperti  yang terlihat pada gambar 4.6.

 

Gambar 4.6 Tampilan Software Qm dari Stagecoach

Ketik huruf N untuk membuat data baru. Muncul tampilan seperti yang terlihat pada gambar 4.7.

Gambar 4.7 Tampilan Software Qm

Tampilan seperti di atas lalu masukan data untuk type of problem lalu berapa banyak stage (tahap) yang harus dilalui dan kemudian memasuka data pada setiap stage (tahap). Muncul tampilan seperti yang terlihat pada gambar 4.8.

Gambar 4.8 Tampilan Software Qm Setelah Input Data

Tekan enter dan akan muncul perintah untuk memasukan data node tujuan dan node starat serta nilai dari kedua node tersebut. Muncul tampilan seperti yang terlihat pada gambar 4.9.

                        

Gambar 4.9 Tampilan Software Qm dari Input Data Node

Masukkan data maka tekan tombol escape (esc) lalu tekan huruf R (Run) untuk menjalankan Software. Muncul tampilan seperti yang terlihat pada gambar 4.10.

                                        Gambar 4.10 Tampilan Perhitungan Data Software Qm

Program software dijalankan (run) maka didapat hasil (final solution) yaitu 9 10 dengan nilai 3, 5 9 dengan nilai 2, 2 5 dengan nilai 5, 1 2 dengan nilai 3. Total panjang lintasan tersebut adalah 13.

          Dalam studi kasus untuk pendekatan mundur telah disebutkan bahwa PT. Bangkrut Abadi yang menjual pakan ternak ingin memasarkan produknya ke wilayah Bogor dari lokasi pabrik yang terletak di Bekasi.  Didapatlah 10 tempat persimpangan yang dibagi menjadi 4 area untuk mencapai daerah tujuan (Bogor). Masing masing area tersebut memiliki nilai masing masing. Selesai input data ke software qm.exe, maka rute yang menjadi solusi (final solution) didapat adalah 1 2 5 9 10 dengan panjang lintasan sepanjang 13. Hasil tersebut didapatkan dari penyelesaian tiap tiap area pendistribusian. Berdasarkan hasil ini dapat diketahui bahwa dengan mengikuti urutan rute yang telah didapat, maka PT Bangkrut Abadi tidak kesulitan dalam pendistribusian produk karna telah mengetahui jalur yang membuat biaya oprasional dapat ditekan seminimum mungkin.