pemrograman dinamis: contoh kasus dan ...pemrograman dinamis: contoh kasus dan implementasi dengan...

PEMROGRAMAN DINAMIS: CONTOH KASUS DAN IMPLEMENTASI

DENGAN MENGGUNAKAN MICROSOFT EXCEL

Tugas Akhir

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Oleh :

Destika Amalia

143114014

PROGRAM STUDI MATEMATIKA, JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2019

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

i


DENGAN MENGGUNAKAN MICROSOFT EXCEL

Tugas Akhir

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Sains

Program Studi Matematika

Oleh :

Destika Amalia

143114014

PROGRAM STUDI MATEMATIKA, JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2019


ii

DYNAMIC PROGRAMMING: CASE EXAMPLE AND

IMPLEMENTATION BY USING MICROSOFT EXCEL

Thesis

Presented as Partial Fulfillment of the

Requirements to Obtain the Degree of Sarjana Sains

Mathematics Study Program

Written by

Destika Amalia

143114014

MATHEMATICS STUDY PROGRAM

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2019


TUGAS AKIIIR

PEMROGRAMAN DINAMIS: CONTOH KASUS DAN IMPLEMENTASIDENGAII MENGGT]NAKAN MICROSOFT EXCEL

Disusun oleh:

Dosen pembimbing td

YG. Hartoflo, S.Si., M.Sc., Ph.D. Tangg al: 25 Februari ZAI?

4.\Y

ryryffiFFd#

at**b**

iii


TUGAS AKHIR


DENGAh{ MENGGUNAKAI\ MICROSOFT EXCEL

Dipersiapkan dan Ditulis oleh:

Destika Amalia

hlIM:1431 14014

Telah dipertahankan di depan panitia penguji

pada tanggal 28 Februan 2019

dan dinyatakan memenuhi syarat

Susunan Panitia Penguj i

Ir{ama Lengkap

: Sudi Mungkasi, S.Si., M.Math.Sc., Ph.D.

: Dr. rer.'nat. Herry P. Suryawan, S.Si., M.Si:

: YG. Hartooo, S.Si., M.Sc,, Ph.D.

Tanda Tangan

Ketua

Sekretaris

Anggota

Yo gy akart a,EX,tar et 2A W

Fakultas Sains dan Teknologi

I-Jniversitas Sanata Dharma

ffi-RrI;.Math.sc.,Ph.D.&t**j**,#-:;

Dekan

*ffffid['u-


v

HALAMAN PERSEMBAHAN

“Kepuasan terletak pada usaha, bukan pada hasil.

Berusaha dengan keras adalah kemenangan yang hakiki”

Mahatma Gandhi

Tugas akhir ini aku persembahkan untuk:

1. Allah SWT yang telah melimpahkan rahmat dan karunia-Nya sehingga

tugas akhir ini dapat selesai.

2. Ibu dan Ayah yang senantiasa mendoakanku dan memberi perhatian serta

kasih sayang mereka.

3. Ivan, Karin, Dek Tika, Andhika dan Alvin yang selalu mendukung serta

menyemangatiku.

4. Mbah Basuki dan Mbah Sihono di surga sana yang setia menungguku

menyelesaikan tugas akhir ini hingga akhir hayat mereka.


PER}IYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya" bahwa tugas a}fiir yang saya tulis ini

tidak memuat karya orang lain kecuali yang telatr disebutkan dalam daftar

pustaka.

Yogyakarta" \9 tutaret 20 I 9

m/'I tilt Y-VW

Destika Amalia

vi


LEMBAR PERITYATAAIY PERSETUJUA}I

PUBLIKASI KARYA ILMIAH T]NTUK KEPENTINGANI AKADEMIS

yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:

hlama : Destika Amalia

Nomor Mahasiswa : 143 114014

Demi pengembangan ilmu pengetahuan, saya memberikan kepada Perpustakaan

universitas sanata Dharma karya ilmiah saya yang berjudul:


DENGAI\ MENGGT]NAKAN MICROSOT"T EXCEL

beserta perangkat yang diperlukan (bita ada)- Dengan demikian saya memberikan

kepada Perpustakaan universitas sanata Dharma hak untuk menyimpan,

mengalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan

dat4 mendistribusikan secara terbatas, dan mempublikasikannya di Internet atau

media lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya

maupgn memberikan royalti kepada saya selama tetap mencantumkan nama saya

sebagai penulis.

Demikian pernyataan ini yang saya buat dengan sebenamya'

Dibuat di YogYakarta

Pada tanggal: !.? Maret 20 I 9

Yang menYatakan '

Destika Amalia


vii

ABSTRAK

Pemrograman dinamis (DP) adalah metode pemecahan masalah dengan

cara menguraikan masalah menjadi subproblem yang lebih mudah ditangani.

Perhitungannya dilakukan secara rekursif dan solusi optimal dari satu subproblem

digunakan sebagai input untuk subproblem berikutnya. Solusi optimal untuk

seluruh masalah didapatkan ketika subproblem terakhir diselesaikan.

Pemrograman dinamis merupakan cara pendekatan khusus dalam masalah

pengoptimalan yang mudah untuk dipelajari dan diterapkan dalam kehidupan

sehari-hari. Pemrograman dinamis juga dapat diselesaikan menggunakan program

komputer sederhana pada Microsoft Excel.

Dalam tugas akhir ini akan dijelaskan bagaimana cara menyelesaikan

persamaan rekursif yang dihasilkan dari pemrograman dinamis dengan cara

manual dan menggunakan Microsoft Excel. Pada Microsoft Excel akan digunakan

fungsi IF, fungsi MAX dan menu SOLVER untuk menyelesaikan persamaan

rekursif.

Kata kunci: pemrograman dinamis, persamaan rekursif, Microsoft Excel.


viii

ABSTRACT

Dynamic Programming (DP) is a problem-solving method by breaking the

problems down into subproblems that are easier to manage. The calculation is

done recursively and the optimal solution of a subproblem is used as the input of

the following subproblem. The optimal solution for all problems is obtained when

the last subproblem is solved. Dynamic Programming is a particular approach in

optimization problems that is easy to learn and apply in daily basis. Dynamic

Programming is also able to be solved using a simple computer program,

Microsoft Excel.

In this thesis, it is going to be explained how to solve recursive equations

that are generated from dynamic programming manually and using Microsoft

Excel. In the Microsoft Excel, IF function, MAX function and SOLVER menu are

going to be used to solve recursive equations.

Keyword: Dynamic Programming, recursive equations, Microsoft Excel.


ix

KATA PENGANTAR

Puji dan syukur kepada Allah SWT atas berkat yang selalu menyertai

penulis dalam menyelesaikan tugas akhir ini. Tugas akhir ini dibuat sebagai salah

satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi

Matematika, Universitas Sanata Dharma.

Banyak rintangan dalam proses penulisan tugas akhir ini, namun dengan

rahmat Allah SWT serta dukungan dari berbagai pihak akhirnya tugas akhir ini

dapat diselesaikan. Untuk itu penulis ingin mengucapkan terima kasih kepada:

1. Bapak YG. Hartono, S.Si., M.Sc., Ph.D., selaku dosen pembimbing

sekaligus Ketua Program Studi Matematika yang telah meluangkan

waktu, tenaga dan pikiran serta ilmu yang telah diberikan sehingga

terselesaikannya tugas akhir ini.

2. Bapak Sudi Mungkasi, S.Si., M.Math.Sc., Ph.D. selaku Dekan

Fakultas Sains dan Teknologi.

3. Romo Prof. Dr. Frans Susilo, S.J., selaku Dosen Pembimbing

Akademik.

4. Bapak Ir. Ig. Aris Dwiatmoko, M.Sc., Ibu M.V. Any Herawati, S.Si.,

M.Si., Bapak Dr. rer. nat. Herry P. Suryawan, S.Si., M.Si., selaku

dosen-dosen Program Studi Matematika yang telah memberikan

banyak pengetahuan kepada penulis selama proses perkuliahan.

5. Bapak/Ibu dosen/karyawan Fakultas Sains dan Teknologi yang telah

berdinamika bersama selama penulis berkuliah.

6. Kedua orang tua, Sunarko dan Dwi Ratna Februhartati. Adikku Ivan

Mahendra Septiawan. Om, tante dan adik sepupu Ikhwan yang selalu

memberikan dukungan, doa dan semangat.

7. Sahabat-sahabatku, Karina, Kartika dan Andhika yang selalu

menghibur, memberi semangat serta dukungan dan doa saat penulis

lelah.

8. Teman-teman sosial media, Alvin, Kak Ersa, Eka, Dila, Ais dan semua

yang selalu mendukung dan mendoakan.


9. Teman-teman Matematika 2014: Nando, Edo, Arista" Ek4 Monic,

Dewi, Meme, M.gq Wula.n, Efrem dan teman-teman lainnya yang

telah berdinamika selama perkuliahan.

10. Semua pihak yang tidak dapat dituliskan satu per satu atas dukungan

dan doa yang diberikan selama ini.

Semoga segala doa, perhatian" dukungan dan bantuan yang telah diberikan

mendapatkan balasan dari Allah SWT.

penulis menyadari bahwa masih banyak kekurangan dalam penulisan

tugas akhir ini. Semoga tugas akhir ini dapat b€rmanfaat bagi pembaca dan

menjadi referensi belajar yang baik.

Yogyakarte 19 tvtar et 2019

Destika Amalia

Penulis.


xi

DAFTAR ISI

HALAMAN JUDUL ................................................................................................... i

TITLE PAGE ............................................................................................................... ii

HALAMAN PERSETUJUAN PEMBIMBING .......................................................... iii

HALAMAN PENGESAHAN ..................................................................................... iv

HALAMAN PERSEMBAHAN .................................................................................. v

PERNYATAAN KEASLIAN KARYA ...................................................................... vi

ABSTRAK ................................................................................................................... vii

ABSTRACT ................................................................................................................ viii

KATA PENGANTAR ................................................................................................. ix

DAFTAR ISI ............................................................................................................... xi

DAFTAR TABEL ....................................................................................................... xiii

DAFTAR GAMBAR ................................................................................................... xiv

BAB I PENDAHULUAN ............................................................................................ 1

1.1 Latar Belakang ................................................................................................. 1

1.2 Rumusan Masalah ............................................................................................ 3

1.3 Batasan Masalah .............................................................................................. 3

1.4 Tujuan Penulisan ............................................................................................. 3

1.5 Manfaat Penulisan ........................................................................................... 3

1.6 Metode Penulisan ............................................................................................. 3

1.7 Sistematika Penulisan ...................................................................................... 4

BAB II LANDASAN TEORI ...................................................................................... 5

2.1 Teori Optimalisasi ........................................................................................... 5

2.2 Hukum Probabilitas ......................................................................................... 20

BAB III PEMROGRAMAN DINAMIS ..................................................................... 24

3.1 Pemrograman Dinamis Deterministik ............................................................. 24

3.2 Pemrograman Dinamis Probabilistik ............................................................... 61

BAB IV PEMROGRAMAN DINAMIS DENGAN MICROSOFT EXCEL .............. 77

4.1 Masalah Jarak Terpendek ................................................................................ 77

4.2 Masalah Penggantian Alat ............................................................................... 84


xii

BAB V PENUTUP ...................................................................................................... 88

5.1 Kesimpulan ...................................................................................................... 88

5.2 Saran ................................................................................................................ 88

DAFTAR PUSTAKA .................................................................................................. 89

LAMPIRAN ................................................................................................................ 90


xiii

DAFTAR TABEL

Tabel 3.1.1 ..................................................................................................... 28

Tabel 3.1.2 ..................................................................................................... 29

Tabel 3.1.3 ..................................................................................................... 31

Tabel 3.1.4 ..................................................................................................... 35

Tabel 3.1.5 ..................................................................................................... 37

Tabel 3.1.6 ..................................................................................................... 39

Tabel 3.1.7 ..................................................................................................... 43

Tabel 3.1.8 ..................................................................................................... 44

Tabel 3.1.9 ..................................................................................................... 45

Tabel 3.1.10 ................................................................................................... 45

Tabel 3.1.11 ................................................................................................... 46

Tabel 3.1.12 ................................................................................................... 48

Tabel 3.1.13 ................................................................................................... 50

Tabel 3.1.14 ................................................................................................... 51

Tabel 3.1.15 ................................................................................................... 51

Tabel 3.1.16 ................................................................................................... 52

Tabel 3.1.17 ................................................................................................... 55

Tabel 3.1.18 ................................................................................................... 56

Tabel 3.1.19 ................................................................................................... 58

Tabel 3.1.20 ................................................................................................... 59

Tabel 3.1.21 ................................................................................................... 60

Tabel 3.2.1 ..................................................................................................... 67

Tabel 3.2.2 ..................................................................................................... 68

Tabel 3.2.3 ..................................................................................................... 68

Tabel 3.2.4 ..................................................................................................... 69

Tabel 3.2.5 ..................................................................................................... 70

Tabel 3.2.6 ..................................................................................................... 74

Tabel 3.2.7 ..................................................................................................... 76

Tabel 3.2.8 ..................................................................................................... 76


xiv

DAFTAR GAMBAR

Gambar 2.1.1 ............................................................................................... 9

Gambar 3.1.1 ............................................................................................... 26

Gambar 3.1.2 ............................................................................................... 49

Gambar 4.1.1 ............................................................................................... 78

Gambar 4.1.2 ............................................................................................... 79

Gambar 4.1.3 ............................................................................................... 79

Gambar 4.1.4 ............................................................................................... 80

Gambar 4.1.5 ............................................................................................... 80

Gambar 4.1.6 ............................................................................................... 81

Gambar 4.1.7 ............................................................................................... 81

Gambar 4.1.8 ............................................................................................... 81

Gambar 4.1.9 ............................................................................................... 82

Gambar 4.1.10 ............................................................................................. 82

Gambar 4.1.11 ............................................................................................. 82

Gambar 4.1.12 ............................................................................................. 83

Gambar 4.1.13 ............................................................................................. 83

Gambar 4.2.1 ............................................................................................... 84

Gambar 4.2.2 ............................................................................................... 84

Gambar 4.2.3 ............................................................................................... 85

Gambar 4.2.4 ............................................................................................... 85

Gambar 4.2.5 ............................................................................................... 86

Gambar 4.2.6 ............................................................................................... 86

Gambar 4.2.7 ............................................................................................... 87


1

BAB I

PENDAHULUAN

A. Latar Belakang

Dalam kehidupan sehari-hari seringkali kita memikirkan bagaimana cara

mengoptimalkan pengambilan keputusan dalam suatu masalah. Misalnya akan

dilakukan pengiriman barang ke suatu tempat dengan menggunakan truk,

kemudian masalah yang timbul adalah bagaimana cara mengoptimalkan ruang

dalam truk agar tidak kelebihan muatan. Atau misalkan sebuah pabrik ingin

mengganti peralatan yang sudah tidak layak pakai, masalah yang muncul adalah

bagaimana cara meminimalkan pengeluaran untuk mengganti peralatan-peralatan

tersebut. Contoh lainnya, ketika seorang investor ingin menginvestasikan uangnya

ke sebuah bank, ia akan mempertimbangkan beberapa kemungkinan agar investasi

yang dibuat dapat menghasilkan keuntungan yang maksimal. Masalah-masalah ini

dapat direpresentasikan ke dalam bentuk model matematika dengan menggunakan

pemrograman dinamis.

Pemrograman dinamis merupakan metode pemecahan masalah dengan

menguraikan masalah asli menjadi subproblem yang lebih mudah diselesaikan.

Pada pemrograman dinamis, keputusan optimal dibuat dengan menggunakan

prinsip optimalitas. Jika kita bekerja mulai dari tahap 1 ke tahap , maka

kita dapat menggunakan solusi optimal dari tahap tanpa harus kembali ke tahap

1.

Sebagai contoh kasus, seorang pemburu ikan berencana melakukan

perburuan liar di cagar alam nasional yang terdiri dari danau. Pemburu tersebut

telah melakukan perencanaan yang cermat dengan mengumpulkan data sebagai

berikut:

= jumlah ikan yang ditangkap dalam waktu 1 jam memancing di danau .

= waktu tempuh (dalam jam) dari danau ke danau .

Misalkan waktu perjalanan memenuhi ketaksamaan segitiga .

Pemburu sadar ada beberapa resiko ditangkap oleh pengawas cagar alam. Untuk

meminimalkan resiko ini, ia memutuskan untuk memancing selama 1 jam di


2

setiap danau yang ia kunjungi. Hal ini memberinya perlindungan terhadap

kemungkinan bertemu dengan pengawas cagar alam. Pemburu memberikan

pilihan pada dirinya sendiri untuk kembali ke danau awal setelah memancing di

danau lain, karena ia merasa kemungkinan pengawas telah pergi. Pemburu mulai

memasuki cagar alam 12 jam sebelum jam makan malam. Bagaimanakah ia akan

melanggar masuk dan memaksimalkan tangkapannya sampai sebelum jam makan

malam tiba ?

Solusi:

Sangat jelas bahwa pemburu harus melacak jumlah jam yang tersisa sampai waktu

makan malam dari danau tempat dia berada sekarang. Pemburu tidak perlu

mengecek jumlah ikan yang ditangkap sebelumnya karena tidak akan

mempengaruhi tangkapan selanjutnya. Ada 2 kemungkinan solusi yang optimal

yaitu segera meninggalkan danau 1 atau memancing kurang dari 12 jam.

Akan dipasangkan variabel sebagai keadaan yang menunjukkan situasi saat

meninggalkan danau dengan jam tersisa sebelum makan malam. Didefinisikan

adalah jumlah seluruh ikan yang telah ditangkap selama jam di danau .

Selanjutnya pemburu harus menentukan danau selanjutnya. Jika ia memilih danau

maka estimasi waktunya adalah jam kemudian. Persamaan yang

memungkinkan untuk kasus ini adalah

{

| { ( )}

Jika pemburu menangkap ikan selama 1 jam di danau 1, ia mendapat total

ikan. Jika ia segera meninggalkan danau 1 tanpa memancing di sana, ia

mendapat ikan.

Kesulitan dalam pemrograman dinamis adalah menentukan model yang

tepat untuk mewakili situasi tertentu. Dalam pengembangan model sangat penting

untuk dapat mengelola masalah yang kompleks dan membangun hubungan antara

subproblem yang saling berkaitan dalam suatu tahap. Pemrograman dinamis dapat

diselesaikan menggunakan program komputer sederhana pada Microsoft Excel.

Dalam tugas akhir ini akan dijelaskan bagaimana cara menyelesaikan persamaan


3

rekursif yang dihasilkan dari pemrograman dinamis dengan cara manual dan

Microsoft Excel.

B. Rumusan Masalah

Perumusan masalah yang akan dibahas pada tugas akhir ini adalah:

1. Bagaimana cara menyelesaikan beberapa masalah di kehidupan nyata dengan

pemrograman dinamis ?

2. Bagaimana menyelesaikan pemrograman dinamis menggunakan Microsoft

Excel ?

C. Batasan Masalah

Tugas akhir ini dibatasi oleh beberapa masalah, yaitu:

1. Model yang dibahas adalah model deterministik dan probabilistik.

2. Program yang digunakan untuk menyelesaikan permasalahan hanya Microsoft

Excel.

D. Tujuan Penulisan

Tujuan penulisan tugas akhir ini adalah untuk mengetahui bagaimana

menyelesaikan beberapa masalah pengoptimalan dengan pemrograman dinamis

dan Microsoft Excel.

E. Manfaat Penulisan

Manfaat penulisan tugas akhir ini adalah untuk mengetahui cara penyelesaian

beberapa masalah di kehidupan nyata menggunakan pemrograman dinamis.

F. Metode Penulisan

Metode penulisan yang digunakan dalam tugas akhir ini adalah studi pustaka yaitu

dengan membaca referensi buku mengenai Pemrograman Dinamis yang telah

dicantumkan pada daftar pustaka.


4

G. Sistematika Penulisan

BAB I PENDAHULUAN

1.1 Latar Belakang

1.2 Rumusan Masalah

1.3 Batasan Masalah

1.4 Tujuan Penulisan

1.5 Manfaat Penulisan

1.6 Metode Penulisan

1.7 Sistematika Penulisan

BAB II LANDASAN TEORI

2.1 Teori Optimalisasi

2.2 Hukum Probabilitas

BAB III PEMROGRAMAN DINAMIS

3.1 Pemrograman Dinamis Deterministik

3.2 Pemrograman Dinamis Stokastik

BAB IV PEMROGRAMAN DINAMIS DENGAN MICROSOFT EXCEL

4.1 Masalah Jarak Terpendek

4.2 Masalah Penggantian Alat

BAB V PENUTUP

5.1 Kesimpulan

5.2 Saran

DAFTAR PUSTAKA

LAMPIRAN


5

BAB II

LANDASAN TEORI

2.1 Teori Optimalisasi

Dalam menyelesaikan masalah matematika dibutuhkan keahlian untuk

melakukan pendekatan masalah agar hasil yang diperoleh merupakan hasil yang

optimal. Pendekatan masalah ini biasa disebut dengan optimalisasi. Secara umum,

optimalisasi adalah mendapatkan hasil yang terbaik dari situasi yang diberikan

(Rutherford Aris, 1964). Situasi atau masalah yang ada di dunia nyata dapat

dirumuskan dengan menggunakan model matematika. Dengan model matematika,

latar belakang dari masalah yang diberikan dapat dijelaskan dalam bahasa

matematika. Optimalisasi dapat digunakan untuk menyelesaikan model

matematika dan pemrograman dinamis merupakan salah satu pendekatan khusus

untuk optimalisasi.

Komponen dasar dalam setiap model optimalisasi adalah:

1. Variabel

Variabel adalah faktor yang dapat dimanipulasi untuk mencapai beberapa hasil

atau tujuan. Variabel biasa disimbolkan dengan atau dalam bentuk

vektor variabel .

2. Fungsi objektif

Fungsi objektif adalah ukuran efektivitas atau nilai yang terkait dengan beberapa

kombinasi variabel tertentu.

3. Kendala

Kendala adalah persamaan/ketidaksamaan yang variabelnya harus memberikan

nilai maksimum atau minimum dari fungsi objektif. Biasanya kendala dapat

dirumuskan sebagai


6

Secara umum, masalah optimalisasi adalah untuk memaksimalkan atau

meminimalkan

dengan

{ }

2.1.1 Pengantar Pemrograman Dinamis

Pemrograman dinamis adalah prosedur optimalisasi yang mengubah masalah

dengan berbagai kemungkinan keputusan menjadi subproblem yang diatur secara

bertahap sehingga lebih mudah diselesaikan. Penyelesaian masalah ini biasa

dilakukan dengan menerapkan prinsip optimalitas yaitu, “Kebijakan yang optimal

memiliki properti bahwa apapun keadaan awal dan keputusan awal, keputusan

yang tersisa harus merupakan kebijakan yang optimal berkenaan dengan

keadaan yang dihasilkan dari keputusan awal” (Richard Bellman, 1952).

Pada setiap tahap sistem dapat digambarkan oleh seperangkat parameter yang

relatif kecil yang disebut dengan variabel keadaan. Di setiap tahap dan apapun

sistemnya, satu atau lebih keputusan harus dibuat. Keputusan ini dapat bergantung

pada salah satu tahap atau keadaan atau keduanya.

Keputusan terbaik harus mengoptimalkan fungsi objektif yang

menghubungkan tahap saat ini dengan tahap sebelumnya atau tahap saat ini

dengan tahap selanjutnya. Komponen dasar model pemrograman dinamis

ditunjukkan pada persamaan berikut:

( ∑

)

dengan

∑

dimana dan adalah bilangan real positif. Model ini bertujuan

untuk memaksimalkan total keuntungan.


7

Dalam pemrograman dinamis ada beberapa istilah yang sering digunakan,

yaitu:

1. Tahap

Tahap adalah proses membagi masalah asli menjadi bagian yang berbeda

dengan tahap adalah tahap awal dan tahap 1 adalah tahap terakhir. Tahap dapat

ditulis menjadi tahap dengan . Konsep dari tahapan diperlukan

untuk menetukan keputusan. Misalnya sebuah agen travel membuat rencana

dengan mengelompokkan beberapa tempat wisata yang akan didatangi pada hari

pertama, kedua dan seterusnya. Rencana yang disusun tersebut merupakan sebuah

tahap.

2. Keadaan

Keadaan adalah beberapa kondisi yang mungkin terjadi pada setiap tahap

dari masalah pemrograman dinamis. Setiap tahap mempunyai keadaan yang

bersesuaian. Misalkan sebuah perusahaan pemasok komponen elektronik untuk

industri otomotif memutuskan akan memperluas perusahaannya dengan

membangun 9 fasilitas baru yang lebih dekat dengan lokasi pelanggan dalam 4

tahun ke depan. Biaya konstruksi terdiri dari biaya tetap ditambah biaya per

fasilitas yang dibangun. Apabila tidak ada fasilitas yang dibangun pada tahun

tertentu maka biaya tetap tidak harus dibayarkan. Keadaan pada masalah ini

dapat ditentukan dengan jumlah fasilitas yang telah dibangun.

3. Variabel Keputusan

Variabel keputusan adalah kemungkinan pilihan yang dapat dibuat ketika

masalah berada pada keadaan tertentu. Setiap tahap memiliki satu variabel

keputusan. Misalkan seorang tukang pos sedang berada di kota 2 dan ia harus

membuat keputusan apakah akan pergi ke kota 4, 5 atau 6. Maka dapat ditentukan

variabel keputusan yaitu { } yang merupakan cara

singkat mengatakan bahwa ia dapat memilih rute dari kota 2 ke kota 4, dari kota 2

ke kota 5 atau dari kota 2 ke kota 6.

4. Fungsi Output ( )

Fungsi output adalah nilai keluaran dari variabel keputusan pada tahap .


8

5. Fungsi Nilai Optimal ( )

Fungsi nilai optimal adalah hasil terbaik dari tahap ke tahap dengan adalah

keadaan pada tahap .

6. Kebijakan Optimal

Kebijakan optimal adalah keputusan optimal pada tahap tertentu yang bergantung

pada keadaan. Prosedur dalam pemrograman dinamis didesain untuk menemukan

keputusan optimal pada tiap tahap untuk semua keadaan yang mungkin.

7. Fungsi Transformasi ( )

Fungsi transformasi adalah fungsi yang menunjukkan bagaimana keadaan untuk

tahap selanjutnya berubah sesuai dengan keadaan, tahap dan keputusan yang telah

diketahui pada tahap sebelumnya. Misalkan seorang pengantar paket berada di

kota 3 dan dia akan pindah ke kota lain dengan suatu keadaan yaitu dia tidak akan

pergi ke kota lain yang tidak terhubung dengan kota 3. Rute optimal yang

mungkin adalah pergi ke kota 5. Sehingga dapat ditentukan proses

yang artinya pengantar paket tersebut bergerak dari kota 3 ke kota 5. Fungsi

transformasi juga dapat ditulis sebagai berikut:

8. Hubungan Pengulangan

Hubungan pengulangan adalah fungsi yang menunjukkan kebijakan optimal

(keputusan) pada tahap dengan keputusan pada tahap diketahui. Contoh

fungsinya sebagai berikut

⌊

⁄ ⌋

{ }

9. Kondisi Batas

Kondisi batas adalah kondisi awal pada tahap dan merupakan hasil dari fungsi

nilai optimal. Contohnya

⌊

⁄ ⌋

{ }

10. Hasil

Hasil adalah solusi optimal secara keseluruhan dari masalah pemrograman

dinamis yang ditentukan pada tahap terakhir (tahap 1). Contohnya .


9

Dalam model pemrograman dinamis ini, proses bergerak mundur dimulai

pada tahap dan berakhir pada tahap 1. Proses yang sama juga dapat

dikembangkan dengan urutan terbalik mulai dari tahap 1 ke tahap . Dalam

beberapa penerapan, kedua proses itu setara dan membutuhkan cara perhitungan

yang sama untuk menyelesaikan masalah tertentu. Gambar 2.1.1 menunjukkan

ilustrasi grafis yang setara dengan proses pemrograman dinamis. Setiap kotak

menunjukkan tahap pada proses yang berlangsung. Keadaan pada tahap tertentu

ditentukan oleh keputusan pada tahap sebelumnya.

Model pemrograman dinamis dapat diklasifikasikan menjadi dua yaitu

deterministik dan stokastik. Keduanya bergantung pada jenis data yang tersedia

untuk menyelesaikan masalah. Jika data yang diketahui bersifat konstan, maka

model pemrograman dinamis deterministik akan digunakan untuk menemukan

solusi terbaik dari masalah tersebut. Jika data yang diketahui bersifat

probabilistik, maka model pemrograman dinamis stokastik akan digunakan untuk

mengoptimalkan nilai yang diharapkan. Akan dijelaskan secara umum beberapa

aplikasi pemrograman dinamis sebagai berikut:

Model pemrograman dinamis deterministik

a. Model penggantian alat

Sebuah perusahaan perlu memiliki mesin untuk tahun ke depan. Seiring

dengan bertambahnya usia mesin, biaya operasi tahunan meningkat sehingga

mesin harus diganti dengan yang baru. Harga mesin yang baru di tahun adalah

. Biaya tahunan untuk mengoperasikan mesin tua berumur adalah .

Setiap kali mesin diganti, perusahaan menerima sejumlah kompensasi untuk

mesin yang lama sebagai nilai tukar tambah dan adalah nilai tukar tambah

. . .

Tahap 2 Tahap Tahap

. . .

Tahap 1

Gambar 2.1.1


10

untuk mesin yang memiliki umur . Pada akhir tahun , mesin dapat dijual

seharga dimana adalah usia mesin. Diketahui umur mesin pada awal

tahun pertama adalah , perlu ditentukan kebijakan penggantian alat untuk

mesin yang dapat meminimalkan total biaya untuk tahun berikutnya dengan

mengingat keputusan penggantian hanya dapat dibuat pada awal setiap tahun.

Diasumsikan bahwa biaya operasional tahunan dan nilai tukar tambah hanya

bergantung pada usia mesin. Selanjutnya akan dibentuk model pemrograman

dinamis dan solusinya.

Model pemrograman dinamis untuk masalah ini melibatkan tahap yang

sesuai dengan periode perencanaan (tahun). Pada awal tahap , keadaan

dapat berubah sesuai dengan usia mesin yang telah digunakan pada tahun

sebelumnya. Ada dua keputusan yang mungkin dibuat yaitu menyimpan mesin

saat ini atau mengganti mesin dengan yang baru. Jika perusahaan memutuskan

untuk menyimpan mesin, maka satu-satunya biaya pada tahap ini adalah biaya

operasional mesin. Jika keputusannya adalah untuk mengganti mesin, maka

biaya tahunan akan termasuk harga mesin baru dikurangi dengan nilai tukar

yang diterima untuk mesin saat ini dan ditambah dengan biaya operasional

mesin baru. Biaya pada tahap adalah yang bergantung pada usia mesin

saat ini dan keputusan yang diambil

{

Fungsi nilai optimal ( ) : biaya minimum untuk memiliki mesin dari awal

tahun hingga akhir tahun (atau awal tahun ) dengan keadaan umur

mesin pada awal tahap telah berubah menjadi .

Kebijakan optimal ( ) : “diganti” atau “disimpan”.

Fungsi transformasi ( ) : fungsi ini menunjukkan bagaimana keadaan

untuk tahap berikutnya berubah sesuai dengan keadaan saat ini, tahap dan

keputusan.

{


11

Hubungan pengulangan :

{

Kondisi batas :

Hasil :

b. Model masalah produksi sederhana

Sebuah perusahaan perlu menghasilkan setidaknya unit produk selama

periode berikutnya. Biaya produksi pada periode adalah fungsi kuadratik dari

jumlah yang diproduksi. Jika unit diproduksi pada periode , biaya

produksinya adalah , dimana adalah koefisien positif. Tujuan

dari masalah ini adalah untuk menentukan jumlah produksi optimal yang

meminimalkan total biaya untuk periode. Masalah ini dapat dimodelkan

sebagai persamaan nonlinear dengan fungsi tujuan kuadratik dan kendala linier

sebagai berikut:

( ∑

)

dengan kendala

∑

Model ini menggambarkan situasi dimana variabel keputusannya bersifat

kontinu. Oleh karena itu subproblem tidak dapat diselesaikan dengan memeriksa

semua solusi yang layak karena domain yang layak tidak terbatas. Secara umum,

ketika variabel keputusan kontinu, prosedur optimasi harus digunakan untuk

menemukan solusi optimal. Dalam masalah khusus ini, subproblem variabel

tunggal dapat diselesaikan dengan menetapkan turunan pertama dari fungsi nilai

optimal sama dengan nol dan menyelesaikan hasil persamaan linearnya.


12

Model pemrograman dinamis digunakan berdasarkan pada metode maju yaitu

kondisi batas diberikan untuk tahap 1 dan proses berulang dari setiap tahap ke

tahap . Keadaan dari model pada tahap ditentukan oleh jumlah unit

yang diproduksi pada awal periode . Model dan solusi yang dapat dibuat untuk

masalah ini adalah sebagai berikut:

Fungsi nilai optimal ( ) : biaya produksi minimum untuk awal periode

dengan sebanyak unit diproduksi pada periode ini.

Kebijakan optimal : unit yang diproduksi pada periode .

Fungsi transformasi ( ) : menentukan banyaknya unit yang diproduksi

pada akhir periode dengan diketahui fungsi dari banyaknya unit yang

diproduksi pada awal periode dan banyaknya unit yang telah diproduksi pada

periode .

Hubungan pengulangan :

{ }

Kondisi batas :

Hasil :

Fungsi nilai optimal pada tahap 1 diberikan dalam bentuk tertutup yaitu

. Fungsi ini dapat digunakan sebagai input ke tahap 2 untuk

menentukan fungsi nilai optimal yang sesuai dalam bentuk tertutup:

{ }

{

}

Jelas bahwa fungsi kuadrat variabel tunggal

adalah

fungsi cembung karena turunan keduanya bernilai positif

{

}

{

}


13

Nilai minimum ditentukan dengan menetapkan turunan pertama sama dengan

nol. Jika nilai minimum berada di antara batas maka nilai minimum

tersebut dapat digunakan untuk menyelesaikan subproblem. Jika nilai minimum

tidak berada pada batas maka nilai minimum tersebut akan menjadi salah satu

titik batas.

Karena solusi di atas layak (berada diantara batas), maka solusi tersebut dapat

menyelesaikan subproblem pada tahap 2. Solusi ini dapat disubstitusikan ke

dalam persamaan rekursi pada tahap 2 untuk menghitung nilai optimal dalam

bentuk tertutup sebagai berikut:

Teorema 2.1.1

Secara umum, kebijakan optimal dan fungsi nilai optimal untuk masalah

produksi sederhana diberikan oleh persamaan berikut:

∑

∑

Bukti:

Teorema tersebut dapat dibuktikan dengan induksi matematis.

Karena hasilnya sudah terbukti untuk tahap 1 dan 2, sekarang hanya perlu

menunjukkan jika teorema tersebut benar untuk tahap maka untuk tahap

juga benar. Misalkan pada tahap

{ }

Sekarang, persamaan dapat disubstitusi dengan persamaan

bentuk tertutup yang dianggap benar untuk tahap .


14

{

∑

}

Nilai minimum diperoleh dengan menetapkan turunan pertama sama dengan

nol.

{

∑

}

∑

*( ∑

) +

∑

yang membuktikan solusi bentuk tertutup untuk kebijakan optimal. Nilai ini

adalah nilai minimum unik karena turunan keduanya dapat dibuktikan bernilai

positif. Maka dengan mensubstitusi persamaan tersebut dari menjadi

, solusi bentuk tertutup fungsi nilai optimal dapat diturunkan menjadi:

(

∑

)

(

∑

)

∑

yang dapat disederhanakan menjadi

∑

Model pemrograman dinamis stokastik

Terkadang dalam membuat keputusan terdapat ketidakpastian mengenai

konsekuensi dari keputusan yang diambil. Misalkan produsen dapat memproduksi

barang tanpa mengetahui berapa banyak unit yang akan diminta pelanggan untuk

setiap jenis barang. Contoh lainnya adalah seorang investor dapat memutuskan

untuk membeli sejumlah saham dengan potongan tertentu tanpa mengetahui

apakah sahamnya akan naik atau turun pada tahun berikutnya. Meskipun tidak


15

pasti, secara umum masalah ini masih dapat diperkirakan kemungkinan hasil yang

berkaitan dengan keputusan yang diambil.

Beberapa model pemrograman dinamis yang dibahas pada subbab

sebelumnya telah mempertimbangkan situasi dimana konsekuensi dari semua

keputusan yang mungkin telah ditentukan sebelumnya. Perbedaan mendasar

antara model stokastik dengan model deterministik adalah bahwa keadaan yang

dihasilkan dari suatu keputusan tidak ditentukan sebelumnya, tetapi dapat

dijelaskan oleh fungsi distribusi probabilitas yang diketahui dan bergantung pada

keadaan awal serta keputusan yang diambil.

Pada model pemrograman dinamis stokastik, dimisalkan adalah

keadaan dari tahap dan adalah himpunan semua keputusan yang

berkaitan dengan . Jika proses yang sedang berlangsung berada pada

maka beberapa keputusan pada harus dipilih. Dengan asumsi bahwa

tahap bukan tahap terakhir (tahap ) dan misalkan maka keputusan akan

mengakibatkan transisi ke beberapa keadaan pada tahap . Keadaan

khusus dapat ditunjukkan dengan probabilitas transisi sebagai berikut:

probabilitas bahwa keadaan yang diamati pada tahap akan

menjadi mengingat keadaan saat ini pada tahap adalah dan keputusan telah

dibuat

Perhatikan bahwa untuk pasangan tertentu dan keputusan khusus

, nilai ∑ dan

untuk setiap keadaan . Dalam

pemrograman dinamis stokastik, serangkaian keadaan yang berbeda dapat terjadi

untuk hasil yang berbeda dari masalah yang sama meskipun kebijakan yang sama

diterapkan.

a. Model stokastik masalah penggantian alat

Model ini merupakan pengembangan dari masalah yang telah dibahas

pada subbab sebelumnya. Diasumsikan bahwa biaya operasi tahunan mesin

berusia adalah variabel acak dengan distribusi probabilitas yang diketahui.

Kemudian diasumsikan juga bahwa mesin dapat mengalami kerusakan pada akhir

tahun dan harus diganti. Probabilitas kerusakan yang terjadi bergantung pada usia


16

mesin di awal tahun. Sehingga pada awal tahun ditambahkan opsi untuk menjual

mesin yang saat ini dimiliki dan menyewa mesin baru selama setahun. Jika

perusahaan telah menyewa mesin pada tahun sebelumnya, ia dapat menyewa

mesin lain atau membeli yang baru pada awal tahun. Dengan asumsi bahwa

perusahaan memiliki mesin dengan usia pada awal tahun pertama, perlu

ditentukan kebijakan penggantian atau sewa yang optimal. Didefinisikan:

= jumlah tahun yang harus dipertimbangkan

= umur mesin pada awal tahun 1

= harga beli mesin baru di awal tahun

= biaya operasional tahunan yang diharapkan untuk mesin usia pada

awal tahun

= nilai tukar tambah untuk mesin usia yang berada dalam kondisi kerja

= nilai jual untuk mesin usia yang berada dalam kondisi kerja

= nilai tukar tambah untuk mesin usia yang rusak

= nilai jual untuk mesin usia yang rusak

= probabilitas bahwa mesin usia dalam kondisi kerja pada awal tahun

rusak pada akhir tahun

= biaya tahunan untuk menyewa mesin

Dalam masalah ini, diasumsikan bahwa perusahaan tidak perlu membayar

apa pun jika mesin yang disewa rusak pada akhir tahun karena biaya sewa

termasuk asuransi untuk mesin tersebut. Model pemrograman dinamis berikut

menggunakan dua fungsi nilai optimal. Fungsi pertama yaitu memberikan nilai

optimal untuk tahun ke karena perusahaan memiliki mesin pada awal tahun.

Fungsi kedua yaitu memberikan nilai optimal jika perusahaan menyewa mesin

pada tahun sebelumnya. Dalam fungsi pertama, sejumlah keadaan perlu

dipertimbangkan bergantung pada usia mesin yang dimiliki pada awal tahun .

Jika menyewa mesin hanya ada satu keadaan karena perusahaan saat ini tidak

memiliki mesin. Beberapa keadaan membutuhkan dua keputusan yaitu keputusan

pertama diterapkan pada awal tahun dan keputusan kedua diambil hanya jika

perusahaan memutuskan untuk memiliki mesin selama satu tahun kedepan dan


17

mesin mengalami kerusakan pada akhir tahun. Jika keputusan yang diambil pada

awal tahun adalah untuk menyewa mesin, maka keputusan kedua tidak perlu

diambil. Proses pengambilan keputusan dapat ditunjukkan dengan notasi sebagai

berikut:

B : “mengganti mesin”

K : “menyimpan mesin saat ini”

L : “menyewa mesin baru selama satu tahun”

Model untuk masalah ini dapat dibentuk dengan menentukan

Tahap : tahun dengan

Keadaan: jika perusahaan memiliki mesin pada tahun , maka keadaan pada

awal tahun adalah sebagai usia mesin; jika sebuah mesin disewa pada tahun

, satu-satunya keadaan adalah perusahaan tidak memiliki mesin pada awal

tahun .

Variabel keputusan ( ) : dua keputusan mungkin harus diambil pada

setiap keadaan. Keputusan pertama pada awal tahun adalah

{ }, jelas bahwa opsi “simpan” hanya tersedia jika

perusahaan memiliki mesin. Keputusan kedua mungkin diperlukan pada akhir

tahap , jika mesin yang dimiliki rusak pada akhir tahun maka keputusan kedua

adalah { }.

Fungsi nilai optimal : ada dua fungsi yang perlu dievaluasi dalam setiap tahap

yaitu

= biaya minimum yang diharapkan dari awal tahun hingga awal tahun

dengan keadaan bahwa perusahaan memiliki mesin yang

bekerja pada usia pada awal tahun .

= biaya minimum yang diharapkan dari awal tahun hingga awal tahun

dengan keadaan bahwa perusahaan tidak memiliki mesin

pada awal tahun saat mesin disewa pada tahun sebelumnya.

Kebijakan optimal : rencana optimal untuk mengganti

mesin atau menyewa mesin pada tahun .


18

Hubungan pengulangan: untuk (

)

{

( )

{

( )

{

Untuk ,

{

Untuk

{

( )

{

Kondisi batas: untuk ( )

,

{

(kasus ini dapat digunakan dalam perhitungan dan )

Hasil :

b. Model perencanaan investasi

Misalkan seorang investor memiliki $10,000 untuk diinvestasikan selama

3 tahun ke depan. Investasi hanya dapat dilakukan selama 1 tahun pada awal

setiap tahun dalam kelipatan $10,000. Ada dua jenis peluang investasi yaitu A dan

B. Investasi B lebih konservatif daripada investasi A. Jika investor akan

berinvestasi pada A di tahun tertentu, maka pada akhir tahun uang akan hilang


19

dengan probabilitas 0.3 atau akan digandakan dengan probabilitas 0.7. Jika

investasi dilakukan pada B, di akhir tahun uang akan dikembalikan dengan

probabilitas 0.9 atau akan digandakan dengan probabilitas 0.1. Tujuan dari

masalah ini adalah untuk menghasilkan kebijakan investasi yang memaksimalkan

total pengembalian yang diharapkan pada akhir tahun ketiga. Untuk

menyederhanakan prosedur solusi, diasumsikan bahwa hanya ada satu jenis

investasi yang dapat dipilih pada tahun tertentu.

Dalam model berikut, himpunan keputusan yang mungkin begantung pada

jumlah uang yang tersedia pada awal tahun. Jika investor memiliki uang kurang

dari $10,000 maka satu-satunya kemungkinan adalah menyimpan uang tersebut.

tetapi jika uang yang tersedia untuk diinvestasikan adalah $10,000 atau lebih,

kelipatan $10,000 dari total uang yang tersedia dapat diinvestasikan pada A atau

B.

Tahap : tahun dengan

Keadaan : jumlah uang yang ada pada awal tahun . Pada tahun 1,

$10,000

Variabel keputusan : keputusan pada tahap terdiri dari jumlah

uang yang tersedia untuk diinvestasikan dalam kelipatan $10,000 ( dan jenis

investasi yang akan dibuat { } dimana 0 berarti tidak ada investasi

yang dilakukan.

Fungsi nilai optimal : jumlah maksimum yang diharapkan dari uang pada

awal tahun hingga akhir tahun 3 dengan keadaan bahwa uang yang tersedia pada

awal tahun adalah .

Kebijakan optimal : rencana optimal untuk investasi pada tahun

dengan keadaan uang yang tersedia adalah .

Hubungan pengulangan : untuk

Untuk

{

{ }

{ }


20

dimana { } adalah himpunan jumlah investasi yang

mungkin (dalam ribuan dolar).

Kondisi batas : untuk

Untuk ,

{

{ }

{ }

dimana { }.

Hasil :

2.2 Hukum Probabilitas

Dalam kehidupan sehari-hari, istilah probabilitas dapat diartikan sebagai

ukuran keyakinan dari sebuah peristiwa yang akan terjadi di masa depan. Konsep

probabilitas diperlukan dalam bekerja dengan mekanisme fisik, biologis atau

sosial yang menghasilkan pengamatan yang tidak dapat diprediksi dengan pasti.

Misalkan tekanan darah seseorang pada kondisi tertentu atau berapa lama kita

harus menunggu antrian saat berada di loket. Peristiwa acak seperti itu tidak dapat

diprediksi dengan pasti, namun frekuensi relatif yang terjadi dalam serangkaian

uji coba yang dilakukan setara.

2.2.1 Hukum Probabilitas Bersyarat

Probabilitas suatu kejadian terkadang akan bergantung pada peristiwa lain

yang telah terjadi. Misalkan akan diprediksi apakah besok akan turun hujan

dengan mengabaikan kondisi atmosfer atau kejadian lainnya. Hal ini merupakan

probabilitas tanpa syarat dari peristiwa “besok akan turun hujan”. Jika ditambah

informasi bahwa hujan turun selama dua hari berturut-turut, maka diperoleh

informasi tambahan yang berkaitan dengan apakah besok akan turun hujan.

Dengan tambahan informasi tersebut, probabilitas hujan bersyarat (diketahui

bahwa hujan turun selama dua hari berturut-turut) jauh lebih besar daripada

probabilitas hujan tanpa syarat (dengan mengabaikan kejadian lain).


21

Probabilitas bersyarat dari suatu peristiwa A, mengingat bahwa suatu

peristiwa B telah terjadi adalah

|

dengan . Simbol | dibaca probabilitas dari A dengan diberikan B

(Dennis D. Wackerly, 2008).

Misalkan kemungkinan terjadinya peristiwa A tidak terpengaruh oleh

peristiwa B hal ini menandakan bahwa peristiwa A dan peristiwa B bersifat

independen (saling bebas). Dua peristiwa A dan B dikatakan independen jika

memenuhi salah satu dari sifat berikut

1. |

2. |

3.

Jika tidak memenuhi salah satunya, maka kedua peristiwa itu saling bergantung.

Maksud dari independen dalam konsep probabilistik sesuai dengan

penggunaan kata sehari-hari dengan mempertimbangkan suatu peristiwa yang

dimaksud. Misalkan sebagian besar orang akan setuju bahwa “merokok” dan

“terjangkit kanker paru-paru” adalah peristiwa yang saling bergantung karena

probabilitas seseorang terjangkit kanker paru-paru jika ia merokok lebih besar

daripada probabilitas jika ia tidak merokok. Sebaliknya, peristiwa “hari ini hujan”

dan “hujan sebulan dari hari ini” saling bebas dan tidak terkait.

2.2.2 Hukum Probabilitas Total

Pendekatan beberapa peristiwa untuk memecahkan masalah probabilitas

dilakukan dengan melihat ruang sampel , sebagai gabungan dari himpunan

bagian yang saling terpisah. Untuk beberapa bilangan bulat positif , diberikan

himpunan sehingga

1.

2.

Himpunan { } dikatakan sebagai partisi dari . Jika adalah setiap

bagian dari , maka dapat ditulis sebagai berikut:


22

Teorema 2.2.1

Asumsikan bahwa { } adalah sebuah partisi dari dengan ,

untuk . Maka untuk sebarang peristiwa berlaku

∑ |

Bukti:

Setiap subset A dari dapat ditulis sebagai berikut

Karena { } adalah partisi dari , jika maka

( ) ( )

diperoleh dan adalah kasus yang berlainan. Maka

| | |

∑ |

Dalam beberapa contoh terkadang lebih mudah untuk menghitung probabilitas

bersyarat | untuk nilai yang sesuai daripada menghitung secara

langsung.


23

BAB III

PEMROGRAMAN DINAMIS (DYNAMIC PROGRAMMING)

Pemrograman dinamis (DP) adalah metode pemecahan masalah dengan

cara menguraikan masalah menjadi subproblem yang lebih mudah ditangani.

Perhitungannya dilakukan secara rekursif dan solusi optimal dari satu subproblem

digunakan sebagai input untuk subproblem berikutnya. Solusi optimal untuk

seluruh masalah kita dapatkan ketika subproblem terakhir diselesaikan. Cara

perhitungan dilakukan tergantung pada bagaimana masalah asli diuraikan. Secara

khusus, subproblem biasanya dihubungkan oleh kendala umum dan kelayakan

kendala umum ini dipertahankan pada semua iterasi.

3.1 Pemrograman Dinamis Deterministik

Pada pemrograman dinamis, rangkaian keputusan yang optimal dibuat dengan

menggunakan prinsip optimalisasi, yaitu jika solusi memiliki kebijakan yang

optimal apapun keadaan awal dan keputusan awalnya, maka keputusan yang

tersisa harus merupakan kebijakan optimal yang sesuai dengan keadaan yang

dihasilkan dari keputusan awal. Jika kita bekerja dari tahap 1 ke tahap ,

kita dapat menggunakan solusi optimal dari tahap tanpa harus kembali ke tahap

1. Misalkan jika kita ingin mencari jarak pada tahap ke- maka kita bisa

dapatkan dari menjumlahkan jarak yang dihasilkan pada tahap ke- dengan jarak

dari tahap ke tahap .

Rekursi adalah proses pengulangan fungsi yang dalam prosedur

penggunaannya memanggil fungsi itu sendiri satu atau beberapa kali hingga

kondisi yang ditentukan terpenuhi. Ada dua pendekatan yang dapat dilakukan

dalam mencari solusi optimal pemrograman dinamis, yaitu rekursi maju (Forward

Recursion) dan rekursi mundur (Backward Recursion). Dalam metode maju,

perhitungannya dilakukan dari tahap awal atau tahap 1 ke tahap selanjutnya

sampai ke tahap terakhir. Sedangkan metode mundur perhitungannya dilakukan

dari tahap terakhir ke tahap paling awal. Kedua metode ini mendapatkan hasil


24

optimal yang sama. Meski metode maju lebih logis tetapi dalam pemrograman

dinamis metode mundur lebih sering digunakan.

Misalkan kita akan pergi dari kota A menuju ke kota H melewati beberapa

kota dengan jarak yang berbeda-beda. Kita menginginkan rute tercepat untuk

sampai ke kota H. Pada pengaplikasian pemrograman dinamis kita misalkan kota

A adalah simpul 1 dan kota H adalah simpul terakhir.

Untuk metode maju, perhitungan dimulai dari kota awal yaitu kota A sebagai

simpul 1. Sehingga nilai dan persamaan rekursifnya adalah

dengan

= jarak terpendek ke simpul pada tahap ke-

= jarak dari ke

Nilai karena belum ada jarak pada tahap awal. Kemudian untuk jarak

pada tahap selanjutnya dapat diperoleh dengan mencari nilai dengan

.

Untuk metode mundur, perhitungan dimulai dari kota tujuan yaitu kota H

sebagai simpul terakhir dengan persamaan rekursifnya adalah

dengan

= jarak terpendek ke simpul pada tahap ke-(

= jarak dari ke

dengan adalah simpul teakhir bernilai 0 karena belum ada jarak pada

tahap awal. Untuk jarak pada tahap selanjutnya dapat diketahui dengan mencari

nilai dengan .

Dalam pemrograman dinamis terminologi, dirujuk pada keadaan (state)

tahap ke- . Keadaan (state) adalah kendala pada suatu tahapan ke- yang


25

menghubungkan tahapan-tahapan yang berurutan secara independen dari solusi

yang telah dibuat pada semua tahapan sebelumnya.

Contoh 3.1.1

Di sebuah daerah terdapat 7 kota dengan jarak yang terlihat seperti pada gambar

3.1.1. Seorang kurir ingin mengantarkan barang dari kota 1 ke kota 7. Kurir

tersebut menginginkan rute terpendek yang dapat ia lewati. Tentukanlah rute

terpendek tersebut !

Jawab:

a. Dengan menggunakan metode maju

Tahap 1

Dari Gambar 3.1.1 kita dapatkan:

Jarak dari simpul 1 ke simpul 2 = 5



Tahap 2

Pada tahap 2, kita mempunyai 2 ujung simpul yang berbeda yaitu simpul 5 dan

simpul 6. Pada Gambar 3.1.1 kita dapat melihat bahwa simpul 5 dapat dicapai

melalui simpul 2, 3, dan 4. Kita dapat mencari jarak terpendek dengan

menjumlahkan jarak antar simpul ke simpul 5 dengan solusi optimal pada tahap 1

(

*

{(

* (

*}

Gambar 3.1 .1

9

8

9 9

10

4

17 10

8

9 5

1

6

5

4

3

2

7


26

Pada Gambar 3.1.1, simpul 6 dapat dicapai melalui simpul 2, 3, dan 4. Dengan

cara yang sama, kita dapatkan solusi optimal untuk simpul 6

Jarak terpendek dari simpul 1 ke simpul 5 = 13 (dari simpul 3)


Tahap 3

Pada tahap 3 ini merupakan langkah terakhir perhitungan. Menurut Gambar 3.1.1,

simpul terakhir atau simpul 7 dapat dicapai melalui simpul 5 dan 6. Dengan cara

yang sama pada tahap 2 kita peroleh


Dari ketiga tahapan di atas dapat disimpulkan bahwa rute terpendek yang dapat

ditempuh dari simpul 1 ke simpul 7 adalah .

b. Dengan menggunakan metode mundur

Pada metode mundur, perhitungan dimulai dari tahap 3 menuju tahap 1. Jika

adalah keadaan pada tahap ke- yang menghubungakan tahapan-tahapan yang

{

}

(

*

{(

* (

*}

{

}

(

*

{(

* (

*}

{

}


27

berurutan, maka kita dapat menentukan pada setiap tahap dengan

memperhatikan Gambar 3.1.1. Kita misalkan adalah rute kota yang akan dituju

pada setiap tahap. Semua jarak diukur dari 0 dengan menetapkan

Tahap 3

Kita misalkan sehingga kita bisa menetapkan nilai

Pada Gambar 3.1.1 simpul 7 dapat dicapai melalui simpul 5 dan 6, dimana

masing-masing rute hanya memilili 1 rute yang saling menghubungkan. Keadaan

pada tahap 3 adalah hubungan antara simpul 5 ke simpul 7 dan simpul 6 ke simpul

7. Maka dapat ditentukan nilai pada tahap 3 adalah 5 dan 6.

Persamaan rekursif pada tahap 3 didefinisikan

Karena nilai maka persamaan rekursifnya dapat ditulis

dengan

= jarak terpendek ke simpul pada tahap 3

= jarak dari simpul ke simpul

Tabel 3.1.1

Pada Tabel 3.1.1 kolom pertama menunjukkan nilai yang telah ditentukan

dan kolom kedua menunjukkan jarak antara ke yang dapat diperoleh dari

Gambar 3.1.1.

Solusi Optimal

5 8 8 7

6 9 9 7


28

Entri pada kolom diperoleh dengan mencari nilai minimal yang

terdapat pada kolom kedua, karena kolom kedua hanya memiliki satu nilai maka

entri pada kolom kedua dan ketiga sama sehingga jarak terpendek antara simpul 5

ke simpul 7 dan simpul 6 ke simpul 7 adalah 8 dan 9. Simpul 5 dan 6 sama-sama

memiliki jarak terpendek menuju simpul 7, maka dapat diperoleh nilai adalah

7.

Tahap 2

Pada tahap 3 kita mempunyai nilai dan . Dari Gambar 3.1.1 dapat

dilihat bahwa simpul 5 dan simpul 6 dapat dicapai melalui simpul 2, 3, dan 4

dimana masing-masing rute mempunyai satu rute dengan jarak yang berbeda yang

saling menghubungkan. Keadaaan pada tahap 2 adalah hubungan antara simpul 5

ke simpul 2, 3 dan 4 serta simpul 6 ke simpul 2, 3, dan 4. Sehingga dapat

ditentukan nilai adalah 2, 3, dan 4.


dengan



Tabel 3.1.2

Pada Tabel 3.1.2 kolom pertama menunjukkan nilai yang telah ditentukan.

Kolom kedua menunjukkan jarak dari ke . Untuk menentukan jaraknya dapat

dicari dengan rumus

Solusi Optimal

2 10+8=18 17+9=26 18 5

3 4+8=12 10+9=19 12 5

4 9+8=17 9+9=18 17 5


29

nilai diperoleh dari Tabel 3.1.1. Karena nilai ada dua, maka harus

dihitung satu persatu

Untuk

a. Jarak dari ke

Pada Gambar 3.1.1 diketahui jarak dari simpul 2 ke simpul 5 adalah 10

sehingga

b. Jarak dari ke


sehingga

c. Jarak dari ke


sehingga

Untuk

a. Jarak dari ke


sehingga

b. Jarak dari ke


sehingga

c. Jarak dari ke


sehingga


30

Untuk entri pada kolom kita mencari nilai minimum dari kolom kedua dan

diperoleh nilai seperti pada Tabel 3.1.2. Dari kolom ketiga dan kedua dapat dilihat

bahwa simpul 5 memiliki jarak terpendek ke simpul 2, 3 dan 4, sehingga dapat

diperoleh nilai adalah 5.

Tahap 1

Pada tahap 2 kita mempunyai nilai , dan . Dari Gambar 3.1.1

dapat dilihat bahwa simpul 2, 3 dan 4 dapat dicapai melalui simpul 1 dimana

masing-masing rute mempunyai satu rute dengan jarak yang berbeda yang saling

menghubungkan. Keadaaan pada tahap 1 adalah hubungan antara simpul 2, 3 dan

4 ke simpul 1. Sehingga dapat ditentukan nilai adalah 1.


dengan



Tabel 3.1.3

Pada Tabel 3.1.3 kolom pertama menunjukkan nilai yang telah ditentukan.

Kolom kedua menunjukkan jarak dari ke . Untuk menentukan jaraknya dapat

dicari dengan rumus

nilai diperoleh dari Tabel 3.1.2. Karena nilai ada tiga, maka harus

dihitung satu persatu

Untuk

Jarak dari ke

Solusi Optimal

1 5+18=23 9+12=21 8+17=25 21 3


31

Pada Gambar 3.1.1 diketahui jarak dari simpul 1 ke simpul 2 adalah 5 sehingga

Untuk

Jarak dari ke


Untuk

Jarak dari ke


Untuk entri pada kolom kita mencari nilai minimum dari kolom kedua dan

diperoleh nilai seperti pada Tabel 3.1.3. Dari kolom ketiga dan kedua dapat dilihat

bahwa simpul 3 memiliki jarak terpendek ke simpul 1, sehingga dapat diperoleh

nilai adalah 1.

Kita dapat menentukan rute terpendek dengan melihat nilai pada setiap tahap.

Pada tahap 1 kita memiliki yang terhubung ke . Sehingga rute

pertama yang harus dilalui adalah dari simpul 1 ke simpul 3. Karena tujuan

terakhir berada di simpul 3 maka dapat ditentukan nilai untuk tahap 2 adalah 3.

Pada tahap 2, terhubung ke . Sehingga rute selanjutnya yang harus

dilalui adalah dari simpul 3 ke simpul 5. Simpul 5 menjadi tujuan terakhir pada

tahap 2 sehingga dapat ditentukan nilai untuk tahap 3 adalah 5. Pada tahap 3,

terhubung ke . Sehingga rute terakhir yang harus ditempuh adalah

dari simpul 5 ke simpul 7. Jadi dapat disimpulkan rute terpendek yang harus

dilalui kurir tersebut adalah dari .


32

Dari kesimpulan di atas, dua metode pendekatan tersebut mempunyai hasil

optimal yang sama.

Ada 4 jenis pengaplikasian pemrograman dinamis yang akan dibahas, yaitu:

3.1.1 Model Pengepakan

Model pengepakan adalah model yang biasa digunakan dalam masalah

pengepakan barang. Model ini digunakan untuk mengalokasi sumber daya umum

dimana sumber daya yang terbatas digunakan untuk kegiatan ekonomi. Tujuan

dari model ini adalah untuk memaksimalkan total keuntungan yang dapat diambil.

Model ini menggunakan persamaan rekursif mundur yang dikembangkan

untuk masalah umum pengalokasian item ke dalam pengepakan dengan

kapasitas berat . Didefinisikan adalah jumlah unit item dalam pengepakan,

adalah unit pendapatan dan adalah berat barang .

Masalah umumnya didefinisikan sebagai berikut:

dengan

Tiga elemen dari model adalah

1. Tahap ke- didefinisikan oleh item ke- dengan

2. Definisi alternatif pada tahap ke- adalah jumlah unit item ke- dengan

[

], dimana [

]

dan [

] adalah bilangan bulat terbesar. Definisi ini

memungkinkan solusi untuk mengalokasikan jumlah sumber daya ke salah satu

item dengan keuntungan untuk adalah .

3. Definisi keadaan pada tahap ke- ditunjukkan oleh , dimana adalah total berat

yang ditetapkan untuk tahap atau item . Definisi ini menyatakan batas

berat adalah satu-satunya kendala yang mengikat semua tahap. Definisi keadaan

bersifat multidimensi dimana keadaan ini dapat menimbulkan perhitungan


33

tahapan yang lebih kompleks. Misalkan keadaaan volume dari ransel dapat

menimbulkan batasan lain.

Didefinisikan adalah keuntungan maksimum jika diberikan pada tahap

ke- , ) dan . Ada dua langkah yang paling mudah untuk menghitung

model.

Langkah 1

Nyatakan sebagai fungsi dari dengan

[

]

Langkah 2

Nyatakan sebagai fungsi dari untuk memastikan konsistensi dengan sisi

kiri persamaan rekursif. Menurut definisi menunjukkan berat

yang digunakan pada tahap ke- . Sehingga dan persamaan

rekursifnya didefinisikan sebagai berikut

[

]

Contoh 3.1.2

Sebuah bejana dengan berat 4 ton dapat memuat satu atau lebih 3 item

barang. Diberikan tabel berat dalam ton dan unit pendapatan dalam

ribuan dollar.

Item ke-

1 1 30

2 2 60

3 3 80


34

Carilah banyaknya unit dari item yang dapat memaksimalkan keuntungan !

Jawab:

Karena unit berat dan berat maksimal adalah bilangan bulat, maka

keadaan diasumsikan hanya bilangan bulat. Diketahui total berat bejana adalah

4 ton dan karena berat bejana adalah satu-satunya kendala yang mengikat semua

tahap, maka keadaan pada tiap tahap dalam masalah ini sama yaitu

untuk . Misalkan adalah banyaknya item ke- yang dapat

dialokasikan pada bejana di tahap ke- . Nilai dari hanya dapat ditentukan jika

dan semua nilai yang tidak layak dapat diabaikan.

Tahap 3

Berat yang akan dialokasikan pada tahap 3 tidak diketahui sebelumnya, namun

dapat diasumsikan dari nilai [

] sehingga didapatkan nilai adalah

[

] [

]

Karena nilai maksimal adalah1 maka dapat ditentukan .

Persamaan rekursif untuk tahap 3 adalah

dengan

= keuntungan maksimal pada tahap 3

= pendapatan untuk item ke-3

Solusi Optimal

0 0 0 0

1 0 0 0

2 0 0 0

3 0 80 80 1

4 0 80 80 1

Tabel 3.1.4


35

Pada kolom pertama menunjukkan nilai yang telah ditentukan. Karena

mempunyai dua nilai maka kolom kedua dibagi menjadi dua kolom untuk masing-

masing nilai .

Untuk

Diketahui nilai maka

Dapat dilihat bahwa sehingga tidak ada nilai yang diabaikan maka

diperoleh

untuk setiap .

Untuk


Dapat dilihat bahwa untuk nilai sehingga nilainya

dianggap tidak layak dan dapat diabaikan.

Sedangkan untuk nilai sehingga dapat diperoleh

untuk .

Entri pada kolom ketiga diperoleh dengan mencari nilai maksimum pada kolom

kedua dan nilai diperoleh dari nilai yang memuat nilai maksimum pada

kolom ketiga.

Tahap 2

Sama seperti pada tahap 3 nilai diperoleh dari

[

] [

]

Karena nilai maksimum adalah 2 maka dapat ditentukan .


dengan

= keuntungan maksimal pada tahap 2



36

Solusi Optimal

0 0+0=0 0 0

1 0+0=0 0 0

2 0+0=0 60+0=60 60 1

3 0+80=80 60+0=60 80 0

4 0+80=80 60+0=60 120+0=120 120 2

Tabel 3.1.5

Pada kolom pertama Tabel 3.1.5 menunjukkan nilai yang telah ditentukan.

Karena mempunyai tiga nilai maka kolom kedua dibagi lagi menjadi tiga

kolom untuk masing-masing nilai .

Untuk



diperoleh

Untuk nilai lihat entri pada Tabel 3.1.4 kolom dengan

memasukkan nilai sehingga diperoleh entri untuk kolom

seperti pada Tabel 3.1.5.

Untuk


Dapat dilihat bahwa untuk nilai sehingga nilainya dianggap

tidak layak dan dapat diabaikan.



37




Untuk










kolom ketiga.

Tahap 1

Sama seperti dua tahap sebelumnya nilai diperoleh dari

[

] [

]

Karena nilai maksimum adalah 4 maka dapat ditentukan .


dengan

= keuntungan maksimum pada tahap 1



38

Solusi Optimal

4

0 0+0=0 0 0

1 0+0=0 30+0

=30 30 1

2 0+60

=60

30+0

=30

60+0

=60 60 0,2

3 0+80

=80

30+60

=90

60+0

=60

90+0

=90 90 1,3

4 0+120

=120

30+80

=110

60+60

=120

90+0

=90

120+0

=120 120 0,2,4

Tabel 3.1.6


Karena mempunyai empat nilai maka kolom kedua dibagi lagi menjadi empat

kolom untuk masing-masing nilai .

Untuk



diperoleh




Untuk






39




Untuk








Untuk








Untuk






40






kolom ketiga.

Dari tahap 1 diperoleh = 4 yang memberikan alternatif optimal = 0, = 2

dan = 4 diketahui bahwa

Untuk = 0,

Untuk = 2,

Untuk = 4,

Karena nilai dan tidak ada, maka dari tahap 1 diperoleh nilai

Dari tahap 2, nilai memberikan alternatif optimal sehingga

Dari tahap 3, nilai memberikan alternatif optimal

Sehingga diperoleh solusi optimalnya adalah

Maka keuntungan maksimal yang diperoleh adalah

3.1.2 Model Ukuran Tenaga Kerja

Dalam sebuah proyek konstruksi, kebutuhan tenaga kerja dapat dipenuhi

melalui perekrutan dan memberhentikan pekerja. Sebuah perusahaan memerlukan

biaya untuk merekrut dan memberhentikan pekerjanya. Tujuan dari model ukuran

tenaga kerja adalah untuk meminimalkan total biaya tenaga kerja yang diperlukan

untuk proyek tersebut.

Diasumsikan bahwa durasi proyek adalah minggu dan minimal tenaga

kerja yang diperlukan dalam minggu ke- adalah pekerja. Model ini

mengasumsikan bahwa biaya tambahan ditanggung jika tenaga kerja mingguan


41

melebihi persyaratan minimum atau jika perekrutan tambahan dilakukan dalam

seminggu. Dengan kata lain, tidak ada biaya yang terjadi ketika pekerja direkrut.

Biaya mempertahankan tenaga kerja lebih besar dari minimal pada

minggu ke- dan menimbulkan kelebihan biaya . Jika ,

perekrutan pekerja terjadi dengan biaya tambahan sebesar

Elemen dari model pemrograman dinamis didefinisikan sebagai berikut:

1. Tahap menunjukkan minggu ke- , .

2. Alternatif pada tahap ke- adalah yang menunjukkan jumlah buruh dalam

minggu ke- .

3. Keadaan pada tahap ke- adalah yang menunjukkan jumlah buruh yang

tersedia di minggu ke .

Persamaan rekursif Program Dinamis diberikan

Perhitungan dimulai dari tahap ke- dan berakhir di tahap 1.

Contoh 3.1.3

Seorang kontraktor memperkirakan bahwa banyaknya tenaga kerja yang

dibutuhkan selama 5 minggu masing-masing adalah 5, 7, 8, 4 dan 6 pekerja.

Kelebihan tenaga kerja dari jumlah yang dibutuhkan akan dikenai biaya $300 per

pekerja per minggu, dan perekrutan pekerja baru dalam setiap minggu akan

dikenai biaya tetap sebesar $400 ditambah biaya tambahan sebeasar $200 per

pekerja per minggu. Tentukan total minimal biaya tenaga kerja yang dibutuhkan !

Jawab:

Diketahui


42

Fungsi biaya dan dalam ribuan dollar. Misalkan adalah banyaknya

tenaga kerja yang direkrut pada tahap ke- .

Tahap 5

Pada minggu ke-5 dibutuhkan minimal 6 pekerja, sedangkan pada minggu ke-4

membutuhkan minimal 4 pekerja. Sehingga diperoleh nilai dan

. Diketahui dan misalkan nilai .


dengan

= biaya minimum yang dibutuhkan pada tahap 5

= fungsi biaya untuk tahap 5

Solusi Optimal

4 3(0)+4+2(2)=8 8 6

5 3(0)+4+2(1)=6 6 6

6 3(0)+0=0 0 6

Tabel 3.1.7

Pada kolom pertama Tabel 3.1.7 menunjukkan nilai yang telah ditentukan dan

kolom kedua menunjukkan fungsi biaya pada tahap 5 dengan nilai

sehingga diperoleh entri seperti pada Tabel 3.1.7. Entri pada kolom

diperoleh dengan mencari nilai minimum pada kolom kedua dan nilai

diperoleh dari nilai yang memuat nilai minimum pada kolom ketiga.

Tahap 4


membutuhkan minimal 8 pekerja. Sehingga diperoleh nilai dan pada tahap


43

5 kita mempunyai nilai . Diketahui , maka persamaan rekursif

untuk tahap 4 adalah

dengan



Solusi Optimal

)

8 3(0)+0+8=8 3(1)+0+6=9 3(2)+0+0=6 6 6

Tabel 3.1.8


kolom kedua menunjukkan fungsi biaya pada tahap ke 4 dengan nilai seperti

yang telah diperoleh pada tahap 5 sehingga diperoleh entri seperti pada Tabel

3.1.8. Entri pada kolom diperoleh dengan mencari nilai minimum pada

kolom kedua dan nilai diperoleh dari nilai yang memuat nilai minimum

pada kolom ketiga.

Tahap 3


membutuhkan minimal 7 pekerja. Sehingga diperoleh nilai dan pada

tahap 4 kita mempunyai nilai . Diketahui , maka persamaan rekursif

untuk tahap 3 adalah

dengan




44

Solusi Optimal

7 3(0)+4+2(1)+6=12 12 8

8 3(0)+0+6=6 6 8

Tabel 3.1.9






pada kolom ketiga.

Tahap 2


membutuhkan minimal 5 pekerja, namun pada minggu ke-3 dibutuhkan 8 pekerja.

Sehingga diperoleh nilai dan pada tahap 3 kita mempunyai nilai

. Diketahui , maka persamaan rekursif pada tahap 2 adalah

dengan



Solusi Optimal

)

5 3(0)+4+2(2)+12=20 3(1)+4+2(3)+6=19 19 8

6 3(0)+4+2(1)+12=18 3(1)+4+2(2)+6=17 17 8

7 3(0)+0+12=12 3(1)+4+2(1)+6=15 12 7

8 3(0)+0+12=12 3(1)+0+6=9 9 8

Tabel 3.1.10


45






pada kolom ketiga.

Tahap 1


belum ada pekerja. Sehingga diperoleh nilai dan pada tahap 2 kita

mempunyai nilai . Diketahui , maka persamaan rekursif pada

tahap 1 adalah

dengan



Solusi

Optimal

)

0 3(0)+4+2(5)

+19=33

3(1)+4+2(6)

+17=36

3(1)+4+2(7)

+12=36

3(2)+4+2(8)

+9=35 33 5

Tabel 3.1.11






pada kolom ketiga.


46

Solusi optimalnya ditentukan oleh

Minggu

ke-

Minimum tenaga

kerja yang

dibutuhkan (

Tenaga kerja

yang direkrut ( Keputusan Biaya

1 5 5 Rekrut 5 pekerja

2 7 8 Rekrut 3 pekerja

3 8 8 Tidak ada

perubahan 0

4 4 6 Pecat 2 pekerja

5 6 6 Tidak ada

perubahan 0

Jadi total biaya yang dikeluarkan adalah .

3.1.3 Model Penggantian Peralatan

Dalam sebuah pabrik, jika ada mesin yang bertahan lama dalam

pelayanannya dikenai biaya pemeliharaan yang lebih tinggi dan dapat diganti

setelah beberapa tahun beroperasi. Situasi ini mencakup tahun. Pada awal setiap

tahun, sebuah mesin dapat dipertahankan satu tahun lagi atau diganti dengan yang

baru. Diberikan , dan masing-masing adalah nilai tukar-tambah,

biaya operasi dan biaya pembelian mesin baru. Biaya untuk mendapatkan mesin

baru di setiap tahun adalah .

Elemen dari Program Dinamis diberikan oleh:

1. Tahap ke- menunjukkan tahun ke- , .

2. Alternatif pada tahap (tahun) ke- akan menyimpan (K) atau mengganti (R) mesin

pada awal tahun ke- .

3. Keadaan pada tahap ke- adalah usia mesin pada awal tahun ke- .

Diketahui mesin berumur tahun pada awal tahun , maka didefinisikan

penghasilan bersih maksimum selama tahun


47

Persamaan rekursifnya adalah

Contoh 3.1.4

Sebuah perusahaan perlu menentukan kebijakan penggantian yang optimal untuk

mesin yang berumur 2 tahun untuk 4 tahun ke depan. Perusahaan mempunyai

ketentuan bahwa mesin yang berumur 6 tahun harus diganti. Biaya yang

diperlukan untuk membeli mesin baru setiap tahunnya adalah $100,000.

Diberikan tabel sebagai berikut

0 20,000 200

1 19,000 600 80,000

2 18,500 1200 60,000

3 17,200 1500 50,000

4 15,500 1700 30,000

5 14,000 1800 10,000

6 12,200 2200 5000

Tabel 3.1.12

Dengan adalah umur mesin (dalam tahun), adalah nilai tukar-tambah,

adalah biaya operasi dan adalah biaya pembelian mesin baru. Nilai tukar-

tambah, biaya operasi dan biaya pembelian mesin baru dalam dollar. Tentukan

solusi optimal dalam penggantian mesin di perusahaan tersebut !

Jawab:

Penentuan solusi yang layak untuk usia mesin pada setiap tahap agak rumit. Pada

awal tahun pertama, perusahaan memiliki mesin berusia 2 tahun. Perusahaan

memiliki 2 pilihan, yaitu mengganti (R) atau menyimpannya (K). Jika

{

{

}


48

penggantian terjadi, maka pada awal tahun kedua perusahaan memiliki mesin baru

yang berumur 1 tahun. Jika tidak terjadi penggantian, maka pada awal tahun

kedua perusahaan memiliki mesin yang berumur 3 tahun. Hal ini terus terjadi dari

awal tahun kedua hingga tahun keempat. Jika mesin berusia 1 tahun diganti pada

awal tahun 2, 3, dan 4, maka umur mesin adalah 1 tahun pada awal tahun

berikutnya. Pada akhir tahun 4, perusahaan akan menyelamatkan mesin (S).

Uraian di atas dapat diringkas seperti Gambar 3.1.2 berikut

Grafik menunjukkan bahwa pada awal tahun ke-2, kemungkinan usia dari

mesin adalah 1 dan 3 tahun. Pada awal tahun ke-3, kemungkinan usia mesin

adalah 1, 2 dan 4 tahun. Dan untuk awal tahun ke-4, kemungkinan usia mesin

adalah 1, 2, 3 dan 5 tahun. Grafik juga mengasumsikan bahwa mesin akan

diselamatkan pada awal tahun ke-5 tanpa memandang usia.

Solusi pada Gambar 3.1.2 sama seperti menentukan rute terpanjang. Pada

permasalahan ini kita mencari pendapatan maksimum dari awal tahun pertama

hingga akhir tahun keempat. Kita akan menggunakan tabel untuk menyelesaikan

permasalahan. Perhatikan bahwa jika mesin diganti pada tahun keempat atau pada

Gambar 3.1.2

Tahun ke-

Um

ur

mes

in

K K

K

R

K

6

3

4

5

1

1

2 3 5 4

S

S

S

S

K

K

R R R S R

K

K

R

R

K

R K

R

R

4

1

2

1 1 1

4

2 2

3 3

5

6

End 3

K = Disimpan

R = Diganti

S = Dijual

2


49

akhir dari perencanaan, maka pendapatannya mencakup nilai sisa dari mesin

pengganti. Begitu pula jika pada tahun keempat mesin dengan usia disimpan,

maka nilai sisa akan menjadi .

Tahap 4

Tahap 4 menunjukkan usia mesin pada tahun ke-4. Dari Gambar 3.1.2 dapat

diketahui bahwa pada tahun ke-4 umur mesin adalah 1, 2, 3 dan 5 sehingga dapat

ditentukan nilai .

Persamaan rekursif pada tahap 4 adalah

{

Solusi Optimal

Keputusan

1 79.8

2 67.3

3 49.8

5 17.2

Tabel 3.1.13


Kolom kedua diperoleh dengan memasukkan nilai yang diketahui pada Tabel

3.1.12 dan entri pada kolom diperoleh dengan mencari nilai maksimum

antara kolom kedua dan kolom ketiga. Keputusan dapat diambil berdasarkan

kolom yang memuat nilai maksimum yang telah ditentukan pada kolom keempat.

Tahap 3

Seperti pada tahap 4, tahap 3 menunjukkan usia mesin pada tahun ke-3. Dari

Gambar 3.1.2 dapat diketahui bahwa usia mesin pada tahun ke-3 adalah 1, 2 dan 4

sehingga dapat ditentukan nilai . Karena pada tahap 4 kita memiliki nilai

) maka persamaan rekursif pada tahap 3 menggunakan persamaan yang kedua

yaitu


50

{

}

Tabel 3.1.14






Tahap 2

Seperti pada 2 tahap sebelumnya, tahap 2 menunjukkan usia mesin pada tahun ke-

2. Dari Gambar 3.1.2 dapat diketahui bahwa usia mesin pada tahun ke-2 adalah 1

dan 3 sehingga dapat ditentukan nilai . Karena pada tahap 3 kita memiliki

nilai ) maka persamaan rekursif pada tahap 2 menggunakan persamaan yang

kedua yaitu

{

}

Tabel 3.1.15




Solusi Optimal

Keputusan

1 85.7

2 67.1

4 31

Solusi Optimal

Keputusan

1 85.5

3 55.5


51



Tahap 1

Seperti pada tahap-tahap sebelumnya, tahap 1 menunjukkan usia mesin pada

tahun ke-1. Dari Gambar 3.1.2 dapat diketahui bahwa usia mesin pada tahun ke-1

adalah 2 sehingga dapat ditentukan nilai . Karena pada tahap 2 kita memiliki

nilai ) maka persamaan rekursif pada tahap 2 menggunakan persamaan yang

kedua yaitu

{

}

Solusi Optimal

Keputusan

2 72.8

Tabel 3.1.16






Gambar 3.1.2 merangkum solusi optimal. Pada awal tahun pertama diberikan

, keputusan optimalnya adalah mempertahankan mesin tersebut. Dengan

demikian, pada awal tahun kedua mesin akan berumur 3 tahun, dan keputusan

optimalnya adalah mengganti mesin. Pada awal tahun ketiga, mesin akan berumur

1 tahun karena baru saja diganti, sehingga keputusan optimalnya adalah

mempertahankan mesin. Dan pada tahun keempat umur mesin adalah 2 tahun,

solusi optimalnya adalah mempertahankan mesin.


52

Kebijakan optimal alternatif mulai dari tahun pertama adalah . Total

biaya yang diperlukan adalah $72,800.

3.1.4 Model Investasi

Misalkan kita akan menginvestasikan sejumlah pada awal

setiap tahun berikutnya. Kita memiliki dua peluang di dua bank, Bank Pertama

menawarkan bunga sebesar dan Bank Kedua menawarkan bunga sebesar ,

keduanya bertambah setiap tahun. Untuk meningkatkan jumlah simpanan, kedua

bank membayar bonus investasi baru dalam bentuk persentase dari jumlah yang

diinvestasikan. Masing-masing persentase bonus untuk Bank Pertama dan Bank

Kedua adalah dan untuk tahun . Bonus dibayarkan pada akhir tahun

dimana investasi tersebut dibuat dan dapat dapat diinvestasikan kembali di salah

satu bank pada tahun berikutnya. Ini berarti hanya bonus dan uang baru yang

dapat diinvestasikan di salah satu bank. Namun, begitu investasi disimpan harus

tetap di bank sampai akhir tahun .

Elemen dari model pemrograman dinamis didefinisikan sebagai berikut:

1. Tahap menunjukkan tahun ke- dengan .

2. Alternatif pada tahap adalah dan , masing-masing menunjukkan jumlah yang

diinvestasikan untuk Bank Pertama dan Bank Kedua.

3. Keadaan pada tahap adalah yang menunjukkan jumlah modal yang tersedia

untuk investasi pada awal tahun .

Didefinisikan , maka

( )

Jumlah reinvestasi hanya mencakup uang baru ditambah dengan bonus dari

investasi yang dibuat pada tahun . Misalkan diberikan nilai dan

didefinisikan adalah nilai optimal dari investasi untuk tahun .


53

Selanjutnya, tentukan sebagai akumulasi jumlah pada akhir tahun .

Perlu diingat bahwa dan masing-masing adalah investasi yang dibuat

pada tahun di Bank Pertama dan Bank Kedua. Diketahui dengan

maka permasalahan tersebut dapat dinyatakan sebagai berikut:

dimana

(

)

Nilai dan pada ditambahkan karena bonus untuk tahun adalah bagian

dari akumulasi jumlah uang pada akhir dari investasi.

Persamaan rekursif untuk model pemrograman dinamis adalah

dengan didefinisikan sebagai fungsi dari .

Contoh 3.1.4

Seorang investor ingin menginvestasikan uang sebesar $5000 untuk sekarang,

$4000 pada awal tahun ke-2, $3000 pada awal tahun ke-3 dan $2000 pada awal

tahun ke-4. Suku bunga yang ditawarkan oleh Bank Pertama adalah 8% setiap

tahun dengan bonus selama 4 tahun kedepan masing-masing adalah 1.8%, 1.7%,

2.1% dan 2.5%. Sedangkan suku bunga yang ditawarkan Bank Kedua sebesar

7.8% dengan bonus yang ditawarkan setiap tahun 0.5% lebih tinggi dibandingkan

Bank Pertama. Tentukan maksimum akumulasi modal pada akhir tahun ke-4 !

Jawab:

Menggunakan notasi yang telah diberikan, diketahui

,


54

Misalkan adalah jumlah yang diinvestasikan pada tahap .

Tahap 4

Misalkan , maka persamaan rekursif untuk tahap 4 adalah

karena maka dapat ditulis

dimana

=

Fungsi linear terhadap pada rentang dan nilai maksimumnya

terjadi pada saat karena koefisien bernilai negatif. Dengan demikian

solusi optimal untuk tahap 4 dapat diringkas sebagai berikut

Solusi optimal

Keadaan

Tabel 3.1.17

Kolom pertama menunjukkan jumlah modal yang tersedia untuk tahap 4. Kolom

kedua menujukkan nilai optimal dari investasi yang diperoleh dengan mencari

nilai maksimum pada saat sedangkan adalah jumlah yang akan

diinvestasikan pada tahap 4 yang nilainya sama dengan .


55

Tahap 3


dimana

Maka diperoleh

Sama seperti tahap 4, fungsi tersebut linear terhadap pada rentang

sehingga nilai maksimum terjadi pada saat karena koefisien bernilai

negatif. Dengan demikian solusi optimal untuk tahap 3 adalah

Solusi Optimal

Keadaan

Tabel 3.1.18


56


kedua menunjukkan nilai optimal dari investasi yang diperoleh dengan mencari

nilai maksimum pada saat . Sedangkan adalah jumlah yang akan

diinvestasikan pada tahap 3 yang nilainya sama dengan .

Tahap 2


dimana

Maka diperoleh

Sama seperti dua tahap sebelumnya, fungsi tersebut linear terhadap pada

rentang sehingga pada saat fungsi tersebut akan mempunyai

nilai maksimum. Dengan demikian solusi optimal untuk tahap 2 adalah


57

Solusi Optimal

Keadaan

Tabel 3.1.19


kedua menunjukkan nilai optimal dari investasi yan diperoleh dengan mencari

nilai maksimum pada saat sedangkan adalah jumlah yang akan

diinvestasikan pada tahap 2.

Tahap 1


dimana

Maka diperoleh


58

Sama seperti tahap 2, fungsi tersebut linear terhadap pada rentang

yang mempunyai nilai maksimum ketika nilai . Dengan demikian solusi

optimal untuk tahap 1 adalah

Solusi Optimal

Keadaan

Tabel 3.1.20

Pada kolom pertama menunjukkan besarnya modal awal yang akan diinvestasikan

pada tahun pertama yaitu sebesar $5000. Sedangkan kolom kedua menunjukkan

fungsi nilai optimal dari total akumulasi pada akhir tahun keempat. Dan adalah

jumlah yang akan diinvestasikan pada tahun pertama.

Dari semua tahap diperoleh

, sehingga

Dan diperoleh nilai sebagai berikut


59

Solusi optimal dari permasalahan tersebut dapat diringkas sebagai berikut

Tabel 3.1.21

Total akumulasi yang hasilnya akan sama jika

dihitung dengan menggunakan persamaan

Tahun Solusi Optimal Keputusan Akumulasi

1

Investasi

di Bank Pertama

2

Investasi

di Bank Pertama

3

Investasi

di Bank Kedua

4

Investasi

di Bank Kedua


60

3.2 Pemrograman Dinamis Probabilistik

Unsur-unsur utama dari model pemrograman dinamis probabilistik sama

seperti dalam kasus pemrograman dinamis deterministik, yaitu model ini juga

menguraikan masalah menjadi tahap-tahap dengan keadaan (state) dan alternatif

yang terkait dengan setiap tahap. Yang membedakan adalah sifat probabilistik

dari variabel keadaan dan keuntungan yang diharapkan berdasarkan pada kriteria

pengoptimalan nilai. Pemrograman dinamis probabilistik muncul dalam model

persediaan pengobatan stokastik dan proses keputusan Markovian. Berikut adalah

beberapa contoh model pemrograman dinamis probabilistik:

3.2.1 Permainan Peluang

Permainan peluang (Game of Chance) merupakan sebuah variasi dari

permainan rolet Rusia. Rolet Rusia dimainkan dengan cara memutar roda yang

ditandai dengan angka berturut-turut di sepanjang permukaan roda tersebut.

Probabilitas bahwa roda akan berhenti pada angka setelah satu putaran adalah .

Seorang pemain membayar untuk hak istimewa memutar roda sebanyak

maksimum kali. Imbalan kepada pemain adalah dua kali jumlah yang

dihasilkan pada putaran terakhir.

Dengan asumsi permainan diulang berkali-kali, dapat dibuat strategi optimal

untuk pemain dengan mendefinisikan masalah model pemrograman dinamis

sebagai berikut:

1. Tahap adalah putaran ke- dengan .

2. Alternatif pada setiap tahap adalah kesempatan memutar roda sekali lagi atau

mengakhiri permainan.

3. Keadaan dari sistem pada tahap adalah peluang angka yang muncul

pada akhir putaran.

Diberikan adalah ekspektasi pengembalian maksimum yang diberikan

pada tahap dan adalah hasil atau keluaran angka yang muncul pada putaran

terakhir.


61

Dengan demikian

Maka persamaan rekursifnya adalah

{

∑

}

∑

Pada putaran pertama diberikan nilai karena permainan baru saja

dimulai, maka dapat diperoleh

Setelah putaran terakhir , permainan harus berakhir terlepas dari hasil

akhir yang keluar pada putaran ke- , maka . Perhitungan dimulai

dengan dan diakhiri dengan , sehingga menghasilkan tahapan.

Karena adalah pengembalian yang diharapkan dari semua putaran dan

adalah biaya permainan, maka laba bersihnya adalah .

Contoh 3.2.1

Seorang pemain membayar $5 untuk memutar rolet Rusia yang ditandai dengan

angka 1 sampai 6 maksimal 5 putaran. Diketahui peluang kemungkinan berhenti

pada nomor masing-masing adalah

dan . Tentukan strategi optimal untuk masing-masing

putaran dan laba bersih yang diharapkan !

Jawab:

Diketahui

(

, {

∑


62

Tahap 6


Karena tahap ini merupakan tahap terakhir maka permainan harus berhenti.

Dari tahap 6 kita peroleh nilai

Tahap 5

Persamaaan rekursif untuk tahap 5 adalah

{

∑

Sehingga diperoleh

{

Pada tahap 5 jika angka yang keluar adalah angka 1, 2 atau 3 maka permainan

tetap berlanjut. Sedangkan jika angka yang keluar adalah angka 4, 5 atau 6 maka

permainan berhenti.

Tahap 4



63

{

∑

Sehingga diperoleh

{

Pada tahap 4 jika angka yang keluar adalah angka 1, 2, 3, 4 atau 5 maka

permainan tetap berlanjut. Sedangkan jika angka yang keluar adalah angka 6

maka permainan berhenti.

Tahap 3


{

∑

Sehingga diperoleh

{

Pada tahap 3 permainan terus berlanjut berapapun angka yang keluar saat rolet

diputar.

Tahap 2



64

{

∑

Sehingga diperoleh

{

Pada tahap 2 permainan terus berlanjut berapapun angka yang keluar saat rolet

diputar.

Tahap 1

Karena tahap 1 merupakan putaran pertama maka nilai sehingga

Dari tahap 1 sampai dengan 6 dapat diringkas sebagai berikut

Ekspektasi laba bersih yang diterima pemain adalah

Putaran ke- Strategi Optimal

1 Permainan dimulai, putar rolet

2 Permainan berlanjut berapapun angka yang keluar

3 Permainan berlanjut berapapun angka yang keluar

4 Lanjutkan jika angka yang keluar 1, 2, 3, 4, 5 atau permainan

berhenti

5 Lanjutkan jika angka yang keluar 1, 2, 3 atau permainan berhenti


65

3.2.2 Masalah Investasi

Misalkan seorang investor ingin berinvestasi sebesar ribu di pasar saham

selama tahun berikutnya. Rencana investasi yang akan dilakukan adalah

membeli saham pada awal tahun dan menjual saham pada akhir tahun yang sama.

Akumulasi yang diperoleh dapat diinvestasikan kembali secara keseluruhan atau

sebagian pada awal tahun berikutnya. Tingkat resikonya ditunjukkan dengan

adanya pengembalian probabilistik. Studi pasar menunjukkan laba atas investasi

dipengaruhi oleh kondisi pasar dan kondisi menghasilkan keuntungan

yang bernilai positif, nol atau negatif dengan probabilitas , .

Didefinisikan adalah dana yang tersedia pada awal tahun dan adalah

dana yang diinvestasikan pada awal tahun . Untuk merealisasikan akumulasi

tertinggi pada akhir tahun dengan menginvestasikan sejumlah ditetapkan

unsu-unsur model pemrograman dinamis sebagai berikut:

1. Tahap adalah tahun ke- dengan .

2. Alternatif pada tahun ke- adalah dengan .

3. Keadaan pada tahun ke- adalah dengan .

Diberikan pada awal tahun ke- dan diketahui adalah dana

maksimum yang diharapkan untuk tahun .

Untuk kondisi pasar diketahui

dengan

= jumlah dana pada awal tahun ke-

= total bunga atau keuntungan yang diperoleh pada tahun ke-

Mengingat bahwa kondisi pasar terjadi dengan probabilitas , maka persamaan

rekursif model pemrograman dinamis untuk masalah investasi adalah

{∑

}


66

dimana karena tidak terjadi investasi setelah tahun ke- .

Untuk tahun ke- diperoleh persamaan sebagai berikut:

{∑

}

{(∑

+ }

Misalkan

∑

maka

{

dan

{

Contoh 3.2.2

Seorang investor ingin menginvestasikan uang sebesar $10,000 selama 4 tahun ke

depan dengan probabilitas dan pengembalian setiap tahunnya diberikan oleh

Tabel 3.2.1

Tahun

1

2

3

4

Tabel 3.2.1

Jawab:

Diketahui

Tahap 4

Dari data pada Tabel 3.2.1 dapat diperoleh nilai


67

∑

Karena nilai maka sehingga persamaan rekursif untuk tahap 4

adalah

Maka solusi optimal untuk tahap 4 sebagai berikut

Solusi Optimal

Keadaan

Tabel 3.2.2

Tahap 3


{∑

}


Maka solusi optimal untuk tahap 3 sebagai berikut

Solusi Optimal

Keadaan

Tabel 3.2.3


68

Tahap 2


{∑

}


Karena maka solusi optimal untuk tahap 2 adalah

Solusi Optimal

Keadaan

Tabel 3.2.4

Tahap 1


{∑

}



69

Kareana maka solusi optimal untuk tahap 4 adalah

Solusi Optimal

Keadaan

Tabel 3.2.5

Karena untuk maka solusi optimal dapat diinvestasikan secara

keseluruhan pada awal setiap tahunnya. Akumuasi dana pada akhir tahun keempat

adalah

3.2.3 Memaksimalisasi Kejadian Untuk Mencapai Tujuan

Pada subbab ini dibahas masalah yang berkaitan dengan memaksimalkan

pengembalian optimal yang diharapkan atau memaksimalkan kemungkinan

mencapai tingkat pengembalian tertentu. Hal ini biasa ditemukan dalam masalah

investasi untuk menggambarkan penerapan kriteria baru.

Definisi tahap , alternatif dan keadaan pada subbab ini sama dengan

definisi pada subbab 3.2.2. Kriteria baru memaksimalkan kemungkinan

merealisasikan sejumlah uang pada akhir tahun .

Diberikan adalah jumlah dana yang tersedia pada awal tahun dan

didefinisikan adalah probabilitas untuk merealisasikan sejumlah uang

dengan kebijakan optimal yang dilaksanakan selama tahun .

Persamaan rekursif pemrograman dinamis untuk masalah ini adalah

{∑

}

{∑

}

dengan

= probabilitas pada tahun

= jumlah uang yang tersedia pada tahun

= keuntungan pada tahun


70

Karena probabilitas yang diperoleh pada tahun bergantung pada jumlah

uang yang tersedia pada tahun ditambahkan dengan keuntungan yang diperoleh

pada tahun yang sama maka persamaan tersebut dapat ditulis berdasarkan hukum

probabilitas sebagai berikut

∑ |

dengan dianggap sebagai | .

Contoh 3.2.3

Seorang investor ingin menginvestasikan uang sebesar $3000. Peluang jumlah

uang yang diinvestasikan dapat digandakan adalah 0.6 sedangkan kemungkinan

untuk kehilangan semua investasi adalah 0.4. Investasi akan dijual pada akhir

tahun dan diinvestasikan kembali secara keseluruhan atau sebagian pada awal

tahun berikutnya. Proses ini terus diulang untuk 3 tahun ke depan. Tujuan dalam

investasi ini adalah untuk memaksimalkan kemungkinan mendapat $6000 pada

akhir tahun ke-3. Diasumsikan bahwa semua investasi berkelipatan $1000.

Jawab:

Dengan menggunakan notasi model diperoleh nilai dengan probabilitas 0.6

dan dengan probabilitas 0.4.

Tahap 3

Pada tahap ini, keadaan bisa sekecil $0 dan sebesar $12,000 sehingga diperoleh

nilai . Nilai minimum terjadi ketika seluruh investasi hilang dan

nilai maksimal terjadi ketika investasi digandakan pada akhir tahun. Persamaan

rekursif untuk tahap 3 adalah

{ }

dimana

Tabel 3.2.6 meringkas perhitungan untuk tahap 3. Semua entri yang diarsir tidak

layak karena tidak memenuhi syarat . Dengan memperhatikan perhitungan

dapat diperoleh


71

{

{

Tabel 3.2.6 menunjukkan bahwa solusi optimal untuk pada

kolom terakhir hanya memberikan nilai optimal yang terkecil. Artinya bahwa

investor tidak akan berinvestasi lebih dari apa yang benar-benar diperlukan untuk

mencapai tujuan yang diinginkan.

Tahap 2

Pada tahap ini, keadaan bisa sekecil $0 dan sebesar $6000 sehingga diperoleh

nilai . Nilai minimum terjadi ketika seluruh investasi hilang dan

nilai maksimum terjadi ketika investasi digandakan. Persamaan rekursif untuk

tahap 2 adalah

dengan

Tabel 3.2.7 meringkas perhitungan untuk tahap 2. Semua entri yang diarsir tidak

layak karena tidak memenuhi syarat . Seperti tahap sebelumnya Tabel

3.2.7 juga menunjukkan bahwa solusi optimal untuk pada kolom

terakhir hanya memberikan nilai optimal yang terkecil.

Tahap 1

Tahap 1 merupakan tahap awal dimana investor mulai menginvestasikan uangnya,

sehingga dapat ditentukan nilai . Persamaan rekursif untuk tahap 1 adalah

dengan .

Perhitungan untuk tahap ini ditunjukkan oleh Tabel 3.2.8.


72

Dari ketiga tabel tersebut dapat ditentukan strategi optimal dengan cara sebagai

berikut:

Pada tahap 1, investasi awal sebesar $3000 dan dari Tabel 3.2.8 nilai

menghasilkan nilai , yang berarti tidak ada investasi yang harus dilakukan

pada tahun pertama. Karena pada tahun pertama investor tidak menginvestasikan

uangnya, maka pada tahun kedua investor masih memiliki modal untuk investasi

sebesar $3000. Pada tahap 2 Tabel 3.2.7, nilai menghasilkan nilai optimal

, yang artinya investor masih belum menginvestasikan uangnya pada tahun

kedua. Sehingga pada tahun ketiga investor masih memiliki uang sebesar $3000.

Dan pada tahap 3 Tabel 3.2.6, nilai menghasilkan nilai optimal ,

yang artinya investor akan menginvestasikan seluruh uangnya pada tahun ketiga.

Probabilitas untuk memaksimalkan kemungkinan mendapatkan pada

tahun ketiga adalah .


73

{

}

{

}

So

lusi

Op

tim

al

0

0

0

1

0

0

2

0

0

3

0

.6

3

4

0

.6

2

5

0.6

1

6

1

0

Tab

el 3

.2.6


74

{

}

{

}

So

lusi

Op

tim

al

7

1

0

8

1

0

9

1

0

10

1

0

11

1

0

12

1

0

Tab

el 3

.2.6


75

( ) ( ) Solusi

Optimal

( )

0

( ) ( )

0 0

1

( ) ( )

( ) ( )

0 0

2

( ) ( )

( ) ( )

( ) ( )

0.36 1

3

( ) ( )

( ) ( )

( ) ( )

( ) ( )

0.6 0

4

( ) ( )

( ) ( )

( ) ( )

( ) ( )

( ) ( )

0.6 0

5

( ) ( )

( )

( )

( )

( )

( ) ( )

( ) ( )

( ) ( )

0.84 1

6

( ) ( )

( )

( )

( )

( )

( )

( )

( ) ( )

( ) ( )

( ) ( )

1 0

Tabel 3.2.7

( ) ( ) Solusi Optimal

( )

3

( ) ( )

( ) ( )

( ) ( )

( ) ( )

0.6 0

Tabel 3.2.8


76

BAB IV

PEMROGRAMAN DINAMIS DENGAN MICROSOFT EXCEL

Pada bab ini akan dibahas tentang cara menyelesaikan pemrograman

dinamis dengan menggunakan Microsoft Excel. Fasilitas yang akan digunakan

adalah fungsi IF, fungsi MAX dan menu SOLVER. Untuk cara menambahkan

menu SOLVER pada toolbar akan dijelaskan pada lembar lampiran. Sebelum

memulai simulasi akan dijelaskan secara singkat mengenai fasilitas yang akan

dipakai.

1. Fungsi IF

Fungsi IF adalah salah satu fungsi yang memungkinkan untuk membuat logika

perbandingan antara nilai dan hasil apa yang diharapkan. Pernyataan IF dapat

memiliki dua hasil. Hasil pertama jika perbandingan benar dan hasil kedua jika

perbandingan salah.

2. Fungsi MAX

Fungsi MAX adalah fungsi yang digunakan untuk menentukan nilai terbesar

dalam sekumpulan nilai yang ada.

3. Menu SOLVER

Menu SOLVER adalah program tambahan pada Microsoft Excel yang bisa

digunakan untuk menganalisis kasus “Bagaimana-Jika”. Misalkan bagaimana

memaksimalkan keuntungan jika diberikan beberapa syarat yang mempengaruhi

keputusan. Menu SOLVER dapat digunakan untuk menemukan nilai maksimum

atau minimum sehingga keuntungan yang diharapkan optimal.

Ada 2 kasus yang akan diselesaikan menggunakan Microsoft Excel

4.1 Masalah Jarak Terpendek

Diketahui masalah jarak terpendek seperti pada Contoh 3.1.1. Akan dicari rute

terpendek dari kota 1 ke kota 7 dengan menggunakan menu SOLVER.


77

Langkah-langkah yang harus dilakukan adalah sebagai berikut:

1. Ubah data pada Gambar 3.1.1 menjadi tabel seperti Gambar 4.1.1. Apabila tidak

ada jalan yang menghubungkan dua kota secara langsung maka beri angka 100

pada kolom tersebut. Angka 100 hanya sebarang bilangan yang besar sehingga

penyelesaian tidak akan mengambil jalur tersebut.

Gambar 4.1.1

Terlihat pada gambar bahwa dari kota 1 ke kota 5 tidak ada jalan yang

menghubungkan kedua kota secara langsung, kota 5 hanya bisa ditempuh dari

kota 1 dengan melewati kota 2, kota 3 atau kota 4. Sehingga kolom yang

menghubungkan kedua kota tersebut diberi angka 100.

2. Copy-paste tabel pertama dan letakkan pada bagian bawah lembar kerja. Hapus

semua entri pada tabel kedua kemudian tambahkan kolom-kolom seperti pada

Gambar 4.1.2.


78

Gambar 4.1.2

3. Karena akan dicari total jarak maka semua kolom dan baris harus dijumlahkan. Isi

kolom-kolom tersebut dengan rumus sebagai berikut:

a. Kolom Total In

( )

Gambar 4.1.3

b. Kolom Total Out

( )


79

Gambar 4.1.4

4. Tambahkan kolom Out-In dan kurangkan hasil pada kolom I dengan baris 22

dengan rumus

Gambar 4.1.5

5. Tuliskan parameter untuk mengetahui bahwa hasil sudah optimal. Parameter yang

diberikan bergantung pada kasus yang diketahui. Jika kita menuliskan rumus In-

Out pada kolom J maka parameternya dimulai dari dan diakhiri dengan 1.


80

Gambar 4.1.6

6. Sediakan kolom untuk menghitung total jarak dan beri rumus

( )

Gambar 4.1.7

7. Masuk pada menu SOLVER yang ada pada toolbar Data

Gambar 4.1.8

8. Kemudian masukkan kendala-kendala sebagai berikut

a. Pada bagian Set Target Cell masukkan cell L4. Karena kita akan mencari

rute terpendek pilih min pada bagian Equal to


81

Gambar 4.1.9

b. Pada bagian By Changing Cells tuliskan tabel pertama (tabel soal)

Gambar 4.1.10

c. Masukkan kendala-kendala berikut ke dalam Subject to the Constraints

dengan menambahkannya menggunakan menu Add

Gambar 4.1.11

Pilih bin untuk memunculkan hasil binary pada cell tujuan kemudian klik OK.

Hasil dari cell nantinya akan menunjukkan rute yang akan dilalui.

Kemudian masukkan kendala seperti pada Gambar 4.1.12


82

Gambar 4.1.12

9. Setelah selesai memasukkan semua kendala klik Solve dan akan muncul hasil

sebagai berikut

Gambar 4.1.13

Kolom yang berwarna biru menujukkan rute yang akan dilewati. Dimulai dari

kota 1 menuju kota 3 kemudian ke kota 5 dan mencapai kota 7 dengan total jarak

21.


83

4.2 Masalah Penggantian Alat

Pada kasus kedua ini akan dibahas bagaimana menyelesaikan masalah

penggantian alat dengan menggunakan fungsi IF dan MAX. Penyelesaian masalah

dengan menggunakan fungsi IF dan MAX lebih sederhana dibandingkan dengan

menggunakan menu SOLVER.

Diketahui tabel seperti pada Contoh 3.1.4

Gambar 4.2.1

Akan dicari solusi optimal untuk mengganti mesin dengan umur tertentu dan

berapa total biaya yang harus dikeluarkan untuk mengganti mesin.

Langkah-langkah untuk menyelesaikannya adalah sebagai berikut:

1. Sama seperti cara manual yang sudah dijelaskan pada Bab III, penyelesaian

masalah ini dimulai dari tahap 4.

Gambar 4.2.2


84

Gambar 4.2.3

Perhitungan pada kolom B dan C dilakukan sesuai rumus yang tertera di atasnya

dengan mengambil data pada tabel soal yang diberikan. Pada kolom C cell tujuan

diberi tanda “$” yang berfungsi untuk mengunci cell sehingga kita tidak perlu

menulis cell yang sama berulang-ulang.

Pada kolom D dan E diperlukan fungsi IF dan MAX untuk menentukan hasilnya.

Untuk kolom D, masukkan rumus ( )

Untuk kolom E, masukkan rumus ( ) yang artinya jika hasil

pada cell D4 sama dengan cell B4 maka mesin akan disimpan, jika tidak maka

mesin akan diganti

Gambar 4.2.4


85

Gambar 4.2.5

2. Dengan cara yang sama dapat ditentukan hasil untuk tahap 3, 2 dan 1 seperti

berikut

Gambar 4.2.6

3. Dari Gambar 4.2.6 dapat dilihat bahwa cell D25 merupakan solusi optimal dari

masalah tersebut sehingga dapat ditentukan total biayanya sebagai berikut


86

Gambar 4.2.7

Untuk menentukan keputusan penggantian mesin dapat dilihat dari tahap 1. Pada

tahap 1 keputusan yang dihasilkan adalah K yang berarti mesin tetap disimpan

sampai tahun depan. Pada tahap 2 umur mesin adalah 3 tahun, pada baris 20

keputusan yang dihasilkan adalah R yang berarti mesin diganti dengan yang baru.

Maka pada tahun berikutnya yaitu pada tahap 3 umur mesin adalah 1 tahun, pada

baris 12 keputusan yang dihasilkan adalah K sehingga mesin tetap disimpan

sampai tahun depan. Pada tahap terakhir, umur mesin adalah 2 tahun, pada baris

ke 5 keputusan yang dihasilkan adalah K sehingga mesin tetap disimpan sampai

tahun depan. Maka keputusan yang optimal untuk masalah ini adalah K,R,K,K

dengan total biaya 72.800.


87

BAB V

PENUTUP

5.1 Kesimpulan

1. Penggunaan Pemrograman Dinamis dalam menyelesaikan beberapa

masalah dalam kehidupan sehari-hari sangat efektif karena langkah-

langkahnya yang sederhana dan mudah pahami.

2. Penggunaan Microsoft Excel dalam menyelesaikan masalah

Pemrograman Dinamis dirasa cukup mempermudah karena sebagian

orang sudah mengenal fungsi-fungsi umum yang sering digunakan

pada Microsoft Excel.

3. Menu SOLVER jarang digunakan dalam Microsoft Excel sehingga

tidak banyak yang tahu mengenai manfaat menu ini.

5.2 Saran

Beberapa hal yang perlu dipertimbangkan untuk penyempurnaan:

1. Pada makalah ini hanya diberikan satu kasus yang diselesaikan dengan

menu SOLVER. Oleh karena itu disarankan untuk mencari contoh

kasus lain yang dapat diselesaikan dengan menggunakan menu

SOLVER.

2. Pada makalah ini program yang dipakai dapat diperluas sehingga hasil

dapat otomatis keluar ketika data diinput ke dalam program.


88

DAFTAR PUSTAKA

Aris, Rutherford. (1964). Discrete Dynamic Programming. New York: Blaisdell

Publishing Company.

Cooper, Leon & Cooper, Mary W. (1981). Introduction to Dynamic Programming.

New York: Pergamon Press Ltd.

Denardo, Eric V. (2003). Dynamic Programming Models and Applications. New

York: Dover Publications, Inc.

Taha, Hamdy A. (2011). Operations Research An Introduction Ninth Edition. New

Jersey: Pearson Education, Inc.

Ventura, Jose A. “Dynamic Programming”. Operation Research and Management

Science Handbook edited by A. Ravi Ravindran. Taylor & Francis Group,

LLC, 2008, pp. 7.1-7.24.

Wackerly, Dennis. D. (2008). Mathematical Statistics with Applications 7th

Edition. USA: Thomson Learning, Inc.


89

LAMPIRAN

Cara menginstall add-ins pada Microsoft Excel:

1. Buka lembar kerja Microsoft Excel.

2. Pilih menu File kemudian pilih excel options.

3. Pilih menu add-ins.

4. Pada bagian manage pilih excel add-ins kemudian klik go.

5. Beri tanda pada solver add-ins kemudian klik OK dan menu solver telah

terinstal pada lembar kerja Microsoft Excel.


pemrograman dinamis: contoh kasus dan ...pemrograman dinamis: contoh kasus dan implementasi dengan...

Documents