MAKALAH RISET OPERASI
“DYNAMIC PROGRAMMING (PROGRAM DINAMIK)”
Dosen Pengajar : Marline S. Paendong [Link], [Link]
Disusun Oleh Kelompok 2 :
Fitriana Pandiangan Citra Filadelfia Manoppo
[Link] (18101103060) Fanda Tumiwa
Tiffany Celine Ukus Firmina Sorlury
Gretti Euodia Kumaseh (18101103074) Ester Tindi
Tania Gam Edo Kahimpon
Jon Prasetio Bawues Nevia Manangka
Christin Esther Palit (18101103030) Yuni Kristina Ninia(`18101103070)
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
UNIVERSITAS SAM RATULANGI
MANADO
2020
DYNAMIC PROGRAMMING (PROGRAM DINAMIK)
[Link]
Dynamic Programming adalah suatu Teknik kuantitatif yang digunakan untuk membuat suatu
rangkaian keputusan yang saling berkaitan (Hillier & Lieberman, Introductions to Operations
Research, sixth edition).
Dynamic Programming adalah prosedur matematis yang terutama dirancang untuk
memperbaiki efisiensi perhitungan masalah pemrograman matematis tertentu dengan
menguraikannya menjadi bagian-bagian masalah yang lebih kecil ([Link]
Operations Research : An Introduction, seventh edition).
Jadi, berdasarkan kedua definisi diatas dapat disimpulkan bahwa dynamic programming
merupakan suatu pendekatan solusi untuk pengoptimalan (maksimum atau minimum) dengan
menguraikan pokok masalah menjadi sub-sub masalah yang lebih kecil yang terkait satu sama
lain dengan tetap memperhatikan kondisi dan Batasan permasalahan tersebut.
Istilah - istilah yang biasa digunakan dalam program dinamik antara lain:
Stage (tahap) adalah bagian persoalan yang mengandung decision variable.
Alternatif, pada setiap stage terdapat decision variable dan fungsi tujuan yang
menentukan besarnya nilai setiap alternative.
State, state menunjukkan kaitan satu stage dengan stage lainnya, sedemikian sehingga
setiap stage dapat dioptimisasikan secara terpisah sehingga hasil optimasi layak untuk
seluruh persoalan.
Fungsi Transisi menunjukkan perubahan keadaan dalam setiap tahap. Fungsi Transisi
dapat ditulis sebagai berikut
Sj = Xj + Sj-1 - Dj
[Link]
Adapun beberapa karakteristik problem pemrograman dinamik yaitu:
a. Problem dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil
satu keputusan.
b. 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.
c. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang
bersangkutan ke status berikutnya pada tahap berikutnya.
d. Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan
pada tahap sebelumnya.
e. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status
pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.
f. Prinsip optimalitas berlaku pada persoalan tersebut.
Pemrograman dinamik probabilistik berbeda dengan pemrograman dinamik deterministik.
Dimana pemrograman dinamik deterministik, pada tahap berikutnya sepenuhnya ditentukan
oleh keadaan dan keputusan kebijakan pada tahap sebelumnya, sedangkan pemrograman
dinamik probabilistik, terdapat suatu distribusi probabilitas keadaan mendatang yang
distribusi peluang ini tetap ditentukan oleh keadaan dan keputusan kebijakan pada keadaan
sebelumnya. Selanjutnya terdapat dua hal dalam pemrograman dinamik probabilistik yaitu:
a. Stage berikutnya tidak seluruhnya ditentukan oleh state dan keputusan pada stage saat ini,
tetapi ada suatu distribusi kemungkinan mengenai apa yang akan terjadi.
b. Distribusi kemungkinan ini masih seluruhnya ditentukan oleh state dan keputusan pada
stage saat ini.
Struktur dasar yang dihasilkan pemrograman dinamis probabilistik diuraikan secara diagram
dalam Gambar 1.
Gambar 1.
Di mana:
a. S melambangkan banyaknya keadaan yang mungkin pada tahap (stage) n + 1 dan keadaan
ini digambarkan pada sisi sebelah kanan sebagai 1,2,…,S. 𝑠𝑛 𝑥𝑛 1 2 s
b. (p1,p2,...ps) adalah distribusi kemungkinan dari terjadinya suatu state berdasarkan state Sn
dan keputusan Xn pada stage n
c. Ci adalah kontribusi dari stage n terhadap fungsi tujuan, jika state berubah menjadi state i
d. fn(Sn, Xn) menunjukkan jumlah ekspektasi minimal dari tahap n ke depan, dengan
diberikan status dan keputusan pada tahap n masing-masing Sn dan Xn.
C. Bentuk Umum Dynamic Programming
Masalah Program dinamik dapat dinyatakan dalam bentuk umum :
Maksimisasi :
Dengan Batasan :
Dimana :
D. Proses Recursive
Penyelesaian program dinamik dilakukan dengan perhitungan rekursif yang berulang setiap
tahap. Keputusan optimum pada suatu tahap adalah hasil optimum pada tahap tersebut
ditambah hasil optimum tahap sebelumnya.
Ada dua prosedur rekursif yaitu:
a. Forward recursive equation (perhitungan dari depan ke belakang). Program dinamis
bergerak mulai dari tahap 1 sampai tahap n. Peubah keputusan adalah x1, x2, …, xn.
b. Backward recursive equation (perhitungan dari belakang ke depan). Program dinamis
bergerak mulai dari tahap n, terus mundur ke tahap n – 1, n – 2, dan seterusnya sampai tahap
1. Peubah keputusan adalah xn, xn-1, …, x1.