Dynamic programming

1.     Definisi System Dynamic Programming

Dynamic programming problems adalah masalah multi tahap(multistage) dimana keputusan dibuat secara berurutan (in sequence).

Pemrograman dinamis (dynamic programming) adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian rupa sehingga solusi dari permasalahan ini dapat dipandang dari serangkaian keputusan-keputusan kecil yang saling berkaitan satu dengan yang lain. Penyelesaian persoalan dengan pemrograman dinamis ini akan menghasilkan sejumlah berhingga pilihan yang mungkin dipilih, lalu solusi pada setiap tahap-tahap yang dibangun dari solusi pada tahap sebelumnya, dan dengan metode ini kita menggunakan persyaratan optimasi dan kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

Karakteristik Persoalan yang dimiliki oleh Program Dinamis:

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

b.     Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut. Jumlahnya bisa berhingga atau tak berhingga.

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

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

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

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

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

h.     Prinsip optimalitas berlaku pada persoalan tersebut.

Langkah-langkah Pengembangan Algoritma Program Dinamis sebagai berikut :

a.           Karakteristikkan struktur solusi optimal.

b.     Definisikan secara rekursif nilai solusi optimal.

c.      Hitung nilai solusi optimal secara maju atau mundur.

d.     Konstruksi solusi optimal.

2.               Kelebihan dan kekurangan System Dynamic Programming

Kelebihan:

a.                Mengoptimalkan penyelesaian suatu masalah tertentu yang diuraikan menjadi sub-submasalah yang lebih kecil yang terkait satu sama lain dengan tetap memperhatikan kondisi dan batasan permasalahan tersebut.

b.     Proses pemecahan suatu masalah yang kompleks menjadi sub-sub masalah yang lebih kecil membuat sumber permasalahan dalam rangkaian proses masalah tersebut menjadi lebih jelas untuk diketahui.

c.      Pendekatan dynamic programming dapat diaplikasikan untuk berbagai macam masalah pemrograman matematik, karena dynamic programming cenderung lebih fleksibel daripada teknik optimasi lain.

d.     Prosedur perhitungan dynamic programming juga memperkenankan bentuk analisissensitivitas terdapat pada setiap variabel status (state) maupun pada variabel yang ada di masing-masing tahap keputusan (stage).

e.      Dynamic programming dapat menyesuaikan sistematika perhitungannya menurut ukuran masalah yang tidak selalu tetap dengan tetap melakukan perhitungan satu persatu secara lengkap dan menyeluruh.

Kelemahan:

a.              Penggunaan dynamic programming jika tidak dilakukan secara tepat, akan mengakibatkan ketidakefisienan biaya maupun waktu. Karena dalam menggunakan dynamic programming diperlukan keahlian, pengetahuan, dan seni untuk merumuskansuatu masalah yang kompleks, terutama yang berkaitan dengan penetapan fungsi transformasi dari permasalahan tersebut.

3.               Multi Stage Graph Problem

Multistage Graph adalah Graph dengan sifat-sifat khusus :

a.                Graph berarah (Directed Graph)

b.     Setiap edge-nya memiliki weight (bobot)

c.      Hanya terdapat 1 source (disebut s) dan 1 sink (disebut t)

d.     Lintasan dari source ke sink terdiri atas beberapa stage V1 sampai Vk

e.      Semua edge menghubungkan node di Vi ke sebuah node di Vi + 1 dimana 1 ≤ i ≤ k

f.      Terdapat stage sebanyak k, dimana k ≥ 2

g.     Setiap path dari s ke t merupakan konsekuensi dari pilihan sebanyak k–2

Multistage Graph merupakan bentuk permodelan yang dapat digunakan untuk menyelesaikan berbagai permasalahan dunia nyata.

Contoh : pemilihan project untuk mendapatkan keuntungan maksimal; serta pemilihan langkah-langkah yang harus dipilih dalam menyelesaikan sebuah tugas.

Multistage Graph Problem

a.                Problem mencari lintasan terpendek dari source ke sink pada sebuah Multistage Graph.

b.     Problem ini merupakan salah satu contoh penerapan yang bagus dari Dynamic Programming.

Dynamic Programming pada Multistage Graph Problem

Teknik penyelesaian Multistage Graph Problem dengan Dynamic Programming berdasar pada sebuah prinsip bahwa jalur terpendek dari satu node (awal atau akhir) ke node lain di stage tertentu merupakan jalur terpendek dari stage sebelumnya ditambah panjang salah satu edge penghubung stage.

a.    Metode Forward

Menghitung jarak ke depan (menuju sink)

b.     Metode Backward

Menghitung jarak ke belakang (dari source)

METODE FORWARD

·        Prinsip : analisis dilakukan dengan menghitung path (jalur) dari suatu node ke sink

·        Rumus : cost (i,j) = min{c (j,k) + cost (i+1,k)}

·        Perhitungan dimulai dari node-node di stage k–2

·        Cost (i,j) artinya panjang lintasan dari node j di stage i menuju sink (t)

·        c (j,l) artinya panjang lintasan dari node j ke node l

METODE BACKWARD

·        Prinsip : analisis dilakukan dengan menghitung path (jalur) dari source ke suatu node

·        Rumus : bcost (i,j) = min{bcost (i–1,l) + c (l,j)}

·        Perhitungan dimulai dari node-node di stage 3

·        Bcost (i,j) artinya panjang lintasan backward dari source (s) menuju node j di stage i

·        c (j,l) artinya panjang lintasan dari node j ke node l

Rute Terpendek Multistage Graph

·                  PEMBAHASAN

1.                Pengertian

Capital Budgeting adalah merupakan proses evaluasi dan pemilihan investasi jangka panjang yang konsisten terhadap maksimalisasi tujuan perusahaan. Definisi Capital Budgeting “Capital Budgeting is the Process of evaluating and selecting long-term invesments consistents with the firm’s goal of owner wealth maximization”. Investasi juga berarti pengeluaran pada saat ini dan hasil yang diharapkan dari pengeluaran tersebut baru akan diterima lebih dari satu tahun mendatang. Definisi Capital Budgeting adalah sebagai berikut: “Capital Budgeting involves the entire process of planning whose returns are expected to extend beyond one year”.

Sebagai konsekuensinya, perusahaan membutuhkan prosedur tertentu untuk menganalisa dan menyeleksi beberapa alternatif investasi yang ada. Keputusan mengenai investasi tersebut sulit dilakukan karena memerlukan penilaian mengenai situasi dimasa yang akan datang, sehingga dibutuhkan asumsi-asumsi yang mendasari estimasi terhadap situasi yang paling mendekati yang mungkin terjadi, baik situasi internal maupun eksternal perusahaan. Investasi tersebut harus dihitung sesuai dengan cash flow perusahaan dan harus merupakan keputusan yang paling tepat untuk menghindari resiko kerugian atas investasi tersebut. “As time passes, fixed assets may become obselete or may require an overhaul; at these points, too, financial decisions may be required”. Perusahaan biasanya membuat berbagai alternatif atau variasi untuk berinvestasi dalam jangka panjang, yakni berupa penambahan aset tetap seperti tanah, mesin dan peralatan. Aset tersebut merupakan aset yang berpotensi, yang merupakan sumber pendapatan yang potensial dan mencerminkan nilai dari sebuah perusahaan.Capital budgeting dan keputusan keuangan diperlakukan secara terpisah. Bila investasi yang diajukan telah ditentukan untuk diterima, manager keuangan kemudian memilih metoda pembiayaan yang paling baik.

·                  Anggaran (budget) adalah sebuah rencana rinci yg memproyeksikan aliran kas masuk dan aliran kas keluar selama beberapa periode pada saat yg akan datang.

·                  Capital budget adalah garis besar rencana pengeluaran aktiva tetap

·                  Penganggaran modal (capital budgeting) adalah proses menyeluruh menganalisa proyek2 dan menentuan mana saja yang dimasukkan ke dalam anggaran modal.

·                  Proses mengumpulkan, mengevaluasi, menyeleksi, dan menentukan alternatif penanaman modal yang akan memberikan penghasilan bagi perusahaan untuk jangka waktu lebih dari 1 tahun.

*. Pentingnya Penggangaran Modal

1.                Keputusan penggaran modal akan berpengaruh pada jangka waktu yang lama sehingga perusahaan kehilangan fleksibilitasnya.

2.                Penanggaran modal yg efektif akan menaikkan ketepatan waktu dan kualitas dari penambahan aktiva.

3.                Pengeluaran modal sangatlah penting

*. Motif Capital Budgeting

·                  Pengembangan produk baru atau pembelian aktiva baru

·                  Pengurangan biaya dengan mengganti aktiva yang tidak efisien

·                  Modernisasi atas aktiva tetap.

*. JENIS-JENIS KEPUTUSAN PENGANGGARAN MODAL

·                  Penambahan dan perluasan fasilitas

·                  Produk baru

·                  Inovasi dan perluasan produk

·                  Penggantian (replacements) (a) penggantian pabrik a1/11/2005tau peralatan usang (b) penggantian pabrik atau peralatan lama dengan pabrik atau peralatan yang lebih

·                  Menyewa/membuat atau membeli

·                  Penyesuaian fasilitas dan peralatan dengan peraturan pemerintah, lingkungan, dan keamanan

·                  Lain-lain keputusan seperti kampanye iklan, program pelatihan dan proyek-proyek yang memerlukan analisis arus kas keluar dan arus kas masuk.

*. PRINSIP DASAR PROSES PENGANGGARAN MODAL

·                  Penganggaran modal pada dasarnya adalah aplikasi prinsip yang mengatakan bahwa perusahaan harus menghasilkan keluaran atau menyelenggarakan kegiatan bisnis sedemikian rupa sehingga hasil imbuh (marginal revenue) produk sama dengan biaya imbuhnya (marginal cost).

·                  Prinsip ini dalam kerangka penganggaran modal berarti bahwa perusahaan harus melakukan tambahan investasi sedemikian rupa sehingga perolehan imbuh (marginal returns) investasi itu sama dengan biaya imbuhnya. Daftar berbagai proyek investasi dari hasil yang tertinggi hingga yang terendah mencerminkan kebutuhan perusahaan akan modal untuk investasi.

·                  Biaya imbuh dari berbagai daftar investasi itu memberi petunjuk tentang upaya perusahaan untuk memperoleh tambahan modal guna membiayai investasi. Biaya imbuh modal berarti sejumlah biaya yang harus ditanggung oleh perusahaan untuk memperoleh dana dari luar (misalnya meminjam atau menjual saham dan biaya tumbal/opportunity cost dari dana sendiri yang dapat diperoleh

*. Jenis Proyek

·                  Independent project: proyek atau investasi yang berdiri sendiri (tidak akan mempengaruhi usulan proyek lainnya).

·                  Mutually exclusive project: proyek yang memiliki fungsi yang sama (dengan memilih suatu proyek akan menghilangkan kesempayan proyek yang lainnya).

*. Ketersediaan Dana

·                  Jika dana TIDAK TERBATAS, maka perusahaan dapat memilih semua independen project yang sesuai dengan expected return yang diharapkan.

·                  Jika dana TERBATAS, maka perusahaan perlu melakukan capital rationing dengan mengalokasikan dana hanya pada proyek yang memberikan return maksimal

http://soalparna.blogspot.co.id/2015/03/teori-system-dynamic-programming.html