INTEGER PROGRAMMING Rudi Susanto, M.Si
1
Pendahuluan • Pemecahan dgn Linier Programing menghasilkan nilai variabel yg biasanya berupa pecahan, padahal banyak masalah memerlukan hasil yg bulat. • Misal lokasi fasilitas, Pilihan Investasi, Production planning dll. • Misal hasil optimal X1 = 6,67, X2 = 15,73. Kalau dibulatkan dgn 7 dan 16 apakah tidak melanggar kendala/ sumberdaya yg ada? • Maka diperlukan hasil optimalnya angka utuh (integer), dan kendala tetap diikuti. 2
Integer Programming • Definisi :
–Suatu model matematis dari Integer Programming adalah Program linier dengan penambahan batasan bahwa beberapa atau semua variabel harus bernilai integer. .
Kapan Model Integer Diperlukan ? • • • •
Produk atau bahan baku tidak dapat dibagi. Batasan Logikal : \if A then B"; \A or B" Biaya tetap. Merupakan bentuk kombinasi (sequencing, allocation) • Dalam keputusan membeli, investasi, sewa atau lainnya.
Tipe Dari Integer Programming 1. Pure IP - Semua variable adalah integers. 2. Mixed IP - Beberapa variable adalah integers. 3. 0-1 IP – Semua variable harus sama dengan 0 atau 1.
LP optimal Vs IP optimal – IP optimal tidak lebih baik dari pada LP optimal, kenapa ?
5 4 3
2
LP Optimal IP Optimal
1
0
1
2
3
Penyelesaian Integer Programming • Branch and Bound – Cara yang effektif untuk mendapatkan solusi integer. – Tahap demi tahap dengan menggambarkan cabang pada solusi yang akan didapatkan nilai integernya.
• Grafik, • Komputer
Contoh Tipe Integer Programming Max z = 3x1 + 2x2 st 2x1 + x2
<= 4 (1)
x1 + 3x2
<= 5 (2)
x1, x2
>= 0 & Integer (3)
Solusi Grafis X2
Pure IP : ditambah batasan X1, X2 integer
Mixed IP : ditambah batasan X1 atau X2 integer 0-1 IP : ditambah batasan X1, X2 = 0 atau 1
X1
Solusi Grafis Pure IP – Penambahan batasan x1, x2 integer – Daerah feasible (0,0), (0,1), (1,0), (1,1), (2,0)
Mixed IP – Penambahan batasan x2 integer – Daerah feasible x2 = 0 and x1 <= 2;
x2 = 1 and x1 <= 3/2
0-1 IP – Penambahan batasan x1, x2 = 0 atau 1 – Daerah feasible (0,0), (0,1), (1,0), (1,1)
Cara Menyelesaikan Permasalahan Integer Programming
• Max z = 4x1 + 5x2 • s.t. 2x1 + x2 ≤ 5 (1) 2x1 + 3x2 ≤ 5 (2) x1 ≥0 (3) x2 ≥ 0 (4) x1 dan x2 = integer
Cara Menyelesaikan Permasalahan Integer Programming X2
X1
Cara Menyelesaikan Permasalahan Integer Programming Nilai optimal dari LP adalah (2.5,0) dengan z =10 – Dibulatkan keatas : (3,0) menjadi infeasible. – Dibulatkan kebawah : (2,0) nilai z =8. Apakah nilai tersebut optimal untuk IP?
Bila dibutuhkan nilai x1 and x2 adalah integer. – Daerah feasibel menjadi: (0,0), (0,1), (1,0),(1,1), (2,0) – Nilai optimal IP adalah (1,1) dengan z =9.
Contoh 1: Formulasi masalah sbb: • Fungsi tujuan: Maksimum Z = 2X1 + 5X2 • Kendala-kendala: (1) 3X1 + 6X2 < 16 (2) X1, X2 > 0 Kalau diselesaikan dgn metoda grafik sbb:
14
• X2 •
• •
B (0, 2,67) Z = 13,33
A(5,33, 0) Z = 10,67 X1 15
Hasil optimal: • Dgn LP di titik B, memiliki nilai variabel pecahan (noninteger) • Untuk membuat integer harus ditambah kendala X2 = 2 • Jangan dijadikan 3 sebab akan melanggar kendala • X1 juga harus integer, diberi kendala X1 = 1 • Hasil integer-nya sbb: 16
Grafik untuk integer programming • X2 • • • • •
B (0, 2,67) Z = 13,33
2
C 0
1
A(5,33, 0) X1 17
Hasil optimal integer programming: • Untuk membuat nilai X2 integer, maka harus dijadikan 2, kalau 3 melanggar kendala • X1 juga dapat menjadi 1, lihat gambar! • Maka hasil optimal di titik C: X1 = 1, X2 = 2, Z = 12
18
Latihan Soal! • F Tujuan: Maks. Z = 7X1 + 6X2 • Kendala-kendala: (1) 2X1 + 3X2 < 12 (2) 6X1 + 5X2 < 30 (3) X1, X2 > 0
19
Grafik: X2
6
4 (3,75, 0,5) Z = 35,25 (5, 0) Z = 35 6 X1 20
Alternatif titik: X1
X2
Z
0
4
24
1
3
25
2
2
26
3
2
33
4
1
34
5
0
35 Optimal
21
Latihan Max z = 5 x1 + 4 x2 • St x 1 + x2 <= 5 10 x1 + 6 x2 <= 45 x1, x2 >= 0 x1, x2 adalah integer
Solusi
Contoh Model Total Integer •
Pemilik Toko Jual Beli mesin merencanakan untuk mengadakan perluasan dengan membeli beberapa mesin baru-mesin pencetak dan mesin bubut. Pemilik mengestimasikan bahwa tiap mesin pencetak akan menaikkan keuntungan sebesar $100 per hari dan tiap mesin bubut akan menaikkan keuntungan sebesar $150 per hari. Banyaknya mesin yang dapat dibeli dibatasi dengan biaya mesin dan tersedianya ruang dalam toko. Harga beli mesin dan luas tempat sbb :
Mesin
Luas Tempat (ft2)
Harga Beli ($)
Pencetak Bubut
15 30
8.000 4.000
Contoh Model Total Integer • Anggaran pembelian mesin sebesar $40.000 sedangkan tempat yang tersedia seluas 200 feet persegi. Pemilik ingin mengetahui beberapa banyak tiap jenis mesin dapat dibeli untuk memaksimalkan kenaikan keuntungan per hari. • Maksimalkan Z = 100 x1 + 150 x2 Batasan 8.000 x1 + 4.000 x2 ≤ 40.000 15 x1 + 30 x2 ≤ 200 ft2 x1 , x 2 ≥ 0 di mana x1 = jumlah mesin pencetak x2 = jumlah mesin bubut
Contoh Model Integer 0-1 •
Suatu dewan kota harus memutuskan fasilitas rekreasi yang perlu didirikan di kota tersebut. Empat fasilitas rekreasi yang telah diusulkan-sebuah kolam renang, sebuah lapangan tenis, sebuah lapangan atletik, dan sebuah gelanggang olahraga. Dewan berkeinginan mendirikan fasilitasfasilitas yang dapat memaksimalkan penggunaan harian yang diharapkan oleh penduduk setempat dengan biaya dan lahan yang terbatas. Penggunaan harian sbb:
Fasilitas Rekreasi Kolam renang Lapangan tenis Lapangan atletik Gelanggang olah raga
Penggunaan yang Diharapkan (orang/hari) 300 90 400 150
Biaya ($) 35.000 10.000 25.000 90.000
Lahan yang Diperlukan (acre) 4 2 7 3
Contoh Model Integer 0-1 • Kota menyediakan anggaran sebesar $120.000 dan lahan seluas 12 acre. Karena lahan untuk kolam renang dan lapangan tenis berada di daerah yang sama maka hanya akan didirikan satu dari dua fasilitas rekreasi ini.
Formulasi matematiknya?
Contoh Model Integer Campuran • Seorang pengusaha memiliki kelebihan uang $250.000 dan akandi investasikan pada 3 alternatif, yaitu : kondominium, tanah, danobligasi. Dia ingin menginvestasikan uangnya dengan tujuanpengembalian terbesar diperoleh pada akhir tahun.Data jenis investasi:
Formulasi matematiknya?
Terima Kasih
