Makalah Menentukan Utilitas Anggaran Biaya yang Dimiliki Menggunakan Metode Knapsack

MENENTUKAN UTILITAS ANGGARAN BIAYA YANG DIMILIKI MENGGUNAKAN

METODE KNAPSACK

  

Disusun untuk Memenuhi Tugas Kelompokpada Mata Kuliah

Mathematics Real Problem Solving yang Diampu oleh Drs. Kartono,M.Si dan Dr. Hj. Sunarsih,M.Si

Oleh :

1.             Pertiwi Putri Andini                     (24010110120024)

2.             Siti Shofiyyatul Afifah                (24010110141032)

3.             Sutikno                                         (24010111130046)

4.             Fitriyani                                        (24010113120025)

5.             Berti Nevada                                (24010113120040)

Telah dipresentasikan pada hari Jumat, 8 Mei 2015

JURUSAN MATEMATIKA

FAKULTAS SAINS DAN MATEMATIKA

UNIVERSITAS DIPONEGORO

SEMARANG

2015

KATA PENGANTAR

Puji syukur penyusun panjatkan kepada Tuhan Yang Maha Esa karena atas rahmat serta hidayah-Nya penyusun dapat menyelesaikan tugas yang berjudul“Menentukan Utilitas Anggaran Biaya Yang Dimiliki Menggunakan Metode Knapsack” guna memenuhi tugas kelompok pada mata kuliah Mathematics Real Problem Solving. Penyusun di dalam penyusunan makalah ini menyampaikan ucapan terima kasih kepada:

1.         Bapak Drs. Kartono,M.Si dan Ibu Dr. Hj. Sunarsih,M.Si selaku dosen pengampu pada mata kuliahMathematics Real Problem Solving.

2.         Bapak Bambang Irawanto, S.Si, M.Si selaku dosen pembimbing mata kuliah Program Bilangan Bulat yang telah memberikan bimbingan dan pengarahan dalam menyelesaikan tugas ini

3.         Rekan-rekan semua yang mengikuti perkuliahanMathematics Real Problem Solving.

4.         Keluarga yang selalu mendukung penyusun.

5.         Semua pihak yang ikut membantu penyusunan tugas “Menentukan Utilitas Anggaran Biaya Yang Dimiliki Menggunakan Metode Knapsack”, yang tidak dapat penyusun sebutkan satu persatu.

Penyusun merasa masih banyak kekurangan-kekurangan dalam penyusunan makalah ini baik pada teknis penulisan maupun materi, mengingat akan kemampuan yang dimiliki penyusun. Untuk itu, kritik dan saran dari semua pihak sangat penyusun harapkan demi penyempurnaan pembuatan makalah ini.

Semarang, Juni 2015

Penyusun

DAFTAR ISI

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

KATA PENGANTAR................................................................................   ii

DAFTAR ISI...............................................................................................   iii

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

A.      Latar Belakang ................................................................   1

B.       Rumusan Masalah............................................................   1

C.       Pembatasan Masalah........................................................   2

D.      Tujuan..............................................................................   2

BAB II         DASAR TEORI.....................................................................   3

A.    Program Bilangan Bulat....................................................   3

B.     Metode Knapsack (Ransel)...............................................   5

C.     Penentuan sebuah problem dengan Algoritma Knapsack. 5

D.    Penyelesaian Masalah Knapsack ( Ransel ) dengan Metode Branch & Bound............................................................... 6

BAB III       PEMBAHASAN....................................................................   8

A.    Formulasi Masalah.............................................................   8

B.     Penyelesaian Masalah.........................................................   8

BAB VIPENUTUP.....................................................................................   11

A.    Kesimpulan........................................................................   11

B.     Saran..................................................................................   12

DAFTAR PUSTAKA.................................................................................   13

LAMPIRAN.................................................................................................. 14

BAB I

PENDAHULUAN

A.    Latar Belakang

Kebutuhan sehari-hari terdiri dari beberapa macam, misalnya digolongkan berdasarkan tingkatan atau intensitasnya yaitu primer, sekunder, dan tersier. Bagi mahasiswa, kebutuhan primer misalnya makan, kost, pakaian. Kebutuhan sekunder seperti  membeli perlengkapan kecantikan, perlengkapan mandi, perlengkapan cuci, dan pembalut. Kebutuhan dengan sifat tersier seperti membeli bensin, pulsa,  fotokopi/print. Dalam memenuhi kebutuhan-kebutuhan tersebut dengan biaya atau uang saku yang terbatas, mahasiswa dituntut untuk pandai mengatur uang saku yang diberikan oleh orang tua agar dapat memenuhi kebutuhan tersebut hingga waktu yang ditentukan, biasanya dalam rentang waktu 1 bulan.

Banyak mahasiswa yang membeli kebutuhan sehari-hari tanpa memperhatikan faktor-faktor pentingnya. Misalnya, saat menentukan kebutuhan mana yang harus didahulukan yang sesuai dengan uang saku yang dimiliki dan anggaran yang telah ditentukan atau dirinci. Perincian anggaran ini diharapkan agar  setiap pengeluaran dapat terkontrol dan terencana, hingga pada akhirnya uang saku tidak habis sebelum pada waktunya. Oleh karena itu, diperlukan suatu metode untuk menentukan kebutuhan mana yang dapat dipenuhi jika anggaran biaya masing-masing kebutuhan telah ditentukan atau dirinci, yaitu dengan menggunakan metode knapsack.

B.     Rumusan Masalah

Memenuhi kebutuhan sehari-hari merupakan tujuan utama bagi mahasiswa  dikarenakan kebutuhan adalah hal yang sangat penting untuk menunjang hidup. Permasalahan yang akan dibahas adalah bagaimana cara menentukan kebutuhan yang dapat dipenuhi dengan memaksimalkan utilitas anggaran biaya kebutuhan yang telah ditentukan atau dirinci.

E.     Pembatasan Masalah

            Dalam tugas ini, pembatasan masalah diambil berdasarkan data yang diperoleh dari kebutuhan sehari-hari setiap bulan. Pembatasan masalah ini digunakan dalam penentuan kebutuhan sehari-hari dari anggaran yang dimiliki.

Asumsi-asumsi yang digunakan adalah sebagai berikut :

1.        Uang kost tidak termasuk di dalam uang saku.

2.        Tidak semua kebutuhan dibeli.

3.        Biaya yang dimiliki untuk memenuhi kebutuhan sehari-hari terbatas.

4.        Koefisien pada fungsi kendala adalah harga sebenarnya dari masing-masing kebutuhan.

5.        Koefisien pada fungsi tujuan adalah anggaran biaya yang telah ditentukan atau dirinci.

6.        Biaya atau uang saku diberikan oleh orang tua di setiap awal bulan.

F.      Tujuan

Penyusunan tugas ini memiliki tujuan, yaitu :

1.        Memberikan gambaran nyata yang ada pada kehidupan sehari-hari para mahasiswa dengan menggunakan Matematika untuk menjelaskan masalah tersebut.

2.        Mengaplikasikan metode Knapsack yang ada pada mata kuliah Program Bilangan Bulat untuk menentukan kebutuhan yang dapat dipenuhi jika anggaran biaya masing-masing kebutuhan telah dirinci.

BAB II

DASAR TEORI

A.    Program Bilangan Bulat

Program Bilangan Bulat adalah bentuk khusus dari Program Linier dimana asumsi divisibilitas melemah atau hilang sama sekali. Bentuk ini muncul karena dalam kenyataannya tidak semua variabel keputusan dapat berupa pecahan. Misalnya, jika variabel keputusan yang dihadapi berkaitan dengan jumlah mesin yang diperlukan pada suatu horizon perencanaan, maka jawaban 10/3 mesin sangat tidak realistis dalam konteks keputusan yang nyata. Dalam hal ini harus ditentukan, apakah akan menggunakan 3 atau 4 mesin.

Menurut  Tjutju  Tarliah  dan Ahmad Dimyati  (1992:  17), struktur model Program Bilangan Bulat :

1.      Variabel Keputusan 

Variabel  keputusan  adalah  variabel  yang  menguraikan  secara  lengkap keputusan-keputusan  yang  akan  dibuat  yang  merupakan  formulasi  dari apa yang dicari dalam persoalan tersebut.

2.      Fungsi Tujuan

Fungsi  tujuan  merupakan  fungsi  dari  variabel  keputusan  yang  harus dicapai agar penyelesaian optimal dapat ditentukan dari  semua nilai-nilai yang layak.

3.      Fungsi Kendala

Fungsi  kendala  merupakan  formulasi  dari  kendala-kendala  yang  dihadapi dalam menentukan nilai variabel-variabel keputusan.

4.      Pembatas Tanda

Pembatas  tanda  adalah  pembatas  yang  menjelaskan  apakah  variabel keputusan  hanya  bernilai  nonnegatif  atau  boleh  positif,  nol,  negatif, bernilai 1 (tidak terbatas dalam tanda).  

Asumsi Program Bilangan Bulat :

1.      Proporsionality (kesebandingan)

Kontribusi setiap variabel keputusan terhadap fungsi tujuan dan kendala adalah sebanding dengan nilai variable keputusan.

2.      Additivity (penambahan)

Kontribusi setiap variabel keputusan pada fungsi tujuan dan kendala adalah tidak tergantung dengan nilai variable keputusan yang lain (masing-masing variabel keputusan independen).

3.      Certainly (kepastian)

Setiap parameter pada koefisien fungsi tujuan,ruas kanan dan koefisien kendala diasumsikan dapat diketahui secara pasti.

Formulasi Program Bilangan Bulat :

1.      Pure Integer Programming

Contoh :

max

2.      Mix Integer Programming

Contoh :

3.      Binary Variable

Contoh :

B.     Masalah Knapsack(Ransel)

Persoalan  Knapsack(ransel) didefinisikan  sebagai  persoalan  yang  menyangkut pemilihan objek dengan bobot dan keuntungan tertentu sedemikian sehingga tidak melebihi kapasitas yang  telah ditentukan dan keuntungan yang ditargetkan dapat tercapai. Persoalan Knapsack atau persoalan ransel adalah persoalan program linier bilangan bulat yang hanya memiliki kendala  tunggal. 

Jenis Persoalan :

1.      Knapsack 0/1

Sesuatu yang dimasukkan ke dalam ransel (Knapsack) harus dimasukkan semua atau tidak sama sekali.

2.      Knapsack Bounded

Sesuatu yang dimasukkan ke dalam ransel (Knapsack) bisa dimasukkan sebagaian atau seluruhnya.

C.     Penentuan sebuah problem dengan Algoritma Knapsack

Algoritma Knapsack Problem memiliki sebuah problem atau pemasalahan yang bisa dilakukan, yaitu:

1.      UniversalSolusi, yaitu semua kemungkinan solusi baik yang benar dan yang salah. Memilih kandidat yang paling memungkinkan mencapai solusi optimal. Kandidat yang sudah dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah selanjutnya.

2.      Solusi Feasible, yaitu semua kemungkinan solusi benar, tetapi tingkat kebenarannya berbeda-beda. Memeriksa apakah suatu kandidat yang telah dipilih dapat memberikan solusi yang layak, yakni kandidat tersebut bersama-sama dengan himpunan solusi yang sudah terbentuk tidak melanggar kendala (constraints) yang ada. Kandidat yang layak dimasukkan ke dalam himpunan solusi, sedangkan kandidat yang tidak layak tidak diambil.

3.      Fungsi Objektif, yaitu fungsi untuk mengukur solusi mana yang lebih benar. Fungsi yang memaksimumkan atau meminimumkan nilai solusi (misalnya panjang lintasan, keuntungan, dan lain-lain). 

4.      Solusi Optimal, yaitu solusi yang paling benar. Dimana solusi bernilai minimum atau maksimum dari sekumpulan alternatif solusi yang mengoptimumkan fungsi optimasi.

D.   Penyelesaian Masalah Knapsack( Ransel ) dengan Metode Branch and Bound

Persoalan Knapsack(ransel) adalah persoalan Integer Programming yang hanya memiliki pembatas tunggal. Pada bagian ini kita hanya akan mendiskusikan persoalan ransel (Knapsack) yang seluruh variabelnya harus berharga 0 atau 1, yang dapat diformulasikan sebagai berikut:

Maksimumkan:                    

Dengan kendala :

                     

                     

adalah manfaat yang dapat diperoleh apabila barang ke-i dipilih, b adalah jumlah sumber yang tersedia,adalah jumlah sumber yang digunakan oleh barang ke-i, dan x_i adalah variabel keputusan.

Apabila persoalan ini diselesaikan dengan Branch and Bound, maka ada dua aspek pendekatan Branch and Bound yang disederhanakan. Pertama, karena setiap variabel harus berharga 0 atau1 maka pencabangan pada akan menghasilkan cabang =0 dan =1. Kedua, Linier Programming (Program Linier) relaksasi (dan sub persoalan yang lain) dapat diselesaikan dengan melakukan pemeriksaan terhadap nilai . Untuk melihat hal ini perhatikan bahwa  dapat diinterpretasikan sebagai manfaat yang diperoleh barang ke-i dari setiap unit sumber yang digunakan oleh barang ke-i. Jadi, barang yang terbaik adalah barang yang memiliki nilai terbesar dan barang yang terburuk adalah yang memiliki nilai terkecil.

Untuk menyelesaikan setiap sub persoalan yang dihasilkan dari suatu persoalan

ke Knapsack (ransel). Setelah itu masukkan barang kedua terbaik dan seterusnya hingga Knapsack (ransel) terisi dengan sebanyak-banyaknya barang-barang ini.

Algoritma penyelesaian masalah Knapsack (ransel) dengan metode Branch and Bound adalah sebagai berikut.

1.         Membuat formulasi masalah berdasarkan peringkat variabel.

2.         Melakukan iterasi dengan ketentuan :

a.         Jika nilai variabel berupa pecahan, dilakukan pencabangan iterasi

b.        Jika nilai variabel berupa bilangan bulat, tidak dilakukan pencabangan iterasi dan iterasi tersebut menjadi calon solusi

c.         Jika nilai variabel disubstitusikan ke fungsi kendala, dan melebihi kapasitas pada fungsi kendala maka tidak dilakukan pencabangan dan iterasi tersebut menjadi solusi tidak fisibel.

3.         Menganalisa kemungkinan dari semua calon solusi dan menentukan solusi optimal yang sesuai dengan ketentuan pada fungsi kendala dan fungsi tujuan.

BAB III

PEMBAHASAN

A.    Formulasi Masalah

Kebutuhan seorang mahasiswi dalam 1 bulan beserta harga dan rincian anggaran biayanya  adalah sebagai berikut :

Kebutuhan	Harga Normal	Kemampuan
Makan	Rp 540.000,00	Rp 450.000,00
Bensin	Rp   60.000,00	Rp   45.000,00
Pembalut	Rp   15.000,00	Rp   12.000,00
Make up	Rp 200.000,00	Rp 150.000,00
Alat Mandi	Rp   30.000,00	Rp   20.000,00
Detergen	Rp   30.000,00	Rp   18.000,00
Pulsa	Rp 100.000,00	Rp   70.000,00
Fotocopy/Print	Rp   20.000,00	Rp   10.000,00
Listrik	Rp   25.000,00	Rp   25.000,00
Jumlah	Rp 1.020.000,00	Rp 800.000,00

Berdasarkan tabel rincian biaya di atas, diketahui bahwa harga semua kebutuhan tiap bulannya adalah Rp 1.020.000,00, sedangkan uang saku yang dimiliki oleh mahasiswi tersebut pada setiap bulannya hanya sebesar Rp 800.000,00. Bagaimana cara memaksimalkan utilitas uang saku tersebut agar dapat memenuhi kebutuhan mahasiswi tersebut setiap bulan?

B.     Penyelesaian

Variabel Keputusan

 = Makan

 = Bensin

 = Pembalut

 = Make Up

 = Alat Mandi

 = Detergen

 = Pulsa

 = Fotocopy/print

 = Listrik         

Fungsi Tujuan

Memaksimalkan

Kendala

Pembatas Tanda

Kebutuhan		Peringkat	Variable Baru
Makan	450/540 = 0.833	2
Bensin	45/60 = 0.75	4
Pembalut	12/15 = 0.8	3
Make Up	150/200 = 0.75	5
Alat Mandi	20/30 = 0.667	7
Detergen	18/30 = 0.6	8
Pulsa	70/100 = 0.7	6
Fotocopy/print	10/20 = 0.5	9
Listrik	25/25 = 1	1

Untuk mempermudah dalam perhitungan, kita dapat mengubah variable keputusan sesuai dengan peringkat di atas menjadi variable baru, yaitu sebagai berikut :

 = Listrik

 = Makan

 = Pembalut

 = Bensin

 = Make Up

 = Pulsa

 = Alat Mandi

 = Detergen

 = Fotocopy/print

Fungsi tujuan menjadi :

Memaksimalkan

Dengan kendala

Penyelesaian masalah tersebut dapat  diselesaikan dengan menggunakan metode Knapsack (terlampir).

BAB IV

PENUTUP

A.    Kesimpulan

Metode Knapsack(ransel) dapat diaplikasikan untuk menentukankebutuhan mana yang dapat dipenuhi dengan memperhatikan jumlah anggaran yang dimiliki. Pada metode Knapsack terdapat 3 tahapan, yaitu :

1.        Menentukan peringkat (c_i / a_i)

2.        Menentukan variable, kendala dan fungsi tujuan baru

3.        Pencabangan

Pada pembahasan sebelumnya, diperoleh tabel solusi optimal, yaitu sebagai berikut:

Calon Solusi	Biaya (ribu rupiah)	Nilai Variabel Keputusan	Keterangan  (Kebutuhan yang terpenuhi)
1	640	1,1,1,1,0,1,1,1,0	Listrik, makan, pembalut, bensin, pulsa, alat mandi dan detergen
2	647	1,1,1,0,1,0,0,0,1	Listrik, makan, pembalut, make up dan fotocopy/ print
3	643	1,1,0,0,1,0,0,1,0	Listrik, makan, make up dan detergen
4	203	1,0,0,0,1,0,0,1,1	Listrik, make up, detergen dan fotocopy/ print
5	350	1,0,1,1,1,1,1,1,1	Listrik, pembalut, bensin, make up, pulsa, alat mandi, detergen dan fotocopy/ print
6	645	0,1,0,1,1,0,0,0,0	Makan, bensin dan make up
7	305	1,0,1,0,1,1,1,1,1	Listrik, pembalut, make up, pulsa, alat mandi, detergen dan fotocopy/ print
8	645	1,1,0,0,1,0,1,0,0	Listrik, makan, make up dan alat mandi
9	223	1,0,0,0,1,0,1,1,1	Listrik, make up, alat mandi, detergen dan fotocopy/ print
10	632	0,1,1,0,1,0,1,0,0	Makan, pembalut, make up dan alat mandi
11	215	1,0,1,0,1,0,0,1,1	Listrik, pembalut, make up, detergen dan fotocopy/ print
12	628	0,1,0,0,1,0,0,1,1	Makan, make up, detergen dan fotocopy/ print
13	235	1,0,1,0,1,0,1,1,1	Listrik, pembalut, make up, alat mandi, detergen, fotocopy/print

Namun berdasarkan teori pada metode knapsackmaka dipilih calon solusi nomor 2 yaitu kebutuhan yang terpenuhi adalah listrik, makan, pembalut, make up dan fotocopy/ print dengan biaya Rp 647.000,00 karena memiliki nilai fungsi tujuan yang paling maksimal.

B.     Saran

Terdapat 13 calon solusi yang dapat digunakan untuk mengambil keputusan dalam menentukan kebutuhan mana yang dapat dipenuhi. Berdasarkan biaya anggaran dengan uang Rp 800.000,00 masih terdapat sisa sehingga dapat digunakan untuk memenuhi kebutuhan lain yang belum terpenuhi.

DAFTAR PUSTAKA

Irawanto, Bambang, dkk. 2004.  Program Linier. Semarang : Universitas Diponegoro

Kurniawan, Fidianto. 2012. Knapsack Algoritma. http://kurniawan-fidianto2.blogspot.com/2012/01/knapsack-algoritma_29.html. (Diakses pada tanggal 20 Mei 2013).