Dynamic
Programming
Raihan Dara Lufika, S.T., [Link]
Introduction
Banyak masalah industri yang melibatkan pencarian nilai
untuk variabel keputusan tertentu yang memaksimalkan atau
meminimalkan fungsi tujuan tertentu.
Masalah seperti itu disebut masalah pengoptimalan.
Fungsi tujuan biasanya mewakili keuntungan, pendapatan,
efisiensi, dll. (Untuk masalah maksimalisasi) atau biaya,
waktu, pemborosan, dll. (Untuk masalah minimisasi).
Secara matematis, masalahnya adalah memilih nilai untuk
variabel keputusan x1,. . . , xn dari beberapa himpunan X
yang layak untuk memaksimalkan / meminimalkan nilai
tujuan f (x1,..., xn).
Pemrograman dinamis adalah teknik yang ampuh untuk
memecahkan jenis masalah pengoptimalan tertentu.
Tidak ada rumusan matematis standar dari masalah
pemrograman dinamis.
Pemrograman dinamis adalah pendekatan solusi daripada
algoritma tertentu.
Prinsip Optimalitas Bellman
Misalkan P menjadi jalur terpendek dari A ke B dan misalkan Z menjadi titik
perantara di P.
Kemudian prinsip optimalitas menyatakan bahwa porsi P yang berakhir di Z
merupakan jalur terpendek dari A ke Z.
Mengapa? Misalkan, sebaliknya, ada jalur P 'yang lebih pendek dari A ke Z.
Kemudian kita dapat membangun jalur baru dari A ke B sebagai berikut:
berjalan sepanjang P 'dari A ke Z, dan kemudian berjalan sepanjang P dari Z
ke B.
Tetapi jalur baru ini jelas lebih pendek dari P, yang bertentangan dengan
optimalitas P.
Pemrograman dinamis melibatkan pembagian
masalah pengoptimalan menjadi beberapa tahap, di
mana a keputusan kebijakan diperlukan di setiap
tahap.
Sistem yang sedang dipertimbangkan dapat
mengasumsikan berbagai kondisi di setiap tahap.
Keputusan kebijakan di setiap tahap memindahkan
Elemen sistem dari kondisi saat ini ke kondisi baru di tahap
berikutnya.
Notasi:
Pemrograman N = jumlah tahapan
k = label tahapan saat ini (k = 1,..., N)
Dinamis sk = keadaan di tahap k
xk = variabel keputusan dalam tahap k
xk ∗ = nilai optimal xk (sk diberikan)
Prinsip Optimalitas:
Prinsip optimalitas berarti bahwa keputusan kebijakan yang
optimal pada setiap tahap hanya bergantung pada keadaan
saat ini dan bukan pada bagaimana keadaan saat ini dicapai.
Fungsi nilai fk (sk) adalah salah satu ide kunci dalam
pemrograman dinamis. Kami biasanya mendefinisikan fk (sk)
sebagai berikut:
◮ Nilai fungsi tujuan yang optimal untuk tahap 1,. . . , k,
Elemen mengingat bahwa sistem berakhir dalam keadaan sk pada
tahap k (rekursi maju); atau
◮ Nilai fungsi tujuan optimal untuk tahapan k,. . . , N, mengingat
Pemrograman sistem dimulai
dalam keadaan sk pada tahap k (rekursi mundur).
Dinamis Tugas utama dalam pemrograman dinamis adalah
mendapatkan persamaan pengulangan yang mengekspresikan
fk baik dalam fk −1 atau fk +1.
Kami menyelesaikan persamaan pengulangan ini untuk
mendapatkan fk (sk) untuk semua status dan semua tahapan;
solusi dari masalah optimasi kemudian dapat ditentukan.
Prosedur dimulai dengan menemukan kebijakan optimal untuk
tahap pertama (rekursi maju) atau tahap terakhir (rekursi
mundur).
Misalkan kita perlu mengalokasikan satu sumber daya dalam
persediaan terbatas untuk sejumlah kegiatan independen.
Tujuannya adalah untuk mengoptimalkan distribusi sumber daya
dengan memaksimalkan pengembalian total.
Notasi:
N = jumlah kegiatan
S = total pasokan sumber daya
xk = jumlah sumber daya yang dialokasikan untuk aktivitas k
(integer)
gk (xk) = return yang diperoleh dengan mengalokasikan xk unit
sumber daya ke aktivitas k
MASALAH ALOKASI
SUMBER DAYA
MASALAH ALOKASI
SUMBER DAYA
MASALAH
ALOKASI
SUMBER
DAYA
MASALAH
ALOKASI
SUMBER
DAYA
Example
Seorang petani memiliki 5 ton pupuk untuk didistribusikan di antara 3
tanaman. Hasil panen yang sesuai dengan setiap tingkat pemupukan
ditunjukkan pada tabel di bawah ini (kami mengasumsikan bahwa
pemupukan diterapkan dalam jumlah bilangan bulat).
Ini adalah masalah alokasi sumber daya dengan
N = 3 dan S = 5
Kami akan menggunakan program dinamis dengan rekursi maju untuk
menentukan alokasi pupuk yang optimal.
EXAMPLE
CONTINUED
Karena f3 (5) = 12, hasil panen maksimum yang dapat dicapai adalah 12.
Untuk menentukan alokasi pupuk yang optimal, kita bekerja mundur dari tahap 3:
◮ Karena s3 = S = 5, alokasi optimal untuk krop 3 adalah x3 ∗ = 3.
◮ Maka tinggal s2 = 5 - x3 ∗ = 2 ton pupuk untuk tanaman 1 dan 2. Dari tabel tahap
2, jika s2 = 2, alokasi optimal untuk tanaman 2 adalah x2 ∗ = 1 atau x2 ∗ = 2.
◮ Dua solusi optimal: x1 ∗ = 1, x2 ∗ = 1, x3 ∗ = 3 dan x1 ∗ = 0, x2 ∗ = 2, x3 ∗ = 3.
Apa yang terjadi jika hanya tersedia 4 ton pupuk, bukan 5 ton?
Dalam kasus ini, kami memodifikasi solusi kami dengan menghitung f3 (4) dan
menambahkan hasilnya ke tabel tahap 3.
KNAPSACK PROBLEM
Masalah knapsack melibatkan penentuan barang
paling berharga untuk dibawa di ransel. Strukturnya
mirip dengan masalah alokasi sumber daya.
Notasi:
N = jumlah item
W = kapasitas berat ransel
wk = bobot item k vk = nilai item k
xk = jumlah unit item k di ransel
KNAPSACK PROBLEM
Perumusan:
◮ Tahap k sesuai dengan item k.
◮ Status pada tahap k adalah jumlah total bobot yang
dialokasikan untuk item 1,. . . , k.
◮ Variabel keputusan pada tahap k adalah jumlah unit item k
yang dimasukkan ke dalam ransel.
Persamaan Pengulangan:
Misalkan fk (sk) menunjukkan nilai total maksimum yang dapat
dicapai dengan mengalokasikan unit bobot sk ke item 1,. . . , k.
Kami menempatkan xk unit item k ke dalam ransel dan
kemudian secara optimal mendistribusikan sisa berat sk - wk xk
di antara item 1 ,. . . , k - 1. Ini memberikan nilai total:
KNAPSACK PROBLEM
KNAPSACK PROBLEM
KNAPSACK PROBLEM
EXAMPLE
Kapal seberat 9 ton dapat memuat satu atau lebih dari
empat item. Tabel di bawah ini memberikan berat
satuan (dalam ton) dan nilai satuan (dalam ribuan
dolar) untuk setiap item. Tujuannya adalah memuat
kapal dengan kargo paling berharga.
Ini adalah knapsack problem dengan N = 4 and W = 9
Because wk and W are integers, the state can only
assume integer values.
Backward recurrence equation:
EXAMPLE
CONTINUED
Thanks!