integer programming ( quantitative method )

PROGRAM INTEGER disusun olehAndika JanuariantoAndry KurniawanLuqman HakimM.Taufiq IsnainiSeptian Prima Winda Fairunisa

Email :andika.januarianto@gmail.com

Pengantar• Pada program linier, solusi yang dihasilkan bisa berbentuk bilangan bulat dan pecahan• Namun untuk beberapa kasus, solusi dalam bentuk pecahan tidak bisa digunakan karena tidak logis, contoh : Meja dan kursi yang dihasilkan masing-masing 4,35 unit dan 5,5 Unit• Meja dan kursi harus dalam bentuk utuh/bulat dan tidak bisa dalam bentuk pecahan• Oleh karena itu diperlukan solusi “Program Integer ( PI )”• PI merupakan metode untuk menemukan solusi dari banyak permasalahan terkait pencarian nilai optimasi.

Permasalahan PI• Sebuah solusi kadang bisa dibulatkan dengan pendekatan bilangan dan tidak memerlukan PI, • Contoh : X1 = 8000,4 paku, dapat dibulatkan menjadi 8000 paku karena harga paku hanya beberapa rupiah• Jika metode pendekatan bilangan kita gunakan dalam solusi produksi pesawat jet, maka proses pembulatan akan mempengaruhi keuntungan atau biaya sebesar milyaran rupiah• Pada kasus tersebut , kita memerlukan PI untuk mendapatkan solusinya

Klasifikasi PIBerdasarkan banyaknya variable keputusan yang bernilai bulat:1) Pure Integer Programmingsemua variable keputusan harus bernilai bilangan bulat 2) Mixed Integer Programming (MIP)tidak semua variable keputusan berupa bilangan bulat 3) Binary Integer Programming (BIP)semua variable keputusan memiliki nilai berupa bilangan biner (0 atau 1)

Contoh Masalah PIPermasalahan yang mengharuskan variabel keputusan bernilai integer diantaranya adalah Investasi Multiperiode Budgeting Routing Knapsack Scheduling Mixed Product AssignmentDll…

Bentuk Umum PISecara umum masalah PI dapat dirumuskan dalam bentuk : Maks/min : Z = C1X1+C2X2+….+CnXn n aij Xj ( , ≥ ) bi ij=1 untuk : i = 1,2,3…, m j = 1,2,3,…,n X1,X2,…,Xn 0

Fungsi Tujuan

Kendala

Variabel Keptusan

Catatan :- Operator matematiika disesuaikan dengan fungsi tujuan, jika tujuan ingin mencari nilai maksimal maka menggunakan ≤, jika tujuan ingin mencari nilai minimum maka menggunakan ≥

Studi Kasus PIPemilik toko jual Beli mesin merencanakan untuk mengadakan

perluasan dengan membeli beberapa mesin baru yaitu mesin

cetak dan mesin potong kertas. Pemilik memperkirakan bahwa

setiap mesin cetak akan menaikkan keuntungan sebesar $100

per hari dan tiap mesin potong menaikkan keuntungan $150 per

hari. Banyaknya mesin yang dapt dibeli terbatas dengan tempat

dan biaya. Pemilik ingin mengetahui berapa banyak mesin yang

harus dibeli agar memperoleh keuntungan maksimum ?

Studi Kasus PIMarket Data :

Goal : berapa banyak mesin yang harus dibeli oleh pemilik toko agar memperoleh keuntungan maksimum ?

Studi Kasus PIModel Program LinierMaksimalkan Z = 100x1 + 150x2Dengan kendala :8.000x1 + 4.000x2 ≤ 40.00015x1 + 30x2 ≤ 200x1,x2 ≥ 0Garis Kendala 1 memotong X1 = 5 dan X2 = 10Garis kendala 2 memotong X1 = 13,3 dan X2 = 6,7

Studi Kasus PISolusi Grafis

8.000x1 + 4.000x2 ≤ 40.000

15x1 + 30x2 ≤ 200= Possible Integer solution

Studi Kasus PIModel Program integerMaksimalkan Z = 100x1 + 150x2Dengan kendala :8.000x1 + 4.000x2 ≤ 40.00015x1 + 30x2 ≤ 200x1,x2 ≥ 0 dan IntegerGaris Kendala 1 memotong X1 = 5 dan X2 = 10Garis kendala 2 memotong X1 = 13,3 dan X2 = 6,7

Studi Kasus PISolusi Integer Garis Selidik

= Possible Integer solution

Studi Kasus PISolusi Titik Terdekat

= Possible Integer solution

Catatan Tambahan PIUntuk mencegah ketidak layakan, nilai solusi dalam masalah minimisasi harus dibulatkan ke atas, sedang dalam masalah maksimisasi dibulatkan ke bawah.

Jawaban Kasus

Jadi Untuk mendapatkan keuntungan Maksimum sebesar $1000, maka pemilik toko membeli 1 Mesin Pencetak dan 6 Mesin Potong Kertas

Referensi[1.] Anonymus, IntegerProgrammingExtendedIntro,Website,[Online] http://www.ohio.edu/people/melkonia/math3050/slides/IPextendedintro.ppt,2013

[2.] Nadia Rahmatul Ummah,Nadia Ummah Slide, SlideShare Website, [Online] http://www.slideshare.net/NadiaUmmah/4-program-integer,2012

[3.] Widya Kusumaningdyah ST.,MT, Widhadyah.Lecture.ub.ac.id[Online]http://widhadyah.lecture.ub.ac.id/files/2012/11/Materi-9_INTEGER-PROGRAMMING-CUTTING-PLANE-ALG.pdf,2012

Q & A