Kamal, Achsanul (2017) Analisis perbandingan Algoritma Dynamic Programming dengan pendekatan Forward dan Backward melalui hasil studi kasus distribusi produk air minum kemasan galon di depot air minum isi ulang Banyu Belik, Purwokerto. Undergraduate thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
5213100146-Undergraduate-Theses.pdf - Published Version Download (2MB) | Preview |
Abstract
Dynamic Programming (DP) merupakan salah satu algoritma optimasi yang dapat diaplikasikan dalam kehidupan sehari-hari. Dynamic Programming menguraikan solusi menjadi tahapan-tahapan sehingga permasalahan dapat dipandang melalui serangkaian keputusan yang saling berkaitan. Dalam menyelesaikan permasalahan, Dynamic Programming memiliki dua pendekatan yaitu Forward dan Backward. Dengan kondisi yang sama, suatu permasalahan dapat diselesaikan melalui dua pendekatan tersebut. Namun pada penerapannya proses pencapaian nilai optimal pada tiap stage antara pendekatan Forward dan Backward ialah berbeda meskipun dengan nilai optimal akhir yang sama. Pada kondisi yang sama juga suatu permasalahan dapat menghasilkan nilai optimal akhir yang berbeda jika diselesaikan dengan pendekatan Forward dan Backward. Terkait dengan hal tersebut, maka Tugas Akhir ini bertujuan untuk mengetahui apa saja faktor yang mempengaruhi perbedaan tersebut serta mengetahui karakteristik dari tiap pendekatan diatas.
Dalam penelitian ini digunakan data dari studi kasus distribusi produk air kemasan galon di depot air minum isi ulang Banyu Belik yang terdapat di daerah Purwokerto. Pada studi kasus ini sebelumnya telah dilakukan optimasi dengan menggunakan kombinasi algoritma genetika dan pencarian tabu. Sehingga selain Melalui Tugas Akhir ini juga akan dilakukan perbandingan antara penyelesaian dengan menggunakan Dynamic Programming (DP) dan kombinasi algoritma genetika dan pencarian tabu untuk mengetahui hasil mana yang lebih optimal. Hasil dari tugas akhir ini menunjukkan bahwa pendekatan forward dan backward menghasilkan nilai optimal yang berbeda. Perbedaan nilai optimal tersebut dikarenakan oleh karakteristik dynamic programming dimana nilai optimum pada stage -k akan dipengaruhi oleh nilai optimum pada stage k-1. Selain itu faktor lain yang mengakibatkan adanya perbedaan nilai optimal untuk masing-masing pendekatan adalah karena karakteristik permasalahan Travelling Salesman Problem (TSP) yang memiliki beberapa titik tujuan yang dinamis. Permasalahan studi kasus berfokus kepada penyusunan rangkaian node agar mencapai nilai yang optimal.
=============================================================================
Dynamic Programming (DP) is one of the optimization
algorithms can be applied in daily life. Dynamic Programming devides solution into stages so that the problem can be seen through a series of interrelated decisions. By solving a problem, Dynamic Programming has two approaches, Forward and Backward. In the same conditions, a problem can be solved through two approaches. However, the implementation process of achieving optimal value at each stage between Forward and Backward approach is different even with the same final optimum value. On certain condition, a problem can also generate different final optimal value if completed with Forward and Backward approach. Related to this case, the final project aims to find out what factors influence these differences and to know the characteristics of
both approaches. This study used data from a case study of packaged water distribution at water refill depot Banyu Belik contained in Purwokerto. In this case study had previously been done optimization by using a combination of genetic algorithm and tabu search. So in addition Through this Final will also be made a comparison between Dynamic Programming (DP) and
the combination of genetic algorithm and tabu search to find out which is more optimal results. The results of this thesis show that the forward and backward
approach produces different optimal values. The optimal rate differences due to the characteristics of dynamic programming on a stage where the optimum value of k will be influenced by the optimum value in stage k-1. Besides other factors that lead to differences in the optimal value for each approach is due to the characteristics of the problem Travelling Salesman Problem (TSP), which has several points of interest are dynamic. The problems of case studies focused on the preparation of a series of nodes in order to achieve optimal value
| Item Type: | Thesis (Undergraduate) |
|---|---|
| Uncontrolled Keywords: | Dynamic Programming; Forward Approach; Backward Approach |
| Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science. EDP |
| Divisions: | Faculty of Information Technology > Information System > 57201-(S1) Undergraduate Thesis |
| Depositing User: | ACHSANUL KAMAL |
| Date Deposited: | 28 Feb 2017 03:33 |
| Last Modified: | 05 Mar 2019 06:29 |
| URI: | http://repository.its.ac.id/id/eprint/2394 |
Actions (login required)
 |
View Item |