BAB II TINJAUAN PUSTAKA 2.1 Riset Operasi Masalah pengoptimalan timbul sejak adanya usaha untuk menggunakan pendekatan ilmiah dalam memecahkan masalah manajemen suatu organisasi. Sebenarnya kegiatan yang disebut riset operasi (operation research) dimulai di kalangan militer pada awal Perang Dunia II, dimana sejumlah ilmuwan dari berbagai bidang keahlian bekerja sama dalam sebuah tim melakukan riset dalam operasi militer. Mereka berupaya menerapkan pendekatan ilmiah agar dapat mengalokasikan sumber-sumber atau input yang terbatas untuk melayani berbagai kegiatan secara efisien dan efektif sehingga diperoleh hasil operasi yang optimal. Didefinisikan riset operasi adalah riset sebuah tim tepadu yang menerapkan metode ilmiah untuk memecahkan permasalahan yang timbul dalam kegiatan operasi suatu sistem organisasi agar diperoleh pemecahan yang optimal.
2.2 Model Pengoptimalan Menurut Rardin (1998) model pengoptimalan menampilkan pilihan masalah sebagai variabel keputusan dan mencari nilai yang maksimal atau minimal fungsi tujuan (fungsi objektif) pada variabel keputusan menurut batasan nilai variabel sesuai dengan alternatif keputusan yang mungkin. Model standar pada model pengoptimalan adalah sebagai berikut: minimalkan atau maksimalkan fungsi tujuan f ( x1 ,..., xn ), dengan kendala g i ( x1 ,..., xn ) ( , , atau ) bi , i 1,..., m, dimana
f , g1 ,..., g m adalah fungsi yang diberikan untuk variabel keputusan
x1,..., xn dan b1 ,..., bm adalah konstanta parameter yang telah ditentukan. Ketika riset operasi digunakan untuk memecahkan sebuah masalah organisasi, 7 langkah prosedur pembentukan model berikut seharusnya diikuti, yaitu 1 perumusan masalah, 2 pengobservasian sistem,
3 perumusan sebuah model matematis untuk problem tersebut, 4 pengujian model, 5 pemilihan alternatif yang sesuai, 6 penyajian hasil dan kesimpulan studi kepada organisasi, 7 penerapan dan pengevaluasian rekomendasi. (Winston, 1995) Williams (1991) mengemukakan bahwa tujuan pengoptimalan suatu organisasi
bisa
berupa
pemaksimalan
keuntungan,
peminimalan
biaya,
pemaksimalan kegunaan, ... , dan pemaksimalan kekuatan rencana operasi. Sebuah model pengoptimalan disebut linear programming (LP) jika memiliki sebuah fungsi tujuan, semua fungsi kendalanya linear, dan variabel keputusannya bernilai tidak negatif. Beberapa tipe kendala yang paling umum muncul dalam model LP diklasifikasikan sebagai berikut Kendala kapasitas produksi Ketersediaan bahan baku Permintaan pasar dan pembatasnya Kendala keseimbangan kesinambungan bahan.
2.3 Integer Programming Sebuah model pengoptimalan disebut integer programming (IP) jika variabel keputusan berupa bilangan bulat. Jika semua variabel adalah bilangan bulat, maka model itu disebut pure integer program, tapi jika tidak demikian maka disebut mixed-integer program. (Rardin 1998) Penyelesaian masalah IP berkaitan dengan LP-relaksasi. LP-relaksasi dari suatu IP merupakan LP yang diperoleh dari IP tersebut dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. (Winston, 1995) Untuk masalah pemaksimalan, nilai fungsi objektif yang optimal di LP-relaksasi lebih besar atau sama dengan nilai objektif optimal di IP, sedangkan untuk masalah peminimuman nilai fungsi objektif yang optimal di LP-relaksasi lebih kecil atau sama dengan nilai fungsi objektif yang optimal di IP.
4
Salah satu metode pemecahan masalah IP adalah metode Branch and Bound, dimana langkah awalnya dimulai dengan menyelesaikan LP-relaksasi pada IP. Prinsip dasar metode Branch and Bound adalah membagi daerah fisibel dari masalah LP-relaksasi dengan cara membuat subproblem-subproblem baru sehingga masalah IP terpecahkan. Daerah fisibel suatu LP adalah daerah yang memuat titik-titik yang dapat memenuhi kendala linear masalah LP. Menurut Taha (2003), berikut ini adalah langkah-langkah dalam metode Branch and Bound untuk masalah pemaksimalan. Ditetapkan batas bawah awal z =
untuk nilai optimal dari fungsi objektif
IP dan i = 0. Langkah 1 (pem-fathom-an dan pembatasan). Memilih LPi sebagai subproblem untuk diteliti. LP i diselesaikan dan LPi difathom-kan dengan salah satu dari ketiga kondisi berikut: (a) Nilai optimal z dari LPi tidak lebih baik daripada batas bawah sekarang. (b) LPi menghasilkan solusi integer fisibel yang lebih baik daripada batas bawah sekarang. (c) LPi tidak memiliki solusi yang fisibel. Dua kasus akan muncul. (a) Jika LPi di-fathom-kan dan sebuah solusi yang lebih baik ditemui, batas bawah diperbarui. Jika semua subproblem sudah di-fathom-kan, berhenti, optimal dari IP dihubungkan dengan batas bawah sekarang, bila ada. Jika sebaliknya, ditentukan i = i + 1, dan langkah 1 diulangi. (b) Jika
LPi tidak di-fathom-kan, dilanjutkan ke langkah 2 untuk
melakukan pencabangan LPi. Langkah 2 (pencabangan). Memilih salah satu variabel xj yang nilai optimalnya adalah xj* tidak memenuhi batasan integer dalam solusi LPi. Memisahkan bidang [xj*] < xj < [xj*] + 1 (dengan [v] sebagai integer terbesar yang
v) dengan membuat dua subproblem
LP yang sesuai dengan xj
[xj*] dan xj
[xj*] + 1
Menentukan i = i + 1, dan kembali ke langkah 1.
5
Contoh: Misalkan diberikan masalah IP sebagai berikut: Maksimalkan z = 8x1 + 5x2 terhadap
x1 + x2 9x1 + 5x2 x1 , x2
6 45 0, x1 , x2 integer.
(1)
Solusi optimal dari LP-relaksasi contoh tersebut (LP0) adalah z = 41,25, x1 = 3,75, dan x2 = 2,25. Daerah fisibel LP-relaksasi dari masalah di atas dapat dilihat pada Gambar 1. Menurut metode Branch and Bound, karena solusi optimal LPrelaksasi tersebut tidak memenuhi syarat integer, maka harus dibuat subproblem baru. Dipilih sembarang variabel xi optimal yang tidak memenuhi syarat integer, misalnya x1 = 3,75, sehingga bidang 3
x1
4 bukan daerah fisibel bagi masalah
IP dan harus dipisahkan. Ruang LP0 semula diganti dengan dua ruang LP yakni LP1 dan LP2 yang didefinisikan sebagai berikut: Ruang LP1 = ruang LP0 + kendala (x1
4).
Ruang LP2 = ruang LP0 + kendala (x1
3).
Ruang LP1 dan LP2 dapat dilihat pada Gambar 2.
6
x2 10
9 8 7 6
9
8
7
6
55 44 33
Solusi optimal LP x 1=3,75 x2=2,25
22 11
x1
00 0
1
0
2
1
3
2
4
3
4
5
5
6
6
7
7
Gambar 1 Daerah Fisibel LP.
x10 2 9
9
8
8
7
7
6
6
5
5
4
4
3
3
2
2
1
1
0
0
LP2 LP1
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
x1
7
Gambar 2 Grafik ruang LP1 dan LP2. Dari gambar di atas terlihat batasan baru LP1 dan LP2 tidak dapat dipenuhi secara bersamaan, sehingga LP1 dan LP2 harus ditangani sebagai 2 LP yang
7
berbeda. Masalah LP1 dan LP2 diselesaikan satu per satu. Misalkan LP 1 dipilih pertama kali untuk diselesaikan, sehingga permasalahan menjadi Maksimalkan z = 8x1 + 5x2 terhadap
x1 + x2 9x1 + 5x2
6 45
x1
4
x1 , x2
0.
(2)
Diperoleh solusi optimal untuk masalah LP di atas, yaitu z = 41, x 1 = 4 dan x2 = 1,8. Karena solusi optimal LP1 bukan solusi integer, berarti LP1 tidak difathom-kan, maka dilakukan pencabangan di LP1 menjadi 2 subproblem, yakni LP3 dan LP4. Ruang LP3 dan LP4 didefinisikan sebagai berikut: Ruang LP3 = ruang LP0 + kendala (x1 LP1 + kendala (x2
2) = ruang
4) + kendala (x2
1) = ruang
2).
Ruang LP4 = ruang LP0 + kendala (x1 LP1 + kendala (x2
4) + kendala (x2
1).
Berikutnya akan dipecahkan LP3. Ternyata tidak ada solusi fisibel untuk LP 3, berarti LP3 di-fathom-kan. Dilanjutkan dengan menyelesaikan LP 4. Diperoleh solusi optimal z = 40,56, x1 = 4,44, dan x2 = 1. LP4 tidak di-fathom-kan, sehingga dibuat pencabangan di LP4, menjadi LP5 dan LP6, dengan Ruang LP5 = ruang LP4 + kendala (x1
5).
Ruang LP6 = ruang LP4 + kendala (x1
4).
Solusi optimal dari LP6 adalah x1 = 4 dan x2 = 1, dengan z = 37. Karena solusi LP 6 integer, maka LP6 di-fathom-kan. Nilai z = 37 sebagai batas bawah calon solusi optimal IP. Solusi optimal dari LP5 adalah x1 = 5 dan x2 = 0, dengan z = 40. Karena solusi LP5 juga integer, maka LP5 di-fathom-kan. Nilai z = 40 melebihi batas bawah sebelumnya (z = 37), sehingga solusi LP6 bukan solusi optimal IP. Calon batas bawah untuk solusi optimal IP adalah z = 40. Tinggal LP2 yang belum terselesaikan. Dari penghitungan diperoleh solusi optimal LP2 z = 39, x1 = 3, dan x2 = 3, yang berupa solusi integer, sehingga LP 2 di-fathom-kan. Nilai z = 39 tidak melebihi batas bawah terakhir (z = 40), sehingga solusi LP2 bukan solusi optimal IP.
8
Karena semua subproblem sudah di-fathom-kan, maka pencabangan berhenti. Diperoleh solusi optimal z = 40 dari penyelesaian LP 5 dengan x1 = 5, dan x2 = 0. Penggunaan metode Branch and Bound untuk menyelesaikan masalah IP pada contoh di atas dapat dilihat pada Gambar 3. Penghitungan nilai-nilai variabel dilakukan dengan bantuan software Lingo 10 dapat dilihat pada Lampiran 1. LP0 z = 41,25, x1 = 3,75, dan x2 = 2,25
x1
4
x1
3 LP2
LP1
z = 39, x1 = 3, dan x2 = 3
z = 41, x1 = 4, dan x2 = 1,8 x2
2
x2
1
LP4
LP3 Tanpa solusi
z = 40,56, x1 = 4,44, dan x2 = 1
x1
5
LP5 z = 40, x1 = 5, dan x2 = 0 batas bawah (optimal)
x1
4 LP6
z = 37, x1 = 4, dan x2 = 1
Gambar 3 Pencabangan dengan metode Branch and Bound untuk menemukan solusi IP.
9
