Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Dynamic Programming

No description
by

Rama Prima

on 7 June 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Dynamic Programming

V
Dynamic programming dapat dibagi menjadi empat tahap yang berurutan sebagai berikut :
1. Karakterisasi struktur pada solusi optimasi
2. Mendefinisikan nilai solusi optimal secara rekursif
3. Menghitung nilai solusi optimal pada model bottom-up
4. Menyusun solusi optimal dari informasi hasil perhitungan
Langkah 1-3 adalah dasar dynamic-programming dalam menemukan solusi untuk suatu problem, Step 4 dapat dilakukan jika nilai solusi optimal diperlukan.

4 Tahap Dynamic Programming
Penyelesaian Dengan Metode Program Dinamis
Masalah Rute Terpendek
Dynamic Programming
Kelompok 10
Aplikasi Dalam Masalah Rute Terpendek
SEKIAN DAN TERIMA KASIH
Danny Purnamahadi
Iman Tri Atmojo
Rama Prima Revandia
Seszi Lubis
Abstract: Permasalahan pencarian jalur terpendek adalah permasalahan umum yang sering terjadi di dunia nyata.
Untuk menyelesaikannya terdapat banyak metode yang bisa digunakan, salah satunya adalah dengan
menggunakan metode dynamic programming. Dengan menggunakan metode ini, hasil dari pencarian jalur akan menjadi sangat optimum
Pemrograman dinamis merupakan suatu teknik analisa kuantitatif untuk membuat tahapan keputusan yang saling berhubungan. Teknik ini menghasilkan prosedur yang sistematis untuk mencari keputusan dengan kombinasi yang optimal.Pemrograman dinamis membagi permasalahan menjadi beberapa tahap keputusan, dimana hasil keputusan dari satu tahap akan mempengaruhi keputusan dari tiap-tiap tahapan selanjutnya.Berbeda dengan pemrograman linier, dalam pemrograman dinamis tidak ada formulasi matematis standar. Tetapi, pemrograman dinamis adalah sebuah pendekatan umum untuk pemecahan masalah, dan perhitungan yang digunakan harus dikembangkan agar sesuai dengan tiap-tiap situasi tertentu. Oleh karenanya, diperlukan suatu kepandaian dan pemahaman pada struktur umum permasalahan untuk mengetahui kapan dan bagaimana suatu permasalahan harus dipecahkan dengan pemrograman dinamis.
Ada 2 perbedaan mendasar antara pemrograman dinamis dan pemrograman linier. -Pertama, tidak ada algoritma (seperti metode simplex) yang bisa diprogramkan untuk memecahkan semua permasalahan. Sebaliknya, pemrograman dinamis adalah teknik yang mengarahkan kita untuk memecahkan masalah yang sulit menjadi tahapan dari beberapa masalah yang lebih mudah, yang kemudian dievaluasi berdasarkan tahapan. -Kedua, pemrograman linier adalah suatu metode yang menghasilkan solusi satu tahap (single stage solution) atau satu periode waktu. Pemrograman dinamis mempunyai kemampuan untuk mencari solusi optimal dari suatu permasalahan menjadi beberapa permasalahan dalam satuan waktu yang lebih kecil dan memecahkan tiap permasalahan tersebut dengan optimal (misal permasalahan dengan jangka waktu satu tahun dapat dibagi menjadi 12 permasalahan dengan jangka waktu 1 bulan). Jadi pemrograman dinamis menggunakan pendekatan banyak tahap (multistage).
Masalah dari gambar tersebut adalah bagaimana menentukan rute yang harus dilalui mulai dari kota 1 ke kota tujuan 9, agar diperoleh total jarak minimum. Hal ini dapat diselelesaikan dengan dua cara :

1. Mengambil rute yang terpendek dari satu kota ke kota berikutnya dalam setiap tahapan. Jika hal ini dilakukan maka rute yang ditempuh adalah mulai dari 1-3-6-8-9 dengan total jarak 520 km. Tetapi, rute terpendek yang sebenarnya adalah rute 1-3-5-7-9 dengan jarak 510 km.

2. Dengan cara menghitung satu-persatu setiap rute dan memilih rute terpendek diantaranya.

• 1-2-4-7-9 560 km
• 1-2-4-8-9 650 km
• 1-2-5-7-9 550 km
• 1-2-5-8-9 590 km
• 1-2-6-7-9 600 km
• 1-2-6-8-9 580 km
• 1-3-5-7-9
510 km
terpendek
• 1-3-5-8-9 550 km
• 1-3-6-7-9 540 km
• 1-3-6-8-9 520 km

Prinsip Dasar Dalam Menentukan Kebijakan Optimum & Aplikasi Dalam Masalah Rute Terpendek
Full transcript