LAPORAN RENCANA KEGIATAN

LAPORAN RENCANA KEGIATAN

(LRK- INDIVIDU)

KULIAH KERJA NYATA TIM II TAHUN 2016

KELURAHAN/DESA  : GIRIREJO

KECAMATAN            : NGABLAK

KABUPATEN             : MAGELANG

Disusun oleh :

Nama     : Atik Rumariyanti

NIM      : 24010113120003

Jurusan  : Matematika

Fakultas : Sains dan Matematika

           

PUSAT PELAYANAN KULIAH KERJA NYATA (P2KKN)

LEMBAGA PENELITIAN DAN PENGABDIAN KEPADA MASYARAKAT (LPPM)

UNIVERSITAS DIPONEGORO

SEMARANG

2016

I.         PERMASALAHAN

             Penyusunan program kerja ini disesuaikan dengan keadaan masyarakat dan potensi yang ada di Desa Girirejo, Kecamatan Ngablak, Kabupaten Magelang. Oleh karena itu, dilaksanakan survei yang bertujuan untuk pengumpulan informasi dan data-data yang dibutuhkan untuk penyusunan rencana program kegiatan KKN-PPM TIM II TAHUN 2016. Berikut adalah tabel hasil survei:

Tabel 1. Rekapitulasi Identifikasi Permasalahan Tingkat Desa

No.	Permasalahan	Lokasi	Sumber (P/M/D)
1.	Dalam hal pendidikan masih kurang dalam pemahaman pelajaran matematika	Desa Girirejo	M
2.	Masih menganggap pelajaran matematika sebagai pelajaran yang susah dan membosankan.	Desa Girirejo	M
3.	Belum tersedianya informasi kependudukan berupa piramida penduduk Desa Girirejo	Desa Girirejo	P

                Keterangan: P : Perangkat Desa, M : Masyarakat, D : Dinas Instansi Vertikal/Stakeholder

               

II.      PRIORITAS PEMILIHAN PERMASALAHAN

           Berdasarkan permasalahan yang telah ditemukan di Desa Girirejo yang diperoleh dari berbagai sumber, maka alasan pemilihan masalah yang diprioritaskan, antara lain yaitu:

      Tabel 2. Rekapitulasi Prioritas Pemilihan Permasalahan Tingkat Desa

No	Permasalahan	Alasan Pemilihan Program
1.	Masih kurangnya pengetahuan siswa SD mengenai bentuk bangun datar serta bangun ruang dengan Tangram dan cubecraft	Mengenalkan matematika sebagai mata pelajaran yang mudah serta menyenangkan melalui Tangram dan cubecraft
2.	Belum tersedianya informasi kependudukan berupa piramida penduduk Desa Girirejo	Data kependudukan merupakan salah satu data penting dalam perencanaan pembangunan. Sehingga pengolahan data kependudukan beserta informasinya penting untuk diketahui. Salah satunya yakni mengenai piramida penduduk. Dimana dapat diketahui prosentase jumlah penduduk laki-laki dan perempuan dalam suatu wilayah.

III. RENCANA PROGRAM KKN

Berdasarkan prioritas pemilihan permasalahan yang telah ditentukan untuk Desa Girirejo yang diperoleh dari berbagai sumber, maka rencana program KKN yang disusun mempunyai rincian, antara lain yaitu:

Tabel 3. Rincian Program Monodisiplin

No	Nama Program	Bahan dan Alat	Volume	Alokasi Waktu	Sumber Dana
1	Belajar Bangun Datar serta Bangun Ruang dengan Tangram dan Cubecraft untuk siswa SD	●  Laptop ●  Gunting ●  Kertas manila ●  Kertas origami ●  Lem ●  Kertas Cubecraft	35 orang	40 jam	Swadaya Mahasiswa
2	Pembuatan Piramida Penduduk untuk Desa Girirejo	●  LCD ●  Proyektor ●  PPT ●  Laptop	9 orang	40 jam	Swadaya Mahasiswa

Makalah Mengoptimasikan Keuntungan Danusan Menggunakan ILP

MENGOPTIMASI KEUNTUNGAN DANUSAN MENGGUNAKAN INTEGER LINEAR PROGRAMMING DENGAN METODE BRANCH AND BOUND

 

DRAF

Disusun untuk Memenuhi Tugas Kelompok

pada Mata Kuliah Math. Real Problem Solving Semester Empat

yang Diampu oleh Drs. Kartono, M.Si dan Dr. Hj. Sunarsih, M.Si

yang telah dipresentasikan pada 22 Mei 2015

Oleh :

1. Atik Rumariyanti              (24010113120003)

2. Nur Rifdah Lestyorini      (24010113120045)

3. Lathifatul Aulia                 (24010113130051)

4. Uni Nur Cahyowati          (24010113130057)

JURUSAN MATEMATIKA

FAKULTAS SAINS DAN MATEMATIKA

UNIVERSITAS DIPONEGORO

SEMARANG

2015

KATA PENGANTAR

Puji syukur kami panjatkan kepada Allah SWT, atas rahmat-Nya maka kami dapat menyelesaikan penulisan laporan yang berjudul “Mengoptimasi Keuntungan Danusan Menggunakan Integer Linear Programming dengan Metode Branch and Bound ”.

Penulisan laporan ini merupakan salah satu tugas dan persyaratan untuk menyelesaikan tugas mata pelajaran Math. Real Problem Solving di Universitas Diponegoro.

Dalam penulisan draf ini kami menyampaikan ucapan terima kasih yang tak terhingga kepada :

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

2.      Bapak Bambang Irawanto M.Si selaku dosen pembimbing akademik.

3. Rekan-rekan semua yang mengikuti perkuliahan Math. Real Problem Solving.
4. Keluarga yang selalu mendukung.
5. Semua pihak yang ikut membantu penyusunan laporan “Mengoptimasi Keuntungan Danusan Menggunakan Integer Linear Programming dengan Metode Branch and Bound”

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

Semarang, 8 Mei 2015

                                                                                                          Penulis

I.  TUJUAN

1.1 Untuk memenuhi tugas kelompok mata kuliah math. real problem solving pada semester empat

1.2 Menemukan real world problems dengan membawanya kedalam bentuk matematik

1.3 Menyelesaikan real world problems dengan menggunakan metode Branch and Bound pada matakuliah integer linear programming

1.4 Memberikan informasi bahwa metode-metode dalam ilmu Matematika dapat digunakan untuk memecahkan real world problems

II. ANALISIS SITUASI

Kegiatan yang dilakukan mahasiswa di kampus tidak hanya kuliah saja tetapi juga berorganisasi. Terdapat banyak organisasi yang ada di kampus mulai dari tingkat universitas sampai tingkat jurusan. Setiap organisasi didirikan dengan tujuan untuk menampung minat serta bakat mahasiswa pada bidang-bidang tertentu untuk dikembangkan. Tentunya setiap organisasi mempunyai program-program kerja yang biasa disebut dengan proker, yang mana akan melahirkan acara-acara besar. Untuk merealisasikan acara-acara tersebut tentunya membutuhkan dana lumayan besar sehingga mahasiswa perlu mendapatkan dana dengan mengajukan proposal ke fakultas atau rektor bahkan sponsor-sponsor. Selain itu, mahasiswa juga kerap mencari dana sendiri yang biasa disebut dengan dana usaha (danus). Dana usaha ini biasanya menjual makanan, baju bekas (ngawul), pin, gantungan kunci, stiker dan lain-lain. Namun, yang paling cepat terjual dari sekian banyak jenis danusan adalah dengan menjual makanan atau jajanan. Dengan bermodal uang sekitar Rp 50.000,00 dan satu buah box, terkadang dalam seminggu mahasiswa dapat mendapatkan keuntungan yang lumayan besar sampai ratusan ribu. Satu box jajanan biasanya terdapat 5 jenis makanan yang berbeda-beda dengan biaya yang berbeda-beda pula, namun dengan harga jual yang sama. Masing-masing jenis makanan mempunyai nilai permintaan yang berbeda-beda dilihat dari banyaknya makanan yang diminati oleh konsumen, sehingga si penjual danus tersebut membatasi banyaknya setiap jajanan yang akan dijual untuk memenuhi permintaan para pelanggannya.

Kepengurusan dalam Himpunan Mahasiswa pada periode baru ini akan melaksanakan suatu proker. Proker tersebut memerlukan dana. Oleh karena itu, mahasiswa melakukan upaya dana usaha untuk memenuhi kebutuhan dana tersebut. Dana usaha yang akan mahasiswa lakukan adalah dengan menjual jajanan. Dengan memperhatikan minat konsumen, jenis jajanan danus yang akan dijual yaitu tahu bakso, risoles ayam, risoles sayur, martabak dan donat. Jajanan danus tersebut akan ditempatkan dalam box yang berukuran 23 x 23 x 7. Jika box hanya diisi dengan satu jenis jajanan, kapasitas maksimal untuk tahu bakso, risoles ayam, risoles sayur, martabak dan donat berturut-turut adalah 50 buah, 70 buah, 50 buah, 70 buah, dan 35 buah. Data tersebut diperoleh dari percobaan secara langsung oleh kelompok kami. Satu buah jajanan danus akan dijual kepada mahasiswa sebesar Rp1.500,00. Berikut data harga beli tiap jenis jajanan danus per buah dan permintaan minimal tiap jenis jajanan danus per harinya.

Jenis jajanan	Harga beli per buah (Rp)	Permintaan minimal per hari
Tahu bakso	1200	15
Risoles ayam	1200	7
Risoles sayur	1000	6
Martabak	1000	7
Donat	1000	5

Jika proker tersebut akan dilaksanakan 1 bulan terhitung setelah danus hari pertama dan 1 bulan diasumsikan terdapat 4 minggu, berapa keuntungan maksimum yang dapat diperoreh dari danus tersebut jika danus hanya dijual pada hari aktif kuliah saja (dari Senin sampai Jumat) serta modal awal setiap harinya diasumsikan sama yaitu Rp 50.000,00?

III. RUMUSAN MASALAH

Dari analisis situasi diatas, dapat dirumuskan masalah yaitu bagaimana memaksimalkan keuntungan dengan modal yang minimal dan kendala sebagai berikut:

1.      Keterbatasan box

2.      Harus ada 5 jenis jajan yang dijual

3.      Permintaan setiap jenis jajanan

IV. DASAR TEORI

4.1 Metode Simplex

Metode simpleks merupakan prosedur aljabar yang bersifat iteratif, dimana pada setiap iterasi mencari penyelesaian suatu sistem persamaan ini kemudian digunakan menguji keoptimalan dari linear programming  yang akan diselesaikan. Formulasi model secara matematis masalah  linear programming  bentuk baku memaksimumkan/meninimumkan Z = C_j X_j kendala

               i = 1, 2, ... m dan j = 1, 2, ... n,

secara umum bentuk baku (standar) model memenuhi sifat-sifat sebagai berikut:

1. Semua kendala merupakan bentuk persamaan,

2.  Harga ruas kanan hendaklah harga non negatif,

3.  Semua nilai variabel keputusan adalah non negatif,

4.  Fungsi tujuan berbentuk maksimum atau minimum,

     Pada umumnya persoalan linear programming dengan dua variabel keputusan dapat diselesaikan dengan metode grafik, tetapi untuk menyelesaikan persoalan yang memiliki variabel keputusan yang lebih besar atau sama dengan dua digunakan simplex. Pada kenyataannya masalah model matematis pada linear programming  tidak selalu berbentuk baku, oleh karena itu diberikan beberapa cara untuk membwa model kedalam bentuk baku (standar).

Adapun model umum  linear programming  sebagai berikut

Sumber daya	Pemakaian sumber daya per unit kegiatan        1          2           3         ....           n	Jumlah sumber daya yang tersedia
1 2 . . . M	a11          a12           a13          .....              a1n         a21           a22          a23           .....              a2n          .            .            .   .....          .        .            .            .   .....          .         .           .            .   .....          .       am1          am2         am3   ....         amn	b1 b1 . . . bm
∆Z / Unit kegiatan tingkat kegiatan	C1        C2               C3           .....                     Cn        X1         X2             X3          .....                     Xn

               4.1.1 Perubahan ke Bentuk Baku

Metode simplex dibuat untuk menyelesaikan linear programming baku. Metode ini digunakan untuk menyelesaikan linear programming yang umum, tetapi harus diturunkan terlebih dahulu menjadi bentuk baku dengan cara :

1. Jika pada kendala berbentuk ≤ maka persamaan kendala diubah dengan menambah variabel kelonggaran (slack variable) pada ruas kiri misal sebuah kendala :

     X₁ + 2X₂ ≤ 6 diubah menjadi X₁ + 2X₂ + S₁ = 6, S₁ ≥ 0

2. Jika kendala berbentuk  ≥ maka persamaan kendala diubah dengan mengurangkan dengan variabel surplus pada ruas kiri.

3. Jika ruas kanan berharga negatif, diubah menjadi positif dengan mengalikan kedua arus dengan (-1)

4. Jika terdapat variabel keputusan tak terbatas (X_i unrestriced) maka X_i  dapat diubah bentuk dua variabel non negatif dengan subtitusi

       X_i = X_i’ - X_i” , X_i’ , X_i” ≥ 0,

            4.1.2 Prosedur Metode Simplex

Prosedur metode simplex secara keseluruhan terdiri dari 3 langkah/tahapan yaitu :

1. Langkah awal (step 1)    : persiapan untuk memulai iterasi

2. Langkah iterasi (step 2)  : proses melakukan iterasi

3. Uji optimalitas (step 3)   : suatu langkah dimana untuk menentukan apakah hasil yang digunakan telah tercapai atau belum, jika pada langkah ini hasil belum optimal maka proses kembali ke langkah iterasi sampai hasil optimal

Adapun penjelasan langkah-langkah pada metode simplex yaitu

1. Langkah awal

     Langkah ini adalah langkah untuk mempersiapkan iterasi, yaitu dengan membentuk model matematis kedalam bentuk baku dengan menambahkan variabel kelonggaran (slack), sehingga diperoleh variabel basis. Pada fungsi tujuan koefisien variabel kelonggaran sama dengan nol dan dipindahkan/ pisahkan variabel-variabel disebelah kiri dan konstanta di sebelah kanan.

2. Langkah iterasi

     Bagian 1 : bagian menentukan Entering Variable (EV) / variabel yang masuk menjadi basis dengan cara mencari variabel non basis pada persamaan (0) harga negatif terbesar untuk masalah maksimum dan harga positif terbesar untuk masalah minimum.

     Bagian 2 : menentukan Leaving Variable (LP) / variabel dasar yang akan keluar dengan cara membandingkan harga ruas kanan (b_i) dengan harga koefisien pada variabel yang terpilih menjadi basis baru pada setiap persamaan ke-i (i = 1, 2, ... ,m) dipilih yang paling minimum, atau

  selanjutnya perpotongan antara Entering Variable dengan Leaving Variable disebut elemen pivot.

Bagian 3 : menentukan solusi baru dengan melakukan operasi eliminasi Gauss, dengan menjadikan setiap harga pada variabel baru menjadi nol dan elemen pivot menjadi 1.

  3. Langkah optimal

Pada langkah ini periksa persamaan (0) / (Z) apakah pada setiap variabel non basis berharga ≥ 0 (masalah maksimal) dan ≤ 0 (untuk masalah minimal), jika ini terpenuhi maka penyelesaian sudah optimal dan jika belum maka lanjutkan kelangkah iterasi.

4.2 BnB (Branch and Bound )

          Metode Branch and Bound (cabang dan batas) adalah salah satu metode  yang dianggap efisien dan efekif untuk mencari solusi bilangan bulat yang optimal dari persoalan linear programming, yang selanjutnya menjadi salah satu metode untuk menyelesaikan persoalan integer linear programming. Metode ini merupakan suatu pendekatan solusi yang layak digunakan dalam menyelesaikan permasalahan integer linear programming dengan membagi daerah solusi yang layak menjadi subset yang lebih kecil, untuk selanjutnya dilakukan evaluasi secara sistematis terhadap subset tersebut sampai solusi yang terbaik ditemukan.

Metode Branch and  Bound digunakan bersama-sama dengan metode simplex. Metode Branch and  Bound  ini menggunakan suatu diagram yang terdiri dari node dan cabang (branch) sebagai suatu kerangka dalam proses pemerolehan solusi optimal. Masing-masing node memuat solusi program linier relaksasi sesuai dengan fungsi tujuan dan batasannya. Node pertama akan memuat solusi program linier relaksasi dari persoalan yang diberikan. Node kedua, ketiga, keempat, dan seterusnya memuat solusi program linier relaksasi dari persoalan yang diberikan ditambah dengan batasan yang terdapat pada masing-masing cabangnya. Adapun langkah-langkah penggunaan metode  Branch and Bound adalah sebagai berikut :

1.    Metode ini diawali dengan metode simplex sampai terdapat penyelesaian optimal

2.    Solusi yang dihasilkan pada langkah a dinyatakan sebagai batas atas (upper bound ) dan pembulatan ke bawah sebagai batas bawah (lower bound ) pada node 1

3.    Pilihlah variabel dengan pecahan yang terbesar untuk pencabangan (branch). Ciptakan dua batasan baru untuk variabel ini. Hasilnya adalah sebuah batasan ≥ dan sebuah batasan ≤

4.    Ciptakan dua node baru, satu dengan batasan ≤ dan satu dengan batasan ≥

5.    Selesaikan model program linier relaksasi dengan batasan baru yang ditambahkan pada tiap node

6.    Solusi simpleks adalah merupakan batas atas pada tiap node, dan solusi bilangan bulat maksimum yang ada (pada node mana saja) adalah merupakan batas bawah

7.    Jika proses ini menghasilkan solusi bilangan bulat fisibel dengan nilai batas atas pada akhir node mana saja, maka solusi bilangan bulat optimal telah tercapai. Jika tidak muncul solusi bilangan bulat fisibel, lakukan pencabangan dari node dengan batas atas terbesar

V. ANALISIS PEMBAHASAN

5.1 Identifikasi Variabel

Diketahui jenis-jenis jajanan sebagai berikut:

x₁ : Tahu Bakso

x₂ : Risoles Ayam

x₃ : Risoles Sayur

x₄ : Martabak

x₅ : Donat

5.2 Pemodelan

Diberikan tabel berikut :

Jenis jajanan	Harga beli per buah (Rp)	Permintaan minimal per hari	Keuntungan (Rp)
Tahu bakso	1200	15	300
Risoles ayam	1200	7	300
Risoles sayur	1000	6	500
Martabak	1000	7	500
Donat	1000	5	500

a. Fungsi tujuan:

Memaksimalkan keuntungan

 Z = 300x₁ + 300x₂ + 500x₃ + 500x₄ + 500x₅

b. Kendala

Harga beli   : 1200x₁ + 1200x₂ + 1000x₃ + 1000x₄ + 1000x₅  ≤ 50000

Kapasitas box : x₁ ≤ 50

x₂ ≤ 70

x₃ ≤ 50

x₄ ≤ 70

x₅ ≤ 35

     Permintaan : x₁ ≥ 15

  x₂ ≥ 7

  x₃ ≥ 6

  x₄ ≥ 7

  x₅ ≥ 5

c. Pembatas tanda x₁, x_2, x_3, x_4, x_{5  =}  integer

Perhatikan!

          Z = (300x₁ + 300x₂+ 500x₃ + 500x₄ + 500x₅)

Berhubung hari efektif kuliah mahasiswa dalam satu bulan ada 20 hari, maka fungsi tujuan Z akan dikalikan dengan 20 hari sehingga menjadi

          Z = (300x₁ + 300x₂+ 500x₃ + 500x₄ + 500x₅) X 20

 = 6000x₁ + 6000x₂ + 10000x₃ + 10000x₄ + 10000x₅

                         = 6000 (x₁ + x₂ )+ 10000 (x₃ + x₄ + x₅ )

Harga beli :    1200x₁ + 1200x₂ + 1000x₃ + 1000x₄ + 1000x₅

                        = 1200 (x₁ + x₂ ) + 1000 (x₃ + x₄ + x₅ )

Untuk memudahkan perhitungan, maka dilakukan permisalan yaitu sebagai berikut

                        x₁ + x₂ = y₁

                            x₃ + x₄ + x₅ = y₂

sehingga formulasi berubah menjadi

a. Variabel keputusan   y₁ = x₁ + x₂

                                                 y₂ = x₃ + x₄ + x₅

b. Fungsi tujuan              Z = 6000 y₁ + 1000 y₂

c. Kendala

Harga beli   :           1200 y₁ + 1000 y₂  ≤ 50000

Kapasitas    :           y₁ ≤ 120

                                                y₂ ≤ 155

Permintaan  :           y₁ ≥ 22

                                y₂ ≥ 18

d. Pembatas tanda

                        y₁, y_{2  =}  integer

5.3 Metode

Dengan menggunakan alat bantu softwere optimasi yaitu POMWIN maka didapatkan perhitungan sebagai berikut

Setelah memasukkan formulasi seperti gambar di atas, maka didapat solusi seperti gambar di bawah

Karena solusi dari y₂ adalah pecahan, maka solusi akan dicari dengan mengunakan metode Branch and Bound. Dengan menggunakan alat bantu POMWIN  maka perhitungan solusinya dapat dituliskan dengan langkah-langkah sebagai berikut:

Langkah 1

Menghitung solusi optimal dari metode simpleks atau program linier relaksasi. Diperoleh nilai y₁ = 22 dan y₂ = 23,6. Dengan nilai fungsi tujuan Z = 368000

Langkah 2

Menetapkan batas atas, batas bawah dan node awal. Node awal merupakan penyelesaian program linier relaksasi (sub masalah 1). Batas atas = 368000 sementara itu, batas bawah merupakan nilai Z untuk pembulatan solusi program linier relaksasi batas bawah = 362000

Langkah 3

Percabangan pada node-1 dengan penambahan kendala y₂ ≤ 23 dan y₂ ≥ 24.

Sub masalah 2 = sub masalah 1 + kendala y₁ ≤ 23

Diperoleh nilai y₁ = 22,5 dan y₂ = 23 dengan nilai fungsi tujuan Z = 365000

Sub masalah 3 = sub masalah 1 + kendala y₂ ≥ 24

Solusi simpleks sub masalah 3 tidak fisible, sehingga pecabangan  dilakukan pada sub masalah 2.

Langkah 4

 Pencabangan pada node-2 dengan penambahan y₁ ≤ 22 dan y₁ ≥ 23

Sub masalah 4 = sub masalah 2 + kendala y₁ ≤  22

Solusi simpleks untuk sub masalah 4 sudah integer yaitu y₁ = 22 dan

y₂ = 23 dengan Z = 362000 sehingga menjadi calon solusi 1

Sub masalah 5 = sub masalah 2 + kendala y₁ ≥ 23

Diperoleh nilai y₁ = 23 dan y₂ = 22,4. Dengan nilai Z = 362000

Karena sub masalah 4 sudah fisible, sehingga percabangan dilakukan pada sub masalah 5.

Langkah 5

Percabangan pada node-3 dengan penambahan kendala  y₂ ≤ 22

Dan y₂ ≥ 23

Sub masalah 6 = sub masalah + kendala y₂ ≥ 23

Solusi simpleks sub masalah 6  tidak fisible, sehingga dilanjutkan untuk sub masalah 7.

Sub masalah 7 = sub masalah 5 + kendala y₂ ≤ 22

Diperoleh nilai y₁ = 23,33 dan y₂ = 22 dengan Z = 360000

Karena Z = 360000 < Z dari calon 1. Maka percabangan dihentikan / tidak lebih baik dari calon solusi 1.

Diperoleh solusi optimal integer

Karena dimisalkan   maka

 

Û

dengan mengambil permintaan minimal dan kapasitas maksimal box maka diperoleh interval untuk  dan  sebagai berikut

Dari interval  dan  akan dibuat kombinasi dari  dan  yang memenuhi

Atau dengan cara menggambar interval  dan   serta  ,akan diperoleh daerah fisibel seperti pada grafik berikut :

Dari grafik di atas diperoleh titik fisibel yaitu

( ,  ) = ( 15, 7 )       

Jadi,  = 15 dan  = 7

Untuk permisalan yang kedua yaitu

Û

mengambil permintaan minimal dan kapasitas maksimal box maka diperoleh interval untuk  dan  sebagai berikut

Maka diperoleh interval sebagai berikut

 berubah menjadi  , yaitu maksimal diperoleh dari 23 – {min  = 23-7-5 =11

 berubah menjadi  , yaitu maksimal diperoleh dari 23 – {min  = 23-6-5 =12

 berubah menjadi , yaitu maksimal diperoleh dari 23 – {min  = 23-6-7 =10

Sehingga juga dapat dituliskan sebagai berikut

Dari himpunan dicari kombinasi angka yang memenuhi

 Didapat himpunan fisibel yang integer ( , ,  ) =

( 6, 7, 10 ), ( 7, 7, 9 ), ( 8, 7, 8 ), ( 9, 7, 7 ), ( 10, 7, 6 ), ( 11, 7, 5 ), ( 6, 8, 9 ), ( 7, 8, 8 ), (8, 8, 7 ), ( 9, 8, 6 ), ( 10, 8,5 ), ( 6, 9, 8 ), ( 7, 9, 7), ( 8, 9, 6 ), ( 9, 9, 5 ), ( 6, 10, 7 ), ( 7, 10, 6 ), ( 8, 10, 5 ), ( 6, 11, 6 ), ( 7, 11, 5 ), ( 6, 12, 5 ).

Sehingga keuntungan maksimal dana usaha ( danus ) yang dapat diperoleh adalah

Z = Rp 362.000,00

Dengan 21 cara alternatif untuk pembelian dari masing-masing jenis makanan yaitu

1.      ( , , , ,  ) = ( 15, 7, 6, 7, 10 )

2.      ( , , , ,  ) = ( 15, 7, 6, 8, 9 )

3.      ( , , , ,  ) = ( 15, 7, 6, 9, 8 )

4.      ( , , , ,  ) = ( 15, 7, 6, 10, 7 )

5.      ( , , , ,  ) = ( 15, 7, 6, 11, 6 )

6.      ( , , , ,  ) = ( 15, 7, 6, 12, 5 )

7.      ( , , , ,  ) = ( 15, 7, 7, 7, 9 )

8.      ( , , , ,  ) = ( 15, 7, 7, 8, 8 )

9.      ( , , , ,  ) = ( 15, 7, 7, 9, 7 )

10.  ( , , , ,  ) = ( 15, 7, 7, 10,6 )

11.  ( , , , ,  ) = ( 15, 7, 7, 11, 5 )

12.  ( , , , ,  ) = ( 15, 7, 8, 7, 8 )

13.  ( , , , ,  ) = ( 15, 7, 8, 8, 7 )

14.  ( , , , ,  ) = ( 15, 7, 8, 9, 6 )

15.  ( , , , ,  ) = ( 15, 7, 8, 10, 5 )

16.  ( , , , ,  ) = ( 15, 7, 9, 7, 7 )

17.  ( , , , ,  ) = ( 15, 7, 9, 8, 6 )

18.  ( , , , ,  ) = ( 15, 7, 9, 9, 5 )

19.  ( , , , ,  ) = ( 15, 7, 10, 7, 6 )

20.  ( , , , ,  ) = ( 15, 7, 10, 8, 5 )

21.  ( , , , ,  ) = ( 15, 7, 11, 7, 5 )

Untuk mengecek apakah 21 alternatif cara pembelian danus dapat termuat di box, perlu dilakukan pengecekan kapasitas. Dari data yang ada 1 box dapat memuat 50 tahu bakso ini berarti kapasitas 1 tahu bakso ( ) dalam box adalah . Untuk  1 risoles ayam(  kapasitasnya , 1 risoles sayur (  kapasitasnya , 1 martabak ( ) kapasitasnya , dan 1 donat ( kapasitasnya . Apabila nilai dari c(x) =  dan diperoleh nilai c(x) ≤ 1 maka lima jenis makanan tersebuat termuat dalam satu box.

Berikut  adalah perhitungan c(x) untuk pengecekan kapasitas :

Alternatif ke						c(x)	keterangan
1	15	7	6	7	10	0,905714286	≤ 1
2	15	7	6	8	9	0,891428571	≤ 1
3	15	7	6	9	8	0,877142857	≤ 1
4	15	7	6	10	7	0,862857143	≤ 1
5	15	7	6	11	6	0,848571429	≤ 1
6	15	7	6	12	5	0,834285714	≤ 1
7	15	7	7	7	9	0,897142857	≤ 1
8	15	7	7	8	8	0,882857143	≤ 1
9	15	7	7	9	7	0,868571429	≤ 1
10	15	7	7	10	6	0,854285714	≤ 1
11	15	7	7	11	5	0,84	≤ 1
12	15	7	8	7	8	0,888571429	≤ 1
13	15	7	8	8	7	0,874285714	≤ 1
14	15	7	8	9	6	0,86	≤ 1
15	15	7	8	10	5	0,845714286	≤ 1
16	15	7	9	7	7	0,88	≤ 1
17	15	7	9	8	6	0,865714286	≤ 1
18	15	7	9	9	5	0,851428571	≤ 1
19	15	7	10	7	6	0,871428571	≤ 1
20	15	7	10	8	5	0,857142857	≤ 1
21	15	7	11	7	5	0,862857143	≤ 1

Karena semua alternatif nilai c(x) ≤ 1 maka semua alternatif dapat termuat dalam satu box dan menjadi solusi yang fisibel (solusi yang memenuhi semua kendala, di mana kasus tersebut memiliki kendala pada modal dan tempat/ box). Sehingga lima jenis makanan yang berbeda dapat termuat dalam satu box untuk setiap alternatif cara yang dapat dipilih.

VI. KESIMPULAN

Dari permasalahan di atas dapat diambil kesimpulan bahwa untuk mengoptimalkan keuntungan dari danusan tersebut yaitu banyaknya variasi menjual danusan. Adapun variasi menjual banyaknya kelima jajanan yaitu Tahu Bakso, Risoles Ayam, Risoles Sayur, Martabak, Donat berturut turut sebagai berikut :

( 15, 7, 6, 7, 10 )                 ( 15, 7, 6, 8, 9 )

( 15, 7, 6, 9, 8 )                   ( 15, 7, 6, 10, 7 )

( 15, 7, 6, 11, 6)                  ( 15, 7, 6, 12, 5 )

( 15, 7, 7, 7, 9 )                   ( 15, 7, 7, 8, 8 )

( 15, 7, 7, 9, 7 )                   ( 15, 7, 7, 10,6 )

( 15, 7, 7, 11, 5 )                 ( 15, 7, 8, 7, 8 )

( 15, 7, 8, 8, 7 )                   ( 15, 7, 8, 9, 6 )

( 15, 7, 8, 10, 5 )                 ( 15, 7, 9, 7, 7 )

( 15, 7, 9, 8, 6 )                   ( 15, 7, 9, 9, 5 )

( 15, 7, 10, 7, 6 )                 ( 15, 7, 10, 8, 5 )

( 15, 7, 11, 7, 5 )

DAFTAR PUSTAKA

Nufus, hayatun. 2015.  “Branch and Bound (Program Linier)”. https://www.academia.edu/3330553/Branch_and_Bound_Program_Linier

Irawanto, Bambang dkk. 2004. Buku Ajar Program Linear. Semarang: FSM  UNDIP