I PENDAHULUAN 1.1 Latar Belakang Istilah Pemrograman Geometrik (PG) diperkenalkan oleh Duffin, Peterson, dan Zener pada tahun 1967. Istilah ini diambil dari masalah-masalah geometri yang dapat diformulasikan sebagai PG. Pemrograman Geometrik adalah suatu tipe masalah optimalisasi matematik yang ditandai oleh fungsi objektif dan fungsi-fungsi kendala yang memiliki bentuk khusus. Dalam karya ilmiah ini PG dibedakan menjadi 2, yaitu PG takberkendala dan PG berkendala. Untuk menentukan solusi optimumnya digunakan metode yang sama,
yaitu menentukan masalah dual terlebih dahulu kemudian dengan prosedur yang ada dihitung solusi optimum dari masalah dual tersebut. Setelah diperoleh solusi optimum masalah dual maka akan diperoleh solusi PG. Selain itu, ingin dicari pengaruh perubahan koefisien fungsi objektif masalah PG terhadap solusi optimumnya. 1.2 Tujuan Tujuan penulisan karya ilmiah ini adalah mempelajari penyelesaian masalah PG, dan melakukan analisis sensitivitas terhadap PG takberkendala.
II LANDASAN TEORI Pada bab ini akan diberikan teori yang menjadi landasan pengerjaan karya ilmiah ini. Berikut diberikan beberapa definisi dan teorema yang digunakan dalam penulisan karya ilmiah ini. 2.1 Fungsi Kalkulus Dalam subbab ini diberikan beberapa jenis fungsi kalkulus yang digunakan dalam penulisan karya ilmiah ini. Definisi 2.1.1 (Fungsi Naik dan Fungsi Turun) Jika f suatu fungsi dengan f ( x1 ) < f ( x2 ) , ∀x1 < x2 dalam suatu selang I maka f disebut fungsi naik pada selang I. Jika berlaku f ( x1 ) > f ( x2 ) , maka f disebut fungsi turun pada selang I. (Stewart, 1998) Definisi 2.1.2 (Fungsi Eksponensial) Fungsi eksponensial adalah fungsi yang berbentuk f ( x) = a x dengan a suatu konstanta positif dan x ∈ . (Stewart, 1998) Definisi 2.1.3 (Fungsi Eksponensial Natural) Fungsi eksponensial natural adalah fungsi yang berbentuk f ( x) = e x dengan e ≈ 2.718 dan x ∈ . (Stewart, 1998)
Teorema 2.1.1 (Hukum Eksponen) Jika a > 0 dan a ≠ 1 , maka f ( x) = a x merupakan fungsi kontinu dengan daerah asal dan daerah nilai (0, ∞) . Khususnya, a x > 0 untuk setiap x . Jika 0 < a < 1 maka f ( x) = a x merupakan fungsi turun. Jika a > 1
maka f ( x) = a x merupakan fungsi naik. Jika a, b ≠ 0 dan x, y ∈ , maka 1. a x + y = a x a y ax 2. a x − y = y a 3. ( a x ) y = a xy 4. (ab) x = a x b x . (Stewart, 1998) Definisi 2.1.4 (Fungsi Logaritma) Jika f ( x) = log a x , maka f disebut fungsi logaritma dengan bilangan pokok a, dengan a suatu konstanta positif, x > 0 dan x ∈ . (Stewart, 1998) Definisi 2.1.5 (Fungsi Logaritma Natural) Jika f ( x) = log e x = ln x , maka f disebut fungsi logaritma natural, dengan x > 0 dan x∈ . (Stewart, 1998) Teorema 2.1.2 (Hukum Logaritma) a >1, fungsi f ( x) = log a x Jika merupakan fungsi naik dengan daerah asal (0, ∞) dan daerah nilai . Jika x, y > 0 dan r bilangan real sebarang, maka
2
1. log a ( xy ) = log a x + log a y ⎛x⎞ 2. log a ⎜ ⎟ = log a x − log a y ⎝ y⎠ 3. log a ( x r ) = r log a x . (Stewart, 1998) Teorema 2.1.3 (Hukum Logaritma Natural) Fungsi f ( x) = ln x merupakan fungsi naik dengan daerah asal (0, ∞) dan daerah nilai . Jika x, y > 0 dan r bilangan real sebarang, maka 1. ln( xy ) = ln x + ln y ⎛x⎞ 2. ln ⎜ ⎟ = ln x − ln y ⎝ y⎠ 3. ln( x r ) = r ln x . (Stewart, 1998)
Definisi 2.1.6 (Global Minimizer) Misalkan f fungsi bernilai real
yang
terdefinisi pada himpunan D ⊆ . Titik x* di D adalah global minimizer untuk f di D jika f (x* ) ≤ f (x) untuk setiap x di D, dengan x vektor berukuran n. (Peressini et al., 1988) n
Definisi 2.1.7 (Global Maximizer) Misalkan f fungsi bernilai real
yang
terdefinisi pada himpunan D ⊆ . Titik x* di D adalah global maximizer untuk f di D jika f (x* ) ≥ f (x) untuk setiap x di D, dengan x vektor berukuran n. (Peressini et al., 1988) n
Teorema 2.1.4 (Pertaksamaan Holder) Misalkan x, y ∈ n , maka untuk p > 1, q > 1 , dengan
1 1 + = 1 , berlaku p q 1
1
n ⎛ n p ⎞p ⎛ q ⎞q xi yi ≤ ⎜ ∑ xi ⎟ ⎜ ∑ yi ⎟ . ∑ i =1 ⎝ i =1 ⎠ ⎝ i =1 ⎠ (Boyd & Vandenberghe, 2004)
pemrograman geometrik dan pengoptimuman konveks.
Definisi 2.2.1 (Himpunan Konveks) Himpunan C ⊂ n disebut himpunan konveks jika dan hanya jika untuk setiap x dan y di C, dan setiap λ dengan 0 ≤ λ ≤ 1 maka λ x + (1 − λ )y ∈ C. (Peressini et al., 1988) Definisi 2.2.2 (Fungsi Konveks) Misalkan f fungsi bernilai real yang terdefinisi pada himpunan konveks C di n maka 1. fungsi f disebut konveks di C jika f (λ x + [1 − λ ]y ) ≤ λ f (x) + [1 − λ ] f (y ) untuk setiap x dan y di C dan setiap λ dengan 0 ≤ λ ≤ 1 , 2. fungsi f disebut konveks sempurna di C jika f (λ x + [1 − λ ]y ) < λ f (x) + [1 − λ ] f ( y ) untuk setiap x dan y di C dan setiap λ dengan 0 < λ < 1 . (Peressini et al., 1988) Teorema 2.2.1 (Fungsi Konveks untuk Fungsi Satu Variabel) Jika f terdiferensialkan dua kali pada I , maka f fungsi konveks pada I jika dan hanya jika f ''( x) ≥ 0 untuk setiap x ∈ I . Jika f ''( x) > 0 untuk setiap x ∈ I , maka f disebut fungsi konveks sempurna. (Peressini et al., 1988) Definisi 2.2.3 (Fungsi Afin) Fungsi f : n → m disebut fungsi afin jika merupakan penjumlahan fungsi linear dan suatu konstanta, notasinya f (x) = Ax + b , dengan A matriks berukuran m × n , x vektor berukuran n, dan b vektor berukuran m . (Boyd & Vandenberghe, 2004)
n
2.2 Pengoptimuman Konveks dan Pemrograman Geometrik Pengoptimuman konveks terdiri atas pemrograman linear dan pemrograman nonlinear. Pemrograman geometrik termasuk pemrograman nonlinear. Berikut ini diberikan beberapa landasan yang berhubungan dengan
Contoh 2.2.1 Misalkan didefinisikan fungsi f sebagai berikut f ( x1 , x2 , x3 ) = 2 x1 + x2 + 1.5 x3 + 3.2 ⎛ x1 ⎞ ⎜ ⎟ = ( 2 1 1.5 ) ⎜ x2 ⎟ + 3.2 , ⎜x ⎟ ⎝ 3⎠ f merupakan fungsi afin.
3
Teorema 2.2.2 Misalkan f
Bukti (lihat Lampiran 1). fungsi
konveks
yang
terdefinisi pada himpunan konveks C ⊂ n . Jika λ1 , λ2 ,..., λk adalah bilangan-bilangan taknegatif, dengan λ1 + λ2 + ... + λk = 1 dan x1 , x 2 ,..., x k titik di C , maka
⎛ k ⎞ k f ⎜ ∑ λi xi ⎟ ≤ ∑ λi f (xi ). ⎝ i =1 ⎠ i =1 (Peressini et al., 1988) Bukti (lihat Peressini et al., 1988) Definisi 2.2.4 (Bentuk Umum Pengoptimum an Konveks) Suatu pengoptimuman konveks didefinisikan mempunyai bentuk umum ⎫ Minimumkan f 0 ( x) ⎪⎪ fi (x) ≤ 0, i = 1,..., m ⎬ (2.2.1) terhadap ⎪ hi ( x) = 0, i = 1,..., p ⎪⎭ fungsi konveks untuk dengan f 0 , fi 1 ≤ i ≤ m , hi fungsi afin untuk 1 ≤ i ≤ p , x adalah vektor berukuran n dengan x j > 0 untuk 1 ≤ j ≤ n .
(Boyd & Vandenberghe, 2004) Contoh 2.2.2 Minimumkan terhadap
f 0 (x) = x12 + x22
f1 ( x) =
x1 ≤0 1 + x22
h1 ( x) = ( x1 + x2 ) 2 = 0.
Terlihat h1 merupakan fungsi kuadrat sehingga menurut Definisi 2.2.3 h1 bukan fungsi afin. Karena salah satu syarat sudah terbukti tidak terpenuhi, maka permasalahan pada Contoh 2.2.2 bukan pengoptimuman konveks. Tetapi permasalahan pada Contoh 2.2.2 bisa dikonversi menjadi pengoptimuman konveks dengan cara sebagai berikut: 2
Karena 1 + x2 > 0 maka agar pertaksamaan x1 terpenuhi haruslah ≤0 1 + x22 sehingga kendala pertaksamaan f1 ( x) = x1 ≤ 0 . (i) Dapat diperlihatkan bahwa adalah fungsi konveks.
x1 ≤ 0
menjadi
f 0 dan
(ii) Fungsi kendala ( x1 + x2 ) 2 = 0 terpenuhi jika dan hanya jika x1 + x2 = 0 , sehingga fungsi h1 menjadi h1 (x) = x1 + x2 = 0 , sehingga berdasarkan Definisi 2.2.3, h1 adalah fungsi afin. Berdasarkan (i) dan (ii) maka permasalahan Contoh 2.2.2 dapat dimodelkan menjadi, Minimumkan f 0 (x) = x12 + x22 ⎫ ⎪ terhadap f1 (x) = x1 ≤ 0 (2.2.2) ⎬ h1 (x) = x1 + x2 = 0 ⎪⎭ Permasalahan (2.2.2) adalah pengoptimuman konveks karena f0 , f1 fungsi konveks, dan h1 fungsi afin.
Berikut ini diberikan dua definisi dan dua teorema yang berperan penting dalam pemrograman geometrik.
Definisi 2.2.5 (Fungsi Monomial) Fungsi g yang terdefinisi untuk x = ( x1 , ..., xn ) dengan xi > 0 untuk setiap i = 1, 2,3,..., n disebut fungsi monomial atau monomial jika g ( x ) = cx1a1 x2a2 ...xnan , dengan c konstanta positif dan ai ∈ R . (Boyd & Vandenberghe, 2004)
Contoh 2.2.3 Misalkan didefinisikan f ( x1 , x2 ) = 2.3 x12 x2−0.15 h( x1 , x2 ) = −2.3x12 x2−0.15 . Fungsi f adalah fungsi monomial sedangkan h bukan fungsi monomial, karena koefisien pada h bukan konstanta positif. Berikut dapat diperlihatkan bahwa fungsi monomial tertutup terhadap operasi perkalian dan pembagian. Misalkan f dan g fungsi monomial dengan f ( x) = cx1a1 x2a2 ...xnan g ( x ) = dx1b1 x2b2 ...xnbn ,
maka (i) ( fg )( x) = f ( x) g (x) = (cx1a1 x2a2 ...xnan )( dx1b1 x2b2 ...xnbn )
f1
= cdx1( a1 + b1 ) x2( a2 + b2 ) ...xn( an + bn ) .
4
Karena c, d > 0 maka cd > 0 , xi > 0, dan untuk setiap ai , bi ∈ , maka ai + bi ∈ untuk i = 1, 2,..., n, sehingga menurut Definisi 2.2.5 fg merupakan fungsi monomial. (ii)
f f (x) (x) = g g ( x)
=
n
n
∏ ( x )δ ≤ ∑ δ x i
i
i =1
i =1
i i
,
dengan persamaannya berlaku jika dan hanya jika x1 = x2 = ... = xn . (Peressini et al., 1988) Bukti (lihat Lampiran 2)
cx1a1 x2a2 ...xnan dx1b1 x2b2 ...xnbn
⎛c⎞ = ⎜ ⎟ x1( a1 − b1 ) x2( a2 − b2 ) ...xn( an −bn ) . ⎝d ⎠ c > 0 , xi > 0 dan Karena c, d > 0 maka d maka ai − bi ∈ , untuk setiap ai , bi ∈ untuk i = 1, 2,..., n sehingga menurut Definisi f merupakan fungsi monomial. 2.2.5 g Dari (i) dan (ii) terbukti bahwa fungsi monomial tertutup terhadap operasi perkalian dan pembagian.
Definisi 2.2.6 (Fungsi Posinomial) Fungsi f yang terdefinisi di x = ( x1 , x,..., xn ) untuk setiap x j > 0 disebut posinomial
jika m
n
i =1
j =1
f ( x) = ∑ ci ∏ ( x j ) ij , a
dengan ci konstanta positif dan aij ∈ R untuk 1 ≤ i ≤ m dan 1 ≤ j ≤ n . (Peressini et al., 1988)
Dengan perkataan lain fungsi posinomial merupakan penjumlahan dari beberapa fungsi monomial. Contoh 2.2.4 Didefinisikan fungsi f sebagai berikut f ( x1 , x2 ) = 2.3 x12 x2−0.15 + 4 x1 2 x2 + 3 x2
dengan x = ( x1 , x2 ) di
2
, x1 , x2 > 0. Karena
c1 = 2.3 > 0 , c2 = 4 > 0 , c3 = 3 > 0 , dan x1 , x2 > 0, maka berdasarkan Definisi 2.2.6
f adalah fungsi posinomial. Teorema 2.2.3 (Pertaksamaan AritmatikGeometrik (A-G)) Jika x1 , x2 ,..., xn bilangan-bilangan real positif dan jika δ1 , δ 2 ,..., δ n adalah bilangan-bilangan positif dengan δ1 + δ 2 + ... + δ n = 1 , maka
Teorema 2.2.4 (Perluasan Pertaksamaan AG) Misalkan x1 , x2 ,..., xn bilangan-bilangan positif. Jika δ1 , δ 2 ,..., δ n bilangan-bilangan positif dan λ = δ1 + δ 2 + ... + δ n , maka δi
λ
n ⎛ xi ⎞ ⎛ n ⎞ λ ⎜ ∑ xi ⎟ ≥ λ ∏ ⎜ δ ⎟ , ⎝ i =1 ⎠ i =1 ⎝ i ⎠ persamaannya berlaku jika dan hanya jika δ ⎛ n ⎞ xi = i ⎜ ∑ x j ⎟ , λ ⎝ j =1 ⎠ untuk i = 1, 2,..., n . (Peressini et al., 1988)
Bukti (lihat Lampiran 3) 2.3 Fungsi Lagrange Misalkan diberikan masalah pengoptimuman yang mempunyai bentuk umum sebagai berikut ⎫ Minimumkan f (x) ⎪ terhadap g i ( x) = 0 (2.3.1) ⎬ n ⎪ dengan i = 1, 2,..., m, x ∈ .⎭
Salah satu metode yang dapat digunakan untuk menyelesaikan masalah (2.3.1) adalah metode pengali Lagrange. Metode ini dimulai dengan pembentukan fungsi Lagrange yang didefinisikan sebagai berikut. Definisi 2.3.1 (Fungsi Lagrange) Misalkan diberikan masalah pengoptimuman (2.3.1). Fungsi Lagrange dari masalah tersebut didefinisikan m
L(x, λ ) = f (x) − ∑ λi gi (x)
(2.3.2)
i =1
dengan λi ≥ 0. (Kuhn, 2006) Teorema 2.3.1 Syarat perlu bagi sebuah fungsi objektif f ( x) dengan fungsi kendala gi ( x) = 0, dengan i = 1, 2,..., m, agar mempunyai nilai
5
maksimum lokal pada titik x* adalah turunan parsial pertama dari fungsi Lagrange-nya yang didefinisikan pada (2.3.2) terhadap setiap
elemennya
∂L = 0, ∂x j
∂L =0 ∂λi
dan
untuk
i = 1, 2,..., m, dan j = 1, 2,..., n.
(Kuhn, 2006)
III PEMROGRAMAN GEOMETRIK Pemrograman geometrik (PG) merupakan pengoptimuman suatu fungsi posinomial terhadap kendala monomial atau posinomial. Suatu PG didefinisikan mempunyai bentuk standar : Minimumkan f 0 (x) ⎫ ⎪ terhadap f i (x) ≤ 1, i = 1,..., k ⎬ (3.1) ⎪ gi ( x) = 1, i = 1,..., l ⎭ dengan f 0 , fi fungsi posinomial, g i fungsi monomial, x vektor berukuran n, dan x j > 0 untuk 1 ≤ j ≤ n . (Boyd & Vandenberghe, 2004) Contoh 3.1 Misalkan diberikan pemrograman sebagai berikut. Minimumkan f 0 ( x, y, z ) = x −1 y −1/ 2 z −1 + 2.3 xz + 4 xyz terhadap f1 ( x, y, z ) = (1/ 3) x −2 y −2 + (4 / 3) y1/ 2 z −1 ≤ 1 f 2 ( x, y, z ) = xy 2 + 2 xyz −1 + 3 x −1/ 2 z ≤ 1 g ( x, y, z ) = (1/ 2) xy = 1, dengan x, y, z > 0 . Contoh 3.1 merupakan PG bentuk standar dengan n = 3 , k = 2 dan l = 1.
Contoh 3.2 Misalkan diberikan suatu permasalahan sebagai berikut. Minimumkan f 0 ( x, y, z ) = x −1 y −1/ 2 z −1 + 2.3 xz + 4 xyz terhadap f1 ( x, y, z ) = (1/ 3) x −2 y −2 + (4 / 3) y1/ 2 z −1 ≤ 1 f 2 ( x, y, z ) = 3xyz ≤ 1 g ( x, y, z ) = (−1/ 2) xy = 1. dengan x, y, z > 0 . Contoh 3.2 bukan PG karena g bukan fungsi monomial.
Contoh 3.3 Misalkan diberikan fungsi objektif dari suatu permasalahan sebagai berikut Maksimumkan f ( x1 , x2 , x3 ) = x1 x2 x3 dengan x1 , x2 , x3 > 0 . Dapat diperlihatkan bahwa memaksimumkan x1 x2 x3 ekuivalen dengan meminimumkan
1 . x1 x2 x3 Misalkan f mempunyai nilai maksimum di titik x* = ( x1* , x2* , x3* ) maka f (x* ) ≥ f (x)
(menurut Definisi 2.1.7)
⇔ x x x ≥ x1 x2 x3 * * * 1 2 3
⇔
1 1 ≤ xxx x1 x2 x3 * * * 1 2 3
(karena x1 , x2 , x3 , x1* , x2* , x3* > 0 ), menurut Definisi 2.1.6,
1 minimum x1 x2 x3
di titik x* = ( x1* , x2* , x3* ) . Jadi terbukti bahwa memaksimumkan x1 x2 x3 ekuivalen dengan meminimumkan
1 , x1 x2 x3
untuk x1 , x2 , x3 > 0 . 3.1 Pengubahan PG Standar ke Bentuk Umum Pengoptimuman Konveks Dengan menggunakan hukum eksponensial dan hukum logaritma maka bentuk PG standar pada (3.1) dapat diubah menjadi pengoptimuman konveks dengan cara sebagai berikut: (i) Pada fungsi monomial g (x) = cx1a1 x2a2 ...xnan disubstitusikan
persamaan yi = ln xi ⇔ xi = e yi sehingga fungsi g menjadi g (e y1 , e y2 ,..., e yn ) = c(e y1 ) a1 (e y2 ) a2 ...(e yn ) an = ce a1 y1 ea2 y2 ...ean yn .
