Catatan Kuliah 12 Memahami dan Menganalisa Optimisasi dengan Kendala Ketidaksamaan
1. Non Linear Programming Misalkan dihadapkan pada ilustrasi berikut ini : (i) Max : U = U ( x1 , x2 ,..., xn ) s.t : ∑ pi xi ≤ B
xi ≥ 0 ; i = 1, 2,..., n (ii) Min : C = pK K + pL L
s.t : K α Lβ ≥ Q0 Q0 , K , L ≥ 0 ; Q0 ≠ 0 Secara umum, persoalan maksimisasi keuntungan atau minimisasi biaya untuk n variabel dan m kendala ditulis dalam bentuk : (i) Max : π = f ( x1 , x2 ,..., xn ) s.t : g i ( x1 , x2 ,..., xn ) ≤ ri
dimana i = 1, 2,..., m (ii) Min : C = f ( x1 , x2 ,..., xn ) s.t : g i ( x1 , x2 ,..., xn ) ≥ ri
dimana i = 1, 2,..., m Apabila dalam kedua persoalan di atas fungsi kendala dan tujuan semua berbentuk linear, maka dikenal dengan Linear Programming (LP). Sedangkan bila ada fungsi kendala atau tujuan yang tidak linear, mka disebut Non Linear Programming (NLP)
Contoh 1 :
Min : C = ( x1 − 4 ) + ( x2 − 4 ) 2
2
s.t : 2 x1 + 3x2 ≥ 6 −3x1 − 2 x2 ≥ −12 x1 , x2 ≥ 0 Solusi bagi persoalan di atas akan didekati dengan pendekatan grafik sbb : Perhatikan bahwa fungsi tujuan berbentuk lingkaran yang berpusat di titik
( 4, 4 )
dengan jari-jari r = C
x2 6
−3x1 − 2 x2 ≥ −12
4 2 x1 + 3x2 ≥ 6
2 0 Berdasarkan
3 4 grafik
x1 di
atas,
solusi
terletak
antara
−3x1 − 2 x2 = −12 dengan lingkaran yang berpusat di titik
persinggungan
( 4, 4 ) .
garis
Solusinya dapat
dicari melalui konsep jarak terdekat antara titik dan garis. Perhatikan lingkaran pada grafik tersebut dimana dapat dinyatakan sebagai fungsi implisit yaitu : F ( x1 , x2 ) = 0 → ( x1 − 4 ) + ( x2 − 4 ) − C = 0 2
Maka slope lingkaran :
2
2 ( x1 − 4 ) ( x − 4) dx2 F =− 1 =− =− 1 2 ( x2 − 4 ) dx1 F2 ( x2 − 4 )
Slope garis −3 x1 − 2 x2 = −12 :
dx2 F − ( −3) 3 =− 1 = =− dx1 F2 2 ( −2 )
Pada persinggungan, slope lingkaran = slope garis : −
( x1 − 4 ) = − 3 ( x2 − 4 ) 2
2 ( x1 − 4 ) = 3 ( x2 − 4 )
2 x1 − 8 = 3x2 − 12 2 x1 − 3 x2 = −4
…(*)
Solusi dapat diperoleh dari eliminasi persamaan (*) dan −3 x1 − 2 x2 = −12 −3 x1 − 2 x2 = −12 → kali 3 2 x1 − 3 x2 = −4 → kali 2 −13 x1 = −28
x1* =
−
28 36 → x2 * = 13 13
Catatan :
Pengamatan pada daerah kendala dan fungsi tujuan : Daerah kendala merupakan himpunan convex Solusi yang diperoleh adalah solusi global Fungsi tujuan adalah fungsi convex
Contoh 2 :
Min : C = ( x1 − 4 ) + ( x2 − 4 ) 2
s.t : x1 + x2 ≥ 5 − x1 ≥ −6 −2 x2 ≥ −11 x1 , x2 ≥ 0
2
x1 = 6
x2
x2 = 5,5
5,5 5
(4,4) •
x1 + x2 = 5 0
5 6
x1
Solusinya adalah lingkaran yang berpusat di titik ( 4, 4 ) dengan jari-jari r = 0
Contoh 3 :
Max : π = 2 x1 + x2
s.t : − x12 + 4 x1 − x2 ≤ 0 2 x1 + 3 x2 ≤ 12 x1 , x2 ≥ 0 x2 4
− x12 + 4 x1 − x2 = 0
P1
F1
P2
0
2
4 F2 6
2 x1 + 3 x2 = 12 P3 x1
Pengamatan : (i) F1 ∪ F2 bukan himpunan convex (ii) P1 adalah titik optimal di F1 (iii) Setiap titik di F2 nilainya lebih optimal dari P1 (iv) P3 adalah maksimum global
Kesimpulan : ♦
Apabila set atau himpunan kendala tidak convex maka solusinya belum tentu global dan bisa tidak unique.
♦ Apabila set atau himpunan kendala convex maka solusinya pasti global.
2. Kondisi Kuhn Tucker Konsep Kendala Non Negatif Max : π = f ( x1 )
s.t : x1 ≥ 0 Berdasarkan optimisasi di atas, kemungkinan solusinya adalah :
π
π A : solusi interior
π B : corner solution C D
x1 *
0
x1
x1 *
x1
x1 *
C,D : bukan titik stasioner
x1
Berdasarkan pengamatan ketiga gambar di atas dapat diperoleh bahwa x1 * merupakan maksimum lokal dari π bila memenuhi salah satu dari ketiga syarat berikut : (i)
f ' ( x1 ) = 0 dan x1* > 0 (titik A)
(ii)
f ' ( x1 ) = 0 dan x1* = 0 (titik B)
(iii)
f ' ( x1 ) < 0 dan x1* = 0 (titik C,D)
Secara matematis, tiga syarat di atas dapat dirangkum menjadi first order necessary condition (FONC) maksimum lokal dengan kendala non negatif sbb : f ' ( x1 *) ≤ 0 ; x1* ≥ 0 ; x1 * f ' ( x1 *) = 0
Jadi ketika masalah optimisasi dengan n variabel : Max : π = f ( x1 , x2 ,..., xn )
s.t : x j ≥ 0 dimana j = 1, 2,..., n Maka FONC : f j ≤ 0 ; x j ≥ 0 ; x j f j = 0
( j = 1, 2,..., n )
Secara khusus apabila kita bandingkan pada fungsi objektif dengan 3 variabel dan 2 kendala, maka permasalahan tersebut dapat ditulis sbb : Max : π = f ( x1 , x2 , x3 ) s.t : g 1 ( x1 , x2 , x3 ) ≤ r1 g 2 ( x1 , x2 , x3 ) ≤ r2
x1 , x2 , x3 ≥ 0 atau dengan variabel dummy ( s1 , s2 ) dapat dinyatakan dengan : Max : π = f ( x1 , x2 , x3 ) s.t : g 1 ( x1 , x2 , x3 ) + s1 = r1 g 2 ( x1 , x2 , x3 ) + s2 = r2
x1 , x2 , x3 , s1 , s2 ≥ 0 Apabila kendala non-negatif diabaikan, maka fungsi Lagrangenya dapat dinyatakan sbb : Fungsi Lagrange : Z ' = f ( x1 , x2 , x3 ) + λ1 ⎡⎣ r1 − g 1 ( x1 , x2 , x3 ) − s1 ⎤⎦ + λ2 ⎡⎣ r2 − g 2 ( x1 , x2 , x3 ) − s2 ⎤⎦ FONC : ∂Z ' ∂Z ' ∂Z ' ∂Z ' ∂Z ' ∂Z ' ∂Z ' = = = = = = =0 ∂x1 ∂x2 ∂x3 ∂s1 ∂s2 ∂λ1 ∂λ2
Karena ada syarat x j ≥ 0 dan si ≥ 0 , maka FONC menjadi : (i)
∂Z ' ≤0 ∂x j
; xj ≥ 0
; xj
∂Z ' =0 ∂x j
(ii)
∂Z ' ≤0 ∂si
; si ≥ 0
; si
∂Z ' =0 ∂si
(iii)
∂Z ' =0 ∂λi
⎛ i = 1, 2 ⎞ ⎜ ⎟ ⎝ j = 1, 2,3 ⎠
Selanjutnya dari syarat FONC tersebut, ingin dieliminasi variabel pembantu yaitu si . Dari FONC (ii) :
∂Z ' ≤ 0 maka −λi ≤ 0 atau λi ≥ 0 ∂si si
∂Z ' = 0 maka − si λi = 0 atau si λi = 0 ∂si
Sehingga FONC (ii) dapat dinyatakan dengan : λi ≥ 0 ; si ≥ 0 ; si λi = 0 Sedangkan dari FONC (iii) :
∂Z ' = 0 maka ri − g i ( x1 , x2 , x3 ) − si = 0 ∂λi atau si = ri − g i ( x1 , x2 , x3 )
Karena si ≥ 0 maka si = ri − g i ( x1 , x2 , x3 ) ≥ 0 Sehingga kombinasi dari FONC (ii) dan (iii) adalah: ri − g i ( x1 , x2 , x3 ) ≥ 0 ;
λi ≥ 0 ;
λi ⎣⎡ ri − g i ( x1 , x2 , x3 ) ⎦⎤ = 0
Dengan demikian dapat disimpulkan bahwa FONC dari 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 FONC dari 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
Contoh :
Min : C = ( x1 − 4 ) + ( x2 − 4 ) 2
2
s.t : 2 x1 + 3x2 ≥ 6 −3x1 − 2 x2 ≥ −12 x1 , x2 ≥ 0 Jawab : Fungsi Lagrange : 2 2 Z ' = ⎡( x1 − 4 ) + ( x2 − 4 ) ⎤ + λ1 ⎡⎣6 − ( 2 x1 + 3 x2 ) ⎤⎦ + λ2 ⎡⎣ −12 − ( −3 x1 − 2 x2 ) ⎤⎦ ⎣ ⎦
FONC : ∂Z ' = 2 ( x1 − 4 ) − 2λ1 + 3λ2 ≥ 0 ∂x1
;
x1 ≥ 0
;
x1
∂Z ' =0 ∂x1
∂Z ' = 2 ( x2 − 4 ) − 3λ1 + 2λ2 ≥ 0 ∂x2
;
x2 ≥ 0 ;
x2
∂Z ' =0 ∂x2
∂Z ' = 6 − 2 x1 − 3 x2 ≤ 0 ∂λ1
;
λ1 ≥ 0 ;
λ1
∂Z ' =0 ∂λ1
∂Z ' = −12 + 3x1 + 2 x2 ≤ 0 ∂λ2
;
λ2 ≥ 0 ;
λ2
∂Z ' =0 ∂λ2
Mencari solusi dengan coba-coba, karena ada 2 variabel dan 2 kendala maka jumlah kombinasi penyelesaian yang mungkin adalah : 22+ 2 = 24 = 16 kemungkinan. x1 = 0; x2 = 0 ⎧λ1 = 0; λ2 x1 = 0; x2 > 0 ⎪⎪λ1 = 0; λ2 ⎨ x1 > 0; x2 = 0 ⎪λ1 > 0; λ2 x1 > 0; x2 > 0 ⎪⎩λ1 > 0; λ2
=0 >0 =0 >0
Perhatikan grafik di bawah ini ! x2 6
−3x1 − 2 x2 = −12
4 2 x1 + 3x2 = 6
2
0
3 4
x1
Berdasarkan solusi grafik di atas diketahui bahwa x1 > 0 dan x2 > 0 , sehingga hanya ada 4 solusi yang mungkin yaitu : ⎧λ1 = 0; λ2 ⎪λ = 0; λ ⎪ 1 2 x1 > 0; x2 > 0 ⎨ ⎪λ1 > 0; λ2 ⎪⎩λ1 > 0; λ2
=0 >0 =0 >0
¾ Misalkan solusi yang mungkin adalah : x1 > 0; x2 > 0; λ1 = 0; λ2 = 0
Karena x1 > 0 dan x1
∂Z ' ∂Z ' = 0 , maka = 2 ( x1 − 4 ) − 2λ1 + 3λ2 = 0 ∂x1 ∂x1
…(1)
Karena x2 > 0 dan x2
∂Z ' ∂Z ' = 0 , maka = 2 ( x2 − 4 ) − 3λ1 + 2λ2 = 0 ∂x2 ∂x2
…(2)
Karena λ1 = 0; λ2 = 0 , maka dari persamaan (1) dan (2) diperoleh solusi : x1* = 4 dan x2 * = 4 Maka solusinya menjadi : x1* = 4; x2 * = 4; λ1* = 0; λ2 * = 0 Selanjutnya akan diperiksa apakah solusi ini memenuhi KKT atau tidak. Karena λ1 = 0 dan λ1
∂Z ' ∂Z ' = 0 , maka = 6 − 2 x1 − 3x2 < 0 ∂λ1 ∂λ1
Substitusi x1* = 4 dan x2 * = 4 ke persamaan (3), terbukti Karena λ2 = 0 dan λ2
…(3)
∂Z ' <0 ∂λ1
∂Z ' ∂Z ' = 0 , maka = −12 + 3x1 + 2 x2 < 0 ∂λ2 ∂λ2
…(4)
Substitusi x1* = 4 dan x2 * = 4 ke persamaan (4), ternyata
∂Z ' >0 ∂λ1
Jadi, solusi x1* = 4; x2 * = 4; λ1* = 0; λ2 * = 0 bukan solusi optimal yang memenuhi KKT. ¾ Misalkan solusi yang mungkin adalah : x1 > 0; x2 > 0; λ1 = 0; λ2 > 0
Karena x1 > 0 dan x1
∂Z ' ∂Z ' = 0 , maka = 2 ( x1 − 4 ) − 2λ1 + 3λ2 = 0 ∂x1 ∂x1
…(1)
Karena x2 > 0 dan x2
∂Z ' ∂Z ' = 0 , maka = 2 ( x2 − 4 ) − 3λ1 + 2λ2 = 0 ∂x2 ∂x2
…(2)
Karena λ1 = 0 , maka persamaan (1) dan (2) menjadi : 2 ( x1 − 4 ) + 3λ2 = 0
…(3)
2 ( x2 − 4 ) + 2λ2 = 0
…(4)
Eliminasi persamaan (3) dan (4) menghasilkan : 4 x1 − 6 x2 + 8 = 0
…(5)
Karena λ2 > 0 dan λ2
∂Z ' ∂Z ' = 0 , maka = −12 + 3x1 + 2 x2 = 0 ∂λ2 ∂λ2
…(6)
Kemudian eliminasi persamaan (5) dan (6) menghasilkan : 13 x1 − 28 = 0 x1* =
28 13
Substitusi nilai x1* =
28 36 ke persamaan (5) sehingga diperoleh nilai x2 * = 13 13
Substitusi nilai x1* =
28 16 ke persamaan (3) sehingga diperoleh nilai λ2 * = 13 13
Maka solusinya menjadi : x1* =
28 36 16 ; x2 * = ; λ1* = 0; λ2 * = 13 13 13
Selanjutnya akan diperiksa apakah solusi ini memenuhi KKT atau tidak. Substitusi x1* =
28 16 ∂Z ' ke persamaan (2), terbukti , λ1* = 0 dan λ2 * = =0 13 13 ∂x1
Substitusi x2 * =
36 16 ∂Z ' ke persamaan (1), terbukti , λ1* = 0 dan λ2 * = =0 13 13 ∂x2
Karena λ1 = 0 dan λ1
∂Z ' ∂Z ' = 0 , maka = 6 − 2 x1 − 3x2 < 0 ∂λ1 ∂λ1
Substitusi x1* =
28 36 ∂Z ' <0 dan x2 * = ke persamaan (7), terbukti ∂λ1 13 13
Substitusi x1* =
28 36 ∂Z ' =0 dan x2 * = ke persamaan (6), terbukti ∂λ2 13 13
Jadi, solusi x1* =
…(7)
28 36 16 merupakan solusi optimal yang ; x2 * = ; λ1* = 0; λ2 * = 13 13 13
memenuhi KKT.
Soal :
Diketahui : R ( Q ) = 32Q − Q 2 C ( Q ) = Q 2 + 8Q + 4
π 0 = 18 Tentukan solusi dari optimisasi berikut yang memenuhi kondisi Kuhn Tucker : Max : R ( Q )
s.t : C − R ≤ −π 0
