PROGRAM DINAMIS

1. A. Pendahuluan

A.1. Definisi Program Dinamis
Program dinamis adalah suatu  teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. 

Dalam hal ini program dinamis menyediakan prosedur sistematis untuk menentukan kombinasi keputusan yang optimal. 

Tujuan utama model ini ialah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu.
Tidak seperti pemrograman linier, tidak ada bentuk matematis standar untuk perumusan pemrograman dinamis. Akan tetapi, pemrograman dinamis adalah pendekatan umum untuk pemecahan masalah dan persamaan tertentu yang digunakan di dalamnya harus dibentuk sesuai dengan situasi masalah yang dihadapi.

Istilah yang biasa digunakan antara lain:

1. Stage(tahap)  adalah bagian persoalan yang mengandung decision variable.
2. Alternatif, pada setiap stage terdapat decision variable dan fungsi tujuan yang menentukan besarnya nilai setiap alternative.
3. State, state menunjukkan kaitan satu stage dengan stage lainnya, sedemikian serupa sehingga setiap stage dapat dioptimisasikan secara terpisah sehingga hasil optimasi layak untuk seluruh psrsoalan.

A.2. Karakteristik Program Dinamis
Salah satu cara untuk mengenali suatu situasi yang dapat dirumuskan sebagai masalah pemrograman dinamis adalah menyadari struktur dasar masalah tersebut apakah serupa dengan masalah ekspedisi.

Sifat dasar yang menjadi ciri masalah pemrograman dinamis antara lain:

1. Masalah dapat dibagi menjadi tahap-tahap dengan keputusan kebijakan yang dibuat pada masing-masing tahap.

Masalah ekspedisi secara harfiah dibagi menjadi 4 tahap yang sesuai dengan 4 tahap perjalanan. Kebijakan keputusan pada masing-masing tahap adalah kebijakan asuransi jiwa mana yang dipilih (sama dengan tujuan yang dipilih untuk tahap berikutnya). 

Dengan cara yang sama, masalah  pemrograman dinamis lain memerlukan pembuatan suatu urutan keputusan yang saling berhubungan, dengan setiap keputusan diambil pada satu tahap masalah.

1. Masing-masing tahap mempunyai state yang berhubungan dengan kondisi awal tahap.

State pada masing-masing tahap pada masalah ekspedisi adalah Negara bagian (wilayah) tempat pencari harta bisa singgah sementara ketika tiba pada akhir suatu bagian/tahap perjalanan tersebut. 

Secara umum, state adalah bebagai kondisi system yang mungkin pada suatu tahap masalah. Banyaknya state bisa terbatas (seperti dalam masalah ekspedisi) ataupun tidak terbatas.

1. Efek keputusan kebijakan pada setiap tahap adlah mengubah state saat ini menjadi state lain pada awal tahap berikutnya. (mungkin mengikuti pola distribusi tertentu.)

Keputusan pencari harta dalam bentuk tujuan berikutnya, membawanya dari state sekarang kepada state berikutnyadalam perjalanan. Prosedur ini menyatakan bahwa masalah pemrograman dinamis dapat dinyatakan sebagai jaringan. 

Setiap simpul menyatakan state. Jaringan akan terdiri dari kolom simpul, degan setiap kolom menyatakan tahap, sehingga aliran dari suatu simpul hanya dapat melangkah ke kolom yang berada di sebelah kanannya. 

Hubungan dari suatu simpul ke simpul pada kolom berikutnya sesuai dengan keputusan kebijakan yang mungkin untuk menentukan state untuk langkah berikutnya. Nilai yang ditugaskan pada setiap hubungan dapat ditafsirkan sebagai kontribusi langsung terhadap fungsi tujuan dari pembuatan keputusan kebijakan itu. 

Dalam banyak kasus, mencari solusi untuk mencapai tujuan dapat dinyatakan dengan menemukan jalur terpendak atau terpanjang pada jaringan.

1. Prosedur penyelesain dirancang untuk menemukan kebijakan optimal dari keseluruhan masalah, yang menunjukkan keputusan kebijakan mana yang optimal pada setiap tahap untuk setiap state yang mungkin.

Untuk masalah ekspedisi, prosedur penyelesaian membentuk tabel untuk setiap tahap (n) yang menunjukkan keputusan optimal   pada setiap state yang mungkin (s). 

jadi, selain bisa menemukan tiga solusi optimal (rute terbaik) untuk masalah keseluruhan, hasil yang diperoleh juga dapat dipakai sebagai petunjuk bagi pencari harta untuk menentukan langkah jika ia terpaksa dialihkan ke state yang tidak berada dalam rute optimal. 

Untuk masalah apapun pemrograman dinamis menyediakan petunjuk mengenai kebijakan apa yang harus dilakukan pada setiap keadaan yang mungkin terjadi (inilah alasan mengapa keputusan aktual yang dibuat pada saat mencapai state tertentu pada tahap tertentu disebut keputusan kebijakan). 

Penyedian informasi tambahan selain menyatakan solusi optimal (urutan keputusan optimal) dapat berguna dalam berbagai hal, termasuk untuk analisis sensitivitas.

1. Berkaitan dengan state saat ini, kebijakan optimal untuk langkah tersisa bersifat independen terhadap keputusan kebijakan yang telah diambil pada tahap sebelumnya. Oleh karena itu, keputusan optimal selanjutnya  hanya tergantung pada state saat ini dan bukan cara mencapai state saat ini. Inilah prinsip optimalitas untuk pemrograman dinamis.

Sehubungan dengan state tempat pencari harta berada sekarang, kebijakan asuransi jiwa yang optimal (dan rute perjalanannya)dari simpul ini sampai akhir bersifat independen dengan caranya tiba pada state itu. 

Untuk masalah pemrograman dinamis pada umumnya, pengetahuan menyangkut state sekarang dari system menyampaikan semua informasi tentang prilaku sebelumnya yang diperlukan untuk menentukan kebijakan optimal selanjutnya (sifat ini disebut sifat Markovian). 

Setiap masalah yang tidak mempunyai sifat ini tidak bisa dirumuskan sebagai masalah program dinamis.

1. Prosedur penyelesaian dimulai dengan mencari  kebijakan optimal untuk langkah terakhir.

Kebijakan optimal untuk langkah terakhir ini akan menentukan keputusan kebijakan optimal untuk setiap state yang mungkin pada tahap itu. Penyelesaian dari masalah satu tahap ini umumnya sangat  mudah, seperti terlihat pada masalah ekspedisi.

1. Tersedia hubungan rekursif yang menunjukkan kebijakan optimal untuk tahap n dengan dasar kebijakan optimal untuk lanhkah n+1.

Hubungan rekursif untuk masalah ekspedisi adalah
Oleh karena itu, untuk menemukan keputusan kebijakan optimal saat mulai dari state s pada tahap n, Anda akan memerlukan nilai minimum untuk  x_n. untuk masalah tertentu, biaya minimum yang diperoleh  dengan menggunakan nilai x_n, kemidian mengikuti kebijakan optimal saat mulai dari state s pada tahap n+1.
Bentuk yang tepat dari hubungan rekursif ini berbeda dalam masalah pemrograman dinamis yang berbeda. Krterangan dari notasi tersebut:
N= jumlah tahap.
n = label untuk tahap sekarang (n=1,2,…N).
= state sekarang untuk tahap n.
= variable keputusan untuk tahap n.
= kontribusi tahap n,n+1,…N pada fungsi tujuan jika system dimulai dari state pada tahap n.
keputusan selanjutnya adalah dan keputusan optimal belum dibuat.
hubungan rekursif akan selalu berbentuk:

1. 
   

Pergerakan mundur (backward) seperti yang ditunjukkan dalam masalah ekspedisi, dengan kebijakan optimal diperoleh secara berurutan pada tahap       4,3,2, dan 1⁴. Untuk semua masalah pemrograman dinamis, dapat dibentuk table sebagai berikut untuk setiap tahap (n=N,N-1,…,1)
Jika tabel seperti ini sudah diperoleh untuk tahap awal (n=1), masalah sudah dipecahkan. Oleh karena state awal telah diketahui, keputusan awal adalah  dalam tabel ini. Nilai optimal variable keputusan lain kemudian ditetapkan dari tabel yang lain secara bergilir menurut state sistem yang dihasilkan oleh keputusan sebelumnya

1. B. Program Dinamis Probablistik

Perbedaan pengunaan program dinamis probablistik dari program dinamis deterministik adalah state pada tahap berikutnya tidak hanya ditentukan oleh state dan keputusan kebijakan pada tahap saat ini, melainkan juga terdapat distribusi probablitas untuk state pada tahap berikutnya. Akan tetapi, distribusi probablitas ini dapat ditentukan berdasarkan state dan keputusan kebijakan pada tahap saat ini. Diagram yang menggambarkan struktur dasar pemrograman dinamis probablistik terdapat pada gambar  berikut:
Dalam diagram ini, misalkan S adalah lambang dari jumlah state yang mungkin terjadi pada tahap n+1 dan menadai state ini pada bagian kanan  gambar dengan 1,2,…S. Sistem akan berpindah ke state i dengan probablitas  P_i (i= 1,2,…S) jika terdapat  dalam state dan keputusan pada tahap ini. Jika sistem menuju sistem i , C_i merupakan kontribusi dari tahap n pada fungsi tujuan.
Jika gambar 1.1 dikembangkan hingga meliputi semua tahap yang mungkin dan keputusan pada semua tahap, biasanya gambar dikenal dengan nama pohon keputusan. Jika pohon keputusan tidak terlalu besar, ia akan menyediakan cara yang berguna untuk merangkum variasi kemungkinan yang mungkin terjadi.
Oleh karena struktur probablitas tersebut, hubungan antara fungsi  dan yang diperlukan lebih rumit daripada pemrograman dinamis deterministik. Bentuk tepat yang dari hubungan ini tergantung pada bentuk fungsi tujuan secara keseluruhan.
Sebagai ilustrasi untuk hal ini, dimisalkan tujuan suatu masalah adalah meminimalkan ekspektasi jumlah kontribusi dari semua tahap. Dalam kasus ini  menyatakan ekpektasi jumlah minimum dari tahap n sampai akhir, dengan catatan jika berada  dalam state dan keputusan pada tahap n. jadi,
dengan
pada nilai minimum yang diambil dari nilai yang layak untuk nilai .

1. C. Contoh Penggunaan Program Dinamis

Contoh Masalah ekspedisi
Masalah ekspedisi (the stage coach problem)adalah suatu masalah yang secara khusus dibuat untuk mengilustrasikan elemen-elemen pemrograman dinamis serta memperkenalkan istilah-istilah pemrograman dinamis. Hal ini berhubungan dengan cerita mengenai pencari harta di Missouri yang memutuskan untuk pergi ke barat bergabung dalam perebutan ladang emas di California pada pertengahan abad ke- 19. Perjalanan ini memerelukan ekspedisi melalui kota – kota yang masih liar dengan ancaman bahaya serangan perampok selalu menghadang. Walaupun simpul awal perjalanan dan simpul tujuan akhir telah di tetapkan, Ia mempunyai pilihan untuk mempertimbangkan melalui Negara bagian mana saja (atau wilayah yang kemudian akan menjadi Negara bagian/setalah ini akan di sebut stip) Perjalanan tersebut harus di lalui rute yang mungkin di lalui tercantum pada gambar 1.2 dengan setiap state di lambangkan dengan lingkaran dan arah perjalanan selalu dari kiri ke kanan. Jadi, diperlukan empat tahap untuk melakukan perjalanan dari simpul awal di state A (Missouri) ke tujuan akhir di state J (California).
Pencari harta ini adalah orang yang sangat memperhatikan keselamatan dirinya. Setelah memikirkan beberapa hal, muncul ide cemerlang untuk menenutkan rute yang paling aman. Polisi asuransi jiwa ditawarkan ke peserta ekspedisi. Oleh karena biaya asuransi untuk melakukan tahapan perjalanan ekspedisi ditentukan berdasarkan evaluasi terhadap keselamatan tahapan tersebut maka rute yang paling aman adalah rute yang mempunyai biaya asuransi jiwa yang  paling murah.
Biaya asuransi standar untuk perjalanan ekspedisi dari state I ke state j, disimbolkan C_n, adalah sebagai berikut:
Penyelesaian Masalah
Secara sekilas, pertama kali dapat dilihat bahwa pemilihan biaya perjalanan termurah yang ditawarkan pada setiap tahap tidaklah menghasilkan keputusan yang optimal secara keseluruhan. Dengan cara ini akan diperoleh rute A→B→F→I→J, dengan total biaya 13. Akan tetapi, dengan mengorbankan sedikit biaya pada suatu tahap dapat memberikan lebih banyak penghematan biaya. Sebagai contoh, rute A→D→F akan lebih murah dibanding A→B→F.
Satu cara yang bisa digunakan untuk memecahkan masalah iniadlah dengan trial and error. Akan tetapi, kemungkinan jumlah rute yang digunakan sangatlah banyak (18), sementara menghitung total biaya untuk setiap rute bukanlah tugas yang menarik (sudah pasti akan menghabiskan waktu).
Untuk masalah ekspedisi, kita mulai dengan masalah yang lebih sederhana, yaitu saat pencari harta hampir menyelesaikan perjalananya dan hanya memerlukan tahap terakhir agar tiba di tujuan. Solusi optimal sudah jelas, yaitu dengan meninggalkan state sekarang menuju state tujuan akhir (state J). Pada setiap iterasi, masalah diperbesar dengan menambah 1 tahap untuk penyelesaian perjalanan  tersebut. Untuk masalah yang telah diperbesar, solusi optimal menuju state mana pada tahap berikutnya dari setiap tahap yang mungkin dapat ditemukan secara mudah dari hasil iterasi sebelumnya. Informasi rinci yang digunakan untuk menggunakan pendekatan ini sebagai berikut:
Perumusan, misalkan variable keputusan  (n=1,2,3,4) adalah state tujuan pada tahap n (tahap ke-n yang sudah ditempuh ekspedisi). Jadi, rute terpilih adalah, dengan
Misalkan  adalah total biaya dari keseluruhan kebijakan terbaik untuk tahap yang  tersisa. Jika diketahui pencari harta benda pada state s, siap untuk memulai tahap ke-n dan memilih  (tidak harus unik, boleh lebih dari satu) yang menghasilkan nilai minimum dan  adalah nilai minimum dari . Dengan demikian diperoleh:
Dimana:
Prosedur penyalesaian. Ketika pencari harta hanya memerlukan satu tahap lagi untuk sampai ke tujuan akhir (n=4), rute berikutnya hanya ditentukan oleh state sekarang (baik H ataupun I) dan tujuan akhirnya , sehingga rute perjalanan ekspedisi terakhir adalah s→J. jadi , solusi langsung untuk tahap n=4 adalah

ketika pencari harta mempunyai dua tahap lagi untuk sampai ketujuan akhir (n=3),prosedur penyelesaian memerlukan  sedikit perhitungan sebagai contoh, anggap bahwa pencari harta berada pada state F. seperti tergambar dibawah ini, langkah berikutnya ia harus menuju ke state H atau I dengan biaya langsung masing-masing atau . Jika ia memilih state H, biaya tambahan minimum yang harus dikeluarkan setelah ia sampai pada state itu adalah(H)=3, seperti pada tabel di atas. Dengan demikian, total biaya untuk keputusan ini adalah 6+3=9. Jika ia memilih state I, total biayanya adalah 3+4=7, yang lebih kecil nilainya.
Jadi, pilihan optimal adalah yang terakhir, = I, karena memberikan total biaya minimum
Perhitungan yang sama juga diperlukan ketika mulai dari 2 state lain yang mungkin s=E dan s=G yang memerlukan 2 tahap lagi sampai tujuan akhir. Untuk masalah n=3:
Penyelesaian untuk masalah tahap kedua (n=2), dengan sisa 3 tahap untuk sampai tujuan akhir, dapat dicari dengan cara yang sama. Dalam kasus ini,. Sebagai contoh, anggaplah pencari harta sedang berada dalam state C, seperti gambar berikut:
Selanjutnya, ia harus menuju ke state E,F, atau G dengan biaya langsung , dan . Setelah sampai disana, biaya tambahan minimum untuk tahap 3 sampai akhir terdapat dalam tabel untuk n=3 yaitu, seperti juga yang telah ditunjukkan di atas simpul E dan F dan di bawah simpul G pada gambar di atas. Hasil perhitungan untuk ketiga alternatif tersebut dapat diringkas sebagai berikut:
Hasil minimum dari ketiga nilai ini adalah 7 sehingga total biaya minimum dari state C ke tujuan akhir adalah, dan tujuan langsung dari state C adalah.
Dengan perhitungan yang sama, jika dimulai dari state B atau D maka akan menghasilkan nilai berikut untuk masalah n=2
Pada baris pertama dan ketiga dalam tabel di atas, perhatikan bahwa E dan F memilki nilai yang sama sebagai nilai minimum  sehingga tujuan selanjutnya dari state B dan D adalah bergerak ke tahap pertama (n=1), dengan masih 4 tahap lagi untuk menuju tujuan akhir, kita dapat menggunakan perhitungan yang sama seperti pada tahap kedua (n=2), kecuali bahwa pada saat ini hanya terdapat satu state s=A, seperti pada gambar di bawah ini.
Perhitungan untuk ketiga alternative tujuan tersebut dapat diringkas sebagai berikut:
Oleh karena 11 merupakan nilai minimum  dan , seperti yang ditunjukkan dalam tabel berikut:
Solusi optimal untuk keseluruhan masalah dapat diperoleh dari 4 tabel di atas. Hasil untuk masalah n=1 menunjukkan bahwa pencari harta harus melangkah ke
state C atau D. Anggap ia memilih  Untuk n=2, hasil untuk s=C adalah . Hasil ini diteruskanpada masalah n=3, yang akan memberikan
untuk s=E, dan untuk masalah n=4 akan menghasilkan . Dengan demikian, salah satu rute optimal adalah A→C→E→H→J. memilih
akan menghasilkan pada 2 rute optimal lainnya, yaitu A→D→E→H→J dan A→D→F→I→J. semuanya akan menghasilkan total biaya
Hasil analisis pemrograman dinamis ini dirangkum pada gambar 1.2. perhatikan bahwa 2 anak panah pada tahap 1 berasal dari kolom pertama dan terakhir
untuk tabel n=1 dan nilai biaya berasal dari kolom sebelum terakhir. Masing-masing anak panah (dan biayanya) berasal dari suatu baris dari tabel lain yang
diperoleh dengan cara yang sama.
GAMBAR 1.3. Tampilan grafis solusi masalah ekspedisi dengan pemrograman dinamis. Setiap panah menunjukkan keputusan kebijakan yang optimal (pilihan terbaik dari tujuan selanjutnya) dari suatu state dan bilangan di dekat state menunjukkan biaya yang diperlukan dari state tersebut sampai tujuan akhir. Mengikuti anak panah yang tebal dari A ke T memberikan tiga alternative soluso optimal (ketiga rute ini memberikan nilai total biaya minimum 11)
Contoh pemrograman dinamis probablistik
Seorang ahli statistic muda percaya bahwa ia telah mengembangkan suatu system agar dapat memenangkan salah satupermainan terkenal di Las Vegas. Rekan-rekannya tidak percaya bahwa system tersebut dapat berhasil sehingga mereka bertaruh dengan nya ia mulai dengan 3 keping taruhan, ia tidak  akan mendapatkan sekurang-kurangnya 5 keping setelah 3 kali permainan. Setiap kali permainan memerlukan taruhan sejumlah keping yang diambil dari dari keping yang tersedia dan menang atau kalah setara dengan mendapatkan atau kehilangan sejumlah keeping tersebut. Ahli statistik ini yakin bahwa system yang dibuatnya akan memberikan kemungkinan 2/3 kemenengan dalam satu kali permainan tersebut.
Asumsikanlah bahwa keyakinan ahli statistik tersebut benar, dan sekarang kita menggunakan pemrograman dinamis untuk menentukan kebijakan yang optimal mengenai jumlah keping yang dipertaruhkan pada masing-masing permainan (ada tiga permainan). Keputusan pada masing-masing permainan harus memperhatikan hasil permainan sebelumnya. Tujuannyaialah memaksimalkan probablitas kemenangan taruhan ahli statistik tersebut dengan rekannya.
Perumusan. Perumusan pemrograman dinamis untuk masalah ini adalah
Tahap n= permainan ke-n (n= 1,2,3,…)
= jumlah keping yang dipertaruhkan pada tahap ke-n
State s_n= jumlah keping yang tersedia untuk memulai tahap n
Definisi state ini dipilih karena dapat menyediakan informasi mengenai situasi sekarang yang diperlukan untuk membuat keputusan optimal tentang banyaknya keping yang harus dipertaruhkan kemudian.
Oleh karena tujuannya ialah memaksimalkan probablitas  ahli statistic tersebut akan menang dalam taruhannya, fungsi tujuan yang harus dimasimalkan pada setiap tahap adalah probablitas penyelesaian ketiga permainan tersebut dengan sekurang-kurangnya 5 keping. (catat bahwa nilai akhir lebih dari 5 keping berarti sama dengan tepat 5 keping, karena taruhan sama-sama dimenangkan). 

Dengan demikian, = probablitas penyelesain ketiga permainan dalam sekurang-kurangnya 5 chip, jika ahli ahli statistic berada pada State s_n di tahap n, membuat                keputusan x_n , dan membuat keputusan optimal pada tahap-tahap selanjutnya.


Ekspedisi untuk funsi  haruslah mencerminkan kenyataan masih terdapat kemungkinan untuk meng akumulasikan 5 keping meskipun ahli statistik tersebut kalah pada satu tahap pernainan. Jika ia kalah pada satu tahap maka state pada tahap selanjutnya menjadi s_n-x_n, dan probablitas ia dapat mengakhiri permainan dengan sekurang-kurangnya 5 keping adalah . jika Ia menang pada suatu tahap maka state berikutnya akan menjadi s_n+x_n, dan probablitas yang bersangkutan adalah . Oleh karena probablitas kemenangan permainan diasumsikan 2/3 maka


[dengan  didefinisikan sama dengan 0 untuk s₄<5 dan sama dengan 1 untuk]. Jadi tidak terdapat kontribusi yang langsung mempengaruhi fungsi tujuan dari tahap n selain pengaruh menjadi apa state selanjutnya.
Hubungan dasar ini terdapat dalam gambar 1.3.
Lantas hubungan rekursif untuk masalah ini adalah:
Untuk n= 1,2,3, dengan  yang sudah didefinisikan di atas.

Prosedur Penyelesaian. Hubungan rekursif tersebut akan membawa pada hasil perhitungan berikut:
Oleh karena itu, kebijakan optimalnya adlah:
Kebijakan ini akan memberikan ahli statistik tersebut probablitas kemenangan sebesar 20/27 saat bertaruh dengan rekannya.
Refrensi

1. Arga, W., Dinamika Dan Integer Programming, BPFE, Yogyakarta, 1985.
2. Dimyati,Tjutju Tarliah dan Dimyati, Ahmad, Operation Research: Model-Model Pengambilan keputusan, Sinar Baru Algesindo, Bandung, 2006.
3. Lieberman, Gerald J., and Hiller, Fredrick S., Introduction operation research, edisi ke-8, ANDI, Yogyakarta, 2008.