PROGRAMA INTEGER
10/31/2012
1
Programa linier integer (integer linear programming/ILP) pada intinya berkaitan dengan program-program linier dimana beberapa atau semua variabel memiliki nilai-nilai integer (bulat) atau diskrit. Sebuah ILP dikatakan bersifat campuran atau murni bergantung pada apakah beberapa atau semua variabel tersebut dibatasi pada nilai-nilai integer.
Kondisi nyata di lapangan justru adalah dalam bentuk ini. Kita hanya berbicara jumlah kursi sebagai kesatuan (6 atau 25 buah, tidak berupa pecahan 6,25 atau 25,8 buah). Teknik yang dapat digunakan untuk menyelesaikan program integer salah satunya adalah dengan metode Branch & Bound : (1) Branch-ing (atau pencabangan): untuk mencoba kedua kemungkinan jawaban integer, misal diperoleh X1 = 3,45 ~ berarti kita buatkan 2 pencabangan (program baru dengan tambahan fungsi pembatas baru pada masing-masingnya, yaitu X1 < 3 dan X1 > 4). (2) Bound-ing (atau pembatasan): memilih salah satu cabang yang memberikan jawaban ke arah yang diinginkan (maksimasi atau minimasi). 10/31/2012
2
Pendekatan Pembulatan • Masalah 1 Z Maks = 100 X1 + 90 X2 10 X1 + 7 X2 70 5 X1 + 10 X2 50 X1 , X2 0 • Masalah 2 Z Min = 200 X1 + 400 X2 10 X1 + 25 X2 70 3 X1 + 2 X2 50 X1 , X2 0
10/31/2012
• Masalah 3 Z Maks = 80 X1 + 100 X2 4 X1 + 2 X2 12 X1 + 5 X2 15 X1 , X2 0
3
Perbandingan antara solusi dengan metode simpleks tanpa pembatasan bilangan bulat, pembulatan bilangan bulat terdekat dan solusi integer Masalah
Simpleks biasa
Pembulatan
1
X1 = 5,38 X2 = 2,31 Z = 746,15
2
X1 = 1,82 X1 = 2 X2 = 3,27 X2 = 3 Z = 1.672,73 Tak layak
X1 = 3 atau 5 X2 = 3 atau 2 Z = 1.800
3
X1 = 2,14 X2 = 1,71 Z = 343
X1 = 0 X2 = 3 Z = 300
10/31/2012
X1 = 5 X2 = 2 Z = 680
Integer
X1 = 2 X2 = 2 Tak layak
X1 = 7 X2 = 0 Z = 700
4
Contoh 1 : Program 1
Max S/t
Z =
10X1
+ 8X2
2X1
+ 3X2
< 11
X1 dan X2 > 0 dan integer
• Program (1) adalah PL awal di atas, dicari solusinya (untuk 2 dimensi dapat digunakan cara grafik, untuk yang 3 atau lebih gunakan metode simpleks). • Solusi awal (lihat grafiknya) : X1 = 5,5 ; X2 = 0 ; Z = 55 (solusi integer belum diperoleh karena X1 bernilai pecahan, walaupan Z sudah integer). • Perlu dilakukan pencabangan ~ ada di program (2) dan (3). 10/31/2012
5
Grafik 1
10/31/2012
6
Program
(2) : tambahan pembatas baru X1 < 5 Max S/t
• • • •
Z =
10X1
+ 8X2
2X1 X1
+ 3X2
< 11 < 5
Daerah fisibel adalah (0;0) - (5;0) - (5;0,3) - (3,7;0) Nilai Z maksimal ada di (5;0,3) = 52,4 ~ belum solusi integer - cabangkan ke program (4) dan (5) Pencabangan untuk tambahan pembatas X2 < 0 dan X2 > 1 Hasilnya lihat pada grafik 2
10/31/2012
7
Grafik 2
10/31/2012
8
Program (3) : Tambahan pembatas baru X1 > 6 Max S/t
• •
•
Z =
10X1
+ 8X2
2X1 X1
+ 3X2
< 11 > 6
Program ini tidak fisibel (tidak ada daerah jawaban) Caranya: masukkan pembatas (2) ke (1) ~ nilainya pasti lebih besar dari batas 11 Tidak perlu BOUND-ing, pencabangan sudah pasti harus dari program (2) tercabang ke program 4 dan 5
10/31/2012
9
Program (4) : Tambahan pembatas baru X2 < 0 Max S/t
•
Z =
10X1
+ 8X2
2X1 X1
+ 3X2 X2
< 11 < 5 < 0
Solusinya adalah pada titik (5;0) dengan Z = 50 ~ solusi OPTIMAL
10/31/2012
10
Program (5) : Tambahan pembatas baru X2 > 1 Max S/t
• •
Z =
10X1
+ 8X2
2X1 X1
+ 3X2 X2
< 11 < 5 > 1
Solusinya pada titik (4;1) dengan Z = 48 – masih kalah dengan hasil program 4 Solusi program 4 dan 5 lihat grafik 3
10/31/2012
11
Grafik 3
10/31/2012
12
Bila digambarkan proses pencabangan/pembatasan untuk soal 1 adalah sebagai berikut:
10/31/2012
13
Contoh 2 Program (1) – program asalnya Max S/t
10/31/2012
Z =
3X1
+ 4X2
2X1 2X1
+ X2 + 3X2
< 6 < 9
14
Solusi program (1) ~ dengan grafik adalah :
Daerah fisibel adalah (0;0) - (3;0) - (2,25;1,5) - dan (0;3) daerah yang diarsir Jawab optimal pada (2,25;1,5) dengan Z = 12,75 ~ namun belum integer, baik pada X1 maupun X2 Pencabangan dilakukan pada X2 karena nilai desimal dekat ke SETENGAH (0,5), selanjutnya buatkan program (2) dan (3) dengan tambahan fungsi pembatas baru X2 < 1 dan X2 > 2 10/31/2012
15
Program (2) : Tambahan pembatas baru X2 < 1
Max S/t
10/31/2012
Z =
3X1
+ 4X2
2X1 2X1
+ X2 + 3X2 X2
< 6 < 9 < 1
16
Grafik (baru) – untuk program 2 dan 3
Daerah fisibel adalah (0;0) - (3;0) - (2,5;1) - dan (0;1) Z maksimal ada di (2,5;1) = 11,5
10/31/2012
17
Program (3) : Tambahan pembatas baru X2 > 2 Max S/t
• •
Z =
3X1
+ 4X2
2X1 2X1
+ X2 + 3X2 X2
< 6 < 9 > 2
Daerah fisibel adalah (0;2) - (1,5;2) - dan (0;3) Z maksimal ada di (1,5;2) = 12,5
Dari solusi program (2) dan (3) dilakukan bounding (pembatasan) dengan menetapkan bahwa pencabangan berikutnya adalah dari program (3) ~ buatkan program (4) dan (5) dasar bounding adalah nilai terbesar ~ bila kedua program fisibel Pencabangan baru adalah dengan menambahkan pembatas ke program 3 dengan X1 < 1 dan X1 > 2 10/31/2012
18
Program
(4) : Ada tambahan pembatas baru X1 < 1 Max Z = 3X1 + 4X2 S/t 2X1 + X2 2X1 + 3X2 X2 X1
< < >
Program (5) : Ada tambahan pembatas baru X1 > 2 Max Z = 3X1 + 4X2 S/t 2X1 + X2 2X1 + 3X2 X2 X1
< < > >
6 9 2 1
6 9 2 2
Program (5) tidak fisibel, masukkan pembatas (3) dan (4) ke (2) ~ hasilnya tidak fisibel Dari gambar terlihat tidak ada daerah yang memenuhi syarat 10/31/2012 program 3 dan X1 > 2
19
Grafik (baru): untuk program 4
10/31/2012
Hasil program (4) adalah: Daerah fisibel adalah (0;2) - (1;2) - (1;2,3) dan (0;3) Z maksimal pada (1;2,3) = 12,33 ~ belum integer Lakukan pencabangan baru dari program (4) ini menjadi program (6) dan (7) dengan menambahkan pembatas yang baru X2 < 2 dan X2 > 3 20
Program (6) : Ada tambahan pembatas baru X2 < Max S/t
Z =
3X1
+ 4X2
2X1 2X1
+ X2 + 3X2 X2
X1
X2
< < > <
2
6 9 2 1 2
Solusi program (6) ini ada pada (1;2) dengan Z = 11 10/31/2012
21
Program (7) : Ada tambahan pembatas baru X2 > Max S/t
Z =
3X1
+ 4X2
2X1 2X1
+ X2 + 3X2 X2
X1
X2
< < > >
3 6 9 2 1 3
Solusi untuk program (7) adalah pada (0;3) dengan Z = 12 >> SOLUSI OPTIMAL : integer X1 = 0, X2 = 3 Z = 12 10/31/2012
22
Bila dibuatkan diagran pencabangan dan pembatasannya hasilnya sebagai berikut:
X1= 2,5 X2=1
X1= 1 X2= 2,3
X1= 1 X2= 2
X1= 2,25 X2= 1,5
X1= 0 X2= 3
10/31/2012
X1= 1,5 X2= 2
23
