BAB 1
PENDAHULUAN
1.1 Latar Belakang
Zaman yang semakin berkembang membuat persoalan semakin kompleks, tidak terkecuali persoalan yang melibatkan persoalan matematika. Dalam pemecahannya, matematika memegang peranan cukup penting terutama dalam perkembangan ilmu pengetahuan dan teknologi baik secara matematika murni maupun matematika terapan.
Matematika terapan misalnya dijumpai dalam perkembangan bidang industri yang menghendaki tercapainya suatu kondisi yang optimal yang sebelumnya hanya persoalan
sederhana
yang
berbentuk
linear
karena
perkembangan
zaman,
kompleksitas semakin meningkat sehingga memunculkan persoalan yang berbentuk nonlinear. Hal tersebut disebabkan karena munculnya faktor-faktor yang membuat ketaklinearan suatu fungsi. Selain itu, banyak faktor-faktor yang menjadi penghambat dalam
optimisasi
sehingga
memunculkan satu
atau
lebih
kendala
dalam
mengoptimalkan suatu fungsi.
Banyak metode yang telah dikembangkan untuk memecahkan persoalan nonlinear di antaranya seperti Metode Pengali Lagrange, Metode Karush-Kuhn Tucker. Akan tetapi, metode-metode tersebut sering tidak dapat digunakan untuk persoalan program nonlinear berskala besar.
Oleh karena itu, penulis menggunakan metode Sequential Quadratic Programming (SQP) untuk memecahkan persoalan nonlinear berkendala dimana metode ini menggunakan pendekatan Lagrange dan metode Newton tanpa harus
Universitas Sumatera Utara
mengkonversikan ke barisan persoalan minimimisasi yang tidak berkendala. Metode ini mengkonversi persoalan nonlinear menjadi bentuk persoalan pemrograman kuadratis.
Berdasarkan uraian di atas maka penulis memberi judul tulisan ini dengan “Metode Sequential Quadratic Programming (SQP) untuk Menyelesaikan Persoalan Nonlinear Berkendala”.
1.2 PERUMUSAN MASALAH
Permasalahan yang akan dibahas adalah menyelesaikan persoalan nonlinear berkendala dengan metode Sequential Quadratic Programming (SQP).
1.3 TINJAUAN PUSTAKA
Menurut Bradley dkk (1976), persoalan umum optimisasi adalah memilih n variabel keputusan
dari daerah fisibel yang diberikan untuk mengoptimasi
(maksimum atau minimum) fungsi tujuan yang diberikan
dari variabel keputusan. Persoalan ini disebut persoalan pemrograman nonlinear jika fungsi tujuannya nonlinear dan atau daerah fisibelnya ditentukan oleh kendala nonlinear. Bentuk umumnya:
subject to:
Untuk beberapa keadaan, maksimum dan minimum lokal disebut global. Fungsi yang minimum lokal merupakan global disebut konveks. Fungsi yang maksimum lokal merupakan maksimum global disebut konkaf. Karena alasan ini fungsi
konveks
selalu
diminimumkan
sedangkan
fungsi
konkaf
selalu
dimaksimumkan (Bradley dkk, 1976). Menurut Luenberger (1984), fungsi konveks
Universitas Sumatera Utara
adalah dimana untuk setiap dua titik y dan z, dapat ditarik garis yang menghubungkan f(y) dan f(z) pada fungsi tersebut.
Kekonvergenan untuk barisan bilangan riil (Dennis dan Schnabel, 1983): Diberikan sebuah metode iterasi sehingga menghasilkan barisan titik sebuah titik awal
dari
, ingin diketahui apakah iterasi konvergen ke solusi
diasumsikan bahwa
menyatakan barisan bilangan riil
. Jika , maka
definisi berikut menyatakan sifat yang dibutuhkan: Jika
maka barisan
konvergen ke
dikatakan
jika
Jika dalam tambahan, ada sebuah konstanta
dan sebuah bilangan bulat
sehingga untuk setiap
Richard Bronson (1996) dalam bukunya yang berjudul “Teori dan Soal-soal Operation Research”, menyatakan bahwa persamaan Lagrange dari persoalan nonlinear seperti yang telah dipaparkan yaitu sebagai berikut:
dimana
adalah tetapan-tetapan (yang tidak diketahui) yang disebut
pengali Lagrange. Kemudian kita pecahkan sistem n+m persamaan
Syarat Kuhn-Tucker: (Winston dan Venkataramanan, 2003) 1. Andaikan persoalan nonlinear di atas adalah persoalan maksimisasi. Jika adalah solusi optimal dari persoalan tersebut, maka harus memenuhi m kendala dan harus ada pengali yang memenuhi
Universitas Sumatera Utara
2. Andaikan persoalan nonlinear di atas adalah persoalan minimisasi. Jika adalah solusi optimal dari persoalan tersebut, maka harus memenuhi m kendala dan harus ada pengali yang memenuhi
S.S Rao (1977) dalam bukunya yang berjudul “Optimization Theory and Application” menjelaskan bahwa pemrograman kuadratis merupakan persoalan optimasi nonlinear dimana fungsi tujuannya adalah fungsi minimisasi yang konveks dan semua kendalanya berbentuk persamaan atau pertidaksamaan linear. Bentuk umum persoalan pemrograman kuadaratis adalah sebagai berikut: Min. s.t
dimana
d11 d 21 d n1
d12 d 22 dn2
d1n d 2 n d nn
Pada fungsi tujuan di atas yaitu suku
a11 a A = 21 am1
a12 a22 am 2
a1n a2 n amn
menyatakan bagian kuadratis dari fungsi
tujuan dengan D adalah matriks definit positif simetri. Jika D=0 maka menjadi
Universitas Sumatera Utara
persoalan linear. Karena D adalah matriks definit positif maka f(x) adalah fungsi strictly convex.
Menurut Winston dan Venkataramanan (2003), metode untuk menyelesaikan persoalan pemrograman kuadratis yaitu metode Wolfe. Pertama, semua fungsi tujuan dan kendala harus ditambahkan variabel buatan pada masing-masing kendala dengan kondisi Kuhn-Tucker dan variabel basis belum jelas kemudian minimumkan jumlah variabel buatan. Metode wolfe merupakan versi modifikasi dari fase I pada metode simplex dua fase. Untuk menjamin bahwa solusi akhir (dengan variabel buatan sama dengan
nol)
memenuhi
kondisi
complementary
slackness,
metode
Wolfe
memodifikasi pilihan variabel simplex yang masuk: 1. Tidak diperbolehkan
dari kendala ke-i dan
kedua-duanya sebagai
variabel basis. 2. Tidak diperbolehkan variabel slack atau excess dari kendala ke-i dan kedua-duanya sebagai variabel basis. Dimitri P Bertsekas (2007) dalam jurnalnya yang berjudul “SQP and PDIP Algorithms for Nonlinear Programming” dikatakan bahwa metode Sequential Quadratic Programming digunakan untuk menyelesaikan persoalan nonlinear yang memiliki kendala dalam bentuk persamaan dengan bentuk umum : Min. f(x) s.t. h(x)=0 Metode Sequential Quadratic Programming menyerupai metode Newton yang digunakan untuk mencari penyelesaian pada optimisasi tidak berkendala. Ide utama dari SQP adalah memodelkan persoalan kendala yang berbentuk persamaan pada titik awal
kemudian mencari pendekatan
dengan subpersoalan pemrograman
kuadratis berbentuk:
dimana
Universitas Sumatera Utara
Metode Sequential Quadratic Programming atau yang juga dikenal sebagai metode Lagrange-Newton karena metode SQP merupakan penggabungan dari kedua metode tersebut. Algoritmanya adalah sebagai berikut: 1. Tentukan 2. Atur k=0 3. Ulang 4. Pecahkan sistem Langrange-Newton untuk menemukan 5. 6. 7. Sampai konvergen Metode SQP merupakan aplikasi dari metode Newton dengan memenuhi kondisi optimal KKT. Menurut Mark S. Gockenbach dalam jurnalnya yang berjudul “Introduction to Sequential Quadratic Programming”, metode SQP mencoba untuk memecahkan persoalan nonlinear secara langsung daripada mengubahnya ke barisan persoalan minimisasi yang tidak berkendala. Ide dasar analog dengan metode Newton untuk persoalan minimisasi yang tidak berkendala. Metode SQP dapat digunakan untuk menyelesaikan persoalan aplikasi yang kompleksitasnya tinggi (Schittkowski dan Yuan, 2010)
1.4 TUJUAN PENELITIAN
Tujuan dari penelitian ini adalah untuk mendapatkan penyelesaian dari persoalan nonlinear berkendala.
1.5 KONTRIBUSI PENELITIAN
Manfaat dari penelitian ini adalah 1.
Setiap mahasiswa dapat menemukan jawab optimal dari persoalan nonlinear berkendala persamaan maupun pertidaksamaan dengan menggunakan metode Sequential Quadratic Programming
Universitas Sumatera Utara
2.
Digunakan
sebagai
tambahan
informasi
dan
referensi
bacaan
untuk mahasiswa matematika, terlebih bagi mahasiswa yang hendak melakukan penelitian serupa.
1.6 METODE PENELITIAN
Penelitian ini adalah penelitian literatur yang disusun dengan langkah-langkah sebagai berikut: 1.
Membaca dan memahami persoalan pemrograman nonlinear dari buku dan jurnal.
2.
Mengambil contoh soal untuk dikerjakan sesuai dengan langkah-langkah yang telah didapat dari jurnal-jurnal.
3.
Menjelaskan tentang penyelesaian persoalan nonlinear berkendala persamaan dan pertidaksamaan dengan menggunakan metode Sequential Quadratic Programming (SQP).
Universitas Sumatera Utara
