PERANAN PERSYARATAN KARUSH-KUHN-TUCKER DALAM MENYELESAIAN PEMROGRAMAN KUADRATIS SKRIPSI AMALIA

PERANAN PERSYARATAN KARUSH-KUHN-TUCKER DALAM MENYELESAIAN PEMROGRAMAN KUADRATIS

SKRIPSI

AMALIA 050803033

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009

Amalia : Peranan Persyaratan Karush-Kuhn-Tucker Dalam Menyelesaikan Pemrograman Kuadratis, 2010.

PERANAN PERSYARATAN KARUSH-KUHN-TUCKER DALAM MENYELESAIAN PEMROGRAMAN KUADRATIS

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains

AMALIA 050803033

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009


ii

PERSETUJUAN

Judul : PERANAN PERSYARATAN KARUSH KUHN QQQQQQQQQQQQQQQQQ.gTUCKER DALAM MENYELESAIKAN QQQQQQQQQQQQQQQQQ .PEMROGRAMAN KUADRATIK Katagori : SKRIPSI Nama : AMALIA Nomor Induk Mahasiswa : 050803033 Program Studi : PROGRAM (S1) MATEMATIKA Departemen : MATEMATIKA Fakultas : MATEMATIKA DAN ILMU PENGETAHUAN qqqqqqqqqqqqqqqqqqqqqqqqqqALAM (FMIPA) UNIVERSITAS SUMATERA qqqqqqqqqqqqqqqqqqqqqqqqqkUTARA Diluluskan di Medan, Desember 2009 Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Drs. H. Haludin Panjaitan NIP. 194603091979021001

Drs. Marwan Harahap, M.Eng NIP. 194612251974031001

Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,

Dr. Saib Suwilo, M.Sc NIP. 196401091988031004


iii

PERNYATAAN

PERANAN PERSYARATAN KARUSH KUHN TUCKER DALAM MENYELESAIAN PEMROGRAMAN KUADRATIS

SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, Desember 2009

AMALIA 050803033


iv

PENGHARGAAN

Puji dan syukur penulis ucapkan kehadirat Allah SWT karena atas berkah dan rahmatNya kepada penulis hingga dapat menyelesaikan skripsi ini. Pada kesempatan ini penulis mengucapkan banyak terima kasih kepada : 1. Bapak Drs. Marwan Harahap, M.Eng dan Bapak Drs. H. Haludin Panjaitan, selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan bimbingan, pengarahan serta pemeriksaan terhadap skripsi ini sehingga dapat selesai dengan baik. 2. Bapak Dr. Saib Suwilo, M.Sc dan Drs. Henry Rani Sitepu, M.Si, selaku Ketua dan Sekretaris Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. 3. Bapak Prof. DR. Eddy Marlianto, M.Sc, selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, seluruh Staf Pengajar jurusan Matematika yang telah mendidik penulis selama mengikuti perkuliahan. 4. Ayahanda dan Ibunda tercinta, abang dan kakak, serta seluruh keluarga yang telah memberikan semangat dan dukungan yang tak ternilai harganya. 5. Rekan-rekan mahasiswa Matematika stambuk 2005, khususnya Depi, Feby, Nenna, Rima, Sundari, Yuni, Andika, Radhi, Santri, dan masih banyak lagi yang tidak mungkin disebutkan satu persatu, terima kasih atas bantuannya.


v

ABSTRAK

Salah satu bentuk khusus dari permasalahan pemrograman nonlinier adalah masalah pemrograman kuadratik. Dimana pemrograman kuadratik ini memiliki fungsi tujuan yang berbentuk kuadratik dan fungsi kendala berbentuk linier. Dalam penelitian ini dirancang sebuah penyelesaian permasalahan pemrograman kuadratik dengan menggunakan persyaratan Karush Khun Tucker. Syarat yang harus dipenuhi untuk optimum adalah bahwa turunan parsial pertama dari fungsi tujuan terhadap semua variabel dan pengali lagrange bernilai nol. (λi g i ( x) = 0)


vi

ABSTRACT

One particular form of nonlinear programming is a quadratic programming problem. This quadratic programming where the objective function which has a quadratic form and the constraint function is a linear. In this research we proposed a quadratic programming problem solving using Karush Khun Tucker requirements. The condition that must be met for the optimum is that the first partial derivative of the objective function of all variables and Lagrange multiplier is zero. (λi g i ( x) = 0) .


vii

DAFTAR ISI

Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

ii iii iv v vi vii viii ix

Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Tinjauan Pustaka 1.4 Tujuan Penelitian 1.5 Kontribusi Penelitian 1.6 Metode Penelitian

1 2 3 5 6 6

Bab 2 Landasan Teori 2.1 Pemrograman Nonlinier 2.1.1 Pemrograman Nonlinier Tak Berkendala 2.1.2 Pemrograman Nonlinier Berkendala 2.2 Permasalahan Pemrograman Kuadratis 2.2.1 Pemilihan Portofolio dengan Sekuritas Beresiko 2.2.2 Masalah Transportasi dengan Diskon Volume pada Biaya Pengiriman Barang 2.3 Konveksitas Fungsi 2.6.1 Fungsi Konveks atau Konkaf Satu Variabel 2.6.2 Fungsi Konveks dan Konkaf untuk Beberapa Variabel 2.4 Matriks Hessian 2.5 Matriks Definite Positif 2.6 Persyaratan Karush Khun Tucker 2.7 Masalah Komplementaritas

16 17 17 19 22 24 27

Bab 3 Pembahasan 3.1 Pemrograman Kuadratis Tak Berkendala 3.2 Pemrograman Kuadratis Berkendala modifikasi simpleks 3.3 Pemrograman Kuadratis Karush Kuhn Tucker

29 30 37

Bab 4 Penutup 4.1 Kesimpulan 4.2 Saran

41 42

Daftar Pustaka

43


7 7 8 12 12 14

viii

DAFTAR TABEL

Halaman Table 1.1 Uji Konveksitas untuk Fungsi Dua Variabel Tabel 1.2 Tabel Simpleks iterasi 0, 1, 2, dan 3


19 39

ix

DAFTAR GAMBAR

Halaman Gambar 1.1 Bentu Himpunan Konveks dan bukan Konveks 3

2

16

Gambar 1.2 Plot dari f ( x1 , x 2 ) = x1 + x 2 + 21 + 4 x 2 + 6

21

Gambar 1.3 Grafik dari f ( x ) = 24 − 2 x − x 2

29

3

2


1

BAB 1

PENDAHULUAN

1.1 Latar Belakang Pesatnya perkembangan ilmu pengetahuan dan teknologi membuat matematika menjadi sangat penting artinya. Oleh karena itu dapat dikatakan bahwa perkembangan ilmu pengetahuan dan teknologi tersebut tidak lepas dari peranan matematika. Hampir dapat dipastikan bahwa setiap bagian dari ilmu dan teknologi baik dalam unsur kajian umum ilmu murni maupun terapannya memerlukan peranan matematika sebagai ilmu bantunya. Salah satu bagian dari matematika terapan adalah program linear (linear programming) yang merupakan suatu model dari penelitian operasional (operation research) yang digunakan untuk memecahkan masalah optimasi. Dalam masalah optimasi ini kita diminta untuk menentukan nilai optimum (nilai maksimum atau nilai minimum) dari suatu fungsi matematik. Namun dalam pemograman linier semua fungsi yang terlibat (fungsi tujuan dan fungsi kendala) adalah linier. Meskipun pada dasarnya diaplikasikan pada banyak masalah praktis, asumsi ini sering kali tidak sesuai. Pada kenyataannya, banyak ahli ekonomi menemukan drajat nonlinearitas yang merupakan suatu aturan dan bukan merupakan suatu perkecualian dalam berbagai masalah. Oleh sebab itu, sering kali memang perlu untuk segera mengarahkan pada masalah pemrograman nonlinier, sehingga kita memfokuskan perhatian pada area yang penting ini. Terdapat banyak jenis masalah pemrograman nonlinier, tergantung pada karakteristik fungsi tujuan dan fungsi kendala. Salah satunya adalah pemograman kuadratis yang merupakan bentuk khusus dari pemrograman nonlinier. Dimana masalah pemrograman kuadaratis ini memiliki kendala linier, tetapi fungsi tujuan


2

berbentuk kuadratis. Oleh karena itu, satu-satunya perbedaan antara pemrograman ini dengan pemrograman linier terletak di fungsi tujuannya yang melibatkan pangkat dua dari variabel atau perkalian dari dua variabel. Beberapa

metode

telah

dikembangkan

untuk

menyelesaikan

kasus

pemrograman kuadratis dengan asumsi tambahan fungsi tujuan merupakan fungsi konkaf. Salah satu metode untuk menyelesaikan masalah pemrograman kuadratis adalah dengan persyaratan Karush-Kuhn-Tucker. Metode ini sangat efektif untuk permasalahan optimasi nonlinier dengan kendala pertidaksamaan.

1.2 Perumusan Masalah Dengan pendekatan persyaratan Karush-Kuhn-Tucker dapat diperoleh optimasi dari pemrograman kuadratis. Dalam hal ini kondisi yang perlu diperhatikan adalah mengikuti syarat cukup agar mendapatkan nilai-nilai variabel yang optimal untuk mencapai hasil yang diinginkan.

1.3 Tinjauan Pustaka 1. Pemrograman Kuadratis Pemrograman kuadratis adalah masalah optimasi dimana memaksimumkan atau meminimumkan fungsi tujuan yang berbentuk kuadratis dengan fungsi kendalanya berbentuk persamaan atau pertidaksamaan linier. Bentuk fungsi kuadratis dengan variabel x = ( x1 , x 2 ,..., x n ) adalah : n

f (x ) = ∑ c j x j + j =1

1 n n ∑∑ qkj xk x j 2 k =1 j =1

Dengan menggunakan notasi matriks maka persamaan diatas dapat disederhanakan menjadi


3

f (x ) = cx + Dengan kendala

1 T x Qx 2

Ax ≤ b

dan

x≥0

Dimana: Q ∈ ℜ nxn

= matriks simetris (nxn) yang dikenal juga dengan matriks Hessian

A ∈ ℜ mxn

= matriks kendala

x ∈ ℜn

= vektor kolom dari variabel keputusan

c ∈ ℜn

= vector baris dari fungsi tujuan

b ∈ ℜm

= vector kolom dari kendala bagian kanan

T

= transposisi matriks

Adanya faktor

1 pada fungsi tujuan merupakan konstanta qij (elemen dari 2

Q ) dimana qij = q ji . Maka setelah melakukan perkalian matriks dan vektor maka

fungsi tujuannya dinyatakan dalam qij , c j (elemen c) dan untuk tiap suku dengan i = j dalam penjumlahan ganda xi x j = x 2j sehingga x 2j . Ketika i ≠ j maka −

1 qij merupakan koefisien dari 2

1 (qij xi x j + qij x j xi ) , sehingga − qij adalah koefisien total 2

untuk perkalian xi dan x j .

Ketika fungsi objektif f (x) adalah cembung sempurna (konkaf) untuk semua daerah layak diperoleh titik yang merupakan minimum lokal dan juga global. Maka dalam kondisi seperti ini menjamin bahwa Q adalah definite positif.

2. Kondisi Karush-Kuhn-Tucker Pada tahun 1951 Kuhn Tucker mengemukakan suatu teknik optimisasi yang dapat digunakan untuk pencarian titik optimum dari suatu fungsi yang berkendala. Metode Karush Kuhn Tucker ini dapat dipergunakan untuk mencari solusi yang optimum dari suatu fungsi tanpa memandang sifat dari fungsi tersebut apakah linier atau nonlinier. Jadi metode Kuhn Tucker ini bersifat teknik yang umum dalam


4

pencarian titik optimum dari setiap fungsi. Metode Karush Kuhn Tucker dapat digunakan untuk memecahkan persoalan baik yang nonlinier maupun yang linier. Jika kita menghadapi masalah optimasi dalam bentuk : Maksimumkan / minimumkan :

Dengan kendala

Z = f (X )

dengan X = {x1 , x 2 ,..., x n }t

gi (X ) ≤ / ≥ 0

:

dengan

i = 1,2,3,…, m

X ≥0

m ≤ n (jumlah kendala lebih kecil dari variabel) Pertama tuliskan kembali persyaratan-persyaratan yang tak negative seperti − x1 ≤ 0,− x 2 ≤ 0,...,− x n ≤ 0 , sehingga himpunan kendalanya adalah m + n persyaratan ketidaksamaan yang masing-masing dengan tanda lebih kecil dari pada atau sama dengan. Kemudian tambahkan variabel-variabel kurang x n2+1 , x n2+ 2 ,..., x 22n + m berturutturut pada ruas kiri dari kendala-kendala tadi, yang dengan demikian merubah tiaptiap ketidaksamaan menjadi suatu kesamaan. Variabel-variabel kendur (slack

variables) yang ditambahkan disini berbentuk suku-suku kuadrat untuk menjamin bahwa mereka tak negatif. Kemudian bentuk fungsi Lagrange :

m

[

] ∑ λ [− x

L ≡ f ( X ) − ∑ λi g i ( X ) − x n2+i − i =1

m+ n

i = m +1

1

i

+ x n2+i

]

Untuk λ1 , λ 2 ,..., λ m + n adalah pengali-pengali Lagrange. Terakhir selesaikan sistem

persamaan ∂L =0 ∂x j

( j = 1,2,...,2n + m )

∂L =0 ∂λi

(i = 1,2,..., m + n )

λi ≥ 0

(i = 1,2,..., m + n )

Persamaan-persamaan diatas membentuk persyaratan Karush-Kuhn-Tucker untuk maksimasi ataupun minimasi program liner dan nonlinier.


5

3. Kondisi Optimal dalam Pemrograman Kuadratis Prosedur menggunakan Kondisi Karush-Kuhn-Tucker untuk memecahkan suatu masalah optimasi dalam pemrograman kuadratis dengan kendala berupa suatu pertidaksamaan, secara essensial melibatkan langkah-langkah yang sama seperti halnya dalam menggunakan teorema Lagrange untuk memecahkan masalah optimasi dengan kedala berupa persamaan, yaitu pertama bentuklah suatu ”Lagrangean” L.[3] Jadi dalam hal ini dibentuk suatu fungsi L ( x, y ) =

1 T x Qx + cx + y ( Ax − b ) 2

Dimana y adalah baris vektor dimensi m . Maka kondisi Karush-Kuhn-Tucker untuk lokal minimum memenuhi ∂L ≥ 0 , j = 1,2,..., n ∂x j

c + x T Q + yA ≥ 0

∂L ≥ 0 , i = 1,2,..., m ∂y i

Ax − b ≤ 0

xj

∂L = 0 , j = 1,2,..., n ∂x j

(

)

x T c T + Qx + AT y = 0

y i g i (x ) = 0 , i = 1,2,..., m

y ( Ax − b ) = 0

x j ≥ 0 , j = 1,2,..., n

x≥0

y i ≥ 0 , i = 1,2,..., m

y≥0

Dimana

y ∈ ℜ n = surplus variabel nonnegatif v ∈ ℜ m = slack variabel nonnegatif.

1.4 Tujuan Penelitian

Adapun tujuan penulisan ini adalah menguraikan cara dan persyaratan KarushKuhn-Tucker untuk mendapatkan nilai optimum (nilai maksimum atau nilai minimum) dari pemrograman kuadratis.


6

1.5 Kontribusi Penelitian

Selain untuk tambahan literatur dan pengetahuan pembaca mengenai metode yang dapat digunakan dalam menentukan nilai optimum dari pemograman kuadratis, dalam

bidang

ekonomi

memformulasikan

penelitian

pemrograman

ini

kuadratis

juga

bermanfaat

dalam

untuk

pemilihan

membantu

portofolio

dan

sekuritasnya yang beresiko.

1.6 Metode Penelitian

Metode penelitian dalam tulisan ini adalah : 1. Membuat formulasi model pemrograman kuadratis dalam bentuk persyaratan Karush-Kuhn-Tucker 2. Fungsi tujuan yang telah dimodifikasi menjadi m

L(x, λ ) = f ( X ) + ∑ λ1 g i ( X ) ; harus sesuai pada titik tersebut i =1

3. Menghitung titik-titik kritis dan menguji nilai untuk fungsi objektif pada setiap titik-titik kritis tersebut yang membuat nilai fungsi objektif menjadi optimum. 4. Mencari semua solusi ( x, λ ) dalam himpunan persamaan berikut ∂L ( x, λ ) = 0 ; ∂x j

j = 1,2,..., n

Dimana ∂L ( x, λ ) ≥ 0 ; ∂λi

λi

∂L ( x, λ ) = 0 ; ∂λi

λ≥0 i = 1,2,..., l

5. Diperoleh titik-titik kritis yang merupakan solusi optimal dari pemrograman kuadratis.


7

BAB 2

LANDASAN TEORI

2.1 Pemrograman Nonlinier Pemrograman nonlinier merupakan pemrograman dengan fungsi tujuannya saja atau bersama dengan fungsi kendala berbentuk nonlinier yaitu pangkat dari variabelnya lebih dari satu. Salah satu bentuk umun masalah pemrograman nonlinier adalah untuk menentukan x = ( x1 , x 2 ,..., x n ) sehingga mencapai tujuan untuk: Maksimumkan / Minimumkan

:

f (x )

Dengan kendala

:

g m (x ) ≥ 0

dan

x≥0

Dengan f ( x ) dan g m (x ) merupakan fungsi yang diketahui dengan n variabel keputusan. Terdapat banyak jenis masalah pemrograman nonlinier dalam berbagai bentuk. Hal ini tergantung pada karakteristik fungsi tujuan dan kendalanya. Pemrograman nonlinier dapat mempunyai kendala ataupun tidak mempunyai kendala.

2.1.1 Pemrograman Nonlinier Tak Berkendala Pemrograman nonlinier tak berkendala merupakan masalah optimasi yang tidak memiliki batasan-batasan, sehingga untuk x = ( x1 , x 2 ,..., x n ) mempunyai fungsi tujuan adalah Maksimumkan / Minimumkan

:

f (x )

Syarat perlu dan cukup agar suatu penyelesaian x = x* merupakan penyelesaian optimal saat f(x) merupakan fungsi yang dapat diturunkan adalah


8

∂f =0 ∂x j

Pada

x = x* , untuk j = 1,2,..., n

Dimana f (x ) merupakan fungsi konkaf, 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. Ketika variabel x j memiliki kendala nonnegativitas atau x j ≥ 0 , kondisi yang diperlukan dan mungkin cukup akan berubah menjadi

∂f ∂x j

⎧≤ 0 ⎨ ⎩= 0

pada x = x * , jika x j * = 0 pada x = x * , jika x j * > 0

Untuk setiap j.

Setelah titik kritis yang memenuhi kondisi diketahui, masing-masing titik digolongkan sebagai maksimum atau minimum lokal jika fungsi tersebut bersifat konveks ataupun konkaf disekitar titik tersebut. Maksimum dan minimum global akan ditemukan dengan membandingkan minimum lokal dan maksimum lokal dan kemudian menguji nilai dari fungsi tersebut dengan sebagian variabel mendekati − ∞ atau + ∞ . Jika fungsi diketahui konveks maupun konkaf, maka titik kritisnya pastilah merupakan minimum global maupun mkasimum globalnya.

2.1.2 Pemrograman Nonlinier Berkendala

Pemrograman nonlinier berkendala merupakan masalah optimasi yang memiliki batasan-batasan, sehingga untuk x = ( x1 , x 2 ,..., x n ) , maka bentuk standard untuk program-program tak linier yang mengandung hanya kendala-kendala kesamaan (equality) adalah Maksimumkan / Minimumkan

:

f (x )

Dengan kendala

:

g1 (x ) = 0

………… g m (x ) = 0


9

Disini m ≤ n (jumlah kendala lebih kecil daripada variabel) , jika terjadi bahwa m > n, maka biasanya tidak dapat diselesaikan. Pada program minimasi dapat diubah ke dalam bentuk program maksimasi dengan mengalikan fungsi objektif -1. Suatu metode yang dapat dipakai untuk menyelesaikan masalah optimasi ini adalah metode pengali Lagrange. Metode pengali Lagrange dipilih karena prinsip kerjanya sederhana dan mudah dimengerti. Metode ini dimulai dengan pembentukan fungsi Lagrangian yang didefinisikan sebagai: m

L( X , λ ) = f ( X ) + ∑ λ j g m ( X ) j =1

Teorema:

Syarat perlu bagi sebuah fungsi f(X) dengan kendala gi(X)=0, dengan j = 1,2,..., m agar mempunyai minimum relatif pada titik X* adalah derivasi parsial pertama dari fungsi Lagrangenya yang didefinisikan sebagai L = L( x1 , x 2 ,..., x n , λ1 , λ2 ,..., λm ) terhadap setiap argumennya mempunyai nilai nol.

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

Q=

n

n

∑∑

i =1 j = 1

∂2L ∂x i ∂x j ∂x i ∂x j

dievaluasi pada X = X* harus definit positif (atau negatif) untuk setiap nilai dX yang memenuhi semua kendala. n

∂2L ∂xi ∂x j menjadi definit positif (atau negatif) untuk j =1 ∂xi ∂x j n

Syarat perlu agar Q = ∑∑ i =1

setiap variasi nilai dX adalah setiap akar dari polinomial, z i , yang didapat dari determinan persamaan di bawah ini harus positif (atau negatif).


10

(L11 − z )

K K

L21 M

L12 (L22 − z ) M

L13 L23 O

Ln1

Ln 2

Ln 3

g11 g 21 M g m1

g12 g 22 M g m2

g13 g 23 M K g m3 K

Dengan Lij =

(

∂2L X *,λ ∂xi ∂x j

)

K K K K

L1n L2 n M

(Lnn − z )

g11 g12 M

g 21 g 22 M

g m1

g m2

g 1n g 2n M g mn

0 0 M 0

0 0 M 0

K g n1 K g 2n K M K gn K 0 K 0 K K

M 0

( )

∂g i X * ∂x j

dan g ij =

Pengali Lagrange mempunyai arti secara fisik yang menarik. Misalkan terdapat permasalahan optimasi dengan satu kendala sebagai berikut: Maksimumkan / Minimumkan

:

f (x )

Dengan kendala

:

g (x ) = b

Fungsi Lagrange-nya adalah L( X , λ ) = f ( X ) + λ (b − g ( X ))

Syarat perlu untuk penyelesaian diatas adalah : ∂L =0 ∂xi

i = 1,2,..., n

untuk

dan

∂L =0 ∂λ Persamaan diatas menghasilkan : ∂f ∂g −λ =0 ∂xi ∂xi

untuk

i = 1,2,..., n

b − g(X ) = 0

atau

b=g


11

Maka : ∂f ∂g ∂xi − λ ∂xi = 0 ∂xi ∂xi atau

n

∂f

∑ ∂x ∂x i −1

atau

n

− λ∑

i

= λ∑

i

∂f

∑ ∂x ∂x i −1

atau

n

i

i −1 n

i

i −1

i = 1,2,..., n

untuk

∂g ∂xi = 0 ∂xi

∂g ∂xi ∂xi

n ∂g = λ ∑ ∂xi i −1 −1 ∂x i 1 42i4 3 1i4 243 n

∂f

∑ ∂x ∂x df

i

dg

df = λdb

Menghasilkan hasil yang final yaitu :

atau

df = λ * db

Dari Persamaan ini dapat ditarik kesimpulan bahwa: pada penyelesaian optimum, perubahan fungsi tujuan f, berbanding lurus dengan perubahan kendala b dengan faktor sebesar pengali Lagrange λ. Bentuk standard dari program-program tak linier yang mengandung hanya kendala-kendala ketidaksamaan adalah : Maksimumkan / Minimumkan

:

f (x )

Dengan kendala

:

g i (x ) ≤ 0 untuk i = 1,2,..., n x≥0

Kunci dari penanganan permasalahan di atas adalah merubah kendala pertidaksamaan menjadi persamaan dengan menambah variabel slack. Masalah pemrograman ini ditandai dengan adanya kendala-kendala yang sama sepenuhnya dengan pemrograman linier. Semua fungsi kendala g i ( x ) adalah linier, tetapi fungsi tujuan f (x ) berbentuk nonlinier. Masalah ini dipertimbangkan secara sederhana dengan hanya memiliki satu fungsi nonlinier yang diperhitungkan, bersama dengan daerah layak dari pemrograman linier. Sejumlah algoritma khusus yang didasari atas perluasan metode simpleks telah dikembangkan untuk memperhitungkan fungsi tujuan yang nonlinier.


12

2.2 Permasalahan Pemrograman Kuadratis

Masalah pemrograman kuadratis memiliki fungsi tujuan yang berbentuk kuadratis yang melibatkan x j dan xi x j ( i ≠ j ) dan memiliki kendala berbentuk linier. 2

Pemrograman kuadratis sangat penting karena dapat diterapkan pada berbagai masalah yang ada. Beberapa contoh kasus yang merupakan masalah dari pemrograman kuadratis ini adalah :

2.2.1 Pemilihan Portofolio dengan Sekuritas Beresiko

Saat ini para manjer professional dari portofolio besar biasa menggunakan model komputer berbasis pemrograman nonlinier untuk memandu pekerjaan mereka. Oleh karena itu inverstor harus memperhatikan baik ekspetasi pendapatan maupun resiko investasi, pemrograman nonlinier digunakan untuk menentukan portofolio yang pada asumsi tertentu dapat menghasilkan keseimbangan optimal antara kedua factor tersebut. Pendekatan ini sebagian besar merupakan hasil riset yang dilakukan oleh Harry Markowitz dan William Sharpe, pemenang hadiah nobel tahun 1990 dalam bidang ekonomi karena hasil risetnya tersebut. Model pemrograman nonlinier untuk masalah ii dapat dirumuskan sebagai berikut. Misalkan terdapat n senis saham/sekuritas yang sedang dipertimbangkan untuk masuk dalam portofolio, dan variabel keputusan x j ( j = 1,2,..., n ) adalah share dari saham j yang masuk dalam portofolio. μ i dan σ jj adalah (estimasi) rata-rata dan varians masing-masing untuk pendapatan setiap share dari saham j , dengan σ jj sebagai ukuran resiko dari saham ini. Untuk i = 1,2,..., n(i ≠ j ) , adalah σ ij kovariansi dari pendapatan setiap share antara saham i dan saham j . Oleh karena itu sulit mengestimasi seluruh nilai σ ij , langsung dari σ ii dan σ jj . Kemudian, nilai ekspetasi R( x ) dan variansi V (x ) dari total pendapatan keseluruhan portofolio adalah n

R(x ) = ∑ μ j x j j =1

Dan

n

n

V ( x ) = ∑∑ σ ij xi x j i =1 j =1


13

Dengan V (x ) mengukur resiko yang terasosiasi dengan portofolio. Salah satu cara

untuk mempertimbangkan keseimbangan antara dua faktor adalah dengan

menggunakan V ( x ) sebagai fungsi tujuan untuk diminimalkan dan menggunakan kendala yang memastikan R(x ) tidak lebih kecil dari ekspetasi pendapatan minimum yang dapat diterima. Model pemrograman nonlinier yang lengkap adalah

Minimumkan

n

n

V ( x ) = ∑∑ σ ij xi x j i =1 j =1

Dengan kendala

n

∑μ j =1

j

xj ≥ L

j

xj ≥ B

n

∑p j =1

xj ≥ 0

untuk

j = 1,2,..., n

dengan L adalah ekspetasi pendapatan minimum yang dapat diterima, Pj adalah harga tiap share dari saham j dan B adalah jumlah uang yang dianggarkan untuk portofolio. Untuk memilih nilai L yang sesuai agar tercapai keseimbangan terbaok antara R( x ) dan V ( x ) relatif sulit. Jadi daripada berhenti dengan satu pilihan nilai L ,

pendekatan pemrograman nonlinier parametric biasa digunakan untuk membangkitkan solusi optimal sebagai fungsi L pada kisaran nilai L yang lebar. Langkah selanjutnya adalah mengevaluasi R(x ) dan V ( x ) untuk solusi optimal tersebut dan memilih solusi yang memberikan keseimbangan antara dua nilai itu. Prosedur ini sering disebut pembangkitan solusi pada batas efisien dari grafik dua dimensi titik-titik {R(x ), V ( x )} untuk nilai x yang layak. Alasannya adalah titik {R(x ), V ( x )} yang

optimal untuk x (pada beberapa nilai L ) pasti terletak pada batas daerah layak setiap nilai optimal x disebut efisien karena tidak ada solusi layak lain yang sekurangkurangnya memiliki satu nilai ukuran yang sama R atau V dan lebih baik pada ukuran yang lain (nilai V yang lebih kecil atau nilai R yang lebih besar).


14

2.2.2 Masalah Transportasi dengan Diskon Volume pada Biaya Pengiriman Barang

Jenis aplikasi dari masalah transportasi dengan volume pada biaya pengiriman barang adalah menentukan rencana yang optimal untuk mengirimkan barang dari berbagai sumber ke berbagai tempat tujuan pengiriman, dengan kendala sumber dan permintaan, dengan tujuan untuk meminimalkan total biaya pengiriman. Kita asumsikan biaya pengiriman per unit dari sumber tertentu ke tujuan pengiriman adalah tetap, tanpa memperhatikan jumlah pengiriman. Pada kenyataannya, biaya ini mungkin tidak tetap. Diskon volume kadang tersedia untuk pengiriman dalam jumlah yang besar sehingga biaya marginal pengiriman satu atau lebih unit mungkin akan mengikuti pola bila jumlah pengiriman besar maka biaya marginal juga akan semakin besar begitu juga sebaliknya. Dengan demikian hasilnya adalah biaya yang terjadi dari pengiriman x unit diberikan dalam bentuk fungsi nonlinier C ( x ) , yang merupakan fungsi poongan linier sama dengan biaya marginal.. konsekuensinya, jika setiap kombinasi dari sumber dan tujuan memiliki fungsi biaya pengiriman yang sama maka biaya pengiriman xij unit dari sumber i = 1 = (1,2,..., m) ke tujuan j = 1 = (1,2,..., n) dinyatakan dengan funsi nonlinier Cij ( xij ) sehingga keseluruhan fungsi tujuan diminimalkan adalah m

n

f ( x ) = ∑∑ C ij ( xij ) i =1 j =1

Meskipun dengan funsi tujuan yang nonlinier, kendala dari permasalahan ini adalah kendala linier khusus yang sesuai dengan model permasalahan tranportasi. Dari contoh-contoh kasus diatas maka dapat kita tuliskan bentuk standard dari pemrograman kuadratis yaitu Minimumkan :

n

f (x ) = ∑ c j x j + j =1

1 n n ∑∑ qij xi x j 2 i =1 j =1


15

Dengan menggunakan notasi matriks maka persamaan diatas dapat disederhanakan menjadi Minimumkan : Dengan kendala:

f ( x ) = cx + Ax ≤ b

1 T x Qx 2

x≥0

dan

Dimana:

Q ∈ ℜ nxn = matriks simetris (nxn) yang dikenal juga dengan matriks Hessian A ∈ ℜ mxn = matriks kendala

x ∈ ℜn

= vektor kolom dari variabel keputusan

c ∈ ℜn

= vector baris dari fungsi tujuan

b ∈ ℜm

= vector kolom dari kendala bagian kanan

T

= transposisi matriks

Adanya faktor

1 pada fungsi tujuan merupakan konstanta qij (elemen dari 2

Q ) dimana qij = q ji . Maka setelah melakukan perkalian matriks dan vektor maka fungsi tujuannya dinyatakan dalam qij , c j (elemen c) dan untuk tiap suku dengan

i = j dalam penjumlahan ganda xi x j = x 2j sehingga x 2j . Ketika i ≠ j maka −

1 qij merupakan koefisien dari 2

1 (qij xi x j + qij x j xi ) , sehingga − qij adalah koefisien total 2

untuk perkalian xi dan x j .

Beberapa algoritma telah dikembangkan untuk khasus pemrograman kuadratis dengan funsi tujuan merupakan fungsi konkaf. Satu cara untuk membuktikan bahwa fungsi tujuan merupakan fungsi konkaf adalah dengan membuktikan kondisi yang sepadan dengan x T Qx ≥ 0 . Untuk semua x yaitu Q merupakan matriks definite positif. Penyelesaian dari masalah pemrograman kuadratis ini dapat dilakukan dengan pendekatan kondisi persyaratan Karush Kuhn Tucker kemudian dinyatakan ulang dalam bentuk yang mirip dengan program linier, sehingga mempermudah mencari solusi optimalnya.


16

2.3 Konveksitas Fungsi

Konsep konveksitas sering digunakan dalam bidang penelitian operasianal, terutama dalam ruang lingkup pemrograman nonlinier. Konsep fungsi konveks berhubungan langsung dengan himpunan konveks. Jadi, jika f ( x1 , x 2 ,..., x n ) adalah fungsi konveks maka kumpulan titik-titik yang terletak diatas atau pada grafik f ( x1 , x 2 ,..., x n ) membentuk himpunan konveks. Hal yang sama, kumpulan titik yang

terletak di bawah atau pada grafik fungsi konkaf adalah himpunan konveks. Himpunan konveks mempunyai sifat penting yaitu untuk beberapa himpunan konveks, kumpulan titik yang berada dalam semua himpunan (irisan dari himpunan konveks) juga merupakan himpunan konveks. Dengan demikian, kumpulan titik yang terletak di atas atau pada fungsi konveks dan di bawah atau pada fungsi konkaf adalah merupakan himpunan konveks juga. Jadi, himpunan konveks dapat dilihat secara intuitif sebagai kumpulan titik dengan batas atas fungsi konveks dan batas bawah fungsi konkaf. Sebuah himpuan vektor berdimensi- m adalah konveks jika untuk dua vektor yang termasuk dalam himpunan ini berlaku bahwa penggal garis (line segment) antara kedua vektor juga termasuk dalam himpunan ini.

C

C

Q

P

Penggal garis antara P dan Q

S

R

Gambar 1.1 Bentuk Himpunan Konveks dan Bukan Konveks


17

2.3.1 Fungsi Konveks atau Konkaf Satu Variabel Definisi :

Fungsi satu variabel f ( x ) disebut fungsi konveks jika setiap pasangan nilai x , katakanlah x ′ dan x ′′(x ′ < x ′′) , f [λx ′′ + (1 − λ ) x ′] ≤ λf ( x ′′) + (1 − λ ) f ( x ′) untuk semua nilai λ yang memenuhi 0 < λ < 1 . Fungsi tersebut merupakan fungsi konveks ketat jika ≤ dapat diganti < dan merupakan fungsi konkaf (fungsi konkaf ketat) jika pernyataan ≤ diganti dengan ≥ (atau dengan > ).

f ( x ) bersifat konveks jika untuk setiap pasang titik pada grafik f ( x ) , segmen garis yang menghubungkan kedua titik ini terletak pada ataupun diatas grafik f (x ) dan begitu juga sebaliknya untuk fungsi konkaf. Tepatnya jika memeiliki turunan kedua, maka f ( x ) bersifat konveks jika dan hanya jika d 2 f (x ) / dx 2 > 0 untuk setiap nilai x yang mungkin. Uji konveksitas untuk fungsi satu variabel : Pertimbangkan fungsi satu variabel f ( x ) yang memeiliki turunan kedua untuk setiap nilai x yang mungkin. Dengan demikian, fungsi f ( x ) dapat bersifat: 1. Konveks jika dan hanya jika

d 2 f (x ) ≥ 0 untuk setiap nilai x yang mungkin. dx 2

2. Konveks ketat jika dan hanya jika 3. Konkaf jika dan hanya jika

d 2 f (x ) > 0 untuk setiap nilai x yang mungkin. dx 2

d 2 f (x ) ≤ 0 untuk setiap nilai x yang mungkin. dx 2

4. Konkaf ketat jika dan hanya jika

d 2 f (x ) < 0 untuk setiap nilai x yang mungkin. dx 2

2.3.2 Fungsi Konveks dan Konkaf untuk Beberapa Variabel

Konsep fungsi konveks dan konkaf dari satu variabel dapat digeneralisasikan untuk fungsi dengan lebih dari satu variabel. Dengan demikian, saat f ( x ) digantikan dengan fungsi f ( x1 , x 2 ,..., x n ) definisi masih diterapkan apabila x digantikan oleh

(x1 , x2 ,..., xn ).

Hal yang sama, penafsiran geometri yang berhubungan juga berlaku


18

setelah generalisasi konsep titik dan segmen garis. Jadi, sama dengan nilai ( x, y ) tertentu ditafsirkan sebagai sebuah titik dalam ruang dua dimensi. Setiap kemungkinan nilai dari

(x1 , x2 ,..., xn )

dapat diartikan sebagai titik dalam ruang

m − dimensi (ruang Euclide).

Misalakan m = n + 1 , titik pada grafik f ( x1 , x 2 ,..., x n ) menjadi nilai yang mungkin dari titik

[x1 , x2 ,..., xn , f (x1 , x2 ,..., xn )] .

Kemudian,

(x1 , x 2 ,..., xn , xn+1 )

dikatakan terletak di atas, tepat, atau di bawah grafik f ( x1 , x 2 ,..., x n ) tergantung pada

(

)

nilai x n +1 yang lebih besar, sama dengan atau lebih kecil daripada f x1 , x 2 ,..., x mn .

Definisi :

(

Segmen garis yang menghubungkan kedua titik x1′ , x 2′ ,..., x ′m

)

(

dan x1′′, x 2′′ ,..., x m′′

)

merupakan penjumlahan titik-titik

(x , x ,..., x ) = [λx′′ + (1 − λ ) x′ , λx′′ + (1 − λ ) x′ ,..., λx′′ + (1 − λ ) x′ ] 1

2

m

1

1

2

2

m

m

dengan 0 ≤ λ ≤ 1 . Jadi segmen garis dalam ruang m − dimensi merupakan generalisasi langsung dari segmen garis dalam ruang dua dimensi.

Definisi :

f ( x1 , x 2 ,..., x n ) merupakan fungsi konveks jika untuk setiap pasang titik pada grafik f ( x1 , x 2 ,..., x n ) , segmen garis yang menghubungkan kedua titik tersebut seluruhnya terletak di atas atau tepat pada grafik fungsi

f ( x1 , x 2 ,..., x n ) . Fungsi tersebut

merupakan fungsi konveks ketat jika segmen garis tersebut seluruhnya terletak diatas grafik kecuali pada kedua titik akhirnya. Begitu juga sebaliknya untuk fungsi konkaf dan fungsi konkaf ketat. Turunan parsial kedua dapat digunakan untuk menguji fungsi banyak variabel konveks atau tidak, meskipun dengan cara yang lebih kompleks. Misalnya, jika terdapat dua variabel dan semua turunan parsial ada di semua tempat, uji konveksitas menilai tiga kuantitas memenuhi pertidaksamaan yang sesuai untuk semua nilai

(x1 , x 2 ) yang mungkin seperti yang ditunjukkan pada tabel berikut ini :


19

Tabel 1.1 Uji Konveksitas untuk Fungsi Dua Variabel Kuantitas

Konveks Konveks Konkaf Ketat

d 2 f ( x1 , x 2 ) d 2 f ( x1 , x 2 ) ⎡ d 2 f ( x1 , x 2 ) ⎤ −⎢ ⎥ 2 2 dx12 dx 22 ⎣ dx1 dx 2 ⎦

Kankaf Ketat

≥0

>0

≥0

>0

d 2 f ( x1 , x 2 ) dx12

≥0

>0

≤0

<0

d 2 f ( x1 , x2 ) dx22

≥0

>0

≤0

<0

f ( x1 , x 2 ,..., x n ) adalah konveks jika dan hanya jika matriks Hessian

n × n − nya positif definite untuk semua nilai

(x1 , x2 ,..., xn )

yang mungkin. Uji

konveksitas selalu diperlukan sebagai sifat umum fungsi. Akan tetapi, beberapa fungsi nonkonveks memenuhi syarat konveksitas pada interval tertentu dari variabel. Dengan demikian, penting untuk membicarakan fungsi yang menjadi konveks pada daerah tertentu.

2.4 Matriks Hessian

Matrik Hessian adalah matrik yang setiap elemennya dibentuk dari turunan parsial kedua dari suatu fungsi. Milsalkan f(x) fungsi dengan n variabel yang memiliki turunan parsial kedua dan turunan-turunannya kontinu, Matriks Hessian dari f(x) ditulis H adalah ⎡ ∂2 f ⎢ 2 ⎢ ∂x2 1 ⎢ ∂ f H ⎢ ∂x ∂x ⎢ 2 1 ⎢ L 2 ⎢ ∂ f ⎢⎣ ∂x n ∂x1

∂2 f ∂x1 ∂x 2 ∂2 f ∂x 22 L ∂2 f ∂x n ∂x 2

∂2 f ⎤ ⎥ ∂x1 ∂x n ⎥ ∂2 f ⎥ L ∂x 2 ∂x n ⎥ ⎥ O L ⎥ 2 ∂ f ⎥ L ∂x n2 ⎥⎦ L


20

Matrik Hessian dapat digunakan untuk melakukan uji turuanan 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. Misalkan x0 adalah titik stasioner dari F dan kita definisikan H = H( x0 ) dengan persamaan

H ij = Fxi y j ( x0 )

dimana

H ( xt ) adalah Hessian dari F pada x0

Titik stasioner dapat digolongkan sebagai berikut : 1. x0 adalah suatu minimum relatif dari F jika H ( x0 ) definite positif 2. x0 adalah suatu maksimum relatif dari F jika H ( x0 ) definite negatif 3. x0 adalah suatu titik pelana dari F jika H ( x0 ) indefinite

Teorema 2.2 :

Misalkan nilai eigen dari matriks Hnxn adalah λ1, λ2 , λ3, …, λn yang didefinisikan oleh

λI − H = 0 dengan I adalah matriks identitas ukuran nxn. Maka : (i) H adalah definite negatif jika dan hanya jika nilai eigen dari matriks H yaitu λ1, λ2 , λ3, …, λn kesemuanya bertanda negatif. (ii) H adalah definite positif jika dan hanya jika nilai eigen dari matriks H yaitu λ1, λ2 , λ3, …, λn kesemuanya bertanda positif. (iii) H adalah Semi definite negatif jika dan hanya jika nilai eigen dari matriks H yaitu λi ≤ 0, i = 1, 2, 3, …, n (iv) H adalah Semi definite positif jika dan hanya jika nilai eigen dari matriks H yaitu λi ≥ 0, i = 1, 2, 3, …, n

Contoh : 3

3

2

2

f ( x1 , x 2 ) = x1 + x 2 + 2 x1 + 4 x 2 + 6 Titik-titik ekstrem harus memenuhi syarat:


21

∂f = 3 x12 + 4 x1 = x1 3 x1 + 4 = 0 ∂x1

(

)

∂f = 3 x 22 + 8 x 2 = x 2 3 x 2 + 8 = 0 ∂x 2

(

)

Persamaan di atas dipenuhi oleh titik-titik (0, 0); (0, –8/3); (–4/3, 0); dan (–4/3, –8/3) Untuk mengetahui titik yang mana yang maximum dan yang mana yang minimum, harus diselidiki matrik Hessiannya. Derivasi kedua dari f adalah: ∂2 f = 6 x1 + 4, 2 ∂x1

∂2 f = 6 x 2 + 8, 2 ∂x 2

∂2 f =0 ∂x1 x2

dan

Jadi matrik Hessiannya menjadi 0 ⎤ 0 ⎤ ⎡6 x + 4 ⎡6 x + 4 sehingga H 1 = [6 x1 + 4] dan H 2 = ⎢ 1 H =⎢ 1 ⎥ 6 x 2 + 8⎦ 6 x 2 + 8⎥⎦ ⎣ 0 ⎣ 0

Nilai matrik Hessian untuk masing-masing titik ekstrem disajikan di bawah ini.

(x1 , x 2 )

Matriks H

H1

H2

(0,0)

⎡ 4 0⎤ ⎢0 8 ⎥ ⎣ ⎦

+4

+ 32

8⎞ ⎛ ⎜ 0,− ⎟ 3⎠ ⎝

⎡4 0 ⎤ ⎢0 − 8⎥ ⎣ ⎦

+4

− 32

⎛ 4 ⎞ ⎜ − ,0 ⎟ ⎝ 3 ⎠

⎡ − 4 0⎤ ⎢ 0 8⎥ ⎣ ⎦

−4

− 32

−4

+ 32

⎛ 4 8 ⎞ ⎡− 4 0 ⎤ ⎜ − ,− ⎟ ⎢ ⎥ ⎝ 3 3 ⎠ ⎣ 0 − 8⎦

Sifat ( x1 , x 2 )

f ( x1 , x 2 )

Minimum

6

Tak tentu

Titik belok

418 27

Tak tentu

Titik belok

194 27

Maksimum

50 3

Sifat H

Definite positif

Definite negatif

3

3

2

2

Gambar 1.2 Plot dari f ( x1 , x 2 ) = x1 + x 2 + 21 + 4 x 2 + 6


22

2.5 Matriks Definite Positif

Bentuk kuadrat pada

(x1 , x2 ,..., x n )

adalah ekspresi yang dapat kita tulis

⎡ x1 ⎤ ⎢x ⎥ sebagai [x1 , x 2 ,..., x n ]. A.⎢ 2 ⎥ . Dengan A adalah matriks simetrik nxn . Jadi misalkan ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦ ⎡ x1 ⎤ ⎢x ⎥ X = ⎢ 2 ⎥ maka bentuk ini dapat ditulis sebagai X t AX ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦ Definisi

Bentuk kuadrat X t AX disebut definite positif jika X t AX > 0 untuk semua x ≠ 0, sedangkan matriks simetrik A kita sebut matriks definit positif jika X t AX adalah bentuk kuadrat definit positif.

Contoh :

Dipunyai matriks simetrik berikut : ⎡ 2 −1 0 ⎤ a = ⎢⎢− 1 2 − 1⎥⎥ ⎢⎣ 0 − 1 2 ⎥⎦

Untuk mengkaji apakah matriks A bersifat definte positif, maka: X AX = [x1 t

= [x1

x2

⎡ 2 − 1 0 ⎤ ⎡ x1 ⎤ x3 ] ⎢⎢− 1 2 − 1⎥⎥ ⎢⎢ x 2 ⎥⎥ ⎢⎣ 0 − 1 2 ⎥⎦ ⎢⎣ x3 ⎥⎦

x2

⎡ 2 x1 − x 2 ⎤ ⎢ x3 ] ⎢− x 2 + 2 x 2 − x3 ⎥⎥ ⎢⎣ − x 2 + 2 x3 ⎥⎦

= x 1 (2 x 1 − x 2 ) + x 2 (− x 1 + 2 x 2 − x 3 ) + x 3 (− x 2 + 2 x 3 ) = 2 x12 − x 1 x 2 − x 1 x 2 + 2 x 22 − x 2 x 3 − x 2 x 3 + 2 x32 = 2 x12 − 2 x 1 x 2 + 2 x 22 − 2 x 2 x 3 + 2 x32


23

= x12 + ( x12 − 2 x1 x 2 + x 22 ) + ( x 22 − 2 x 2 x3 + x32 ) + x32 = x12 + ( x1 − x 2 ) 2 + ( x 2 − x3 ) 2 + x32 Dari sini dapat disimpulkan bahwa matrik A bersifat definit positif karena memenuhi: x12 + ( x1 − x 2 ) 2 + ( x 2 − x3 ) 2 + x32 > 0 kecuali jika x1 = x 2 = x3 = 0

Sebaliknya matrik A dan bentuk kuadrat X t AX disebut : 1. Definite negatif jika X t AX < 0 , untuk semua x ≠ 0 . 2. Semidefinite positif jika X t AX ≥ 0 , untuk semua x. 3. Semidefinite negatif jika X t AX ≤ 0 , untuk semua x. 4. Indefinite 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 definite positif. Suatu himpunan syarat perlu dan syarat cukup bentuk X t AX sebagai definite positif adalah h11 > 0 ,

h11 h21

h12 > 0, h22

h11 h21 h31

h12 h22 h32

h13 h23 > 0 , . . . , A > 0 h33

Jika n minor dari A adalah positif, maka X t AX adalah definite positif. Dan X t AX hanya definite positif, jika minor-minor ini positif. 2. Syarat perlu dan syarat cukup untuk bentuk definite negatif Suatu himpunan syarat perlu dan syarat cukup bentuk X t AX menjadi definite negatif atau setaranya untuk X t (− A) X sebagai definite positif adalah h11 < 0 ,

h11

h12

h21

h22

> 0,

h11 h21 h31

h12 h22 h32

h13 h23 < 0 , . . . , (−1) n A > 0 h33

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


24

2.6 Persyaratan Karush Khun Tucker Pada tahun 1951 Kuhn Tucker mengemukakan suatu teknik optimisasi yang dapat digunakan untuk pencarian titik optimum dari suatu fungsi yang berkendala. Metode Karush Kuhn Tucker ini dapat dipergunakan untuk mencari solusi yang optimum dari suatu fungsi tanpa memandang sifat dari fungsi tersebut apakah linier atau nonlinier. Jadi metode Kuhn Tucker ini bersifat teknik yang umum dalam pencarian titik optimum dari setiap fungsi. Metode Karush Kuhn Tucker dapat digunakan untuk memecahkan persoalan baik yang nonlinier maupun yang linier. Jika kita menghadapi masalah optimasi dalam bentuk : Maksimumkan / minimumkan : Dengan kendala

Z = f (X )

dengan X = {x1 , x 2 ,..., x n }t

gi (X ) ≤ / ≥ 0

:

dengan

i = 1,2,3,…, m

X ≥0

m ≤ n (jumlah kendala lebih kecil dari variabel) Pertama tuliskan kembali persyaratan-persyaratan yang tak negative seperti − x1 ≤ 0,− x 2 ≤ 0,...,− x n ≤ 0 , sehingga himpunan kendalanya adalah m + n persyaratan ketidaksamaan yang masing-masing dengan tanda lebih kecil dari pada atau sama dengan. Kemudian tambahkan variabel-variabel kurang x n2+1 , x n2+ 2 ,..., x 22n + m berturutturut pada ruas kiri dari kendala-kendala tadi, yang dengan demikian merubah tiaptiap ketidaksamaan menjadi suatu kesamaan. Variabel-variabel kendur (slack

variables) yang ditambahkan disini berbentuk suku-suku kuadrat untuk menjamin bahwa mereka tak negatif. Kemudian bentuk fungsi Lagrange :

m

[

] ∑ λ [− x

L ≡ f ( X ) − ∑ λi g i ( X ) − x n2+i − i =1

m+ n

i = m +1

1

i

+ x n2+i

]

Untuk λ1 , λ2 ,..., λm + n adalah pengali-pengali Lagrange. Terakhir selesaikan sistem persamaan


25

∂L =0 ∂xi

(i = 1,2,...,2n + m )

∂L =0 ∂λi

(i = 1,2,..., m + n )

λi ≥ 0

(i = 1,2,..., m + n )

Untuk fungsi konveks, syarat perlu dan cukup untuk mencapai titik minimum dapat dicari menggunakan syarat Karush Kuhn Tucker. Tetapi untuk fungsi nonkonvek, syarat Karush Kuhn Tucker merupakan syarat perlu saja, tetapi belum cukup untuk mencapai optimal. Jadi untuk masalah jenis konveks, syarat Karush Kuhn Tucker menjadi syarat perlu dan cukup untuk sebuah minimum/maksimum global.

Teorema 1 (Frederick S. Hillier dan Gerald J. Lieberman, 1994) Misalkan f(x,y) merupakan fungsi 2 variabel. f(x,y) merupakan fungsi konveks jika dan hanya jika dipenuhi ketiga syarat berikut : (i)

d 2 f ( x1 , x 2 ) d 2 f ( x1 , x 2 ) ⎡ d 2 f ( x1 , x 2 ) ⎤ . =⎢ ⎥ 2 2 dx12 dx 22 ⎣ dx1 dx 2 ⎦

(ii)

d 2 f ( x1 , x 2 ) ≥0 dx12

(iii)

d 2 f ( x1 , x 2 ) ≥0 dx 22

2

Teorema 2 (Frederick S. Hillier dan Gerald J. Lieberman, 1994) Suatu fungsi 2 variabel f(x,y) merupakan fungsi konkaf jika tidak memenuhi paling tidak satu dari ketiga syarat pada teorema 1, atau dengan kata lain –f(x,y) merupakan fungsi konveks.

Teorema 3 (Frederick S. Hillier dan Gerald J. Lieberman, 1994) Untuk permasalahan dengan asumsi f(x) konkaf dan gj(x) konveks, maka syarat perlu dan

cukup

keoptimalannya

berdasarkan

teorema

berikut.

Misalkan

f ( x), g1 ( x), g 2 ( x),..., g m ( x) merupakan fungsi-fungsi yang dapat diturunkan maka


26

x * = ( x1′ , x 2′ ,..., x n′ ) merupakan penyelesaian optimal untuk masalah program nonlinier apabila terdapat sejumlah λi untuk i = 1,2,..., m sehingga semua syarat terpenuhi : (i)

m ∂g j ∂f + ∑ λi =0 ∂xi j =1 ∂xi

(ii)

λjg j = 0

j = 1,2,..., m

(iii)

gj ≤0

j = 1,2,..., m

(iv)

λj ≥ 0

j = 1,2,..., m

i = 1,2,..., n

Syarat Karush Kuhn Tucker untuk program nonlinier berkendala :

Teorema Diasumsikan f ( x), g1 ( x), g 2 ( x),..., g m ( x) merupkan fungsi yang dapat diturukan maka x * = ( x1′ , x 2′ ,..., x n′ ) menjadi solusi optimal untuk permasalahan pemrograman nonlinier hanya jika terdapat sejumlah m bilangan μ1 , μ 2 ,..., μ m sehingga semua syarat kondisi Karush Kuhn Tucker berikut ini terpenuhi : (i)

m ∂g ∂f − ∑ λi ≤0 ∂x j i =1 ∂x j

pada x = x *

untuk j = 1,2,..., n

(ii)

m ⎛ ∂f ∂g ⎞ ⎟=0 − ∑ λi xj⎜ ⎜ ∂x ⎟ ∂ x i = 1 j j ⎝ ⎠

pada x = x *

untuk j = 1,2,..., n

(iii)

g i ( x * ) − bi ≤ 0

untuk j = 1,2,..., m

(iv)

λi [g i ( x * ) − bi ] = 0

untuk j = 1,2,..., m

(v)

x *j ≥ 0

untuk j = 1,2,..., m

(vi)

λj ≥ 0

untuk j = 1,2,..., m

Dapat dilihat darik kondisi (ii) dan (iv) memerlukan hasil perkalian dua kuantitas sama dengn nol. Oleh karena itu, tiap kondisi ini menyatakan bahwa setidaknya salah satu dari kuantitas itu harus sama dengan nol. Akibatnya, kondisi (iv) dapat digabung dengan kondisi (iii) untuk menyatakan mereka dalam bentuk lain sebagai berikut.: g i ( x * ) − bi = 0

(atau ≤ 0 jika μ i = 0 )

untuk i = 1,2,..., m


27

Demikian pula kondisi (ii) dapat digabung dengan kondisi (i) menjadi : m ∂g ∂f − ∑ λi i = 0 ∂x j i =1 ∂x j

(atau ≤ 0 jika x *j = 0 )

untuk j = 1,2,..., m

Ketika m=0 (tidak ada kendala yang berbentuk fungsi), jumlahan berbilai 0 dan fungsi gabungan (i,ii) menjadi kondisi yang ada. Oleh karena itu, untuk m>0, tiap suku dalam jumlahan mengubah kondisi untuk m=0 dengan memasukkan pengaruh dari kendala berbentuk fungsi yang bersangkutan. Dalam kondisi diatas, μ i setara dengan variabel dual dalam pemrogramana linier dan memiliki interpretasi ekonomi yang juga dapat diperbandingkan. Akan tetapi, μ i juga ada dalam penurunan matematika seperti dalam faktor pengali Lagrange. Pada kondisi (iii) dan (v) hanya melakukan penegasan kelayakan dari solusi. Kondisi yang lainnya menghilangkan sebagian besar solusi layak lainnya menjadi kandidat yang mungkin untuk menjadi solusi optimal.

Corollary Diasumsikan bahwa f (x ) merupakan fungsi konkaf

dan g1 ( x), g 2 ( x),..., g m ( x)

merupakan fungsi konveks (misalakan saja masalah ini merupakan masalah pemrograman konveks), dengan semua fungsi ini memenuhi kondisi biasa. Lalu x * = ( x *1 , x * 2 ,..., x * n ) adalah solusi optimal jika dan hanya jika semua kondisi teorema terpenuhi.

2.7 Masalah Komplementaritas Saat kita berhadapan dengan pemrograman kuadratis, maka kita harus mengetahui terlebih dahulu bagaimana menyelesaikan permasalahan pemrograman nonlinier tertentu dapat direduksi menjadi memecahkan masalah komplementaritas. Dengan variabel w1 , w2 ,..., w p dan z1 , z 2 ,..., z p , masalah komplementaritas bertujuan menemukan solusi layak untuk kendala

w = F ( z)

w≥0

z≥0


28

Yang juga memenuhi kendala komplementaritas

wT z = 0 Disini, w dan z adalah vektor kolom. F adalah fungsi bernilai vektor yang diketahui, dan T menandakan transpose matriks. Masalah ini tidak memiliki fungsi tujuan, sehingga secara teknis bukanlah murni masalah pemrograman nonlinier. Hal ini disebut masalah komplementaritas karena hubungan komplementernya. w = 0 atau z i = 0 (atau kedua-duanya) untuk i = 1,2,..., p Suatu kasus khusus yang penting yaitu masalh komplementaritas linier dengan

F ( z ) = q + Mz Dengan q merupakan vektor kolom yang diketahui dan M adalah matriks pxp yang diketahui. Algoritma yang efisien telah dikembangkan untuk pemecahan masalah ini dengan asumsi tertentu tentang sifat matriks M. satu jenis algoritma menggunakan pemutaran (pivoting) dari satu solusi BF (Basic Feasible) kesolusi BF selanjutnya, seperti metode simpleks dalam pemrograman linier. Masalah komplementaritas ini memiliki aplikasi dalam teori permainan, masalah keseimbangan ekonomi, dan masalah keseimbangan teknik sebagai tambahan sebagai aplikasi dari pemrograman nonlinier.


29

BAB 3

PEMBAHASAN

Dalam masalah optimasi terdapat dua bentuk optimasi yaitu, optimasi fungsi tak bersyarat dan optimasi fungsi bersyarat. Kita sudah mengenal beberapa cara untuk menyelesaikan bentuk yang pertama seperti uji turunan pertama, uji turunan kedua, untuk fungsi satu variabel, serta uji parsial kedua untuk fungsi dua variabel, semuanya telah diuraikan pada bab sebelumya. Sedangkan untuk jenis yang kedua merupakan jenis yang paling banyak kita jumpai dalam kehidupan nyata. Banyak aplikasi dari pemodelan matematika dalam optimasi fungsi yang mensyaratkan beberapa kondisi atau syarat untuk diperoleh suatu solusi optimal. Syarat ini yang mengoptimumkan fungsi tujuan. Persoalan dengan model tersebut dinamakan optimasi bersyarat. Bentuk umum dari optimasi fungsi dengan kendala adalah tentukan nilai dari variabel keputusan (nilai ekstrim) x = ( x1 , x 2 ,..., x n ) yang memaksimumkan (meminimumkan) fungsi dari permasalahan: Maksimumkan / minimumkan :

Z = f (X )

Dengan kendala

g1 ( X )(≤ / ≥) b1

:

.......... g i ( X )(≤ / ≥) bi

dengan

i = 1,2,3, …, m

Dimana f(X) merupakan fungsi tujuan (objective function), dan g i ( X )(≤, =, ≥) bi merupakan fungsi kendala.

3.1 Pemrograman Kuadratis Tak Berkendala

Contoh : Maksimalkan f ( x ) = 24 − 2 x − x 2 Dengan kendala x ≥ 0


30

24 - x^2 - 2*x y

Maksimum global karena f ( x ) adalah ∂f = −2 ≤ 0 pada x = 0 konkaf dan ∂x Jadi, x = 0 adalah optimal.

25

20

15

10

5 0 -4

-2

0

2

4 x

Gambar 1.3 Contoh yang mengambarkan solusi optimal dapat terletak pada titik dengan nilai turunan negatif, bukan nol, karena titik tersebut terletak pada batas kendala nonnegativitas. Solusi optimal untuk suatu masalah dengan satu variabel terletak pada x = 0 meskipun turunannya bernilai negatif. Oleh karena itu setiap permasalahan yang memiliki fungsi konkaf untuk dimaksimalkan pada kendala nonnegativitas, mempunyai turunan yang kurang dari satu atau sama dengan nol untuk x = 0 adalah kondisi yang diperlukan dan cukup untuk x = 0 menjadi optimal.

3.2 Pemrograman Kuadratis Berkendala Modifikasi Simpleks

Contoh : Maksimalkan

:

f ( x1 , x 2 ) = 15 x1 + 30 x 2 + 4 x1 x 2 − 2 x12 − 4 x 22

Dengan kendala

:

x1 + 2 x 2 ≤ 30 x1 ≥ 0 x2 ≥ 0

Penyelesaian : Dalam kasus ini diperoleh c = [15 30]

⎡x ⎤ x = ⎢ 1⎥ ⎣ x2 ⎦

⎡ 4 − 4⎤ Q=⎢ ⎥ ⎣− 4 8 ⎦


31

A = [1 2]

b = [30]

Catat bahwa :

x T Qx = [x1

⎡ 4 − 4⎤ ⎡ x1 ⎤ x2 ] ⎢ ⎥⎢ ⎥ ⎣− 4 8 ⎦ ⎣ x 2 ⎦

⎡x ⎤ = [ (4 x1 − 4 x1 ) (− 4 x1 + 8 x 2 ) ] ⎢ 1 ⎥ ⎣ x2 ⎦ 2 = 4 x12 − 4 x1 x 2 − 4 x1 x 2 + 8 x 21 2 = q11 x12 − q 21 x1 x 2 − q12 x1 x 2 + q 22 x 21

Mengalikan dengan −

−

1 mengghasilkan 2

1 T x Qx = −2 x12 + 4 x1 x 2 − 4 x 22 2

Yang merupakan bagian nonlinier dari fungsi tujuan untuk contoh ini. Oleh karena 1 q11 = 4 dan q 22 = 8 ini menggambarkan bahwa − q jj merupakan koefisien dari x 2j 2 dalam fungsi tujuan. Fakta bahwa q12 = q 21 = −4 menggambarkan bahwa baik − qij maupun − q ji adalah koefisien total untuk perkalian xi dan x j .

Kondisi KKT untuk Pemrograman Kuadratis Untuk konkritnya, kita mulai dengan membentuk kondisi Karush Kuhn Tucker adalah sebagai berikut : 1.

( j = 1) . 15 + 4 x 2 − 4 x1 − μ1 ≤ 0

2.

( j = 1) . x j (15 + 4 x 2 − 4 x1 − μ1 ) = 0

1.

( j = 2) . 30 + 4 x1 − 8 x 2 − 2μ1 ≤ 0

2.

( j = 2) . x 2 (30 + 4 x1 − 8 x 2 − 2 μ1 ) = 0

3.

x1 + 2 x 2 − 30 ≤ 0

4.

μ1 ( x1 + 2 x 2 − 30) = 0

5.

x1 ≥ 0 ,

6.

μ1 ≥ 0

x2 ≥ 0


32

Untuk mulai menyatakan ulang kondisi ini di dalam bentuk yang lebih tepat, kita memindahkan konstanta dalam kondisi 1 ( j = 1) ,1 ( j = 2) , dan 3 ke sisi sebelah kanan dan lalu menambahkan slack variabel nonnegatif yang dilambangkan dengan y1 , y 2 , v1 untuk mengubah pertidaksamaan menjadi persamaan.

1. ( j = 1) . − 4 x1 + 4 x 2 − μ1 + y1 = −15 1. ( j = 2) . − 4 x1 − 8 x 2 − 2 μ1 + y 2 = −30 3.

x1 + 2 x 2 + v1 = 30

Perhatikan bahwa kondisi 2 ( j = 1) sekarang dapat dinyatakan ulang secara sederhana, yaitu memerlukan syarat x1 = 0 atau y1 = 0 , yaitu 2 ( j = 1) . x1 y1 = 0 Dengan cara yang sama, kondisi 2 ( j = 2) dan 4 dapat digantikan dengan 2 ( j = 2) . x 2 y 2 = 0 4.

μ1v1 = 0

Untuk setiap dari tiga pasang variabel ini ( x1 . y1 ) , ( x 2 . y 2 ) , ( μ1 , v1 ) dua variabel tersebut disebut variabel komplementer,karena hanya satu dari dua variabel ini yang dapat bernilai selain nol. Bentuk baru kondisi 2 ( j = 1) ,2 ( j = 2) ,dan 4 ini dapat digabung menjadi satu kendala yaitu : x1 y1 + x 2 y 2 + μ1v1 = 0

Yang disebut kendala komplementaritas. Setelah mengalikan dengan -1 persamaan untuk kondisi 1 ( j = 1) dan 1 ( j = 2) untuk mendapat ruas kanan nonnegatif, kita sekarang memiliki bentuk yang diinginkan untuk keseleruhan kondisi seperti yang ditunjukkan sebagai berikut. 4 x1 − 4 x 2 + μ1 − y1 = 15 − 4 x1 + 8 x 2 + 2 μ1 − y 2 = 30 x1 + 2 x 2 + v1 = 30 x1 ≥ 0 , x 2 ≥ 0 , μ1 ≥ 0 , y1 ≥ 0 , y 2 ≥ 0 , v1 ≥ 0 x1 y1 + x 2 y 2 + μ 1 v1 = 0


33

Bentuk ini cukup baik karena, kecuali untuk kendala komplementaritas, kondisi ini adalah kendala pemrograman linier . Untuk setiap masalah pemrograman kuadratis, kondisi Karush Kuhn Tuckernya dapat direduksi menjadi bentuk inidengan hanya mengandung kendala pemrograman linier ditambah satu kendala komplentaritas. Dalam notasi matriks dapat dituliskan bentuk umumnya adalah

Qx + AT u − y = c T Ax + v = b x ≥ 0, u ≥ 0,

y ≥ 0, v ≥ 0

xT y + uT v = 0

Dengan element vektor u adalah u i dari bagian sebelumnnya dan elemenelemen vektor kolom y dan v adalah slack variabel. Oleh karena fungsi tujuan masalah asli diasumsikan konkaf dan fungsi kendalanya linier sehingga konveks maka corollary teorema pada kondisi Karush Kuhn Tucker dapat digunakan. Oleh karena itu, x optimal jika dan hanya jika y, u dan v memiliki nilai sehingga semua empat vektor memenuhi kondisi di atas. Masalah asli tereduksi menjadi masalah untuk mencari solusi layak untuk kendala ini.

Metode Modifikasi Simpleks Metode modifikasi simpleks memanfaatkan kata kunci bahwa, dengan perkecualian pada kendala komplementer bentuk kondisi Karush Kuhn Tucker yang telah diperoleh tidak lebih daripada kendala pemrogramn linier. Lebih jauh lagi, kendala komplementer menyatakan secara sederhana dan tidak langsung bahwa tidak mungkin bagi pasangan variabel komplementer untuk keduanya menjadi variabel basis (satu-satunya variabel >0) saat solusi BF menjadi pertimbangan. Oleh karena itu, masalah ini menjadi masalah pencarian solusi BF awal pada tiap masalah pemrograman linier yang memeiliki kendala ini, dengan kendala tambahan ini atas identitas dari variabel basis.


34

Pada kasus sederhana pencarian BF awal relatif langsung dengan c T < 0 dan b ≥ 0 , variabel basis awal merupakan elemen y dan v (dengan mengalikan kumpulan

persamaan pertama dengan -1), sehingga solusi yang diinginkan adalah x = 0 , u = 0 ,

y = −c T , v = b . Kalau tidak, kita perlu meninjau lembali masalah dengan memasukkan variabel artificial untuk setiap persamaan dengan c j > 0 (tambahkan variabel tersebut pada ruas kiri) atau bi < 0 (kurabgiruas kiri dengan variabel tersebut lalu kalikan kedua ruas dengan -1) untuk menggunakan variabel artificial ini ( z1 , z 2 dan seterusnya) sebagai variabel basis awal untuk masalah yang ditinjau ulang tersebut. (Perhatikan bahwa pilihan variabel basis asal ini memenuhi kendala komplementer, karena bagian variabel nonbasis, x = 0 dan u = 0 secara otomatis) Selanjutnya untuk mencari solusi BF untuk masalah kuadratis diatas misalnya dengan menggunakan metode simpleks (dengan satu modifikasi) pada masalah pemrograman linier berikut Minimalkan

Z = ∑zj j

Pada kendala-kendala pemrograman linier yang diperoleh dari kondisi Karush Kuhn Tucker, tetapi dengan melibatkan variabel artificial. Satu modifikasi dalam metode simpleks adalah dengan perubahan pada prosedur memilih variabel basis yang akan masuk.

Aturan Masuk-Terbatas : ketika kita memilih variabel basis yang masuk, jangan ikut sertakan variabel nonbasis yang memeiliki variabel komplementer berupa variabel basis; pilihan harus diambil dari variabel nonbasis lain sesuai dengan criteria biasa untuk metode simpleks. Aturan ini menjaga kendala komplementer terpenuhi disepanjang algoritma. Ketika solusi optimal x * , u * , y * , v * , z * , = 0 , . . . , z n = 0 . x * merupakan solusi optimal yang diharapkan untuk masalah asli pemrograman kuadratis.


35

Dari contoh di atas maka diketahui f ( x1 , x 2 ) adalah fungsi konkaf dengan matriks

⎡ 4 − 4⎤ Q=⎢ ⎥ adalah definite positif, maka algoritma dapat diterapkan. Titik awal ⎣− 4 8 ⎦ untuk menyelesaikan permasalahan ini adalah kondisi Karush Kuhn Tucker yang telah diperoleh sebelumnya. Setelah memasukkan variabel artificial yang diperlukan, masalah pemrograman linier yang harus diselesaikan dengna metode modifikasi simpleks adalah Minimalkan

:

Dengan kendala :

Z = z1 + z 2 4 x1 − 4 x 2 + μ1 − y1 + z1 = 15

− 4 x1 + 8 x 2 + 2 μ1 − y 2 + z 2 = 30 x1 + 2 x 2 + v1 = 30 x1 ≥ 0 , x 2 ≥ 0 , μ1 ≥ 0 , y1 ≥ 0 , y 2 ≥ 0 , v1 ≥ 0 , z1 ≥ 0 , z 2 ≥ 0

Kendala komplementer tambahan adalah x1 y1 + x 2 y 2 + μ 1 v 1 = 0

Kendala komplementer tambahan ini tidak termasuk secara eksplisit dalam masalah, karena algoritma akan memaksakan kendala ini secara otomatis dengan adanya turan masuk-terbatas. Khususnya, untuk setiap dari tiga pasang variabel komplementer ( x1 . y1 ) , ( x 2 . y 2 ) , ( μ1 , v1 ) kapan pun jika salah satu dari dua variabel ini menjadi variabel basis, variabel yang lain tidak dapat diikutsertakan menjadi calon untuk variabel basis yang masuk. Variabel yang tidak nol merupakan variabel basis. Oleh karena variabel basis awal untuk masalah ini z1 , z 2 , v1 memberikan solusi BF awal yang memenuhi kendala komplementer, maka tidak mungkin kendala ini dilanggar oleh solusi BF yang berikutnya. Tabel berikut menunjukkan hasil dari penerapan metode modifikasi simpleks pada masalah pemrograman kuadratis di atas.


36

Iterasi 0 Variabel

Ruas

x1

x2

μ1

y1

y2

v1

z1

z2

z1

4

-4

1

-1

0

0

1

0

15

z2

-4

8

2

0

-1

0

0

1

30

v1

1

2

0

0

0

1

0

0

30

Z

0

-4

-3

1

1

0

0

0

-45

x1

x2

μ1

y1

y2

v1

z1

z2

2

0

2

-1

−

1 2

0

1

1 2

30

1 2

1

1 4

0

-

1 8

0

0

1 8

3

v1

2

0

Z

-2

Basis

Kanan

Iterasi 1 Variabel Basis z1 x2

-

Kanan

3 4

1 2

0

1 4

1

0

0

-2

1

1 2

0

0

1 2

x1

x2

μ1

y1

y2

v1

z1

z2

z1

0

0

5 2

-1

−

3 4

-1

1

3 4

7

1 2

x2

0

1

1 8

0

-

1 16

1 4

0

1 16

9

3 8

x1

1

0

−

1 4

0

1 8

1 2

0

−

1 8

11

Z

0

0

−

5 2

1

3 4

1

0

−

−

1 4

Ruas

1 2

22

-30

Iterasi 2 Variabel Basis

1 4


Ruas Kanan

1 4

−7

1 2

37

Iterasi 3 Variabel

x1

x2

μ1

u1

0

0

1

-

5 2

−

x2

0

1

0

1 20

-

x1

1

0

0

Z

0

0

0

Basis

y1

-

y2

Ruas

v1

z1

z2

5 2

5 2

3 10

3

1 20

1 40

9

3 10

-

1 40

3 10

1 10

1 20

5 2

1 10

0

0

0

1

-

−

Kanan

1 20

12

1

0

Hasil solusi optimal dari permasalahan kuadratis di atas adalah x1 = 12 , x 2 = 9 , u1 = 3 , dengan sisa variabel yang ada bernilai nol. Solusi optimal ini

memenuhi kondisi Karush Kuhn Tucker untuk masalah asal ketika ditulis dengan bentuk yang ada. Oleh karena itu, solusi optimal untuk pemrograman kuadratis adalah yang termasuk hanya variabel x1 dan x 2 yaitu x1 = 12 dan x 2 = 9 . Dengan demikian diperoleh nilai fungsi maksimumnya adalah

f ( x1 , x 2 )

= 15(12) + 30(9) + 4(12)(9) - 2(12)2 - 4(9)2 = 180 + 270 + 432 – 288 – 324 = 270

3.3 Pemrograman Kuadratis Karush Kuhn Tucker Sebagai ilustrasi tentang penggunakan kondisi Karush Kuhn Tucker dalam pemrograman kuadratis di atas dapat juga di selesaikan sebagai berikut : Maksimalkan

:

f ( x1 , x 2 ) = 15 x1 + 30 x 2 + 4 x1 x 2 − 2 x12 − 4 x 22

Dengan kendala

:

x1 + 2 x 2 ≤ 30 x1 ≥ 0 , x 2 ≥ 0

Agar dapat menggunakan persyaratan Karush Kuhn Tucker, maka persoalan di atas dirumuskan kembali sebagai berikut :


38

Maksimalkan

:

f ( x1 , x 2 ) = 15 x1 + 30 x 2 + 4 x1 x 2 − 2 x12 − 4 x 22

Dengan kendala

:

g1 ( x ) = x1 + 2 x 2 − 30 ≤ 0 g 2 ( x) = − x1 ≤ 0 g 3 ( x) = − x 2 ≤ 0

Terlihat bahwa kendala dalam masalah pemrograman nonlinier perlu diubah dalam bentuk g i ( x) < 0 agar dapat menggunakan persyaratan Karush Kuhn Tucker dalam memecahkan masalah ini. Jadi semua kendala harus dibuat sama menjadi

g i ( x) ≤ 0 . Selanjutnya rumuskan kembali fungsi tujuan yang merupakakan fungsi tujuan yang dimodifikasi agar dapat dipecahkan dengan kondisi Karush Kuhn Tucker. Fungsi-fungsi tujuan dimodifikasi menjadi : 3

F = f ( x ) + ∑ λi g i

atau

i =1

F = 15 x1 + 30 x 2 + 4 x1 x 2 − 2 x12 − 4 x 22 + λ1 ( x1 + 2 x 2 − 30) + λ2 (− x1 ) + λ3 (− x 2 ) Kondisi pertama yang diperlukan adalah membuat fungsi tujuan yang dimodifikasi menjadi stasioner melalui turunan pertama terhadap setiap variabel berikut:

∂F = 15 + 4 x 2 − 4 x1 + λ1 − λ 2 = 0 ∂x1 ∂F = 30 + 4 x1 − 8 x 2 + 2λ1 − λ3 = 0 ∂x 2 Serta kendala sebagai berikut :

∂F = g1 ( x) = x1 + 2 x 2 − 50 ≤ 0 ∂λ1 ∂F = g 2 ( x) = − x1 ≤ 0 ∂λ 2 ∂F = g 3 ( x) = − x 2 ≤ 0 ∂λ3 Juga perlu membuat kondisi sebagai berikut :

λ1 g 1 ( x) = 0 , λ 2 g 2 ( x) = 0 , λ3 g 3 ( x) = 0


39

Dari persamaan-persamaan di atas maka diketahui variabel x1 dan x 2 tidak mungkin sama dengan nol. Maka agar kondisi λ 2 g 2 ( x) = 0 dan λ3 g 3 ( x) = 0 terpenuhi haruslah λ2 = 0 . Karena g 2 ( x) = − x1 ≠ 0 dan juga λ3 = 0 karena

g 3 ( x) ≠ 0 . Kemudian agar kendala ketiga dapat dipecahkan serta kondisi λ1 g1 ( x ) = 0 terpenuhi, maka perlu dibuat λ1 ≠ 0 , maka g1 ( x) = 0 . Jika g1 ( x ) = 0 berarti diperoleh g1 ( x ) = x1 + 2 x 2 − 50 = 0 . Dengan demikian kita peroleh 3 sistem baru sebagai

berikut : 1. − 4 x1 + 4 x 2 + λ1 + 15 = 0 2. − 4 x1 − 8 x 2 + 2λ1 + 30 = 0 3. x1 + 2 x 2 − 30 = 0

(dengan λ2 = λ3 = 0 )

Langkah selanjutnya adalah memecahkan sistem persamaan 1,2, dan 3 di atas dengan teknik aljabar untuk mendapatkan nilai x1 , x 2 dan λ1 . Persamaan 1 dan 2 − 4 x1 + 4 x 2 + λ1 = -15 − 4 x1 − 8 x 2 + 2λ1 = 30

-

− 4 x 2 + 3λ1 = - 45

3λ1 = −45 + 4 x 2

Persamaan 4

Persamaan 1 dan 3 − 4 x1 + 4 x 2 + λ1 = −15 x1 + 2 x 2

×1

×4

= 30

− 4 x1 + 4 x 2 + λ1 = −15

4 x1 + 8 x 2

= 120

+

12 x 2 + λ1 = 105

λ1 = 105 − 12 x 2

Persamaan 5


40

Dari persamaan 4 dan 5 di atas diperoleh nilai x 2 adalah 3(105 − 12 x 2 ) = −45 + 4 x 2

315 - 36 x 2 = − 45 + 4 x 2 360 = 40 x 2 x2 = 9

Dari persamaan 4 dengan mensubtitusikan nilai x 2 diperoleh nilai λ1 adalah

λ1 = 105 - 12 x 2

λ1 = 105 – 12(9) λ1 = -3 Dengan mensubtitusikan nilai x 2 ke persamaan 3 maka diperoleh nilai x1 adalah

x1 + 2 x 2 − 30 = 0 x1 + 2(9) − 30 = 0 x1 = 12

Dengan demikian berdasarkan persyaratan Karush Kuhn Tucker diperoleh solusi ( x1 , x 2 , λ1 , λ2 , λ3 ) = (12,9,−3,0,0) Karena λ1 < 0 untuk i = 1,2,3 maka sesuai dengan syarat cukup dari persyaratan Karush Kuhn Tucker, dapat disimpulkan bahwa solusi yang diperoleh adalah solusi yang maksimum dengan nilai x1 = 12 dan x 2 = 9 . Dengan demikian diperoleh nilai fungsi maksimumnya adalah

f ( x1 , x 2 ) = 15 x1 + 30 x 2 + 4 x1 x 2 − 2 x12 − 4 x 22 = 15(12) + 30(9) + 4(12)(9) − 2(12) 2 − 4(9) 2 = 180 + 270 + 432 − 288 − 324 = 270


41

BAB 4

KESIMPULAN DAN SARAN

4.1 Kesimpulan Dari pembahasan sebelumnya dalam menyelesaikan masalah pemrograman kuadratik dengan persyaratan Karush Kuhn Tucker, dapat disimpulkan bahwa : a. Untuk menyelesaikan masalah pemrograman kuadratik dengan kendala dapat dilakukan dengan metode modifikasi simpleks ataupun dengan persyaratan langsung dari persyaratan Karush Kuhn Tucker. b. Syarat cukup yang harus dipenuhi dalam persyaratan Karush Kuhn Tucker ini adalah mengikuti salah satu sifat yaitu untuk masalah maksimasi nilai

λi ≤ 0 dan untuk masalah minimasi λi ≥ 0 . c. Dalam contoh kasus di atas merupakan kasus maksimasi oleh karena itu nilai

λi harus ≤ 0 . Dalam contoh kita peroleh λ1 = −3 . Hal ini sesuai dengan λi ≤ 0 sehingga persyaratan Karush Kuhn Tucker ini dapat diterapkan. d. Solusi optium yang diperoleh dalam menggunakan modifikasi simpleks dan juga persyaratan Karush Kuhn Tucker adalah sama saja yaitu variabel x1 = 12 dan variable x 2 = 9 . e. Kelebihan persyaratan Karush Kuhn Tucker ini dibandingkan dengan metode modifikasi simpleks adalah dengan menggunakan persyaratan Karush Kuhn Tucker kita dapat langsung menemukan titik-titik ekstrim yang merupakan solusi dari masalah yang ada dan pengkualifikasian kendala dipenuhi. Dengan demikian prosedur berhasil digunakan. f. Pemrograman kuadratik dengan persyaratan Karush Kuhn Tucker ini dapat diterapkan dalam berbagai bidang ekonomi seperti dalam pemilihan portofolio/bursa saham.


42

4.2 Saran a. Penelitian yang dilakukan hanya sebatas 2 variabel, akan lebih baik apabila juga membahas mengenai beberapa variabel. b. Dalam menggunakan persyaratan Karush Kuhn Tucker perlu diperhatikan titik-titik ekstrimnya karena disinilah diperoleh nilai untuk solusi optimal yang merupakan variael pengambilan keputusan. c. Aplikasi yang dirancang masih sangat manual, akan lebih baik jika kita menggunakan sofware sehingga lebih memudahkan untuk memperoleh hasil yang optimal.


43

DAFTAR PUSTAKA

1. Bradley, Stephen P. 1999. “Applied Methematical Programming”. Graduate aaaaaaaaaSchool of Business Administration, Harvard University. 2. Bronson, Richard Ph.D. 1996. “Theory and Problem of Operations Research”. aaaaaaaaaUSA : McGrow-Hill,lnc. 3. De Klerk, E, D.V. Pasechnik. 2005. Journal : a Linier Programming of the Standard aaaaaaaaaQuadratic Optimization Problem”. Tilburg University. 4. Fletcher, R. 1987. “Practical Methods of Optimization”. Departement of Scotland : aaaaaaaaMathematic University of Undee. 5. Gass, Saul I. 2008. Linier Programming methods and applications. Maryland : mmmmbCollege of Business and Management. 6. Gunawan, Gani. 2002. Journal : “Faktor Pengali Kuhn Tucker dalam Teori aaaaaaaaOptimasi”. Bandung : Universitas Islam Bandung. 7. Giannessi, F. 1990. Journal : “Quadratic Programing Problems and Linier aaaaaaa.Complementary Problems”. Vol.65, No.2 8. Hillier, Frederick S & Lieberman, Gerald J. 2005. “Introduction to Operations aaaaaaaaResearch”. USA : McGrow-Hill Companies,lnc. 9. Jensen, Paul A and Jonathan F.Bard. Journal : “Operation Research Models and aaaaaaaaMethods”. www. me. utexas. Edu /~ jensen / ORMM / supplements/ S2 aaaasaaaquadratic.pdf. Diakses : 15 Oktober 2009. 10.aLuknanto, Ir.Djoko M.sc.,Ph.D. 2000. “Pengantar Optimasi Nonlinier”. aaaaaaaaYogyakarta: Universitas Gajah Mada. 11. Minoux, M. 1983. “Mathematical Programming Theory ang Algorithms”. Paris : aaaaaaaaBordas Dunot Gouthier-Villars. 12. Nasendi, B.D dan Anwar. A. 1985. “Program Linier dan Variasinya”. Jakarta : aaaaaaaaGramedia. 13. Overton, L. 1997. Journal : “ Linier Programming”. America : Draf for aaaaaaaaEncyclopedia Americana. 14. Peter, Carbonetto. 2007. Journal : “ Intuition Behind Primal-Dual For Linear and aaaaaaaaQuadratic Programming”. Colombia: Department of Computer Science, aaaaaaaaUniversity of British Colombia.


44

15. Rao, S.S. 1978. “Optimization”. Deptt.of Machanical Engg. USA : San Diego aaaaaaa.State University. 16. Rardin, Ronald L. 1998. ”Optimization in Operations Research”. New Jersey : aaaa.

Prantice Hall.International, Inc,.

17. Saunders, Michael A and John A Tomlin. Journal : “ Stable Reduction to KKT aaaaaaaaSystem in Barrier Methods for Linier and Quadratic Programming”. aaaaaaaawww.stanford.edu/group/SOL/papers/kkt.pdf.. Diakses : 16 Oktober aaaaaaaa2009. 18. Utam, Ngakan Putu Satria. 2005. Journal : “Aplikasi metode Extended Quadratic sssssssssInterior Point, Bali : Universitas Udayana. 19. Vanderbei, Robert J. 2001. “Linear Programming: Foundation and Extension”. aaaaaaaaPrinceton : Departement of Operations Research and Financial aaaaaaaaEngineering Princeton University. 20. Wegner, P, Journal : “ a Quadratic Programming Formulation of the Portfolio aaaaSelection.Model”.www.actuaries.org.uk/data/assets/pdf_file/0020/../46847 aaaa6.pdf. Diakses : 20 Oktober 2009.


PERANAN PERSYARATAN KARUSH-KUHN-TUCKER DALAM MENYELESAIAN PEMROGRAMAN KUADRATIS SKRIPSI AMALIA

Recommend Documents