PENGGUNAAN DYNAMIC PROGRAMMING UNTUK MEMILIH JALUR TRANSPORTASI DENGAN BIAYA MINIMUM

Print
Category: Bangunan
Last Updated on Monday, 20 April 2015 Published Date Written by supono

 PENGGUNAAN DYNAMIC PROGRAMMING UNTUK MEMILIH JALUR TRANSPORTASI DENGAN BIAYA MINIMUM

 

 Supono

Widyaiswara Madya, Departemen Bangunan PPPPTK BOE Malang

 

 Abstrak

 Apabila kita akan melakukan perjalanan dengan jarak yang jauh dan tidak ada alat transportasi yang langsung sampai ke tempat tujuan, maka perjalanan tersebut dapat kita tempuh dengan cara berantai. Perjalanan berantai artinya bahwa tiket yang kita beli hanya untuk dipakai sampai ke kota berikutnya, sedangkan untuk menuju kota selanjutnya lagi kita harus membeli tiket baru. Pada perjalanan berantai dimungkinkan adanya beberapa pilihan jalur yang bisa kita lalui untuk bisa sampai ke kota tujuan. Dalam kondisi seperti itu, biasanya kita akan menentukan salah satu jalur yang terbaik yang akan kita lalui dengan mempertimbangkan aspek tertentu. Aspek tersebut misalnya biaya, jarak tempuh, waktu tempuh, kemudahan memilih moda transportasi, maupun kenyamanan dalam perjalanan. Kita mengharapkan bahwa dari setiap aspek yang kita pilih, kita mendapatkan kondisi yang optimal.

Untuk menghitung hasil yang optimal dari setiap aspek dari perjalanan itu, kita bisa memakai suatu teknik yang dinamakan Dynamic Programming atau Program Dinamik.Pada pembahasan ini, aspek yang kita bahas adalah permilihan jalur transportasi dengan memperhatikan biaya perjalanan yang minimum.

Kata Kunci: Dynamic Programming, Jalur Transportasi, Biaya Minimum

 

 Pendahuluan

Metode Dynamic Programming (Program Dinamik) ini pertama kali dikembangkan oleh Richard E. Bellman pada tahun 1957. Dynamic Programming atau Program Dinamik adalah suatu teknik matematika yang digunakan untuk mengoptimalkan proses pengambilan keputusan secara bertahap-ganda. Dalam teknik ini, keputusan yang menyangkut suatu persoalan dioptimalkan secara bertahap dan bukan sekaligus. Jadi, inti dari teknik ini adalah membagi satu persoalan menjadi beberapa bagian persoalan yang dalam program dinamik disebut tahap, kemudian memecahkan tiap tahap dengan mengoptimalkan keputusan atas tahap sampai seluruh persoalan telah terpecahkan. Keputusan optimal atas seluruh persoalan ialah kumpulan dari sejumlah keputusan optimal atas seluruh tahap yang kemudian disebut sebagai kebijakan optimal.

Pendekatan Program Dinamik didasarkan pada prinsip optimasi yang mengatakan kurang lebih demikian, “Suatu kebijakan optimal mempunyai sifat bahwa apapun keadaan dan keputusan awal, keputusan berikutnya harus membentuk suatu kebijakan optimal dengan memperhatikan keadaan dari hasil keputusan pertama”. Prinsip ini mengandung arti bahwa:

a. Kita diperkenan untuk mengambil keputusan yang terbaik bagi tahap persoalan yang masih tersisa tanpa melihat kembali keputusan yang diambil pada tahap yang sudah berlalu.

b. Dalam rangkaian keputusan yang telah diambil, hasil dari masing-masing tergantung pada hasil keputusan sebelumnya dalam rangkaian.

 

Prosedur Perhitungan

Teknik perhitungan program dinamik terutama didasarkan pada prinsip optimasi recursive (bersifat pengulangan) yang diketahui sebagai prinsip optimalisasi (principle of optimality). Proses ini mengandung arti bahwa bila dibuat keputusan multistage mulai pada tahap tertentu, keputusan untuk tahap-tahap selanjutnya tergantung pada ketetapan tahap permulaan tanpa menghiraukan bagaimana diperoleh suatu ketetapan tertentu tersebut. Untuk memudahkan pemahaman prinsip optimalisasi, dipakai pemecahan masalah jalur optimum. Bila fn(S) merupakan biaya total minimum yang dihubungkan dengan jalur optimum dalam network, notasi Caj adalah biaya yang terlibat dalam pergerakan dari kota asal pada tahap tertentu ke kota berikutnya dalam tahap selanjutnya. Kemudian persamaan untuk keputusan optimal dapat dinyatakan sebagai berikut:

 fn(S) = minimum [ csj + fn-1(j)] ,     pada kasus ini n = 1, 2, 3, 4.

(s,j) dalam jalur

Di mana fn(S) adalah biaya minimum perjalanan dari kota asal dalam satu tahap ke kota terakhir. Langkah singkat ini dinamakan sebagai sebuah rekursive algorithm, dan persamaan rumusnya dinamakan reqursive equation. Sebuah objek disebut berulang (rekursif, recursive) jika setiap objek mengandung dirinya sendiri atau didefinisikan dengan dirinya sendiri. Hubungan ini dapat ditemukan tidak hanya dalam matematika, tetapi juga pada kehidupan sehari-hari. Dalam matematika, definisi rekursif sebuah fungsi adalah definisi fungsi yang menggunakan fungsi tersebut.

Kasus (Pemilihan Jalur Transportasi dengan Biaya Minimum)

Misalnya, suatu hari kita mau mengadakan perjalanan ke suatu kota ke arah barat. Perjalanan berantai merupakan satu - satunya cara yang ada pada transportasi umum untuk mengadakan perjalanan dari Timur menuju ke arah Barat. Pada peta digambarkan jalur perjalanan yang ada. Dari peta tersebut diketahui juga bermacam - macam jalur perjalanan berantai yang ada seperti pada gambar 1.

           

 Setiap kotak pada peta merupakan sebuah State, dan selanjutnya dalam tulisan ini kita sebut dengan istilah Kota. Simbol untuk State adalah s. Dan setiap State diberi nomor untuk memudahkan kita dalam melakukan operasi hitung. Kemudian jalur perjalanan dibagi menjadi empat stage atau Tahap seperti pada gambar 2.

          

 Angka-angka di antara kotak merupakan biaya perjalanan antar kota. Simbol untuk biaya adalah c, sedangkan s adalah kota asal dan j adalah kota tujuan. Jadi csj menunjukkan  biaya perjalanan dari kota asal s ke kota tujuan j. Nilai biaya perjalanan antar kota dibuat dalam angka kecil (satuan dan puluhan) untuk memudahkan hitungan.

 

Proses Perhitungan

Untuk memudahkan perhitungan, kita gunakan tabel. Ada satu tabel untuk setiap Stage n (Tahap n). Jadi untuk menyelesaikan perhitungan ini akan ada 4 tabel yaitu tabel 1, 2, 3, dan 4.Setiap tabel dibagi lagi menjadi 2 (dua) bagian yaitu tabel sebelah kiri dan tabel sebelah kanan.

           

 Tabel sebelah kiri mempunyai baris untuk setiap State masukan (dalam pembahasan ini kita namakan Entering State/Kota Asal), dan juga mempunyai kolom untuk Tujuan (Decision). Tujuan (Decision) ini merupakan Kota Tujuan yang ada pada tahap berikutnya. Contoh untuk n = 1 atau kita sebut Tabel 1, ada dua baris untuk kota 8 dan kota 9, dan hanya ada satu kolom untuk kota 10, dimana kolom tersebut merupakan tujuan dari kota 8 dan kota 9. Pada pojok tabel sebelah kiri atas, terdapat simbol s yang merupakan simbol untuk Entering State/Kota Asal dan simbol j untuk Tujuan (Decision).

Untuk mengisi angka di dalam tabel, kita mulai dengan mengisi kolom pertama.Pada baris pertama kita isi dengan angka 8. Angka ini menunjukkan Kota Asal 8. Sedangkan pada baris kedua kita isi dengan angka 9 (Kota Asal 9). Kemudian pada baris Judul dibawah Tujuan (Decision), kita isi dengan angka 10.Angka 10 ini merupakan tujuan dari kota 8 dan kota 9.

Berikutnya, kita mengisi isian pada baris pertama kolom kedua. Angka di dalam sel ini merupakan biaya dari kota 8 ke kota 10 ditambah dengan jumlah total biaya perjalanan minimum dari kota 10 sampai kota terakhir.Sebagai catatan bahwa kota 10 merupakan kota terakhir, sehingga perjalanan berhenti di kota 10. Dengan demikian sudah tidak ada lagi biaya yang dikeluarkan untuk melakukan perjalanan (biayanya 0).Biaya dari kota asal (s) ke kota tujuan (j) diberi simbol csj. Sedangkan jumlah total biaya perjalanan minimum pada kota berikutnya diberi simbol fn-1(j).Biaya perjalanan dari kota 8 ke kota 10 adalah 1, sedangkan jumlah total biaya perjalanan minimum dari kota 10 sampai kota terakhir adalah 0 (karena perjalanan berhenti di kota 10). Sehingga perhitungan pada sel ini adalah 1 + 0 = 1.Untuk mengisi sel pada baris kedua kolom kedua, langkah perhitungannya sama dengan cara mengisi sel pada baris pertama kolom kedua.

Langkah selanjutnya yaitu kita memilih jumlah total yang paling kecil pada setiap baris. Caranya yaitu membandingkan angka-angka dalam sel yang ada di bawah kota-kota tujuan (Decision/Tujuan). Kemudian kita pilih angka yang paling kecil. Angka ini merupakan biaya terkecil atau minimum dan selanjutnya kita beri simbol fn(s). Sedangkan kota tujuan (Decision) yang memberikan biaya terkecil ini kita beri simbol jn(s). Kedua hitungan tersebut kita taruh pada tabel sebelah kanan. Untuk memperjelas isian pada sel-sel yang ada di tabel sebelah kanan pada tabel 1, kita bisa lihat asal usul dari setiap angka yang ada dalam sel tersebut. Sebagai tambahan, untuk saat ini warna kuning yang ada pada beberapa sel dalam tabel 1 ini kita abaikan terlebih dahulu. Dan akan kita jelaskan pada akhir perhitungan. Sampai di sini perhitungan untuk tabel 1 sudah selesai.

Proses perhitungan kita lanjutkan pada Tabel 2 (n = 2). Untuk masuk ke kota tujuan (dalam hal ini adalah kota 8 dan kota 9), kita dapat memilih dari salah satu kota yaitu dari kota 5, kota 6, atau kota 7. Untuk menempatkan kota-kota asal tersebut dalam tabel kita memerlukan tiga baris. Sedangkan kota-kota tujuan kita tempatkan pada kolom. Dengan demikian kita memerlukan dua kolom.

           

 Proses perhitungan Tabel 2 ini sebenarnya sama dengan proses perhitungan pada Tabel 1. Namun ada beberapa hal yang perlu dijelaskan di sini. Kita mulai dengan sel baris pertama kolom pertama yaitu asal usul penjumlahan 7 + 1. Angka 7 adalah biaya dari kota 5 ke kota 8, sedangkan angka 1 adalah total jumlah biaya minimum sampai ke kota 8 (angka ini bisa kita lihat pada kolom terakhir baris pertama pada Tabel 1). Penjumlahan pada sel-sel berikutnya di bawah kota tujuan 8, asal usulnya dan cara menghitungnya sama seperti itu. Hal ini berlaku juga untuk kota tujuan 9.

Selanjutnya adalah memilih biaya yang paling minimum. Contoh, kita lihat pada baris pertama. Pada sel di bawah kolom kota tujuan 8, hasil penjumlahan 7 + 1 adalah 8. Kemudian hasil ini kita bandingkan dengan hasil penjumlahan yang ada pada sel di bawah kota tujuan 9 (yaitu 5 + 4 = 9). Dari kedua hasil tersebut kita pilih angka yang paling kecil yaitu 8. Dan selanjutnya angka 8 tersebut kita tempatkan pada baris pertama kolom terakhir (kolom kedua dari tabel sebelah kanan).

Angka-angka yang ada pada kolom pertama tabel bagian kanan adalah merupakan kota tujuan(Decision), dimana kota tersebut bisa dijangkau dengan biaya yang minimum. Sebagai contoh kita lihat pada baris pertama pada Tabel 2. Cara menentukann kota tujuan (Decision) dengan biaya yang minimum yaitukita membandingkan hasil penjumlahan pada sel di bawah kota tujuan 8 dengan kota tujuan di bawah kota 9. Dalam contoh ini adalah 7 + 1 = 8 dibandingkan dengan 5 + 4 = 9. Dengan demikian kita memilih angka 8. Selanjutnya kita lihat sel dimana angka 8 ini berada, kemudian kita lihat ke atas (Tujuan/Decision). Ternyata kota tujuannya adalah kota 8. Nah angka 8 inilah yang kita tempatkan pada sel baris pertama kolom pertama pada tabel sebelah kanan Tabel 2. Untuk sel-sel di bawahnya pada kolom yang sama di isi dengan cara seperti di atas.

Analisa perhitungan untuk n = 3, kita tampilkan pada Tabel 3. Cara perhitungannya secara prinsip sama dengan Tabel 2. Sebagai catatan disini bahwa ada dua sel yang kosong. Hal ini disebabkan karena tidak adanya jalur dari kota 2 ke kota 7 dan jalur dari kota 4 ke kota 5. Sekali lagi kita lihat bahwa hanya data yang berasal dari Tabel 2 kolom terakhir yang kita masukkan untuk menghitung pada Tabel 3 ini. Sebenarnya inilah kunci dari semua perhitungan program dinamik.

          

Proses perhitungan berakhir pada n = 4 (Tahap 4). Hasil perhitungannya kita tampilkan pada Tabel 4. Di sana kita dapat melihat bahwa biaya minimum adalah f4(1) = 17 untuk j4(1) = 3. Artinya bahwa total biaya perjalanan yang paling minimum sebesar 17, dengan jalur dari kota 1 ke kota 3.

           

 

Jalur Transportasi dengan Biaya Minimum

Untuk menentukan jalur tansportasi yang mempunyai biaya minimum, kita harus menelusuri melalui tabel yang pernah kita buat. Caranya dengan melihat sel-sel pada setiap tabel yang diberi tanda warna kuning. Kita mulai dengan Tabel 4 (n = 4). Di sana kita menemukan bahwa jalur dengan biaya minimal adalah jalur dari kota 1 ke kota 3. Selanjutnya kita lihat  pada tabel 3 (n = 3). Kita bisa mengetahui bahwa dari kota 3 (baris kedua pada tabel), biaya yang paling minimum adalah kita melanjutkan perjalanan ke kota 7. Berikutnya kita lihat pada tabel 2 (n = 2). Pada tabel 2 kita bisa melihat bahwa ketika kita berangkat dari kota 7, jalur yang membutuhkan biaya minimum adalah menuju ke kota 9. Dan dari kota 9 kita mengakhiri perjalanan di 10. Sebagai kesimpulan, jalur perjalanan yang membutuhkan biaya yang minimum adalah jalur dari kota 1 ke kota 3, kemudian ke kota ke 7, selanjutnya ke kota 9, dan berakhir di kota 10. Dengan total biaya 5 + 7 + 1 + 4 = 17. Jalur transportasi yang mempunyai biaya minimum tersebut bisa kita lihat pada gambar 3.

           

 

Kesimpulan

Program dinamik (Dynamic Programming ) adalah suatu teknik matematika yang digunakan untuk mengoptimalkan proses pengambilan keputusan secara bertahap-ganda. Inti dari teknik ini adalah membagi satu persoalan menjadi beberapa bagian persoalan yang disebut tahap, kemudian memecahkan tiap tahap dengan mengoptimalkan keputusan atas tahap sampai seluruh persoalan telah terpecahkan. Keputusan optimal atas seluruh persoalan ialah kumpulan dari sejumlah keputusan optimal atas seluruh tahap yang kemudian disebut sebagai kebijakan optimal.

Salah satu penggunaan program dinamik (Dynamic Programming) adalah untuk menghitung hasil yang optimal dari setiap aspek dari perjalanan berantai. Perjalanan berantai artinya bahwa tiket yang kita beli hanya untuk dipakai sampai ke kota berikutnya, sedangkan untuk menuju kota selanjutnya lagi kita harus membeli tiket baru. Pada perjalanan berantai dimungkinkan adanya beberapa pilihan jalur yang bisa kita lalui untuk bisa sampai ke kota tujuan. Dalam kondisi seperti itu, biasanya kita akan menentukan salah satu jalur yang terbaik yang akan kita lalui dengan mempertimbangkan aspek tertentu.

 Pada pembahasan ini, aspek yang dibahas adalah permilihan jalur transportasi dengan memperhatikan biaya perjalanan yang minimum. Dari pembahasan diketahui bahwa jalur perjalanan yang membutuhkan biaya yang minimum adalah jalur dari kota 1 ke kota 3, kemudian ke kota ke 7, selanjutnya ke kota 9, dan berakhir di kota 10. Dengan total biaya 5 + 7 + 1 + 4 = 17.

 

 Referensi

Siagian, P. 2006. Penelitian Operasional. Teori dan Praktek. Jakarta, Penerbit Universitas Indonesia (UI-Press).

Wagner, Harvey.M. 1978. Principles of Operations Research. New Delhi, Prentice Hall of India Private Limited.

Yamit, Zulian. 2003. Manajemen Kuantitatif untuk Bisnis (Operations Research). Yogyakarta, Penerbit: BPFE-Yogyakarta.