1
PEMROGRAMAN LINEAR BULAT
(Integer Linear Programming - ILP)
Apa yang dimaksud dengan Pemrograman Bulat ?
METODE SIMPLEKS
Solusi yang didapat optimal,
tetapi mungkin tidak integer.
2
Integer Linear Programming
Misalnya saja kita ingin menentukan solusi
optimal dari satu lini perakitan televisi, yang
memproduksi beberapa tipe televisi.
Pembulatan matematis ? Mengganggu batasan
ILP
3
Integer Linear Programming
Jika model mengharapkan semua variabel basis bernilai
integer (bulat positif atau nol), dinamakan pure integer
programming.
Jika model hanya mengharapkan variabel-variabel tertentu
bernilai integer, dinamakan mixed integer programming.
Jika model hanya mengharapkan nilai nol atau satu untuk
variabelnya, dinamakan zero one integer programming.
4
SOLUSI INTEGER PROGRAMMING
PENDEKATAN PEMBULATAN
Pendekatan ini mudah dan praktis dalam hal usaha, waktu
dan biaya. Pendekatan pembulatan dapat merupakan cara
yang sangat efektif untuk masalah integer programming
yang besar dimana biaya-biaya hitungan sangat tinggi atau
untuk masalah nilai-nilai solusi variabel keputusan sangat
besar.
Contohnya, pembulatan nilai solusi jumlah pensil yang
harus diproduksi dari 14.250,2 menjadi 14.250,0
semestinya dapat diterima.
Sebab utama kegagalan pendekatan ini adalah bahwa
solusi yang diperoleh mungkin bukan solusi integer
optimum yang sesungguhnya. Solusi pembulatan dapat
lebih jelek dibanding solusi integer optimum yang
sesungguhnya atau mungkin merupakan solusi tak layak.
5
PENDEKATAN PEMBULATAN
Maksimumkan Z = 100 X1 + 90 X2
Dengan syarat 10 X1 + 7 X2 ≤ 70 Masalah 1
5 X1 + 10 X2 ≤ 50
X1 ; X2 ≥ 0
Minimumkan Z = 200 X1 + 400 X2
Dengan syarat 10 X1 + 25 X2 ≥ 100
3 X1 + 2 X2 ≥ 12
Masalah 2
X1 ; X2 ≥ 0
Maksimumkan Z = 80 X1 + 100 X2
Dengan syarat 4 X1 + 2 X2 ≤ 12
X1 + 5 X2 ≤ 15
Masalah 3
X1 ; X2 ≥ 0
6
Perbandingan antara solusi dengan metode simpleks tanpa pemba-
tasan bilangan bulat, pembulatan ke bilangan bulat terdekat dan solusi
integer optimum yang sesungguhnya untuk ketiga masalah diatas
adalah :
Solusi dengan Dgn pembulatan Bulat optimum
Masalah
Metode simpleks terdekat sesungguhnya
1 X1 = 5,38 X1 = 5 X1 = 7
X2 = 2,31 X2 = 2 X2 = 0
Z = 746,15 Z = 680 Z = 700
2 X1 = 1,82 X1 = 2 X1 = 3, X2 = 3
X2 = 3,27 X2 = 3 X1 = 5, X2 = 2
Z = 1.672,73 Z tak layak Z = 1.800
3 X1 = 2,14 X1 = 2 X1 = 0
X2 = 1,71 X2 = 2 X2 = 3
Z = 343 Z tak layak Z = 300
7
PENDEKATAN GRAFIK (Branch and
Bound)
Pendekatan ini identik dengan metode grafik LP dalam semua aspek, kecuali bahwa solusi optimum harus meme-nuhi persyaratan bilangan bulat.
Contoh :
Maksimumkan Z = 8X1 + 5X2
s/t X1 + X2 ≤ 6
9X1 + 5X2 ≤ 45
X1, X2 ≥ 0 dan integer
8
LINIER PROGRAMMING RELAKSASI
(SUB PERSOALAN 1)
X2
9
A (15/4 , 9/4)
0 5 6 X1
X1 + X2 = 6
9X1 + 5X2 = 45 9
SUB PERSOALAN 1
X1 = 15/4 X2 = 9/4
Z = 165/4
SP - 2 SP - 3
X 1 3 X 1 4
10
SUB PERSOALAN 2 & 3
X2
9
X1 = 3 X1 = 4
SP - 2
SP-3
0 3 4 5 6 X1
X1 + X2 = 6
9X1 + 5X2 = 45
11
SUB PERSOALAN 2 & 3
SP - 2 SP - 3
X1 = 3 X2 = 3 X1 = 4 X2 = 9/5
Z = 39 Z = 41
SP - 4 SP - 5
X 2 1 X 2 2
12
SUB PERSOALAN 4 & 5
X2
9
SP-5
2 X2 = 2
1 X2 = 1
SP-4
0 3 4 5 6 X1
X1 + X2 = 6
9X1 + 5X2 = 45
13
SUB PERSOALAN 4 & 5
SP - 4 SP - 5
X1 = 40/9 X2 = 1
FATHOMED
Z = 365/9
SP - 6 SP - 7
14
SUB PERSOALAN 6 & 7
X2
9
X1 = 4 X1 = 5
1 SP-6 SP-7
0 3 4 5 6 X1
9X1 + 5X2 = 45
15
SUB PERSOALAN 6 & 7
SP - 6 SP - 7
X1 = 4 X2 = 1 X1 = 5 X2 = 0
Z = 37 Z = 40
16
SOLUSI AKHIR
17