Integer Linier Programming dalam riset operasional .ppt

Riset operasional

1. 1

2. 2
PPEMROGRAMAN LINEAR BULATEMROGRAMAN LINEAR BULAT
(Integer Linear Programming - ILP)(Integer Linear Programming - ILP)
Apa yang dimaksud dengan Pemrograman Bulat ?

Solusi yang didapat optimal,
tetapi mungkin tidak integer.
METODE SIMPLEKSMETODE SIMPLEKS

3. 3
Integer Linear ProgrammingInteger Linear Programming
Misalnya saja kita ingin menentukan solusi
optimal dari satu lini perakitan televisi, yang
memproduksi beberapa tipe televisi.
Pembulatan matematis ? Mengganggu batasan
ILP

4. 4
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.
Integer Linear ProgrammingInteger Linear Programming

5. 5
SSOLUSI INTEGER PROGRAMMINGOLUSI INTEGER PROGRAMMING
PENDEKATAN PEMBULATANPENDEKATAN 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.

6. 6
PENDEKATAN PEMBULATANPENDEKATAN PEMBULATAN

Maksimumkan Z = 100 X1 + 90 X2
Dengan syarat 10 X1 + 7 X2 ≤ 70
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
X1 ; X2 ≥ 0

Maksimumkan Z = 80 X1 + 100 X2
Dengan syarat 4 X1 + 2 X2 ≤ 12
X1 + 5 X2 ≤ 15
X1 ; X2 ≥ 0
Masalah 1
Masalah 2
Masalah 3

7. 7
Masalah
Solusi dengan
Metode simpleks
Dgn pembulatan
terdekat
Bulat optimum
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


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 :

8. 8
PPENDEKATAN GRAFIK ENDEKATAN GRAFIK
Pendekatan ini identik dengan metode grafik LP dalam
semua aspek, kecuali bahwa solusi optimum harus meme-
nuhi persyaratan bilangan bulat.

Maksimumkan Z = 100 X1 + 90 X2
Dengan syarat 10 X1 + 7 X2 ≤ 70
5 X1 + 10 X2 ≤ 50
X1 ; X2 non negatif integer

9. 9
Model ini serupa dengan model LP biasa. Perbedaanya
hanya pada kendala terakhir yang mengharapkan bahwa
variabel terjadi pada nilai non negatif integer.
Solusi grafik masalah ini ditunjukkan pada gambar dibawah
ini. Ruang solusi layak adalah OABC. Solusi optimum
masalah LP ditunjukkan pada titik B, dengan X1 = 5,38 dan
X2 = 2,31 serta Z = 746,15. Untuk mencari solusi integer
optimum masalah ini, garis Z (slope = -9/10) digeser secara
sejajar dari titik B menuju titik asal.
Solusi integer optimum adalah titik integer pertama yang
bersinggungan dengan garis Z. Titik itu adalah A, dengan
X1 = 7 dan X2 = 0 serta Z = 700.
PENDEKATAN GRAFIKPENDEKATAN GRAFIK

10. 10
A
B
C
O
5
10
X1107
X2
Z = 700
Z = 746,15
5X1 + 10X2 = 50
10X1 + 7X2 = 70
PENDEKATAN GRAFIK PENDEKATAN GRAFIK

11. 11
PPENDEKATAN GOMORYENDEKATAN GOMORY
((CUTTING PLANE ALGORITHMCUTTING PLANE ALGORITHM ))
Langkah-langkah prosedur Gomory diringkas seperti
berikut :
1.Selesaikan masalah integer programming dengan meng-
gunakan metode simpleks. Jika masalah sederhana, ia
dapat diselesaikan dengan pendekatan grafik, sehingga
pendekatan Gomory kurang efisien.
2.Periksa solusi optimum. Jika semua variabel basis memi-
liki nilai integer, solusi optimum integer telah diperoleh dan
proses solusi telah berakhir. Jika satu atau lebih variabel
basis masih memiliki nilai pecah, teruskan ke tahap 3.
3.Buatlah suatu skala Gomory (suatu bidang pemotong atau
cutting plane) dan cari solusi optimum melalui prosedur
dual simpleks. Kembali ke tahap 2.

12. 12
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING
Tabel optimum masalah LP dibawah ini merupakan tabel solusi
optimum kontinyu.
Basis X1 Xm W1 Wn Solusi
Z 0 . . . . . 0 c1. . . . . cn b0
X1 1 . . . . . 0 a11. . . . . a1n b1
. . . . . .
. . . . . .
. . . . . .
Xm 0 1 am1 amn b1

13. 13
 Variabel Xi (i =1,…, m) menunjukkan variabel basis.
 Variabel Xj (j = 1,..., n) adalah variabel non basis.
Perhatikan persamaan ke i dimana variabel Xi diasumsikan bernilai
non integer.
Xi = bi – Σ aij Wj , dimana b non integer
Kemudian pisahkan bi dan aij menjadi bagian yang bulat dan bagian
pecah non negatif seperti berikut :
bi = bi + f i jadi f i = bi - bi , dimana 0 ≤ f i ≤ 1
aij = aij + f i jadi f i = aij - aij , dimana 0 ≤ f ij ≤ 1
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING

14. 14
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING
Kendala Gomory yang diinginkan adalah :
Sg - f ij Wj = - f i , Sg adalah variabel slack Gomory ke g.
Pada umumnya, persamaan kendala yang berhubungan
dengan solusi pecah dipilih untuk menghasilkan suatu
kendala Gomory. Namun, sebagai aturan main biasanya
dipilih persamaan yang memiliki fi, maksimum.
bi bi f i aij aij f ij
3/2 1 ½ 7/3 - 3 2/3
7/8 0 7/8 - 1 - 1 0
7/3 2 1/3 - 2/5 - 1 3/5

15. 15
Tabel baru setelah penambahan kendala Gomory menjadi :
Basis X1 Xm W1 Wn Sg Solusi
Z 0 . . . . . 0 c1. . . . . cn 0 b0
X1 1 . . . . . 0 a11. . . . . a1n . b1
. . . . . . .
. . . . . . .
. . . . . . .
Xm 0 1 am1 amn amn b1
Sg 0 . . . . . 0 - fi1 - fin 1 - fi

16. 16
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING
Jika diperoleh solusi primal optimum tetapi
tidak layak maka digunakan metode dual
simpleks.
Proses pembentukan kendala Gomory berakhir
jika solusi baru semua berupa bilangan bulat.
Jika tidak, suatu kendala Gomory baru dibuat
lagi dari tabel yang dihasilkan dan metode dual
simpleks digunakan lagi untuk mengatasi
ketidak layakan.
Jika pada setiap iterasi metode dual simpleks
menunjukkan bahwa tidak ada solusi layak,
berarti masalah itu tidak memiliki solusi integer
yang layak.

17. 17
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING
Solusi kontinyu optimumnya diperoleh dalam tabel berikut :

Maksimumkan Z = 7 X1 + 9 X2
Dengan syarat - X1 + 3 X2 ≤ 6
7 X1 + X2 ≤ 35
X1 ; X2 non negatif integer
Basis X1 X2 S1 S2 Solusi
Z 0 0 28/11 15/11 63
X2 0 1 7/22 1/22 7/2
X1 1 0 - 1/22 3/22 9/2

18. 18
Karena solusi tidak bulat, suatu kendala Gomory ditambah-
kan pada tabel itu. Kedua persamaan (X1 dan X2) pada
masalah ini memiliki nilai f i yang sama, yaitu f 1 = f 2 = ½ ,
sehingga salah satu dapat digunakan, misalkan digunakan
persamaan X2 , ini menghasilkan :
X2 + 7/22 S1 + 1/22 S2 = 7/2 atau
X2 + (0 + 7/22) S1 + (0 + 1/22) S2 = (3 + ½)
Sehingga kendala Gomorynya adalah :
Sg1 - 7/22 S1 – 1/22 S2 = - ½
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING

19. 19
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING
Basis X1 X2 S1 S2 Sg1 Solusi
Z 0 0 28/11 15/11 0 63
X2 0 1 7/22 1/22 0 7/2
X1 1 0 - 1/22 3/22 0 9/2
Sg1 0 0 - 7/2 - 1/22 1 - ½

Tabel baru setelah penambahan kendala Gomory menjadi :
Dengan memakai metode dual simpleks diperoleh tabel baru yaitu :
Basis X1 X2 S1 S2 Sg1 Solusi
Z 0 0 0 1 8 59
X2 0 1 0 0 1 3
X1 1 0 0 1/7 - 1/7 32/7
S1 0 0 1 1/7 - 22/7 11/7

20. 20
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING
Karena solusi baru masih pecah, suatu kendala Gomory bary
ditambahkan. Karena persamaan X1 memiliki f 1 terbesar (f 1 = 4/7),
maka X1 dituliskan dalam bentuk :
X1 + (0 + 1/7) S2 + (0+ 6/7) Sg1 = (4 + 4/7),
Menghasilkan kendala Gomory kedua :
Sg2 – 1/7 S1 – 6/7 Sg1 = - 4/7, kemudian tambahkan pada tabel :
BasisX
1
X
2
S
1
S
2
S
g1
S
g2 Solusi
Z 0 0 0 1 8 0 59
X
2 0 1 0 0 1 0 3
X
1 1 0 0 1/7 - 1/70 32/7
S
1 0 0 1 1/7 - 22/70 11/7
S
g2 0 0 0 - 1/7- 6/71 - 4/7

21. 21
Dengan menggunakan dual simpleks diperoleh hasil :
Yang menghasilkan solusi bulat optimum X1 = 4, X2 =3 dan Z = 55
BasisX
1
X
2
S
1
S
2
S
g1
S
g2 Solusi
Z 0 0 0 0 2 7 55
X
2 0 1 0 0 1 0 3
X
1 1 0 0 0 -1 1 4
S
1 0 0 1 0 - 4 1 1
S
g2 0 0 0 1 6 -7 4
KENDALA GOMORY DALAM PURE INTEGER PROGRAMMINGKENDALA GOMORY DALAM PURE INTEGER PROGRAMMING

22. 22
MMETODE BRANCH DAN BOUNDETODE BRANCH DAN BOUND
Metode Branch dan Bound telah menjadi kode komputer
standar untuk integer programming, dan penerapan- penerap-
an dalam praktek tampaknya menyarankan bahwa metode ini
lebih efisien dibanding dengan pendekatan Gomory. Teknik ini
dapat diterapkan baik untuk masalah pure programming
maupun mixed integer programming.

23. 23
1.Selesaikan LP dengan metode simpleks biasa
2.Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat
adalah bulat, solusi optimum bulat telah tercapai.
3.Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub
masalah. Tujuannya adalah untuk menghilangkan solusi kontinyu
yang tidak memenuhi persyaratan bulat dalam masalah itu.
4.Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi
tujuan ditetapkan sebagai batas atas. Solusi bulat terbaik menjadi
batas bawah (pada awalnya, ini adalah solusi kontinyu yang
dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas
kurang dari batas bawah yang ada, tidak diikut sertakan pada
analisa selanjutnya. Suatu solusi bulat layak adalah sama baik atau
lebih baik dari batas atas untuk setiap sub masalah yang dicari. Jika
solusi yang demikian terjadi, suatu sub masalah dengan batas atas
terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.
Langkah-langkah metode Branch dan Bound untuk
masalah maksimasi dapat dilakukan seperti berikut :

24. 24
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND
Untuk memperoleh gambaran yang lebih jelas tentang
metode Branch dan Bound, perhatikan contoh masalah
berikut :

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X1 ; X2 non negatif integer
Solusi optimum kontinyu masalah ini adalah X1 = 8, X2 =
2,26 dan Z = 35,25.
Solusi ini menunjukkan batas atas awal.

25. 25
Batas bawah adalah solusi yang dibulatkan ke bawah X1 = 8, X2 =
2 dan Z = 34. Dalam metode Branch dan Bound, masalah itu
dibagi ke dalam dua bagian untuk mencari nilai solusi bulat yang
mungkin bagi X1 dan X2.
Variabel dengan nilai solusi pecah terbesar dipilih. Karena pada
solusi ini hanya X2 yang memiliki bagian pecah, ia dipilih. Untuk
menghilangkan bagian pecah dari nilai X2 = 2,25, dua kendala baru
dibuat.
Kendala-kendala ini mewakili dua bagian baru dari masalah itu.
Dua nilai bulat terdekat terhadap 2,25 adalah 2 dan 3. Sehingga
diperoleh dua masalah baru melalui dua kendala mutually
exclusive, X2 ≤ 2 dan X2 ≥ 3, yang akan diuraikan berikut ini se-
bagai bagian A dan B. Kendala-kendala ini secara efektif menghi-
langkan semua nilai pecah yang mungkin bagi X2, antara 2 dan 3.
Pengaruhnya mereka mengurangi ruang solusi layak sehingga
angka solusi bulat yang dievaluasi pada masalah ini makin sedikit
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND

26. 26

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X2 ≤ 2
X1 ; X2 ≥ 0
(berlebih)

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X2 ≥ 3
X1 ; X2 ≥ 0
Bagian A :
Bagian B :
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND

27. 27
Bagian A dan B diselesaikan tanpa pembatasan bilangan bulat
dengan metode simpleks. Solusi simpleksnya adalah :
Bagian A : X1 = 8, X2 = 2 dan Z = 34
Bagian B : X1 = 6,5, X2 = 3 dan Z = 34,5
Bagian A menghasilkan suatu solusi yang semuanya bulat.
Untuk bagian A batas atas dan bawah adalah Z = 34. Solusi
pecah bagian B membenarkan pencarian lebih lanjut karena
menghasilkan nilai fungsi tujuan yang lebih besar dari batas
atas bagian A. Sangat mungkin bahwa pencarian lebih lanjut
dapat menghasilkan suatu solusi yang semuanya bulat dengan
nilai fungsi tujuan melebihi batas atas bagian A = 34.
Bagian B dicabangkan ke dalam dua sub bagian, B1 dan B2,
pertama dengan kendala X1 ≤ 6 dan yang lain dengan X2 ≥ 7.
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND

28. 28

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X2 ≥ 3
X1 ≤ 6
X1 ; X2 ≥ 0

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X2 ≥ 3
X1 ≥ 7
X1 ; X2 ≥ 0
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND
Sub Bagian B1 :
Sub Bagian B2 :
(berlebih)

29. 29
Solusi simpleksnya adalah :
Sub-bagian B1 : X1 = 6, X2 = 3,25 dan Z = 34,25
Sub-bagian B2 : tidak layak.
Karena sub-bagian B1 menghasilkan nilai fungsi tujuan yang
lebih besar dari 34 (batas atas bagian A), maka harus dica-
bangkan lagi ke dalam dua sub masalah, dengan kendala
X2 ≤ 3 dan X2 ≥ 4. Kedua kendala sub masalah diberi nama
bagian B1a dan B2b.
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND

30. 30

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X2 ≥ 3
X2 ≥ 4
X1 ≤ 6
X1 ; X2 ≥ 0

Maksimumkan Z = 3 X1 + 5 X2
Dengan syarat 2 X1 + 4 X2 ≤ 25
X1 ≤ 8
2 X2 ≤ 10
X2 ≥ 3
X2 ≤ 3
X1 ≤ 6
X1 ; X2 ≥ 0
Bagian B1a :
Bagian B1b :
(berlebih)
(berlebih)
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND

31. 31
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND
Solusi optimum dengan metode simpleks adalah :
Sub-bagian B1a : X1 = 6, X2 = 3 dan Z = 33
Sub-bagian B1b : X1 = 4,25, X2 = 4 dan Z = 33,5
Kedua solusi itu memiliki batas atas ( Z = 33 dan Z = 33,5)
yang lebih buruk dibanding dengan solusi yang dihasilkan
oleh bagian A. Karena itu, solusi bulat optimum adalah X1 =
8, X2 = 2 dan Z = 34 yang dihasilkan oleh bagian A.
Jika pencarian telah diselesaikan, solusi bulat dengan
fungsi tujuan tertinggi (dalam masalah maksimasi) dipilih
sebagai solusi optimum.

32. 32
Kelemahan dasar dari metode ini adalah bahwa diperlukan
pemecahan masalah LP untuk setiap pencabangan. Dalam
masalah yang besar dapat memakan banyak waktu. Karena
itu dalam prosedur pencabangan dan pencarian, analisa
selanjutnya dihentikan jika :
1.Hasil dari sub-problem lebih jelek dibanding dengan batas
atas yang sudah diidentifikasi
2.Pencabangan selanjutnya menghasilkan solusi tak layak.
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND

33. 33
X1 = 8
X2 = 2
Z = 34
1
0
X
1 ≤ 6
X
1
≥

7
Solusi bulat optimum
X1 = 8
X2 = 2,25
Z = 35,25
2
Tak layak
X1 = 6,5
X2 = 3
Z = 34,5
X
2 ≤ 2
X
2
≥

3
inferior
inferior
X1 = 6
X2 = 3,25
Z = 34,25
X
2 ≤ 3
X
2
≥

4
METODE BRANCH DAN BOUNDMETODE BRANCH DAN BOUND
SSeluruh prosedur Branch dan Bound untuk contoh yang lalu
dapat digambarkan seperti berikut :