BAB 2 LANDASAN TEORI

BAB 2

LANDASAN TEORI

Pada bab ini akan dibahas beberapa pengertian dari optimasi bersyarat dengan kendala persamaan menggunakan multiplier lagrange serta penerapannya yang akan digunakan sebagai landasan berfikir dalam melakukan penelitian ini, yang akan dipergunakan pada bab pembahasan.

2.1 Optimasi

Suatu permasalahan optimasi disebut nonlinear jika fungsi tujuan dan kendalanya mempunyai bentuk nonlinear pada salah satu atau keduanya. Optimasi merupakan masalah yang berhubungan dengan keputusan yang terbaik, maksimum, minimum dan memberikan cara penentuan solusi yang memuaskan. Salah satu bentuk umum masalah optimasi adalah untuk menentukan bersyarat x = (x1, x2, … , xn)

sehingga

mencapai tujuannya untuk memaksimumkan/ meminimumkan f(x) dengan kendala gn (x) ≥ 0 dan untuk x ≥ 0 . dengan f(x) dan gn(x) adalah fungsi yang diketahui dengan n variabel keputusan.

Dalam masalah optimasi terdapat dua bentuk masalah optimasi yaitu optimasi bersyarat dan optimasi tak bersyarat.

2.1.1 Optimasi Tak Bersyarat

Optimasi tak bersyarat merupakan masalah optimasi yang tidak memiliki syarat atau tidak memiliki batasan- batasan , sehingga untuk x = (x1, x2, … , xn) mempunyai fungsi tujuan adalah memaksimumkan/ meminimumkan f(x) .

Universitas Sumatera Utara

10

Syarat perlu dan syarat cukup untuk suatu penyelesaian x = x* merupakan penyelesian optimal saat f(x) merupakan fungsi yang dapat diturunkan adalah pada x = x* , untuk j = 1,2, … , n. Dimana f(x) dengan kondisi ini juga mencukupi, sehingga mencari solusi untuk x* tereduksi menjadi penyelesaian dari sistem n persamaan yang diperoleh dengan n turunan parsial sama dengan nol.

2.1.2 Optimasi Bersyarat

Optimasi bersyarat adalah masalah optimasi yang memiliki syarat atau memiliki batasan - batasan yang merupakan masalah pemodelan matematika dalam optimasi fungsi yang mensyaratkan beberapa kondisi atau syarat untuk diperoleh

solusi

optimal yaitu syarat yang mengoptimumkan fungsi tujuan. Maksimumkan / Minimumkan z = f(x), x = {x1, x2, …, xn} Dengan kendala g1(x) (≤, =, ≥) = b1 g2(x) (≤, =, ≥) = b2 … gm(x) (≤, =, ≥) = bm Disini jika terjadi bahwa m > n maka tidak dapat diselesaikan. Akan tetapi untuk dapat menyelesaikannya maka m ≤ n (jumlah kendala lebih kecil daripada variabel).

Metode yang dapat digunakan untuk menyelesaikan masalah optimasi adalah metode pengali Lagrange, karena metode Lagrange tersebut prinsip kerjanya sederhana dan mudah dimengerti. Metode ini dimulai dengan pembentukan fungsi Lagrange yang didefinisikan sebagai : L(x, λ) = f(x) +

m

λigi (x)

i1

Universitas Sumatera Utara

11 Teorema : Syarat perlu bagi sebuah fungsi f(x) dengan kendala gj (x) = 0, untuk j = 1, 2, … , m agar mempunyai minimum relatif pada titik x* adalah derivasi parsial pertama dari fungsi Lagrangenya yang didefinisikan sebagai L(x, λ) = ( x1,x2,…,xn,

,

1

2

,...,

m

)

terhadap setiap argumennya mempunyai nilai nol. (Luknanto, 2000: 12)

Teorema: Syarat harus bagi sebuah fungsi f(x) agar mempunyai minimum(atau maximum) relatif pada titik x* adalah jika fungsi kuadrat Q, yang didefinisikan sebagai n

n

Q i 1 j 1

2

L dxi dx j xi x j

Dievaluasi pada x = x* harus definit positif (atau negatif) untuk semua nilai dx yang memenuhi semua kendala. (Luknanto, 2000: 13)

n

2

n

Syarat perlu agar Q i 1 j 1

L dxi dx j xi x j

menjadi definit positif( atau

negatif) untuk setiap variasi nilai dx adalah setiap akar dari polynomial zi, yang didapat dari determinan persamaan dibawah ini harus positif (atau negatif).

(L11- z)

L12

L13

…

L1n

g11

L21

(L22-z)

L23

…

L2n

g12

g12

… gm1

g22 …

…

g2n

…

Ln1

Ln2

Ln3

…

(Lnn-z)

gm1

gm2 …

g11

g12

g13

…

g1n

0

0

… 0

g21

g22

g23

…

g2n

0

0

… 0

… gm1

Dengan L11 =

gm2

gm3

…

gmn

=0

… gmn

0

0

… 0

dan gij = (Luknanto, 2000 : 13)

Universitas Sumatera Utara

12

Arti dari pengali Lagrange secara fisik yang menarik dimisalkan terdapat permasalahan optimasi

dengan satu kendala sebagai berikut: maksimumkan/

minimumkan f(x) dengan kendala g(x) = b Fungsi Lagrangenya adalah L (x, λ) = f (x) + λ(b-g (x)) Syarat perlu untuk penyelesaian diatas adalah

=0 Maka persamaan diatas menghasilkan :

b – g(x) = 0 atau b = g(x) didapat;

Atau

Atau

Atau

df

dg

Universitas Sumatera Utara

13

menghasilkan yang final yaitu df =λdb

karena b = g(x)

atau df = λ*db

Dapat diambil suatu kesimpulan bahwa dari persamaan diatas pada penyelesaian optimum, perubahan fungsi tujuan f, berbanding lurus dengan perubahan Kendala b dengan faktor sebesar pengali Lagrange λ.

2.2 Metode Pengali Lagrange

Sejauh ini proses optimasi dilakukan tanpa menggunakan kendala, padahal seringkali persoalan optimasi dihadapkan pada kendala - kendala tertentu. Sebagai contoh persoalan dasar dalam teori konsumen adalah bagaimana menentukan tingkat konsumsi yang memberikan kepuasan optimal dengan tingkat pendapatan tertentu.

Multiplier Langrange adalah sebuah konsep populer dalam menangani permasalahan ini untuk program-program non-linear. Sesuai namanya, konsep ini dikemukakan oleh Joseph Louis Langrange (1736-1813). Teori ini dapat digunakan untuk menangani optimalitas dari permasalahan program non-linear.

Metode pengali Lagrange merupakan sebuah tehnik dalam menyelesaikan masalah optimasi dengan kendala persamaan. Inti dari metode pengali Lagrange adalah mengubah persoalan titik ekstrem terkendala menjadi persoalan ekstrem bebas kendala. Fungsi yang terbentuk dari tranformasi tersebut dinamakan fungsi Lagrange. misalkan permasalahan yang dihadapi adalah Maksimumkan (Minimumkan) z = f(x),

x = {x1, x2, …, xn}

Dengan kendala g1(x) (≤, =, ≥) = b1 g2(x(≤, =, ≥)) = b2 … gm(x) (≤, =, ≥) = bm

Universitas Sumatera Utara

14

Fungsi baru Lagrange yang telah dimodifikasi menjadi L(x, λ) = f(x) +

m

λigi (x)

i1

2.3 Matrik Hessian Matrik adalah susunan bilangan yang diatur berdasarkan baris dan kolom. Bilangan – bilangan tersebut dinamakan entri dalam matrik atau disebut juga elemen (unsur).

Matrik Hessian adalah matrik yang setiap elemennya dibentuk dari turunan parsial kedua dari suatu fungsi. Misalkan f(x) fungsi dengan n variabel yang memiliki turunan parsial kedua dan turunannya kontinu, matrik Hessian f(x) ditulis H adalah :

… …

H=

…

…

… …

Matrik Hessian dapat digunakan untuk melakukan uji turunan kedua fungsi lebih dari satu variabel, yaitu untuk mengidentifikasi optimum relatif dari nilai fungsi tersebut. Penggolongan titik stasioner fungsi dua variabel dengan menggunakan matriks Hessian misalkan f(x) = F(x1, …, xn) adalah fungsi bernilai real dimana semua turunan parsialnya kontinu. Misalnya x0 adalah titik stasioner dari F dan didefinisikan H = H(x0) dengan persamaan Hij = Fxi, yj (x0). H (x0) adalah Hessian dari F pada x0.

Universitas Sumatera Utara

15

Titik stasioner dapat digolongkan sebagai berikut : 1. x0. Adalah suatu minimum relatif dari F jika jika H(x0.) definit positif 2. x0. Adalah suatu maksimum relatif dari F jika H(x0.) definit negatif 3. x0. Adalah suatu titik pelana dari F jika H(x0.) indefinite (Leon,1998 : 313)

Contoh : 1 Untuk mendapatkan titik ekstrim dari suatu fungsi dipakai sebuah contoh sebagai berikut : +

+

+

Solusi : Titik ekstrim harus memenuhi syarat : +4 +8 Persamaan diatas dipenuhi oleh titik – titik (0, 0), (0, -8/3), (-4/3, 0), dan (-4/3, -8/3) Untuk mengetahui titik maksimum dan minimum maka digunakannya matrik Hessian untuk menyelidikinya. Derivasi kedua dari f adalah : ,

,

dan

Jadi matrik Hessian menjadi

6x1 + 4 0

0 6x2 + 8

sehingga H1 = [6x1 + 4] dan

H2 =

6x1 + 4 0

0 6x2 + 8

Universitas Sumatera Utara

16

Tabel 2.1. Nilai matrik Hessian untuk masing – masing titik ekstrim.

( x1 ,x2)

Matrik H 4

0

0

8

4

0

H1

(0, 0)

+4

(0, -8/3)

+4

H2

Sifat H

Sifat ( x1 ,x2)

+32

Definit positif

Minimum

-32

Tak tentu

Titik belok

- 32

Tak tentu

Titik belok

Definit nefgatif

Maksimum

f(x1, x2)

6

418 / 27

0 -8

(-4/3, 0)

(-4/3, -8/3)

-4

0

0

8

-4

0

0

-8

-4

-4

+ 32

194/ 27

50/ 3

Grafik f(x) disajikan dalam ruang tiga dimensi diperlihatkan dalam gambar dibawah ini : Maksimum (-4/3, -8/3) -2 -1

0

Titik belok (0, -8/3)

15

12,5

10

7,5 (-) -1

X2

X1

0 Minimum (0,0)

Gambar. 2.1. Grafik dari

(-)

-0,5

+

+

+

Universitas Sumatera Utara

17

2.4 Matrik Definit Positif Bentuk kuadrat pada ( x1, x2, … xn ) adalah ekspresi yang dapat kita tulis sebagai

X1 X2

[ x1, x2, … xn ] A

Xn

Dengan A merupakan matrik simetrik n x n . Jadi misalkan X1 X2

X=

Xn

maka bentuk ini dapat ditulis sebagai X t AX

contoh : 2 Misalkan sebuah matrik simetrik berikut : 2 A=

-1 0

-1

0

2 -1 -1

2

Untuk mengkaji apakah matriks A bersifat definite positif, maka; 2 X t AX = [x1 x2 x3 ]

-1 0

0

X1

2 -1

X2

-1

-1

2

X3

Universitas Sumatera Utara

18

2x1 –x2 X t AX = [x1 x2 x3 ] -x1 + 2x2 –x3 -x2 + 2x3

Sehingga hasilnya adalah X t AX = x1(2x1-x2) + x2(-x1 + 2x2 – x3) + x3(-x2 +2x3) X t AX = 2

- x1x2 - x1x2 +

X t AX = 2

- 2x1x2 +

X t AX =

+(

X t AX =

+(

- x2x3 - x2x3 + - 2x2x3 +

2x1x2 +

)+(

)2 + (

-2x2x3 +

)+

)2 +

-

Dari sini dapat disimpulkan bahwa matrik A bersifat definit positif karena memenuhi: )2 + (

+(

-

)2 +

> 0 kecuali jika x1 = x2 = x3 = 0

Sebaliknya matrik A dan bentuk kuadrat X t AX disebut : 1. Definit negatif jika X t AX < 0, untuk semua x

0

2. Semidefinit positif jika X t AX ≥ 0, untuk semua x 3. Semidefinit negatif jika X t AX ≤ 0, untuk semua x 4. Indefinit bila tidak termasuk golongan diatas

Himpunan syarat perlu dan syarat cukup untuk bentuk – bentuk definit positif dan negatif yaitu : 1. Syarat perlu dan syarat cukup untuk bentuk definit positif Suatu himpunan syarat perlu dan syarat cukup bentuk X t AX sebagai definit positif adalah

h11 > 0,

h11

h12

h21

h22

> 0,

h11

h12

h13

h21

h22

h23 > 0, … ,

h31

h32

h33

A >0

Universitas Sumatera Utara

19

Jika n minor dari A adalah positif, maka X t AX adalah definit positif dan X t AX hanya definit positif, jika minor – minor ini positif.

2. Syarat perlu dan syarat cukup untuk bentuk definit negatif Suatu himpunan syarat perlu dan syarat cukup bentuk X t AX sebagai definit negatif atau setaranya untuk X t (-A)X sebagai definite positif adalah

h11 < 0,

h11

h12

h21

h22

> 0,

h11

h12

h13

h21

h22

n h23 < 0, … , (-1) A > 0

h31

h32

h33

Dimana aij adalah elemen – elemen dari A (bukan –A).

2.5 Maksimum dan Minimum

Suatu fungsi y = f(x) dikatakan mempunyai maksimum lokal (maksimum relatif) dimana x = a bila f(a) lebih besar dari sembarang nilai f(x) lainnya dari x sekitar a, dan dikatakan mempunyai minimum lokal (minimum relatif) pada x = a bila f(a) lebih kecil dari sembarang nilai f(x) lain untuk x sekitar a. Maksimum dan minimum local suatu fungsi adalah maksimum dan minimum absolut dari suatu fungsi mempunyai jarak yang lebih besar lagi dan terletak pada titik yang paling tinggi atau paling rendah dari jarak tersebut, melebihi maksimum atau minimum lokal. Jadi f(x) mempunyai nilai maksimum absolute pada nilai x = a1 dengan batas b

apabila nilai f(x)

pada x = a1 mempunyai nilai paling tinggi , f(a1) > f(x), sedangkan f(x) mempunyai nilai maksimum lokal pada batas b

, apabila f(x) pada

demikian suatu fungsi yang mempunyai titik maksimum

x =a2. Dengan

kurvanya berbentuk

cembung keatas dan fungsi yang mempunyai titik minimum kurvanya berbentuk cembung kebawah.

Universitas Sumatera Utara

20

Maksimum lokal

f(x)

Maksimum lokal

f(c)

Minimum lokal

Minimum lokal

f(b)

x=b

Gambar. 2.2. Grafik 1

Sebaliknya, titik kritis x dan f dapat dianalisa dengan menggunakan turunan kedua dari f di x : 1. Jika turunan kedua bernilai positif, x adalah minimum 2. Jika turunan kedua bernilai negatif, x adalah maksimum 3. Jika turunan kedua bernilai nol, x mungkin maksimum, minimum, ataupun tidak kedua- duanya. Menurunkan fungsi dan mencari titik – titik kritis merupakan salah satu cara yang sederhana untuk mencari nilai minimum dan maksimum, yang dapat digunakan untuk optimasi. Hal ini juga mempunyai aplikasi tersendiri dalam proses sketsa grafik, jika diketahui minimum dan maksimum dari fungsi yang diturunkan tersebut sebuah grafik dapat digunakan untuk mengamati meningkat atau menurun dari titik – titik kritis. Uji turunan kedua masih dapat digunakan untuk menganalisa titik – titik kritis dengan menggunakan matrik Hessian dari turunan parsial kedua fungsi dititik kritis. Apabila f(x) = 0 atau f1(a) tidak tertentu jika a = 0, maka a merupakan titik kritis yaitu maksimum atau minimum.

Universitas Sumatera Utara

21

Contoh : 3 Tentukan nilai ekstrim dari fungsi f(x) =

pada (-∞,∞)

Penyelesaian : Turunan pertama dari f(x) adalah f’(x) = 0 maka 0

f’(x) = ( x + 1)(x – 3) =0 sehingga nilai x = -1 dan x = 3 maka titik kritis f

(x) adalah -1 dan 3. Maka turunan kedua dari f(x) adalah f”(x) = 2x – 2 sehingga nilai untuk mengujinya maka bahwa (x + 1)(x - 3) > 0 pada (-∞, -1) dan (3, ∞) maka menurut uji dari turunan pertama dapat disimpulkan bahwa

merupakan

merupakan nilai minimum grafiknya

nilai minimum dan untuk diperlihatkan oleh gambar dibawah ini.

y

3 2 maksimum 1 -2

-1

0

1

2

3

4

x

-1 -2

Minimum

-3 -4 -5

Gambar 2.3. Grafik nilai maksimum dan minimum

Universitas Sumatera Utara

22

2.6 Fungsi Utilitas Marginal

Fungsi utilitas merupakan fungsi yang menjelaskan besarnya utilitas (kepuasan, kegunaan) yang diperoleh seseorang dari mengkonsumsi suatu barang atau jasa. Pada umumnya semakin banyak jumlah suatu barang dikonsumsi semakin besar utilitas yang diperoleh, kemudian mencapai titik puncaknya (titik jenuh) pada jumlah konsumsi tertentu, sesudah itu justru menjadi berkurang atau bahkan negatif jika jumlah barang yang dikonsumsi terus menerus ditambah. Utilitas total merupakan fungsi dari jumlah barang yang dikonsumsi. Adapun persamaan utilitas total (total utility, U) dari mengkonsumsi suatu jenis barang berupa fungsi kuadrat parabolic, dengan kurva berbentuk parabola terbuka kebawah. Utilitas marginal (marginal utility, MU) merupakan utilitas tambahan yang diperoleh dari setiap unit barang yang dikonsumsi. Secara matematik, fungsi utilitas marginal merupakan derivative pertama dari fungsi utilitas total.

Jika fungsi utilitas total

dinyatakan dengan U= f(Q) dimana U melambangkan utilitas total dan Q jumlah barang yang dikonsumsi, maka utilitas marginal : MU = U’ = dU / dQ (Dumairy, 1996 : 226 ) U

U = f(Q)

0

MU

Q

Gambar 2.4. Grafik bentuk kurva utilitas

Universitas Sumatera Utara

23

Karena fungsi utilitas total yang non liner pada umumnya berbentuk fungsi kuadrat, fungsi utilitas marginalnya akan berbentuk fungsi liner. Kurva utilitas marginal (MU) selalu mencapai nol tepat pada saat kurva utilitas total (U) berada pada posisi puncaknya. Contoh : 4 U = f(Q) = 90Q – 5Q2 MU = U’ = 90 – 10Q U maksimum pada MU = 0 MU = 0 Sehingga nilai Q = 9 Maka, Umaksimum = 90(9) – 5(9)2 = 810 – 405 = 405

Diperlihatkan oleh gambar dibawah ini : U, MU

405

U = 90Q – 5Q2

90

0

9

18

Q

MU = 90 -10Q

Gambar 2.5. Grafik kurva fungsi U = f(Q) = 90Q – 5Q2 dan MU = U’ = 90 – 10Q

Universitas Sumatera Utara

24

2.7 Produk Marginal

Produk marginal ( marjinal product, MP) ialah produk tambahan yang dihasilkan dari suatu unit tambahan faktor produksi yang digunakan. Secara matematik fungsi produk marjinal merupakan derivative pertama dari fungsi produk total. Jika fungsi produk total dinyatakan P = f(x) dimana P melambangkan jumlah produk total dan x adalah jumlah masukan, maka produk marginal : MP = P’ = dp/ dx

Karena fungsi produk total yang non liner pada umumnya berbentuk fungsi kubik, fungsi produk marjinalnya akan berbentuk fungsi kuadrat. Kurva produk marginal (MP) selalu mencapai nilai ektrimnya, dalam hal ini nilai maksimum, tepat pada saat kurva produk total ( P) berada pada posisi titik beloknya. Produk total mencapai puncaknya ketika produk marjinalnya nol. Produk total menurun bersamaan dengan produk marginal menjadi negatif. Produk marjinal negatif menunjukkan bahwa penambahan penggunaan masukan yang bersangkutan justru akan mengurangi jumlah produk total. (Dumairy, 1996: 227)

Contoh 5. Produksi total P = f(x) = 9x2 – x3 produk marjinalnya adalah MP = P’ = 18x – 3x2 Sehingga Pmaksimum pada P’ = 0 yaitu pada x = 6 dengan Pmaksimum = 108 P berada dititik belok dan MP maksimum pada P’’ = (MP)’ = 0 yaitu pada x = 3

Universitas Sumatera Utara

25

Diperlihatkan oleh gambar dibawah ini : P,MP 108

P=f(X)

54

27

0

x 3

6

MP = g(x)

Gambar. 2.6. Kurva fungsi P = f(x) = 9x2 – x3 dan MP = P’ = 18x – 3x2

Universitas Sumatera Utara