Penelitian Operasional II Program Bilangan Bulat PROGRAM BILANGAN BULAT (INTEGER PROGRAMMING)

Penelitian Operasional II

Program Bilangan Bulat 37

3. PROGRAM BILANGAN BULAT (INTEGER PROGRAMMING)

3.1 PENDAHULUAN : Formulasi Program Bilangan Bulat dan Aplikasinya Program Linear (LP) Program Linear biasa diformulasikan secara matematis dengan cara sebagai berikut : (LP) max cX kendala : AX ≤b X ≥0 atau secara singkat dapat dituliskan menjadi : max { cX : AX ≤ b, X ∈ R+n } Program Linear Bilangan Bulat Linear Integer Programming (ILP) Program linear bilangan bulat memiliki formulasi mirip dengan (LP) hanya saja kendala bahwa peubah bebasnya merupakan bilangan real positif diubah menjadi bilangan bulat positif, yaitu : (ILP) max cX kendala : AX ≤b X ≥0 X Bilangan Bulat Atau secara singkat dapat dituliskan menjadi : max { cX : AX ≤ b, X ∈ Z+n } Bila batasan bahwa X harus merupakan bilangan bulat diubah menjadi X ∈ {0,1}, maka permasalahan ini menjadi Program Linear Bilangan Biner (Linear Binary Integer Programming – LBIP) Program Linear Bilangan Bulat Campuran Linear Mixed Integer Programming (MIP) Bila sebagian dari permasalahan memerlukan pemecahan dalam bilangan real dan sebagian lagi dalam bilangan bulat, maka model matematik yang harus dibuat merupakan campuran dari (LP) dan (ILP) , ini sebut sebagai (MIP), yaitu : (MIP) max { cX + hY: AX + G Y ≤ b, X ∈ Z+n , Y ∈ R+n } dimana A : matriks berukuran m x n G : matriks berukuran m x p c : vektor berukuran n h : vektor berukuran p b : vektor berukuran m Penyelesaian dari (MIP) merupakan penyelesaian yang layak bila penyelesaian ini berada dalam himpunan layak : S = { (x,y) : x ≥ 0, y ≥ 0, x integer, A x + G y ≤ b } Siana Halim – T.Industri – UK. Petra



Dan penyelesaiannya dikatakan optimal bila: (xo, yo) ∈ S sedemikian hingga ∀(x,y) ∈S : c x + h y ≤ c xo + h yo (MIP) dikatakan tak terbatas (unbounded) jika : ∀ L ∈ R; ∃ (x,y ) ∈ S : c x + h y > L Beberapa aplikasi khusus dalam (LP) selalu memperoleh penyelesaian bilangan bulat yang optimal, misalnya : malalah aliran pada jaringan pipa (Network – Flow), Matching TETAPI secara umum hal ini TIDAK BENAR !!! Contoh 3.1 : S .

.

.

.

Peny. Optimal (IP) . . .

.

.

.

.

.

.

.

. Peny. Optimal (LP) .

.

.

.

.

.

.

.

.

|

|

|

|

|

|

|

Contoh 3.2 : Masalah Ransel (Knapsack Problem, 0-1) Masalah ini diilhami dari seorang petualangan yang hendak bepergian dengan membawa satu ransel. Dia harus menentukan barang-barang apa saja yang hendak dibawanya dengan mengingat kapasitas dari ransel yang mampu disandangnya terbatas. Selain itu masalah ini juga dikenal dengan permasalah dengan satu fungsi tujuan dan satu kendala saja, karena itu ia memerlukan penyelesaian khusus. Pada dunia industri hal ini seringkali muncul ketika orang hendak menentukan proyek apa yang harus dikerjakan jika diketahui bahwa anggaran total yang dimilikinya terbatas. Permasalahan ini dapat dimodelkan sebagai berikut : Misalkan terdapat j buah proyek, j = 1,…, n aj ≥ 0 : biaya dari proyek j cj ≥ 0 : nilai dari proyek j b > 0 : dana yang tersedia Masalah : pilihlah proyek yang akan dikerjakan sedemikian hingga jumlah dari nilai proyek tersebut maksimal dan biaya yang dikeluarkan tidak melebihi dana yang tersedia. Model : 1, jika proyek j dilaksanakan Xj =  j = 1,...., n 0, lainnya

Siana Halim – T.Industri – UK. Petra



n

∑c X

Max

j

j

j=1

n

Kendala :

∑a X j

j

≤b

j=1

Xj ∈ {0,1} , j = 1,…, n Contoh 3.3:The Facility Location Problem Diketahui N = {1,2,..,n} adalah himpunan facility location yang potensial M={1,2,…,m} adalah himpunan dari pengguna (clients) cj : biaya untuk memilih sebuah fasilitas di lokasi j, j ∈ N hij: biaya untuk memenuhi permintaan dari pengguna i dari sebuah fasilitas yang diletakkan di j, dimana i ∈ I , j ∈ N (asumsi : tiap pengguna hanya memiliki satu permintaan untuk suatu fasilitas tertentu) Masalah : Pilihlah lokasi di N dimana fasilitas tersebut akan diletakkan dan tugaskanlah pengguna-pengguna yang ada pada fasilitas tersebut sedemikian hingga total biaya yang diperlukan minimum. Model : 1 jika sebuah fasilitas diletakkan di lokasi j Xj =   0 lainnya, j = 1,2,..., n Kendala : (a) Permintaan dari pengguna i terpenuhi ∑ Yij = 1 j∈N

Yij : Bagian permintaan dari pengguna i yang dipenuhi oleh fasilitas j (b) Pengguna i hanya dapat dilayani dari lokasi j, jika fasilitasnya diletakkan di lokasi j Yij – Xj ≤ 0 ∀i ∈ I, j ∈ N Pemodelan : Min ∑ c j X j + ∑∑ h ij Yij j∈N

s.d.h

∑Y

ij

=1 ,

i∈I j∈N

∀i ∈ I

j∈N

Yij – Xj ≤ 0

∀i ∈ I, j ∈ N

(MIP)

∀i ∈ I, j ∈ N Yij ≥ 0 Xj ∈ {0,1} , j ∈ N Contoh 3.4 : The Capacitated Facility Location Problem Masalah ini hampir sama dengan masalah pada contoh 3.3 cuman saja kapasitas dari tiap lokasi dibatasi, sehingga model di atas akan sedikit berubah. Siana Halim – T.Industri – UK. Petra

Program Bilangan Bulat 40 Diketahui


N = {1,2,..,n} adalah himpunan facility location yang potensial M={1,2,…,m} adalah himpunan dari pengguna (clients) uj : kapasitas dari sebuah fasilitas yang berlokasi di j, j ∈ N bi : permintaan dari pengguna i, i ∈ I cj : biaya untuk memilih sebuah fasilitas di lokasi j, j ∈ N hij: biaya untuk memenuhi permintaan dari pengguna i dari sebuah fasilitas yang diletakkan di j, dimana i ∈ I , j ∈ N (asumsi : tiap pengguna hanya memiliki satu permintaan untuk suatu fasilitas tertentu)

Model : Min ∑ c j X j + ∑∑ h ij Yij j∈N

s.d.h

i∈I j∈N

∑Y

ij

= bi

∀i ∈ I

,

j∈N

Yij – uj Xj ≤ 0 ∀i ∈ I, j ∈ N Yij ≥ 0 ∀i ∈ I, j ∈ N Xj ∈ {0,1} , j ∈ N

(MIP)

Contoh 3.5 : Travelling Salesman Problem (TSP) Diketahui : V = {1,2,..,N} himpunan Vertex /Kota E : himpunan Edge, merupakan pasangan terurut antara satu kota dengan yang lain yang memiliki hubungan dalam jaringan yang ada. cij : waktu tempuh untuk melakukan perjalanan dari kota i ke kota j; i,j ∈ V dan (i,j) ∈ E Masalah : Mencari sebuah tour yang dimulai dari kota pertama sedemikian hingga : (1) Tiap kota harus dikunjungi sekali dan pada akhir perjalanan harus kembali lagi ke kota yang pertama (2) Total waktu yang diperlukan minimum. Model : 1 jika kota j langsung dikunjungi dari kota i pada tour ini Xij   0 lainnya , (i, j) ∈ E Kendala : (a) Tiap kota hanya dituju satu kali : j

Dari kota

menuju kota



∑X

{i : ( i , j)∈E}


=1 , j∈ V

ij

(b) Tiap kota hanya ditinggalkan satu kali :

j

∑X

{ j : ( i , j)∈E}

ij

= 1 ,i ∈ V

Kendala (a) dan (b) tidaklah cukup untuk mendefinisikan sebuah tour, karena kendala-kendala ini juga memenuhi untuk sebuah subtour, yaitu 4

1

2

5

3

6

Pengamatan : Untuk sebarang tour pasti terdapat edge dari {1,2,3} ke {3,4,5} dan sebuah edge dari {4,5,6} ke {1,2,3}. (c) ∑ X ij ≥ 1 ∀ u ⊂ V, 2 ≤ u ≤ V − 2 {( i , j)∈E ,i∈u , j∈V \ u }

(TSP) :min

∑c X ij

ij

( i , j)∈E

s.d.h (a), (b), (c) terpenuhi Xij ∈{0,1}, (i,j) ∈ E Contoh 3.6: The Assignment Problem (Matching Problem) Diketahui : N = {1,2,…,n} adalah himpunan pekerja M = {1,2,…,m} adalah himpunan pekerjaan cij adalah biaya jika pekerja j mengerjakan pekerjaan i.j ∈N, i ∈M. Masalah

Model

: menentukan penugasan yang tepat untuk pekerja-pekerja yang ada pada pekerjaan-pekerjaan yang tersedia sehingga biaya keseluruhan untuk menyelesaikan pekerjaan-pekerjaan yang ada minimum. : 1 jika orang j melakukan pe ker jaan i Xij =   0 lainnya m

Min

n

∑∑ c X ij

ij

i =1 j=1




s.d.h n

∑X j=1

ij

= 1, ∀i ∈ M

tiap orang harus melakukan pekerjaan

ij

≤ 1, ∀j ∈ N

tiap orang dapat melakukan pekerjaan

m

∑X i =1

sebanyak-banyaknya satu Xij ∈{0,1}, i∈ M, j ∈ N. 3.2 PROGRAM LINEAR RELAKSASI Bentuk program linear yang diperoleh dengan mengabaikan pembatas bilangan bulat disebut sebagai progral linear (LP) relaksasi. Pada (LP) relaksasi ini daerah layak untuk (LIP) merupakan sub-ruang dari daerah layak (LP).

3.3 MENYELESAIKAN PERSOALAN(LIP-murni) DENGAN MENGGUNAKAN TEKNIK BRANCH-AND-BOUND • Teknik ini mencari penyelesaian optimal dari suatu persoalan LIP dengan mengenumerasi titik-titik dalam daerah layak dari suatu sub-persoalan. • Jika penyelesaian dari LP relaksasi memiliki seluruh peubah yang berharga bilangan bulat, maka penyelesaian optimal dari LP relaksasi merupakan juga penyelesaian optimal dari LIP. • Prosedur Branch-and-Bound : (1) Jika pencabangan dari suatu subpersoalan tidak diperlukan, maka subpersoalan ini disebut Fathomed. Ada 3 situasi yang mungkin yaitu : (a) Apabila subpersoalan itu tidak layak (b) Apabila subpersoalan itu memberikan penyelesaian yang optimal dimana seluruh peubahnya berharga bilangan bulat. (c) Apabila nilai z-optimal untuk sub-persoalan itu tidak lebih baik dari nilai z-optimal dari subpersoalan yang lain. (2) Suatu subpersoalan dapat diabaikan atau dieliminasi dari pertimbangan selanjutnya, apabila : (a) Tidak layak (b) Batas bawah yang menyatakan nilai z dari calao solusi terbaik sekurang-kurangnya berharga sama besar dengan nilai z dari subpersoalan yang bersangkutan.




3.4 MENYELESAIKAN PERMASALAHAN (MIP) DENGAN BRANCHAND-BOUND Teknik penyelesaian dari permasalahan ini hampir sama dengan teknik penyelesaian yang telah dibahas pada sub.bab 3.3, hanya saja pencabangan hanya dilakukan pada peubah-peubah yang harus berharga bilangan bulat. 3.5 MENYELESAIKAN PERMASALAHAN RANSEL DENGAN BRANCHAND-BOUND Permasalahan Ransel (Knapsack Problem) dapat dituliskan secara mamemtis dalam bentuk sebagai berikut : Max z = c1X1 + c2X2 + … + cnXn s.d.h a1X1 + a2X2 + … + anXn ≤ b Xi ∈ {0,1} ∀i = 1,2,..,n Dua aspek pendekatan branch-and-bound: (1) karena tiap peubah harus berharga nol atau satu maka pencabangan pada Xi akan menghasilkan cabang Xi = 0 dan Xi = 1. (2) LP relaksasi dilakukan dengan memeriksa nilai ci /ai yang merupakan perwujudan dari manfaat yang diperolah dari tiap unit sumber yang digunakan oleh barang ke-I

3.6 MENYELESAIKAN PERMASALAHAN IP DENGAN METODE ENUMERASI IMPLISIT Digunakan untuk menyelesaikan permasalahan BIP (LIP 0-1). Ada 3 hal pokok yang akan dilakukan yaitu : (1) Melakukan penyempurnaan terbaik bagi suatu node dengan cara : (a) dilakukan dengan menjadikan peubah bebas berharga 0 atau 1 sedemikian hingga diperoleh nilai fungsi tujuan optimal (b) jika penyempurnaan node ini layak, maka pencabangan berikutnya tidak perlu dilakukan (2) Mengeliminasi suatu node dari pertimbangan selanjutnya. (a) Suatu node akan diabaikan apabila setelah dilakukan penyempurnaan terbaik terhadap node itu, diperoleh nilai fungsi tujuan yang lebih buruk daripada nilai fungsi tujuan calon penyelesaian sebelumnya. (3) Menguji ada tidaknya penyempurnaan yang layak dari suatu node (a) Apabila penyempurnaan suatu node tidak memenuhi pembatas yang ada, maka pasti tidak akan ada penyempurnaan yang layak dari node tersebut terhadap permasalahan semula Siana Halim – T.Industri – UK. Petra



3.7 MENYELESAKAN PERMASALAHAN (LIP) DENGAN TEKNIK CUTTING PLANE Pada teknik ini pendekatan yang digunakan adalah membuat pembatas tambahan yang memotong ruang layak dari LP relaksasi sehingga dapat mengeliminasi penyelesaian yang bukan merupakan bilangan bulat. TETAPI tidak semua permasalahan dapat diselesaikan dengan teknik ini, karena itu teknik ini jarang digunakan. 3.7.1 Algoritma Pecahan (Bilangan bulat murni) Syarat : Semua koefisien pembatas dan ruas kanannya harus merupakan bilangan bulat Alasan: Koefisien pecahan pada pembatas akan menyebabkan harga dari peubah slack akan menjadi pecahan juga. Algoritma : (1) Selesaikan permasalahan dengan LP (2) Jika penyelesaian optimum sudah merupakan bilangan bulat -! Berhenti (3) Jika tidak lakukan langkah berikut : Perhatikan Tabel Optimum dari LP : Xi … Xm Basis X1 … Z 0 … 0 … 0 X1 . . . Xi . . . Xm

1 . . . 0 . . . 0

… … … … …

0 . . . 1 . . . 0

…

W1

C1 α1 . . . αi1 . . . αm1 1

0 . . . 0 . . . 1

… … … …

… … … … … … …

Wj

Cj α1 . . . αij . . . αmj j

… … … … … … …

Wn

Cn α1n . . . αin . . . αmn

Solusi β0 β1

βi

βm

Peubah-peubah Xi : basis, i = 1,2,…, m Wj : nonbasis j = 1,2,…,n Asumsikan Xi bukan bilangan bulat Xi = β i -

n

∑α W j i

j=1

(1)

j

Misalkan : β i = [β i] + fi ,[ β i] : bilangan bulat tersebesar sedemikian hingga [β i] ≤ β i j j αi =[αi ] + fij , 0 < fi < 1 , 0 < fij < 1 Maka persaman (1) berubah menjadi :

∑ [α ]W − ∑ f n

Xi = [β i] + fi -

n

j i

j=1

j

n

f i − ∑ f ij W j j=1

ij

Wj

j=1

∑ [α ]W n

= Xi - [β i] +

j=1

j i

j




Ruas kiri harus merupakan bilangan bulat demikian pula dengan ruas kanan. fij ≥0 , Wj ≥ 0 berarti

n

∑f j=1

ij

Wj ≥ 0 n

fi -

∑f j=1

ij

Wj ≤ f i

ij

Wj < 1

ij

Wj ≤ 0

n

karena fi < 1 berarti

fi -

∑f j=1 n

merupakab bil. bulat

fi -

∑f j=1

Tambahkan peubah slack didapat : n

fi -

∑f

ij

W j + Si = 0

j=1

n

SI =

∑f

ij

W j - fi inilah yang disebut sebagai fractional cut

j=1

Karena pada tabel akhir didapat bahwa Wj = 0 berarti Si = fi menjadi tidak layak karena itu gunakan metode dual simplex untuk menyelesaikannya. Jika penyelesaiannya sudah merupakan bilangan bulat -! berhenti, jika belum ulang kembali prosedur ini. Contoh 3.7 Selesaikan permasalahan berikut : Max Z = 7 X1 + 9 X2 Kendala : - X1 + 3 X2 ≤ 6 7 X1 + X2 ≤ 35 X1, X2 bilangan bulat tak negatif Penyelesaian : Tabel Simplex LP: X2 X3 X4 Solusi Basis X1 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 Terlihat bahwa X1 dan X2 bukan bilangan bulat, karena itu pilihlah pertidaksamaan yang ‘kuat’ untuk mempercepat pencapaian penyelesaian bilangan bulat optimum, yaitu :

Misalnya : terdapat 2 pertidaksamaan n

∑f j=1

ij

Wj ≥ f i

n

∑f j=1

kj

dan

Wj ≥ f k


(2) (3)



Persamaan (2) lebih kuat dari persamaan (3) jika : fi ≥ fk fij ≤ fkj ∀j Definisi ‘kekuatan’ ini digunakan pada pembatas baru yang diturunkan dari baris yang mempunyai : (a) max ( fi ) ! baris dengan pecahan terbesar i

(b) max i

fi

! baris dengan rasio

n

∑f

ij

j=1

fi

terbesar

n

∑f

ij

j=1

Pada contoh soal di atas : β1 = 9/2 ! 4+ ½ β2 = 7/2 !3 + ½ berarti f1 = f2 = ½ ( aturan (a) tidak berlaku) Gunakan aturan (b) α23 = 7/22 = 0 + 7/22 ! f23 = 7/22 α24 = 1/22 = 0 + 1/22 ! f24 = 1/22 α13 = -1/22 =-1+21/22 ! f13 = 21/22 α14 = 3/22 = 0 + 3/22 ! f14 = 3/22 f 1/ 2 1/ 2 = > max n i i 7 / 22 + 1 / 22 21 / 22 + 3 / 22 ∑ f ij j=1

berarti pilih persamaan X2 = 7/22 X3 + 1/22 X4 ≥ ½ X2 + 7/22 X3 + 1/22 X4 = 3 ½ X2 +(0+ 7/22) X3 + (0+1/22) X4 = 3 + ½ Persamaan pembatas baru : S1 - 7/22 X3 - 1/22 X4 = - ½ Tabel Simpleks baru : Basis Z X2 X1 S1

X1 0 0 1 0

X2 0 1 0 0

X3 28/11 7/22 -1/22 -7/22

X4 15/11 1/22 3/22 -1/22

S1 0 0 0 1

X4 1 0 1/7 1/7

S1 8 1 -1/7 -22/7

Solusi 63 7/2 9/2 -1/2

Dengan Dual Simpleks di dapat : Basis Z X2 X1 X3

X1 0 0 1 0

X2 0 1 0 0

X3 0 0 0 1

Solusi 59 3 4 1/7 1 4/7




Masih terdapat penyelesaian yang bukan bilangan bulat , buat lagi pembatas baru : X1 + (0 + 1/7) X4 + (-1 + 6/7) S1 = 4 + 4/7 S2 – 1/7 X4 – 6/7 S1 = -4/7 Basis Z X2 X1 X3 S2

X1 0 0 1 0 0

X2 0 1 0 0 0

X3 0 0 0 1 0

X4 1 0 1/7 1/7 -1/7

S1 8 1 -1/7 -22/7 -6/7

S2 0 0 0 0 1

Solusi 59 3 4 1/7 1 4/7 -4/7

X4 0 0 0 0 1

S1 2 1 -1 -4 6

S2 7 0 1 1 -7

Solusi 55 3 4 1 4

Hasil dari dual Simpleks Basis Z X2 X1 X3 X4

X1 0 0 1 0 0

X2 0 1 0 0 0

X3 0 0 0 1 0

Penyelesaian akhir di dapat hasil bilangan bulat dengan X1 = 4, X2 = 3 dan Z = 55 3.7.2. Algoritma Campuran Asumsi : Xk peubah bilangan bulat dari masalah campuran Xk = βk -

n

∑ α kj Wk = [βk] + fk j=1

n

∑α j=1

j k

Wj

n

Xk - [βk] = fk -

∑α j=1

j k

Wj

Ingat : beberapa peubah Wj bukan merupakan bilangan bulat. Supaya Xk berharga bilangan bulat maka : Xk ≤ [βk] atau Xk ≥ [βk] +1 Berarti : n

∑α j=1

j k

W j ≥ fk

(4)

j k

W j ≤ fk – 1

(5)

n

∑α j=1

Tentukan : J+ : himpunan dari subskrip j untuk α kj ≥ 0 J- : himpunan dari subskrip j untuk α kj < 0 Dari (4) dan (5) didapat ∑ α kj Wj ≥ f k j∈J +


(6)



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

(7)

Semua pembatas ini tidak terjadi secara simultan maka persamaan (6) dan (7) dapat dikombinasi menjadi : fk Sk – { ∑ α kj W j + α kj W j } = -fk (Potongan Campuran) ∑ f k − 1 j∈J −1 j∈J + Gunakan dual simpleks (Karena Wj = 0 ! tidak layak) Contoh 3.8 Dari contoh 3.7 di atas, misalakan X1 harus merupakan bilangan bulat X1 – 1/22 X3 + 3/22 X4 = ( 4+ ½) J- = {3}; J+ = {4}, f1= ½ Potongan campuran : 1/ 2 (-1/22) X3 } = -1/2 S1 – {3/22 X4 + 1/ 2 − 1 S1 – 1/22 X3 – 3/22 X4 = -1/2 Tabel : Basis Z X2 X1 S1

X1 0 0 1 0

X2 0 1 0 0

X3 28/11 7/22 -1/22 -7/22

X4 15/11 1/22 3/22 -1/22

S1 0 0 0 1

X1 0 0 1 0

X2 0 1 0 0

X3 23/11 10/33 -1/11 1/3

X4 0 0 0 1

S1 10 -1/3 1 -22/4

Solusi 63 7/2 9/2 -1/2

Dual Simpleks : Basis Z X2 X1 X4

Solusi 58 10/3 4 11/3

Penyelesaian optimal : X1 = 4, X2 = 10/3 Z = 58


Penelitian Operasional II Program Bilangan Bulat PROGRAM BILANGAN BULAT (INTEGER PROGRAMMING)

Recommend Documents