BAB 2 TINJAUAN PUSTAKA

BAB 2 TINJAUAN PUSTAKA

2.1 Program Integer Program Integer merupakan pengembangan dari Program Linear dimana beberapa atau semua variabel keputusannya harus berupa integer. Jika hanya sebagian variabel keputusannya merupakan integer maka disebut Program Integer campuran (Mixed Integer Progamming). Jika semua variabel keputusannya bernilai integer disebut Program Integer Murni (Pure Integer Progamming). Sedangkan Program Integer 0-1 merupakan bentuk Program Integer dimana semua variabel keputusannya harus bernilai integer 0 atau 1 (binary). Bentuk umum Program Integer adalah: (Mehrotra dan Li 2004) max

n P

cj xj

j=1

dengan kendala : Pn j=1 aij xj = bi , (i = 1, 2, ..., m) xj ≥ 0, xj

integer

(j = 1, 2, ..., n) (untuk beberapa atau semua j = 1, 2, ..., n)

Suatu metode yang sederhana dan praktis untuk menyelesaikan program integer adalah dengan membulatkan hasil variabel keputusan yang diperoleh melalui LP. Pendekatan ini mudah dan praktis dalam hal usaha, waktu dan biaya yang diperlukan untuk memperoleh suatu solusi. Bahkan, pendekatan pembulatan dapat merupakan cara yang sangat efektif untuk permasalahan program integer yang besar dimana biaya-biaya hitungan sangat tinggi atau untuk permasalahan nilai-nilai solusi variabel keputusan yang sangat besar. Dengan kata lain, solusi pembulatan dapat lebih jelek dibanding solusi integer optimum yang sesungguhnya atau mungkin merupakan solusi tak layak. Ini membawa konsekuensi besar jika jumlah produk-produk seperti pesawat angkut komersial atau kapal perang yang harus diproduksi dibulatkan ke bilangan bulat terdekat. 5 Universitas Sumatera Utara

6 Meskipun IP dibatasi sejumlah solusi layak yang berhingga, namun karena peubahnya mengambil nilai bilangan bulat membuatnya sulit untuk menemukan algoritma yang efisien yang dapat mencari secara langsung titik layak yang integer di dalam ruang solusi. Dalam beberapa hal kesulitan ini sudah dapat diatasi oleh para ahli dengan menghasilkan sebuah prosedur solusi yang didasarkan pada penyelesaian problema LP. Strategi yang dimaksud dapat disimpulkan dalam tiga langkah berikut : 1. Mengkonversi IP menjadi LP biasa 2. Menyelesaikan model LP yang direlaksasi dan mengidentifikasi titik optimum yang kontinu (yang bernilai pecahan) 3. Dimulai dari titik optimum yang kontinu, dengan menambahkan kendala khusus berturut-turut yang dapat memaksa titik optimum dari hasil model LP ke arah pembatasan integer yang diinginkan. Ada dua metode umum yang digunakan untuk menghasilkan kendala khusus yang memaksa titik optimum dari LP yang direlaksasi ke arah solusi integer yang diinginkan, yakni metode : a. Cutting plane b. Branch and bound

2.2 Metode Branch and Bound Salah satu metode yang dapat digunakan dalam menyelesaikan persoalan program integer (IP) adalah metode Branch and Bound. Menurut Winston (2000) metode branch and bound adalah suatu metode mencari solusi optimal dari suatu persoalan IP dengan mengenumerasi titik-titik dalam daerah fisibel dari suatu subpersoalan. Pada metode branch and bound berlaku : 1. Jika pencabangan dari suatu subpersoalan tidak diperlukan maka subpersoalan itu adalah fathomed. Ada tiga situasi yang menyebabkan suatu subpersoalan fathomed Terukur), yaitu :

Universitas Sumatera Utara

7 a. Apabila subpersoalan itu tidak fisibel b. Apabila subpersoalan itu memberikan solusi optimal dimana seluruh variabelnya berharga bilangan bulat c. Apabila nilai Z optimasi untuk subpersoalan itu tidak lebih baik dari nilai Z optimal (dalam persoalan maksimal berarti nilai Z optimal dari subpersoalan itu tidak lebih besar daripada batas bawah yang telah diperoleh) 2. Suatu subpersoalan dapat diabaikan (dieliminasi dari pertimbangan selanjutnya) apabila subpersoalan itu berada dalam situasi berikut : a. Tidak fisibel b. Batas bawah (LB) (menyatakan nilai Z dari calon solusi terbaik) sekurangkurangnya berharga sama dengan nilai Z dari subpersoalan yang bersangkutan Menurut Winston (2004), dikatakan terukur jika terdapat kondisi sebagai berikut: 1. Subpersoalan menghasilkan solusi tak fisibel, sehingga tidak dapat menghasilkan solusi optimal bagi IP 2. Subpersoalan tersebut menghasilkan suatu solusi optimal dengan semua variabelnya bernilai integer. Jika solusi optimal ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimal dan nilai fungsi objektifnya menjadi batas bawah nilai fungsi objektif optimal bagi masalah IP pada saat itu. Bisa jadi subpersoalan menghasilkan solusi optimal untuk masalah IP. 3. Nilai fungsi objektif optimal untuk subpersoalan tersebut tidak melebihi (untuk masalah maksimisasi) batas bawah saat itu, maka subpersoalan ini dapat dieliminasi.

Universitas Sumatera Utara

8 2.3 Algoritma Branch and Bound untuk Program Integer Dalam banyak usaha pemecahan permasalahan program integer campuran (atau permasalahan optimasi diskrit lainnya, misalnya pedagang keliling, penjadwalan job shop) metode branch and bound paling berhasil diterapkan hingga saat ini. Misal permasalahan ini disebut P0 . Langkah pertama adalah untuk memecahkan masalah LP ’berkelanjutan’ diperoleh dengan mengabaikan kendala integralistik. Jika pada solusi optimal, satu atau lebih dari variabel-variabel bilangan bulat berubah menjadi non-integer, pilih salah satu variabel tersebut dan menggunakannya untuk membagi soal yang diberikan P0 menjadi dua ’sub-masalah’ P1 dan P2 . Misalkan variabel yang dipilih adalah yj dan mengambil nilai non-integral βj di optimalkan terus menerus. Kemudian P1 dan P2 didefinisikan sebagai berikut: P1 ≡ P0 dengan penambahan kendala yj ≤ bβj c P2 ≡ P0 dengan penambahan kendala yj ≥ bβj + 1c

Setiap solusi untuk P0 adalah juga solusi untuk P1 atau P2 dan sehingga P0 dapat diselesaikan dengan menyelesaikan P1 dan P2 . Dilanjutkan dengan memecahkan permasalahan LP terkait dengan P1 dan P2 . Kemudian pilih salah satu masalah dan jika perlu membaginya menjadi dua sub-masalah seperti yang dilakukan dengan P0 . Prinsip branch and bound diillustrasikan dalam gambar 2.1 berikut ini.

Gambar 2.1 Prinsip branch and bound

Universitas Sumatera Utara

9 Proses ini dapat dilihat sebagai pembangunan sebuah pohon biner dari submasalah yang untuk terminal node yang sesuai dengan permasalahan yang masih harus diselesaikan. Dalam perhitungan yang sebenarnya, satu menyimpan daftar masalah yang belum terpecahkan dimana masalah utama telah terpecahkan. Satu juga menyimpan catatan nilai MIN tujuan solusi integer terbaik yang ditemukan sejauh ini.

Langkah 0: Awalnya, persoalan terdiri dari masalah awal P0 . Masukkan MIN sama dengan salah satu nilai dari beberapa solusi bilangan bulat yang diketahui, atau jika salah satu tidak memberikan hasil pada beberapa batas atas dihitung dari data awal, jika tidak ada kemungkinan adalah tidak mungkin menempatkan MIN. Memecahkan masalah LP terkait dengan P0 . Jika solusi memiliki nilai integer untuk semua variabel bilangan bulat maka akhiri, jika tidak Langkah 1: Hapus masalah P dari daftar yang nilai fungsi tujuan optimal x0 lebih besar dari MIN. Jika tidak ada masalah akhiri. Solusi bulat terbaik yang ditemukan sejauh ini adalah optimal. Jika tidak ada ditemukan, maka permasalahan adalah tidak layak. Langkah 2: Di antara variabel integer dalam masalah P dengan nilai-nilai non-integer dalam solusi optimal terus menerus untuk P , pilih satu untuk percabangan. Biarkan variabel ini menjadi yp dan biarkan nilai tersebut dalam solusi seterusnya menjadi β. Langkah 3: Buat dua masalah baru P 0 dan P 00 dengan menambahkan pembatasan ekstra masing-masing yp ≤ β dan yp ≥ β + 1. Selesaikan masalah LP terkait dengan P 0 dan P 00 dan menambahkan masalah ini ke dalam daftar. Jika solusi bilangan bulat baru dan lebih baik ditemukan, simpan dan memperbarui MIN. Masalah LP baru tidak harus dipecahkan dari awal tetapi dapat kembali dioptimalkan dengan menggunakan algoritma ganda (atau secara parametris mengubah batasan pada yp ). Jika selama re-optimasi dari persoalan LP, nilai fungsi tujuan melebihi MIN masalah ini dapat diabaikan. Kembali ke langkah 1.

Universitas Sumatera Utara

10 Jika dianggap bahwa setiap variabel integer dalam P0 memiliki batas atas terbatas (sama dengan beberapa nilai besar untuk variabel nominal yang tak terbatas) maka algoritma harus berhenti pada akhirnya, karena sebagai salah satu hasil yang lebih rendah, pohon dari masalah batas-batas pada variabel semakin ketat dan ketat, dan ini akhirnya akan menjadi tepat jika solusi LP tidak pernah integer. Perhatikan contoh berikut: Maksimumkan Z = −7x1 − 3x2 − 4x3 Kendala : x1 + 2x2 + 3x3 − x4 = 8

(2.1)

3x1 + x2 + x3 − x5 = 5

(2.2)

x1, x2, . . . , x5 ≥ 0 dan integer

(2.3)

Penyelesaian : Awalnya persoalan ini diselesaikan sebagai persoalan LP. Solusi optimal LP adalah x1 = 2/5, x2 = 19/5, x3 = x4 = x5 = 0 dengan Z¯0 = [−71/5] = −15. Selanjutnya P0 dipisahkan pada x1 atau x2 dan pilih sembarang x2. Hasilnya ditunjukkan pada gambar 2.2 berikut :

Gambar 2.2 Calon solusi 1 Solusi optimal dari LP pada node 1 adalah x1 = 1/2, x2 = 3, x3 = 1/2, x4 = x5 = 0 dengan Z¯1 = [−29/2] = −15. Ini tidak merubah batas. Pencabangan dipilih pada node 1 dengan memilih x1. Hasilnya dinyatakan dalam gambar 2.3 berikut:

Universitas Sumatera Utara

11

Gambar 2.3 Calon solusi 2 Dengan mengambil pencabangan sebelah kiri dan menyelesaikan LP-nya, diperoleh solusi yang semuanya integer : x1 = 0, x2 = 3, x3 = 2, x4 = 4, x5 = 0 dengan Z¯1 = −17. Selanjutnya batas bawah baru Z0 = max {z1 }=-17. Node 3 difathom dan kembali ke node 4. Hasilnya diperoleh Z¯4 = −18 < z0 , maka node 4 difathom. Kembali ke node 2. Solusi optimal dari LP-nya x1 = 1/3, x2 = 4, x3 = 0,x4 = 1/3,x5 = 0 dengan Z¯2 = [−43/3] = −15. Pencabangan dipilih pada x1 dan hasilnya terlihat pada gambar 2.4 berikut:

Gambar 2.4 Calon solusi 3 Pada node 5, solusi optimal dari LP-nya semuanya integer dan Z5 = −15. Selanjutnya Z0 = max {z5 }=-15 dan node 5 dan 6 difathom. Sebuah solusi optimal diberikan dengan solusi pada node 5 : x1 = 0, x2 = 5, x3 = 0, x4 = 2, x5 = 0 dan Z = −15.

Universitas Sumatera Utara

12 Sementara Baravukaite dan Ciegis (2007), memberikan algoritma branch and bound sebagai berikut : Algoritma BnB() begin  m Lj using covering rule (1) cover solution space D by L = Lj |D ⊆ Uj=1 (2) S = ∅, UB(D) = ∞ (3) while (subspace list is not empty L 6= ∅) do (4)

choose I ∈ L using selection rule, exclude I from L

(5)

if (LB(I) ⊂ U B(D) + 

(6)

Branch I into p subspace Ij using branching rule

(7)

for all (Ij , j = 1, 2, . . . , p) do

(8)

find U B(Ij ∩ D) and LB(Ij ) using branching rules

(9)

U B(D) = min(U B(D), U B(Ij ∩ D))

(10)

if (LB(Ij ) < U B(D) + ε)

(11)

if (Ij is a possible solution) then S = Ij

(12)

else L = LU {Ij }

(13)

end if

(14)

end if

(15) (16)

end for end if

(17) end while

Universitas Sumatera Utara

13 end AlgoritmaBnB Dimana L menunjukkan sebagai calon himpunan, S adalah solusi, UB (Di) dan LB (Di) menunjukkan sebagai batas atas dan batas bawah untuk nilai minimum dari fungsi objektif atas sub ruang Di . Baravukaite dan Ciegis (2007)mendeskripsi dari sebuah template baru ke algoritma parallel branch and bound. Kelas C++ untuk semua langkah utama algoritma BnB termasuk banyak contoh untuk seleksi, estimasi bound dan langkah-langkah pencabangan.

2.4 Kelayakan Program Integer Masalah kelayakan program integer linier murni (FILP) adalah untuk {x ∈ Zn+ |Ax = a}

(2.4)

dimana A ∈ Zm×n , a ∈ Zm , dan A diasumsikan matriks memiliki peringkat tertinggi. Jika tidak, maka baris linier dari A akan dihapus (Mehrotra dan Li 2004). Masalah kelayakan program integer linier campuran (FMILP) adalah untuk i o n h xz n n ¯ , x (2.5) x = xc z ∈ Z+ , xc ∈ R+ |Rx = r i h i h : C , r = b , B ∈ Zmׯ ¯ n ¯ n dan C ∈ Zmׯ . dimana R mempunyai bentuk R = B a A:0 Kolom A sebagai variabel integer, dan kolom C sebagai variabel riil. Tanpa menghilangkan asumsi umum bahwa matriks C memiliki peringkat tertinggi. Jika hal ini tidak terjadi, maka dimiliki π sedemikian rupa sehingga π T C = 0, memungkinkan untuk menghapus kendala untuk setiap πi 6= 0, dan menggantinya dengan kendala π T B = π T b. merupakan transpose dari vektor atau matriks. Untuk x ∈ Rn , kxk p merupakan norm l2 , dan kxkQ merupakan norm ellipsoid xT Qx. Range space dari maSuperscript

T

triks Am×n , diwakili oleh R(A). Null space A diwakili oleh N (A) = {p ∈ Rn |Ap = 0}. o n P Diberikan B = {b1, . . . , bk }, L(B) = x ∈ Rn |x = ki=1 Zbi adalah lattice yang dihasilkan oleh vektor kolom bi , i = 1, . . . , k. Dual dari A didefinisikan sebagai himpunan

Universitas Sumatera Utara

14  A⊥ = z ∈ Rn |Az = 0, z T x ∈ Z, untuk semua x ∈ A . Suatu lattice K∗ (AT ) disebut adjoin lattice dari A jika untuk setiap basis Z dari A ada sebuah basis Z ∗ dari K∗ (AT ) sehingga ZT Z∗ = I

(2.6)

Adjoint lattice adalah integral jika setiap anggotanya integral. Proposisi 2.1 (Mehrotra dan Li, 2004) ˜ adalah basis dari lattice A. Maka terdapat matriks integral Z˜ ∗ sedemikian Misal Z rupa sehingga Z˜ ∗T Z˜ = I

(2.7)

Mehrotra dan Li (2004) membuktikan dengan mengasumsikan sebuah basis Z dari A dipenuhi dari perhitungan HNF dari A, dan Z ∗ terbentuk seperti yang diuraikan diatas. ˜ adalah basis untuk A dimiliki sebuah matriks unimodular V sehingga Karena Z dan Z Z˜ = ZV . Ambil Z˜ ∗ = Z ∗ V −T . Sejak V adalah unimodular, V −T juga unimodular. 2.5 Algoritma Pencabangan Hyperplane Menurut Mehrotra dan Li (2004) masalah persoalan percabangan hyperplane ε(w, Q) adalah untuk menyelesaikan masalah minimasi : min W (u, ε(w, Q)) atau ekivalen min W (u, ε(0, Q)) ∗

u∈A∗ \0

(2.8)

u∈A \0

o n dimana ε(0, Q) = x ∈ Rn | kxkQ ≤ 1, Ax = 0 . Adjoint kisi adalah paling sederhana untuk menghasilkan percabangan hyperplanes dalam ruang asli. Untuk sebuah kisi A∗, sejak A∗ ⊕ L(AT ) adalah juga merupakan adjoint kisi, memungkinkan seseorang untuk mengurangi unsur-unsur sebelum A∗ melakukan perhitungan apapun. Numerik ini menguntungkan terutama ketika menambahkan pencabangan hyperplane pada kendala yang ada. Sedangkan, menurut Lenstra (1983) menghasilkan pencabangan hyperplane sebagai produk sampingan dari perhitungan pembulatan setelah menemukan pembulatan ellipsoidal dan pengurangan basis-LLL.

Universitas Sumatera Utara