. .? \P?q. i"/...a ?.
-
i
.-#'
?r
,
PEMROGRA
RMINISTIK
Oleh INA RUBlA SETlAWATl
G. 26.0766
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANiAN BOGOR 1994
RINGKASAN
Setiawati, Ilia Rirbia.
G 26.0766.
I'e~iirograoian Dinamik Determi~iistik
(Diba~rahbi~i~birrga~i Dra. Berliau Setiawaty, Ms. sebagai penibimbirig Ittanla dan Ir. Bib Parirhi~mSilalahi sebagai pe~r~birubirig anggota). Penlrograman dinamik rnernpakan tek~iikmatematika yang diguuakan iintr~k rnemecahkan
n~asalah per~gan~biiankeputusari
bertahap ganda.
Berdasarban jr~nllahstate penlrogranlan dinan~ikdibagi menjadi pemrogranlari dinarllik dengan satu variabel state dan pemrograman dinaniik dengan beberapa variabel state.
Penelitiai~ ini bertujiran ontuk n~en~pelajarikedua jenis
pemrograman dinan~ikdi atas dengari variabel diskrit maupun kontinu. Masalah utania dalam pemrogranlari dinamik adalah mengubah masalah merljadi persamaan rekursif, untuk keniudian dilakukan perhitungan. Pada umunlnya perhitungan pada penlrograman dinamik beberapa state lebih konipleks. Pada karya tulis ini dibahas pula tiga metode yang dapat digunakan untuk mengurangi perhitungari yaitu metode Lagrange, nietode one at a time dan metode grid kasar. Metode Lagrange dan metode one at a time digunakan untuk mengurangi jumlah variabel state, sedang metode grid kasar digunakan untulc mengurangi nilai variabel state. pendekatan.
Tetapi metode i ~ i i hanya nlempakan
Untuk menghasilkan sol~isi optimal global, ada beberapa
persyaratan yang hams dipenuhi.
PEMROGRAMAN DINAMIK DETERMINISTIK
Oleh
INA RUBIA SETIAWATI G.26.0766
Ktlrya llmiah
Sebagai Salah Satu Syarat untuk M a i h Gelar Sarjana Matematika
pada Fakultas Matematika dan Ilmu Pmgdilhuan Alam di Institut Pertiinian Bogor
JURUSAN MATEMATIKA VAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 1994
.
Judul Karya Ilmiah
:PEMROGRAMAN DINAMIK DETERMIMSTIK
Nama Mahasiswa
:Ina Rubia Setiawati
Nomor Pokok
: G. 26.0766
Diitujui oleh :
1. Komisi Pembimbig
Dm. ~ e i l i a nSetiawatv. Ms. Ketua
2. Ketua Jurusan Matematii Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. Ir. Siwadi
Tanggal Lulus :
Q 2 NAY i994
'
Penulis dilahirkan pada tanggal 7 Ja~luari1971 di Pnrwokerto Jawa Tengah, sebagai anak ketiga dari empat bersaudara, kehtarga I n ~ a nSar~tosadan Setiawati Jenjang pendidikan peaulis dinlnlai dari Sekolah Dasar Karitas di Purwoke~lo, lulus tahun 1983.
Menyelesaikan Sekolah Menengah Pertarna
Susteran di Purwokerlo pada t a h ~ l n1986, dan Sekolah Menengah Atas Negeri 1 Purwokerto pada tah11111989. Pada tahun yang sama penulis diterima sebagai mahasiswa Institut Pertar~iar~ Bogor rnelalr~ijalur USMI, dan setahnn kemudian diterima di jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahnan Alam dengan p e ~ i r ~ n j aSosial ~ ~ g Ekonomi.
KATA PENGANTAR
Puji syukur penulis pa~ijatkankepada Tuhan Yaug Maha Esa atas segala rahmat dan k a r ~ r ~ iyarig i a telah dili~ilpahliar~ kepada pe~~ulis, sehingga karya tolis ini dapat diselesaikar~. Pada kesempata~~ iui penulis nre~rgucapltai~ terima kasih yang sebesarbesarnya kepada :
1.
Ibu Dra. Berlian Setiasaty, Ms. sebagai pe~nbimbiog I yalig telah memberikan saran, nias~~karl dao dorollgall s e l a ~ i ~perlrrlis a me~~yelesaikan karya tulis i ~ rmaupun i sebagai perldidik selan~apenulis n~enuntutilmu di Jurosan Matematika.
2.
Bapak Ir. Bib P a n ~ h u n lSilalahi sebagai perubin~bing I1 yang telah r~~eniberikan saran selanla per~ulis~t~enyelesaikan karya tulis ini.
3.
Segenap staf pengajar Jurusan Maten~atikayang telah n~emberikanbekal dibidang keahlian matematika.
4.
Seluruh staf tata usaha dan perpustakaan J u n ~ s a nMatematika.
5.
Seluruh
teman
yang
telah
banyak
men~bantu penulis
dalan~
menyelesaikan karya tulis ini.
6.
Mama serta kakak dan adik yang selalu nlernberikan dorongan dari selahl mendoakan penulis.
7.
Semua pihak yang telah membantu d a l a n ~n~enyelesaikankarya tulis ini. Mudah-mudahansemua kebaikan r a n g telah diberikan niendapat imbalan
sepadan dari Tuhan Yang Maha Esa.
Akhiruya penulis berharap agar hasil
karya tulis dapat dimanfaatkarl oleh pihak-pihak yang memerlukan
Bogor, Mei 1994
.
DAFTAR IS1 DAFTAR TABEL DAFTAR GAMBAR BABI
PENDAHULUAN
..........................................
...................... Pemecahan Masalah Bartahap Ganda . . . . . . . . . . . . . . . . . . . . . . . . . . Prinsip Keoptimalan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pembentukan Persamaan Rekursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Syarat Pembentukan Persamaan Rekursif . . . . . . . . . . . . . . . . . . . 2.3.2. Pembentukan Persamaan Rekunif Secara Umum . . . . . . . . . . . . . . Karakteristik Pemrograman Dinamik . . . . . . . . . . . . . . . . . . . . . . . . . .
BAB I1 KONSEP DASAR PEMROGRAMAN DINAMIK 2.1. 2.2. 2.3.
2.4.
BAB 111 BEBERAPA KASUS DALAM PEMROGRAMAN DINAMIK
..............
................... 3.2. Masslah dengan Beberapa Variabel Stole . . . . . . . . . . . . . . . . . . . . . . 3.2.1. Variabel Diskrit dan Kendala Penjumlahan . . . . . . . . . . . . . . . . . 3.2.2. Variabel Diskrit dan Lebih dari Satu . . . . . . . . . . . . . . . . . . . . . 3.3. Pengurnngan Perhitungan dengan Beberapa Metcde . . . . . . . . . . . . . . . . 3.3.1. Metode Pengali Lagrange . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2. Metode One nt n Tinre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.3. Metode Pendekatan Grid Kasar . . . . . . . . . . . . . . . . . . . . . . . . BAB IV PENERAPAN PEMROGRAMAN DINAMlK . . . . . . . . . . . . . . . . . . . . . . . . BAB V KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DAFTARPUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LAMPIRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.
Penuograman Dinamik Detenninistik Satu Sfare
1 1
1 3 3 3 5 5
6
6 14 14 16 17 17 18 20 22 24 24 24 24 26
Teb
halaman
Tabel 3.1.2.
................................. 7 Nilai Optimal t.(d..x.) uotuk Cont.. h 3 . l . l . . . . . . . . . . . . . . . . . . . . . . 8
Tahrl 3.1.3.
Nilai Optinial f:(d2.x,) untu l. Cootoll 3.1.1
Tahel 3 .I.?.
N i l ~ i0ptini;tl f:(d,.x?) untuk Conlc>li3.1.2
Tahel 3.1.1.
Nilai Optimal f.(d..x.)
...................... ......................
Tahrl 3.2. I . I . Nilai Optimal f,(x...x,.) untuk Contoll 3.2.1.1
8 9
. . . . . . . . . . . . . . . . . . . 15
untuk Contoh j.2. I . I
...................
15
Nilai Optimal f,(x,,.x2.) untuk Contoh 3.2.2.1
...................
16
................... Tahel 3.3.2.1. Nilai Optimal pada Tahap 2 dan Tahap 3 untuk Contoh 3.3.2.1 . . . . . . . . . T a k l 3.3.3. l . Nilai Optimal f.(x,.d,) untuk Contoh 3.3.3.1 . . . . . . . . . . . . . . . . . . . .
16
Tahel j.2.1. 2. Nilai Optimal f:(x.,.x,.) Tahel 3.2.2.1. Tabel 3.2.2.2.
Nilai Optimal f3(xI2.x2-)untuk Contoh 3.2.2.1
T a k l 3.3.3.2.
Nilai Optimal fi(x,.d,) untuk Contoll 3.3.3.1
Tahel 3.3.3.j.
Nilai Optimal f;(x,.d;) untuk Contoh 3.3.3.1
.................... ....................
20 21 21 21
DAFTAR GAMBAR Taks Galnhar 2.1.1. Ruta Pqjalanan dari Katn I kz Kota 10............................. Gamhar 3 . 1 . 1 . Nilai Maksimum Kuwa Notrcorn.er...................................
DAFTAR LAMPIRAN
Lampiran I .
Beherapa Teorema dan Detinisi yang Dihuluhkan
Lan~piran2.
Program nntuk Mencari Produksi Optimal
