Catatan Kuliah 10 Memahami dan Menganalisa Optimasi dengan Kendala Persamaan
1. Metode Lagrange Multiplier Misal diberikan masalah optimisasi sbb : OF : U = f ( x, y ) s.t : g ( x, y ) = c
Selanjutnya akan dipelajari bagaimana mencari titik stasioner dan syarat cukup bagi persoalan optimisasi di atas. Ada 2 pendekatan yang digunakan untuk menyelesaikan persoalan tersebut yaitu teknik substitusi dan Lagrange Multiplier (LM). Namun dalam kuliah ini hanya akan dipelajari metode LM. Bentuk fungsi Lagrange Multiplier (LM) dari permasalahan di atas adalah :
Ζ = f ( x, y ) + λ ⎡⎣c − g ( x, y ) ⎤⎦
(1)
dimana λ (baca : lambda) adalah Lagrange Multiplier. Untuk mencari titik stasioner dari Z , maka dilakukan FONC (First Order Necessary Condition). FONC : Ζx = 0 → fx − λ gx = 0
Ζy = 0 → fy − λgy = 0 Ζ λ = 0 → c − g ( x, y ) = 0
Contoh :
Tentukan nilai ekstrem dari : OF : U = x1 x2 s.t : x1 + x2 = 6 Maka fungsi Lagrange : Z = x1 x2 + λ ⎡⎣6 − ( x1 + x2 ) ⎤⎦ FONC : Ζ x1 = 0 → x2 − λ = 0
Ζ x2 = 0 → x1 − λ = 0 Z λ = 0 → 6 − x1 − x2 = 0
(2)
Dengan metode Cramer diperoleh solusi : x1* = 3 ; x2 * = 3 ; λ * = 3 Sehingga nilai stasioner : Z * = U * = 9 Selanjutnya nilai ini akan diuji dengan SOSC (Second Order Sufficient Condition) untuk mengetahui apakah nilai stasioner ini maksimum, minimum, atau bukan keduanya.
Pendekatan Total Differensial
Misalkan fungsi tujuan : U = f ( x, y ) FONC dapat ditentukan dengan total differensial kedua ruas : dU = f x dx + f y dy = 0
(3)
Misal diberikan fungsi kendala : g ( x, y ) = c Maka FONC : dg = g x dx + g y dy = 0 Karenanya untuk memenuhi FONC maka
(4) f fx = y gx g y
(5)
Berdasarkan persamaan (2) diperoleh : fx =λ gx
dan
fy gy
=λ
(6)
Interpretasi dari Lagrange Multiplier
Lagrange Multiplier atau λ * mengukur sensitivitas dari Z * terhadap perubahan dalam kendala. Misalkan dari FONC masalah optimisasi yang pertama di atas (Persamaan(2)), FONC : Ζx = 0 → fx − λ gx = 0 Ζy = 0 → fy − λgy = 0 Ζ λ = 0 → c − g ( x, y ) = 0
dimana x , y , dan λ adalah variabel endogen, dan satu-satunya variabel eksogen adalah c yaitu parameter dalam kendala.
Suatu perubahan dalam c , akan menyebabkan kurva dari kendala shifting. Secara khusus, efek dari kenaikan c (meningkatnya anggaran atau meningkatnya jumlah produksi) akan menunjukkan bagaimana solusi optimal dipengaruhi oleh relaksasi kendala. Ketiga persamaan dalam FONC di atas dapat dibentuk dalam fungsi implisit, yaitu : F j ( λ , x, y; c ) = 0 , dimana j = 1, 2,3
(7)
Maka determinan Jacobian : ∂F 1 ∂λ
∂F 1 ∂x
∂F 2 J = ∂λ
∂F 2 ∂x
∂F 3 ∂λ
∂F 3 ∂x
∂F 1 ∂y
0 ∂F 2 = −gx ∂y −gy ∂F 3 ∂y
−gx
−gy
f xx − g xx f yx − g yx
f xy − g xy f yy − g yy
(8)
Misalkan J ≠ 0 maka kita dapat menyatakan x * , y * , dan λ * sebagai fungsi implisit dari parameter c : x* = x * ( c )
;
y* = y * ( c )
;
λ* = λ * ( c )
(9)
Sehingga persamaan dalam equilibrium menjadi : f x ( x*, y *) − λ * g x ( x*, y *) ≡ 0 f y ( x*, y *) − λ * g y ( x*, y *) ≡ 0
(10)
c − g ( x*, y *) ≡ 0
Karena nilai optimal dari Z bergantung pada x * , y * , dan λ * , maka
Ζ* = f ( x*, y *) + λ * ⎡⎣c − g ( x*, y *) ⎤⎦
(11)
Total differensial Z * terhadap c : dΖ* dx * dy * dλ * dx * dy * ⎞ ⎛ = fx + fy + ⎡⎣ c − g ( x*, y *) ⎤⎦ + λ * ⎜1 − g x − gy ⎟ dc dc dc dc dc dc ⎠ ⎝
= ( fx − λ * gx )
dx * dy * dλ * + ( fy − λ * gy ) + ⎡⎣ c − g ( x*, y *) ⎤⎦ +λ* dc dc dc
Berdasarkan persamaan dalam equilibrium, maka
(12)
dΖ* =λ* dc
(13)
Artinya, Lagrange Multiplier (LM) mengukur efek dari suatu perubahan dalam kendala melalui parameter c terhadap nilai optimal dari fungsi objektif atau fungsi tujuan. Apabila c meningkat 1 satuan maka nilai fungsi tujuan akan meningkat atau menurun sebesar λ * satuan.
2. Kondisi Turunan Kedua Total Differensial Turunan Kedua
Misalkan fungsi tujuan : U = f ( x, y ) Total differensial kedua ruas, sehingga diperoleh : dU = f x dx + f y dy
(14)
Kemudian total differensial kembali kedua ruas : d 2U = d ( dU ) =
=
∂ ( dU ) ∂ ( dU ) dx + dy ∂x ∂y
∂ ∂ f x dx + f y dy ) dx + ( f x dx + f y dy ) dy ( ∂x ∂y
⎡ ⎛ ⎡ ∂dy ⎞ ⎤ ∂dy ⎞ ⎤ ⎛ = ⎢ f xx dx + ⎜ f xy dy + f y ⎟ ⎥ dy ⎟ ⎥ dx + ⎢ f yx dx + ⎜ f yy dy + f y ∂x ⎠ ⎦ ∂y ⎠ ⎦ ⎝ ⎣ ⎝ ⎣
= f xx dx 2 + f xy dydx + f y
∂dy ∂dy dx + f yx dxdy + f yy dy 2 + f y dy ∂x ∂y
(15)
⎡ ∂dy ∂dy ⎤ dx + dy ⎥ = f y d ( dy ) = f y d 2 y Karena f y ⎢ ∂ x ∂ y ⎣ ⎦
(16)
Maka, d 2U = f xx dx 2 + 2 f xy dxdy + f yy dy 2 + f y d 2 y
(17)
d 2U dapat ditransformasikan ke dalam bentuk kuadratik dengan bantuan kendala g ( x, y ) = c
Karena dg = 0 maka d 2 g = d ( dg ) = 0 Dengan cara yang sama diperoleh :
d 2 g = g xx dx 2 + 2 g xy dxdy + g yy dy 2 + g y d 2 y = 0
(18)
g g g xx 2 dx − 2 xy dxdy − yy dy 2 gy gy gy
(19)
d2y = −
Substitusi persamaan (19) di atas ke persamaan (17), menghasilkan : ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ f f f d 2U = ⎜ f xx − y g xx ⎟ dx12 + 2 ⎜ f xy − y g xy ⎟ dxdy + ⎜ f yy − y g yy ⎟ dy 2 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ gy gy gy ⎝ ⎠ ⎝ ⎠ ⎝ ⎠
(20)
Berdasarkan persamaan (6) maka persamaan (20) dapat dinyatakan dengan : d 2U = ( f xx − λ g xx ) dx 2 + 2 ( f xy − λ g xy ) dxdy + ( f yy − λ g yy ) dy 2
(21)
Differensial parsial persamaan (2) menghasilkan : Ζ xx = f xx − λ g xx Ζ xy = f xy − λ g xy = Z yx
(22)
Ζ yy = f yy − λ g yy Sehingga persamaan (21) menjadi : d 2U = Z xx dx 2 + 2 Z xy dxdy + Z yy dy 2
SOC (Second Order Condition)
Jadi untuk masalah optimisasi : OF : U = f ( x, y ) s.t : g ( x, y ) = c
SONC (Second Order Necessary Condition): Maksimum : d 2U negative semidefinite, dengan kendala dg = 0 Minimum : d 2U positive semidefinite, dengan kendala dg = 0
SOSC (Second Order Sufficient Condition) : Maksimum : d 2U negative definite, dengan kendala dg = 0 Minimum : d 2U positive definite, dengan kendala dg = 0
(23)
3. Bordered Hessian
Ingat kembali bahwa untuk optimisasi dengan 2 variabel tanpa kendala, bentuk kuadrat untuk kasus tersebut adalah : q = au 2 + 2huv + bv 2 dimana : u = dx ;
v = dy ;
a = f xx
;
b = f yy
;
h = f xy = f yx
Saat ini kita menghadapi fungsi 2 variabel dengan kendala, dimana : OF : U = f ( x, y ) s.t : g ( x, y ) = c
Dari fungsi tujuan di atas, diketahui bentuk kuadratnya adalah : q = au 2 + 2huv + bv 2 dimana : u = dx ;
(24) v = dy ;
a = f xx
;
b = f yy
;
h = f xy = f yx
Sedangkan dari fungsi kendala, diketahui bentuk differensial totalnya adalah : dg = g x dx + g y dy = 0
(25)
Apabila juga diasumsikan bahwa : u = dx ;
v = dy ; g x = α
maka persamaan (25) dapat ditulis sebagai : α u + β v = 0 Dari persamaan (26) diperoleh : v = −
αu β
; gy = β , (26) (27)
Substitusi persamaan (27) ke (24) : ⎛ αu ⎞ ⎛ αu ⎞ q = au + 2hu ⎜ − ⎟ + b⎜− ⎟ ⎝ β ⎠ ⎝ β ⎠
2
2
= au 2 − 2h =
a β 2u 2
β2
−
α 2 α2 u + b 2 u2 β β 2hαβ u 2
β2
+
bα 2u 2
= ( a β 2 − 2hαβ + bα 2 )
β2 u2
β2
(28)
2
Karena
⎛u⎞ u2 = >0 ⎜ ⎟ β2 ⎝β ⎠
,
maka
nilai
q
sangat
bergantung
dari
nilai
aβ 2 − 2hαβ + bα 2 dan ternyata, 0 α
β
α β
h = 2hαβ − αβ 2 − bα 2 b
a h
(29)
Dengan demikian, dapat dinyatakan bahwa : ⎧ positive definite ⎫ q⎨ ⎬ subject to α u + β v = 0 ⎩ negative definite ⎭
0 α iff
α β
a h
β
⎧< 0 h⎨ ⎩> 0 b
Dengan kata lain,
⎧ positive definite ⎫ q⎨ ⎬ subject to dg = 0 ⎩ negative definite ⎭
iff
0 gx
gx Z xx
gy
Z yx
gy ⎧< 0 Z xy ⎨ ⎩> 0 Z yy
Nilai determinan di sebelah kanan disebut dengan Bordered Hessian, dengan notasi H .
Kasus n-Variabel OF : U = f ( x1 , x2 ,..., xn ) s.t : g ( x1 , x2 ,..., xn ) = c
Fungsi Lagrange : Z = f ( x1 , x2 ,..., xn ) + λ ⎡⎣c − g ( x1 , x2 ,..., xn ) ⎤⎦ "
0
g1
g2
gn
g1
Z11
Z12 " Z1n
Bordered Hessian : H = g 2 Z 21 " " g n Z n1
Z 22 " Z 2 n " " " Z n 2 " Z nn
dimana minor Bordered Hessian : 0
g1
g2
H 2 = g1 g2
Z11 Z 21
Z12 Z 22
H3 =
0
g1
g2
g3
g1 g2
Z11 Z 21
Z12 Z 22
Z13 Z 23
g3
Z 31
Z 32
Z 33
(dst)
Maka, ⎧ positive definite ⎫ d Z⎨ ⎬ subject to dg = 0 ⎩negative definite ⎭ 2
iff
⎧ H 2 , H 3 ,..., H n < 0 ⎪ ⎨ ⎪⎩ H 2 > 0; H 3 < 0; H 4 > 0; dst
Berikut tabel uji determinan untuk masalah optimisasi kasus n-variabel : Kondisi
Maksimum
Minimum
FONC
Z λ = Z1 = Z 2 = ... = Z n = 0
Z λ = Z1 = Z 2 = ... = Z n = 0
SOSC
H 2 > 0; H 3 < 0; H 4 > 0;...; ( −1) H n > 0 n
Contoh :
OF : Max U ( x, y ) = 10 x 3 y 1
2
3
s.t : 4 x + 6 y = 72 Tentukan nilai x dan y serta perlihatkan SOSC ! Jawab : 1
Fungsi Lagrange : Z = 10 x 3 y
2
3
+ λ ⎡⎣72 − ( 4 x + 6 y ) ⎤⎦
FONC : Zx = 0 →
10 − 2 3 2 3 x y − 4λ = 0 3
…(i)
Zy = 0 →
20 13 − 13 x y − 6λ = 0 3
…(ii)
Z λ = 0 → 72 − 4 x − 6 y = 0
…(iii)
H 2 , H 3 ,..., H n < 0
Persamaan (i) dibagi dengan persamaan (ii) : 10 − 2 3 2 3 x y 4λ y 2 4x 3 = → = →y= 1 1 20 3 − 3 6λ 2x 3 3 x y 3
(iv)
Substitusi persamaan (iv) ke (iii) : ⎛ 4x ⎞ 72 − 4 x − 6 ⎜ ⎟ = 0 → 12 x = 72 → x* = 6 ⎝ 3 ⎠ Substitusi nilai x* = 6 ke persamaan (iv) :
y* =
4 ( 6) =8 3
Jadi diperoleh solusi : x* = 6 dan y* = 8 SOSC :
Z xx = −
2 20 − 5 3 2 3 20 − 5 x y = − ( 6 ) 3 ( 8 ) 3 = −0, 4487 9 9
Z xy = Z yx = Z yy = −
20 − 2 3 − 13 20 − 2 3 − 13 x y = ( 6 ) ( 8 ) = 0,3365 9 9
1 20 13 − 4 3 20 −4 x y = − ( 6 ) 3 ( 8 ) 3 = −0, 2524 9 9
0 4 Maka H 2 = 4 Z xx 6 Z yx
6 Z xy = −16Z yy + 48Z xy − 36 Z xx = 36,3436 > 0
Z yy
Karena H 2 > 0 , maka solusi x* = 6 dan y* = 8 memaksimumkan utilitas dengan kendala 4 x + 6 y = 72
Soal :
Misalkan seseorang mempunyai fungsi kepuasan sbb : U = ( x + 2 )( y + 1) , dengan dihadapkan pada kendala anggaran xPx + yPy = B a) Perlihatkan bahwa x * , y * , dan λ * merupakan fungsi dari Px , Py , dan B b) Tentukan tanda dari
∂x * ∂y * ∂y * , , dan ∂Px ∂Px ∂B
