BAB 2 KAJIAN PUSTAKA
2.1 Masalah Optimisasi dan Program Non Linier Menurut Asghar (2000), secara garis besar masalah optimisasi terbagi dalam beberapa tipe berikut: 1. Masalah optimisasi tanpa kendala. 2. Masalah pemrograman linear. 3. Masalah pemrograman kuadratis. 4. Masalah pemrograman nonlinear/optimisasi nonlinear. Sedangkan masalah optimisasi nonlinear menurut Bronson (1997) terbagi dalam tiga bagian, yaitu: 1. Masalah optimisasi nonlinear satu variable. 2. Masalah optimisasi nonlinear multi variable tanpa kendala. 3. Masalah optimisasi nonlinear multi variable dengan kendala. Dilihat dari bentuk kendalanya, masalah optimisasi nonlinear dengan kendala terbagi menjadi 3 bagian, yaitu: 1. Fungsi kendala berbentuk persamaan 2. Fungsi kendala berbentuk pertidaksamaan 3. Fungsi kendala berbentuk campuran persamaan dan pertidaksamaan.
6
7 Hamdy (2003) menawarkan beberapa metode penyelesaian berdasarkan kriteria permasalahan: 1. Pemrograman Terpisah, jika fungsi obyektif dan kendala merupakan fungsi yang terpisah (separable). 2. Pemrograman Kuadratik, jika fungsi obyektif berupa fungsi kuadrat, dan kendalanya fungsi linear. 3. Pemrograman Geometrik. Teknik ini telah dikembangkan oleh R. Duffin dan C. Zener tahun 1964. Metode ini dapat digunakan jika fungsi obyektif P Qn aij dan kendala berupa fungsi f (X) = N j=1 Uj , dimana Uj = cj i=1 xi , j = 1, 2, . . . , N , dan cj > 0, dan N berhingga. Pangkat aij tidak terbatas dalam tanda. Fungsi f (X) berupa fungsi polynomial. 4. Metode Kombinasi Linear, jika kendalanya berupa fungsi linear. 5. Algoritma SUMT (Sequential Unconstrained Maximization Technique), jika fungsi obyektifnya cekung dan fungsi kendalanya cembung, serta daerah fisibelnya memiliki interior. Metode ini mengubah optimisasi berkendala menjadi optimisasi tanpa kendala, hampir mirip dengan metode Pengali Lagrange. Bronson (1997) juga mengemukakan beberapa metode penyelesaian masalah optimisasi nonlinear berkendala, yaitu: 1. Pengali Lagrange (Lagrange Multipliers), jika kendalanya berupa persamaan. 2. Persyaratan Kuhn-Tucker (Kuhn-Tucker condition), jika kendalanya berupa pertidaksamaan, dan masing-masing fungsi obyektif dan kendala memiliki turunan parsial pertama yang kontinu. 3. Metode arah layak (feasible directions), jika kendala berupa pertidaksamaan. Metode ini dapat digunakan jika daerah fisibel memiliki interior. Metode ini akan konvergen ke maksimum global hanya jika iterasi awal dekat dengan solusi sebenarnya. Daerah fisibel tidak akan memiliki interior jika dua dari kendala pertidaksamaannya merupakan perubahan dari kendala persamaan. 4. Metode fungsi penalty, yang mengubah masalah berkendala (kendala berbentuk persamaan), menjadi masalah tanpa kendala. Jika masalah awal adalah
8 memaksimumkan z = f (x) dengan kendala hi (x) = 0 , maka masalah diubah menjadi memaksimumkan q = f (x) + cP (x), dengan c > 0 yang disebut bobot penalty. Penyelesaian dari bentuk yang terakhir ini menjadi penyelesaian dari masalah awal jika tiap-tiap hi (x) = 0 .
2.2 Penyelesaian Sistem Persamaan Nonlinear Pandang suatu sistem persamaan nonlinear n × n. f1 (x1 , x2 , . . . , xn ) = 0 f2 (x1 , x2 , . . . , xn ) = 0 .. . fn (x1 , x2 , . . . , xn ) = 0 Sistem persamaan nonlinear tersebut dapat diselesaikan secara iterasi dengan metode Newton-Raphson, dengan menggunakan iterasi xk+1 = xk + δxk ,
k = 0, 1, 2, . . .
dimana x0 adalah titik awal.
2.3 Metode Homotopy Newton Jika masalah SPNL adalah f (X) = 0, dengan f = (f1 , f2 , . . . , fn )T dan X = (x1 , x2 , . . . , xn )T , maka penyelesaiannya adalah: X = X0 − J −1 .H dimana: X0 : titik awal yang diambil H : fungsi homotopy yang berbentuk H(x, t) = f (x) − (1 − t)f (x0 ), 0 ≤ t ≤ 1 J : matrik Jacobian
9 2.4 Metode Newton-Rapshon Masalah optimisasi non linear tanpa kendala dapat diselesaikan secara iteratif dengan menggunakan metode Newton-Rapshon. Ide dasar metode ini adalah melakukan pendekatan fungsi nonlinear dengan fungsi kuadrat. Pendekatan kuadratik dari fungsi f : Rn → R yang memiliki derivatif tingkat dua dapat diperoleh dengan menggunakan deret Taylor di sekitar titik x(k) . 1 f (x) ∼ f (x(k) ) + (∆x)∇f (x(k) ) + (∆x)2 ∇2 f (x(k) ) 2
2.5 Optimisasi Nonlinear Berkendala dengan Pengali Lagrange Metode yang sering digunakan untuk menyelesaikan masalah optimisasi non linear berkendala adalah pengali Lagrange (Lagrange multipliers). Bentuk umumnya adalah: Minimum
f (x)
Kendala
h(x) = 0
dimana x ∈ Rn , f : Rn → R, h : Rm → Rn , m < n. Diasumsikan bahwa fungsi h diferensiabel. ∇f (x∗ ) + λ∇h(x∗ ) = 0
2.6 Heuristik Kata heuristik berasal dari kata Heuriskein berasal dari bahasa Yunani yang berarti menemukan. Pertama kali, Polya (1947) mengemukakan bahwa heuristik bertujuan untuk mempelajari metode dan aturan penemuan, atau membantu menyelesaikan problema. Penelitian operasional memandang heuristik sebagai prosedur untuk mengurangi pencarian dalam kegiatan penyelesaian problema,
10 Tonge (1961). Sementara menurut Nicholson (1971) metode heuristik adalah suatu prosedur untuk menyelesaikan problema dengan pendekatan intuisi, yang di dalamnya problema dapat diterjemahkan dan digali untuk memperoleh penyelesaian yang dapat diterima. Heuristik baik digunakan pada saat: 1. Data yang tidak tepat atau terbatas. 2. Model yang disederhanakan. 3. Metode tepat yang terpercaya tidak tersedia. 4. Untuk memberikan penyelesaian awal/pemandu pencarian/mengurangi jumlah calon penyelesaian. 5. Kebutuhan pengulangan untuk menyelesaikan problema yang sama. 6. Keterbatasan sumber lain, misal dana, waktu, tenaga kerja, pengetahuan, dll. Suatu heuristik yang baik hendaknya memperhatikan hal-hal sebagai berikut: 1. Kesederhanaan. 2. Memori yang dipakai. 3. Kecepatan waktu komputasi. 4. Ketepatan. 5. Metode harus memperoleh penyelesaian yang baik dalam waktu singkat, tidak sensitif terhadap perubahan parameter. 6. Menerima beberapa titik awal, tidak perlu layak. 7. Kriteria penghentian yang baik Burkard et. al. (1997)
Studi mengenai heuristic ini mula-mula tidak begitu jelas, hanya garis besarnya dan jarang disajikan secara rinci , dan tidak diikat oleh etika matematika
11 (bukti, teorema, konvergensi, optimalitas). Hal ini dirasakan akibat oleh reaksi yang lambat antara praktisi-peneliti praktisi. Namun akhir-akhir ini gambaran tersebut mulai berubah, terbukti dengan semakin banyaknya tulisan terkait dalam journal ilmiah terkemuka, dan sekarang dalam tahap percepatan, praktisi ditekan oleh kemerosotan produktivitas untuk menganalisis problema manajemen yang rumit, dengan ketersediaan sumber daya yang terbatas, sehingga menimbulkan bertambahnya kebutuhan untuk menggunakan heuristik. Keterbukaan peneliti akhirnya menyadari bahwa kekuatan matematika tidak menjamin sukses sistem OR dalam praktek. Kebanyakan dari alasan di atas telah diajukan oleh orang-orang praktisi, namun perlu dicatat bahwa, bukan dianjurkan untuk mengesampingkan metode optimisasi. Jadi, jika algoritma optimisasi dapat diterapkan secara efektif untuk menyelesaikan problema, maka algoritma tersebut dapat dipakai. Dalam aplikasi berskala besar, seperti penempatan fasilitas, perbedaan satu atau dua persen dapat berakibat kerugian jutaan rupiah. Untuk keputusan keuangan demikian, dipandang lebih baik untuk pengumpulan data dan pembentukan modal, karena itu teknik optimisasi lebih sesuai. Umumnya tanpa memandang spesifikasi problema, suatu heuristik yang baik harus memperhatikan hal-hal sebagai berikut: 1. Kesederhanaan kepada pemakai. 2. Memori pada computer yang dipakai. 3. Kecepatan, yaitu waktu komputasi memadai yang tidak berkembang secara polinomial ataupun eksponensial bila ukuran problema bertambah. 4. Ketepatan, yaitu galat kuadrat rataan (mean square error) kecil, yang dapat mengakibatkan peningkatan kemungkinan diperolehnya penyelesaian yang baik. 5. Metode harus memperoleh penyelesaian baik, dalam waktu yang cukup singkat, untuk berbagai problema, dan tidak terlalu sensitif karena perubahan parameter. 6. Menerima beberapa titik awal, dan tidak perlu layak (f easible).
12 7. Menghasilkan penyelesaian ganda dengan memilih parameter masukan, atau menggeser penyelesaian akhir. 8. Kriteria penghentian yang baik. 9. Estimasi statistik dari optimum sebenarnya. 10. Kemampuan interaktif dengan analisis dalam pengambilan keputusan. Suatu heuristik yang ideal adalah yang memiliki semua sifat di atas. Perlu dicatat bahwa heuristik problema dependent, yang mengambil keuntungan dari struktur problema tertentu, misal pada Mawengkang dan Murtagh (1985).
