PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

METODE HIMPUNAN AKTIF UNTUK MENYELESAIKAN MASALAH PEMROGRAMAN KUADRATIK

Skripsi Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Oleh: Yudith Kase NIM: 083114014

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2012


ACTIVE SET METHODS TO SOLVE QUADRATIC PROGRAMMING PROBLEMS

Thesis Presented as Partial Fulfillment of the Requirements to obtain The Sarjana Sains Degree in Mathematics

By: Yudith Kase Student Number : 083114014

MATHEMATICS STUDY PROGRAM, MATHEMATICS DEPARTMENT FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2012 ii


iii


iv


v


HALAMAN PERSEMBAHAN

Ketika hatiku merasa pahit dan buah pinggangku menusuknusuk rasanya,

aku dungu dan tidak mengerti, seperti hewan aku di dekatMu;

tetapi aku tetap di dekatMu; Engkau memegang tangan kananku.

Dengan nasihatMu Engku menuntun aku, dan kemudian Engkau mengangkat

aku ke dalam kemuliaan. (Mazmur 73:2124)

Skripsi ini kupersembahkan kepada: Tuhan Yesus dan Bunda Maria, juru selamat dan pelindungku Almarhum Bapa yang selalu mendoakanku, Mama dan kedua saudaraku terkasih Engel dan Ewal My beloved sister Ima Teme beserta keluarga Universitas kebangganku Sanata Dharma

vi


vii


ABSTRAK

Penentuan penyelesaian masalah pemrograman nonlinear, seperti masalah pemrograman kuadratik konveks berkendala tidak mudah dilakukan secara analitik. Namun, tidak berarti bahwa masalah tersebut tidak dapat diselesaikan. Salah satu metode yang dapat digunakan untuk menyelesaikannya adalah Metode Himpunan Aktif. Metode himpunan aktif merupakan metode untuk menyelesaikan masalah pemrograman kuadratik konveks yang melibatkan kendala berupa persamaan dan pertidaksamaan. Dalam metode himpunan aktif, yang diselesaikan adalah submasalah pemrograman kuadratik konveks, yakni dengan membangun sebuah himpunan kerja yang terdiri dari kendala-kendala pertidaksamaan aktif. Kendala-kendala pertidaksamaan aktif digunakan karena memiliki nilai nol pada penyelesaiannya sehingga dapat digantikan oleh kendala berupa persamaan, sedangkan kendala pertidaksamaan tidak aktif dapat dihilangkan dari himpunan kerja. Selanjutnya, dicari penyelesaian untuk arah layak. Jika arah layak sama dengan nol dan syarat Karush-Kuhn-Tucker dipenuhi maka akan diperoleh penyelesaian yang merupakan peminimum dari fungsi objektif pada masalah pemrograman kuadratik konveks. Jika tidak, maka perlu dibangun himpunan kerja yang lain dan diselesaikan submasalah baru tersebut. Kelebihan dari metode himpunan aktif, yaitu lebih sederhana perhitungannya karena tidak semua kendala digunakan. Tetapi jika pemilihan titik awal tidak tepat atau dengan kata lain titik awal menyebabkan tidak ditemukannya kendala aktif maka akan dibutuhkan banyak iterasi untuk mencapai hasilnya.

Kata Kunci: himpunan aktif, Karush-Kuhn-Tucker, konveks, pengali Lagrange, arah layak.

viii


ABSTRACT

Determination of the solution of nonlinear programming problems, such as the convex quadratic programming problems that involve constraints is not easy done analitcally. However, it does not mean that the problem can not be completed. One of the methods that can be used to solve this problem is Active Set Methods. Active Set Method is a method to solve the problems of convex quadratic programming with involving constrains in the form of equalities and inequalities. In the Active Set Method, the convex quadratic programming subproblems are solved by first building a working set of active ineqaulity constraints. The active inequality constraints are used because it has zero value on the solution so that it can be replaced by equality constraints, whereas inactive inequality constraints can be removed from a working set. Next, looking for a solution for the feasible direction. If the feasible direction equal to zero and the condition of Karush Kuhn Tucker is satisfied, so it will be obtained a solution that is the minimizer of objective function in the convex quadratic programming problems. If not, it is necessary to build another working set and solved the new subprobems. The advantages of the Active Set Method that is simpler in its computation because not all constraints are used. But if the selection of starting point is not appropriate or in other words, the starting point causes not to find active constraints then it needs much iteration to achieve the results. Keywords: active set, Karush-Kuhn-Tucker, convex, Lagrange multiplier, feasible direction.

ix


KATA PENGANTAR

Puji dan syukur penulis panjatkan ke hadirat Tuhan Yang Maha Esa, karena atas kasih dan penyertaan-Nya sehingga skripsi berjudul “METODE HIMPUNAN

AKTIF

UNTUK

MENYELESAIKAN

MASALAH

PEMROGRAMAN KUADRATIK” dapat penulis selesaikan dengan baik. Skripsi ini disusun sebagai syarat kelulusan guna memperoleh gelar Sarjana Sains di Universitas Sanata Dharma. Dalam penyusunan skripsi ini, tidak terlepas dari bantuan berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin menyampaikan ucapan terimakasih kepada: 1.

Lusia Krismiyati Budiasih, S.Si., M.Si., selaku dosen pembimbing dan Kaprodi Matematika yang telah meluangkan waktu serta penuh kesabaran membimbing dan menuntun penulis dalam penyusunan skripsi ini.

2.

P.H. Prima Rosa, S.Si., M.Sc., selaku Dekan Fakultas Sains dan Teknologi, Universitas Sanata Dharma.

3.

M.V. Any Herawati, S.Si., M.Si., selaku dosen penguji dan dosen pembimbing Angkatan 2008.

4.

Dr. Marcellinus Andy Rudhito, S.Pd., M.Si., selaku dosen penguji.

5.

Prof. Drs. R. Soemantri, Herry Pribawanto, S.Si., M.Si. dan A. Prasetyadi, S.Si., M.Si., yang telah membantu penulis dalam penyusunan skripsi ini.

x


6.

Bapak dan Ibu dosen yang telah memberikan bekal ilmu baik yang berhubungan dengan akademik maupun non akademik.

7.

Staf FST khususnya Pak Tukija, Ibu Linda dan Ibu Rina, Karyawan Perpustakaan USD serta Mas Susilo selaku Laboran .

8.

Almarhum Bapak yang telah tenang di sisi Bapa, Mama dan kedua saudaraku Engel, Ewal serta Ka ima yang selalu mendukung penulis.

9.

Teman-teman seperjuangan (Nooppy, Donat, Amel, Marcell, Fenny, Ethus, Moyo dan Widi). Friendship Never Be A Part guys.

10. Ina dan Adel, anak kos Aulia, Ao, Sende, Novi, Wiwi, Elvira, Tere, Tesa dan Asri, ka Merlin, Pipot serta teman KKN kelompok 31 angkatan XLII. 11. Semua pihak yang tidak dapat disebutkan satu-persatu yang telah mendukung penulis dalam penyusunan skripsi ini. Penulis menyadari bahwa tulisan ini masih sangat jauh dari sempurna. Oleh karena itu kritik dan saran dari berbagai pihak akan penulis terima dengan senang hati. Semoga skripsi ini berguna bagi semua pihak.

Yogyakarta, 29 Februari 2012 Penulis

Yudith Kase

xi


DAFTAR ISI Halaman HALAMAN JUDUL .................................................................................

i

HALAMAN JUDUL DALAM BAHASA INGGRIS ...............................

ii

HALAMAN PERSETUJUAN PEMBIMBING ........................................

iii

HALAMAN PENGESAHAN ....................................................................

iv

PERNYATAAN KEASLIAN KARYA ....................................................

v

HALAMAN PERSEMBAHAN ................................................................

vi

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPENTINGAN AKADEMIS ..................................

vii

ABSTRAK .................................................................................................

viii

ABSTRACT ...............................................................................................

ix

KATA PENGANTAR ...............................................................................

x

DAFTAR ISI ..............................................................................................

xii

DAFTAR GAMBAR .................................................................................

xv

DAFTAR TABEL .......................................................................................

xvi

xii


BAB I PENDAHULUAN ..........................................................................

1

A. Latar Belakang ..................................................................................

1

B. Rumusan Masalah ............................................................................

3

C. Pembatasan Masalah .........................................................................

3

D. Tujuan penulisan ..............................................................................

3

E. Manfaat Penulisan ............................................................................

4

F. Metode Penulisan .............................................................................

4

G. Sistematika Penulisan .......................................................................

4

BAB II RUANG VEKTOR DAN TEORI OPTIMASI .............................

6

A. Ruang Vektor ....................................................................................

6

B. Himpunan Konveks dan fungsi Konveks .........................................

33

C. Teori Optimasi ..................................................................................

60

BAB III METODE HIMPUNAN AKTIF UNTUK MENYELESAIKAN MASALAH PEMROGRAMAN KUADRATIK .......................................

79

A. Pemrograman Kuadratik ...................................................................

79

B. Metode Himpunan Aktif ...................................................................

85

BAB IV PENUTUP ................................................................................... 117 A. Kesimpulan ....................................................................................... 117 B. Saran ................................................................................................. 118 xiii


DAFTAR PUSTAKA ................................................................................ 119 LAMPIRAN ................................................................................................ 120

xiv


DAFTAR GAMBAR Gambar 2.1 Fungsi ‫ݏ‬ሺ‫ݔ‬ሻ = ݂ሺ‫ݔ‬ሻ − ݃ሺ‫ݔ‬ሻ ..................................................

40

Gambar 2.2 Himpunan Konveks dan yang bukan Himpunan Konveks .....

43

Gambar 2.3 Fungsi Konveks dan Bukan Fungsi Konveks ........................

44

Gambar 3.1 Diagram Alir Metode Himpunan Aktif ..................................

95

xv


DAFTAR TABEL Tabel 3.1 Output Penyelesaian contoh 3.3 dengan Matlab ........................ 115 Tabel 3.2 Tabel Perbandingan Nilai Awal Metode Himpunan Aktif......... 115

xvi


BAB I PENDAHULUAN

A. LATAR BELAKANG Optimasi merupakan pokok persoalan yang sering dijumpai dalam kehidupan. Optimasi menyangkut bagaimana menghadapi berbagai macam kemungkinan untuk mencapai hasil yang optimal, contohnya pengoptimalan dalam pemakaian lahan parkir. Dalam pengoptimalan pemakaian lahan parkir terdapat hal-hal yang berpengaruh,

misalnya jenis kendaraan dan jumlah kendaraan.

Permasalahan tersebut dapat dimodelkan secara matematis. Misalkan pengoptimalan pemakaian lahan parkir dinyatakan dengan fungsi f. Hal-hal yang mempengaruhi dinyatakan dengan variabel misalnya ‫ݔ‬1 , ‫ݔ‬2 , … , ‫ ݊ݔ‬. Variabel-variabel tersebut perlu diberi batasan yang disebut sebagai kendala sedangkan fungsi ݂ሺ‫ݔ‬ଵ , ‫ݔ‬ଶ , … , ‫ݔ‬௡ ሻ disebut fungsi objektif. Fungsi objektif yang sering dijumpai adalah berbentuk linear. Namun dengan adanya perkembangan muncul faktor-faktor yang menyebabkan ketidaklinearan suatu fungsi sehingga memicu munculnya permasalahan nonlinear. Permasalahan nonlinear merupakan masalah untuk mengoptimumkan fungsi objektif terhadap himpunan variabel real, di mana salah satu atau keduanya dari fungsi objektif dan kendala berbentuk nonlinear. Dalam permasalahan nonlinear, fungsi objektif dioptimalkan dengan melibatkan


2

kendala. Namun, pada masalah-masalah lainnya fungsi objektif dapat pula dioptimalkan walaupun tidak melibatkan kendala. Pemrograman kuadratik merupakan salah satu dari masalah pemrograman nonlinear yang melibatkan kendala. Masalah pemrograman kuadratik merupakan masalah optimasi nonlinear dengan fungsi objektif berbentuk kuadratik dan kendalanya berbentuk linear. Jika fungsi objektif merupakan fungsi konveks maka dikatakan masalah pemrograman kuadratik konveks. Untuk menyelesaikan masalah pemrograman kuadratik, khususnya pemrograman kuadratik konveks dapat digunakan beberapa metode, antara lain Metode Titik Dalam, Metode Dual dan Metode Himpunan Aktif. Dalam penulisan ini akan dipaparkan tentang Metode Himpunan Aktif. Metode himpunan aktif adalah metode untuk menyelesaikan masalah pemrograman kuadratik dengan kendala berupa persamaan yang dapat digeneralisasikan untuk menyelesaikan masalah pemrograman kuadratik dengan kendala yang bersifat umum. Dengan kata lain metode himpunan aktif dapat digunakan untuk menyelesaikan masalah pemrograman kuadratik yang melibatkan kendala berupa persamaan dan pertidaksamaan. Secara intuitif dalam metode himpunan aktif, kendala pertidaksamaan yang tidak aktif tidak berperan dalam pencapaian penyelesaian, sehingga dapat dihilangkan. Dalam metode himpunan aktif, dibangun sebuah subhimpunan dari kendala berupa persamaan yang diberi indeks dengan suatu himpunan kerja. Salah satu syarat optimal untuk optimasi berkendala adalah syarat Karush-Kuhn-


3

Tucker. Jika penyelesaian dari submasalah pemrograman kuadratik dengan kendala persamaan dalam himpunan kerja adalah layak untuk masalah pemrograman kuadratik semula dan syarat Karush-Kuhn-Tucker dipenuhi maka akan diperoleh penyelesaiannya. Jika syarat Karush-Kuhn-Tucker tidak dipenuhi maka himpunan kerja tersebut dihilangkan dan diselesaikan submasalah baru.

B. RUMUSAN MASALAH Pokok-pokok permasalahan yang akan dibahas dalam tulisan ini yaitu: 1.

Bagaimana menyelesaikan masalah pemrograman kuadratik dengan metode himpunan aktif?

2.

Bagaimana algoritma metode himpunan aktif dan implementasinya dalam MATLAB untuk menyelesaikan masalah pemrograman kuadratik?

C. PEMBATASAN MASALAH Pembahasan metode himpunan aktif dalam tulisan ini hanya dibatasi pada masalah pemrograman kuadratik konveks dan pada masalah optimasi yang melibatkan kendala.

D. TUJUAN PENULISAN Tujuan penulisan ini yaitu untuk menyelesaikan masalah pemrograman kuadratik yang melibatkan kendala dengan menggunakan metode himpunan aktif


4

dan untuk menyusun algoritma metode himpunan aktif dengan menggunakan bahasa pemrograman MATLAB.

E. MANFAAT PENULISAN Manfaat dari tulisan ini yaitu untuk memperoleh pengetahuan tentang metode himpunan aktif yang digunakan untuk menyelesaikan masalah pemrograman kuadratik yang melibatkan kendala serta dapat menggunakan bahasa pemrograman MATLAB untuk menyelesaikan masalah pemrograman kuadratik.

F. METODE PENULISAN Metode yang digunakan penulis adalah metode studi pustaka yaitu dengan mempelajari buku-buku yang berkaitan dengan metode himpunan aktif untuk menyelesaikan masalah pemrograman kuadratik.

G. SISTEMATIKA PENULISAN BAB I PENDAHULUAN A. Latar Belakang B. Perumusan Masalah C. Pembatasan Masalah D. Tujuan Penulisan E.

Manfaat Penulisan

F.

Metode Penulisan


5

G. Sistematika Penulisan

BAB II RUANG VEKTOR DAN TEORI OPTIMASI A. Ruang Vektor B. Himpunan Konveks dan Fungsi Konveks C. Teori Optimasi

BAB III METODE HIMPUNAN AKTIF UNTUK MENYELESAIKAN MASALAH PEMROGRAMAN KUADRATIK A. Pemrograman Kuadratik B. Metode Himpunan Aktif

BAB IV PENUTUP A. Kesimpulan B. Saran


BAB II RUANG VEKTOR DAN TEORI OPTIMASI

Dalam Bab II ini akan dibahas tentang ruang vektor, matriks, himpunan dan fungsi konveks serta teori optimasi. Matriks yang akan dibahas, yaitu matriks Hesse dan matriks semidefinit positif. Untuk teori optimasi diawali dengan penjelasan optimasi berkendala dan optimasi tidak berkendala serta penjelasan-penjelasan lain yang berkaitan dengan teori optimasi.

A. Ruang Vektor Definisi 2.1 Ruang ℝ adalah himpunan dari semua kumpulan terurut , , ⋯ , .

Definisi 2.2 Misalkan himpunan tak kosong yang dilengkapi dengan operasi

1. Jumlah: untuk setiap , ∈ , + ∈ .

2. Perkalian skalar: untuk setiap ∈ dan skalar ∈ ℝ, ∈ .

Himpunan dengan operasi penjumlahan dan perkalian skalar dikatakan membentuk suatu ruang vektor atas ℝ jika memenuhi aksioma-aksioma berikut:

a. + = + , untuk setiap , ∈ .

b. + + = + + , untuk setiap , , ∈ .


7

c. Terdapat elemen ∈ sehingga + = , untuk setiap ∈ .

d. Untuk setiap ∈ terdapat elemen – ∈ sehingga + – = 0.

e. + = + , untuk setiap skalar ∈ ℝ dan untuk setiap , ∈ .

f. ( + = + , untuk setiap skalar , ∈ ℝ dan untuk setiap ∈ . g. ( = , untuk setiap skalar , ∈ ℝ dan untuk setiap ∈ . h. 1 = , untuk setiap ∈ .

Contoh 2.1 Buktikan bahwa ℝ = , , ⋯ , | ∈ ℝ, ∈ ℝ, ⋯ , ∈ ℝ adalah ruang vektor.

Bukti Misalkan = , , ⋯ , dan = , , ⋯ , , maka + = + , + , ⋯ , + = , , ⋯ ,

a. + = + , + , ⋯ , +

= + , + , ⋯ , + = +

b. + + = + , + , ⋯ , + + , , ⋯ ,


= , , ⋯ , + , , ⋯ , + , , ⋯ , = , , ⋯ , + , , ⋯ , + , , ⋯ ,

= , , ⋯ , + , , ⋯ , + , , ⋯ , = , , ⋯ , + + , + , ⋯ , + = + +

c. + = , , ⋯ , + 0,0, ⋯ ,0 = + 0, + 0, ⋯ , + 0 = , , ⋯ , =

d. + − = , , ⋯ , + − , − , ⋯ , −

= + − , + − , ⋯ , + − = 0,0, ⋯ ,0 =

e. + = + , + , ⋯ , +

= , , ⋯ , + , , ⋯ , = , , ⋯ , + , , ⋯ , = +

8


9

f. + = + , , ⋯ ,

= + , + , ⋯ , +

= + , + , ⋯ , +

= , , ⋯ , + , , ⋯ , = , , ⋯ , + , , ⋯ , = +

g. = , , ⋯ ,

= , , ⋯ ,

= , , ⋯ , = , , ⋯ , =

h. 1 = 1 , , ⋯ ,

= 1 , 1 , ⋯ , 1 = , , ⋯ , =

Karena ℝ = , , ⋯ , | ∈ ℝ, ∈ ℝ, ⋯ , ∈ ℝ dengan operasi penjumlahan dan perkalian skalar memenuhi aksioma-aksioma seperti pada Definisi 2.2 maka terbukti bahwa ℝ membentuk ruang vektor.


10

Definisi 2.3 Misalkan ! = banyaknya baris pada matriks " dan # = banyaknya kolom pada

matriks " maka matriks " dikatakan bujur sangkar jika ! = #.

Definisi 2.4 Suatu matriks bujur sangkar " dikatakan simetrik jika " = " $ dengan " $ ada-

lah transpose dari ".

Definisi 2.5 Misalkan " ∈ ℝ× adalah matriks simetrik.

" dikatakan definit positif jika $ " > 0, ∀ ∈ ℝ , ≠ . " dikatakan semidefinit positif jika ) " ≥ 0, ∀ ∈ ℝ .

" dikatakan semidefinit negatif jika $ " ≤ 0, ∀ ∈ ℝ , ≠ 0.

" dikatakan indefinit jika tidak semidefinit positif atau semidefinit negatif.

Contoh 2.2 Diberikan sebuah matriks simetrik berikut: "=,

4 −2 0 −2 3

Untuk mengkaji bahwa matriks " bersifat definit positif, maka: $ " = 1

2 , 4 −20 , 0 −2 3


= 1

11

2 3 4 − 2 4 −2 + 3

= 4 − 2 − 2 + 3 = 4 − 4 + 3 = 2 − + 2

2.1

Persamaan (2.1) adalah penjumlahan kuadrat dan oleh karena itu hasilnya tidak negatif. Persamaan (2.1) akan bernilai nol jika dan hanya jika 2 − = 0 dan

= 0, yang secara tidak langsung menyatakan pula bahwa = 0. Hal ini

membuktikan bahwa $ " > 0 untuk semua ≠ 0. Jadi, dapat disimpulkan

bahwa matriks " bersifat definit positif.

Contoh 2.3 Diberikan sebuah matriks simetrik berikut: 2 "=, 0

0 0 2

Untuk mengkaji bahwa matriks " bersifat semidefinit positif, maka: $ " = 1 = 1

2 ,2 00 , 0 0 2

2 32 4 2

= 2 + 22

Berdasarkan hasil di atas, dapat disimpulkan bahwa matriks " bersifat semidefi-

nit positif karena ∀ ∈ ℝ jumlahan kuadrat di atas ≥ 0.


12

Contoh 2.4 Diberikan sebuah matriks simetrik berikut: 3 0 3 " = 60 3 0 7 3 0 3

Untuk mengkaji bahwa matriks " bersifat semidefinit positif, maka: " = 1 $

= 1

3 8 2 60 3

0 3 3 07 6 7 0 3 8

3 + 0 + 38 8 2 60 + 3 + 08 7 3 + 0 + 38

= 3 + 0 + 38 + 0 + 3 + 08 + 8 3 + 0 + 38 = 3 + 3 8 + 3 + 3 8 + 38 = 3 + 2 8 + 8 + 3 = 3 + 8 + 3

Berdasarkan hasil di atas, dapat disimpulkan bahwa matriks " bersifat semidefinit positif karena ∀ ∈ ℝ jumlahan kuadrat di atas ≥ 0.

Definisi 2.6 Diberikan titik ∈ ℝ dan 9 > 0.

Kitar titik dengan radius 9 yang diberi notasi :; didefinisikan dengan :; = ∈ ℝ |‖ − ‖ < 9


13

Definisi 2.7 Barisan di ℝ dikatakan konvergen ke ∈ ℝ, atau dikatakan titik limit da-

ri , jika untuk setiap > > 0 ada bilangan asli ?> sehingga untuk semua

# ≥ ?> , barisan memenuhi | − | < >.

Definisi 2.8 Jika barisan mempunyai limit, maka barisan tersebut dikatakan konvergen. Jika barisan tidak mempunyai limit, maka barisan tersebut dikatakan divergen.

Definisi 2.9 Misalkan @ ⊂ ℝ dan ∈ ℝ.

Titik dinamakan titik interior dari @ jika terdapat 9 > 0 sehingga :; ⊂ @.

Definisi 2.10 Himpunan @ dikatakan terbuka dalam ℝ jika setiap titik dari @ adalah titik in-

terior @.

Definisi 2.11 Himpunan @ ⊂ ℝ adalah tertutup jika dan hanya jika komplemennya adalah terbuka.


14

Definisi 2.12 Misalkan ∈ ℝ dan misalkan B: ℝ ⟶ ℝ merupakan fungsi bernilai real yang

mempunyai turunan parsial orde ke-2 dalam himpunan terbuka E yang memuat

. Matriks Hesse dari B adalah matriks turunan parsial ke-2 yang dievaluasi pada :

 ∂2 f  2  ∂x1  ∂2 f H (x) =  ∂x ∂x  2 1  M  ∂2 f  ∂x ∂x  n 1

∂2 f ∂x1∂x2 ∂2 f ∂x 22 M 2 ∂ f ∂xn ∂x 2

L L O L

∂2 f ∂x1∂xn ∂2 f ∂x2 ∂xn M 2 ∂ f ∂xn2

         

Definisi 2.13 Himpunan vektor F , … , F di ruang vektor V disebut bebas linear jika persamaan H F + … + HI F =

Hanya dipenuhi oleh bilangan H = ⋯ = HI = 0.

Contoh 2.5 Diketahui F = 1,0,1 , F = 2, −3,4 dan F8 = 3,5,2 . Buktikan bahwa F , F , F8 bebas linear.


15

Bukti Untuk membuktikan bahwa kumpulan tersebut bebas linear maka dibentuk persamaan berikut H F + H F + H8 F8 = H + 2H + 3H8 = 0 K −3H + 5H8 = 0 H + 4H + 2H8 = 0

Selanjutnya, akan digunakan operasi baris elementer untuk mencari nilai dari H , H dan H8 .

1 60 1

2 3 −3 57 4 2

Tambahkan -1 kali baris pertama ke baris ketiga untuk memperoleh 1 2 60 −3 0 2

3 57 −1

Tambahkan 2 kali baris kedua ke 3 dikali baris ketiga untuk memperoleh

•

7H8 = 0 H8 = 0

•

−3H + 5H8 = 0 −3H = 0 H = 0

•

H + 2H + 3H8 = 0

1 60 0

2 3 −3 57 0 7


16

H = 0

Kerana H = H = H8 = 0 maka dapat disimpulkan bahwa kumpulan vektor

F , F , F8 bebas linear.

□

Definisi 2.14 Hasil kali dalam (inner product) ℝ adalah sebuah fungsi yang mengasosiasikan

sebuah bilangan real 〈, 〉 dengan sepasang vektor dan di ℝ sedemikian ru-

pa sehingga aksioma-aksioma berikut ini terpenuhi bagi semua vektor , dan

di ℝ dan semua bilangan skalar H ∈ ℝ. 1. 〈, 〉 = 〈 , 〉;

(Aksioma Kesimetrian)

2. 〈 + , 〉 = 〈, 〉 + 〈 , 〉;

(Aksioma Penjumlahan)

3. 〈H, 〉 = H〈, 〉;

(Aksioma Homogenitas)

4. 〈, 〉 ≥ 0;

(Aksioma Positivitas)

〈, 〉 = 0 jika dan hanya jika = 0;

Sebuah ruang vektor real yang memiliki sebuah hasil kali dalam disebut ruang hasil kali dalam real (Real Inner Product Space).

Definisi 2.15 Hasil kali dalam baku untuk ℝ adalah hasil kali skalar 〈, 〉 = $


17

Definisi 2.16 Norma (norm) atau panjang sebuah vektor di ℝ , dinotasikan dengan ‖‖, didefinisikan sebagai ‖‖ = 〈, 〉

P

= ∙

P

= R + + ⋯ +

Definisi 2.17 Dua vektor dan pada ℝ dikatakan ortogonal jika 〈, 〉 = 0.

Teorema 2.18 (Teorema Pythagoras) Jika dan adalah vektor-vektor ortogonal di dalam sebuah ruang hasil kali da-

lam ℝ , maka

‖ + ‖ = ‖‖ + ‖ ‖

Bukti ‖ + ‖ = 〈 + , + 〉

= 〈, 〉 + 〈, 〉 + 〈 , 〉 + 〈 , 〉

= 〈, 〉 + 〈, 〉 + 〈, 〉 + 〈 , 〉 = ‖‖ + 2〈, 〉 + ‖ ‖ = ‖‖ + ‖ ‖

□


18

Definisi 2.19 Jika dan adalah vektor-vektor ortogonal di dalam ruang hasil kali dalam di ℝ

dan ≠ , maka proyeksi skalar dari pada diberikan oleh =

〈, 〉 ‖ ‖

2.2

dan proyeksi vektor dari pada diberikan oleh

〈, 〉 1 T = U V = ‖ ‖ 〈 , 〉

Teorema 2.20 Jika ≠ , dan T adalah proyeksi vektor dari pada , maka

1. − T dan T adalah ortogonal.

2. = T jika dan hanya jika adalah sebuah perkalian skalar dari .

Bukti 1. Karena 〈T, T〉 = 〈

α α , 〉 ‖ ‖ ‖ ‖

=U

α V 〈 , 〉 ‖ ‖

= α dan

2.3


〈, T〉 =

〈, 〉 〈 , 〉

= Hal ini mengakibatkan

〈 − T, T〉 = 〈, T〉 − 〈T, T〉 = − =0

□

2. Jika = , maka proyeksi vektor dari pada diberikan oleh T=

〈 , 〉 〈 , 〉

=

〈 , 〉 〈 , 〉

= =

Sebaliknya, jika = T, menurut persamaan (2.3) maka = =

‖ ‖

=T

□

Teorema 2.21 (Ketaksamaan Cauchy-Schwarz dalam ℝ )

Jika dan adalah vektor-vektor di dalam ruang hasil kali dalam ℝ , maka |〈, 〉| ≤ ‖‖‖ ‖

19


20

Bukti Jika = , maka

|〈, 〉| = 0 = ‖‖‖ ‖

Jika ≠ , maka misalkan T sebagai proyeksi vektor dari pada . Karena T or-

togonal pada − T, maka menurut Teorema Pythagoras ‖T‖ + ‖ − T‖ = ‖‖

Jadi, 〈, 〉 = ‖T‖ ‖ ‖

= ‖‖ − ‖ − T‖

dan dari sini diperoleh 〈, 〉 = ‖‖ ‖ ‖ − ‖ − T‖ ‖ ‖ ≤ ‖‖ ‖ ‖

Dengan mengambil akar diperoleh |〈, 〉| ≤ ‖‖‖ ‖

□

Teorema 2.22 (Ketaksamaan Cauchy-Buniakowski-Schwarz) Misalkan , ∈ ℝ . Maka

XY Z Z X ≤ ‖‖ ‖ ‖ Z[

2.4


21

Bukti Pertidaksamaan (2.4) akan bersifat trivial jika dan hanya jika = atau = . Oleh karena itu, misalkan dan tak nol. Misalkan \ adalah sebarang bilangan

real. Maka

0 ≤ ‖ + \ ‖ = YZ + \Z Z[

=

Y Z Z[

=

‖‖

+ 2\ Y Z Z + \ Y Z Z[

Z[

+ 2\ Y Z Z + \ ‖ ‖ Z[

Misalkan ] = ‖ ‖ , ^ = ∑Z[ Z Z , dan ` = ‖‖ , sehingga pertidaksamaan di atas menjadi ]\ + 2^\ + ` ≥ 0

untuk semua \ ∈ ℝ. Hal ini dapat terjadi jika dan hanya jika diskriminan atau

@ = 2^ − 4]` = 4^ − 4]` < 0. Karena itu, ^ < ]`.

Dengan mensubstitusikan nilai ], ^ dan `, maka diperoleh

aY Z Z b ≤ ‖‖ ‖ ‖ Z[

Selanjutnya dengan mengambil akar diperoleh

XY Z Z X ≤ ‖‖ ‖ ‖ Z[

□


22

Definisi 2.23 Pemetaan ‖∙‖ disebut norm jika dan hanya jika memenuhi sifat-sifat berikut: 1. ‖‖ ≥ 0, ∀ ∈ ℝ .

2. ‖‖ = 0 jika dan hanya jika = 0. 3. ‖]‖ = ||‖‖, ∀ ∈ ℝ, ∈ ℝ .

4. ‖ + ‖ ≤ ‖‖ + ‖ ‖, ∀, ∈ ℝ .

Contoh 2.6 Akan dibuktikan bahwa ‖‖ = ∑Z[|Z | adalah norm.

Bukti Untuk membuktikan bahwa ‖‖ = ∑Z[|Z | adalah norm, maka harus ditunjuk-

kan bahwa ‖‖ = ∑Z[|Z | memenuhi masing-masing sifat dari Definisi 2.23.

Misalkan dan adalah sebarang vektor di ℝ , # dan adalah sebarang bilangan real, maka 1. Akan ditunjukkan bahwa ‖‖ ≥ 0. Untuk Z ≥ 0, maka

‖‖ = Y|Z | ≥ 0 Z[

2. Akan ditunjukkan bahwa ‖‖ = ∑Z[|Z | = 0 jika dan hanya jika = 0. Jika = 0 maka Z = 0, ∀c.


23

Oleh karena itu, ∑Z[|Z | = 0 dan ‖‖ = 0.

Sebaliknya, jika ‖‖ = 0 maka ∑Z[|Z | = 0.

Karena |Z | ≥ 0, dengan demikian ∑Z[|Z | = 0 hanya dipenuhi jika |Z | = 0

sehingga = 0.

3. Akan ditunjukkan bahwa ‖]‖ = ||‖‖ , ∀ ∈ ℝ, ∈ ℝ .

‖‖ = Y|Z | Z[

= || aY|Z |b Z[

= ||‖‖

4. Akan ditunjukkan bahwa ‖ + ‖ ≤ ‖‖ + ‖ ‖ , ∀, ∈ ℝ .

‖ + ‖ = Y|Z + Z | Z[

Z[

Z[

≤ Y|Z | + Y|Z | = ‖‖ + ‖ ‖

(Ketaksamaan Cauchy-Schwarz)

Jadi, ‖ + ‖ ≤ ‖‖ + ‖ ‖

□

Contoh 2.7 Akan dibuktikan bahwa ‖‖ = ∑Z[ Z ⁄ adalah norm.


24

Bukti Untuk membuktikan bahwa ‖‖ = ∑Z[ Z ⁄ adalah norm, maka harus di-

tunjukkan bahwa ‖‖ = ∑Z[ Z ⁄ memenuhi masing-masing sifat dari Definisi 2.23. Misalkan dan adalah sebarang vektor di ℝ , # dan adalah sebarang bilangan real, maka 1. Akan ditunjukkan bahwa ‖‖ ≥ 0.

Karena Z ≥ 0 untuk sebarang bilangan real Z , maka

‖‖ = aY Z b

⁄

Z[

≥0

2. Akan ditunjukkan bahwa ‖‖ = ∑Z[|Z | ⁄ = 0 jika dan hanya jika = 0.

Jika = 0 maka Z = 0, ∀c.

Oleh karena itu, ∑Z[ Z = 0 dan ‖‖ = 0.

Sebaliknya, jika ‖‖ = 0 maka ∑Z[ Z = 0.

Karena Z ≥ 0, dengan demikian ∑Z[ Z Z = 0 sehingga = 0.

P

= 0 hanya dipenuhi jika

3. Akan ditunjukkan bahwa ‖]‖ = ||‖‖ , ∀ ∈ ℝ, ∈ ℝ .

‖‖ = aYZ b Z[

P


= a Y Z b

P

Z[

= || aY Z b

P

Z[

= ||‖‖

4. Akan ditunjukkan bahwa ‖ + ‖ ≤ ‖‖ + ‖ ‖ , ∀, ∈ ℝ . ‖ +

‖

= YZ + Z Z[

=

Y Z Z[

Z[

Z[

+ 2 Y Z Z + Y Z

≤ ‖‖ + 2|∑Z[ Z Z | + ‖ ‖ ≤ ‖‖ + 2‖‖ ‖ ‖ + ‖ ‖

(Sifat Nilai Mutlak) (Teorema 2.22)

= ‖‖ + ‖ ‖

Dengan mengambil akar maka diperoleh ‖ + ‖ ≤ ‖‖ + ‖ ‖

Teorema 2.24 Misalkan , , adalah sebarang vektor di ℝ , dengan

‖‖ = aY Z b Z[

maka berlaku

⁄

□

25


26

1. ‖ − ‖ ≥ 0.

2. ‖ − ‖ = 0 jika dan hanya jika = .

3. ‖ − ‖ ≤ ‖ − ‖ + ‖ − ‖. 4. ‖ − ‖ = ‖ − ‖.

Bukti 1. Akan dibuktikan bahwa ‖ − ‖ ≥ 0.

‖ − ‖ = aYZ − Z b

P

Z[

Karena Z − Z ≥ 0 untuk sebarang bilangan real Z dan Z maka dipero-

leh ‖ − ‖ ≥ 0.

□

2. Akan dibuktikan bahwa ‖ − ‖ = 0 jika dan hanya jika = . Jika = maka Z = Z , ∀c.

Oleh karena itu ∑Z[Z − Z = 0 dan ‖ − ‖ = 0.

Sebaliknya, jika ‖ − ‖ = 0, maka ∑Z[Z − Z = 0.

Karena Z − Z ≥ 0, dengan demikian ∑Z[Z − Z = 0 hanya dipenuhi

jika Z − Z = 0, ∀c sehingga = .

□

3. Akan dibuktikan bahwa ‖ − ‖ ≤ ‖ − ‖ + ‖ − ‖. ‖ − ‖ = ‖ − + − ‖

= 〈 − + − , − + − 〉

= 〈 − , − 〉 + 〈 − , − 〉 + 〈 − , − 〉 + 〈 − , − 〉


27

= ‖ − ‖ + 〈 − , − 〉 + 〈 − , − 〉 + ‖ − ‖ = ‖ − ‖ + 2〈 − , − 〉 + ‖ − ‖

≤ ‖ − ‖ + 2‖ − ‖‖ − ‖ + ‖ − ‖ = ‖ − ‖ + ‖ − ‖

Dengan mengambil akar maka diperoleh ‖ − ‖ ≤ ‖ − ‖ + ‖ − ‖.

□

4. Akan dibuktikan bahwa ‖ − ‖ = ‖ − ‖.

‖ − ‖ = ‖−1 − ‖ = |1|‖ − ‖ = ‖ − ‖

Jadi, terbukti bahwa ‖ − ‖ = ‖ − ‖.

□

Teorema 2.25 (Hukum Paralelogram) Untuk semua , ∈ ℝ ,

‖ + ‖ + ‖ − ‖ = 2‖‖ + ‖ ‖

Bukti: ‖ + ‖ + ‖ − ‖ = 〈 + , + 〉 + 〈 − , − 〉

= 〈, + 〉 + 〈 , + 〉 + 〈, − 〉 − 〈 , − 〉

= 〈, 〉 + 〈, 〉 + 〈 , 〉 + 〈 , 〉 + 〈, 〉 − 〈, 〉 − 〈 , 〉 +〈 , 〉


28

= 〈, 〉 + 〈 , 〉 + 〈, 〉 + 〈 , 〉 = 2〈, 〉 + 2〈 , 〉 = 2‖‖ + 2‖ ‖

= 2‖‖ + ‖ ‖

□

Definisi 2.26 Barisan I ⊂ ℝ disebut barisan Cauchy jika

lim ‖ h − i ‖ = 0

h,i⟶j

Dengan kata lain untuk setiap k > 0, terdapat sebuah bilangan bulat : sehingga ‖ h − i ‖ < k untuk semua !, l > :.

Definisi 2.27 Misalkan m adalah sebuah relasi pada himpunan n, maka m disebut relasi urutan parsial jika memenuhi tiga sifat berikut: 1. Refleksif m adalah fefleksif jika dan hanya jika ] m ] untuk setiap ] ∈ n. 2. Antisimetris m adalah antisimetris jika dan hanya jika ] m ^ dan ^ m ], maka ] = ^ untuk setiap ], ^ ∈ n.

3. Transitif


29

m adalah transitif jika dan hanya jika ] m ^ dan ^ m `, maka ] m ` untuk setiap ], ^, ` ∈ n.

Relasi urutan parsial biasanya dinotasikan dengan ≤; dan ] ≤ ^ dibaca “] men-

dahului ^”. Relasi ≥, yaitu ] melampaui ^, juga sebuah urutan parsial dari n,

disebut urutan dual.

Definisi 2.28 Himpunan n bersama-sama dengan suatu relasi urutan parsial m pada n disebut himpunan terurut parsial (partially ordered set).

Contoh 2.8 Perhatikan bilangan bulat positif ℕ. Dikatakan ] membagi ^ ditulis ]|^, jika ter-

dapat ` ∈ ℕ sedemikian sehingga ]` = ^. Contoh 2|4, 3|12, 7|21 dan seterusnya. Tunjukkan bahwa pembagian adalah sebuah pengurutan parsial dari ℕ, yaitu, tunjukkan bahwa a. ]|].

b. Jika ]|^ dan ^|] maka ] = ^. c. Jika ]|] dan ^|` maka ]|`. Penyelesaian

a. Karena ] ∙ 1 = ], maka ]|]. (Refleksif).


30

b. Anggap ]|^ dan ^|], misal ^ = p] dan ] = H^. Maka ^ = pH^ sehingga pH = 1. Karena p dan H adalah bilangan bulat positif maka p = 1 dan H = 1.

Dengan demikian ] = ^. (Antisimetris).

c. Anggap ]|^ dan ^|`, misal ^ = p] dan ` = H^. Maka ` = Hp] sehingga ]|`. (Transitif).

Definisi 2.29

Misalkan q adalah subhimpunan dari sebuah himpunan n yang terurut secara parsial. Definisikan:

a. Batas atas dan supremum dari q.

Elemen r dalam n disebut batas atas dari q jika r melampaui (≥) setiap

elemen dari q, yaitu r adalah batas atas dari q jika ∀ ∈ q, ≤ r. Jika suatu batas atas dari q mendahului (≤) setiap batas atas lain dari q maka disebut

batas atas terkecil atau supremum dari q dan dinyatakan dengan: b. Batas bawah dan infimum dari q.

sup(q)

Elemen ! dalam n disebut batas bawah dari q jika ! mendahului (≤) setiap

elemen dari q, yaitu ! adalah batas bawah dari q jika ∀ ∈ q, ! ≤ . Jika

suatu batas atas dari q melampaui (≥) setiap batas bawah lain dari q maka disebut batas bawah terbesar atau infimum dari q dan dinyatakan dengan: inf(q)


31

Definisi 2.30

Misalkan n merupakan subhimpunan tak kosong dari ℝ.

a. Himpunan n dikatakan terbatas ke atas jika ada bilangan x ∈ ℝ sedemikian

sehingga H ≤ x untuk semua H ∈ n. Setiap bilangan x dikatakan batas atas dari n.

b. Himpunan n dikatakan terbatas ke bawah jika ada bilangan y ∈ ℝ sedemi-

kian sehingga y ≤ H untuk semua H ∈ n. Setiap bilangan y dikatakan batas bawah dari n.

Lemma 2.31

Batas bawah l dari himpunan tak kosong n di ℝ adalah infimum dari n jika dan

hanya jika ∀> > 0 terdapat ∈ n sedemikian sehingga l + > > . Bukti (⟹)

Diketahui l = inf n dan > > 0.

Akan ditunjukkan terdapat ∈ n sedemikian sehingga l + > > .

Jika ^ batas bawah n maka ^ ≤ l.

Karena l + > > l maka l + > bukan batas bawah n.

Karena l + > bukan batas bawah n maka harus ada ∈ n sehingga l + > > .


32

(⟸)

Jika l suatu batas bawah n, dan ∀> > 0 terdapat ∈ n sedemikian sehingga l + > > .

Akan dibuktikan l = inf n.

Misalkan bahwa ^ suatu batas bawah n. Karena ∈ n dan ^ suatu batas bawah n maka ≥ ^.

Karena l + > > maka l + > > ^.

Jadi ∀> > 0 berlaku l + > > ^. Andaikan ^ > l maka jika diambil > =

diperoleh l + > =

i~|

|}i

akan

sehingga ^ > l + > > l dan ^ > l + > > yang kontra-

diksi dengan pernyataan bahwa ^ batas bawah. Jadi, jika ^ batas bawah n harus-

lah l ≥ ^ sehingga l merupakan batas bawah terbesar atau l = inf n.

□

Definisi 2.32

Misalkan = merupakan barisan bilangan real. Barisan dikatakan naik jika memenuhi pertidaksamaan ≤ ≤ ⋯ ≤ ≤ ~ ≤ ⋯ dan dikatakan turun jika memenuhi pertidaksamaan ≥ ≥ ⋯ ≥ ≥ ~ ≥ ⋯

Jika barisan merupakan barisan naik atau barisan turun maka merupakan barisan monoton.


33

Teorema 2.33 Barisan turun dan terbatas ke bawah adalah konvergen.

Bukti:

Diberikan turun dan terbatas ke bawah. Karena : # ∈ ℕ ≠ ∅ maka ter-

dapat ^ ∈ ℝ dan ^ = inf : # ∈ ℕ. Jadi, untuk setiap # ∈ ℕ berlaku ≥ ^

(2.5)

Karena ^ = inf : # ∈ ℕ, maka untuk > > 0 yang diberikan terdapat : ∈ ℕ dan

^ − > > ≥ ^

(2.6)

Karena turun, maka mengingat (2.5) dan (2.6), untuk setiap # ≥ : berlaku ^ − > > ≥ ≥ ^ > ^ + >

(2.7)

Jadi, diperoleh pernyataan bahwa untuk setiap > > 0 terdapat : ∈ ℕ sedemikian

sehingga untuk setiap # ≥ ℕ dan # ≥ :, maka | − ^| < >. Jadi, konver-

gen dan lim = ^ = inf : # ∈ ℕ.

□

B. Himpunan Konveks dan Fungsi Konveks Definisi 2.34

Sebuah Fungsi B: ℝ → ℝ dikatakan kontinu pada ∈ ℝ jika untuk setiap

k > 0 yang diberikan, terdapat 9 > 0 sedemikian sehingga jika ‖ − ‖ < 9 ma-

ka |B − B | < k.


34

Definisi 2.35

Limit B() untuk mendekati ` adalah , ditulis

lim f ( x) = L x →c

jika dan hanya jika untuk setiap > > 0 yang diberikan, terdapat 9 > 0 sedemi-

kian sehingga bila 0 < | − `| < 9 berlaku |B − | < >. Teorema 2.36

Misalkan adalah konstanta, B dan adalah fungsi-fungsi yang memiliki limit di `. Maka

1. lim k = k ; x →c

2. lim kf ( x) = k lim f ( x) ; x →c

x →c

3. lim[ f ( x) + g ( x)] = lim f ( x) + lim g ( x) = K + L ; x →c

x →c

x →c

4. lim[ f ( x) − g ( x)] = lim f ( x) − lim g ( x) = K − L ; x →c

x →c

x →c

Bukti: 1. Misalkan didefinisikan B = maka harus dibuktikan lim f ( x) = k . x →c

Misalkan > > 0, harus ditunjukkan bahwa dapat dicari 9 > 0 sedemikian sehingga |B − | < > bila 0 < | − `| < 9


35

Ambil sebarang 9 > 0 maka untuk 0 < | − `| < 9 berlaku |B − | = | − | = 0 < >

Jadi terbukti bahwa lim k = k

□

x →c

2. Jika = 0 maka B() = 0, maka

lim[0 f ( x)] = lim 0 = 0 = 0 f ( x) x →c

x →c

Limit di atas adalah kasus khusus dari rumus 1, dengan = 0. Oleh karena

itu, rumus 1 adalah benar untuk = 0.

Asumsikan bahwa ≠ 0.

Misalkan > > 0, lim f ( x) = K maka melalui definisi limit ada 91 > 0 sedemix →c

kian sehingga bila 0 < | − `| < 9 berlaku |B − | < || >

Pilih 9 = 91 dan harus ditunjukkan bahwa

bila 0 < | − `| < 9 berlaku |B − ?| < >

Misalkan 0 < | − `| < 9, maka

|B − ?| = |||B − ?|

< || =>

Jadi, terbukti bahwa lim kf ( x) = k lim f ( x) x →c

x →c

> ||

□


36

3. Misalkan > > 0, lim f ( x) = K dan lim g ( x) = L maka ada 91 > 0 dan 92 > 0 x →c

x →c

sedemikian sehingga |B − ?| < | − | <

> 2

> 2

bila 0 < | − `| < 9 dan

bila 0 < | − `| < 9

Pilih 9 = min9 , 9 . Harus ditunjukkan bahwa

bila 0 < | − `| < 9 berlaku |B + − ? + |

Misalkan bahwa 0 < | − `| < 9, maka

|B + − ? + | = |B − ? + − |

≤ |B − ?| + | − | <

> > + 2 2

=>

Jadi terbukti bahwa lim[ f ( x) + g ( x)] = lim f ( x) + lim g ( x) = K + L x →c

x →c

x →c

□

4. Untuk membuktikan rumus 4, akan digunakan informasi dari rumus-rumus sebelumnya.

lim[ f ( x) − g ( x)] = lim[ f ( x) + (−1) g ( x)] x→c

x→c

(melalui rumus 3)

= lim f ( x) + lim(−1) g ( x)

(melalui rumus 3)

= lim f ( x) + (−1) lim g ( x)

(melalui rumus 2)

x→c

x →c

x→c

x →c

= lim f ( x) − lim g ( x) x→c

=K −L

x→c


37

Teorema 2.37

Diberikan himpunan ⊂ m, fungsi B dan yang didefinisikan pada ke dalam m dan ∈ ℝ. Jika B dan kontinu di [], ^], maka B − kontinu di [], ^]. Bukti:

Misalkan ` sebarang titik di [], ^].

Akan dibuktikan lim[ f ( x) − g ( x)] = f (c) − g (c) x →c

Karena B dan kontinu di `, maka lim f ( x) = f (c) dan lim g ( x) = g (c) . x →c

x →c

Menurut teorema tentang limit fungsi diperoleh: lim[ f ( x ) − g ( x )] = lim f ( x ) − lim g ( x ) x→ c

x→ c

x→ c

= f (c ) − g ( c )

Karena ` adalah sebarang titik di [], ^] maka B − kontinu di setiap titik pada interval [], ^].

□

Definisi 2.38

Andaikan n daerah asal dari B, yang memuat titik ` maka 1.

B(`) adalah nilai maksimum B pada n jika B(`) ≥ B() untuk semua ∈

2.

B(`) adalah nilai minimum B pada n jika B(`) ≤ B() untuk semua ∈ n.

3.

n.

B(`) adalah nilai ekstrim B pada n jika merupakan nilai maksimum atau nilai minimum.


38

Teorema 2.39 (Teorema Titik Kritis)

Andaikan B terdefinisikan pada selang yang memuat titik `. Jika B(`) adalah nilai ekstrim, maka ` haruslah berupa suatu titik kritis; yakni ` berupa salah satu: 1. 2. 3.

Titik ujung dari ; atau

Titik stasioner dari B yakni titik ` sedemikian sehingga B′(`) = 0; atau

Titik singular dari B yakni titik ` sedemikian sehingga B′(`) tidak ada;

Bukti:

Misalkan B(`) berupa nilai maksimum B pada dan misalkan bahwa ` bukan ti-

tik ujung atau pun titik singular. Harus diperlihatkan bahwa ` adalah titik stasioner.

Karena B(`) adalah nilai maksimum, maka B() ≤ B(`) untuk semua dalam , yaitu B() − B(`) ≤ 0

Jadi, jika < `, sehingga − ` < 0, maka sedangkan jika > `, maka

B() − B(`) ≥0 −`

(2.8)

B() − B(`) ≤0 −`

(2.9)

Karena ` bukan titik singular maka B′(`) ada. Akibatnya, untuk → ` } maka lim

→

B() − B(`) = B (`) ≥ 0 −`


dan untuk → ` ~ maka

lim

→

39

B() − B(`) = B (`) ≤ 0 −`

Jadi, dapat disimpulkan bahwa B (`) = 0 atau ` merupakan titik stasioner. Teorema 2.40 (Teorema Nilai Rata-rata)

Jika B kontinu pada selang tertutup [], ^] dan terdiferensial dalam interval (], ^) maka terdapat paling sedikit satu bilangan ` dalam (], ^) dimana B (`) =

atau ekuivalen dengan

B(^) − B(]) ^−]

B(^) − B(]) = B (`)(^ − ])

Bukti: Pembuktian Teorema Nilai Rata-rata ini didasarkan pada analisis dari fungsi

H() = B() − (), yang akan diperlihatkan pada Gambar 2.1


Gambar 2.1

40

Persamaan = ( ) pada Gambar 2.1 adalah persamaan garis yang melalui (], B(])) dan (^, ( B((^)). Karena garis ini mempunyai kemiringan B(^) − B(]) ^−]

dan melalui (], B(] ])) maka bentuk kemiringan persamaannya adalah () − B(]) =

Selanjutnya dihasilkan ru rumus

B(^) − B(]) ( − ]) ^−]

H() = B() − ()

= B() − B(]) −

B(^) − B(]) ( ( − ]) ^−]

Perhatikan bahwa HH(^) = H(]) = 0 dan untuk dalam (], ^) H () = B () −

B(^) − B(]) ^−]


41

Jika diketahui bahwa terdapat suatu bilangan ` dalam (], ^) yang memenuhi H (`) = 0 maka bukti selesai. Hal ini didasarkan pada persamaan terakhir bahwa 0 = B (`) −

B(^) − B(]) ^−]

Karena B dan kontinu maka B − kontinu di [], ^]. Oleh karena itu H (`) ada untuk suatu ` dalam (], ^)

Berdasarkan sifat bahwa jika B kontinu pada interval tertutup [], ^], maka B

mencapai nilai maksimum dan minimum. Jadi H harus mencapai nilai maksimum

ataupun nilai minimum pada [], ^]. Jika kedua nilai ini kebetulan nol, maka H()

secara identik adalah nol pada [], ^], akibatnya H () = 0 untuk semua dalam

(], ^). Jika salah satu nilai maksimum atau nilai minimum berlainan dengan nol,

maka nilai tersebut dicapai pada sebuah titik dalam `, karena H(]) = H(^) = 0. Karena H mempunyai turunan di setiap titik dari (], ^), sehingga dengan Teorema Titik Kritis H (`) = 0.

Definisi 2.41

Sebuah fungsi B: ℝ → ℝ dikatakan terdiferensial secara kontinu pada ∈ ℝ ,

jika () ada dan kontinu, c = 1 … #. Gradien dari B pada didefinisikan seba

gai ∇B() = 3

$ B B (), … , ()4


42

Jika B terdiferensial secara kontinu pada setiap titik dari sebuah himpunan terbuka @ ⊂ ℝ , maka B dikatakan terdiferensial secara kontinu pada @ dan dinotasikan

dengan B ∈ (@). Definisi 2.42

Sebuah fungsi B: ℝ → ℝ yang terdiferensial secara kontinu dikatakan terdife-

rensial dua kali secara kontinu pada ∈ ℝ , jika

() ada dan kontinu,

c = 1 … #. Matriks Hesse dari B pada didefinisikan sebagai matriks simetri # × # yang elemennya

[∇ B()]Z =

B (), 1 ≤ c, ≤ # Z

Jika B terdiferensial dua kali secara kontinu pada setiap titik dari sebuah himpu-

nan terbuka @ ⊂ ℝ , maka B dikatakan terdiferensial dua kali secara kontinu pa-

da @ dan dinotasikan dengan B ∈ () (@). Definisi 2.43

Himpunan n ∈ ℝ adalah konveks jika untuk setiap , ∈ n, segmen garis

yang menghubungkan dan juga terletak di n.

Segmen garis yang menghubungkan dan didefinisikan dengan: + (1 − ) ∈ n, ∀ ∈ [0,1]

(2.10)


43

Jadi, subhimpunan n dari ℝ adalah konveks jika dan hanya jika untuk setiap

dan di n dan setiap dengan 0 ≤ ≤ 1, vektor + (1 − ) juga di n.

Berikut diberikan beberapa gambar yang mendeskripsikan himpunan konveks dan yang bukan himpunan konveks.

Gambar 2.2

Definisi 2.44

Misalkan n ⊂ ℝ merupakan himpunan konveks tak kosong.

Misalkan B: n ⊂ ℝ ⟶ ℝ.

Jika untuk setiap , ∈ n dan semua ∈ (0,1),

B( + (1 − ) ) ≤ B( ) + (1 − )B( )

maka B dikatakan konveks pada n.

(2.11)


44

Gambar 2.3

Gambar 2.3 merupakan contoh dari fungsi konveks dan bukan konveks. Interpretasi geometri fungsi konveks menyatakan bahwa nilai fungsi di bawah tali busur yang bersesuaian yaitu nilai fungsi konveks di titik pada segmen garis

+ (1 − ) kurang dari atau sama dengan tinggi dari tali busur yang menghubungkan titik-titik ( , B( ) dan ( , B( ). Contoh 2.9

: ℝ ⟶ ℝ didefinisikan oleh = , untuk ∈ ℝ. Buktikan bahwa fungsi tersebut adalah fungsi konveks.

Penyelesaian: Melalui Definisi 2.44 akan dibuktikan bahwa

( + (1 − )) ≤ () + (1 − )()

Ambil , ∈ ℝ dan semua ∈ [0,1] maka () = dan () = . ( + (1 − )) = ( + (1 − ))


45

= + 2(1 − ) + (1 − )

= + 2( − ) + (1 − 2 + )

= + 2( − ) + ( − 2 + )

Karena ∈ [0,1] maka < , sehingga

( + (1 − )) < + 2( − ) + ( − 2 + ) = + 2(0) + ( − ) = + ( − ) = + (1 − )

= () + (1 − )()

Karena ( + (1 − )) ≤ () + (1 − )(), maka dapat disimpulkan bahwa = adalah fungsi konveks untuk sebarang ∈ [0,1].

Contoh 2.10 Diberikan = + − 2 − 5 +

29 4

untuk ∈ ℝ . Akan ditunjukkan bahwa adalah fungsi konveks. Penyelesaian:

adalah fungsi konveks bila memenuhi

( + (1 − ) ) ≤ () + (1 − )( )

Ambil , ∈ ℝ2 di mana = (1 , 2 )$ , = 1 , 2 dan semua ∈ [0,1] maka $


46

+ (1 − ) = + (1 − )

− = + − =U

( − ) + V (} ) +

sehingga,

( + (1 − ) )

= (( − ) + ) + ((} ) + ) − 2(( − ) + ) −5(( − ) + ) +

29 4

= ( − )2 + 2( − ) + 21

+ ( − )2 + 2( − ) + 22

−2( − + ) − 5( − + ) +

29 4

= 21 − 2 + 21 + 2 − 2 21 + 21 + ( 22 − 2 + 22 +2 2 − 2 22 + 22 ) − 2 + 2 − 2 − 5 + 5 − 5 +

29 4

+2 2 − 2 22 + 22 ) − 2 + 2 − 2 − 5 + 5 − 5 +

29 4

= 21 − 2 + 21 + 2 − 221 + 21 + ( 22 − 2 + 22 = (2 +2 − 22 1 1 − 22 2 2 + 2 + 2 + 21 1 + 22

−2 − 2 − 21 + 21 − 52 + 52 ) + + − 21 − 52 +

Karena ∈ [0,1] maka 2 < , sehingga

29 4


47

( + (1 − ) )

< ( 21 + 22 − 2 − 2 + 21 + 22 + 2 + 2 2 − 2 21 −2 − 21 + 21 − 52 + 52 ) + + − 21 − 52 +

29 4

= 21 + 22 + 21 + 22 − 2 21 − 2 22 − 2 + 2 − 5 + 5 + 21 + − 21 − 52 +

29 4

= + − − − 21 + 21 − 52 + 52 + + − 21 − 52

+

29 4

= + − 21 − 52 + + − 21 − 52 − + − 21 − 52 +

29 4

= ( + − 21 − 52 ) + + − 21 − 52 − + − 21 − 52 +

29 4

= ( + − 2 − 5 ) + (1 − )( + − 2 − 5 ) + = () + (1 − )( ) Karena

¡

( + (1 − ) ) ≤ () + (1 − )( )

maka dapat disimpulkan bahwa = 21 +22 − 21 − 52 + veks untuk sebarang ∈ [0,1].

29 4

adalah fungsi kon-


48

Definisi 2.45 (Turunan Berarah)

Misalkan B: ℝ ⟶ ℝ terdiferensial secara kontinu pada himpunan terbuka @ ⊂ ℝ . Maka untuk ∈ @ dan ¢ ∈ ℝ , turunan berarah dari B pada dalam

arah ¢ didefinisikan sebagai

B( + ¦¢) − B() = ∇B()§ ¢ ¤⟶¥ ¦

B (; ¢) ≝ lim

dimana ∇B() adalah gradien dari B pada , merupakan vektor # × 1.

Untuk semua , ∈ @, diperoleh

(2.12)

$

B( ) = B() + ∇B + ¨( − ) ( − ), ¨ ∈ (0,1)

atau

B( ) = B() + ∇B()$ ( − ) + ©(‖ − ‖).

Definisi 2.46 Misalkan B ∈ () @. Untuk sebarang ∈ @, ¢ ∈ ℝ , turunan berarah kedua dari B pada dalam arah d didefinisikan dengan

B′( + ¦¢; ¢) − B′(; ¢) = ¢$ ∇ B()¢ ¤⟶¥ ¦

B (; ¢) ≝ lim

(2.13)

dimana ∇ B() merupakan matriks Hesse dari B pada . Untuk sebarang , + ¢ ∈ @, ada ª ∈ (, + ¢) sedemikian sehingga

atau

1 B( + ¢) = B() + ∇B()$ ¢ + ¢$ ∇ B(ª)¢ 2


49

1 B( + ¢) = B() + ∇B()$ ¢ + ¢$ ∇ B()¢ + ©(‖¢‖« ) 2 Teorema 2.47

Misalkan n ⊂ ℝ adalah himpunan konveks terbuka tak kosong dan misalkan

B: n ⊂ ℝ → ℝ adalah fungsi yang terdiferensial. Maka B adalah konveks jika dan hanya jika

B( ) ≥ B() + ∇B()$ ( − ), ∀, ∈ n

Bukti:

(2.14)

Syarat Perlu: Misalkan B() adalah fungsi konveks, maka untuk semua dengan 0 < < 1 dan , ∈ ℝ .

B( + (1 − )) ≤ B( ) + (1 − )B()

⟺

B( + − ) ≤ B( ) + B() − B()

⟺

B + ( − ) ≤ B( ) − B() + B()

⟺

B + ( − ) − B() ≤ B( ) − B()

Oleh karena itu, B + ( − ) − B() ≤ B( ) − B()

Tetapkan → 0 maka diperoleh

∇B()$ ( − ) ≤ B( ) − B()

−B( ) ≤ −B() − ∇B()$ ( − )


50

B( ) ≥ B() + ∇B()$ ( − ) Syarat Cukup: Asumsikan bahwa (2.14) berlaku. Ambil sebarang , ∈ n dan tetapkan = + (1 − ) , 0 < < 1. Maka

B( ) ≥ B() + ∇B()$ ( − )

B( ) ≥ B() + ∇B()$ ( − ) Oleh karena itu,

B( ) + (1 − )B( )

≥ B() + ∇B()$ ( − ) + (1 − )B() + ∇B()$ ( − )

= B() + ∇B()$ ( − ) + (1 − )B() + (1 − )∇B()$ ( − ) = B() + ∇B()$ ( − ) + B() − αB() + ∇B()$ ( − ) −∇B()$ ( − )

= B() + ∇B()$ ( − + − − + ) = B() + ∇B()$ ( + (1 − α) − ) = B() + ∇B()$ ( − ) = B() + 0

= B( + (1 − ) )

yang berarti bahwa B() adalah fungsi konveks.


51

Teorema 2.48

Misalkan n ⊂ ℝ adalah himpunan konveks terbuka tak kosong, dan misalkan B: n ⊂ ℝ ⟶ ℝ terdiferensial dua kali secara kontinu. Maka B adalah konveks

jika dan hanya jika matriks Hesse adalah semidefinit positif pada setiap titik dalam n.

Bukti:

Syarat cukup: Misalkan bahwa matriks Hesse ∇ B() adalah semidefinit positif

pada setiap titik ∈ n.

Akan dibuktikan bahwa B adalah konveks.

Pertimbangkan , ∈ n. Melalui Teorema Nilai Rata-rata diperoleh,

1 B() = B() + ∇B()$ ( − ) + ( − )$ ∇ B()( − ) 2

dimana = + ¦( − ), ¦ ∈ (0,1). Perhatikan bahwa ∈ n. Karena ∇ B() adalah semidefinit positif ∀ ∈ n maka ( − )$ ∇ B()( − ) ≥ 0

Akibatnya,

B() ≥ B() + ∇B()$ ( − )

Oleh karena itu melalui Teorema 2.47, B adalah fungsi konveks. Syarat perlu: Misalkan bahwa B adalah fungsi konveks dan misalkan ∈ n.

Akan dibuktikan bahwa T$ ∇ B()T ≥ 0, ∀T ∈ ℝ .


52

Karena n adalah himpunan terbuka, maka ada 9 > 0 sedemikian sehingga ketika |\| < 9, + \T ∈ n. Melalui Teorema 2.47

B + \T ≥ B + \∇B $ T

(2.15)

Karena B terdiferensial dua kali pada , maka B + \T = B + \∇B $ T +

\ $ T ∇ B T + ©‖\T‖« 2

2.16

Dengan mensubstitusikan persamaan (2.16) ke pertidaksamaan (2.15) maka \ $ B + \∇B T + T ∇ B T + ©‖\T‖« ≥ B + \∇B $ T 2 $

B − B + \∇B $ T − \∇B $ T +

\ $ T ∇ B T + ©‖\T‖« ≥ 0 2

1 0 + \ T$ ∇ B T + ©‖\T‖« ≥ 0 2

Jadi, setelah disubstitusikan diperoleh 1 $ \ T ∇ B T + ©‖\T‖« ≥ 0 2

Bagi dengan \ dan tetapkan \ → 0, maka

T$ ∇ B T ≥ 0

Jadi, dapat disimpulkan bahwa Matriks Hesse adalah semidefinit positif.

Teorema 2.49 (Teorema Proyeksi)

□

Misalkan n ⊂ ℝ merupakan himpunan konveks tertutup tak kosong dan ∉ n, ° ∈ n dengan jarak minimal dari yaitu maka ada titik tunggal


53

‖ − ° ‖ = inf ‖ − ‖

(2.17)

°〉 ≤ 0, ∀ ∈ n 〈 − ° , −

(2.18)

∈n

° adalah titik minimal dari persamaan (2.17) jika dan hanya jika Selanjutnya, ° adalah proyeksi ±H ( ) dari pada n jika dan atau dapat dikatakan bahwa

hanya jika (2.18) berlaku.

Bukti Misalkan

inf‖ − ‖| ∈ n = ² > 0

(2.19)

Karena ² adalah batas bawah terbesar maka ² ≤ ‖ − ‖, ∀ ∈ n.

Misalkan terdapat sebuah titik 1 ∈ n dan ∉ n. Kemudian, dibuat ruas garis

yang menghubungkan titik 1 dan titik y. Selanjutnya, dari titik 1 dibuat kitar dengan radius 1. Dari titik limit yang diperoleh dari kitar 1 dan berada pada ga-

ris yang menghubungkan titik 1 dan titik y, diperoleh titik 2 . Kemudian, dari ti1

tik 2 dibuat kitar dengan radius 2. Dari titik limit yang diperoleh dari kitar 2

dan berada pada garis yang menghubungkan titik 2 dan titik y, diperoleh titik

3 . Demikian seterusnya, hingga diperoleh titik −1 . Kemudian dari titik −1 1

dibuat kitar dengan radius . Dari titik limit yang diperoleh dari kitar −1 terse-

but dan terletak pada ruas garis yang menghubungkan titik −1 dan titik y dipe-

roleh titik . Dengan demikian akan ada barisan ⊂ n.


54

Akan ditunjukkan bahwa ‖ − ‖ → ².

Karena ² = inf‖ − ‖| ∈ n maka berdasarkan Lemma 2.31, untuk setiap >=

I

> 0 terdapat ‖ − ‖ dengan ∈ n sedemikian sehingga ² + > I

‖ − I ‖.

Dengan demikian, terbentuk barisan ‖ − ‖ yang terbatas dan turun. Berdasarkan Teorema 2.33, maka ‖ − ‖ akan konvergen dan lim ‖ − ‖ = ² = inf‖ − ‖.

→∞

• Berikut ini akan dibuktikan adalah barisan Cauchy dan oleh karena itu ° ∈ n. ada limit

Melalui Teorema Parallelogram diketahui bahwa

‖ + ‖2 + ‖ − ‖2 = 2‖‖2 + ‖ ‖2

Misalkan ambil , h ∈ n di mana diganti dengan − dan diganti de-

ngan ! − . Dengan mensubstitusikan dan ke Hukum Parallelogram di atas maka diperoleh

‖ + ! − 2 ‖2 + ‖ − ! ‖2 = 2‖ − ‖2 + 2‖! − ‖2

‖ − ! ‖2 = 2‖ − ‖2 + 2‖! − ‖2 − ‖ + ! − 2 ‖2

= 2‖ I − ‖ + 2‖ h − ‖ − ³2 U = 2‖ I − ‖ + 2‖ h − ‖ − 4 ´

Karena ⊂ n maka

( +! )

2

∈ n.

I + h − V³ 2

µ ~¶

− ´

(2.20)


55

Dari definisi ² diketahui bahwa inf‖ − ‖ = ² sehingga ‖ − ‖ = ‖ − ‖ ≥ ², ∀ ∈ n. Dengan mengganti = ³

³

+ ! − ³ ≥ γ 2

µ ~¶

, diperoleh

2 + ! − ³ ≥ ² 2 2

(2.21)

Jadi, dengan menggunakan persamaan (2.20) dan (2.21) diperoleh ‖ − ! ‖2 ≤ 2‖ − ‖2 + 2‖! − ‖2 − 4²2

Ambil k dan m cukup besar sehingga ‖ − ‖ → ² dan ‖! − ‖ → ². Dengan demikian dipenuhi ‖ − ! ‖2 → 2²2 + 2²2 − 4²2 = 0 atau ‖ − ! ‖ ⟶ 0

°. Karena yang menunjukkan bahwa · adalah barisan Cauchy dengan limit

° ∈ n. Hal ini menunjukkan bahwa ada ° sehingga n tertutup maka ‖ − ° ‖ = ².

Jadi, barisan adalah barisan Cauchy.

• Akan dibuktikan bahwa ° adalah tunggal.

° tidak tunggal, artinya ada °′ ∈ n dan °′ ≠ ° dengan ‖ ° ′ − ‖ = Andaikan

².

Melalui Hukum Parallelogram, misalkan diganti dengan ° ′ − dan diganti dengan ° − , maka diperoleh

° − 2 ‖2 + ‖° ° ‖2 = 2 ‖° ‖° ′ + ′ − ′ − ‖2 + 2‖° − ‖ 2


56

°′ − ° ‖2 = 2 ‖ °′ − ‖2 + 2‖ ° − ‖ 2 − ‖ °′ + ° − 2 ‖2 ‖

′ + = 2‖′ − ‖ + 2‖ − ‖ − ³2 U − V³ 2

′ + = 2‖′ − ‖ + 2‖ − ‖ − 4 ³ − ³ 2

′ + = 2² + 2² − 4 ³ − ³ 2

Karena

+ ′ 2

∈ n, maka menurut (2.21), ²2 ≤ ´

2 ′+ − . ´ 2

Akibatnya, °′ − °‖2 ≤ 2²2 + 2²2 − 4²2 ‖

=0

°′ − °‖ ≤ 0, padahal ‖ °′ − °‖ > 0. Jadi, ada kontradiksi. Terbukti Jadi, ‖

° °. ′ =

•

°〉 ≤ 0, ∀ ∈ n, maka ° adalah titik Akan dibuktikan bahwa jika 〈 − ° , −

‖ = inf∈n ‖ − ‖. minimum dari ‖ − °

°〉 ≤ 0, ∀ ∈ n dipenuhi, seAmbil x sebarang di S dan misalkan 〈 − ° , − ° − ‖2 hingga ‖ − ‖2 = ‖ − ° +

= ‖ − ‖ + ‖ − ‖ + 2〈 − , − 〉

= ‖ − ‖ + ‖ − ‖ + 2( − )§ ( − )

° − ‖2 ≥ 0 dan ( ° − )¸ ( − ° Karena ‖ ) ≥ 0, maka

° adalah titik minimum dari ‖ − ‖2 ≥ ‖ − ° ‖2 dan


57

‖ − ° ‖ = inf∈n ‖ − ‖.

•

Akan dibuktikan bahwa jika ° adalah titik minimum dari

°〉 ≤ 0, ∀ ∈ n. ‖ − ° ‖ = inf∈n ‖ − ‖, maka 〈 − ° , −

Misalkan ‖ − ‖2 ≥ ‖ − ° ‖2 , ∀ ∈ n.

° + \( − °) ∈ n dengan \ ∈ (0,1), maka diperoleh Karena ° + \( − °))‖2 ≥ ‖ − ° ‖ − ( ‖2

°)‖2 ≥ ‖ − ° ⇔ ‖ − ° − \( − ‖2 ° ‖2 ≥ ‖ − ° ⇔ ‖ − ° − \ + \ ‖2

° − )‖2 ≥ ‖ − ° ⇔ ‖ − ° + \( ‖2

° − ‖2 + 2\( ° − )¸ ( − ° ⇔ ‖ − ° ‖ 2 + \2 ‖ ) ≥ ‖ − ° ‖2 °‖2 + 2\( − °)¸ ( ° − ) ≥ ‖ − ° ⇔ ‖ − ° ‖ 2 + \2 ‖ − ‖2 °‖2 + 2\( − °)¸ ( ° − ) ≥ 0 ⇔ \2 ‖ −

Bagi dengan \ dan misalkan \ → 0, maka diperoleh

°〉 ≤ 0, ∀ ∈ n. 〈 − ° , −

□

Teorema 2.50

Misalkan n ⊂ ℝ merupakan himpunan konveks tertutup tak kosong dan ∉ n.

Maka terdapat vektor tak nol T dan bilangan real sehingga T$ > dan T$ ≤ α, ∀ ∈ n

dengan kata lain

(2.22)


T$ > supT$ , ∀ ∈ n

58

(2.23)

yang mengatakan bahwa terdapat hiperbidang º = |T$ = α yang secara tegas membagi dan n.

Bukti: Karena n adalah himpunan konveks tertutup tidak kosong dan ∉ n, maka mela-

lui Teorema Proyeksi terdapat titik tunggal ∈ n sehingga − $ − ≤ 0, ∀ ∈ n

Karena − $ − ≤ 0 maka $

− $ − = − $ − Diberikan T = − ≠ 0, maka

≤0

0 ≥ − $ − = − $ − + − = T$ − + T$ − = T$ T + T$ − T$

= ‖T‖‖T‖ + T$ − T$ = T$ − T$ + ‖T‖

Karena itu T$ ≥ T$ + ‖T‖ , ∀ ∈ n


59

Tetapkan = supT$ | ∈ n sehingga

T$ ≥ T$ + ‖T‖ = α + ‖T‖

Jadi benar bahwa terdapat vektor tak nol T dan bilangan real sehingga T$ ≥ α + ‖T‖

□

Lemma 2.51 (Lemma Farkas’)

Misalkan q ∈ ℝ»×¼ dan ½ ∈ ℝ . Maka tepat satu dari sistem berikut mempunyai penyelesaian: Sistem 1 q ≤ 0, ½ $ > 0 Sistem 2 q$ = ½, ≥ 0 Bukti:

(2.24) (2.25)

Misalkan bahwa terdapat penyelesaian untuk Sistem 2 yaitu terdapat ≥ 0 sede-

mikian sehingga q$ = ½.

Akan dibuktikan bahwa Sistem 1 tidak mempunyai penyelesaian. Misalkan memenuhi q ≤ 0 Karena ≥ 0 maka

½ $ = (q$ )$ = $ q ≤0

yang menunjukkan bahwa Sistem 1 tidak mempunyai penyelesaian.


60

Sekarang misalkan bahwa Sistem 2 tidak mempunyai penyelesaian.

Misalkan n = | = q$ , ≥ 0 yang adalah himpunan konveks tertutup tidak

kosong dan ½ ∉ n.

Akan dibuktikan bahwa Sistem 1 mempunyai penyelesaian. Melalui Teorema (2.50) terdapat T ∈ ℝ dan ∈ ℝ sehingga T$ ½ > dan T$ ≤ , ∀ ∈ n.

Karena 0 ∈ n, ≥ T$ 0 = 0. Maka T$ ½ > 0. Perhatikan pula bahwa ≥ T$ = T$ q$

= q$ $ T

= $ qT, ∀ ≥ 0

Karena ≥ 0 maka qT ≤ 0. Jadi ada vektor T ∈ ℝ yang merupakan penyelesaian dari Sistem 1.

□

C. Teori Optimasi Teori optimasi merupakan salah satu bidang dalam matematika terapan dan riset operasi yang dapat diaplikasikan dalam bidang sains, teknik, manejemen bisnis dan militer. Melalui teori optimasi ini masalah-masalah yang dihadapi akan didefinisikan secara matematis dan diselesaikan dengan menggunakan alat bantu matematika sehingga diperoleh penyelesaian dari masalah tersebut. Adapun bentuk umum dari masalah optimasi adalah sebagai berikut :


61

min B() ∈Á

(2.26)

dengan x adalah vektor di ℝ , B() adalah fungsi objektif, Á ⊂ ℝ adalah himpunan kendala atau daerah layak. Masalah optimasi ini juga terbagi menjadi dua bagian, yaitu masalah optimasi berkendala dan masalah optimasi tanpa kendala. Jika himpunan kendala Á = ℝ maka (2.26) merupakan masalah optimasi tanpa kendala dengan bentuk umum: ÂÃÄ B() ∈ℝÅ

(2.27)

Untuk masalah optimasi berkendala memiliki bentuk umum sebagai berikut: min∈ℝÅ B()

½Z () = 0, c = 1, … , !Æ

½Z () ≥ 0, c = !Æ + 1, … , !

(2.28) (2.29) (2.30)

dengan E dan I masing-masing adalah himpunan indeks dari kendala berupa per-

samaan dan kendala berupa pertidaksamaan, ½Z (), (c = 1, … , ! ∈ ∪ ) meru-

pakan fungsi kendala. = 1, … , !Æ dan = !Æ + 1, … , ! dimana !Æ dan ! adalah bilangan bulat tak negatif dengan 0 ≤ !Æ ≤ !.

Dilihat dari bentuk fungsi objektif dan fungsi kendala, masalah optimasi ini dapat dibagi pula menjadi dua bagian. Jika fungsi objektif maupun fungsi kendala berbentuk linear maka merupakan masalah optimasi linear. Jika fungsi


62

objektifnya tidak linear maka merupakan masalah optimasi nonlinear. Sebuah fungsi dikatakan fungsi linear jika memenuhi syarat-syarat berikut: 1. Fungsi yang belum diketahui dan derivatif-derivatifnya secara aljabar hanya berderajat satu. 2. Tidak ada hasil kali yang berkaitan dengan fungsi yang belum diketahui dan derivatif-derivatifnya atau dua atau lebih derivatif. 3. Tidak memuat fungsi transendental. Fungsi yang tidak linear merupakan fungsi nonlinear.

Definisi 2.52

Titik ∈ ℝ dikatakan sebagai titik layak atau disebut juga penyelesaian layak jika dan hanya jika memenuhi semua kendala pada persamaan dan pertidaksamaan (2.29)-(2.30). Himpunan semua titik layak dikatakan himpunan layak atau daerah layak.

Definisi 2.53 Penyelesaian optimum merupakan penyelesaian layak yang memiliki nilai terkecil untuk fungsi tujuan minimum.


63

Definisi 2.54

Misalkan nilai optimal dari masalah optimasi dinotasikan dengan È∗ yang merupakan nilai minimum dari fungsi objektif dalam daerah layak, yakni

È∗ = min(): ½c () = 0, c = 1, … , !Ê , ½c () ≥ 0, c = !Ê + 1, … !

Masalah optimasi dikatakan tidak layak jika daerah layaknya kosong dan È∗ bernilai +∞. Masalah optimasi dikatakan tidak terbatas ke bawah jika ada titik

layak sedemikian sehingga () → −∞ atau È∗ bernilai −∞.

Secara umum metode optimasi adalah metode iterasi yang bertujuan untuk mencari peminimum dari sebuah masalah optimasi. Metode iterasi mengacu pada berbagai teknik yang menggunakan aproksimasi pada setiap langkahnya untuk mendapatkan penyelesaian yang lebih akurat dari masalah-masalah optimasi baik masalah optimasi linear maupun nonlinear. Metode ini diawali dengan

memberikan nilai awal ¥ ∈ ℝ . Kemudian dibangun barisan iterasi I mela-

lui beberapa aturan iterasi sehingga ketika barisan I adalah berhingga maka titik akhirnya adalah penyelesaian optimum dari masalah optimasi. Jika barisan

I adalah tak hingga maka barisan tersebut memiliki titik limit yang adalah penyelesaian optimum dari masalah optimasi.


64

Definisi 2.55

Titik ∗ dikatakan peminimum lokal jika ada 9 > 0 sedemikian sehingga B( ∗ ) ≤ B() untuk semua ∈ ℝ memenuhi ‖ − ∗ ‖ < 9.

Titik ∗ dikatakan peminimum lokal tegas jika ada 9 > 0 sedemikian sehingga B( ∗ ) < B() untuk semua ∈ ℝ dengan ≠ ∗ dan ‖ − ∗ ‖ < 9.

Definisi 2.56

Titik ∗ dikatakan peminimum global jika B( ∗ ) ≤ B() untuk semua ∈ ℝ .

Titik ∗ dikatakan peminimum global tegas jika B( ∗ ) < B() untuk semua ∈ ℝ dengan ≠ ∗ .

Definisi 2.57

Misalkan B: ℝ¼ ⟶ ℝ terdiferensialkan pada ∈ ℝ . Jika terdapat vektor ¢ ∈ ℝ sehingga:

〈∇B(), ¢〉 < 0

maka ¢ disebut arah turun dari fungsi B di . Definisi 2.58

Titik ∗ ∈ ℝ dikatakan titik stasioner (atau kritis) untuk B yang terdiferensial jika ∇B( ∗ ) = 0.


65

Algoritma dari metode optimasi dapat diterima apabila iterasi I berge-

rak terus menerus ke arah peminimum lokal ∗ dan dengan cepat konvergen ke

titik ∗ . Jika aturan konvergensi yang diberikan telah dipenuhi maka iterasi dapat dihentikan. Iterasi dihentikan berdasarkan kriteria penghentian berikut: ‖∇B( I )‖ ≤ 9

(2.31)

dimana 9 adalah toleransi yang ditentukan. Jika (2.31) dipenuhi maka vektor

gradien ∇B( I ) cenderung menuju nol dan barisan iterasi I konvergen ke titik stasioner.

Misalkan I merupakan iterasi ke-, ¢I arah ke-, I panjang langkah ke-, maka iterasi ke- + 1 yaitu:

I~ = I + I ¢I

(2.32)

Berdasarkan persamaan (2.32) dapat dilihat bahwa adanya perbedaan panjang langkah I dan perbedaan arah ¢I membentuk metode yang berbeda. Kebanyakan metode iterasi disebut metode turun (descent methods) yang berarti B meme-

nuhi setiap iterasi

B( I~ ) = B( I + I ¢I ) < B( I )

dimana ¢I adalah arah turun seperti pada Definisi 2.57. Definisi 2.59

Misalkan ∗ ∈ Á dengan Á adalah daerah layak dan ¢ ∈ ℝ .

Jika ada barisan ¢I ( = 1,2, … ) dan 9I > 0, ( = 1,2, … ) sehingga

(2.33)


66

∗ + 9I ¢I ∈ Á, ∀ dan ¢I ⟶ ¢, 9I ⟶ 0, maka arah batas ¢ disebut arah layak sekuensial dari Á di ∗ . Himpunan semua arah layak sekuensial dari Á di ∗ ada-

lah

∗ + 9I ¢I ∈ Á, ∀ nÌ@( ∗ , Á) = Í¢Î Ï ¢I ⟶ ¢, 9I ⟶ 0

Berdasarkan definisi di atas, jika himpunan I = ∗ + 9I ¢I maka I adalah barisan titik layak yang memenuhi 1. I ≠ ∗ , ∀

2. limI⟶j I = ∗

3. I ∈ Á untuk semua yang cukup besar. Jika ¢I = ‖ I − ∗ ‖, maka

¢I =

I − ∗ ⟶¢ ‖ I − ∗ ‖

yang berarti bahwa I = ∗ + 9I ¢I adalah barisan titik layak dengan arah layak

¢.

Definisi 2.60

Misalkan ∗ ∈ Á dan ¢ ∈ ℝ . Jika

¢$ ∇cÑ ( ∗ ) = 0, c ∈ ¢$ ∇cÑ ( ∗ ) ≥ 0, c ∈ ( ∗ )

Maka ¢ dikatakan arah layak linear dari Á di ∗ . Himpunan semua arah layak linear dari Á di ∗ adalah


Ì@( ∗ , Á) = Ò¢Ó

67

¢$ ∇cÑ ( ∗ ) = 0, c ∈ Ô ¢$ ∇cÑ ( ∗ ) ≥ 0, c ∈ ( ∗ )

Skema dasar dari metode optimasi mengikuti algoritma berikut:

Algoritma 2.61

Langkah 0. (Langkah Awal) Diberikan titik awal ¥ ∈ ℝ dan toleransi k < 0 Langkah 1. (Kriteria Penghentian) Jika ‖∇B( I )‖ ≤ k, berhenti

Langkah 2. (Pencarian Arah) Menurut beberapa skema iteratif, cari ¢I yang adalah arah turun.

Langkah 3. Menentukan ukuran langkah I sehingga nilai fungsi objektif menurun yaitu

B( I + I ¢I ) < B( I )

Langkah 4. (Pengulangan) Tetapkan I~ = I + I ¢I , = + 1, dan ulang ke langkah 1. □

Efisiensi dari metode optimasi dapat diukur dari kecepatan konvergensinya. Ada beberapa jenis kecepatan konvergensi, diantaranya kecepatan konvergensi hasil bagi (Q-konvergensi) dan kecepatan konvergensi akar (R-konver-

gensi). Misalkan barisan iterasi I dibangun oleh sebuah algoritma yang kon-

vergen ke ∗ dalam suatu norm, yaitu:


lim ‖ I − ∗ ‖ = 0

I⟶j

68

(2.34)

Jika ada bilangan real ≥ 1 dan konstanta positif yang adalah independen dari jumlah k iterasi sehingga

‖ I~ − ∗ ‖ = I⟶j ‖ I − ∗ ‖Õ lim

(2.35)

maka I mempunyai orde- dari kecepatan Q-konvergensi. Secara khusus:

1. Ketika = 1 dan ∈ (0,1), barisan I dikatakan konvergen ke Q-linear.

2. Ketika = 1 dan = 0, atau 1 < < 2 dan > 0, barisan I dikatakan konvergen ke Q-superlinear.

3. Ketika = 2, dapat dikatakan bahwa barisan I mempunyai kecepatan konvergensi Q-kuadratik.

Kecepatan konvergensi ini bergantung pada dan . Andaikan bahwa

ada dua barisan I dan ′I dan orde-Q dan faktor-Q secara berturut-turut

, dan ′, ′. Jika > ′ maka barisan dengan orde Q- lebih cepat kon-

vergen dibandingkan dengan orde Q- ′. Sebagai contoh, barisan konvergen ku-

adratik akan lebih cepat konvergen jika dibandingkan dengan barisan konvergen

linear dan superlinear. Ketika = ′ maka orde-Q dari kecepatan konvergen-

sinya adalah sama, jika < ′ maka barisan I lebih cepat konvergen daripa-

da ′I .


69

Teorema 2.62 (Teorema Taylor)

Misalkan B: ℝ ⟶ ℝ terdiferensial secara kontinu dan bahwa ¢ ∈ ℝ , maka B( + ¢) = B() + ∇B( + ¢)$ ¢

(2.36)

untuk suatu ∈ (0,1). Bukti:

Akan dibuktikan B terdiferensial secara kontinu.

Misalkan B: ℝ ⟶ ℝ terdiferensial secara kontinu pada himpunan terbuka

⊂ ℝ , maka untuk ∈ dan ¢ ∈ ℝ turunan berarah dari B pada dengan arah ¢, didefinisikan dengan

B( + ¦¢) − B() = ∇B()$ ¢ ¤⟶¥ ¦

B ′ (; ¢) = lim

Pandang untuk l norm fungsi B() = ‖‖.

(2.37)

Dari definisi persamaan (2.37) diperoleh bahwa

‖ + ¦¢‖Ö − ‖‖Ö ∑Z[|Z + ¦×Z | − ∑Z[|Z | = lim ¤⟶¥ ¤⟶¥ ¦ ¦

B′(‖‖; ¢) = lim

Jika Z > 0 diperoleh |Z + ¦×Z | = |Z | + ¦×Z untuk semua ¦ yang cukup kecil.

Jika Z < 0, diperoleh

|−Z + ¦×Z | = |−Z − ¦×Z | = |−1||Z − ¦×Z | = |Z | − ¦×Z .

Jika Z = 0, |Z + ¦×Z | = |0 + ¦×Z | = ¦×Z . Selanjutnya diperoleh B′‖‖; ¢ = lim

¤⟶¥

∑Z| Ø¥|Z + ¦×Z | − ∑Z| Ø¥|Z | ¦


+ lim

¤⟶¥

+ lim

¤⟶¥

= lim

¤⟶¥

∑Z| Ù¥|Z + ¦×Z | − ∑Z| Ù¥|Z | ¦

∑Z| [¥|Z + ¦×Z | − ∑Z| [¥|Z | ¦

∑Z| Ø¥|Z | + ∑Z| Ø¥ ¦×Z − ∑Z| Ø¥|Z |

+ lim

¤⟶¥

=

70

¦

∑Z| Ù¥|Z | − ∑Z| Ù¥ ¦×Z − ∑Z| Ù¥|Z | ¦

¦ ∑Z| Ø¥ ×Z −¦ ∑Z| Ù¥ ×Z ¦ ∑Z| [¥ ×Z + + ¦ ¦ ¦

+

∑Z| [¥ ¦|×Z | ¦

= Y ×Z − Y ×Z + Y ×Z Z| Ø¥

Z| Ù¥

Z| [¥

Jadi turunan berarah dari fungsi B ada untuk sebarang dan ¢.

Misalkan B terdiferensial secara kontinu pada suatu kitar dari , maka diperoleh B ′ (B(); ¢) = ∇B()$ ¢

Untuk membuktikan formula ini didefinisikan fungsi

Ú() = B( + ¢) = B( ())

dimana () = + ¢. Catat bahwa

B( + ¦¢) − B() Ú(¦) − Ú(0) = lim = Ú ′ (0) ¤⟶¥ ¤⟶¥ ¦ ¦ lim

dengan menggunakan aturan rantai pada B( ()) diperoleh Ú ′ () =

B( ()) Z B( ()) B( ()) B( ()) ∙ + ∙ +⋯+ ∙ + × × Z × ∙

×


=Y Z[

=Y Z[

71

B( ()) ∙ ∇Z () Z

B( ()) ∙ ×Z = ∇B( ())$ ¢ = ∇B( + ×)$ ¢ Z

Dengan menggunakan = 0, diperoleh

Ú ′ (0) = ∇B()$ ¢ = B ′ (B(); ¢)

Dengan menggunakan Teorema Nilai Rata-rata. Misalkan diberikan sebuah fung-

si yang terdiferensial secara kontinu Ú: ℝ → ℝ dan terdapat paling sedikit satu bilangan ª dalam (¥ , ), dimana ¥ = 0 dan = 1 diperoleh Ú ′ ( ) = Ú(¥ ) + Ú′(ª)( − ¥ )

Ingat bahwa Ú() = B( + ¢).

Jika diganti dengan maka

Ú( ) = B( + ¢)

(2.38)

Substitusikan = 1 ke dalam persamaan (2.38) maka diperoleh Jika diganti menjadi ¥ maka

Ú(1) = B( + ¢)

Ú(¥ ) = B( + ¥ ¢)

(2.39)

Substitusikan ¥ = 0 ke dalam persamaan (2.39) maka diperoleh Ú(0) = B()

Suatu perluasan dari hasil ini untuk fungsi multivariabel B: ℝ ⟶ ℝ bahwa untuk sebuah vektor ¢ diperoleh bahwa


72

B( + ¢) = B() + ∇B( + ¢)$ ¢

Untuk suatu ∈ (0,1). Jadi terbukti untuk B yang terdiferensial secara kontinu. Teorema 2.63

Misalkan ∗ ∈ Á merupakan peminimum lokal dari masalah (2.28)-(2.30). Jika B() dan ½Z ()(c = 1,2, … , !) terdiferensial pada ∗ , maka ¢$ ∇B( ∗ ) ≥ 0, ∀¢ ∈ nÌ@( ∗ , Á)

(2.40)

Bukti

Untuk setiap ¢ ∈ nÌ@( ∗ , Á), terdapat 9I > 0( = 1,2, … ) dan ¢I ( = 1,2, … )

sehingga ∗ + 9I ¢I ∈ Á dengan 9I ⟶ 0 dan ¢I ⟶ ¢. Karena ∗ + 9I ¢I ⟶ ∗ dan ∗ adalah peminimum lokal, maka menurut Teorema Taylor dan untuk cukup besar diperoleh B( ∗ ) ≤ B( ∗ + 9I ¢I ) = B( ∗ ) + 9I ¢$I ∇B( ∗ ) + ©(9I ) 0 ≤ 9I ¢$I ∇B( ∗ ) + ©(9I )

(2.41)

Karena 9I > 0 dengan = 1,2, … maka diperoleh ¢$ ∇B( ∗ ) ≥ 0

Karena ¢ adalah sembarang, diperoleh pertidaksamaan (2.40).

(2.42) □


73

Lemma 2.64 Himpunan

¢$ ∇B( ∗ ) < 0, n = Û¢ Ü¢$ ∇½Z ( ∗ ) = 0, c ∈ ,Ý ¢$ ∇½Z ( ∗ ) ≥ 0, c ∈

(2.43)

adalah kosong jika dan hanya jika ada bilangan real \Z, c ∈ dan bilangan real tak negatif \Z > 0, c ∈ sehingga

∇B( ∗ ) = Y \Z ∇½Z ( ∗ ) + Y \Z ∇½Z ( ∗ ) Z∈Þ

Z∈ß

Tetapkan ∗)

¢ = −, ∇B(

= ½, q = à

Berdasarkan informasi di atas diperoleh: ¢$ ∇B( ∗ ) < 0

− $ ½ < 0

−½ $ < 0 hä

Y ¢ ∇½Z Z[

$

( ∗ )

h

½$ > 0

+ Y ¢$ ∇½Z ( ∗ ) ≥ 0 Z[hä ~ h

Y ¢$ ∇½Z ( ∗ ) ≥ 0 Z[

∇½$ ( ∗ )

â , ã = , ⋮ $ ( ∗ ) ∇½h

(2.44)


74

− $ q$ ≥ 0

−q ≥ 0 q ≤ 0

Jadi, persamaan 2.43 dapat dinyatakan dengan $ n = Í−Î½ > 0Ï q ≤ 0

dan persamaan 2.44 dapat dinyatakan dengan

∇B( ∗ ) = Y ãZ ∇½Z ( ∗ ) + Y ãZ ∇½Z ( ∗ ) Z∈Þ h

= Y ãZ ∇½Z ( ∗ )

Z∈ß

Z[ h

= Y ∇½Z ( ∗ ) ãZ Z[

½ = q$

Hasil di atas menunjukkan bahwa persamaan 2.43 merupakan sistem 1 pada Lemma 2.51 (Lemma Farkas’) dan 2.44 merupakan sistem 2 pada Lemma 2.51 (Lemma Farkas’). Melalui Lemma 2.64 ini • Misalkan bahwa terdapat penyelesaian untuk persamaan 2.44, akan dibuktikan bahwa persamaan 2.43 tidak mempunyai penyelesaian. • Misalkan persamaan 2.44 tidak mempunyai penyelesaian, akan dibuktikan bahwa persamaan 2.43 mempunyai penyelesaian. Selanjutnya untuk bukti analog dengan bukti pada Lemma 2.51.


75

Definisi 2.65

Pengali Lagrange merupakan barisan bilangan real \Z , sehingga titik ¥ , yang

meminimalkan B() dengan ½ () = 0, … , ½h () = 0 akan menjadi titik stasioner dari fungsi Lagrange h

ℒ(, ã) = B() − Y \Z ½Z () Z[

Teorema 2.66 (Teorema Karush-Kuhn-Tucker)

Misalkan ∗ merupakan peminimum lokal dari masalah (2.28)-(2.30). Jika kendala memenuhi

nÌ@( ∗ , Á) = Ì@( ∗ , Á)

(2.45)

∗ ∗ ∇B( ∗ ) − ∑h Z[ \Z ∇½Z ( ) = 0

(2.46)

maka terdapat pengali Lagrange \∗Z sehingga syarat-syarat berikut dipenuhi pada ( ∗ , ã∗ ) :

½Z ( ∗ ) = 0, ∀ c ∈ ½Z ( ∗ ) ≥ 0, ∀ c ∈ \∗Z ≥ 0, ∀ c ∈

\∗Z ½( ∗ ) = 0, ∀ c ∈

(2.47) (2.48) (2.49) (2.50)


76

Bukti:

Karena ∗ adalah peminimum lokal, ∗ adalah layak dan syarat (2.47) dan (2.48) dipenuhi.

Misalkan ¢ ∈ nÌ@( ∗ , Á);

Karena ∗ adalah peminimum lokal, berdasarkan Teorema 2.63 menyatakan bahwa ¢$ ∇B(æ∗ ) ≥ 0. Misalkan \∗Z = Í

\Z , c ∈ ç( ∗ ) 0, c ∈ \( ∗ )

(2.51)

Melalui Lemma Farkas’, didapatkan bahwa ∇B( ∗ ) = Y \∗Z ∇½Z ( ∗ ) + Y \∗Z ∇½Z ( ∗ ) Z∈Þ

Z∈ß( ∗ )

dimana \∗Z ∈ ℝ(c ∈ ) dan \∗Z ≥ 0(c ∈ ( ∗ )).

Tetapkan \∗Z = 0c ∈ \( ∗ ), sehingga diperoleh (2.46) yaitu: h

Jelas bahwa \∗Z ≥ 0, ∀ c ∈ .

∇B( ∗ ) = Y \∗Z ∇½Z ( ∗ ) Z[

Perhatikan bahwa:

Bila c ∈ ( ∗ ), ½Z ( ∗ ) = 0 dan \∗Z ≥ 0, karena itu \∗Z ½Z ( ∗ ) = 0.

Bila c ∈ \( ∗ ), ½Z ( ∗ ) > 0 tetapi \∗Z = 0, karena itu diperoleh pula

\∗Z ½Z ( ∗ ) = 0.

Dengan demikian, diperoleh \∗Z ½Z ( ∗ ) = 0, ∀ c ∈ .

□

(2.52)


77

Definisi 2.67 Titik Karush-Kuhn-Tucker adalah titik yang memenuhi syarat (2.46)-(2.50)

Definisi 2.68 ∇

ℒ∗ , ã∗

=

! ∗ ∇B( ) − Y \∗c ∇½c (∗ ) c=1

=0

adalah titik stasioner dalam syarat Karush-Kuhn-Tucker.

Teorema 2.69 Titik Karush-Kuhn-Tucker dari pemrograman konveks adalah peminimalnya.

Bukti:

Misalkan ∗ , ã∗ adalah sebarang titik Karush-Kuhn-Tucker dari pemrograman konveks. Diketahui fungsi Lagrange adalah sebagai berikut: (, ã∗ ) = B() − Y \∗Z ½Z () − Y \∗Z ½Z () Z∈é

Z∈ê

(2.53)

adalah konveks untuk . Melalui sifat fungsi konveks dan syarat Karush-KuhnTucker untuk sebarang yang layak, maka diperoleh

(, ã∗ ) ≥ ( ∗ , ã∗ ) + ( − ∗ )$ ∇ ( ∗ , ã∗ ) = ( ∗ , ã∗ ) + ( − ∗ )$ 0 = ( ∗ , ã∗ )


78

h

= B( ∗ ) − Y \∗Z ½Z ( ∗ ) Z[

= B( ∗ ) − 0 = B( ∗ )

Perhatikan bahwa adalah titik layak dan \∗c ≥ 0, c ∈ , jadi diperoleh

(2.54)

\∗c ½c () = 0, c ∈ ; \∗c ½c () ≥ 0, c ∈

Oleh karena itu diperoleh

(, ã∗ ) ≤ B()

Dari (2.54) dan (2.55) diperoleh

(2.55)

B() ≥ B( ∗ )

Jadi, titik Karush-Kuhn-Tucker ∗ adalah peminimal.

□


BAB III METODE HIMPUNAN AKTIF UNTUK MENYELESAIKAN MASALAH PEMROGRAMAN KUADRATIK

A. Pemrograman Kuadratik Pemrograman kuadratik merupakan salah satu masalah optimasi dalam matematika yang melibatkan kendala. Secara umum masalah pemrograman kuadratik merupakan masalah optimasi nonlinear dengan fungsi objektif berbentuk kuadratik dan kendala berbentuk linear. Fungsi kuadratik merupakan fungsi di mana nilai yang diberikan dalam bentuk polinomial kuadratik. Fungsi kuadratik tersebut mempunyai bentuk = + +

dengan = 1 , ⋯ , T, adalah matriks simetrik × , adalah matriks

1 × dan adalah suatu skalar. Fungsi vektor T

= =1

=1

adalah bentuk kuadrat dengan peubah yang diasosiasikan dengan fungsi kuadratik yang bersangkutan.


80

Contoh 3.1 Diberikan contoh di mana terdapat empat peubah, jika = , =

!

! , = "#

#

#

# $

maka diperoleh fungsi kuadratik sebagai berikut

= + +

= + + + + 2 + 2 + 2

+2 + 2 + 2! +# + # + # + # + .

Dengan mengetahui bentuk umum dari fungsi kuadratik, selanjutnya akan diberikan bentuk umum dari masalah pemrograman kuadratik. Adapun bentuk umum dari masalah pemrograman kuadratik tersebut, yaitu min ' = ( + )

Kendala:

12 = 32 − #2 = 0, ∈ 7 dengan ' ( 7

12 = 32 − #2 ≥ 0, ∈ 9 = fungsi objektif.

= matriks Hesse × dari fungsi objektif.

= himpunan indeks dari kendala yang berupa persamaan, : = {1,…, me}

(3.1)

(3.2) (3.3)


9

81

= himpunan indeks dari kendala yang berupa pertidaksamaan, ; = {me+1,…, m}

sedangkan g, x, ai, adalah vektor di ℝ= dan bi ∈ ℝ. Dari (3.1)-(3.3), terlihat bahwa secara umum masalah pemrograman kuadratik yang dibatasi oleh kendala berupa persamaan dan pertidaksamaan. Namun, ada kasus dimana masalah pemrograman kuadratik hanya dibatasi oleh kendala berupa persamaan. Bentuk umum dari masalah ini yaitu min ' = ( + )

Kendala:

= >

dengan ), ∈ ℝ= , > ∈ ℝ? , ∈ ℝ=×? , dan ( ∈ ℝ=×= .

(3.4)

(3.5)

Untuk menyelesaikan masalah (3.4) dengan kendala (3.5), dapat digunakan metode Lagrange yang didasarkan pada syarat Karush-kuhn-Tucker. Dari (3.4) diketahui,

= ( + ) dan 1 = − >

sehingga dengan menggunakan persamaan (2.46)-(2.47) maka syarat KarushKuhn-Tucker untuk persamaan (3.4) adalah: ∇ = ∇1A

1 ∇ B ( + ) C = ∇ − >A 2


1 1 ( + ( + ) 2 2 Kendala

( + )

82

= A

= A

(3.6)

− >

(3.7)

Jadi, sistem pada (3.6)-(3.7) dapat ditulis dalam bentuk matriks sebagai berikut

Matriks

( D −

) − ED E = −D E > 0 A

( D −

− E 0

(3.8)

(3.9)

adalah matriks Karush-Kuhn-Tucker untuk pemrograman kuadratik (3.4)-(3.5).

Masalah pemrograman kuadratik dapat diselesaikan dengan sejumlah metode, namun bergantung pada karakteristik dari fungsi objektifnya. Jika matriks Hesse G pada (3.1) adalah semidefinit positif maka masalah tersebut merupakan masalah pemrograman kuadratik konveks. Jika matriks Hesse G adalah definit positif maka merupakan pemrograman kuadratik konveks tegas dan jika matriks Hesse G adalah indefinit maka merupakan masalah pemrograman kuadratik nonkonveks. Masalah pemrograman kuadratik yang akan dibahas dalam tulisan ini yaitu masalah pemrograman kuadratik konveks. Masalah pemrograman kuadratik konveks ini dapat diselesaikan dengan menggunakan beberapa metode, di antaranya metode titik dalam dan metode himpunan aktif. Dalam pro-


83

sesnya, jika taksiran nilai awal penyelesaian itu layak maka akan lebih efektif

menggunakan metode himpunan aktif daripada metode titik dalam. Melalui metode ini akan lebih cepat konvergen hanya dengan menggunakan beberapa iterasi. Selain itu, metode himpunan aktif juga lebih sederhana karena tidak semua kendala digunakan untuk mencari penyelesaian yang dapat mengoptimumkan fungsi objektif.

Seperti yang disebutkan pada pembahasan sebelumnya bahwa terdapat masalah pemrograman kuadratik yang hanya dibatasi oleh kendala berupa persamaan. Untuk menyelesaikannya, dapat digunakan sistem Karush-Kuhn-Tucker seperti yang ditunjukkan pada persamaan (3.8) yaitu: D

( −

) − ED E = −D E > 0 A

Berikut adalah contoh masalah pemrograman kuadratik dengan kendala berupa persamaan yang diselesaikan dengan menggunakan persamaan (3.8).

Contoh 3.2 Diberikan masalah pemrograman kuadratik berikut:

min ' = 3 + 2 + + 2.5 + 2 + 2 − 8 − 3 − 3 Kendala

+ = 3

+ = 0


84

Dari masalah di atas, diketahui 6 2 ( = L2 5 1 2

1 −8 1 0 1 0 2O, ) = L−3O, = L0 1O sehingga = D 0 1 4 −3 1 1

Akan digunakan persamaan (3.8) untuk mencari dan A.

6 2 R 2 5 Q 1 2 Q 0 Q−1 P 0 −1

1 −1 0 8 U R 2 0 −1 3U T Q 4 −1 −1 T D E = Q 3 TT A −1 0 0T Q−3T S P 0S −1 0 0

6 2 R 2 5 Q 2 D E=Q 1 A 0 Q−1 P 0 −1

0.0769 R 0.0769 Q = Q−0.0769 Q−0.4615 P 0.3846 2 R−1U Q T = Q 1T Q 3T P−2S

1 3 E, > = D E 1 0

1 −1 0 V 8 2 0 −1U R 3 U 4 −1 −1 TT QQ 3 TT −1 0 0 T Q−3T −1 0 0 S P 0S 0.0769 0.0769 −0.0769 0.5385 −0.6154

−0.0769 −0.0769 0.0769 −0.5385 −0.3846

−0.4615 0.5385 −0.5385 −2.2308 0.6923

0.3846 8 U R U −0.6154 T Q 3T −0.3846T Q 3 T 0.6923 T Q−3T −3.0769S P 0 S

2 3 Jadi, = L−1O, A = D E. −2 3 Contoh (3.2) merupakan salah satu contoh dari masalah pemrograman kuadratik. Karena matriks koefisien mempunyai invers maka sistem persamaan di atas mempunyai solusi tunggal, di mana dari sistem persamaan tersebut diper-


85

oleh nilai dan A. Namun, metode di atas hanya dapat digunakan jika masalah

pemrograman kuadratik tersebut hanya dibatasi oleh kendala berupa persamaan. Dengan kata lain, jika terdapat kendala berupa pertidaksamaan, maka metode ini tidak dapat digunakan. Oleh karena itu, dibutuhkan metode lain yang dapat digunakan untuk menyelesaikan masalah pemrograman kuadratik dengan kendala yang bersifat umum. Salah satunya yaitu metode himpunan aktif yang akan dibahas pada subbab selanjutnya.

B. Metode Himpunan Aktif Definisi 3.1

Misalkan ∈ ℝ= , 12 , ∈ 9 adalah kendala pertidaksamaan, 9 = YZ | 12 = 0, ∈ 9\

Definisi 3.2

Misalkan ∈ ℝ= , : adalah himpunan indeks dari kendala berupa persamaan di mana : = {1,…, me}, maka himpunan

] = 7 ∪ 9

adalah himpunan indeks dari kendala aktif pada , 12 untuk ∈ ] adalah

kendala aktif pada , 12 untuk ∉ ] adalah kendala tidak aktif pada .


86

Masalah pemrograman kuadratik konveks dapat diselesaikan dengan menggunakan sebuah metode yang disebut metode himpunan aktif. Metode ini secara meluas digunakan pada tahun 1970. Secara umum metode himpunan aktif adalah metode untuk menyelesaikan masalah pemrograman kuadratik dengan kendala berupa persamaan yang digeneralisasikan untuk menyelesaikan masalah pemrograman kuadratik dengan kendala yang bersifat umum. Dengan kata lain metode himpunan aktif dapat digunakan untuk menyelesaikan masalah pemrograman kuadratik yang melibatkan kendala berupa persamaan dan pertidaksamaan. Dalam metode himpunan aktif terdapat kendala pertidaksamaan yang tidak aktif dan kendala pertidaksamaan aktif. Kendala pertidaksamaan yang tidak aktif tidak berperan dalam pencapaian penyelesaian sehingga dapat dihilangkan sedangkan kendala pertidaksamaan aktif memiliki nilai nol pada penyelesaiannya, jadi dapat digantikan oleh kendala berupa persamaan. Berikut diberikan lemma yang menjadi dasar dalam metode himpunan aktif tersebut.

Lemma 3.3

Misalkan ∗ adalah peminimum lokal dari masalah pemrograman kuadratik

(3.1)-(3.3) maka ∗ adalah peminimum lokal dari masalah 1 minb ( + ) a∈ℝ 2 Kendala

3c2 = #2 , ∈ 7 ∪ 9 ∗

3.10

(3.11)


87

sebaliknya jika ∗ adalah titik layak dari (3.1)-(3.3) dan titik Karush-Kuhn-

Tucker dari (3.10)-(3.11) dan vektor pengali Lagrange A∗ memenuhi d∗2 ≥ 0, ∈ 9 ∗

maka ∗ juga titik Karush-Kuhn-Tucker dari masalah (3.1)-(3.3).

(3.12)

Bukti: •

Karena titik layak dari (3.1)-(3.3) juga merupakan titik layak dari masalah (3.10)-(3.11), maka jelas bahwa peminimum lokal dari (3.1)-(3.3) juga merupakan peminimum lokal dari (3.10)-(3.11).

•

Misalkan ∗ merupakan titik layak untuk (3.1)-(3.3) dan titik Karush-Kuhn-

Tucker untuk (3.10)-(3.11)

Dari (3.10)-(3.11) diketahui,

∗ = ∗ ( ∗ + ) ∗ dan 12 ∗ = 32 ∗ − #2

Misalkan terdapat d∗2 ∈ 7 ∪ 9 ∗ maka dengan menggunakan syaratsyarat Karush-Kuhn-Tucker diperoleh (3.14)-(3.15) sebagai berikut: ∇ ∗ =

1 ∇ B ∗ ( ∗ + ) ∗ C = 2

2∈e ∗ ∪f

∇12 ∗ d∗2

2∈e ∗ ∪f

∇g32 ∗ − #2 h d∗2

1 1 B ( ∗ + ∗ ( + )C = i 2 2 ∗

2∈e ∪f

32 d∗2 j


( ∗ + ) =

Definisikan

2∈e ∗ ∪f

32 d∗2

d∗2 g3c2 ∗ − #2 h = 0, d∗2 ≥ 0, ∈ 9 ∗ d∗2 = 0, ∈ 9\9 ∗

Dari (3.13)-(3.15) diperoleh

?

( + ) = 32 d∗2 ∗

2l

3c2 ∗ = #2 , ∈ 7

88

3.13 (3.14)

(3.15)

3.16

(3.17)

3c2 ∗ ≥ #2 , ∈ 9

(3.18)

d∗2 g3c2 ∗ − #2 h = 0, ∀

(3.20)

d∗2 ≥ 0, ∈ 9

(3.19)

yang berarti bahwa ∗ adalah titik Karush-Kuhn-Tucker dari masalah (3.1)-

(3.3).

□

Metode himpunan aktif adalah metode titik layak, yaitu semua titik iterasi xk yang dibangun adalah titik layak dari kendala-kendalanya. Dalam setiap iterasi diselesaikan submasalah pemrograman kuadratik dengan sebuah subhimpunan dari kendala berupa persamaan. Subhimpunan ini diberi indeks dari suatu himpunan kerja yang dinotasikan dengan no ⊂ 7 ∪ 9 ∗ . Jika penyelesaian dari ken-


89

dala persamaan submasalah pemrograman kuadratik dalam no layak untuk masa-

lah (3.1)-(3.3) maka perlu diperiksa apakah syarat Karush-Kuhn-Tucker dipenuhi atau tidak. Jika dipenuhi maka akan didapatkan penyelesaiannya. Sebaliknya,

jika syarat Karush-Kuhn-Tucker tidak dipenuhi maka himpunan kerja no dihilangkan dan diselesaikan submasalah baru. Jika penyelesaian dari kendala per-

samaan submasalah pemrograman kuadratik dalam no tidak layak untuk masalah

(3.1)-(3.3) maka perlu ditambahkan kendala dalam himpunan kendala yang indeksnya adalah no kemudian diselesaikan submasalah baru.

Di setiap iterasi, titik layak o dan himpunan kerja no diketahui. Setiap iterasi berupaya mencari penyelesaian dari submasalah yang kendalanya berupa persamaan dalam no . Misalkan q merupakan langkah dari o q = − o

sehingga fungsi objektif dari submasalah pemrograman kuadratik dinyatakan dengan

1 minr o + q ( o + q + ) o + q q∈ℝ 2

3.21

dan kendalanya diperoleh dengan mensubstitusikan = o + q pada persamaan

(3.2),

32 − #2 = 0

32 o + q − #2 = 0

32 o + 32 q − #2 = 0

g32 o − #2 h + 32 q = 0


0 + 32 q = 0

90

32 q = 0, ∈ no

(3.22)

1 minr q (q + ) o q q∈ℝ 2

3.23

Dapat pula dinyatakan sebagai-berikut

32 q = 0, ∈ no

dimana ) o = ∇' o

(3.24)

1 = ∇ B o ( o + ) o C 2 =

1 1 ( o + o ( + ) 2 2

= ( o + ).

Titik Karush-Kuhn-Tucker dari (3.21)-(3.22) dinyatakan dengan qo dan pengali

Lagrange dinyatakan dengan d2 ∈ no . o

Submasalah pemrograman kuadratik (3.21)-(3.22) tersebut dapat diselesaikan dengan menggunakan persamaan berikut: ( D s −

) − q E D E = − D oE 0 0 A

Jika qo = 0 maka o adalah titik Karush-Kuhn-Tucker dari submasalah 1 minr ( + ) ∈ℝ 2

Jika d2

o

32 = #2 , ∈ no

(3.25)

3.26 (3.27)

≥ 0, ∀ ∈ no ∩ 9, maka o adalah titik Karush-Kuhn-Tucker dari

submasalah (3.1)-(3.3) dan iterasi diakhiri. Jika tidak, ada pengali Lagrange ne-


gatif, contohnya d2

o

91

< 0. Dalam hal ini, dimungkinkan untuk mereduksi fungsi

objektif dengan menghilangkan kendala ke-o dari himpunan kerja no . Kemudian

diselesaikan submasalah pemrograman kuadratik yang dihasilkan. Jika ada lebih dari satu indeks sehingga d2 < 0, maka dipilih o yang d2v = min 2∈wv ∩e d2

(3.28)

no ≔ no \Yo \

(3.29)

v xy z{.

dan tetapkan

o

Misalkan bahwa penyelesaian qo ≠ 0. Jika o + qo layak untuk semua kendala,

maka ditetapkan

o~ = o + qo

(3.30)

o~ = o + o qo

(3.31)

Sebaliknya, penentuan ukuran langkah dibuat sepanjang arah qo dan ditetapkan

dimana o adalah ukuran langkah sehingga o + o qo yang adalah titik layak

terbaik pada " o , o qo $ dan paling dekat dengan o + qo , dengan kata lain ambil

o sebesar mungkin dalam interval [0,1].

Selanjutnya dijabarkan rumus eksplisit o . Diberikan o + o qo yang

memenuhi semua kendala. Jika ∈ no , maka kendala yang sesuai pasti layak.

Karena itu hanya perlu mempertimbangkan kendala dimana ∉ no . Ada dua ka-

sus yang perlu dipertimbangkan.


92

1. Jika 32 qo ≥ 0 untuk suatu ∉ no maka untuk semua o ≥ 0 32 o + o qo ≥ 32 o ≥ #2, ∉ no

Dalam hal ini, kendala dipenuhi.

2. Jika 32 qo < 0 untuk suatu ∉ no hanya jika

32 o + o qo ≥ #2

αo ≤ Karena itu diambil

#2 − 32 o , ∉ no 32 qo

αo = min

2∉wv 3 y qv z{

#2 − 32 o 32 qo

3.32 3.33

Karena diinginkan o sebesar mungkin dalam [0,1] yang bergantung pada kelayakan yang tersisa, maka diperoleh rumus berikut

#2 − 32 o αo = min 1, min 2∉wv 32 qo 3 y qv z{

3.34

Jika o < 1 atau dengan kata lain (3.33) berlaku, maka ada suatu ∉ no sehingga

αo = Oleh karena itu,

# − 3 o 3 qo

3 o~ = 3 o + o 3 qo = #


93

Hal ini berarti bahwa ada kendala baru berindeks ∉ no yang menjadi kendala

aktif di o~ . Jadi, masukkan kendala baru tersebut ke dalam himpunan kerja, ar-

tinya, tetapkan no~ = no ∪ Y\. Jika o = 1 maka himpunan kerja tetap sama yaitu no~ = no . Jadi, iterasi berikutnya dapat dilanjutkan pada himpunan kerja

baru no~.

Algoritma 3.4

Langkah 1: Diberikan { yang memenuhi kendala dan tetapkan no = 7 ∪ 9 { , ≔ 0.

Langkah 2: Cari penyelesaian qo dan d2

o

untuk submasalah pemrograman

kuadratik (3.21)-(3.22) dengan menggunakan persamaan (3.25).

Jika qo ≠ 0, ke langkah 3;

Jika qo = 0, pertimbangkan nilai d2

Jika d2

o

Jika d2

o

o

≥ 0, ∀ ∈ no ∩ 9, berhenti;

< 0, cari o melalui (3.28).

no ≔ no \Yo \, o~ = o , ke langkah 4.

Langkah 3: Cari o melalui (3.34) Tetapkan

o~ = o + o qo

Jika o = 1, ke langkah 4

Lain, cari ∉ no sehingga

(3.35)


3 o + o qo = #

Tetapkanno : = no ∪ Y\.

Langkah 4: no~ : = no , ≔ + 1, ke langkah 2.

94

(3.36)

□


95

Diagram Alir Metode Himpunan Aktif

x0 S 0 = E ∪ I (x 0 ) k := 0

k≤N

Tentukan d k dan λi( k ) melalui persamaan (3.25)  G − AT 

− A d  g  = − k  0  λ  0

cari ik melalui persamaan (3.28)

dk ≠ 0

Pertimbangkan

λi( k ) ≥ 0 ∀i ∈ S k ∩ I

(k ) i

nilai λ

λi = min i∈S k

k ∩I λi( k ) < 0

λ(i k )

S k := S k \ {ik } x k +1 = x k

Tentukan α k melalui persamaan  bi − aTi x k  1, T  k ai d k  aTi d k < 0  Tetapkan x k +1 = x k + α k d k

α k = min i∉S

Cari j ∉ S k yang memenuhi

αk =1

a Tj (x k + α k d k ) = b j Tetapkan S k = S k ∪ { j}

S k +1 := S k k := k + 1

Gambar 3.1

Dari Algoritma 3.4 diketahui bahwa semua iterasi adalah layak, atau dengan kata lain


dan fungsi objektif

96

o ∈ , ∀

(3.37)

' o~ ≤ ' o , ∀

(3.38)

Selama qo ≠ 0 (atau dengan kata lain o bukan titik Karush-Kuhn-Tucker dari (3.26)-(3.27)) dan αo > 0, maka

' o~ < ' o

(3.39)

Jika algoritma berakhir dengan langkah yang banyak namun berhingga, titik hasilnya adalah titik Karush-Kuhn-Tucker dari masalah (3.1)-(3.3). Misalkan bahwa algoritma tidak berakhir pada langkah yang banyak namun berhingga; karena hanya ada sejumlah kendala yang berhingga maka tidak mungkin bahwa jumlah elemen di no meningkat tak hingga banyak kali dan tidak berku-

rang. Jadi, ada tak hingga banyak sehingga qo = 0. Berdasarkan algoritma

bahwa ada tak hingga banyak indeks maka o adalah titik Karush-Kuhn-

Tucker dari (3.26)-(3.27). Karena banyaknya kendala berhingga, no hanya

mempunyai sejumlah berhingga kombinasi yang berbeda dan juga barisan dari nilai objektif Y' o \ hanya mempunyai sejumlah berhingga elemen. Oleh ka-

rena itu, harus ada { yang cukup besar sehingga

' o~ = ' o , ∀ ≥ {

(3.40)

αo = 0

(3.41)

Maka untuk semua ≥ { , salah satu dari atau


qo = 0

97

(3.42)

akan berlaku. Karena hanya ada sejumlah berhingga kendala, tidak mungkin

bahwa algoritma hanya meningkatkan kendala ke no , maupun mengurangi kendala dari no . Karena itu, harus ada tak hingga banyak indeks sehingga qo ≠ 0

(3.43)

qo = 0

(3.44)

dan tak hingga banyak indeks sehingga Jadi, ada > > { sehingga

qo = 0, qo = 0,

dan

qo ≠ 0, < < > + 1

(3.45) (3.46)

(3.47)

Definisi 3.5

Misalkan Y= \ adalah sebuah barisan.

• Jika ada bilangan sedemikian sehingga Y= \ ≤ untuk semua ≥ 1, maka Y= \ dikatakan terbatas ke atas.

• Jika ada bilangan sedemikian sehingga Y= \ ≥ untuk semua ≥ 1, maka Y= \ dikatakan terbatas ke bawah.

• Jika Y= \ terbatas ke atas dan terbatas ke bawah maka Y= \ dikatakan terbatas.


98

Teorema 3.6 (Teorema Konvergensi dari Metode Himpunan Aktif) Misalkan kendala dari masalah pemrograman kuadratik konveks adalah

32 − #2 ≥ 0. Jika untuk semua , 32 ∈ 7 ∪ 9 o adalah bebas linear, maka barisan yang dibangun dari Algoritma 3.4 akan konvergen ke titik Karush-Kuhn-

Tucker dari masalah (3.1)-(3.3) dalam iterasi berhingga, atau masalah (3.1)-(3.3) tidak terbatas ke bawah.

Bukti:

Akan dibuktikan bahwa Y o \ konvergen ke titik Karush-Kuhn-Tucker atau masa-

lah (3.1)-(3.3) tidak terbatas ke bawah.

Asumsikan bahwa masalah (3.1)-(3.3) adalah terbatas ke bawah, maka barisan Y o \ adalah terbatas.

Jika penyelesaian dari submasalah (3.21)-(3.22) adalah qo = 0, maka o adalah

titik Karush-Kuhn-Tucker dari (3.26)-(3.27) untuk himpunan kerja no . Jika

d2

o

≥ 0, ∀ ∈ no ∩ 9, maka o adalah titik Karush-Kuhn-Tucker dari masalah

(3.1)-(3.3). Jika tidak, ada d2v < 0 o ∈ no ∩ 9 maka dapat dicari arah turun o

layak qo sedemikian sehingga

3s qo = 0, ∈ no , ≠ o ,

dan dari persamaan (3.6) diperoleh

(3.48)

3s2v qo > 0

(3.49)

) o qo = gAo h o qo = g32v qo hgAo h 2v = g32v qo hd2v < 0.

o

(3.50)


99

Jika persamaan (3.48) disubstitusikan ke kendala pada persamaan (3.22) atau

dengan kata lain no ≔ no \Yo \, submasalah pemrograman kuadratik yang dihasilkan akan memiliki arah turun layak. Karena o > 0, ' o~ < ' o

(3.51)

dan oleh karena itu, melalui kendala yang berhingga, algoritma tidak akan kembali ke himpunan kerja no , dan barisan Y o \ adalah berhingga.

Jika qo ≠ 0 dan o = 1, maka no~ = no , dan submasalah (3.21)-(3.22) tidak berubah untuk o~, jadi o~ adalah penyelesaian dari (3.21)-(3.22).

Hanya jika qo ≠ 0 dan o < 1, o~ bukan merupakan penyelesaian dari (3.21)-

(3.22). Dari persamaan (3.36) pada langkah ke-3 dari Algoritma 3.4, diketahui

bahwa ada indeks ∉ no sehingga kendala ke-j adalah layak. Jadi, seperti kendala ditambahkan ke no~ . Jika proses ini terjadi beulang-ulang, maka setelah

paling banyak iterasi himpunan kerja no akan memuat indeks, yang sesuai

dengan vektor bebas linear, maka melalui persamaan (3.22) diperoleh qo = 0.

Oleh karena itu, prosedur tersebut berlanjut paling banyak kali. Jadi akan ada titik Karush-Kuhn-Tucker o dari (3.26)-(3.27) paling banyak setelah iterasi. Algoritma akan konvergen di iterasi berhingga untuk titik Karush-Kuhn-Tucker dari masalah (3.1)-(3.3).

□


100

Contoh 3.3 Diberikan

min ' = − 1 + − 2.5

Kendala

− 2 + 2 ≥ 0

(1)

− + 2 + 2 ≥ 0

(3)

− − 2 + 6 ≥ 0 ≥ 0

≥ 0

(2)

(4) (5)

Dengan metode himpunan aktif, akan dicari peminimum dari fungsi tersebut.

Penyelesaian: Fungsi objektif di atas dapat diuraikan sebagai berikut min ' = − 1 + − 2.5

= − 2 + 1 + B − 5 + = + − 2 − 5 +

29 4

25 C 4

Jika diubah dalam bentuk masalah pemrograman kuadratik maka fungsi objektif di atas menjadi min ' =

1 2 0 29 −2 + + 0 2 −5 2 4

Jika diilustrasikan, gambar dari masalah di atas adalah sebagai berikut


101

Masalah di atas akan diselesaikan dengan menggunakan langkah-langkah dari Algoritma 3.4.

Iterasi 0 Langkah 1 2 { = D E 0

Dengan mensubstitusikan { ke kendala (1)-(5) akan diperoleh 2 − 20 + 2 = 4

(1)

−2 + 20 + 2 = 0

(3)

−2 − 20 + 6 = 4 2≥0 0≥0

(2)

(4) (5)

Karena kendala (3) dan (5) memenuhi kendala pertidaksamaan aktif dimana 12 = 0, maka dapat ditetapkan bahwa:


102

n{ = Y3, 5\ =0

Langkah 2

Menentukan q{ dan A{ untuk menyelesaikan submasalah pemrograman kuadra-

tik pada persamaan (3.25) dengan, ) { = ( { + ) 2 =D 0

0 2 −2 ED E + D E 2 0 −5

4 −2 = D E+D E 0 −5 2 =D E −5

sehingga,

( D s −

) − q E D E = − D oE 0 0 A

2 0 2 1 0 q 2 −2 −1 { = − −5 0 1 −2 0 0 A{ 0 0 −1 0 0 0

2 0 1 0 V −2 q 2 −2 −1 5 { = 0 1 −2 0 0 0 A{ 0 −1 0 0 0 0 0 1 q{ 0 0 0 = 1 0 −2 A{ −2 −1 4

−2 −2 −1 5 4 0 −10 0


103

0 q{ = 0 −2 A{ −1

0 −2 Jadi, q{ = D E dan A{ = D E. 0 −1

Hasil di atas menunjukkan bahwa q{ = 0 dan A{ < 0. Oleh karena itu { bukan

penyelesaian optimal. Karena A{ < 0 maka akan dicari o melalui persamaan (3.28) yaitu,

A2o = min A2 2∈wv ∩e v

Ay z{.

o

Karena A{ = −2 merupakan pengali Lagrange dari kendala (3) maka harus dihi-

langkan dari himpunan kerja.

2 n{ : = n{ \Y{ \, = { = D E, lanjutkan ke langkah 4. 0 Langkah 4

n : = n{ = Y5\ , ≔ 1 Kembali ke langkah 2

Iterasi 1 Langkah 2

Menentukan q dan A untuk menyelesaikan submasalah pemrograman kuadra-

tik pada persamaan (3.25) dengan,


) = ( + ) 2 =D 0

0 2 −2 ED E + D E 2 0 −5

4 −2 = D E+D E 0 −5 2 =D E −5

sehingga,

2 L0 0

( D s −

) − q E D E = − D oE 0 0 A

0 0 q 2 2 −1O = − L−5O A −1 0 0

2 0 q = L0 2 A 0 −1

0 V −2 −1O L 5 O 0 0

0.5 0 0 −2 q =L 0 0 −1O L 5 O A 0 0 −1 −2 −1 q = L 0O A −5

−1 Jadi, q = D E dan A = −5. 0

Karena q ≠ 0, lanjutkan ke langkah 3.

Langkah 3

Menentukan melalui persamaan (3.34) yaitu,

104


Untuk = 1 maka


2 −2 − "1 −2$ D E −2 − 2 0 =

= =4 −1 −1 "1 −2$ D E 0

Untuk = 2 maka

2 −6 − "−1 −2$ D E −6 + 2 0 =

= = −4 −1 1 "−1 −2$ D E 0

Untuk = 3 maka

2 −2 − "−1 2$ D E −2 + 2 0 =

= =0 −1 1 "−1 2$ D E 0

Untuk = 4 maka

2 0$ D E 0 − 2 0 =

= =2 −1 −1 "1 0 $ D E 0 0 − "1

Karena 32 qo < 0 terjadi untuk = 1 dan 4 maka

= minY1,2,4\ = 1

Tetapkan

= + q

2 −1 = D E + 1D E 0 0

105


106

1 =D E 0

Karena = 1 maka lanjutkan ke langkah 4. Langkah 4

n : = n = Y5\ dan ≔ 2, kembali ke langkah 2. Iterasi 2 Langkah 2


tik pada persamaan (3.25) dengan, ) = ( + ) 2 =D 0

0 1 −2 ED E + D E 2 0 −5

2 −2 = D E+D E 0 −5 0 =D E −5

sehingga,

2 L0 0

( D s −

) − q E D E = − D oE 0 0 A

0 0 q 0 2 −1O = − L−5O A −1 0 0 2 q = L0 A 0

0 0 V 0 2 −1O L5O −1 0 0


107

0.5 0 0 0 q =L 0 0 −1O L5O A 0 −1 −2 0 0 q = L 0O A −5

0 Jadi, q = D E dan A = −5. 0

Karena q = 0 dan A < 0 maka bukan penyelesaian optimal. A{ < 0 maka akan dicari o melalui persamaan (3.28) yaitu,

A2o = min A2 2∈wv ∩e v

Ay z{.

o

Karena A = −5 merupakan vektor pengali Lagrange dari kendala (5), maka

kendala (5) harus dihilangkan dari himpunan kerja.

1 n : = n \Y \, = = D E, lanjutkan ke langkah 4. 0 Langkah 4

n : = ∅ dan ≔ 3, kembali ke langkah 2. Iterasi 3 Langkah 2


tik pada persamaan (3.25) dengan, ) = ( + )


2 =D 0

0 1 −2 ED E + D E 2 0 −5

2 −2 = D E+D E 0 −5 0 =D E −5

sehingga,

( D s −

) − q E D E = − D oE 0 0 A

2 0 q 0 D E = −D E 0 2 A −5

q 2 0 V 0 =D E D E A 0 2 5

q 0 =D E A 2.5

Jadi, q = D

q 0.5 0 0 =D ED E A 0 0.5 5

0 E. 2.5

Karena q ≠ 0, lanjutkan ke langkah 3. Langkah 3

Menentukan melalui persamaan (3.34)


108


Untuk = 1 maka

1 −2 − "1 −2$ D E −2 − 1 0 =

= = 0.6 0 −5 "1 −2$ D E 2.5

Untuk = 2 maka

1 −6 − "−1 −2$ D E −6 + 1 0 =

= =1 0 −5 "−1 −2$ D E 2.5

Untuk = 3 maka

1 −2 − "−1 2$ D E −2 + 1 0 =

= = −0.2 0 5 "−1 2$ D E 2.5

Untuk = 4 maka

=

"1

Untuk = 5 maka

=

1 0$ D E 0 − 1 0 = = tidak terdeinisi 0 0 0$ D E 2.5

0 − "1

1 1$ D E 0 − 0 0 = =0 0 2.5 1$ D E 2.5

0 − "0 "0

Karena 32 qo < 0 terjadi untuk = 1 dan 2 maka

= minY1, 0.6\ = 0.6 Tetapkan

= + q

109


110

1 0 = D E + 0.6 D E 0 2.5 =D

1 E 1.5

Karena < 1 maka akan ditentukan ∉ no yang memenuhi persamaan (3.36)

yaitu,

3 ( o + o qo ) = #

Karena n = ∅ maka ∈ Y(1), (2), (3), (4), (5)\. Untuk = 1 Untuk = 2 Untuk = 3 Untuk = 4 Untuk = 2

# = "1

1 −2$ D E = −2 1.5

1 # = "−1 −2$ D E = −4 1.5 1 # = "−1 2$ D E = 2 1.5 # = "1 # = "0

1 0$ D E = 1 1.5 1 1$ D E = 1.5 1.5

Karena untuk = 1, # memenuhi persamaan (3.36) maka ditetapkan n ≔ n ∪ Y1\


111

Langkah 4

n : = Y1\ dan ≔ 4, kembali ke langkah 2. Iterasi 4 Langkah 2


tik pada persamaan (3.25) dengan, ) = ( + ) 2 =D 0

0 1 −2 ED E + D E 2 1.5 −5

2 −2 = D E+D E 3 −5 0 =D E −2

sehingga,

2 L 0 −1

( D s −

) − q E D E = − D oE 0 0 A

0 −1 q 0 2 2 O = − L−2O A 2 0 0 2 q = L 0 A −1

0 −1 V 0 2 2 O L2O 2 0 0

0.4 0.2 −0.2 0 q = L 0.2 0.1 0.4 O L2O A −0.2 0.4 −0.4 0


0.4 q = L0.2O A 0.8 Jadi, q = D

0.4 E dan A = 0.8 0.2

Karena q ≠ 0, lanjutkan ke langkah 3. Langkah 3

Menentukan melalui persamaan 3.34 yaitu,


Untuk = 2 maka

1 −6 − "−1 −2$ D E −6 + 4 1.5 =

= = 2.5 0.4 −0.8 "−1 −2$ D E 0.2

Untuk = 3 maka

=

"−1

Untuk = 4 maka

=

1 E 1.5 = −2 − 2 = tidak terdeinisi 0.4 0 2$ D E 0.2

−2 − "−1 2$ D

0 − "1 "1

Untuk = 5 maka

1 0$ D E 0 − 1 1.5 = = −2.5 0.4 0.4 0$ D E 0.2

112


=

0 − "0 "0

113

1 1$ D E 0 − 1.5 1.5 = = −7.5 0.4 0.2 $ D E 1 0.2

Karena 32 qo < 0 terjadi untuk = 2 maka

= minY1, 2.5\ = 1 Tetapkan

= + q =D =D

1 0.4 E + 1D E 1.5 0.2 1.4 E 1.7

Karena = 1, lanjut ke langkah 4. Langkah 4

n : = n = Y1\ dan ≔ 5, kembali ke langkah 2. Iterasi 5 Langkah 2

Menentukan q dan A untuk menyelesaikan submasalah pemrograman kuadratik pada persamaan (3.25) dengan, ) = ( + ) 2 =D 0

0 1.4 −2 ED E + D E 2 1.7 −5


114

2.8 −2 = D E+D E 3.4 −5 0.8 =D E −1.6

sehingga,

2 L 0 −1

( D s −

) − q E D E = − D oE 0 0 A

0 −1 q 0.8 2 2 O = − L−1.6O A 2 0 0 2 q = L 0 A −1

0 −1 V −0.8 2 2 O L 1.6 O 2 0 0

0.4 0.2 −0.2 −0.8 q = L 0.2 0.1 0.4 O L 1.6 O A −0.2 0.4 −0.4 0 0 q =L 0 O A 0.8

0 Jadi, q = D E dan A = 0.8 0

Karena A > 0 maka iterasi dihentikan dan = D

optimal.

1.4 E merupakan penyelesaian 1.7

Masalah di atas dapat pula diselesaikan dengan menggunakan program MATLAB sebagai berikut:


115

Tabel 3.1 Output Penyelesaian contoh 3.3 dengan Matlab -----------------------------------------k

x(1)

x(2)

-----------------------------------------1

2.000

0.000

2

2.000

0.000

3

1.000

0.000

4

1.000

0.000

5

1.000

1.500

6

1.400

1.700

-----------------------------------------Pada iterasi ke-6, d2 ≥ 0.

Jadi nilai yang meminimalkan fungsi adalah:

= 1.400 dan = 1.700.

Berikut akan diberikan tabel perbandingan nilai awal dengan hasil akhir dan jumlah iterasi yang dibutuhkan dalam Metode Himpunan Aktif untuk menyelesaikan masalah optimasi seperti pada contoh 3.3. Tabel 3.2 Tabel Perbandingan Nilai Awal Metode Himpunan Aktif No. 1.

Nilai Awal ( { ) (0,1)

Penyelesaian ( o ) (1.400,1.700)

Jumlah Iterasi 3


2. 3. 4. 5. 6. 7. 8. 9. 10. 11 12 13 14 15

(2,2)

(1.400,1.700)

3

(0,0)

(1.400,1.700)

5

(2.5,0)

(1.400,1.700)

(6,4)

(1.400,1.700)

(7,0)

(1.400,1.700)

(4,1)

(1.400,1.700)

(15,0)

(1.400,1.700)

(2,0)

(1.400,1.700)

(3,0)

(1.400,1.700)

(6,2)

(1.400,1.700)

(16,0)

(1.400,1.700)

(23,0)

(24,11) (30,14)

(1.400,1.700) (1.400,1.700) (1.400,1.700)

116

7

3 7 5 7 6 7 6 7 7 6 6

Dari Tabel 3.1 dapat dilihat bahwa dengan titik awal yang berbeda masalah pemrograman

kuadratik

pada

contoh

3.3

akan

memiliki

penyelesaian

(1.400,1.700) . Dengan titik awal yang tepat maka akan mudah ditemukan ken-

dala aktif dan lebih cepat konvergen hanya dengan menggunakan beberapa iterasi.


BAB IV PENUTUP

A. Kesimpulan Berdasarkan pembahasan pada bab-bab sebelumnya, dapat ditarik beberapa kesimpulan sebagai-berikut: 1. Masalah pemrograman kuadratik konveks dapat diselesaikan dengan menggunakan Metode Himpunan Aktif. Dalam Metode Himpunan Aktif, yang diselesaikan adalah submasalah pemrograman kuadratik konveks dengan memanfaatkan sebuah himpunan kerja. Himpunan kerja tersebut terdiri dari kendala-kendala pertidaksamaan aktif yang memiliki nilai nol pada penyelesaiannya sehingga dapat digantikan oleh kendala berupa persamaan, sedangkan kendala pertidaksamaan tidak aktif dihilangkan dari himpunan kerja. Kemudian dicari penyelesaian untuk arah layak. Jika arah layak sama dengan nol dan syarat Karush-Kuhn-tucker dipenuhi maka iterasi dihentikan dan diperoleh penyelesaian dari masalah pemrograman kuadratik konveks tersebut. Jika sebaliknya, maka perlu dibangun himpunan kerja yang lain dan diselesaikan submasalah baru. 2. Setiap langkah dari metode himpunan aktif dimulai dari menentukan sebarang titik dan himpunan kerja, kemudian dicari peminimum fungsi dengan menyelesaikan submasalah pemrograman kuadratik. 3. Keistimewaan dari Metode Himpunan Aktif yaitu:


118

a. Lebih sederhana karena tidak semua kendala digunakan untuk mencari peminimum fungsi. b. Dapat pula digunakan untuk menyelesaikan masalah pemrograman kuadratik dengan kendala berupa persamaan maupun pertidaksamaan.

B. Saran Berikut diberikan permasalahan yang berhubungan dengan Metode Himpunan Aktif dan juga beberapa metode kepada pembaca yang dapat dibahas lebih lanjut, yaitu: 1. Metode Himpunan Aktif untuk menyelesaikan masalah pemrograman kuadratik dual 2. Metode dual dan metode proyeksi gradien yang dapat pula digunakan untuk menyelesaikan masalah pemrograman kuadratik.


119

DAFTAR PUSTAKA Bartle, R. G. & Sherbert, D.R. (2000). Introduction to Real Analysis (4th ed). New York: John Willey & Sons, Inc Bellman, R. (1970). Introduction to Matrix Analysis (2nd ed). New York: McGrawHill Book Company. Budhi, W. S. (1995). Aljabar Linear. Jakarta: Gramedia. Folland, G. B. (1999). Real Analysis Modern Techniques and Their Applications (2nd ed). New York: John Wiley. Hadley, G. (1972). Nonlinear and Dynamic Programming (2nd ed). Menlo Park: Addison-Wesley. Hiller, F. S. & Lieberman, G. J. (1995). Introduction to Mathematical Programming (2nd ed). New York: McGraw-Hill, Inc. Leon, S. J. (2001). Aljabar Linear dan Aplikasinya (Terjemahan). Edisi kelima. Jakarta: Erlangga. Lipschutz, S. & Lipson, M. L. (2001). Seri Penyelesaian Soal Schaum Matematika Diskret 1 (Terjemahan). Edisi pertama. Jakarta: Salemba Teknika. Nocedal, J. & Wright, S. J. (2006). Numerical Optimization (2nd ed). New York: Springer. Peressini, A.L., Sullivan, F.E. & J. J. Uhl, Jr. (1988). The Mathematics of Nonlinear programming. New York: Springer. Sun, W. & Yuan, Y. (2006). Optimization Theory and Methods. New York: Springer. Sundaram, R. K. (1996). A First Course in Optimization Theory. New York: Cambridge University Press.


LAMPIRAN PROGRAM UTAMA: Listing Program

fprintf('\n\n\n\n'); clear clc warning off all disp('---------------------------------------------------------'); disp('---------------------------------------------------------'); disp(' Algoritma Metode Himpunan Aktif '); disp('untuk Menyelesaikan Masalah Pemrograman Kuadratik Konveks'); disp(' min Q(x)={[(1/2)x^(T)Gx]+[g^(T)x]} '); disp(' x '); disp(' Kendala '); disp(' (a(i)^T)x - b(i)= 0 untuk i di E '); disp(' (a(i)^T)x - b(i)>= 0 untuk i di I '); disp('---------------------------------------------------------'); disp(' oleh '); disp(' Yudith Kase '); disp(' 08 3114 014 '); disp('---------------------------------------------------------'); disp(' Contoh 3.3 dengan Program Matlab '); disp('---------------------------------------------------------'); x0=input(' masukkan nilai x0 = '); G =input(' masukkan G = '); g =input(' masukkan g = '); a1=input(' masukkan a1 = '); a2=input(' masukkan a2 = '); a3=input(' masukkan a3 = '); a4=input(' masukkan a4 = '); a5=input(' masukkan a5 = '); b1=input(' masukkan b1 = '); b2=input(' masukkan b2 = '); b3=input(' masukkan b3 = '); b4=input(' masukkan b4 = '); b5=input(' masukkan b5 = '); disp('---------------------------------------------------------'); disp(' HASIL '); disp('---------------------------------------------------------'); disp('---------------------------------------------------------'); A=[a1;a2;a3;a4;a5]; x=x0; b=[b1;b2;b3;b4;b5]; C=A*x-b; Sk=find (C==0);

120


display(' k x(1) x(2)') fprintf('\n%15.0f%15.3f%15.3f',1,x(1),x(2)) for k=1:1000 if length(Sk)>=1 for i=1:length(Sk) B(i,:)=A(Sk(i),:); Abaru=B'; end Abaru; gk=G*x+g; S=([G -Abaru; -Abaru' zeros(size(Abaru',1),size(Abaru,2))]^(-1))*-[gk; zeros(size(Abaru',1),1)]; for i=1:length(x) d0(i)=S(i); end d0; for i=1:size(Abaru',1) lmd0(i)=S(2+i); end lmd0; if abs(d0)<=10^(-3) if lmd0>=0 break else i=find(lmd0==min(lmd0)); Sk(i)=[ ]; B(i,:)=[ ]; lmd0(:,i)=[ ]; xbaru=x; Sk=Sk; end k=k+1; else I=1:length(A); I(Sk)=[ ]; for i=1:length(I) E(i)=(b(i)-A(i,:)*x)/(A(i,:)*d0'); end p=find(E>0); alfa=min(1,min(E(p))); x=x+alfa*d0'; if alfa~=1 I; for i=1:length(I) BB(i)=(A(I(i),:)*x); end B; bb=b(I); j=find(BB-bb'==0); Sk=union(Sk,j); Sk=Sk;

121


k=k+1; else Sk=Sk; k=k+1; end end else gk=G*x+g; S=G^(-1)*-gk; for i=1:length(x) d0(i)=S(i); end d0; if abs(d0)<=10^(-2) if lmd0>=0 break else xbaru=x; Sk=Sk; end k=k+1; else I=1:length(A); I(Sk)=[ ]; for i=1:length(I) E(i)=(b(i)-A(i,:)*x)/(A(i,:)*d0'); end E; p=find(E>0); alfa=min(1,min(E(p))); x=x+alfa*d0'; if alfa~=1 j=find(b==A*x); Sk=union(Sk,j) ; Sk=Sk; k=k+1; else Sk=Sk; k=k+1; end end end fprintf('\n%15.0f%15.3f%15.3f',k,x(1),x(2)) end fprintf('\n') disp(' '); disp('-------------------------------------------------------'); disp('-------Terimakasih Telah Menggunakan Program Ini-------');

122


123

OUTPUT ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Algoritma Metode Himpunan Aktif untuk Menyelesaikan Masalah Pemrograman Kuadratik Konveks ------------------------------------------------------------------------------------------------------oleh Yudith Kase 08 3114 014 ------------------------------------------------------------------------------------------------------Contoh 3.3 dengan Program Matlab ------------------------------------------------------------------------------------------------------masukkan nilai x0 = [2;0] masukkan G = [2 0;0 2] masukkan g = [-2;-5] masukkan a1 = [1 -2] masukkan a2 = [-1 -2] masukkan a3 = [-1 2] masukkan a4 = [1 0] masukkan a5 = [0 1] masukkan b1 = -2 masukkan b2 = -6 masukkan b3 = -2 masukkan b4 = 0 masukkan b5 = 0 ------------------------------------------------------------------------------------------------------HASIL ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------k x(1) x(2) 1 2 3 4 5 6

2.000 2.000 1.000 1.000 1.000 1.400

0.000 0.000 0.000 0.000 1.500 1.700

------------------------------------------------------------------------------------------------------------------------------Terimakasih Telah Menggunakan Program Ini---------------------->>

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents