Catatan Kuliah 13 Memahami dan Menganalisa Optimasi dengan Kendala Ketidaksamaan
1. Interpretasi Kondisi Kuhn Tucker Asumsikan masalah yang dihadapi adalah masalah produksi. Secara umum, persoalan maksimisasi keuntungan atau minimisasi biaya dalam masalah produksi untuk n variabel dan m kendala ditulis dalam bentuk : i. Max : π = f ( x1 , x2 ,..., xn ) s.t : g i ( x1 , x2 ,..., xn ) ≤ ri
ii. Min : C = f ( x1 , x2 ,..., xn ) s.t : g i ( x1 , x2 ,..., xn ) ≥ ri m
Dengan fungsi Lagrange : Z = f ( x1 , x2 ,..., xn ) + ∑ λi ⎡⎣ ri − g i ( x1 , x2 ,..., xn ) ⎤⎦ i =1
dimana i = 1, 2,..., m ; j = 1, 2,..., n Kondisi Kuhn Tucker (KKT) untuk masalah maksimisasi adalah :
∂Z ≤0 ∂x j
; xj ≥ 0
; xj
∂Z =0 ∂x j
∂Z ≥0 ∂λi
; λi ≥ 0
; λi
∂Z =0 ∂λi
Sedangkan Kondisi Kuhn Tucker (KKT) untuk masalah minimisasi adalah :
∂Z ≥0 ∂x j
; xj ≥ 0
; xj
∂Z =0 ∂x j
∂Z ≤0 ∂λi
; λi ≥ 0
; λi
∂Z =0 ∂λi
Definisikan : f j ≡ marginal gross profit of j-th product
λi ≡ shadow price of i-th resource (the opportunity cost of using a unit of the ith resource)
g ij ≡ amount of i-th resource used up in producing the marginal unit of j-th
product
λi g ij ≡ marginal imputed cost of i-th resource incurred in producing a unit of j-th product
∑λ g i
i j
≡ aggregate marginal imputed cost of j-th product
i
Karenanya kondisi marginal :
∂Z = f j − ∑ λi g ij ≤ 0 ∂x j i
Artinya, marginal gross profit of
j-th product kurang dari atau sama dengan
aggregate marginal imputed cost.
2. Kualifikasi Kendala
Kondisi Kuhn Tucker adalah kondisi perlu, hanya jika syarat khusus terpenuhi. Syaratnya adalah kualifikasi kendala yang menentukan restriksi tertentu pada fungsi kendala dari masalah non-linier programming. Irregularities at Boundary Points Contoh 1
Max π = x1 s.t : x2 − (1 − x1 ) ≤ 0 3
x1 , x2 ≥ 0 x2
1
x2 x=2 (=1 − (1x−1 )x1 ) 3
0
3
1
x1
Seperti yang ditunjukkan grafik di atas, daerah feasible (kemungkinan hasil) adalah himpunan titik-titik yang berada pada kuadran 1 dibawah kurva x2 = (1 − x1 ) . Karena fungsi tujuannya adalah memaksimumkan nilai x1 , maka 3
solusi optimal adalah titik (1, 0 ) . Tetapi solusi ini tidak memenuhi kondisi maksimum Kuhn Tucker. Untuk memeriksa hal ini, pertama buat fungsi Lagrange untuk masalah optimisasi di atas. 3 F. Lagrange : Z = x1 + λ1 ⎡ − x2 + (1 − x1 ) ⎤ ⎣ ⎦
KKT :
∂Z 2 = 1 − 3λ1 (1 − x1 ) ≤ 0 ∂x1
;
x1 ≥ 0
;
∂Z x1 = 0 ∂x1
Jika solusi (1, 0 ) kita masukkan ke dalam kondisi di atas maka solusi (1, 0 ) tidak memenuhi kondisi Kuhn Tucker di atas.
Contoh 2
Berdasarkan masalah pada contoh 1 di atas, misalkan ditambahkan fungsi kendala 2 x1 + x2 ≤ 2 x2 2
1
0
x2 = 2 − 2 x1
x2 = (1 − x1 )
3
1
x1
Daerah feasible (kemungkinan hasil) masih sama seperti sebelumnya, begitu juga dengan solusi optimalnya. Tetapi jika dibuat fungsi Lagrange : 3 Z = x1 + λ1 ⎡ − x2 + (1 − x1 ) ⎤ + λ2 [ 2 − 2 x1 − x2 ] ⎣ ⎦
KKT : ∂Z 2 = 1 − 3λ1 (1 − x1 ) − 2λ2 ≤ 0 ∂x1
;
x1 ≥ 0
;
∂Z x1 = 0 ∂x1
∂Z = −λ1 − λ2 ≤ 0 ∂x2
;
x2 ≥ 0
;
∂Z x2 = 0 ∂x2
∂Z 3 = − x2 + (1 − x1 ) ≥ 0 ∂λ1
;
λ1 ≥ 0
;
∂Z λ1 = 0 ∂λ1
∂Z = 2 − 2 x1 − x2 ≥ 0 ∂λ2
;
λ2 ≥ 0
;
∂Z λ2 = 0 ∂λ2
Karena x1* = 1 maka : ∂Z 2 = 1 − 3λ1 (1 − x1 ) − 2λ2 = 0 ∂x1 x1 = 1 → 1 − 3λ1 (1 − 1) − 2λ2 = 0 2
1 = 2λ2 → λ2 * =
1 2
Karena x2 * = 0 maka : ∂Z = −λ1 − λ2 < 0 ∂x2
λ2 * =
1 1 → −λ1 − < 0 2 2
λ1* > − Jadi solusi
1 2
x1* = 1 ; x2 * = 0 ; λ1* > −
1 1 ; λ2 * = memenuhi kondisi Kuhn 2 2
1 Tucker, tetapi solusi ini tidak unique karena nilai λ1* > − . 2
Contoh 3
Max π = x2 − x12 s.t : x2 − (10 − x12 − x2 ) ≤ 0 3
− x1 ≤ −2 x1 , x2 ≥ 0 x2 10
x1 = 2
( 2, 6 )
6
− (10 − x12 − x2 ) = 0 3
0
2 3
x1
Berdasarkan grafik di atas, solusi yang optimal adalah titik ( 2, 6 ) , tetapi solusi tersebut tidak memenuhi kondisi Kuhn Tucker. Untuk memeriksa hal ini, buat fungsi Lagrange untuk masalah optimisasi di atas. 3 Z = x2 − x12 + λ1 ⎡⎢(10 − x12 − x2 ) ⎤⎥ + λ2 [ −2 + x1 ] ⎣ ⎦
KKT :
2 ∂Z = 1 − 3λ1 (10 − x12 − x2 ) ≤ 0 ∂x2
Karena x2 * = 6 maka
;
x2 ≥ 0
;
∂Z x2 = 0 ∂x2
2 ∂Z = 1 − 3λ1 (10 − x12 − x2 ) = 0 ∂x2
Substitusi x1* = 2 dan x2 * = 6 ke persamaan di atas,
(
∂Z 2 = 1 − 3λ1 10 − ( 2 ) − ( 6 ) ∂x2
)
2
=1≠ 0
Ternyata solusi x1* = 2 dan x2 * = 6 terbukti tidak memenuhi kondisi Kuhn Tucker.
Kualifikasi Kendala
Misalkan x* ≡ ( x1*, x2 *,..., xn *) adalah titik-titik dalam daerah feasible dan kandidat solusi, dan dx ≡ ( dx1 , dx2 ,..., dxn ) adalah arah perubahan atau pergerakan dari titik x * (vektor). Dua syarat vektor dx sbb : 1) dx j ≥ 0 jika x j * = 0 ⎪⎧≤ 0 ( max ) ⎪⎫ i 2) dg i ( x *) = g1i dx1 + g 2i dx2 + ... + g n i dxn ⎨ ⎬ jika g ( x *) = ri 0 min ≥ ( ) ⎩⎪ ⎭⎪ dimana j = 1, 2,..., n variabel dan i = 1, 2,..., m constraint Test vektor adalah jika suatu vektor dx memenuhi kedua syarat diatas. Kualifikasi kendala terpenuhi jika untuk suatu titik x * pada batas daerah feasible, terdapat busur (arc) yang memenuhi syarat untuk setiap test vektor dx .
Contoh :
1) Tunjukkan contoh 1 sebelumnya bahwa nilai optimal x1* = 1 dan x2 * = 0 tidak memenuhi kualifikasi kendala. Jawab : Karena x2 * = 0 maka dx2 ≥ 0 Jika g 1 ( x *) = x2 − (1 − x1 ) = 0 = r1 maka 3
dg 1 ( x *) = g11dx1 + g 21dx2 = 3 (1 − x1 ) dx1 + 1dx2 ≤ 0 ( max ) 2
Karena x1* = 1 maka dg 1 ( x *) = 3 (1 − 1) dx1 + 1dx2 = dx2 ≤ 0 2
Karena dx2 ≥ 0 dan dx2 ≤ 0 , dapat dimisalkan dx2 = 0 dan dx1 bebas. Misal ambil vektor sembarang ( dx1 , dx2 ) = ( 2, 0 ) dan ( dx1 , dx2 ) = ( −1, 0 ) Vektor ( −1, 0 ) jika digambarkan dari titik (1, 0 ) arahnya ke barat sehingga dari vektor tersebut dapat dibuat busur. Sedangkan vektor ( 2, 0 ) jika digambarkan dari titik (1, 0 ) arahnya ke timur sehingga dari vektor tersebut tidak dapat dibuat busur.
Oleh karena itu dapat disimpulkan bahwa nilai optimal x1* = 1 dan x2 * = 0 tidak memenuhi kualifikasi kendala. 2) Max π = x1 s.t : x12 + x2 2 ≤ 1 x1 , x2 ≥ 0 a) Gambarkan masalah optimisasi di atas dan tentukan solusinya berdasarkan grafik. b) Periksa apakah solusi tersebut memenuhi kualifikasi kendala. c) Jika iya, periksa apakah solusi tersebut memenuhi kondisi Kuhn Tucker.
