(9) integer programming - branch and bound (ind)

Pemrograman Bilangan Bulat(Integer Programming)

Amelia Kurniawati ST., MT.

Outline

2

Konsep Bilangan Bulat

Metode pemecahan

bilangan bulat

• Pengantar pemrograman bilangan bulat

• Contoh model pemrograman

• Metode branch and bound

3

GOAL

• Memahami permasalahan dan solusi variabel integer

• Memahami metode Branch and Bound

Konsep Bilangan Bulat

Pengantar Pemrograman Bilangan Bulat1

Pemrograman Bilangan Bulat

• Pemrograman bilangan bulat (integer programming) mensyaratkan bahwa beberapa variabel keputusan harus mempunyai nilai yang bulat (bukan pecahan)

• Di sini, pembahasan hanya ditujukan untuk masalah pemrograman linier bilangan bulat (integer linear programming problem)

6

Jenis Pemrograman LinierBilangan Bulat

• Pemrograman linier bilangan bulat murni (pure integer linear programming, PILP)

• Pemrograman linier bilangan bulat campuran (mixed integer linear programming, MILP)

• Pemrograman linier bilangan bulat biner (binary integer linear programming, BILP)

7

8

Pembatas Either-Or

1823 21 xx

164 21 xx

1823 21 xxMxx 164 21

Mxx 1823 21

164 21 xx

dan

dan

Myxx 1823 21

)1(164 21 yMxx atau

atau

LP format:

1,0iy

Contoh Pemrograman Linier Bilangan Bulat Biner

Fungsi dengan N Nilai yang Mungkin

9

Nn dddxxxf atau atau atau ,,, 2121

N

iiin ydxxxf

121 ,,,

Perumusan ILP:

11

N

iiy

Niyi ,,2,1 ,1,0

Contoh Pemrograman Linier Bilangan Bulat Biner

10

Contoh Kasus:18atau 12atau 623 21 xx

32121 1812623 yyyxx

Perumusan ILP:

1321 yyy

3,2,1 ,1,0 iyi

Contoh Pemrograman Linier Bilangan Bulat Biner

Representasi Biner untuk Variabel Bilangan Bulat

ux 0 122 dimana NN u

Representasi biner:

N

ii

i yx0

2

Niyi ,,2,1 ,1,0

Batas-batas untuk variabel x:

Contoh Pemrograman Linier Bilangan Bulat Biner

11

Contoh Kasus:

12

51 x

Representasi biner:

542 210 yyy

2,1,0 ,1,0 iyi

3032 21 xx

308423422 3210210 wwwyyy

u untuk x1 = 5 22 5 23 u untuk x2 = 10 23 10 24

3,2,1,0 ,1,0 iwi

Contoh Pemrograman Linier Bilangan Bulat Biner

Beberapa Contoh Model Pemrograman Bilangan Bulat2

Beberapa Contoh Model-model Pemrograman Bilangan Bulat

• Fixed charge problem• Knapsack problem• Set covering problem– Set Partitioning Problem

• Traveling salesman problem• Job (Machine) scheduling problem

14

Fixed Charge Problem (1)

Misalkan terdapat n jenis produkpj = harga satuan produk j

kj = biaya tetap untuk memproduksi produk j (independen terhadap jumlah produksi)

cj = biaya variabel untuk memproduksi produk j (proporsional terhadap jumlah produksi)

bi = kapasitas sumber i (i = 1, …m)

aij = kebutuhan sumber i untuk per unit produk j

15

16

Fixed Charge Problem (2)

Permasalahan :Menentukan produk mana yang perlu diproduksi dan jumlah produksinya masing-masing agar diperoleh profit (selisih penjualan dengan biaya tetap dan variabel) total yang maksimum dengan memperhatikan kondisi: ketersediaan kapasitas jika suatu jenis produk diputuskan untuk tidak diproduksi maka jumlah produksinya

nol, dan biaya tetap dan biaya variabel untuk produk tersebut juga nol. jika suatu jenis produk diputuskan untuk diproduksi maka jumlah produksinya x, dan

muncul biaya tetap (tidak tergantung jumlah x) dan biaya variabel (tergantung jumlah x) yang harus dikeluarkan.

Variabel keputusan :xj = jumlah produk j yang diproduksiyj = keputusan untuk memproduksi atau tidak produk j;yj = 1 jika produk j diproduksiyj = 0 jika produk j tidak diproduksi

Fixed Charge Problem (3)

17

n

jjjjj

n

jjj xcyKxpZ

11

Maximize

dengan pembatas-pembatas:

mibxa i

n

jjij ,,1 ,

1

njMyx jj ,,1 ,

njx j ,,1 ,0

njy j ,...,1 ,1,0

Knapsack Problem (1)Misalkan terdapat n item.wj = berat item jvj = nilai item jW = kapasitas muatan (berat) dari kantong

Permasalahan :Menentukan jumlah item yang perlu dimasukkan ke dalam kantong agar diperoleh nilai total yang maksimum dengan memperhatikan kondisi kapasitas muatan (berat) dari kantong

Variabel keputusan :xj = jumlah item yang dimasukkan ke kantong

18

Knapsack Problem (2)

19

n

jjj xvZ

1

Maximize

dengan pembatas-pembatas:

Wxwn

jjj

1

bulatbilangan dan 0jx

Set Covering Problem (1)

20

Jalan C

Jalan D

Jalan BJalan A

Jalan E

Jalan

F

Jala

n G Ja

lan

KJa

lan

J

Jala

n I

Jala

n H

1 2

6 7

4

8

5

3

Contoh masalah set covering problem dalam menentukanlokasi pendirian pos siskamling

Set Covering Problem (2)Misalkan terdapat n lokasi pendirian pos dan m jalan.Cj = biaya mendirikan pos di lokasi j

Aij = konstanta biner (0-1)

aij = 1 jika jalan i dilayani oleh pos yang berlokasi di j

aij = 0 jika sebaliknya

Pertanyaan:Menentukan lokasi pendirian pos dimana tiap jalan dapat dilayani minimal oleh satu pos sehingga diperoleh biaya total pendirian yang minimum

Variabel keputusanxj = variabel biner

(0-1) yang menentukan keputusan untuk mendirikan pos di lokasi j (xj = 1 jika pos didirikan di lokasi j, xj = 0 sebaliknya)

21

Set covering problem (3)

22

n

jjj xcZ

1

Minimize

Dengan pembatas-pembatas:

mixan

jjij ,...,1 ,1

1

njx j ,...,1 ,1,0

Set Partitioning Problem

23

n

jjj xcZ

1

Minimize

Dengan pembatas-pembatas:

mixan

jjij ,...,1 ,1

1

njx j ,...,1 ,1,0

Tiap jalantepat dilayanioleh satu pos

Traveling Salesman Problem (1)

24

1

2

3

45

5

6

3

4

38

2

6

1

7

(jarak)

Traveling Salesman Problem (2)Misalkan terdapat n titik.Cij = jarak antara titik i ke titik j (cij = untuk i = j)

PermasalahanMenentukan rute salesman yang berangkat dari suatu titik dan mengunjungi setiap titik yang lain paling banyak sekali, serta kembali ke titik asal agar diperoleh jarak total yang minimum

Variabel keputusanXij = keputusan untuk melintasi atau tidak busur (i, j)

xij = 1 jika busur (i, j) dilintasi

xij = 0 jika busur (i, j) tidak dilintasi

25

Traveling Salesman Problem (3)

26

n

j

n

iijij xcZ

1 1

Minimize

dengan pembatas-pembatas:

nixn

jij ,,1 ,1

1

njxn

iij ,,1 ,1

1

jinjninnxuu ijji ;,,2;,,2 ,1

njnixij ,1;,,1 ,1,0

niui ,...,1 ,0

Subtour breakingconstraint

Traveling Salesman Problem (4)

27

1

2

3

45

Subtour

Subtour breaking constraint bertujuan untuk mengeliminasiterjadinya solusi subtour

Traveling Salesman Problem (5)

28

1

2

3

45

Tour

Suatu solusi traveling salesman problem yang layak (terbentuknyasuatu tour).

Job Scheduling Problem (1)Misalkan - terdapat n job dengan operasi-tunggal - terdapat satu mesin tunggal

pj = waktu pengerjaan job jwj = bobot kepentingan job j

Permasalahan:Menentukan saat awal (juga secara implisit menentukan saat akhir) pengerjaan job agar diperoleh waktu penyelesaian tertimbang total (total weighted completion time) yang minimum dengan memperhatikan bahwa pada suatu saat mesin hanya dapat mengerjakan satu operasi (job)

29

Job Scheduling Problem (2)Variabel keputusan:Bj = saat awal pengerjaan job jCj = saat akhir pengerjaan job jyij = keputusan apakah job i mendahului job j

yij = 1 jika job i mendahului job j yij = 0 jika sebaliknya

30

0

3 1 4 5 2

p3 p1 p4 p5 p2

Suatu solusi (jadwal) pengerjaan job yang layak

Job Scheduling Problem (3)

31

n

jjjCwZ

1

Minimize

dengan pembatas-pembatas:

nipC jj ,,1 ,

jinjnipyMCC iijij ,,1;,,1 ,1

niC j ,...,1 ,0

jinjnipMyCC jijji ;,1;,,1 ,

njniyij ,1,,...,1 ,1,0

nipCB jjj ,,1 ,

Disjunctive constraint(Either-or constraint)

Metode Pemecahan Model Pemrograman Bilangan Bulat

Metode Pemecahan

Metode pemecahan kasus pemrograman bilangan bulat:

• Cutting method– Cutting Plane

• Search method– Branch and Bound

33

Metode Cutting Plane1

Algoritma Cutting Plane• Dikembangkan oleh R.E. Gomory• Algoritma– Fractional algorithm untuk masalah pemrograman

bilangan bulat murni (PILP)– Mixed algorithm untuk masalah pemrograman

bilangan bulat campuran (MILP)

35

36

Ilustrasi Suatu Masalah ILP

Maximize Z = 7x1 + 9x2

Dengan pembatas-pembatas: –x1 + 3x2 6 7x1 + x2 35 x1, x2 ≥ 0 dan bilangan bulat

Daerah layak

37

x2

x1

Solusi Optimal Kontinyu(dengan mengabaikan kondisi integralitas)

38

x2

x1

63

3,4),( 21

21

21

Z

xx

Ide Dasar dari Cutting Plane

• Mengubah convex set dari daerah ruang pemecahan (solution space) sehingga titik ekstrem menjadi bilangan bulat.

• Perubahan dibuat tanpa men-slicing off daerah layak dari masalah awal.

• Perubahan dilakukan dengan penambahan beberapa secondary constraint.

39

Penambahan pembatas sekunder

40

x2

x1

secondary constraint

55

3,4),( 21

Z

xx

Fractional Algorithm (1)

• Digunakan untuk memecahkan masalah pemrograman linier bilangan bulat murni (PILP).

• Mensyaratkan bahwa semua koefisien teknologi dan konstanta ruas kanan adalah bilangan bulat.

• Pada awalnya, masalah PILP dipecahkan sebagai LP reguler, yaitu dengan mengabaikan kondisi integralitas.

41

2

13

3

121 xx 3926 21 xx

Fractional Algorithm (2)

Basis x1 xi xm w1 wj wn Solusi

x1 1 0 0 11 1

j 1n 1

xi 0 1 0 i1 i

j in n

xm 0 0 1 m1 m

j mn m

0 0 0 0

42

jc1c jc

nc

Tabel akhir optimal untuk LP

Fractional Algorithm (3)

43

Variabel xi (i = 1, …, m) menunjukkan variabel basisVariabel wj (j = 1, …, n) menunjukkan variabel non basis

Misalkan persamaan ke-i dimana variabel xi diasumsikan bernilai bilangan bulat

bulatbilangan bukan , i1

n

jj

jiii wx (baris sumber)

Fractional Algorithm (4)

44

Misal: iii f

ijj

ij

i f

dimana N = [a] adalah bilangan bulat terbesar sehingga N a0 < fi < 10 fij < 1

Fractional Algorithm (5)

45

Dari baris sumber diperoleh:

n

jj

jiii

n

jiiji wxwff

11

Agar semua xi dan wj adalah bilangan bulat,maka ruas kanan dari persamaan harus bilangan bulat Akibatnya, ruas kiri harus bilangan bulat

Fractional Algorithm (6)

46

Untuk fij 0 dan wj 0 untuk semua i dan j maka

01

n

jjijwf

Akibatnya

i

n

jjiji fwff

1

Fractional Algorithm (7)

47

11

n

jjiji wff

Karena fi < 1 maka

Karena ruas kiri harus bilangan bulat, maka syarat perluuntuk memenuhi integralitas adalah:

01

n

jjiji wff

Fractional Algorithm (8)

48

Pertidaksamaan terakhir dapat dijadikan sebagai pembatasdalam bentuk:

i

n

jjiji fwfS

1

(fractional cut)

Fractional Algorithm (9)

Basis x1 xi xm w1 wj wn Si Solusi

x1 1 0 0 11 1

j 1n 0 1

xi 0 1 0 i1 i

j in 0 n

xm 0 0 1 m1 m

j mn 0 m

Si 0 0 0 -fi1 -fi

j -fim 1 -fi

0 0 0 0 0

49

jc1c jc

nc

Tabel setelah penambahan fractional cut

Fractional Algorithm (10)

• Dengan penambahan fractional cut, tabel terakhir menjadi tidak layak walaupun optimal sehingga metode dual simplex diterapkan untuk meniadakan ketidaklayakan.

• Algoritma berhenti jika solusi optimal bilangan bulat diperoleh.

50

Fractional Algorithm (11)

51

i

n

jjij fwf

1

k

n

jjkj fwf

1

Cut (1) dikatakan lebih kuat dari cut (2) jika fi fk dan fij fkj untuk semua j dengan strict inequality terpenuhi paling sedikit satu

Kekuatan fractional cut

Fractional Algorithm (12)

52

Aturan : ii

fmax

n

jij

i

if

f

1

max

Ilustrasi Penerapan Fractional Algorithm (1)

53

Maximize Z = 7x1 + 9x2

dengan pembatas-pembatas: –x1 + 3x2 6 7x1 + x2 35 x1, x2 ≥ 0 dan bilangan bulat

Ilustrasi Penerapan Fractional Algorithm (2)

Basis x1 x2 x3 x4 Solusi

x2 0 1 7/22 1/22 3 1/2

x1 1 0 -1/22 3/22 4 1/2

cj – zj 0 0 -28/11 -15/11 Z = 63

54

Tabel optimal kontinyu

Ilustrasi Penerapan Fractional Algorithm (3)

55

2

7

22

1

22

7432 xxx

2

13

22

10

22

70 432 xxx

2

1

22

1

22

7431 xxS

Fractional cut:

Baris sumber persamaan-x2

Ilustrasi Penerapan Fractional Algorithm (4)

Basis x1 x2 x3 x4 S1 Solusi

x2 0 1 7/22 1/22 0 7/2

x1 1 0 -1/22 3/22 0 9/2

S1 0 0 -7/22 -1/22 1 -1/2

cj – zj 0 0 -28/11 -15/11 0

56

Tabel setelah penambahan fractional cut

Ilustrasi Penerapan Fractional Algorithm (5)

Basis x1 x2 x3 x4 S1 Solusi

x2 0 1 0 0 1 3

x1 1 0 0 1/7 -1/7 4 4/7

x3 0 0 1 1/7 -22/7 1 4/7

cj – zj 0 0 0 -1 -8 Z = 59

57

Tabel yang diperoleh dengan dual simplex:

Ilustrasi Penerapan Fractional Algorithm (6)

58

7

44

7

1

7

1141 Sxx

7

44

7

61

7

10 141 Sxx

7

4

7

6

7

1142 SxS

Fractional cut:

Baris sumber persamaan-x1

Ilustrasi Penerapan Fractional Algorithm (7)

Basis x1 x2 x3 x4 S1 S2 Solusi

x2 0 1 0 0 1 0 3

x1 1 0 0 1/7 -1/7 0 4 4/7

x3 0 0 1 1/7 -22/7 0 1 4/7

S2 0 0 0 -1/7 -6/7 1 -4/7

cj – zj 0 0 0 -1 -8 0

59

Tabel setelah penambahan fractional cut

Ilustrasi Penerapan Fractional Algorithm (8)

Basis x1 x2 x3 x4 S1 S2 Solusi

x2 0 1 0 0 1 0 3

x1 1 0 0 0 -1 1 4

x3 0 0 1 0 -4 1 1

x4 0 0 0 1 6 -7 4

cj – zj 0 0 0 -2 -7 0 Z = 55

60

Solusi bilangan bulat optimal, x1 = 4, x2 = 3; Z = 55

Tabel yang diperoleh dengan dual simplex:

Ilustrasi Fractional Cut secara grafis (1)

61

2

1

22

1

22

7431 xxS

2

1735

22

136

22

721211 xxxxS

321 xS

32 x

Fractional cut 1:

62

Ilustrasi Fractional Cut secara grafis (2)

x2

x1

32 x

Ilustrasi Fractional Cut secara grafis (3)

63

7

4

7

6

7

1142 SxS

7

43

7

6735

7

12212 xxxS

7212 xxS

721 xx

Fractional cut 2:

Ilustrasi Fractional Cut secara grafis (4)

64

x2

x1

32 x

721 xx

Mixed Algorithm (1)

• Digunakan untuk memecahkan masalah pemrograman linier bilangan bulat campuran (MILP)

• Pada awalnya, masalah MILP dipecahkan sebagai LP reguler, yaitu dengan mengabaikan kondisi integralitas.

65

Mixed Algorithm (2)

66

Maximize Z = 7x1 + 9x2

dengan pembatas-pembatas: –x1 + 3x2 6

7x1 + x2 35 x1 ≥ 0 dan bilangan bulat x2 ≥ 0

Mixed Algorithm (3)

67

n

jj

jkkk wx

1

Misal xk adalah variabel bilangan bulat dari masalah MILP.

Persamaan-xk dalam solusi kontinyu optimal:

n

jj

jkkkk wfx

1

n

jj

jkkkk wfx

1

(baris sumber)

Mixed Algorithm (4)

68

Untuk xk adalah bilangan bulat, maka

1atau kkkk xx

harus dipenuhi

k

n

jk

jk fw

1

Dari baris sumber, kondisi ini ekivalen dengan

11

k

n

jk

jk fw

(1)

(2)

Mixed Algorithm (5)

69

MisalJ+ = himpunan subscripts j untuk k

j 0J- = himpunan subscripts j untuk k

j < 0

Dari (1) dan (2) diperoleh

k

n

Jjk

jk fw

k

n

Jjk

jk

k

k fwf

f

1

(3)

(4)

Mixed Algorithm (6)

70

Karena (1) dan (2), tidak dapat terjadi secara simultan,maka (3) dan (4) dapat digabungkan menjadi satu pembatas dalam bentuk

k

n

Jjk

jk

k

kn

Jjk

jkk fw

f

fwS

1

(mixed cut)

Ilustrasi Penerapan Mixed Algorithm (1)

71

Maximize Z = 7x1 + 9x2

dengan pembatas-pembatas: –x1 + 3x2 6

7x1 + x2 35 x1 ≥ 0 dan bilangan bulat x2 ≥ 0

Ilustrasi Penerapan Mixed Algorithm (2)

Basis x1 x2 x3 x4 Solusi

x2 0 1 7/22 1/22 7/2

x1 1 0 -1/22 3/22 9/2

cj – zj 0 0 -28/11 -15/11 Z = 63

72

Tabel optimal kontinyu:

Ilustrasi Penerapan Mixed Algorithm (3)

73

2

14

22

3

22

1431 xxx

2

1

22

1

122

33

21

21

41

xxS

2

1

22

3

22

1431 xxS

Mixed cut:

Baris sumber persamaan-x1

21

1 ,4 ,3 fJJ

Basis x1 x2 x3 x4 S1 Solusi

x2 0 1 7/22 1/22 0 7/2

x1 1 0 -1/22 3/22 0 9/2

S1 0 0 -1/22 -3/22 1 -1/2

cj – zj 0 0 -28/11 -15/11 0

74

Tabel setelah penambahan mixed cut

Basis x1 x2 x3 x4 S1 Solusi

x2 0 1 10/33 0 -1/3 10/3

x1 1 0 -1/11 0 1 4

x4 0 0 1/3 1 -22/3 11/3

cj – zj 0 0 -23/11 -10 0 Z= 58

75

Tabel yang diperoleh dengan dual simplex:

Solusi optimal, x1 = 4, x2 = 10/3; Z = 55

Metode Branch and Bound2

Metode Branch and Bound

Algoritma Branch-and-Bound (1)

• Metode yang paling banyak digunakan dalam praktik untuk memecahkan masalah pemrograman bilangan bulat baik murni maupun campuran.

• Digunakan sebagian besar software komersial • Pada dasarnya merupakan prosedur

enumerasi yang efisien untuk memeriksa semua solusi layak yang mungkin.

78

79

Algoritma Branch-and-Bound (2)

• Algoritma BB untuk ILP (PILP & MILP)• Algoritma BB untuk BILP

Algoritma BB untuk ILP (1)

80

Misalkan diberikan suatu masalah pemrogramanbilangan bulat sebagai berikut:

Maximize Z = cxdengan pembatas

Ax = bx 0

xj bilangan bulat untuk j Idimana I adalah himpunan variabel bilangan bulat

Algoritma BB untuk ILP (2)• Langkah pertama adalah memecahkan masalah ILP sebagai LP

dengan mengabaikan pembatas bilangan bulat (bounding)• Misalkan masalah LP dinyatakan sebagai LP-1 yang mempunyai

nilai optimal dari fungsi tujuan Z1.

81

LP-1Maximize Z = cxdengan pembatas

Ax = bx 0

Algoritma BB untuk ILP (3)

• Asumsikan bahwa solusi optimal dari LP-1 mengandung beberapa variabel bilangan bulat yang mempunyai nilai pecahan.

• Oleh karena itu, solusi optimal bilangan bulat untuk ILP belum diperoleh dan Z1

menjadi batas atas (upper bound) dari nilai maksimum Z untuk ILP.

• Langkah berikutnya adalah mempartisi daerah layak dari LP-1 dengan mencabangkan (branching) salah satu variabel bilangan bulat yang nilainya pecahan.

82

Algoritma BB untuk ILP (4)

• Misalkan variabel xj dipilih untuk dicabangkan dengan nilai pecahan j dalam LP-1.

• Misalkan dibuat dua masalah pemrograman linier baru, LP-2 dan LP-3 dengan memasukkan masing-masing pembatas baru xj [] dan xj []+1.

83

Algoritma BB untuk ILP (5)

84

Maximize Z = cxdengan pembatas

Ax = bxj []x 0

Maximize Z = cxdengan pembatas

Ax = b xj []+1 x 0

LP-2 LP-3

Algoritma BB untuk ILP (6)

85

LP-1

LP-2 LP-2

Solusi pecahanZ1

Solusi pecahanZ2

][ jjx 1][ jjx

Solusi pecahanZ5

Algoritma BB untuk ILP (7)

• Memecahkan (bounding) LP-2 dan LP-3• Asumsikan solusi LP-2 dan LP-3 masih pecahan• Langkah berikutnya adalah memilih node (masalah LP)

yang akan dicabangkan

86

Algoritma BB untuk ILP (8)

• Setelah masalah LP dipilih untuk dicabangkan lebih lanjut, langkahnya selanjutnya adalah – memilih variabel bilangan bulat dengan nilai pecahan yang akan

dicabangkan untuk membentuk dua masalah LP baru (proses branching)

– memecahkan masalah LP yang baru (proses bounding)

• Jika solusi bilangan bulat diperoleh dari suatu masalah LP maka nilai Z-nya menjadi batas bawah (lower bound) dari nilai maksimum Z untuk masalah ILP

87

Algoritma BB untuk ILP (9)

• Proses branching dan bounding berlanjut hingga semua node dalam kondisi fathomed.

• Fathoming suatu node (masalah LP):– Solusi optimal LP merupakan bilangan bulat– Masalah LP adalah tak layak– Nilai optimal Z dari masalah LP tidak lebih baik

daripada batas bawah (lower bound) saat ini.

88

Algoritma BB untuk ILP (10)

89

LP-1

LP-2 LP-3

Solusi pecahanZ0 = Z1

Solusi pecahanZ2

][ jjx 1][ jjx

Solusi pecahanZ5

LP-3 LP-4

Tidak layakSolusi bulatZ4

][ iix 1][ iix

Algoritma BB untuk ILP (11)

90

LP-1

LP-2

LP-3 LP-4

LP-5

LP-6 LP-7

Solusi pecahanZ0 = Z1

Solusi pecahanZ2

Tidak layakSolusi bulatZ4

Solusi pecahanZ6 < Z4

][ jjx 1][ jjx

][ iix 1][ iix 1][ kkx ][ kkx

Solusi pecahanZ5

Solusi pecahanZ7 > Z4

Algoritma BB untuk ILP (12)

• Esensi dari algoritma BB– Bounding– Branching– Fathoming

91

Ilustrasi Penerapan Algoritma BB (1)

92

Maximize Z = 2x1 + 3x2

dengan pembatas-pembatas: 5x1 + 7x2 35

4x1 + 9x2 36 x1, x2 ≥ 0 dan bilangan bulat

Contoh Kasus:

93

LP-1178

176

21712

1

14

2,3

Z

xx

94

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

Contoh Kasus:

95

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-4 LP-5

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

Contoh Kasus:

96

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-4 LP-5

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

Contoh Kasus:

97

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-4 LP-5

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

Contoh Kasus:

98

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-4 LP-5

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

Fathomed karena perbedaannilai Z dengan lower bound < 1dan semua koefisien fungsi tujuan adalah bulat

Solusi bilangan bulatoptimalx1 = 4, x2 = 2Z = 14

Contoh Kasus:

99

LP-1178

176

21712

1

14

2,3

Z

xxPencabangandari LP-3

100

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

101

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

102

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

103

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

LP-6 LP-713

3,2 21

Z

xx

32 x 42 x

12

4,0 21

Z

xx

104

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

LP-6 LP-713

3,2 21

Z

xx

32 x 42 x

12

4,0 21

Z

xx

105

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

LP-6 LP-713

3,2 21

Z

xx

32 x 42 x

12

4,0 21

Z

xx

106

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

LP-6 LP-713

3,2 21

Z

xx

32 x 42 x

12

4,0 21

Z

xx

LP-8 LP-9

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

107

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

LP-6 LP-713

3,2 21

Z

xx

32 x 42 x

12

4,0 21

Z

xx

LP-8 LP-9

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

108

LP-1

LP-2 LP-3

178

176

21712

1

14

2,3

Z

xx

22 x 32 x

21

241

1

13

3,2

Z

xx

52

251

1

14

2,4

Z

xx

LP-5LP-4

21 x 31 x

Tidak layak

31

91

21

13

3,2

Z

xx

LP-6 LP-713

3,2 21

Z

xx

32 x 42 x

12

4,0 21

Z

xx

LP-8 LP-9

41 x 51 x

14

2,4 21

Z

xx

72

73

21

14

1,5

Z

xx

Fathomed karena perbedaannilai Z dengan lower bound < 1dan semua koefisien fungsi tujuan adalah bulat

Aturan Pencabangan (1)

• Aturan-aturan pencabangan variabel adalah sebagai berikut:– Pilih variabel bilangan bulat yang mempunyai nilai pecahan

terbesar dalam solusi LP.– Pilih variabel bilangan bulat yang mempunyai prioritas

paling tinggi.• Menunjukkan keputusan yang terpenting dalam model• Mempunyai koefisien profit/biaya paling besar• Mempunyai nilai yang kritis yang didasarkan pengalaman

pengguna– Aturan pemilihan bebas, misal, pilih variabel bilangan bulat

dengan indeks paling kecil.

109

Aturan Pencabangan (2)

• Aturan penentuan masalah LP yang hendak dicabangkan:– Nilai optimal dari fungsi tujuan– LIFO (Last-In First-Out), yaitu masalah LP yang

dipecahkan paling belakangan.

110

Algoritma BB untuk BILP

111

Maximize Z = 9x1 + 5x2 + 6x3 + 4x4

dengan pembatas-pembatas: 6x1 + 3x2 + 5x3 + 2x4 10 x3 + x4 1 -x1 + x3 0 -x2 + x4 0

x1, x2, x3, x4 = {0, 1}

Algoritma BB untuk BILP

112

Tahap Relaksasi :Maximize Z = 9x1 + 5x2 + 6x3 + 4x4

dengan pembatas-pembatas: 6x1 + 3x2 + 5x3 + 2x4 10 x3 + x4 1 -x1 + x3 0 -x2 + x4 0 x1, x2, x3, x4 ≤ 1 x1, x2, x3, x4 ≥ 0

113

LP-1);,,,( 4321 Zxxxx 21

65 16;1,0,1,

114

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

115

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

116

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

LP-4 LP-5

02 x 12 x

54

54 13;0,,0,1

16;,0,1,1 21

117

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

LP-4 LP-5

02 x 12 x

54

54 13;0,,0,1

16;,0,1,1 21

LP-6 LP-7

03 x 13 x

16;,0,1,1 21

Tidak layak

118

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

LP-4 LP-5

02 x 12 x

54

54 13;0,,0,1

16;,0,1,1 21

LP-6 LP-7

03 x 13 x

16;,0,1,1 21

Tidak layak

LP-8 LP-9 14;0,0,1,1

04 x 14 x

Tidak layak

119

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

LP-4 LP-5

02 x 12 x

54

54 13;0,,0,1

16;,0,1,1 21

LP-6 LP-7

03 x 13 x

16;,0,1,1 21

Tidak layak

LP-8 LP-9 14;0,0,1,1

04 x 14 x

Tidak layak

120

LP-1

LP-2 LP-3

);,,,( 4321 Zxxxx 21

65 16;1,0,1,

01 x11 x

9;1,0,1,0 51

54

54 16;,0,,1

LP-4 LP-5

02 x 12 x

54

54 13;0,,0,1

16;,0,1,1 21

LP-6 LP-7

03 x 13 x

16;,0,1,1 21

Tidak layak

LP-8 LP-9 14;0,0,1,1

04 x 14 x

Tidak layak

121

THANKS