Aplikasi Algoritma Pemrograman Dinamik dengan program Matlab pada masalah Knapsack terhadap penentuan keuntungan maksimum di Toko Karomah Batu

ABSTRAK

Algoritma adalah suatu langkah yang digunakan untuk menyelesaikan masalah optimal untuk mencari solusi terbaik. Sedangkan pemrograman dinamik merupakan suatu prosedur optimisasi yang digunakan untuk menyelesaikan masalah yang banyak tahap, misalnya masalah knapsack. Berdasarkan latar belakang tersebut penelitian ini dilakukan dengan tujuan untuk (1) Membentuk model matematika pada permasalahan knapsack di Toko Karomah Batu; (2) Mengaplikasikan algoritma pemrograman dinamik pada masalah knapsack terhadap penentuan jumlah barang di Toko Karomah Batu.

Permasalahan knapsack dapat diselesaikan dengan menggunakan program dinamik dengan membagi masalah-masalah menjadi 17 submasalah yang melambangkan 17 kelompok barang. Langkah-langkah analisanya adalah sebagai berikut (1) Pengambilan data; (2) Menentukan struktur dari masalah; (3) Menentukan persamaan rekursif; (4) Menghitung nilai dari solusi optimal; (5) Menentukan keputusan optimal.

Data yang diperoleh dari Toko Karomah Batu dianalisis dengan mengunakan program Matlab agar diperoleh keuntungan maksimal. Hasil dari penelitian ini menunjukkan bahwa keuntungan total maksimal terbaik pada m=10, diperoleh total keuntungan optimal sebesar Rp. 123.810.628. Di Toko Karomah Batu pengalokasian dana paling banyak pada barang ke-13 yaitu perlengkapan pramuka. Hal ini disebabkan karena perbandingan keuntungan kelompok barang ke-13 dengan harga dasar kelompok barang ke-13 paling banyak diantara yang lain.

ABSTRACT

Algorithms is a step which used for solve optimal problem for look for a good solution. While dynamic programming is a optimization procedure which used for solve problem which many stages, example knapsack problem. Be based on background, the research did with goal for (1) Transform mathemathic modell at knapsack problem in Karomah Batu shop; (2) Apply dynamic programming algorithms at knapsack problem about determining quantity of goods in Karomah Batu shop.

Knapsack problem can solved with use dynamic program with divide problems become 17 subproblem which symbolize 17 goods group. Step by step of analysis is (1) Input data; (2) Determine structure of problem; (3) Determine recursif equation; (4) Calculate value from optimsl solution; (5) Determine optimal decision.

Data which got from Karomah Batu shop analyzed with Matlab program in order to got maximal profit. Result from this research indicate that a good total maximal profit at m = 10 got total optimal profit in the amount Rp. 123.810.628. In Karomah Batu shop, allocating of fund most at thirteenth good is equipment of scouts. This matter cause of comparison profit thirteenth good with cost price thirteenth good most among others.