PEMROGRAMAN DINAMIS (DYNAMIC PROGRAMMING)

PENDAHULUAN

Program Dinamis (dynamic programming): metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.
Pemrograman dinamis merupakan suatu pendekatan solusi bukan suatu teknik.
Pendekatan solusi adalah merinci suatu masalah menjadi masalah-masalah yang lebih kecil tahapan (stages) beurutan.
Hasil dari suatu keputusan (solusi) pada suatu tahap akan mempengaruhi keputusan tahap berikutnya.
Pemrograman dinamik merupakan teknik matematis yang dapat berguna untuk membuat suatu urutan keputusan yang saling berkaitan
Pemrograman dinamis tidak mempunyai rumusan yang baku
Tiap permasalahan memerlukan perumusan tertentu
Teknik pemrograman dinamis dikenal juga dengan multistage programming

PRINSIP OPTIMALITAS

Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas.
Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal.

Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal.

ongkos pada tahap k +1 =

(ongkos yang dihasilkan pada tahap k ) + (ongkos dari tahap k ke tahap k + 1)

• Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.

• Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.

TINJAU GRAF DI BAWAH INI. KITA INGIN MENEMUKAN LINTASAN TERPENDEK DARI 1 KE 10.

KARAKTERISTIK PERSOALAN PEMORGRAMAN DINAMIS

1. Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.

2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.

3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.

4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.

5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.

6. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.

7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.

8. Prinsip optimalitas berlaku pada persoalan tersebut.

GRAF MULTITAHAP (MULTISTAGE GRAPH). TIAP SIMPUL DI DALAM GRAF TERSEBUT MENYATAKAN STATUS, SEDANGKAN V1, V2, … MENYATAKAN TAHAP.