Materi Bahasan. Pemrograman Bilangan Bulat (Integer Programming) Pemrograman Bilangan Bulat. 1 Pengantar Pemrograman Bilangan Bulat

Materi Bahasan ① Pengantar pemrograman bilangan bulat ② Beberapa contoh model pemrograman bilangan bulat ③ Metode pemecahan bilangan bulat

Pemrograman Bilangan Bulat (Integer Programming)

Metode cutting-plane Metode branch-and-bound Metode branch-and-bound untuk pemrograman bilangan bulat biner

Kuliah 11-12

TI2231 Penelitian Operasional I

1


2

Pemrograman Bilangan Bulat • Pemrograman bilangan bulat (integer programming) mensyaratkan bahwa beberapa variabel keputusan harus mempunyai nilai yang bulat (bukan pecahan) • Pembahasan hanya ditujukan untuk masalah pemrograman linier bilangan bulat (integer linear programming problem)

① Pengantar Pemrograman Bilangan Bulat


3


4

Jenis Pemrograman Bilangan Bulat

Fungsi Variabel Biner

• 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)

• Penangangan pembatas either-or • Penanganan nilai lebih dari satu yang mungkin dari suatu pembatas • Representasi bentuk lain dari variabel bilangan bulat


5

Pembatas Either-Or

f ( x1 , x2 , L , xn ) = d1 atau d 2 atau L atau d N

x1 + 4 x2 ≤ 16 Perumusan PLBB:

PL format: 3 x1 + 2 x2 ≤ 18 dan x1 + 4 x2 ≤ 16 + M atau

6

Fungsi dengan N Nilai yang Mungkin (1)

3 x1 + 2 x2 ≤ 18

atau


3 x1 + 2 x2 ≤ 18 + M dan x1 + 4 x2 ≤ 16 TI2231 Penelitian Operasional I

N

f ( x1 , x2 ,L , xn ) = ∑ d i yi

3 x1 + 2 x2 ≤ 18 + My

i =1

N

x1 + 4 x2 ≤ 16 + M (1 − y ) yi = {0,1}

∑y i =1

i

=1

yi = {0,1}, 7

i = 1,2,L , N


8

Representasi Biner untuk Variabel Bilangan Bulat (1)

Fungsi dengan N Nilai yang Mungkin (2)

Batas-batas untuk variabel x: 3 x1 + 2 x2 = 6 atau 12 atau 18

0 ≤ x ≤ u dimana 2 N ≤ u ≤ 2 N +1

Perumusan PLBB: Representasi biner:

3 x1 + 2 x2 = 6 y1 + 12 y2 + 18 y3

N

x = ∑ 2 i yi

y1 + y2 + y3 = 1 yi = {0,1},

i =0

yi = {0,1},

i = 1,2,3


9

i = 1,2, L , N


10

Representasi Biner untuk Variabel Bilangan Bulat (2) x1 ≤ 5 2 x1 + 3 x2 ≤ 30

u untuk x1 = 5 Æ 22 ≤ 5 ≤ 23

x1, x2 bil. bulat

u untuk x2 = 10 Æ 23 ≤ 10 ≤ 24

② Beberapa Contoh Model Pemrograman Bilangan Bulat

Representasi biner:

y0 + 2 y1 + 4 y2 ≤ 5

2( y0 + 2 y1 + 4 y2 ) + 3(w0 + 2 w1 + 4 w2 + 8w3 ) ≤ 30 yi = {0,1}, wi = {0,1},

i = 0,1,2 i = 0,1,2,3 TI2231 Penelitian Operasional I

11


12

Beberapa Contoh Model-model Pemrograman Bilangan Bulat

Misalkan terdapat n jenis produk pj = 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

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

• Traveling salesman problem • Job (Machine) scheduling problem


13

Fixed Charge Problem (2)


14


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 produk diputuskan untuk tidak diproduksi maka jumlah produksinya nol. Variabel keputusan : xj = jumlah produk j yang diproduksi = keputusan untuk memproduksi atau tidak produk j; yj yj = 1 jika produk j diproduksi yj = 0 jika produk j tidak diproduksi TI2231 Penelitian Operasional I


Maksimasi Z = ∑ p j x j − ∑ (K j y j + c j x j ) n

n

j =1

j =1

dengan pembatas-pembatas: n

∑a x j =1

ij

j

≤ bi , i = 1, L , m

x j ≤ My j , x j ≥ 0,

j = 1, L , n

y j = {0,1},

15

j = 1, L , n

j = 1,..., n


16

Knapsack Problem (1)

Knapsack Problem (2)

Misalkan terdapat n item. wj = berat item j vj = nilai item j W = kapasitas muatan (berat) dari kantong

n

Maksimasi

j =1

dengan pembatas-pembatas:

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

n

∑w x j =1


17

Set Covering Problem (1)

Jalan H

3 Jalan K

Jalan I

Jalan C

4

Jalan E 6

Jalan B

5



18

Misalkan terdapat n lokasi pendirian pos dan m jalan. cj = biaya mendirikan pos di lokasi j = konstanta biner (0-1) aij aij = 1 jika jalan i dilayani oleh pos yang berlokasi di j aij = 0 jika sebaliknya

Variabel keputusan xj = variabel biner (0-1) yang menentukan keputusan untuk mendirikan pos di lokasi j (xj = 1 jika pos dididikan di lokasi j, xj = 0 sebaliknya)

Jalan D

7

≤W

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

Jalan J

Ja la n

F

Jalan G

2

j

Set Covering Problem (2)

Contoh masalah set covering problem dalam menentukan lokasi pendirian pos siskamling Jalan A

j

x j ≥ 0 dan bilangan bulat

Variabel keputusan : xj = jumlah item yang dimasukkan ke kantong

1

Z = ∑vjxj

8 19


20

Set covering problem (3)

Set Partitioning Problem

n

Z = ∑cjxj

Minimasi

Z = ∑cjxj

Minimasi

j =1

j =1


∑a x j =1

ij

j

≥ 1,


∑a x

i = 1,..., m

j =1

x j = {0,1},

ij

j

= 1,

i = 1,..., m

x j = {0,1},

j = 1,..., n


21

Traveling Salesman Problem (1)

j = 1,..., n


22

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

2

5

Tiap jalan tepat dilayani oleh satu pos

n

3 8

6

1

Permasalahan Menentukan 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

3 3

7

6

4 (jarak)

2 5

1

Variabel keputusan xij = keputusan untuk melintasi atau tidak busur (i, j) xij = 1 jika busur (i, j) dilintasi xij = 0 jika busur (i, j) tidak dilintas

4


23


24

Traveling Salesman Problem (3) n


n

Z = ∑∑ cij xij

Minimasi

2

j =1 j =1

Subtour


∑x j =1 n

ij

∑x i =1

ij

1 3

= 1, i = 1, L , n

= 1,

Subtour breaking constraint

j = 1, L , n

ui − u j + nxij ≤ n − 1,

5

i = 2, L , n; j = 2, L , n; i ≠ j

4

xij = {0,1}, i = 1, L , n; j = 1, L n

ui ≥ 0,

Subtour breaking constraint bertujuan untuk mengeliminasi terjadinya solusi subtour

i = 1,..., n


25


26

Job Scheduling Problem (1) Misalkan -terdapat n job dengan operasi-tunggal -terdapat satu mesin tunggal = waktu pengerjaan job j pj = bobot kepentingan job j wj

2

Tour 1 3

5 4

Suatu solusi traveling salesman problem yang layak (terbentuknya suatu tour). TI2231 Penelitian Operasional I


27

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) TI2231 Penelitian Operasional I

28

Job Scheduling Problem (2)

Job Scheduling Problem (3) n

Minimasi

Variabel keputusan: = saat awal pengerjaan job j Bj Cj = saat akhir pengerjaan job j = keputusan apakah job i mendahului job j yij yij = 1 jika job i mendahului job j yij = 0 jika sebaliknya

0

Z = ∑ w jC j j =1

dengan pembatas-pembatas:

Cj ≥ pj,

i = 1, L , n

Disjunctive constraint (Either-or constraint)

C j − Ci + M (1 − yij ) ≥ pi , i = 1, L , n; j = 1, L n, i ≠ j

p3

p1

p4

p5

p2

3

1

4

5

2

Ci − C j + Myij ≥ p j , i = 1, L , n; j = 1, L n; i ≠ j C j ≥ 0,

yij = {0,1},

Bj = C j − p j ,

Suatu solusi (jadwal) pengerjaan job yang layak TI2231 Penelitian Operasional I

i = 1,..., n

29

i = 1,..., n, j = 1, L n

i = 1, L , n


30

Metode Pemecahan Model Pemrograman Bilangan Bulat • Cutting method

③ Metode Pemecahan Model Pemrograman Bilangan Bulat


– Cutting Plane

• Search method – Branch and Bound

31


32

Algoritma Cutting Plane

Ilustrasi Suatu Masalah PLBB

• Dikembangkan oleh R.E. Gomory • Algoritma

Maximasi Z = 7x1 + 9x2

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


x2

33

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


34

Solusi Optimal Kontinyu

Daerah layak

x2 (dengan mengabaikan kondisi integralitas) ( x1 , x2 ) = (4 12 ,3 12 ) Z = 63

x1 TI2231 Penelitian Operasional I

35


36

x1

Ide Dasar dari Cutting Plane

x2

• 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.

Penambahan Pembatas Sekunder ( x1 , x2 ) = (4,3) Z = 55

secondary constraint


37


Fractional Algorithm (2)


Tabel akhir optimal untuk PL

• Digunakan untuk memecahkan masalah pemrograman linier bilangan bulat murni (PILP). • Mensyaratkan bahwa semua koefisien teknologi dan konstanta ruas kanan adalah bilangan bulat. 1 13 x1 + x2 ≤ 3 2

6 x1 + 2 x2 ≤ 39

• Pada awalnya, masalah PILP dipecahkan sebagai PL reguler, yaitu dengan mengabaikan kondisi integralitas. TI2231 Penelitian Operasional I

38

39

Basis

x1

xi

xm

w1

wj

wn

Solusi

x1

1

0

0

α11

α1j

α1n

β1

xi

0

1

0

αi1

αij

αin

βn

xm

0

0

1

α m1

α mj

α mn

βm

cj

0

0

0

c1

cj

cn

β0


40



Variabel xi (i = 1, …, m) menunjukkan variabel basis Variabel wj (j = 1, …, n) menunjukkan variabel non basis Misalkan persamaan ke-i dimana variabel xi diasumsikan bernilai bilangan bulat n

xi = β i − ∑ α i j w j , j =1

β i bukan bilangan bulat (baris sumber)


α i j = [α i j ]+ f ij

dimana N = [a] adalah bilangan bulat terbesar sehingga N ≤ a 0 < fi < 1 0 ≤ fij < 1


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

∑f

[ ]

f i − ∑ f ij wi = xi − [β i ] + ∑ α i j w j j =1

j =1

j =1

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


42


Dari baris sumber diperoleh: n

β i = [β i ] + f i

41


n

Misal:

43

ij

wj ≥ 0

Akibatnya n

f i − ∑ f ij w j ≤ f i j =1


44


Fractional Algorithm (8) Pertidaksamaan terakhir dapat dijadikan sebagai pembatas dalam bentuk:

Karena fi < 1 maka n

f i − ∑ f ij w j < 1

n

Si = ∑ f ij w j − f i

j =1

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

(fractional cut)

j =1

n

f i − ∑ f ij w j ≤ 0 j =1


45


46


Tabel setelah penambahan fractional cut Basis

x1

xi

xm

w1

wj

wn

Si

Solusi

x1

1

0

0

α11

α1j

α1n

0

β1

xi

0

1

0

αi1

αi j

αin

0

βn

xm

0

0

1

αm 1

αm j

αm n

0

βm

Si

0

0

0

-fi1

-fij

-fim

1

-fi

cj

0

0

0

c1

cj

cn

0

β0



47

• 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.


48



Kekuatan fractional cut n

∑ j =1

∑f

max{ f i } i

n

j =1

Aturan :

f ij w j ≥ f i kj

wj ≥ fk

⎫ ⎧ ⎪ f ⎪ ⎪ ⎪ max ⎨ n i ⎬ i ⎪ ∑ f ij ⎪ ⎪⎩ j =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 TI2231 Penelitian Operasional I

49

Contoh Penerapan Fractional Algorithm (1)


50


Tabel optimal kontinyu Maximasi Z = 7x1 + 9x2 dengan pembatas-pembatas: –x1 + 3x2 ≤ 6 7x1 + x2 ≤ 35 x1, x2 ≥ 0 dan bilangan bulat


51

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


52

Contoh Penerapan Fractional Algorithm (3) Baris sumber Æ persamaan-x2

Tabel setelah penambahan fractional cut

7 1 7 x2 + x3 + x4 = 22 22 2

7 ⎞ 1 ⎞ 1⎞ ⎛ ⎛ ⎛ x2 + ⎜ 0 + ⎟ x3 + ⎜ 0 + ⎟ x4 = ⎜ 3 + ⎟ 2⎠ 22 ⎠ 22 ⎠ ⎝ ⎝ ⎝

Fractional cut: S1 −


7 1 1 x3 − x4 = − 22 22 2 TI2231 Penelitian Operasional I

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

53



Contoh Penerapan Fractional Algorithm (6) Baris sumber Æ persamaan-x1

Tabel yang diperoleh dengan dual simplex:

x1 +

1 1 4 x4 − S1 = 4 7 7 7

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

Fractional cut:

cj – zj

0

0

0

-1

-8

Z = 59

S2 −


54

55

1⎞ 6⎞ 4⎞ ⎛ ⎛ ⎛ x1 + ⎜ 0 + ⎟ x4 + ⎜ − 1 + ⎟ S1 = ⎜ 4 + ⎟ 7⎠ 7⎠ 7⎠ ⎝ ⎝ ⎝

1 6 4 x4 − S1 = − 7 7 7 TI2231 Penelitian Operasional I

56



Tabel setelah penambahan fractional cut

Tabel yang diperoleh dengan dual simplex:

Basis

x1

x2

x3

x4

S1

S2

Solusi

Basis

x1

x2

x3

x4

S1

S2

Solusi

x2

0

1

0

0

1

0

3

x2

0

1

0

0

1

0

3

x1

1

0

0

1/7

-1/7

0

4 4/7

x1

1

0

0

0

-1

1

4

x3

0

0

1

1/7

-22/7

0

1 4/7

x3

0

0

1

0

-4

1

1

S2

0

0

0

-1/7

-6/7

1

-4/7

x4

0

0

0

1

6

-7

4

cj – zj

0

0

0

-1

-8

0

cj – zj

0

0

0

-2

-7

0

Z = 55

Solusi bilangan bulat optimal, x1 = 4, x2 = 3; Z = 55 TI2231 Penelitian Operasional I

57

Ilustrasi Fractional Cut secara Grafis (1)


58


x2

Fractional cut 1: S1 −

7 1 1 x3 − x4 = − 22 22 2 x2 = 3

S1 −

7 (6 + x1 − 3x2 ) − 1 (35 − 7 x1 − x2 ) = − 1 22 22 2

S1 + x2 = 3

x1

x2 ≤ 3 TI2231 Penelitian Operasional I

59


60



x2

Fractional cut 2: S2 −

1 6 4 x4 − S1 = − 7 7 7 x2 = 3

S2 −

1 (35 − 7 x1 − x2 ) − 6 (3 − x2 ) = − 4 7 7 7

S 2 + x1 + x2 = 7

x1 + x2 = 7

x1 + x2 ≤ 7


61

62

Mixed Algorithm (3)

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

Maximasi Z = 7x1 + 9x2

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



63

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


64

Mixed Algorithm (3)

Mixed Algorithm (4)

Misal xk adalah variabel bilangan bulat dari masalah MILP.

xk ≤ [β k ] atau xk ≥ [β k ] + 1

Persamaan-xk dalam solusi kontinyu optimal: n

harus dipenuhi

xk = β k − ∑ α kj w j j =1

Untuk xk adalah bilangan bulat, maka

n

xk = [β k ] + f k − ∑ α kj w j

Dari baris sumber, kondisi ini ekivalen dengan

(baris sumber)

n

j =1 n

xk − [β k ] = f k − ∑ α w j j =1

j k

∑α

j k

wk ≥ f k

(1)

∑α

j k

wk ≤ f k − 1

(2)

j =1 n

j =1


65

Mixed Algorithm (5) Misal

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

⎧⎪ n j f k n j ⎫⎪ S k − ⎨ ∑ α k wk + ∑ α k wk ⎬⎪ = − f k (mixed cut) f k − 1 j∈J − ⎪⎩ j∈J + ⎭

Dari (1) dan (2) diperoleh

∑α

wk ≥ f k

(1)

fk α kj wk ≥ f k ∑ f k − 1 j∈J −

(2)

j∈J n

+

j k


66

Mixed Algorithm (6)

J+ = himpunan subscripts j untuk αkj ≥ 0 J- = himpunan subscripts j untuk αkj < 0

n


67


68

Contoh Penerapan Mixed Algorithm (1)

Tabel optimal kontinyu:

Maximasi Z = 7x1 + 9x2 dengan pembatas-pembatas: –x1 + 3x2 ≤ 6 7x1 + x2 ≤ 35 x1 ≥ 0 dan bilangan bulat x2 ≥ 0



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

69



70


Baris sumber Æ persamaan-x1 x1 −

Tabel setelah penambahan mixed cut

1 3 1⎞ ⎛ x3 + x4 = ⎜ 4 + ⎟ 22 22 2⎠ ⎝

J = {3}, J = {4}, −

+

f1 =

1 2

Mixed cut:

⎛ 12 ⎞⎛ 1 ⎞ 1 ⎛ 3 ⎞ S1 − ⎜ ⎟ x4 + ⎜⎜ 1 ⎟⎟⎜ − ⎟ x3 = − 2 ⎝ 22 ⎠ ⎝ 2 − 1 ⎠⎝ 22 ⎠ 1 3 1 S1 − x3 − x4 = − 22 22 2 TI2231 Penelitian Operasional I

71

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


72

Contoh Penerapan Mixed Algorithm (5) Tabel yang diperoleh dengan dual simplex: 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

Solusi optimal, x1 = 4, x2 = 10/3; Z = 55 TI2231 Penelitian Operasional I

73

Algoritma Branch-and-Bound (2)

Algoritma Branch-and-Bound (1) • Metode yang paling banyak digunakan dalam praktek 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. TI2231 Penelitian Operasional I

74

Algoritma BB untuk PLBB (1)

• Algoritma BB untuk PLBB (Murni & Campuran) • Algoritma BB untuk PLBB Biner

Misalkan diberikan suatu masalah pemrograman bilangan bulat sebagai berikut: Maksimasi Z = cx dengan pembatas Ax = b x≥0 xj bilangan bulat untuk j ∈ I dimana I adalah himpunan variabel bilangan bulat


75


76



• Langkah pertama adalah memecahkan masalah PLBB sebagai PL dengan mengabaikan pembatas bilangan bulat (bounding) • Misalkan masalah PL dinyatakan sebagai PL-1 yang mempunyai nilai optimal dari fungsi tujuan Z1. PL-1 Maksimasi Z = cx dengan pembatas Ax = b x≥0 TI2231 Penelitian Operasional I

77



78


• Misalkan variabel xj dipilih untuk dicabangkan dengan nilai pecahan βj dalam PL-1. • Misalkan dibuat dua masalah pemrograman linier baru, PL-2 dan PL-3 dengan memasukkan masing-masing pembatas baru xj ≤ [β] dan xj ≥ [β]+1


• Asumsikan bahwa solusi optimal dari PL-1 mengandung beberapa variabel bilangan bulat yang mempunyai nilai pecahan. • Oleh karena itu, solusi optimal bilangan bulat untuk PLBB belum diperoleh dan Z1 menjadi batas atas (upper bound) dari nilai maksimum Z untuk PLBB. • Langkah berikutnya adalah mempartisi daerah layak dari PL-1 dengan mencabangkan (branching) salah satu variabel bilangan bulat yang nilainya pecahan

79

PL-2

PL-3

Maksimasi Z = cx dengan pembatas Ax = b xj ≤ [β] x≥0

Maksimasi Z = cx dengan pembatas Ax = b xj ≥ [β]+1 x≥0


80


PL-1


Solusi pecahan Z1

x j ≤ [β j ]

x j ≤ [β j ] + 1 Solusi pecahan

Solusi pecahan PL-2 Z2

PL-2 Z5


81



82


• Setelah masalah PL dipilih untuk dicabangkan lebih lanjut, langkahnya selanjutnya adalah – memilih variabel bilangan bulat dengan nilai pecahan yang akan dicabangkan untuk membentuk dua masalah PL baru (proses branching) – memecahkan masalah PL yang baru (proses bounding)

• Jika solusi bilangan bulat diperoleh dari suatu masalah PL maka nilai Z-nya menjadi batas bawah (lower bound) dari nilai maksimum Z untuk masalah PLBB. TI2231 Penelitian Operasional I

• Memecahkan (bounding) PL-2 dan PL-3 • Asumsikan solusi PL-2 dan PL-3 masih pecahan • Langkah berikutnya adalah memilih node (masalah PL) yang akan dicabangkan.

• Proses branching dan bounding berlanjut hingga semua node dalam kondisi fathomed. • Fathoming suatu node (masalah PL): – Solusi optimal PL merupakan bilangan bulat – Masalah PL adalah tak layak – Nilai optimal Z dari masalah PL tidak lebih baik daripada • batas bawah (lower bound) saat ini untuk masalah maksimisasi • batas atas (upper bound) saat ini untuk masalah minimisasi

83


84

Algoritma BB untuk PLBB (10) PL-1

Solusi pecahan Z0 = Z1

x j ≤ [β j ] Solusi pecahan PL-2 Z2 xi ≤ [ β i ]

PL-3

Algoritma BB untuk PLBB (11) PL-1

x j ≤ [β j ] + 1

x j ≤ [β j ] Solusi pecahan

PL-3 Z5 xi ≤ [ β i ] + 1

Tidak layak TI2231 Penelitian Operasional I

Solusi pecahan PL-2 Z2 xi ≤ [ β i ]

PL-3

PL-4

Solusi bulat Z4

Solusi pecahan Z0 = Z1


Solusi pecahan

PL-5 Z5 xi ≤ [ β i ] + 1

PL-4

Solusi bulat Z4 85

x j ≤ [β j ] + 1

Tidak layak

xk ≤ [ β k ]

PL-6

xk ≤ [ β k ] + 1 Solusi pecahan PL-7 Z7 > Z4

Solusi pecahan Z6 < Z4


86

Contoh Penerapan Algoritma BB (1)

• Esensi dari algoritma BB – Bounding – Branching – Fathoming

Maximasi Z = 2x1 + 3x2 dengan pembatas-pembatas: 5x1 + 7x2 ≤ 35 4x1 + 9x2 ≤ 36 x1, x2 ≥ 0 dan bilangan bulat


87


88

PL0

PL1

X2

Maximasi Z = 2x1 + 3x2 dengan pembatas-pembatas: 5x1 + 7x2 ≤ 35 4x1 + 9x2 ≤ 36 x1, x2 ≥ 0

12 x1 = 3 17 , x2 = 2 176

Z = 14 178

X1


89



90

PL2

12 x1 = 3 17 , x2 = 2 176

Z = 14 178

PL-1

Maximasi Z = 2x1 + 3x2 dengan pembatas-pembatas: X2 5x1 + 7x2 ≤ 35 4x1 + 9x2 ≤ 36 5 x2 < 2 4 x1, x2 ≥ 0

x1 = 4 15 , x2 = 2 Z = 14 52

Feasible Solution Area 0


91


7

X1

9

92

PL3

Contoh Penerapan Algoritma BB (3) 12 x1 = 3 17 , x2 = 2 176

Maximasi Z = 2x1 + 3x2 dengan pembatas-pembatas: X 5x1 + 7x2 ≤ 35 4x1 + 9x2 ≤ 36 5 x2 > 3 4 x1, x2 ≥ 0

Z = 14 178

x2 ≤ 2

x1 = 4 15 , x2 = 2 Z = 14 52

2

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-2

PL-3

Z = 13 12

Feasible Solution Area

x1 = 2 14 , x2 = 3 Z = 13 12

0

7

X1

9


93


PL4 Maximasi Z = 2x1 + 3x2 dengan pembatas-pembatas: 5x1 + 7x2 ≤ 35 4x1 + 9x2 ≤ 36 x2 < 2 x1 < 4 x1, x2 ≥ 0

PL-1

94

PL5 Maximasi Z = 2x1 + 3x2 dengan pembatas-pembatas: 5x1 + 7x2 ≤ 35 X 4x1 + 9x2 ≤ 36 5 x2 < 2 4 x1 > 5 x1, x2 ≥ 0

X2

2

5 4 x1 = 4, x2 = 2 Z = 14

x1 = 5, x2 = 1 73

Feasible Solution Area 0


7

9

X1

95

Z = 14 72

0


FSA 7

9

X1

96


x1 = 4 , x2 = 2 Z = 14 52

12 x1 = 3 17 , x2 = 2 176

12 x1 = 3 17 , x2 = 2 176

Z = 14

Z = 14 178

8 17

x2 ≤ 2

1 5

PL-1

x2 ≥ 3

PL-2

x1 ≤ 4


x1 = 2 , x2 = 3 1 4

PL-3

Z = 13

1 2

x1 = 4 , x2 = 2 Z = 14 52

x1 ≥ 5

PL-4

Z = 14

Z = 14


x2 ≤ 2

x1 = 4 15 , x2 = 2 Z = 14 52

PL-4 x1 = 4, x2 = 2 Z = 14

Z = 14 72


Z = 14 178

Z = 14 178 x1 = 2 , x2 = 3

x1 = 4 , x2 = 2

Z = 13 12

Z = 14 52

1 4

PL-3

x2 ≤ 2

1 5

PL-4

PL-5

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-3

Z = 13 12

x1 ≥ 5 PL-5

x1 = 5, x2 = 1 73

x1 = 4, x2 = 2

Z = 14 72

Z = 14

99

PL-1

PL-2

x1 ≤ 4

x1 ≥ 5


98


x2 ≥ 3

Z = 13 12

x1 = 5, x2 = 1 73

12 x1 = 3 17 , x2 = 2 176

PL-2

x1 ≤ 4

PL-3

97

Contoh Penerapan Algoritma BB (6) PL-1

x1 = 2 14 , x2 = 3

PL-5

x1 = 4, x2 = 2

Z = 14 72

x2 ≥ 3

x1 ≥ 5

PL-4

x1 = 5, x2 = 1 73

PL-1

PL-2

x1 ≤ 4

PL-5

x1 = 4, x2 = 2

x2 ≤ 2

1 5

x1 = 5, x2 = 1 73 Z = 14 2

7 perbedaan Fathomed karena nilai Z dengan lower bound < 1 dan semua koefisien fungsi tujuan adalah bulat


Solusi bilangan bulat optimal x1 = 4, x2 = 2 Z = 14 100

Solusi Optimal


X2

Pencabangan dari PL-3

Z = 14 178

PL-1

x1 = 4, x2 = 2 Z = 14

X1


101




12 x1 = 3 17 , x2 = 2 176

Z = 14 178

x2 ≤ 2

x1 = 4 15 , x2 = 2 Z = 14 52

PL-1

PL-2

102

Z = 14 178

x2 ≥ 3

x1 = 2 , x2 = 3

x1 = 4 , x2 = 2

Z = 13 12

Z = 14 52

1 4

PL-3

x2 ≤ 2

1 5

PL-1

x2 ≥ 3

PL-2

x1 = 2 14 , x2 = 3

PL-3 x1 = 2, x2 = 3 19 Z = 13 13

x1 ≤ 2 PL-4

Z = 13 12

x1 ≥ 3 PL-5 Tidak layak


103


104


x1 = 4 , x2 = 2 Z = 14 52

12 x1 = 3 17 , x2 = 2 176

12 x1 = 3 17 , x2 = 2 176

Z = 14

Z = 14 178

8 17

x2 ≤ 2

1 5


PL-1

x2 ≥ 3

x1 = 2 , x2 = 3 1 4

PL-2

PL-3 x1 = 2, x2 = 3 19 Z = 13 13

x1 ≤ 2

Z = 13 12

x2 ≤ 2

x1 = 4 15 , x2 = 2 Z = 14 52

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-2

PL-3

x1 ≥ 3

PL-4

PL-1

x1 = 2, x2 = 3 19 Z = 13 13

PL-5 Tidak layak

x1 = 2, x2 = 3 Z = 13

x1 ≤ 2

Z = 13 12

x1 ≥ 3

PL-4

PL-5

x2 ≤ 3

x2 ≥ 4

PL-6

PL-7 x = 0, x = 4 1 2

Tidak layak

Z = 12


105




12 x1 = 3 17 , x2 = 2 176

Z = 14

x2 ≤ 2

x1 = 4 15 , x2 = 2 Z = 14 52

8 17

12 x1 = 3 17 , x2 = 2 176

PL-1

Z = 14 178

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-2

PL-3 x1 = 2, x2 = 3 19 Z = 13 13

x1 = 2, x2 = 3 Z = 13

106

x1 ≤ 2

Z = 13 12

x1 ≥ 3

PL-4

PL-5

x2 ≤ 3

x2 ≥ 4

PL-6

PL-7 x = 0, x = 4 1 2

x1 = 4 , x2 = 2 Z = 14 52

PL-1

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-2

PL-3 x1 = 2, x2 = 3 19 Z = 13 13

Tidak layak

Z = 12


x2 ≤ 2

1 5

x1 = 2, x2 = 3 Z = 13

x1 ≤ 2

Z = 13 12

x1 ≥ 3

PL-4

PL-5

x2 ≤ 3

x2 ≥ 4

PL-6

PL-7 x = 0, x = 4 1 2

Tidak layak

Z = 12

107


108



12 x1 = 3 17 , x2 = 2 176

Z = 14 178

x2 ≤ 2

x1 = 4 , x2 = 2 1 5

Z = 14 52

Z = 14 178

PL-1

x2 ≥ 3

PL-2

x1 ≤ 4

PL-3

x1 ≥ 5

PL-8

x1 = 2, x2 = 3 19 Z = 13 13

PL-9

x1 = 4, x2 = 2 Z = 14

Z = 14

x1 ≤ 2

2 7

x1 = 2, x2 = 3 Z = 13

x1 = 4 , x2 = 2

Z = 13 12

Z = 14 52

x1 ≥ 3

PL-4

PL-5

x2 ≤ 3

x1 = 5, x2 = 1 73

x1 = 2 , x2 = 3 1 4

x2 ≥ 4

Tidak layak

PL-7 x = 0, x = 4 1 2

PL-1

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-2

x1 ≤ 4 PL-8 x1 = 4, x2 = 2 Z = 14

PL-6

x2 ≤ 2

1 5

PL-3

x1 ≥ 5 PL-9

x1 = 2, x2 = 3 19 Z = 13 13

x1 = 5, x2 = 1 73 Z = 14

2 7

x1 = 2, x2 = 3 Z = 13

x1 ≤ 2

x1 ≥ 3

PL-4

PL-5

x2 ≤ 3

x2 ≥ 4

PL-6

PL-7 x = 0, x = 4 1 2

109


Tidak layak

Z = 12

Z = 12


Z = 13 12


110

Aturan Pencabangan (1)

12 x1 = 3 17 , x2 = 2 176

Z = 14 178

x2 ≤ 2

x1 = 4 15 , x2 = 2 Z = 14 52

x2 ≥ 3

x1 = 2 14 , x2 = 3

PL-2

x1 ≤ 4 PL-8

PL-3

x1 ≥ 5

x1 = 2, x2 = 3 19 Z = 13 13

PL-9

x1 = 4, x2 = 2 Z = 14

PL-1

x1 = 5, x2 = 1 73 Z = 14 72

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

x1 = 2, x2 = 3 Z = 13

x1 ≤ 2

Z = 13 12

x1 ≥ 3

PL-4

PL-5

x2 ≤ 3

x2 ≥ 4

PL-6

PL-7 x = 0, x = 4 1 2


Tidak layak

Z = 12

111

• Aturan-aturan pencabangan variabel adalah sebagai berikut: – Pilih variabel bilangan bulat yang mempunyai nilai pecahan terbesar dalam solusi PL. – 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 TI2231 Penelitian Operasional I

112

Aturan Pencabangan (2)

Contoh Algoritma BB untuk PLBB Biner (1)

• Aturan penentuan masalah PL yang hendak dicabangkan:

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

– Nilai optimal dari fungsi tujuan – LIFO (Last-In First-Out), yaitu masalah PL yang dipecahkan paling belakangan.


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

113

Contoh Algoritma BB untuk PLBB Biner (2) ( x1 , x2 , x3 , x4 ; Z )

PL-1

( 56 ,1,0,1;16 12 )



PL-1

x1 = 0

(0,1,0,1;9)


115

114

( 56 ,1,0,1;16 12 ) x1 = 1

PL-2

PL-3


(1, 54 ,0, 54 ;16 15 )

116


PL-1

x1 = 0

(0,1,0,1;9)

( 56 ,1,0,1;16 12 )

( x1 , x2 , x3 , x4 ; Z )

PL-1

x1 = 0

x1 = 1

PL-2


PL-3

(1,

4 5

4 5

,0, ;16

1 5

)

(0,1,0,1;9)

( 56 ,1,0,1;16 12 ) x1 = 1

PL-2

PL-3

(1, 54 ,0, 54 ;16 15 )

x2 = 0

(1,0,


117


PL-1

x1 = 0

(0,1,0,1;9)

( 56 ,1,0,1;16 12 ) (1,

x2 = 0

(1,0,

,0;13

4 5

)

4 5

,0, ;16

1 5

)

)

(1,1,0,

1 2

;16 )

PL-6

PL-4

PL-5

118

Contoh Algoritma BB untuk PLBB Biner (7) PL-1

( 56 ,1,0,1;16 12 ) x1 = 1

PL-2

PL-3

Tidak layak 119

(1, 54 ,0, 54 ;16 15 )

x2 = 0

(1,0,

4 5

,0;13

4 5

)

x2 = 1

PL-4

(1,1,0, 12 ;16)

PL-5

x3 = 0

x3 = 1 PL-7

(1,1,0, 12 ;16)


(0,1,0,1;9)

PL-5

x3 = 0

(1,1,0, 12 ;16)

4 5

x2 = 1

PL-4


4 5

x1 = 0 PL-3

4 5

,0;13

( x1 , x2 , x3 , x4 ; Z )

x1 = 1

PL-2

4 5

x2 = 1

(1,1,0, 12 ;16) (1,1,0,0;14)

x3 = 1

PL-6

PL-7

x4 = 0

x4 = 1

PL-8

PL-9


Tidak layak

Tidak layak

120


PL-1

x1 = 0

(0,1,0,1;9)

( 56 ,1,0,1;16 12 )

( x1 , x2 , x3 , x4 ; Z )

PL-3

(1,

x2 = 0

(1,0,

,0;13

4 5

)

4 5

4 5

,0, ;16

x2 = 1

PL-4

1 5

)

(1,1,0,

(0,1,0,1;9) 1 2

;16 )

PL-5

x3 = 0

(1,1,0, 12 ;16) (1,1,0,0;14)

PL-1

x1 = 0

x1 = 1

PL-2

4 5


x1 = 1

PL-2

PL-3

PL-6

PL-7

x4 = 1

PL-8

PL-9

Tidak layak

Tidak layak

121

(1, 54 ,0, 54 ;16 15 )

x2 = 0

(1,0,

4 5

,0;13

4 5

)

x2 = 1

PL-4

(1,1,0, 12 ;16)

PL-5

x3 = 0

x3 = 1

x4 = 0


( 56 ,1,0,1;16 12 )

(1,1,0, 12 ;16) (1,1,0,0;14)

x3 = 1

PL-6

PL-7

x4 = 0

x4 = 1

PL-8

PL-9


Tidak layak

Tidak layak

122

Materi Bahasan. Pemrograman Bilangan Bulat (Integer Programming) Pemrograman Bilangan Bulat. 1 Pengantar Pemrograman Bilangan Bulat

Recommend Documents