BAB 2 PROGRAM LINIER DAN TAK LINIER
2.1 Program Linier Program linier (Linear programming) adalah suatu masalah matematika yang mempunyai fungsi objektif dan kendala berbentuk linier untuk meminimalkan atau memaksimalkan suatu permasalahan dalam bidang optimisasi. Masalah program linier dapat dinyatakan dalam model berikut: Maks Z = cT y
(2.1)
Kendala A(x) 6 0
(2.2)
x>0
(2.3)
Dimana x adalah variabel, c dan b adalah koefisien vektor dan A adalah matriks. Ekpresi untuk memaksimalkan atau meminimalkan disebut fungsi tujuan z = cT x, dan Ax 6 b disebut fungsi kendala.
Pemecaham program linier
dapat dilakukan dengan metode grafik, akan tetapi untuk fungsi objektif atau kendala mempunyai tiga variabel atau lebih metode grafik sulit atau tidak dapat dilakukan. Suatu prosedur umum untuk menyelesaikan permasalahan program linier disebut metode simpleks.
10
11 2.2 Metode Pemecahan 2.2.1 Metode Grafik Pemecahan program linier dengan metode grafik dilakukan apabila hanya mempunyai dua variabel keputusan, artinya, hanya mempunyai dua dimensi. Sehingga prosedur metode grafik dapat digunakan untuk menentukan nilai variabel keputusan. Solusi optimum selalu berada pada titik pojok daerah layak 2.2.2 Metode Simpleks Suatu prosedur umum untuk menyelesaikan permasalahan program linier yang mempunyai tiga variabel atau lebih disebut metode simpleks. Metode ini dikembangkan oleh George Dantzig pada tahun 1947. Metode simpleks adalah suatu penyelesaian secara aljabar, tetapi konsep yang mendasarinya adalah geometris. Metode ini dirancang untuk menyelesaikan permasalahan program linier, baik dua variabel atau lebih yang penyelesaiannya dilakukan melalui perhitungan berulang (iterasi) dengan langkah yang sama hingga solusi optimum dicapai. Penyelesaian program linier dengan metode simpleks didasari dengan ide metode grafik, dimana solusi optimum selalu berada pada titik pojok daerah layak. Langkah-langkah metode simpleks dilakukan sebagai berikut:
1. Inisialisasi dimulai dengan memilih solusi awal dari sebuah titik pojok layak 2. Uji optimalitas dengan bergerak dari suatu titik pojok layak ke titik pojok
12 layak yang berdekatan. Pergerakan akan meningkatkan atau penurunan nilai variabel non-basis, sehingga akan meningkatkan fungsi tujuan untuk masalah maksimalisasi atau menurunkan nilai fungsi tujuan untuk masalah minimalisasi. 3. Iterasi dilakukan berulang-ulang sampai diperoleh solusi yang lebih baik dan iterasi berhenti apabila solusi optimum diperoleh.
Untuk mempermudah perhitungan simpleks, bentuk baku model program linier dapat diubah ke dalam bentuk tabel, dan disebut tabel simpleks. Langkahlangkah perhitungan dalam algoritma simpleks adalah sebagai berikut.
1. Inisialisasi dengan menetapkan n-m variabel non-basis awal sama dengan nol, dimana n jumlah variabel dan m banyak kendala 2. Uji optimalitas, solusi layak basis sudah optimal jika dan hanya jika setiap koefisien dalam baris nol adalah tidak negatif. Bila tidak, dilakukan iterasi untuk mendapatkan solusi layak basis berikutnya 3. Iterasi pertama dilakukan dengan menetukan variabel basis yang masuk dengan memilih variabel (secara otomatis variabel non-basis) yang memiliki koefisien paling negatif dalam suatu kolom tertentu, dimana kolom itu disebut kolom sumbu (pivot). 4. Kemudian iterasi kedua dilakukan uji rasio minimum, yaitu:
13
a. Mengambil masing-masing koefisien dalam kolom sumbu yang berinilai positif, b. Menetapkan baris yang memiliki rasio terkecil dari hasil pembagian kolom ruas kanan dengan koefisien kolom sumbu, c. Variabel basis pada baris rasio terkecil adalah variabel yang keluar, dan digantikan dengan variabel basis yang masuk dalam kolom variabel basis tabel simpleks berikutnya.
2.2.3 Metode Reduced Gradient Metode reduced gradient digunakan untuk mengeluarkan beberapa variabel keputusan dari kendala linier dengan mengurangi ruang matriks dari kendala (Murtagh dan Saunders, 1982). Masalah LP dinyatakan sebagai berikut. Min f (x)
(2.4)
Kendala A(x) = b
(2.5)
x ∈ Rn Partisi variabel keputusan x ke dalam variabel terikat atau basic (xB ) dan variabel bebas atau superbasic (xS ) sehingga dapat dinyatakan menjadi: xB x= xS
(2.6)
14 Akibatnya, matriks A dipartisi ke dalam matriks B dan S, sehingga persamaan kendala (2.6) dinyatakan menjadi:
xB Ax = [B S] =b xS
(2.7)
Dimana matriks B adalah matriks kuadratik, dan sisanya adalah matriks S. Mempertimbangkan ∆x, yaitu suatu pergerakan variabel x, sehingga Pers.(2.6) dapat dinyatakan menjadi:
xkB
∆xB xB − = ∆x = xS − xkS ∆xS
(2.8)
Persamaan (2.7) dan (2.8) dapat memenuhi persamaan (2.6). Oleh karena itu BxB + SxS = b dan BxkB + SxkS = b dapat dinyatakan menjadi; B∆xB + S∆xS = 0
(2.9)
atau ∆xB = −BS∆xS
(2.10)
Sehingga ∆x dapat dinyatakan menjadi: −1 −B xB ∆xS ∆x = I
(2.11)
∆x = Z∆xS
(2.12)
atau
15
−1 −B xB disebut sebagai transformasi matriks Dimana Z = I
Dari derivatif kedua ekspansi deret Taylor dari f(x) pada iterasi ke - k, xk , maka dapat dinyatakan menjadi: f (x) = f (xk ) + ∇f (xk )T ∆x + 1/2(∆xT )∇x f (xk )∆x
(2.13)
Hasil subsitusi Pers.(2.12) ke dalam Pers.(2.13) menjadi: f (xS ) = f (xk ) + ∇f (xk )T Z∆xS + 1/2 (∆xS )T Z T ∇x f (xk )Z∆xS
(2.14)
Dinyatakan reduced gradien gRT = ∇f (xk )T z dan reduced Hessi HR = z T ∇x f (xk )z, sehingga Pers.(2.13) (2.14) dapat dinyatakan menjadi: f (xs ) = f (xk ) + gRT ∆xS + 1/2(∆xS )T HR ∆xS Kondisi penting untuk syarat minimum dipenuhi bila gRT + HR ∆xS = 0
(2.15) δf = 0, yaitu; δ∆xS (2.16)
Oleh karena itu, HR ∆xS = gRT adalah sistem linier dari persamaan dalam (n − m) variabel. 2.3 Program Tak Linier Program tak linier (Non linear programming (NLP)) adalah suatu program dalam masalah optimisasi yang mempunyai fungsi objektif tidak linier dan beberapa atau semua fungsi kendala tidak linier, akan tetapi tidak diketahui konveks atau tidak konveks. Pembahasan tentang program tak linier dapat dilihat dalam
16 Luenberger (1984), Sugden (1992), Hiller dan Lieberman (2005), Boyd dan Vandenberghe (2009). Model program tak linier (NLP) dapat dinyatakan seperti berikut ini. Min f (x)
(2.17)
Kendala g(x) 6 0
(2.18)
h(x) = 0
(2.19)
x>0 Dimana f(x) adalah fungsi tak linier, h(x) dan g(x) keduanya fungsi tak linier atau salah satu tidak linier dengan n variabel keputusan. Pemecahan masalah program tak linier adalah untuk menentukan nilai variabel X = (x1 , x2 , ..., xn ) dari kendala yang memperoleh solusi optimum (minimum atau maksimum) untuk fungsi objektif. Terdapat beberapa bentuk masalah dalam program tak linier, bentuknya tergantung pada ciri-ciri fungsi objektif dan kendala. Sehingga pemecahan yang digunakan akan berbeda sesuai dengan ketidaklinieran fungsi objektif dan kendala yang muncul dalam berbagai bentuk, seperti fungsi konveks atau tidak konveks. Akibatnya daerah layak dapat menjadi menjadi daerah layak konveks atau tak konveks. 2.3.1 Fungsi Tak Linier 2.3.1.1 Himpunan Konveks dan Tak Konveks Definisi 2.1: Himpunan C disebut himpunan konveks atau konkaf, apabila semua titik pada segmen garis melalui sembarang dua titik dalam himpunan C juga ele-
17 men himpunan C. Definisi 2.2: Misalkan xi , xj ∈ R titik-titik yang dapat dibuat dalam bentuk λxi + (1 − λ)xj untuk 0 6 λ 6 1 disebut kombinasi garis dari xi dan xj . Definisi 2.3: Suatu himpunan C ⊂ R disebut himpunan konveks apabila untuk setiap sebarang dua elemen xi , xj ∈ C termuat dalam λxi + (1 − λ) xj untuk 0 6λ6 1 Definisi 2.4. Suatu himpunan NC ⊂ R disebut himpunan tak konveks apabila untuk setiap sebarang dua elemen xi , xj ∈ NC terdapat titik xk sedemikian sehingga xk pada λxi + (1 − λ)xj untuk 0 6 λ 6 1 tetapi xk ∈ / NC .
2.3.1.2 Fungsi Konveks dan Konkaf Fungsi konveks adalah suatu fungsi yang memenuhi untuk setiap dua titik xi dan xj , dapat ditarik garis yang menghubungkan f (xi ) dan f (xj ) pada fungsi tersebut (Luenberger, 1984). Definisi 2.5: Suatu fungsi f(x) disebut fungsi konveks apabila untuk sebarang dua titik xi dan xj pada Rn dipenuhi f (λxi + (1 − λ)xj 6 λf (xi ) + (1 − λ)f (xj ), untuk
18 0 6 λ 6 1. Suatu fungsi f(x) dikatakan fungsi konveks kuat (strictly) apabila untuk sebarang dua titik, xi dan xj pada Rn dipenuhi f (λxi + (1 − λ)xj
>
λf (xi ) + (1 − λ)f (xj ), untuk 0 6 λ 6 1 Definisi 2.6: Suatu fungsi f(x) dikatakan fungsi konkaf apabila untuk sebarang dua titik xi dan xj pada Rn dipenuhi f (λxi + (1 − λ)xj > λf (xi ) + (1 − λ)f (xj ), untuk 0 6 λ 6 1. Suatu fungsi f(x) disebut fungsi konkaf kuat (strictly) apabila untuk sebarang dua titik xi dan xj pada Rn dipenuhi f (λxi + (1 − λ)xj
<
λf (xi ) + (1 − λ)f (xj ), untuk 0 6 λ 6 1 2.2.1.3 Fungsi tak Konveks Definisi 2.7: Suatu fungsi f(x) dikatakan tak konveks, apabila fungsi tak linier yang tidak dapat dinyatakan fungsi konveks atau konkaf. Definisi 2.8: Suatu fungsi f(x) disebut tak konveks apabila untuk sebarang dua titik xi dan xj pada Rn terdapat suatu titik xk ∈ λf (xi ) + (1 − λ)f (xj ) untuk 0 6 λ 6 1 tidak memenuhi f (λxi + (1 − λ)xj > λf (xi ) + (1 − λ)f (xj ), untuk 0 6 λ 6 1.
19 2.2.1.4 Daerah Layak Konveks Definisi 2.9: Daerah layak F adalah konveks apabila untuk setiap dua titik pada daerah layak F, semua kombinasi konveks titik-titik dalam F juga dalam daerah layak F. Dalam permasalahan optimisasi, daerah layak konveks dalam fungsi objektif F, dinyatakan dalam F = {x : x ∈ Rn , h(x) = 0, g(x) 6 0, x > 0} dapat digambarkan sebagai berikut.
Daerah layak F(x) adalah konveks, karena untuk sebarang titik x1 , x2 ∈ F , setiap kombinasi konveks dari titik-titik x1 , dan x2 dalam daerah layak F, yaitu x = λx1 + (1 − λ)x2 ∈ F untuk semua nilai λ, dimana 0 6 λ 6 1. 2.2.1.5 Daerah Layak Tak Konveks Definisi 2.10. Daerah layak dikatakan tidak konveks apabila beberapa titik dalam garis yang menghubungkan dua titik tidak berada dalam daerah layak. Definisi 2.11. Daerah layak F dikatakan tidak konveks apabila kombinasi konveks dari sebarang dua titik dalam F tidak dalam daerah layak F.
20 Dalam permasalahan optimisasi, daerah layak tak konveks dari daerah layak F = x : x ∈ Rn , h(x) = 0, gi (x) 6 0, i = 1, ..., n , dapat digambarkan sebagai berikut.
Daerah layak F(x adalah tidak konveks, karena untu sebarangk dua titik titik x1 , x2 ∈ F (x) terdapat titik xk ∈ / F (x) sedemikian sehingga xk = λ x1 + (1 − λ) x2 ∈ / F (x) untuk semua nilai λ untuk 0 6 λ 6 1. 2.3.2 Metode Pemecahan Membahas masalah program tak linier tidak terlepas dari pemecahan masalah fungsi tak linier. Terdapat beberapa pendekatan yang digunakan untuk pemecahan fungsi tak linier dalam rangka mencari titik ekstrim. Perbedaan pendekatan tergantung kepada bentuk fungsi dan tujuan yang akan dicapai. Pendekatan atau metode yang biasa digunakan dalam pemecahan fungsi tak linier, seperti deret Taylor, fungsi Lagrange, dan Kondisi Kuhn-Tucher, pendekatan tersebut dapat dilihat dalam Rao (2009), Mital (1976), Bronson (1996), Chachuat (2007). Pemecahan itu diuraikan secara ringkas berikut ini
21 2.3.2.1 Deret Taylor Deret Taylor digunakan untuk mengembangkan konsep dasar dari fungsi objektif, yaitu dengan gradient fungsi dan matriks Hessian untuk memperoleh karakteristik solusi optimal dari pengujian konveksitas suatu fungsi dan titik ekstrim. Andaikan fungsi f(x) adalah fungsi yang dapat dideferensialkan secara kontinu dan mempunyai nilai riel dari X dalam Rn . Dapat diambil x + δx sebagai persekitaran dari x dalam Rn sedemikian sehingga ∆X = {δx1 , δx2 , ..., δxn } dan X + ∆x = {x1 + δx1 , x2 + δx2 , ..., xn + δxn }, dimana derivatif dari f(x) adalah i h ∂f ∂f ∂f , , ..., , sehingga deret Taylor untuk f(x) dalam variabel n dapat ∇f = ∂x ∂xn 1 ∂x2 ∂f dinyatakan dengan f {x1 + δx1 , x2 + δx2 , ..., xn + δxn } = f (x1 , x2 , ..., xn )+ f (δx1 ∂x 1 ∂f ∂f ∂f ∂f ∂f 2 + δx2 ∂x + ... + δxn ∂x ) + 12 f (δx1 ∂x + δx2 ∂x + ... + δxn ∂x ) + ... + n1 f (δx1 n n 2 1 2 ∂f ∂f n ∂f ∂f ∂f n+1 ∂f 1 +δx2 ∂x +...+δxn ∂x ) + n+1 f (δx1 ∂x +δx2 ∂x +...+δxn ∂x ) ∂x1 n n 2 1 2
Matriks Hessian dari fungsi f(x) sebagai matriks n x n, yaitu: ∂2f ∂2f ∂2f , ..., 2 , ∂x1 ∂xn ∂ x1 ∂x1 ∂x2 ∂2f ∂2f ∂2f ∂x ∂x , ∂ 2 x , ..., ∂x ∂x 2 1 2 2 n H(x) = ............, ............, .......... ∂2f ∂2f ∂2f , , ..., 2 ∂xn ∂x1 ∂xn ∂x2 ∂ xn
Sehingga deret Taylor dapat dinyatakan menjadi:
(2.20)
22 1 F (x + ∆x) = f (x) + (∆x)1 ∇f (x) + (∆x)1 H(x)∆x + E(x, ∆x) k ∆x k2 (2.21) 2 Dimana E(x, ∆x) → 0, dan k ∆x k→ 0 2.3.2.2 Titik Ekstrim Titik ekstrim adalah suatu titik maksimum atau minimum dari seluruh nilai variabel suatu fungsi. Titik yang membuat f (x) minimum mengakibatkan (−f (x)) menjadi maksimum atau sebaliknya. Hal itu berarti, suatu masalah maksimum dapat diubah menjadi masalah minimum, dan sebaliknya. Definisi 3.11. Titik x∗ ∈ D disebut minimum lokal dari fungsi f(x) pada D apabila terdapat persekitaran ε > 0 dari x∗ sedemikian sehingga untuk semua x dalam persekitaran x∗ memenuhi f (x) > f (x∗ ). Titik x∗ ∈ D disebut maksimum lokal dari fungsi f(x) pada D apabila terdapat persekitaran ε > 0 dari x∗ sedemikian sehingga untuk semua x di persekitaran x∗ memenuhi f (x) 6 f (x∗ ). Definisi 3.12. Titik x∗ ∈ D disebut minimum global dari fungsi f(x)pada D apabila untuk semua x ∈ D memenuhi f (x) > f (x∗ ). Titik x∗ ∈ D disebut maksimum global dari fungsi f(x) pada D apabila untuk semua x ∈ D memenuhi f (x) 6 f (x∗ ). Beberapa syarat penting untuk mengidentifikasi titik stationer dengan menggunakan fungsi gradient dan matriks Hessi, yaitu: 1. Kondisi cukup untuk minimum lokal pada titik x∗ a. Fungsi gradien ∇f (x∗ ) = 0
23
b. Matriks Hessi H(x∗ ) adalah definit positif 2. Kondisi cukup untuk maksimum lokal pada titik x∗ a. Fungsi gradien ∇f (x∗ ) = 0 b. Matriks Hessi H(x∗ ) adalah definit negatif 3. Kondisi cukup untuk titik sadle (pelana) pada titik x∗ a. Fungsi gradien ∇f f (x∗ ) = 0 b. Matriks Hessi H(x∗ ) adalah indefinit
2.3.2.3 Fungsi Lagrange Suatu metode klasik menyangkut pemecahan permasalahan pada program linier atau non-linier adalah dengan metode pengali Lagrange. Metode ini digunakan untuk mencari solusi dari suatu permasalahan titik ekstrim dari beberapa variabel dan fungsi yang memenuhi semua persamaan kendala. Prosedur metode ini dimulai dengan merumuskan fungsi Lagrange seperti berikut. Maks/min f (x)
(2.22)
Kendala: gi (x( i, ., xn )) = bi , i = 1, , m; m < n
(2.23)
xi > 0 dimana f(x) dan g(x) adalah fungsi yang dapat dideferensialkan dan mempunyai nilai riel untuk setiap variabel x.
24 Fungsi F(x) dinyatakan dengan ekspresi:
F (x, λ) = λ0 f (x) + λ1 [b1 − g1 (x)] + ... + λm [bm − gm (x)]
(2.24)
disebut fungsi lagrange, dan bilangan λi disebut pengali lagrange, dengan memenu hi persyaratan pengali, apabila x∗ = x∗1 , ..., x∗n adalah solusi dari masalah pada suatu titik ekstim dari Pers.(2.22) - (2.23), maka terdapat bilangan yang paling kecil tidak nol dari pengali lagrange λ∗ = λ∗0 , ..., λ∗m sedemikian sehingga titik-titik x∗ , λ∗ adalah titik stationer dari fungsi lagrange yang memenuhi variabel xj dan λi , i 6= 0 disebut sebagai variabel bebas. Kondisi penting untuk titik stationer dari fungsi lagrange adalah suatu kepastian sistem pada persamaan m + n Teorema 2. 1. Misalkan x ∈ L ⊆ Rn , f(x) dan g(x) adalah fungsi yang dapat dideferensialkan dan mempunyai nilai real untuk setiap x dalam L. Jika f(x) mempunyai relatif ekstrim di x terhadap kendala gk (x) = 0, k = 1, ..., m, maka terdapat λk , k = 1, ..., m sedemikian sehingga x∗ adalah titik stationer. Bukti: Tanpa mengurangi keumuman dari kendala gk (x) = 0, diasumsikan Jacobian sebagai berikut: ∂(g1 , g2 , ..., gm ) 6= 0 ∂(x1 , x2 , ..., xm )
(2.25)
25
Karena x∗ adalah relatif ekstrim dari f(x), maka (∆x)(∇f (x∗ )) = 0, atau pada x∗ berlaku: ∂x1
∂f ∂f ∂f + ∂x2 + ... + ∂xn =0 ∂x1 ∂x2 ∂xn
(2.26)
Karena kendala gk (x) = 0, k = 1, ..., m, ∂xj , j = 1, ..., m tidak bebas linier, maka dengan pendeferensialan diperoleh: ∂gk ∂gk ∂gk ∂x1 + ∂x2 + ... + ∂xn = 0, k = 1, ..., m ∂x1 ∂x2 ∂xn
(2.27)
Dengan mengalikan Pers. (2. 27) dengan λ1 , λ2 , ..., λm , dan menambahkannya ke Pers. (2. 26), diperoleh: n X ∂f ∂g1 ∂g2 ∂gm ( + λ1 + λ2 + ... + λm )∂xi = 0 ∂xi ∂xi ∂xi ∂xi i=1
(2.28)
Dengan mempertimbangkan persamaan: (
∂f ∂g1 ∂g2 ∂gm + λ1 + λ2 + ... + λm ) = 0, i = 1, ..., m ∂xi ∂xi ∂xi ∂xi
(2.29)
atau
λ1 ∂gm ∂g1 ∂g2 ∂f , , ..., ∂x1 ∂x1 ∂x1 ∂x1 λ2 ∂g1 ∂g2 ∂f ∂gm ∂x , ∂x , ..., ∂x ∂x 2 2 2 2 . = ......., ......., ....... .... . ∂f ∂g1 ∂g2 ∂gm , , ..., ∂xn ∂xn ∂xn ∂xm λm
(2.30)
Karena Pers.(2.24) merupakan matriks non singular, maka terdapat nilai unik dari λ1 , λ2 , ..., λm yang memenuhi Pers.(2.29).
26 Dengan mengurangi variabel xi , i = 1, ..., n dalam Pers.(2.28) maka diperoleh: n X i=m+1
(
∂f ∂g1 ∂g2 ∂gm + λ1 + λ2 + ... + λm )∂xi = 0 ∂xi ∂xi ∂xi ∂xi
Karena terdapat variabel xi , i = m + 1, ..., n adalah variabel bebas linier mengakibatkan: ∂g1 ∂g2 ∂gm ∂f + λ1 + λ2 + ... + λm ∂xi = 0, i = m + 1, ..., n ∂xi ∂xi ∂xi ∂xi
(2.31)
Berdasarkan penyederhanaan Pers.(2.29) dan (2.31) diperoleh: ∂L(x, λ) = 0, i = 1, ..., n pada x∗ ∂xi
(2.32)
Dengan demikian x∗ adalah titik stationer dari f(x). 2.3.2.4 Kondisi Kuhn-Tucher Solusi optimal dari permasalahan program tak linier dianalisis oleh Karush (1939) dan Kuhn-Tucher (1951). Kondisi optimal Karush-Kuhn-Tucher (KKT) adalah valid untuk pemecahan masalah program tak linier dengan fungsi objektif dan kendala tak linier yang mempunyai kendala bentuk pertidaksamaan atau persamaan. Jadi, syarat perlu untuk memperoleh solusi optimal dari program tak linier adalah adanya kondisi Karush-Kuhn-Tucher dari model berikut. Min f (x)
(2.33)
Kendala g(x) 6 0
(2.34)
x>0 Berdasarkan fungsi Lagrange diperoleh L(x, λ) = f (x) + λgi (x), i = 1, ..., n, dimana λ > 0 adalah pengali Lagrange. Sehingga untuk memperoleh titik stationer
27 harus memenuhi;
∂L(x,λ) ∂xi
= 0, i = 1, ..., n sehingga kondisi Karush-Kuhn-Tucher
(KTT) adalah; m
∂L(x, λ) ∂f X ∂gk = + (λk ) = 0, i = 1, ..., n ∂xi ∂xi k=1 ∂gi
(2.35)
dan gk (x) 6 0 λk gk (x) = 0 , k = 1, ..., m λk > 0
(2.36)
atau m X ∂gk ∂f (λk + )>0 ∂xi k=1 ∂gi " # m X ∂gk ∂f (λk xj + ) = 0 ∂xi k=1 ∂gi xj > 0
(2.37)
dan gi (x) 6 0 λi gi (x) = 0 , k = i, ..., m λi > 0
(2.38)
Dimana kondisi Pers.(2.34)-(2.35) merupakan syarat perlu pada (x∗ , λ∗ ) untuk titik pelana (saddle) dari f (x, λ) dengan variabel x tidak dibatasi dan λ > 0. Dengan kondisi yang sama Pers. (2.36)-(2.37) untuk x > 0, λ > 0. Apabila f(x) dan gi (x) adalah fungsi konveks dengan titik sadle (x∗ , λ∗ ), λ∗ > 0 dari L(x, λ)
28 dengan demikian x∗ adalah titik minimum dari f(x) dengan kendala gi (x). Karena f(x) adalah fungsi konveks maka f(x) hanya mempunyai satu titik optimum yang menjadi titik minimumnya. Jadi kondisi ini merupakan solusi perkiraan kondisi Kuhn-Tucher yang memberikan titik minimum dari f(x). Sehingga masalah program tak linier mempunyai solusi optimum hanya jika terdapat m bilangan λ1 , ..., λm sedemikian sehingga semua kondisi berikut dipenuhi. m
X ∂gi ∂f = λk 6 0, ∀i = 1, ..., n di xj = x∗j (1) ∂xj ∂x j k=1 ∂f (2) x∗j ( ∂x − j
m P k=1
∂gi λk ∂x ) = 0, ∀i = 1, ..., n di xj = x∗j j
(4) λi (gi (x∗j ) − bi ) = 0, ∀i = 1, ..., m (5) x∗i > 0, ∀i = 1, ..., n (6) λi > 0, ∀i = 1, ..., m, dimana λi disebut pengali Lagrange’ 2.3.1 Program Konveks Program konveks suatu klas khusus dari program tak linier yang memiliki fungsi tujuan linier atau tidak linier dan kendala tidak linier, dimana semua solusi layak berada dalam daerah layak. Program konveks berarti fungsi adalah konveks, sehingga daerah pencarian adalah konveks. Fungsi dapat dideferensialkan dari banyak variabel bila matriks Hessian (suatu matriks untuk semua derivative keduanya) adalah definit positif pada semua (entire) domainnya, dan masalah program konveks mengacu pada masalah optimisasi yang hanya mempunyai satu minimum lokal, dan dapat menemukan minimum global.
29 Model program konveks dinyatakan sebagai berikut; Min f (x)
(2.39)
Kendala gi (x) 6 0, i = 1, ..., 0
(2.40)
x>0 Dimana fungsif, gi , ..., gm : Rn → R adalah fungsi konveks Definisi 3.13. Misal C adalah himpunan konveks yang tidak kosong di dalam Rn . Jika f : C → R adalah konveks pada C, maka min f (x) disebut program x∈C
konveks. Dalam program konveks diasumsikan minimum lokal menjadi minimum global. Nilai f (x∗ ) adalah minimum pada titik x∗ yang memenuhi f (x) > f (x∗ ) untuk k x − x∗ k< δ, dan minimum global dalam daerah layak F nilai pada f (x∗ ) adalah minimum yang memenuhi memenuhi f (x) > f (x∗ ), ∀x ∈ F, dan menentukan nilai x = x∗ menjadi solusi minimum dilakukan dengan derivarif pertama dari f(x), yaitu
∂f (x) ∂xj
= 0, pada x = x∗ , untuk j = 1, 2, ..., n.
Teorema 2.2. Misal x∗ adalah minimum lokal pada program konveks, maka x∗ adalah juga minimum global. Bukti: Misalkan variabel x∗ adalah minimum lokal, berarti ∃ε > 0 sedemikian sehingga f (x) > f (x∗ ), ∀x ∈ Cε (x∗ ). Dengan kontradiksi, andaikan x∗ bukan minimum global, maka ∃x ∈ C sedemikian sehingga f (x) < f (x∗ ). Misalkan λ ∈ [0, 1] adalah pilihan sedemikian sehingga dengan konveksitas pada C, dan f(x) dalam C, berarti f (x) = λx + (1 − λ) x∗ ∈ Cε (x∗ ).
30 Selanjutnya, dengan konveksitas dari f pada C, berarti; f (x) 6 λ f (x) + (1 − λ)f (x∗ ) < λf (x∗ ) + (1 − λ)f (x∗ ) 6 f (x∗ ) atau f (x) 6 f (x∗ ). Hal ini bertentangan dengan pengandaian, bahwa x∗ adalah minimum lokal. Jadi haruslah x∗ adalah minimum global. Dalam masalah program konveks, dengan penambahan asumsi bahwa f dan g adalah fungsi konveks. Biasanya, bila masalah tidak diasumsikan pada masalah konveks, maka masalah mempunyai solusi optimum lokal . Hasil yang diperoleh berdasarkan penggunaan metode eksak dapat menemukan solusi global, disebut metode optimisasi global. 2.3.2 Program Tak Konveks Program tak konveks adalah suatu program yang mempunyai fungsi objektif tak linier dan beberapa atau semua kendala tak linier. Masalah program tak konveks mungkin mempunyai banyak titik optimum lokal, hal itu akan memerlukan banyak waktu untuk mengidentifikasi apakah masalah mempunyai solusi atau tidak, apabila solusi yang akan dicari adalah minimum global. Oleh karena itu, masalah pemecahan masalah program tak konveks pada umumnya lebih sulit, bahkan fungsi adalah sangat smooth (halus). Dalam program tak konveks, diasumsikan bahwa minimum lokal tidak menjadi minimum global, atau maksimum lokal tidak menjadi maksimum global. Masalah tersebut digambarkan seperti dalam gambar 2.5 berikut.
31
2.4 Metode Pemecahan Beberapa penggunaan algoritma yang efektif dalam pemecahan masalah NLP dapat dilihat dalam Bertsimas (1999), Boyd dan Vabdenberghe (2004), Fletcher (2000), Nocedal dan Wright (2006), pemecahan itu diuraikan secara ringkas berikut ini. 2.4.1 Line Search Pencarian garis (line search) digunakan untuk masalah optimisasi tak berkendala dengan fungsi objektif non-linier. Pada tiap iterasi suatu penaksiran dari fungsi non-linier dipertimbangkan dan (i) suatu petunjuk pencarian ditentukan, (ii) penjang langkah pencarian selama arah pengambilan diperhitungkan. Pendekatan berbeda untuk menentukan arah dan panjang langkah seperti Steepest des− cent, N ewton, Quasi − N ewton, Conjugate Direction methods.
32 2.4.2 Trust Region Daerah kepercayaan (Trust region) adalah suatu metode yang digunakan sebagai suatu alternatif untuk pencarian garis. Pada tiap-tiap iterasi, pencarian dari titik terbaik menggunakan perkiraan yang dibatasi ke dalam suatu trust region, dan ditetapkan dengan suatu panjang langkah maksimum. Pendekatan ini didorong oleh fakta bahwa perkiraan dari fungsi non-linier pada titik yang diberikan tidak dapat menjadi titik terbaik. Oleh karena itu trust region dapat menunjukkan bagian seharusnya yang dapat memberikan perkiraan yang baik. Kemudian arah dan panjang langkah pencarian memberikan perbaikan terbaik untuk nilai fugsi objektif sampai daerah kepercayaan diambil. 2.4.3 Penalty and Augmented Lagrangian Metode P enalty mendefinisikan ulang fungsi objektif dari N LP untuk memperoleh kelayakan dan nilai optimalitas dari suatu penambahan syarat-syarat solusi yang menetapkan ketidaklayakan solusi. Ketika suatu fungsi penalty meminimalkan solusi dari N LP awal. Hal itu disebut eksak, dengan kata lain minimalisasi fungsi penalty mengarahkan kepada solusi optimal dari masalah asli. Suatu contoh dari metode penalty eksak adalah metode Augmented Lagrangian yang membuat dengan jelas penggunaan dari penduga pengali Lagrange.
33 2.4.4 Active Set Himpunan aktif (active set) adalah himpunan variabel aktif dalam suatu persamaan kendala. Metode himpunan aktif adalah suatu metode iteratif untuk pemecahan masalah N LP dengan pertidaksamaan kendala. Berdasarkan pengertian kendala dalam himpunan aktif, suatu pergerakan mengidentifikasi titik baru untuk iterasi selanjutnya. Algoritma simpleks oleh Dantzig (1956) adalah suatu metode kendala aktif untuk pemecahan masalah program linier. Suatu hasil yang efektif dan luas digunakan dalam kasus khusus dengan metode himpunan aktif untuk masalah N LP adalah program kuadratik (Quadratic programming), yaitu suatu rangkaian pemecahan masalah untuk menaksir masalah NLP terakhir. Suatu contoh seperti penyelesaian menggunakan metode Newtons dengan kondisi KKT dari masalah N LP . Metode himpunan aktif adalah suatu metode yang mengestimasi himpunan variabel aktif dari solusi optimal. Masalah N LP dibagi dalam dua bagian himpunan kendala, yaitu pertidaksamaan yang menjadikannya sebagai kendala aktif, dan kendala tidak aktif. Pertidaksamaan kendala dalam himpunan tidak aktif dianggap sebagai pertidaksamaan kuat pada solusi optimum dan mengabaikan yang sangat utama. Sisa masalah dipecahkan dengan suatu metode untuk memecahkan persamaan kendala dari masalah optimisasi. Pemecahan masalah NLP terdiri dari dua tahap iterasi yang memberikan suatu estimasi himpunan aktif dari solusi. Tahap pertama adalah tahap kelayakan, dima-
34 na fungsi objektif diabaikan ketika titik layak ditemukan pada kendala Ax=b dan Dx > f . Tahap kedua adalah tahap optimalitas, dimana fungsi objektif diminimalkan ketika kelayakan diperbaiki. Kedua tahap dari algoritma terkait dengan perubahan minimalisasi fungsi dari suatu fungsi yang menggambarkan tingkat dari ketidaklayakan kepada fungsi objektif. Metode ini mempunyai prosedur untuk meninjau ulang himpunan aktif, salah satu cara adalah dengan penghapusan pertidaksamaan kendala dari kendala asli, atau menambahkan pertidaksamaan kendala dari himpunan tak aktif ke dalamnya. Pembahasan metode himpunan aktif (Active set) dapat dilihat dalam Panier (1987), Murty dan Yu (1997), Oberlin dan Wright (2006). Kontribusi metode active set tersebut mendasari pemecahan masalah NLP dengan kendala aktif.
