PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
METODE TITIK-INTERIOR PADA PEMROGRAMAN KUADRATIK KONVEKS
Skripsi Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika
Oleh: Fenny Basuki NIM: 083114003
PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2012
i
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
INTERIOR-POINT METHODS IN CONVEX QUADRATIC PROGRAMMING
Research Presented as Partial Fulfillment of the Requirements To Obtain the Sarjana Sains Degree In Mathematics
By: Fenny Basuki Student Number: 083114003
MATHEMATICS STUDY PROGRAM MATHEMATICS DEPARTMENT SCIENCE AND TECHNOLOGY FACULTY SANATA DHARMA UNIVERSITY YOGYAKARTA 2012
ii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Yesus berfirman : “Janganlah Janganlah hendaknya kamu kuatir tentang apapun juga, tetapi nyatakanlah dalam segala hal keinginanmu dalam Allah dalam doa dan permohonan dengan ucapan syukur.” (Filipi 4:6)
Karya ini ku persembahkan untuk: Tuhan Yesus dan Bunda Maria sumber inspirasi ku, Papi, mami, serta adik adik-adikku yang selalu memberi perhatian, kasih sayang dan membimbingku membimbingku.
vi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ABSTRAK
Penyelesaian pemrograman kuadratik konveks secara analitik memerlukan langkah yang panjang. Pada skripsi ini akan dipaparkan metode numerik yang dapat digunakan untuk menyelesaikan permasalahan tersebut, yakni metode titik-interior primal-dual. Metode titik-interior primal-dual merupakan suatu metode untuk menemukan penyelesaian primal-dual dengan menerapkan metode Newton dan memodifikasi arah selidik dan panjang langkah. Tujuan dari metode ini adalah membatasi pergerakan nilai optimum yang dihasilkan pada setiap iterasinya dengan toleransi tertentu. Pencarian penyelesaian optimum dimulai dari sebarang titikinterior, sehingga konvergensinya cepat diperoleh.
Kata kunci: Karush Kuhn Tucker, metode titik-interior primal-dual, pemrograman kuadratik konveks, penyelesaian optimum. .
viii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ABSTRACT
Solving the convex quadratic programming need a long step when it is finished analytically. In this thesis, numerical method will be introduced which can be used to solve this problem, namely a primal-dual interior-point method. Primal-dual interiorpoint method is a method to find the primal-dual solution by applying Newton method and modifying the search direction and step-length. This method purpose to restricting the movement of the optimum value generated from each iteration method with certain tolerances. Optimum solution search start from the any interior-point so that the convergence will be faster to obtain.
Key word: Karush Kuhn Tucker, primal-dual interior-point method, convex quadratic programming, optimum solution.
ix
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
KATA PENGANTAR Puji syukur kepada Tuhan Yesus atas anugerah dan karunia-Nya sehingga penulisan skripsi ini dapat terselesaikan. Skripsi ini berjudul: “METODE TITIKINTERIOR PADA PEMROGRAMAN KUADRATIK KONVEKS”, yang diajukan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika, Jurusan Matematika, Fakultas Sains dan Teknologi, Universitas Sanata Dharma Yogyakarta. Penulisan skripsi ini tidak lepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, dengan segala kerendahan hati penulis ingin menyampaikan ucapan terima kasih kepada: 1. Lusia Krismiyati Budiasih, S.Si., M.Si., selaku dosen pembimbing dan Kaprodi Matematika FST-USD yang dengan rendah hati mau meluangkan banyak waktu dan penuh kesabaran telah membimbing penulis selama penyusunan skripsi. 2. P. H. Prima Rosa, S.Si., M.Sc., selaku Dekan FST-USD. 3. MV. Any Herawati, S.Si., M.Si., selaku dosen pembimbing akademik dan dosen penguji. 4. Dominikus Arif Budi Prasetyo, S.Si., M.Si., selaku dosen penguji. 5. A. Prasetyadi, S.Si., M.Si., dan Prof. Drs. R. Soemantri yang telah banyak membantu dan memberi masukan kepada penulis. 6. Herry Pribawanto Suryawan, S.Si., M.Si. yang yang pernah menjadi dosen pembimbing akademik dan telah banyak membantu dan memberi masukan kepada penulis. x
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
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 .................................................................................
xiv
DAFTAR TABEL ......................................................................................
xv
BAB I PENDAHULUAN ..........................................................................
1
A. Latar Belakang Masalah ..............................................................
1
B. Perumusan Masalah .....................................................................
4
C. Batasan Masalah ..........................................................................
5
D. Tujuan Penulisan .........................................................................
5
E. Manfaat Penulisan .......................................................................
5
F. Metode Penulisan .........................................................................
5
G. Sistematika Penulisan....................................................................
6
BAB II HIMPUNAN KONVEKS DAN TEORI OPTIMISASI DALAM ..................................................................................
xii
8
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
A. Matriks dan Ruang Vektor ..........................................................
8
B. Fungsi Terdiferensial ...................................................................
41
C. Himpunan Konveks dan Fungsi Konveks ...................................
55
D. Teori Optimisasi ..........................................................................
72
E. Metode Newton untuk Sistem Persamaan Nonlinear ..................
85
BAB III METODE TITIK-INTERIOR .....................................................
91
A. Pemrograman Kuadratik Konveks ..............................................
91
B. Metode Titik-Interior ..................................................................
94
BAB IV PENUTUP ...................................................................................
120
A. Kesimpulan .................................................................................
120
B. Saran ............................................................................................
121
DAFTAR PUSTAKA ................................................................................
122
LAMPIRAN ...............................................................................................
124
xiii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR GAMBAR Halaman Gambar 1.1.1 Minimum sama dengan maksimum ................
2
Gambar 2.1.1 Lingkaran 1 ....................................................
30
Gambar 2.1.2 Himpunan Terurut ................................................................
38
Gambar 2.2.1 Teorema Nilai Rata-Rata .....................................................
45
Gambar 2.3.1 Ilustrasi dari Himpunan Konveks ........................................
56
Gambar 2.3.2 Lingkaran x 2 + y 2 = 1 .........................................................
57
Gambar 2.3.3 Contoh Fungsi Konveks ......................................................
58
Gambar 3.2.1 Diagram Alir Algoritma Metode Titik-Interior Primal-Dual .........................................................................
xiv
107
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR TABEL Halaman Tabel 3.2.1 Output Penyelesaian Contoh 3.2.1 dengan Matlab ................
117
Tabel 3.2.2 Tabel Perbandingan Nilai Awal Metode Titik-Interior Primal-Dual .........................................................................
xv
118
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB I PENDAHULUAN
A. Latar Belakang Masalah Saat ini semakin banyak permasalahan pada kehidupan sehari-hari yang memerlukan pendekatan optimisasi dalam penyelesaiannya. Sebagai contoh, misalkan sebuah perusahaan ingin meminimumkan biaya pembuatan dua produk. Untuk menyelesaikan permasalahan ini, maka harus diketahui hal-hal apa saja yang mempengaruhi pembuatan dua produk tersebut, misalnya jumlah bahan baku yang tersedia. Misalkan, meminimumkan biaya pembuatan dua produk dinyatakan dengan fungsi f . Sedangkan, banyaknya barang yang dihasilkan dari masing-masing produk, misalnya , . Variabelvariabel tersebut perlu diberi batasan yang disebut dengan kendala, dalam hal ini berupa jumlah bahan baku yang tersedia, sedangkan fungsi , disebut dengan fungsi obyektif. Optimisasi secara matematis dapat diartikan sebagai proses menemukan penyelesaian yang memaksimumkan atau meminimumkan suatu fungsi. Untuk menemukan penyelesaian dari masalah memaksimumkan suatu fungsi dapat diselesaikan dengan cara mencari penyelesaian dari masalah meminimumkan negatif dari fungsi tersebut.
1
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2
Untuk lebih jelasnya, perhatikan Gambar 1.1.1:
Gambar 1.1.1 Minimum ݂ሺݔሻ sama dengan maksimum െ݂ሺݔሻ
Berdasarkan Gambar 1.1.1, (dalam hal ini sebagai contoh ݂ሺݔሻ adalah suatu fungsi dengan satu variabel) dapat dilihat bahwa jika suatu titik כ ݔmenunjukkan nilai pembuat minimum dari fungsi ݂ሺݔሻ, maka titik yang sama itu juga menunjukkan nilai pembuat maksimum dari negatif fungsi tersebut, yakni െ݂ሺݔሻ. Pendekatan optimisasi sendiri menyediakan banyak alternatif metode yang dapat dipilih sesuai dengan karakteristik permasalahan yang akan diselesaikan. Permasalahan optimisasi terbagi menjadi dua bagian, yaitu permasalahan optimisasi berkendala dan permasalahan optimisasi tidak berkendala. Permasalahan optimisasi berkendala adalah optimisasi suatu fungsi, yang disebut fungsi obyektif, dengan kendala-kendala berupa pertidaksamaaan atau
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
3
persamaan. Sedangkan, permasalahan optimisasi tidak berkendala adalah optimisasi suatu fungsi obyektif tanpa kendala. Secara garis besar, permasalahan dalam teknik optimisasi dapat berupa permasalahan pemrograman linear maupun nonlinear. Pemrograman linear adalah pemrograman yang mempelajari kasus dimana fungsi obyektifnya adalah fungsi linear dan kendalanya merupakan persamaaan atau pertidaksamaan linear. Sedangkan, pemrograman nonlinear adalah pemrograman yang mempelajari kasus dimana salah satu fungsi obyektif atau fungsi kendalanya merupakan persamaaan atau pertidaksamaan nonlinear. Salah satu subklas dalam permasalahan pemrograman nonlinear adalah pemrograman kuadratik konveks. Pemrograman kuadratik konveks adalah permasalahan optimisasi berkendala nonlinear dimana fungsi obyektifnya adalah fungsi kuadratik konveks, sedangkan kendala-kendalanya merupakan persamaan atau pertidaksamaan linear. Fungsi kuadratik konveks pada fungsi obyektif yang terdapat dalam pemrograman kuadratik konveks memiliki bentuk ଵ
umum ܳሺܠሻ ൌ ଶ ܠܩ ் ܠ ் ܠdengan G adalah matriks semidefinit positif. Metode yang dapat digunakan untuk menyelesaikan permasalahan optimisasi pada pemrograman kuadratik konveks antara lain adalah metode himpunan aktif dan metode titik-interior. Metode titik-interior pada pemrograman kuadratik terbagi lagi menjadi dua, yakni metode jalur pusat (central path method) dan metode titik-interior primal-dual (primal-dual interior-point me-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
4
thod). Namun dalam skripsi ini metode yang akan dibahas hanya metode titikinterior primal-dual. Metode titik-interior primal-dual merupakan salah satu metode numerik yang menerapkan metode Newton dalam menyelesaikannya. Pada metode titik-interior primal-dual, pencarian penyelesaian optimum dimulai dari sebarang titik-interior sehingga akan menghasilkan iterasi yang lebih sedikit karena konvergensinya lebih cepat diperoleh.
B. Perumusan Masalah Berdasarkan uraian yang dikemukakan dalam latar belakang, pokok– pokok permasalahan yang akan dibahas dalam tulisan ini dapat dirumuskan sebagai berikut : 1. Apa yang dimaksud dengan pemrograman kuadratik konveks? 2. Apa yang dimaksud dengan metode titik-interior primal-dual untuk menyelesaikan permasalahan optimisasi berkendala pada pemrograman kuadratik konveks? 3. Bagaimana cara menyelesaikan pemrograman kuadratik konveks dengan menggunakan metode titik-interior primal-dual? 4. Bagaimana mengimplementasikan metode titik-interior primal-dual dengan menggunakan Matlab?
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
5
C. Batasan Masalah Pembatasan masalah metode titik-interior primal-dual dalam skripsi ini hanya dibatasi untuk pemrograman kuadratik konveks dengan kendalakendala berupa pertidaksamaan.
D. Tujuan Penulisan Tujuan penulisan skripsi ini adalah untuk menyelesaikan permasalahan optimisasi berkendala dengan menggunakan metode titik-interior primaldual pada pemrograman kuadratik konveks serta bagaimana mengimplementasikan metode titik-interior primal-dual dengan menggunakan Matlab.
E. Manfaat Penulisan Manfaat yang diharapkan dalam skripsi ini adalah dapat memahami bagaimana penggunaan metode titik-interior primal-dual pada pemrograman kuadratik konveks serta dapat mengimplementasikan metode titik-interior primal-dual dengan menggunakan Matlab.
F. Metode Penulisan Metode yang digunakan penulis dalam skripsi ini adalah metode studi pustaka, yaitu dengan mempelajari buku-buku yang berkaitan dengan topik metode titik-interior primal-dual pada pemrograman kuadratik konveks.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
6
G. Sistematika Penulisan Sistematika penulisan skripsi ini terdiri dari empat bab dengan urutan sebagai berikut:
BAB I
:
PENDAHULUAN Dalam bab ini akan dibahas mengenai latar belakang masalah, perumusan masalah, batasan masalah, tujuan penulisan, manfaat penulisan, metode penulisan, dan sistematika penulisan.
BAB II
:
HIMPUNAN KONVEKS DAN TEORI OPTIMISASI DALAM Թ Dalam bab ini akan dibahas mengenai matriks dan ruang vektor, fungsi terdiferensial, himpunan konveks dan fungsi konveks, teori optimisasi, dan metode Newton untuk sistem persamaan nonlinear yang akan digunakan untuk memahami metode titik-interior primal-dual.
BAB III :
METODE TITIK-INTERIOR Dalam bab ini akan dibahas mengenai pemrograman kuadratik konveks, metode titik-interior, konsep metode titik-interior primal dual, algoritma metode titik-interior primal-dual beserta
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
7
contoh permasalahan pemrograman kuadratik konveks yang diselesaikan dengan metode titik-interior primal-dual, dan yang terakhir akan dibahas juga implementasinya dengan menggunakan program Matlab.
BAB IV : PENUTUP Bab ini berisi kesimpulan dan saran.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB II HIMPUNAN KONVEKS DAN TEORI OPTIMISASI DALAM
Dalam bab ini akan dibahas mengenai matriks dan ruang vektor, fungsi terdiferensial, himpunan konveks dan fungsi konveks, teori optimisasi, dan metode Newton untuk sistem persamaan nonlinear yang akan digunakan untuk memahami metode titik-interior primal-dual.
A. Matriks dan Ruang Vektor Pada subbab ini akan dibahas mengenai matriks, panjang (norm), jarak, ruang vektor, dan beberapa definisi serta teorema dasar tentang analisis real.
Definisi 2.1.1 (Ruang Berdimensi n) Jika n adalah suatu bilangan bulat positif, maka tupel n berurutan adalah suatu urutan dari n bilangan real , , … , . Himpunan semua tupel n berurutan disebut ruang berdimensi n dan dinyatakan sebagai .
8
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
9
Definisi 2.1.2 (Matriks) Matriks adalah jajaran empat persegi panjang dari bilangan-bilangan yang diatur menurut baris dan kolom. Bilangan-bilangan dalam jajaran tersebut disebut dengan elemen dari matriks.
Elemen-elemen yang terletak pada baris i dan kolom j di dalam ma-
triks A dapat dinyatakan sebagai . Sehingga, matriks secara umum dapat di-
tulis sebagai berikut:
Atau lebih singkat dapat ditulis sebagai atau . Definisi 2.1.3 (Matriks Simetrik) Sebuah matriks bujur sangkar A adalah simetrik jika dan hanya jika A = AT.
Definisi 2.1.4 (Matriks Definit Positif dan Matriks Semidefinit Positif) Misalkan A adalah matriks simetrik.
A dikatakan definit positif jika xTAx > 0, , 0.
A dikatakan semidefinit positif jika xTAx ≥ 0, .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
10
Dari Definisi 2.1.4, dapat disimpulkan bahwa jika A adalah matriks definit positif, maka A juga adalah matriks semidefinit positif.
Untuk lebih memahami definisi matriks, matriks simetrik, matriks definit positif dan matriks semidefinit positif, maka akan diberikan contoh berikut.
Contoh 2.1.1 Misalkan diberikan suatu matriks simetrik: 2 1 0
1 0 2 1 1 2
Untuk mengkaji bahwa matriks A adalah matriks definit positif, maka harus ditunjukkan bahwa xTAx > 0, , 0. !
!
!
!
2 1 0 ! ! 1 2 1 ! 0 1 2 ! 2! ! ! ! " 2! ! ! " 2!
! #2! ! $ " ! #! " 2! ! $ " ! #! " 2! $ 2! ! ! ! ! " 2! !% !& !% !& " 2! 2! 2! ! " 2! 2!% !& " 2!
! " #! 2! ! " ! $ " #! 2!% !& " ! $ " !
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
11
! " #! ! $ " #!% !& $ " !
Dari sini dapat disimpulkan bahwa matriks A bersifat definit positif karena ! " #! ! $ " #!% !& $ " ! ' 0, , kecuali jika ! ! ! 0. ▄
Contoh 2.1.2 Misalkan diberikan suatu matriks simetrik: 2 () 0
0 * 2
Untuk mengkaji bahwa matriks G adalah matriks semidefinit positif, maka ha-
rus ditunjukkan bahwa xTGx ≥ 0, . ( ! !
! ! )2 0* ) * ! 0 2
! +2! , 2!
! #2! $ " ! #2! $ 2! " 2!
Karena ( 2! " 2! - 0, , maka dapat disimpulkan bahwa matriks G adalah matriks semidefinit positif. ▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
12
Definisi 2.1.5 (Ruang Vektor)
Misalkan . adalah himpunan tak kosong yang dilengkapi dengan operasi pen-
jumlahan dan perkalian skalar dengan bilangan real. Artinya, bila diberikan dua elemen / dan 3 di . dan , 5 , maka penjumlahan / " 3 dan perka-
lian skalar / didefinisikan dan terletak di V juga. Kemudian V dengan kedua
operasi ini disebut ruang vektor jika kedua operasi tersebut memenuhi aksi-
oma-aksioma berikut.
Untuk setiap /, 3, 6 . dan , 5 berlaku: (i)
(ii) (iii) (iv) (v) (vi) (vii)
/ " 3 3 " /.
/ " #3 " 6$ #/ " 3$ " 6.
Ada elemen 7 . sehingga / " 7 /.
Ada elemen / . sehingga / " #/$ 7.
#/ " 3$ / " 3.
# " 5$/ / " 5/. #5$/ #5/$.
(viii) 1/ /.
Untuk lebih memahami definisi ruang vektor, maka akan diberikan contoh berikut.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Contoh 2.1.3
13
Buktikan bahwa 8#9 , 9 , … , 9 $|9 , 9 , … , 9 < adalah
ruang vektor!
Bukti:
Misalkan / #9 , 9 , … , 9 $ dan 3 #= , = , … , = $, maka
/ " 3 #9 " = , 9 " = , … , 9 " = $ dan / #9 , 9 , … , 9 $.
a) / " 3 #9 " = , 9 " = , … , 9 " = $
#= " 9 , = " 9 , … , = " 9 $ 3"/
b) #/ " 3$ " 6 >#9 " = , 9 " = , … , 9 " = $? " #@ , @ , … , @ $
>#9 , 9 , … , 9 $ " #= , = , … , = $? " #@ , @ , … , @ $ #9 , 9 , … , 9 $ " #= , = , … , = $ " #@ , @ , … , @ $
#9 , 9 , … , 9 $ " ##= , = , … , = $ " #@ , @ , … , @ $$ #9 , 9 , … , 9 $ " #= " @ , = " @ , … , = " @ $ / " #3 " 6$
c) / " 7 #9 , 9 , … , 9 $ " #0, 0, … , 0$ #9 " 0, 9 " 0, … , 9 " 0$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
#9 , 9 , … , 9 $ /
d) / " #/$ #9 , 9 , … , 9 $ " #9 , 9 , … , 9 $
#9 " #9 $, 9 " #9 $, … , 9 " #9 $$ #0, 0, … , 0$ 7
e) #/ " 3$ #9 " = , 9 " = , … , 9 " = $
##9 , 9 , … , 9 $ " #= , = , … , = $$ #9 , 9 , … , 9 $ " #= , = , … , = $ / " 3
f) # " 5$/ # " 5$#9 , 9 , … , 9 $
># " 5$9 , # " 5$9 , … , # " 5$9 ?
#9 " 59 , 9% " 59% , … , 9 " 59 $
#9 , 9 , … , 9 $ " #59 , 59 , … , 59 $ #9 , 9 , … , 9 $ " 5#9 , 9 , … , 9 $ / " 5/
g) #5$/ #5$#9 , 9 , … , 9 $
14
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
15
>#5$9 , #5$9 , … , #5$9 ?
##59 $, #59 $, … , #59 $$ #59 , 59 , … , 59 $ #5/$
h) 1/ 1#9 , 9 , … , 9 $
#19 , 19 , … , 19 $ #9 , 9 , … , 9 $ /
Karena 8#9 , 9 , … , 9 $|9 , 9 , … , 9 < dengan operasi penjumlahan dan perkalian skalar memenuhi aksioma-aksioma seperti pada Definisi 2.1.5, maka terbukti bahwa adalah ruang vektor.
▄
Definisi 2.1.6 (Ruang Hasil Kali Dalam)
Hasil kali dalam pada adalah sebuah fungsi yang mengasosiasikan se-
buah bilangan real A, BC dengan sepasang vektor x dan y di , sehingga ak-
sioma-aksioma berikut ini terpenuhi bagi semua vektor x, y, dan z di dan
semua bilangan skalar s. (i) (ii)
A, BC AB, C
A " B, DC A, DC " AB, DC
(Aksioma Kesimetrian) (Aksioma Penjumlahan)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
(iii) (iv) (v)
AE, BC EA, BC A, C - 0
A, C 0 jika dan hanya jika 0
16
(Aksioma Homogenitas) (Aksioma Positivitas)
Sebuah ruang vektor real yang memiliki sebuah hasil kali dalam disebut ruang hasil kali dalam.
Untuk lebih memahami sifat hasil kali dalam yang pertama, yakni
A, BC AB, C , maka akan diberikan contoh berikut. Contoh 2.1.4
H ! ! H Untuk F G dan B F G adalah sembarang vektor-vektor di , bukti!
H
kan jika A, BC B, maka B AB, C! Bukti:
H ! ! H Ambil sebarang vektor F G dan B F G dalam ruang vektor . !
H
Akan dibuktikan A, BC B memenuhi A, BC AB, C. B !
!
H H … ! F G H
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
17
! H " ! H " … " ! H
H ! " H ! " … " H !
H
H
B
! ! … H F G !
AB, C
Jadi, terbukti bahwa A, BC AB, C. ▄
Definisi 2.1.7 (Panjang atau Norm)
Panjang atau norm sebuah vektor di dinotasikan dengan LL dan didefinisikan sebagai
LL A, CN # · $N P! " ! " … " ! . M
M
Sebuah pemetaan L . L dikatakan sebuah norm jika dan hanya jika
memenuhi sifat berikut: (1) (2) (3) (4)
LL - 0,
LL 0 jika dan hanya jika x = 0,
LαL |R|LL, R ,
L " BL S LL " LBL, , B (Ketaksamaan segitiga)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
18
Definisi 2.1.8 (Ortogonal)
Dua vektor u dan v di dalam ruang hasil kali dalam di dikatakan ortogonal jika A/, 3C 0.
Teorema 2.1.1 (Hukum Phytagoras) Jika u dan v adalah vektor-vektor ortogonal di dalam ruang hasil kali dalam di , maka
L/ " 3L L/L " L3L .
Bukti:
L/ " 3L A/ " 3, / " 3C
A/, /C " A/, 3C " A3, /C " A3, 3C A/, /C " A/, 3C " A/, 3C " A3, 3C A/, /C " 2A/, 3C " A3, 3C
▄
L/L " L3L
Definisi 2.1.9 (Proyeksi Skalar dan Proyeksi Vektor)
Jika u dan v adalah vektor-vektor di dalam ruang hasil kali dalam di dan
3 0, maka proyeksi skalar dari u pada v diberikan oleh R
proyeksi vektor dari u pada v diberikan oleh T R UL3L 3V
A/,3C A3,3C
3.
A/,3C L3L
dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
19
Teorema 2.1.2
Jika 3 0 dan p adalah proyeksi vektor dari u pada v, maka / T dan p adalah ortogonal.
Bukti:
Karena AT, TC AL3L 3, L3L 3C UL3LV A3, 3C R dan A/, TC W
W
W
#A/,3C$ A3,3C
R.
Ini mengakibatkan A/ T, TC A/, TC AT, TC R R 0. Oleh karena
itu, / T dan p adalah ortogonal. ▄
Teorema 2.1.3 (Ketaksamaan Cauchy-Schwarz)
Jika u dan v adalah vektor-vektor di dalam ruang hasil kali dalam di , maka |A/, 3C| S L/LL3L
Bukti:
Jika 3 0, maka |A/, 3C| 0 L/LL3L. Jika 3 0, maka misalkan p seba-
gai proyeksi vektor dari u pada v. Karena p ortogonal pada / T, maka me-
nurut Hukum Phytagoras
LTL " L/ TL L/L
X LTL L/L L/ TL X R L/L L/ TL
(dari Teorema 2.1.2)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
X
20
#A/, 3C$ L/L L/ TL L3L
X #A/, 3C$ L/L L3L L/ TL L3L S L/L L3L
Dengan mengambil akarnya, maka diperoleh |A/, 3C| S L/LL3L.
▄
Untuk lebih memahami definisi norm serta sifat-sifat dari norm, maka akan diberikan contoh berikut.
Contoh 2.1.5 Buktikan bahwa
Z
LL Y|! | [\
adalah norm!
Bukti:
Untuk membuktikan bahwa LL adalah norm, maka harus ditunjukkan bahwa LL memenuhi keempat sifat dari norm.
Misalkan, x dan y adalah sebarang vektor di dan R adalah sebarang bila-
ngan real. (1)
Akan dibuktikan bahwa LL - 0
Karena ! - 0 untuk sebarang bilangan real ! , maka
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
21
Z
LL Y|! | - 0 [\
(2)
Akan dibuktikan bahwa LL 0 jika dan hanya jika 0. Jika 0, maka ! 0, ].
Oleh karena itu, ∑Z[\|! | 0 dan LL 0.
Sebaliknya, jika LL 0, maka ∑Z[\|! | 0.
Karena |! | - 0, dengan demikian ∑Z[\|! | 0 hanya dipenuhi jika |! | 0 sehingga 0. (3)
Akan dibuktikan bahwa LRL |R|LL , R , .
LRL Y|R! | \
|R| _Y|! |` \
|R|LL (4)
Akan dibuktikan bahwa L " BL S LL " LBL .
L " BL Y|! " H | \
S Y|! | " Y|H | \
\
#Sifat nilai mutlak$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
22
LL " LBL
▄
Jadi, L " BL S LL " LBL .
Teorema 2.1.4 (Ketaksamaan Cauchy-Buniakowski-Schwarz)
Misalkan , B , maka
gY ! H g S LL LBL \
Bukti:
Pertidaksamaan |∑hi\j ! H | S LL LBL akan bersifat trivial jika dan hanya
jika 0 atau B 0. Oleh karena itu, andaikan bahwa dan B, keduanya taknol. Misalkan, k adalah sebarang bilangan real. Maka,
0 S L " kBL Y#! " kH $
\
Y ! " 2k Y ! H " k Y H \
\
\
LL " 2k Y ! H " k LBL
\
Misalkan, LBL , 5 ∑hi\j ! H , dan l LL . Sehingga pertidaksa
maan menjadi k " 25k " l - 0 untuk semua k . Hal ini dapat terjadi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
23
jika dan hanya jika diskriminan atau m #25$ 4l 45 4l o 0.
Karena itu, 5 o l. Dengan mensubstitusikan nilai dari , 5, dan l, maka di-
peroleh
_Y ! H ` S LL LBL \
Dengan mengambil akarnya, maka diperoleh
gY ! H g S LL LBL \
▄
Contoh 2.1.6 Buktikan bahwa
LL _Y ! ` \
p
adalah norm!
Bukti:
Untuk membuktikan bahwa LL adalah norm, maka harus ditunjukkan bah-
wa LL memenuhi keempat sifat dari norm.
Misalkan, x dan y adalah sebarang vektor di dan R adalah sebarang bila-
ngan real.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
(1)
24
Akan dibuktikan bahwa LL - 0 .
Karena ! - 0 untuk sebarang bilangan real ! , maka
LL #Y ! $/ - 0 \
(2)
Akan dibuktikan bahwa LL 0 jika dan hanya jika 0.
Jika 0, maka ! 0, ].
Oleh karena itu, ∑hi\j ! 0 dan LL 0.
Sebaliknya, jika LL 0, maka ∑hi\j ! 0.
Karena ! - 0, dengan demikian #∑hi\j ! $/ 0 hanya dipenuhi jika ! 0 sehingga 0.
(3)
Akan dibuktikan bahwa LRL |R|LL , R , .
LRL _Y#R! $ ` \
/
/
_R Y ! ` \
|R| _Y ! ` \
|R|LL
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
(4)
25
Akan dibuktikan bahwa L " BL S LL " LBL .
L " BL
Y#! " H $ \
Y ! " 2 Y ! H " Y H \
\
\
S LL " 2 gY ! H g " LBL
\
S LL " 2LL LBL " LBL
#LL " LBL $
#Sifat nilai mutlak$
# Ketaksamaan
Cauchy-
Buniakowski-Schwarz)
Dengan mengambil akarnya, maka diperoleh
▄
L " BL S LL " LBL .
Selanjutnya, akan diberikan definisi dan sifat jarak pada . Definisi 2.1.10 (Jarak)
Jarak antara dua buah titik titik dan B dinotasikan dengan
r#, B$ L BL A B, BC # B$ · # B$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
26
Teorema 2.1.5 (Sifat-Sifat Jarak pada )
Jika x, y, dan z adalah vektor-vektor pada , maka: (1) L BL - 0
(2) L BL 0 jika dan hanya jika B (3) L DL S L BL " LB DL
(4) L BL LB L Bukti:
(1) Akan dibuktikan bahwa L BL - 0. Bukti:
n L BL ∑ ( xi − yi ) 2 i =1
1/ 2
Karena #! H $ - 0 untuk sebarang bilangan real ! dan H , maka L BL - 0. ▄
(2) Akan dibuktikan bahwa L BL 0 jika dan hanya jika B. Bukti:
Jika B, maka ! H , ].
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
27
Oleh karena itu, ∑ \#! H $ 0 dan L BL 0.
Sebaliknya, jika L BL 0, maka ∑ \#! H $ 0.
Karena #! H $ - 0, dengan demikian ∑ \#! H $ 0 hanya dipe-
nuhi jika ! H 0 sehingga B. ▄
(3) Akan dibuktikan bahwa L DL S L BL " LB DL. Bukti:
L DL L B " B DL
A B " B D, B " B DC
A B, B " B DC " AB D, B " B DC A B, BC " A B, B DC " AB D, BC "AB D, B DC
L BL " A B, B DC " AB D, BC " LB DL L BL " A B, B DC " A B, B DC " LB DL L BL " 2A B, B DC " LB DL
S L BL " 2L BLLB DL " LB DL Cauchy-Schwarz)
#L BL " LB DL$
Dengan mengambil akarnya, maka diperoleh
(Ketaksamaan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
L DL S L BL " LB DL.
Jadi, terbukti untuk L DL S L BL " LB DL. ▄
(4) Akan dibuktikan bahwa L BL LB L. Bukti:
L BL L#1$#B $L |1|LB L
▄
LB L
Teorema 2.1.6 (Hukum Paralelogram) Untuk semua , B
L " BL " L BL 2#LL " LBL $
Bukti:
L " BL " L BL
A " B, " BC " A B, BC
A, " BC " AB, " BC " A, BC AB, BC
A, C " A, BC " AB, C " AB, BC " A, C A, BC AB, C " AB, BC
28
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
29
A, C " AB, BC " A, C " AB, BC 2A, C " 2AB, BC 2LL " 2LBL
2#LL " LBL $ ▄
Selanjutnya, akan diberikan definisi kitar dan titik-interior.
Definisi 2.1.11 (Kitar)
Diberikan titik dan δ > 0. Kitar- δ dari x didefinisikan sebagai st #$ 8B |LB L o δ<
Definisi 2.1.12 (Titik Interior)
Misalkan m v dan m. Titik x dikatakan titik interior dari D
jika ada suatu kitar- δ dari x sedemikian sehingga st #$ v m.
Untuk lebih memahami definisi titik interior, maka akan diberikan contoh berikut.
Contoh 2.1.7
8#! , ! $|! " ! o 1<
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
30
Himpunan ini merepresentasikan titik yang berada di dalam lingkaran dengan pusat (0,0) dan radius 1 seperti pada Gambar 2.1.1.
Gambar 2.1.1 Lingkaran ! " ! o 1 Titik-titik yang berada di dalam lingkaran adalah titik interior. Sedangkan, titik-titik yang berada pada batas dan luar lingkaran bukan merupakan titik interior.
Definisi 2.1.13 (Himpunan Terbuka) Himpunan semua titik interior dari D disebut interior D dan dinotasikan dengan int(D). Selanjutnya, jika int(D) = D, yakni setiap titik dari D adalah titik interior dari D, maka D adalah himpunan terbuka.
Definisi 2.1.14 (Himpunan Tertutup)
Suatu himpunan m v dikatakan tertutup jika dan hanya jika komplemen-
nya adalah terbuka.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
31
Untuk lebih memahami definisi himpunan terbuka, maka akan diberikan contoh berikut.
Contoh 2.1.8 Berdasarkan Contoh 2.1.7, A adalah himpunan terbuka, karena titik-titik yang berada di dalam lingkaran adalah titik interior.
Selanjutnya, akan diberikan definisi relasi dan himpunan terurut secara parsial.
Definisi 2.1.15 (Relasi) Sebuah relasi dari suatu himpunan A ke himpunan B adalah suatu subset R dari X x, di mana X x 8#, 5$: , 5 x<.
Relasi dapat pula ditulis sebagai z 5 yang berarti bahwa #, 5$ z. Definisi 2.1.16 (Himpunan Terurut Secara Parsial) Misalkan R adalah sebuah relasi pada sebuah himpunan S, maka R disebut relasi urutan parsial jika yang memenuhi tiga sifat berikut: (i)
Refleksif
R dikatakan refleksif jika dan hanya jika z untuk setiap {.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
(ii)
(iii)
32
Antisimetris
R dikatakan antisimetris jika dan hanya jika z 5 dan 5 z , maka
5, untuk setiap #, 5$ {. Transitif
R dikatakan transitif jika dan hanya jika z 5 dan 5 z l, maka z l,
untuk setiap #, 5, l$ {.
Himpunan S bersama dengan suatu relasi urutan parsial R pada A dikatakan himpunan terurut secara parsial.
Relasi urutan parsial dari sebuah himpunan S biasanya dinotasikan
dengan S atau -. Relasi S 5 dibaca dengan “a mendahului b”, sedangkan
relasi - b dibaca dengan “a melampaui b”.
Untuk lebih memahami definisi himpunan terurut secara parsial, maka akan diberikan contoh berikut.
Contoh 2.1.9
Perhatikan bilangan bulat positif }. Didefinisikan relasi " membagi 5" de-
ngan |5, jika terdapat sebuah l } sedemikian sehingga l 5. Misalnya, 2|4, 3|12, 7|21, dan seterusnya. Tunjukkan bahwa pembagian adalah sebuah
pengurutan parsial dari }, yakni tunjukkan bahwa berlaku sifat berikut:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
33
a. Refleksif: |.
b. Antisimetris: Jika |5 dan 5| maka 5. c. Transitif: Jika |5 dan 5|l maka |l.
Bukti:
a. Karena · 1 , maka |.
b. Andaikan |5 dan 5|, misalkan 5 dan E5. Maka, 5 E5 se-
hingga E 1. Karena dan E adalah bilangan bulat positif, maka 1 dan E 1. Dengan demikian, 5.
c. Andaikan |5 dan 5|l, misalkan 5 dan l E5. Maka, l E se▄
hingga |l.
Berikut ini diberikan definisi batas atas, supremum, batas bawah, dan infimum.
Definisi 2.1.17 (Batas Atas) Misalkan A adalah himpunan bagian dari sebuah himpunan S yang terurut secara parsial.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
34
Sebuah elemen M dalam S dikatakan sebuah batas atas dari A jika M melampaui setiap elemen dari A, yaitu M adalah sebuah batas atas dari A jika un-
tuk setiap x dalam A diperoleh ! S . Definisi 2.1.18 (Supremum)
Jika sebuah batas atas dari A mendahului setiap batas atas lain dari A maka disebut batas atas terkecil atau supremum dari A yang dinotasikan dengan sup (A).
Definisi 2.1.19 (Batas Bawah) Sebuah elemen m dalam S dikatakan sebuah batas bawah dari A jika m mendahului setiap elemen dari A, yaitu m adalah sebuah batas bawah dari A jika untuk setiap x dalam A diperoleh S !.
Definisi 2.1.20 (Infimum) Jika sebuah batas bawah dari A melampaui setiap batas bawah lain dari A maka disebut batas bawah terbesar atau infimum dari A yang dinotasikan dengan inf (A).
Definisi 2.1.21 (Terbatas ke Atas dan Terbatas ke Bawah) Misalkan { merupakan subhimpunan tak kosong dari .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
35
a. Himpunan { dikatakan terbatas ke atas jika ada bilangan 9 sedemikian sehingga E S 9 untuk semua E {. Setiap bilangan 9 dikatakan batas atas dari {.
b. Himpunan { dikatakan terbatas ke bawah jika ada bilangan @ se-
demikian sehingga @ S E untuk semua E {. Setiap bilangan @ dikata-
kan batas bawah dari {. Lemma 2.1.1
Batas bawah dari himpunan tak kosong { di adalah infimum dari { jika
dan hanya jika ' 0 terdapat ! { sedemikian sehingga " ' !. Bukti #$
Diketahui inf { dan ' 0.
Akan ditunjukkan terdapat ! { sedemikian sehingga " ' !.
Jika 5 batas bawah { maka 5 S .
Karena " ' maka " bukan batas bawah {.
Karena " bukan batas bawah { maka harus ada ! { sehingga " ' !.
#$
Jika suatu batas bawah {, dan untuk setiap ' 0 terdapat ! { sedemikian
sehingga " ' !.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
36
Akan dibuktikan inf {.
Misalkan bahwa 5 suatu batas bawah {. Karena ! { dan 5 suatu batas bawah { maka ! - 5.
Karena " ' ! maka " ' 5.
Jadi untuk setiap ' 0 berlaku " ' 5. Andaikan 5 ' maka jika diambil
akan diperoleh "
sehingga 5 ' " ' dan 5 ' " ' !
yang kontradiksi dengan pernyataan bahwa 5 batas bawah. Jadi, jika 5 batas
bawah { haruslah - 5 sehingga merupakan batas bawah terbesar atau inf {. ▄
Definisi 2.1.22 (Barisan Naik dan Barisan Turun)
Misalkan 8! < merupakan barisan bilangan real. Barisan dikatakan naik jika memenuhi pertidaksamaan
! S ! S S ! S ! S
dan dikatakan turun jika memenuhi pertidaksamaan
! - ! - - ! - ! -
Jika barisan merupakan barisan naik atau barisan turun maka merupakan
barisan monoton.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
37
Teorema 2.1.7 Barisan turun dan terbatas ke bawah adalah konvergen.
Bukti:
Diberikan 8! < turun dan terbatas ke bawah. Karena 8! : }< maka
terdapat 5 dan 5 inf8! : }<. Jadi, untuk setiap } berlaku ! - 5
(2.1)
5 ' ! - 5
(2.2)
5 ' ! - ! - 5 ' 5 "
(2.3)
Karena 5 inf8! : }<, maka untuk ' 0 yang diberikan terdapat s } dan
Karena 8! < turun, maka mengingat (2.1) dan (2.2), untuk setiap - s berlaku
Jadi, diperoleh pernyataan bahwa untuk setiap ' 0 terdapat s } sedemi-
kian sehingga untuk setiap - } dan - s, maka |! 5| o . Jadi, 8! < konvergen dan lim ! 5 inf8! : }<.
▄
Untuk lebih memahami definisi batas atas, batas bawah, supremum, dan infimum, maka akan diberikan contoh berikut.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
38
Contoh 2.1.10
Misalkan . 8, 5, l, r, , , < terurut seperti pada Gambar 2.1.1 dan misal-
kan 8l, r, <. Tentukan batas atas, batas bawah, supremum, dan infimum
dari X!
l
r
5
Gambar 2.1.2 Himpunan Terurut
Penyelesaian:
Elemen , , dan didahului oleh setiap elemen dari X, sehingga , , dan adalah batas atas dari X.
Elemen mendahului setiap elemen dari X, sehingga adalah batas bawah
dari X.
Elemen mendahului dan , sehingga adalah supremum dari X.
Elemen mendahului setiap batas bawah dari X, sehingga adalah infimum
dari X.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
39
Definisi 2.1.23 (Barisan Cauchy)
Barisan 8 < v dikatakan Barisan Cauchy jika lim , L L 0.
Dengan kata lain untuk setiap ' 0, terdapat bilangan bulat s sedemikian sehingga L L o untuk semua , ' s.
Untuk lebih memahami definisi barisan Cauchy, maka akan diberikan contoh berikut.
Contoh 2.1.11
Buktikan bahwa adalah barisan Cauchy!
Bukti:
Jika diberikan ' 0, dapat dipilih s } sedemikian sehingga s ' . Maka,
jika , - s, diperoleh
S o dan dengan cara yang sama diperoleh
S o . Oleh karena itu, jika , - s, maka
S " o " .
Karena berlaku untuk sebarang ' 0, maka dapat disimpulkan bahwa adalah barisan Cauchy.
▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
40
Definisi 2.1.24 (Konvergen)
Barisan 8E < dikatakan konvergen jika terdapat E dengan sifat, untuk sebarang ' 0 yang diberikan, terdapat s } sehingga untuk semua }
dengan - s berlaku |E E | o . Bilangan s dinamakan limit 8E < untuk
∞ dan ditulis lim∞ E E atau disingkat lim E E.
Untuk lebih memahami definisi konvergen dari suatu barisan, maka akan diberikan contoh berikut.
Contoh 2.1.12
Jika E l untuk semua } dan c suatu konstanta, maka buktikan bahwa 8E < konvergen ke c!
Bukti:
Untuk semua } berlaku |E l| 0. Jadi, jika diberikan ' 0, maka
terdapat s } sehingga - s berlaku |E l| o . Dalam hal ini, dapat diambil bilangan bulat positif manapun untuk }, karena |E l| 0 o untuk }.
▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
41
B. Fungsi Terdiferensial Pada subbab ini akan dibahas mengenai fungsi, fungsi kontinu, fungsi terdiferensial secara kontinu, fungsi terdiferensial dua kali secara kontinu dan beberapa definisi serta teorema dasar tentang kalkulus.
Definisi 2.2.1 (Fungsi atau Pemetaan) Relasi dari himpunan A ke himpunan B disebut dengan fungsi atau pemetaan, jika dan hanya jika setiap anggota dari himpunan A berpasangan tepat hanya dengan sebuah anggota dalam himpunan B.
Fungsi f dapat pula dinotasikan dengan f : A → B , yang mana menunjukkan bahwa fungsi tersebut merupakan pemetaan dari himpunan A ke himpunan B. Himpunan A disebut dengan domain atau daerah asal, sedangkan himpunan B disebut dengan kodomain atau daerah kawan. Definisi 2.2.2 (Fungsi Kontinu di )
Misalkan , : , dan l . Fungsi f dikatakan kontinu di c, jika
untuk setiap ' 0 yang diberikan, dapat dicari ¡ ' 0, sehingga untuk semua
! dan |! l| o ¡, maka |#!$ #l$| o .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
42
Teorema 2.2.1
Jika , kontinu di x, maka juga kontinu di x. Bukti:
Andaikan f dan kontinu di x.
Akan dibuktikan bahwa kontinu di x.
Jika adalah sebarang bilangan positif yang diberikan, maka /2 adalah positif. Karena f kontinu di x, maka untuk setiap ' 0, terdapat suatu bila
ngan positif ¡ , sedemikian sehingga untuk H dan |! H| o
¡ maka |#!$ #H$| o dan karena kontinu di x, maka untuk setiap ' 0, terdapat suatu bilangan positif ¡ , sedemikian sehingga untuk
H dan |! H| o ¡ maka |#!$ #H$| o . Ambil sebarang ' 0
dan pilih ¡ min 8 ¡ , ¡ <, yakni pilih ¡ yang terkecil diantara ¡ dan ¡ .
Maka, untuk H dan |! H| o ¡ mengimplikasikan |#!$ #H$ #!$ #H$|
|#!$ #H$ " #1$#!$ #H$| S |#!$ #H$| " |#1$#!$ #H$|
S |#!$ #H$| " |#1$||#!$ #H$| S |#!$ #H$| " |#!$ #H$| S /2 " /2
(Ketaksamaan Segitiga)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
43
Langkah-langkah di atas memperlihatkan bahwa untuk H dan |! H| o ¡, maka |#!$ #H$ #!$ #H$| o .
Oleh karena itu, dapat disimpulkan bahwa kontinu di x.
▄
Definisi 2.2.3 (Nilai Maksimum, Nilai Minimum, dan Nilai Ekstrim) Andaikan S adalah daerah asal dari f yang memuat titik c. Dapat dikatakan bahwa: (i)
f(c) adalah nilai maksimum f pada S jika #l$ - #!$ untuk semua
x di S. (ii)
f(c) adalah nilai minimum f pada S jika #l$ S #!$ untuk semua x di S.
(iii)
f(c) adalah nilai ekstrim f pada S jika f(c) adalah nilai maksimum atau nilai minimum.
Teorema 2.2.2 (Titik Kritis)
Andaikan f terdefinisikan pada selang , 5 yang memuat titik c. Jika f(c)
adalah nilai ekstrim, maka c haruslah berupa suatu titik kritis, yakni c berupa
salah satu: (i) (ii)
Titik ujung dari , 5.
Titik stasioner dari f, yakni titik c sedemikian sehingga ¢ #l$ 0.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
(iii)
44
Titik singular dari f, yakni titik c sedemikian sehingga ¢ #l$ tidak ada.
Bukti:
Akan dibuktikan untuk f(c) yang berupa nilai maksimum f pada , 5.
Andaikan bahwa c bukan titik ujung ataupun titik singular, sehingga harus diperlihatkan bahwa c adalah titik stasioner. Karena f(c) adalah nilai maksimum, maka #!$ S #l$ untuk semua x dalam , 5 diperoleh #!$ #l$ S 0.
Jadi, jika ! o l sehingga ! l o 0, maka
! ' l, maka
£#¤$£#¥$ ¤¥
£#¤$£#¥$ ¤¥
- 0. Sedangkan, jika
S 0. Akan tetapi, ¢ #l$ ada, karena c bukan titik singu-
lar. Karena f terdiferensial pada c, maka diperoleh ¢ #l$ ¢ #l$
lim¤¥ ¦
£#¤$£#¥$ ¤¥
- 0 dan ¢ #l$ ¢ #l$ lim¤¥ §
£#¤$£#¥$ ¤¥
S 0, yang ma-
na mengakibatkan bahwa ¢ #l$ - 0 dan ¢ #l$ S 0. Sehingga dapat disimpulkan bahwa ¢ #l$ 0, yang mana menunjukkan bahwa c adalah titik stasio-
ner. Jadi, terbukti untuk f(c) yang berupa nilai maksimum f pada , 5. Se-
lanjutnya, untuk f(c) yang berupa nilai minimum f pada , 5 dibuktikan
dengan cara yang sama seperti untuk f(c) yang berupa nilai maksimum f pada
, 5. ▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
45
Teorema 2.2.3 (Teorema Nilai Rata-Rata)
Jika kontinu pada selang tertutup , 5 dan terdiferensiasikan pada titik-
titik dalam dari #, 5$, maka terdapat paling sedikit satu bilangan c dalam #, 5$ dengan
#5$ #$ ¢ #l$ 5
atau sama dengan #5$ #$ ¢ #l$#5 $.
#2.4$
Bukti:
Pembuktian ini berdasarkan pada analisis dari fungsi E#!$ #!$ #!$ yang diperlihatkan pada Gambar 2.2.1.
Gambar 2.2.1 Teorema Nilai Rata-Rata. Pada Gambar 2.2.1, terlihat bahwa H #!$ adalah persamaan garis yang melalui #, #$$ dan #5, #5$$. Karena garis ini mempunyai kemiringan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
46
#5$ #$/#5 $ dan melalui titik #, #$$, maka garis tersebut memiliki persamaan titik kemiringan, yakni #!$ #$
X #!$ #$ "
#5$ #$ #! $ 5
#5$ #$ #! $ 5
Sedangkan, jarak antara fungsi dengan fungsi adalah
#2.5$
E#!$ #!$ #!$
Sehingga persamaan (2.5) dapat ditulis menjadi E#!$ #!$ #!$
#!$ #$
#5$ #$ #! $ 5
#2.6$
Dapat dilihat bahwa E#5$ E#$ 0 dan bahwa untuk ! dalam #, 5$ berlaku
E ¢ #!$ ¢ #!$
#5$ #$ 5
#2.7$
Jika diketahui bahwa terdapat suatu bilangan c dalam #, 5$ yang memenuhi
E ¢ #l$ 0, maka bukti akan selesai. Sehingga, persamaan (2.7) menjadi 0 ¢ #l$
#5$ #$ 5
#2.8$
yang mana persamaan (2.7) tidak lain merupakan persamaan (2.4).
Untuk melihat bahwa E ¢ #l$ 0 untuk suatu c dalam #, 5$ alasannya jelas
karena s kontinu pada , 5 yang merupakan selisih dua fungsi kontinu. Berdasarkan sifat bahwa jika kontinu pada selang tertutup , 5, maka f men-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
47
capai nilai maksimum dan minimum, sehingga s harus mencapai nilai maksi-
mum ataupun nilai minimum pada , 5. Jika kedua nilai ini kebetulan adalah
0, maka E#!$ secara identik adalah 0 pada , 5, akibatnya E ¢ #!$ 0 untuk
semua x dalam #, 5$. Jika nilai maksimum atau nilai minimum berlainan de-
ngan 0, maka nilai tersebut dicapai pada sebuah titik-dalam c, karena E#$ E#5$ 0. Sekarang s mempunyai turunan di setiap titik dari #, 5$, sehingga
berdasarkan Teorema Titik Kritis diperoleh E ¢ #l$ 0. ▄
Definisi 2.2.4 (Fungsi Kontinu di )
Sebuah fungsi : dikatakan kontinu pada « , jika untuk setiap
ε > 0, terdapat δ > 0 sedemikian sehingga L «L o δ maka
L#$ #«$L o .
Definisi 2.2.5 (Turunan Parsial)
Andaikan bahwa f adalah suatu fungsi dua variabel dari ! dan H.
Turunan parsial f terhadap ¬ adalah fungsi yang dinyatakan dengan ¤ #!, H$ atau
£#¤,®$ ¤
yang nilainya di setiap titik #!, H$ diberikan oleh
¤ #!, H$
¯#!, H$ #! " ∆!, H$ #!, H$ lim ∆¤± ¯! ∆!
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
48
apabila limitnya ada. Dengan cara yang sama, turunan parsial f terhadap ²,
fungsi yang dinyatakan dengan ® #!, H$ atau
tik #!, H$ diberikan oleh ® #!, H$
apabila limitnya ada.
£#¤,®$ ®
yang nilainya di setiap ti-
¯#!, H$ #!, H " ∆H$ #!, H$ lim ∆®± ¯H ∆H
Untuk lebih memahami definisi turunan parsial, maka akan diberikan contoh berikut.
Contoh 2.2.1: Tentukan turunan parsial terhadap x dan turunan parsial terhadap y dari fungsi yang dinotasikan dengan #!, H$ ! H " 5! " 4!
Penyelesaian:
¯#!, H$ #! " ∆!, H$ #!, H$ lim ∆¤± ¯H ∆!
#! " ∆!$ H " 5#! " ∆!$ " 4 #! H " 5! " 4$ lim ∆¤± ∆!
! H " 2!∆!H " #∆!$ H " 5! " 5∆! " 4 #! H " 5! " 4$ ∆¤± ∆!
lim
2!∆!H " #∆!$ H " 5∆! ∆¤± ∆!
lim
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
49
2!H " 5
¯#!, H$ #!, H " ∆H$ #!, H$ lim ∆®± ¯H ∆H
! #H " ∆H$ " 5! " 4 #! H " 5! " 4$ ∆®± ∆H
lim
! ∆H ∆®± ∆H
lim !
Definisi 2.2.6 (Fungsi Terdiferensial Kontinu)
Sebuah fungsi kontinu : dikatakan terdiferensial kontinu di
∂f (x) ada dan kontinu dengan i = 1, … n. jika ∂xi
Definisi 2.2.7 (Gradien)
Misalkan : dan , gradien dari f di x didefinisikan sebagai ¯ #$ ¸ ¯! » ¯ · ¯ ¯ #$º º #$, … , ³#$ ´ #$µ · ¯! ¯! ¯!
· º · º ¯ #$ ¶¯!
¹
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
50
Definisi 2.2.8 (Turunan Berarah)
Fungsi : terdiferensial kontinu pada himpunan terbuka D ⊆ . Maka untuk x ∈ D dan ¼ turunan berarah dari f di dalam arah d di-
definisikan sebagai
# " ¿¼$ #$ ³#$ ¼ ¾± ¿
¢ #, ¼$ ½ lim
dimana ³#$ adalah gradien dari f di x, vektor berukuran n x 1. Teorema 2.2.4 (Teorema Taylor di )
Misalkan : terdiferensial secara kontinu dan bahwa ¼ . Maka
diperoleh
# " ¼$ #$ " ³# " À¼$ ¼
untuk suatu À #0,1$.
(2.9)
Bukti:
Misalkan : terdiferensial secara kontinu pada himpunan terbuka
m v sehingga m dan ¼ . Dengan menggunakan Definisi Turunan Berarah diperoleh bahwa
# " ¿¼$ #$ ³#$ ¼ ¾± ¿
¢ #, ¼$ lim
Misalkan, f(x) merupakan fungsi norm , yakni f(x) = LL.
Dari persamaan (2.10) diperoleh bahwa
#2.10$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
51
L " ¿¼L LL ¾± ¿
¢ #LL , ¼$ lim
∑ \|! " ¿r | ∑ \|! | ¾± ¿
lim
Jika ! ' 0, diperoleh |! " ¿r | |! | " ¿r untuk semua ¿ yang cukup ke-
cil. Jika ! o 0, diperoleh |! " ¿r | |#! ¿r $| |1||! ¿r | |! | ¿r . Jika ! 0, diperoleh |! " ¿r | |0 " ¿r | ¿|r |. Selanjutnya, diperoleh
¢ #LL , ¼$ lim
¾±
∑|¤Á ±|! " ¿r | ∑|¤Á ±|! |
"lim
¾±
"lim
¾±
lim
¾±
¿
∑|¤Á ñ|! " ¿r | ∑|¤Á ñ|! | ¿
∑|¤Á \±|! " ¿r | ∑|¤Á \±|! | ¿
∑|¤Á ±|! | " ∑|¤Á ± ¿r ∑|¤Á ±|! |
"lim
¾±
"lim
¾±
¿
∑|¤Á ñ|! | ∑|¤Á ñ ¿r ∑|¤Á ñ|! | ¿
∑|¤Á \±|! | " ∑|¤Á \± ¿|r | ∑|¤Á \±|! | ¿
¿ ∑|¤Á ± r ¿ ∑|¤Á ñ r " lim ¾± ¾± ¿ ¿
lim
¿ ∑|¤Á \±|r | ¾± ¿
"lim
Y r Y r " Y |r | |¤Á ±
|¤Á ñ
|¤Á \±
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
52
Jadi, turunan berarah dari fungsi f(x) ada untuk sebarang x dan d. Misalkan f terdiferensial secara kontinu pada suatu kitar dari x, maka diperoleh
¢ ##$, ¼$ ³#$ ¼
(2.11)
Untuk membuktikan rumus ini, didefinisikan fungsi #À$ # " À¼$ #B#À$$
dimana B#À$ " À¼. Dapat dicatat bahwa
# " ¿¼$ #$ #¿$ #0$ lim ¢ #0$ ¾± ¾± ¿ ¿ lim
Dengan menggunakan aturan rantai pada #B#À$$ diperoleh ¢ #À$
¯>B#À$? ¯B ¯>B#À$? ¯B ¯>B#À$? ¯B · " · " …" · " …" ¯B ¯À ¯B ¯À ¯B ¯À ¯#B#À$$ ¯B
· ¯À ¯B
Y \
Y \
¯>B#À$? · ³B #À$ ¯B ¯>B#À$? · r ¯B
³>B#À$? ¼
³# " À¼$ ¼
(2.12)
Substitusikan untuk À 0 ke dalam persamaan (2.12), sehingga diperoleh ¢ #0$ ³#$ ¼ ¢ ##$, ¼$
(2.13)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
53
yang mana persamaan (2.13) adalah persamaan (2.11). Berdasarkan Teorema Nilai Rata-Rata, misalkan diberikan sebuah fungsi yang terdiferensial secara kontinu : dan terdapat dua bilangan real À± dan À yang memenuhi À ' À± untuk suatu Ä #À± , À $, sehingga dipero-
leh
#À $ #À± $ " ¢ #Ä$#À À± $
Dapat diingat bahwa #À$ # " À¼$. Andaikan bahwa À± 0 dan À 1. Jika À diganti menjadi À , maka diperoleh #À $ # " À ¼$
Substitusikan À 1 ke dalam persamaan (2.15) sehingga diperoleh #1$ # " ¼$. Jika À diganti menjadi À± , maka #À± $ # " À± ¼$
Substitusikan ˱ 0 ke dalam persamaan (2.16) sehingga diperoleh
(2.14)
(2.15)
(2.16)
#0$ #$. Suatu perluasan dari hasil ini untuk fungsi multivariabel : bahwa untuk sebarang vektor d diperoleh bahwa # " ¼$ #$ " ³# " À¼$ ¼ untuk suatu À #0,1$. ▄
Definisi 2.2.9 (Fungsi Terdiferensial Dua Kali Secara Kontinu)
Sebuah fungsi terdiferensial kontinu : dikatakan terdiferensial
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
∂2 f dua kali secara kontinu di jika ∂x ∂x i j
] 1, … , dan Å 1, … , .
54
(x) ada dan kontinu dengan
Definisi 2.2.10 (Matriks Hesse)
Misalkan : dan , matriks Hesse dari f didefinisikan sebagai
matriks simetri berukuran n x n, yang dinotasikan dengan H(x) dengan ele-
men-elemen sebagai berikut: ³ #$
¯ #$, ] 1, … , dan Å 1, … , ¯! ¯!
Atau dapat juga dinyatakan sebagai berikut: ¯ #$ É È ¯! È ¯ #$ Æ#$ È ¯! ¯! È È È ¯ #$ ǯ! ¯!
¯ #$ ¯! ¯! ¯ #$ ¯! ¯ #$ ¯! ¯!
¯ #$ Ì ¯! ¯! Ë Ë Ë Ë Ë ¯ #$ Ë ¯! Ê
Untuk lebih memahami definisi gradien dan matriks Hesse, maka akan diberikan contoh berikut.
Contoh 2.2.2:
Misalkan Í#! , ! $ ! " ! 2! 5! " 7.25.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Maka ³Í#! , ! $
Î
¤ F ÎM ¤N
N Î#¤M ,¤N $
Æ#! , ! $ N Î#¤
¤MN
M ,¤N $
¤N ¤M
#! , ! $ #! , ! $
G+
N Î#¤M ,¤N $ ¤M ¤N
2! 2 , dan 2! 5
2 ) 0
N Î#¤M ,¤N $ ¤NN
55
0 *. 2
C. Himpunan Konveks dan Fungsi Konveks Pada subbab ini akan dibahas mengenai himpunan konveks dan fungsi konveks serta beberapa teorema-teorema yang berkaitan dengan fungsi konveks.
Definisi 2.3.1 (Himpunan Konveks)
Sebuah himpunan Ï v disebut himpunan konveks apabila memenuhi si-
fat berikut: jika diberikan sebarang dua titik x1, x2 ∈ C , maka
θ x1 + (1 − θ ) x2 ∈ C untuk setiap θ ∈ [0,1] . Suku θ x1 + (1 − θ ) x2 dengan θ ∈ [0,1] menggambarkan titik-titik yang terletak pada ruas garis yang menghubungkan x1 dan x2.
Dalam pengertian geometri, himpunan konveks dapat digambarkan pada Gambar 2.3.1.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
56
Gambar 2.3.1 Ilustrasi dari Himpunan Konveks.
Berdasarkan Gambar 2.3.1, jika diberikan sebarang dua titik x1 dan x2 yang berada di dalam C, maka ruas garis yang menghubungkan titik x1 dan x2 akan berada di dalam C.
Untuk lebih memahami definisi himpunan konveks, maka akan diberikan contoh berikut.
Contoh 2.3.1:
K = ( x1 , x 2 ) : x12 + x 22 < 1 v
{
}
Himpunan ini merepresentasikan titik yang berada di dalam lingkaran dengan pusat (0,0) dan radius 1 seperti pada Gambar 2.3.2.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
57
Gambar 2.3.2 Lingkaran x 2 + y 2 = 1
Berdasarkan Gambar 2.3.2, jika diberikan sebarang dua titik x1 dan x2 yang berada di dalam lingkaran, maka ruas garis yang menghubungkan titik x1 dan x2 akan berada di dalam lingkaran.
Definisi 2.3.2 (Fungsi Konveks)
Fungsi : dikatakan konveks jika untuk dua vektor x1, x2 berlaku
f (θ x1 + (1 − θ ) x2) ≤ θ f (x1) + (1 − θ ) f (x2) untuk semua θ ∈ [0,1] .
Fungsi f dikatakan konveks tegas (strictly convex) jika
f (θ x1 + (1 − θ ) x2) < θ f (x1) + (1 − θ ) f (x2) dimana x1≠ x2 dan 0 < θ < 1.
Fungsi konveks dapat diilustrasikan pada Gambar 2.3.3.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
58
Gambar 2.3.3 Contoh Fungsi Konveks.
Gambar 2.3.3 adalah fungsi konveks, dimana θ f (x1) + (1 − θ ) f (x2) digambarkan sebagai titik pada tali busur yang menghubungkan f (x1) dan f (x2), sedangkan f (θ x1 + (1 − θ ) x2) adalah titik pada f yang menghubung-
kan f(x1) dan f(x2). Berdasarkan Gambar 2.3.3, dapat dilihat bahwa ¿# $ " (1 − θ ) f # $
berada
di
atas
#¿ " #1 ¿$ $.
Jadi,
#1 ¿$ $ S ¿# $ " (1 − θ ) f # $, yang berarti f konveks.
#¿ "
Untuk lebih memahami definisi fungsi konveks, maka akan diberikan contoh berikut.
Contoh 2.3.2:
Diberikan f ( x) = x 2 , x , fungsi f merupakan fungsi konveks.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
59
Bukti:
Ambil x1, x2 , maka f ( x1) = x1 dan f ( x2) = x2 ,θ ∈ [0,1] . 2
2
f (θ x1 + (1 − θ ) x2) = (θx1 + (1 − θ ) x 2 ) 2
= (θx1 ) 2 + 2 (θx1 )((1 − θ ) x 2 ) + ((1 − θ ) x 2 ) 2 2
= θ 2 x1 + 2θx1 ( x2 − θx2 ) + ( x2 − θx2 ) 2 2
2
2
= θ 2 x1 + 2θx1 x2 − 2θ 2 x1 x2 + x2 − 2θx2 + θ 2 x 2 2
2
2
= θ 2 x1 + (1 − 2θ + θ 2 ) x 2 + 2θx1 x 2 − 2θ 2 x1 x 2 2
2
= θ 2 x1 + (1 − θ ) 2 x 2 + 2θx1 x 2 − 2θ 2 x1 x 2
Sedangkan, 2
θ f (x1) + (1 − θ ) f (x2) = θx1 + (1 − θ ) x2
2
Karena θ ∈ [0,1] , maka θ 2 < θ sehingga diperoleh:
f (θ x1 + (1 − θ ) x2) 2
2
= θ 2 x1 + (1 − θ ) 2 x 2 + 2θx1 x 2 − 2θ 2 x1 x 2 2
2
2
2
< θx1 + (1 − θ ) x 2 + 2θx1 x 2 − 2θx1 x 2 = θx1 + (1 − θ ) x 2
= θ f (x1) + (1 − θ ) f (x2) Jadi, f (θ x1 + (1 − θ ) x2) ≤ θ f (x1) + (1 − θ ) f (x2) untuk sebarang θ ∈ [0,1] , maka terbukti bahwa f ( x) = x 2 adalah fungsi konveks. ▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
60
Contoh 2.3.3:
Diberikan Í#$ ! " ! 2! 5! " 7.25, , fungsi Q merupa-
kan fungsi konveks.
Bukti:
Misalkan x = [x1 , x 2 ]T dan y = [ y1 , y 2 ]T ,θ ∈ [0,1].
Maka
x
y
2
θ x + (1 − θ ) y = θ 1 + (1 − θ ) 1 x y 2
θx y − θy1 = 1 + 1 θx 2 y 2 − θy 2 θ ( x1 − y1 ) + y1 = θ ( x 2 − y 2 ) + y 2 Karena itu
Í#¿ " #1 ¿$B$
#¿#! H $ " H $ " #¿#! H $ " H $ 2#¿#! H $ " H $ 5#¿#! H $ " H $ " 7.25
#¿ #! H $ " 2¿#! H $H " H $ " #¿ #! H $ "
2¿#! H $H " H $ 2¿#! H $ 2H 5¿#! H $ 5H " 7.25
#¿ #! 2! H " H $ " 2¿! H 2¿H " H $
"#¿ #! 2! H " H $ " 2¿! H 2¿H " H $ 2¿! " 2¿H
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2H 5¿! " 5¿H 5H " 7.25
Sedangkan,
¿Í#$ " #1 ¿$Í#B$ ¿#! " ! 2! 5! $ " #1 ¿$ #H " H 2H 5H $ " 7.25
¿! " ¿! 2¿! 5¿! " H " H 2H 5H ¿H ¿H " 2¿H " 5¿H " 7.25
Karena θ ∈ [0,1] , maka θ 2 < θ sehingga diperoleh:
Í#¿ " #1 ¿$B$
#¿ #! 2! H " H $ " 2¿! H 2¿H " H $
"#¿ #! 2! H " H $ " 2¿! H 2¿H " H $ 2¿! " 2¿H 2H 5¿! " 5¿H 5H " 7.25
o #¿#! 2! H " H $ " 2¿! H 2¿H " H $
"#¿#! 2! H " H $ " 2¿! H 2¿H " H $ 2¿! " 2¿H 2H 5¿! " 5¿H 5H " 7.25
o ¿! 2¿! H " ¿H " 2¿! H 2¿H " H " ¿! 2¿! H "¿H " 2¿! H 2¿H " H 2¿! " 2¿H 2H 5¿! "5¿H 5H " 7.25
¿! " ¿! 2¿! 5¿! " H " H 2H 5H ¿H ¿H "2¿H " 5¿H " 7.25
¿Í#$ " #1 ¿$Í#B$
61
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
62
Jadi, Í#¿ " #1 ¿$B$ S ¿Í#$ " #1 ¿$Í#B$ untuk sebarang θ ∈ [0,1] ,
maka terbukti bahwa Í#$ ! " ! 2! 5! " 7.25 dengan adalah fungsi konveks.
▄
Teorema 2.3.1
Misalkan S ⊆ adalah himpunan konveks terbuka tidak kosong dan
: { adalah fungsi terdiferensial. Maka f dikatakan konveks jika dan hanya jika
#$ - #«$ " ³#«$ # «$, «, {
Bukti: (⇒ )
Misalkan f konveks.
Akan ditunjukkan bahwa #$ - #«$ " ³#«$ # «$, «, {.
Berdasarkan Definisi Fungsi Konveks bahwa jika f adalah konveks, maka un-
tuk semua ¿ dengan 0 < ¿ < 1 berlaku
#¿ " #1 ¿$«$ S ¿#$ " #1 ¿$#«$
Ð #¿ " « ¿«$ S ¿#$ " #«$ ¿#«$
Ð #« " ¿# «$$ S ¿>#$ #«$? " #«$ Ð #« " ¿# «$$ #«$ S ¿>#$ #«$?
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Ð
#« " ¿# «$$ #«$ S #$ #«$ ¿
Dengan pengambilan limit untuk 0 , maka
#« " ¿# «$$ #«$ S #$ #«$ ¾± ¿ lim
Berdasarkan Definisi Turunan Berarah diperoleh
Maka terbukti bahwa
³#«$ # «$ S #$ #«$ #$ - #«$ " ³#«$ # «$
(⇐)
Misalkan bahwa #$ - #«$ " ³#«$ # «$.
Akan ditunjukkan f konveks.
Anggap bahwa #$ - #«$ " ³#«$ # «$, «, { benar.
Pilih sebarang x1, x2 { dan ¿ " #1 ¿$ untuk semua ¿ #0,1$.
Maka diperoleh
dan
Oleh karena itu,
# $ - #«$ " ³#«$ # «$ # $ - #«$ " ³#«$ # «$
¿# $ " #1 ¿$# $
- ¿##«$ " ³#«$ # «$$ " #1 ¿$##«$ " ³#«$ # «$$
63
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
64
¿#«$" ³#«$ ¿# «$ " #«$" ³#«$ # «$ ¿#«$ ³#«$ ¿# «$
#«$" ³#«$ #¿# «$ " # «$ ¿# «$$ #«$" ³#«$ #¿ ¿« " « ¿ " ¿«$ #«$" ³#«$ #¿ " #1 ¿$ «$ #¿ " #1 ¿$ $
Karena #¿ " #1 ¿$ $ S ¿# $ " #1 ¿$# $ untuk sebarang
x1, x2 { dan ¿ #0,1$, maka terbukti bahwa konveks.
▄
Teorema 2.3.2
Misalkan { v adalah himpunan konveks terbuka tidak kosong dan
: { v terdiferensial dua kali secara kontinu. Maka f adalah konveks
jika dan hanya jika matriks Hesse adalah semidefinit positif pada setiap titik dalam S.
Bukti: #Ñ$
Andaikan bahwa matriks Hesse ³ #$ adalah semidefinit positif pada setiap
titik {. Akan dibuktikan bahwa f adalah konveks. Anggap , « {. Mela-
lui Teorema Nilai Rata-Rata diperoleh #$ #«$ " ³#«$ # «$ "
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
65
# «$ ³ #Ò$# «$ dimana Ò « " ¿# «$, ¿ #0,1$. Dapat dicatat
bahwa Ò {. Karena ³ #$ adalah semidefinit positif, {, maka # «$ ³ #Ò$# «$ - 0.
Sehingga
diperoleh
#$ - #«$ "
³#«$ # «$. Dengan menggunakan Teorema 2.3.1 diperoleh bahwa f ada-
lah fungsi konveks. #Ó$
Andaikan bahwa f adalah fungsi konveks dan « {.
Akan dibuktikan bahwa T ³ #«$T - 0, Ô . Karena S terbuka, maka
terdapat ¡ ' 0 sedemikian sehingga ketika |k| o ¡, « " kT {. Dengan Teorema 2.3.1 diperoleh
#« " kT$ - #«$ " ³#«$ #« " kT «$
X #« " kT$ - #«$ " k³#«$ T
Karena #$ terdiferensial dua kali pada «, maka
(2.17)
1 #« " kT$ #«$ " ³#«$ #« " kT «$ " #« " kT «$ ³ #«$ 2 #« " kT «$ " Õ#LkTL $
1 #«$ " k³#«$ T " #kT$ ³ #«$kT " Õ#LkTL $ 2 #«$ " k³#«$ T "
k T ³ #«$T " Õ#LkTL $ 2
#2.18$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
66
Substitusikan persamaan (2.18) ke dalam persamaan (2.17), sehingga diperoleh
#« " kT$ - #«$ " k³#«$ T
k X #«$ " k³#«$ T " T ³ #«$T " Õ#LkTL $ - #«$ " k³#«$ T 2 1 X k T ³ #«$T " Õ#LkTL $ - 0 2
Bagi dengan k dan misalkan k 0, sehingga diperoleh T ³ #«$T - 0. ▄
Teorema 2.3.3
Misalkan , adalah fungsi konveks pada himpunan { v , maka " juga adalah fungsi konveks pada S.
Bukti:
Misalkan , { dan 0 o ¿ o 1, maka
#¿ " #1 ¿$ $ " #¿ " #1 ¿$ $
S ¿# $ " #1 ¿$ " ¿# $ " #1 ¿$ S ¿# $ " # $ " #1 ¿$# $ " # $ ▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
67
Teorema 2.3.4 (Teorema Proyeksi)
Misalkan { v adalah himpunan konveks tertutup tidak kosong dan B Ö {,
maka ada titik tunggal « { dengan jarak minimum dari y, yakni LB «L infLB L
#2.19$
AB «, «C S 0, {
(2.20)
×
Selanjutnya, « adalah titik minimum dari persamaan (2.19) jika dan hanya jika
atau dapat dikatakan bahwa « adalah proyeksi Ù× #B$ dari y di S jika dan hanya jika persamaan (2.20) dipenuhi.
Bukti: Pembuktian Teorema 2.3.4 di atas dapat dibagi menjadi tiga bagian, yakni: (i)
Akan dibuktikan bahwa jika { v adalah himpunan konveks tertutup tidak kosong dan B Ö {, maka ada titik tunggal « { dengan jarak minimum dari y, yakni LB «L inf× LB L. Misalkan
inf8LB L| {< Ú ' 0
(2.21)
Karena Ú adalah batas bawah terbesar maka Ú S LB L, {.
Misalkan terdapat sebuah titik 1 { dan B Ö {. 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 da-
ri kitar 1 dan berada pada garis yang menghubungkan titik 1 dan ti-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
68
tik y, diperoleh titik 2 . Kemudian, dari titik 2 dibuat kitar dengan radius 2. Dari titik limit yang diperoleh dari kitar 2 dan berada pada ga1
ris 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 tersebut dan terletak pada ruas garis yang menghubungkan titik Û1 dan titik y diperoleh titik Û. Dengan demikian akan ada barisan 8Û < v {.
Akan ditunjukkan bahwa LB Û L Ú.
Karena Ú inf8LB L| {< maka berdasarkan Lemma 2.1.1, un-
tuk setiap ' 0 terdapat LB Û L dengan Û { sedemikian se
hingga Ú " ' LB L.
Dengan demikian, terbentuk barisan 8LB Û L< yang terbatas dan turun.
Berdasarkan Teorema 2.1.7, maka 8LB Û L< akan konvergen dan lim LB Û L Ú inf8LB Û L<.
Û∞
Berikut ini, akan dibuktikan bahwa 8 < adalah barisan Cauchy dan
oleh karena itu ada limit « {.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Melalui
Teorema
Paralelogram
diketahui
bahwa
69
L " BL "
L BL 2#LL " LBL $. Misalkan ambil , {, di mana x
diganti dengan B dan B diganti dengan B. Dengan men-
substitusikan x dan y ke dalam Teorema Paralelogram, diperoleh
L# B$ " # B$L " L# B$ # B$L 2L BL "2L BL
L " 2BL " L L 2L BL " 2L BL L L 2L BL " 2L BL L " 2BL " 2L BL " 2L BL Ü´ Bµ 2Ü 2
2L BL " 2L BL 4 Ü
" BÜ 2
#2.22$
Karena 8 < ⊂ { , maka # " $/2 {. Dari definisi Ú dikatakan
bahwa inf LB L Ú, sehingga LB L L BL - Ú, {. Dengan mengganti # " $/2 diperoleh Ü
XÜ
" BÜ - Ú 2
" BÜ - Ú 2
#2.23$
Dengan menggunakan persamaan (2.22) dan (2.23) diperoleh L L S 2L BL " 2L BL 4Ú .
Ambil k dan m yang cukup besar sehingga L BL Ú dan L BL Ú, dengan demikian dipenuhi bahwa L L
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
70
2Ú " 2Ú 4Ú 0 atau L L 0, yang mana menunjukkan
bahwa 8 < adalah barisan Cauchy dengan limit «. Karena S tertutup,
maka « {. Hal ini menunjukkan bahwa ada « sedemikian sehingga
LB «L Ú.
Selanjutnya, akan dibuktikan ketunggalan.
Ý dengan Andaikan Ý tidak tunggal, artinya ada Ý ′ { dan Ý ′
Ý′ BL Ú. L
Ý′ B dan Melalui Hukum Parallelogram, misalkan diganti dengan Ý B, maka diperoleh B diganti dengan
Ý′ " Ý 2BL2 " L Ý′ ÝL2 2L Ý ′ BL 2 " 2 L Ý BL 2 L Ý′ ÝL2 2L Ý′ BL2 " 2L Ý BL 2 L Ý′ " Ý 2BL2 L «′ " « 2L«′ BL " 2L« BL Ü2 ´ BµÜ 2
«′ " « 2L«′ BL " 2L« BL 4 Ü BÜ 2 «′ " « 2Ú " 2Ú 4 Ü BÜ 2
Karena
« "« ′ 2
Akibatnya,
{, maka menurut (2.23), Ú2 S Þ
Ý′ ÝL2 S 2Ú2 " 2Ú2 4Ú2 L
0
2 « ′"« B . Þ 2
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
71
ÝL S 0, padahal LÝ ÝL ' 0. Jadi, ada kontradiksi. TerJadi, LÝ ′ ′ Ý′ Ý. bukti
(ii)
Akan dibuktikan bahwa jika AB «, «C S 0, {, maka « ada-
lah titik minimum dari LB «L inf× LB L.
Ambil x sebarang di S dan misalkan AB «, «C S 0, { dipe-
nuhi, sehingga LB L LB « " « L
LB «L " L« L " 2AB «, « C
LB «L " L« L " 2#« $ #B «$
Karena L« L - 0 dan #« $ #B «$ - 0, maka
LB L - LB «L dan « adalah titik minimum dari LB «L inf× LB L. (iii)
Akan dibuktikan bahwa jika « adalah titik minimum dari
LB «L inf× LB L, maka AB «, «C S 0, {. Misalkan LB L - LB «L , {.
Karena « " k# «$ { dengan k #0,1$, maka diperoleh LB #« " k# «$$L - LB «L
X LB « k# «$L - LB «L X LB « k " k«L - LB «L
X LB « " k#« $L - LB «L
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
72
X LB «L " k L« L " 2k#« $ #B «$ - LB «L X LB «L " k L «L " 2k# «$ #« B$ - LB «L X k L «L " 2k# «$ #« B$ - 0
Bagi dengan k dan misalkan k 0, maka diperoleh
AB «, «C S 0, {. ▄
D. Teori Optimisasi Secara umum, bentuk baku untuk permasalahan optimisasi berkendala adalah sebagai berikut:
minimumkan #$ ß
dengan kendala ci(x) = 0, i à dimana:
ci(x) ≥ 0, i á
(2.24) (2.25) (2.26)
f adalah fungsi obyektif
à = {1, … , me} adalah himpunan indeks dari kendala persamaan
á = {me + 1, … , m} adalah himpunan indeks dari kendala pertidaksamaan
dengan me dan m adalah bilangan bulat nonnegatif dimana 0 ≤ me ≤ m.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
73
Apabila fungsi obyektif dan kendala dari permasalahan (2.24)-(2.26) merupakan fungsi konveks, maka permasalahan tersebut merupakan permasalahan pemrograman konveks.
Definisi 2.4.1 (Titik Layak atau Penyelesaian Layak)
Titik dikatakan titik layak atau penyelesaian layak dari masalah op-
timisasi jika dan hanya jika memenuhi persamaan (2.25) dan (2.26).
Definisi 2.4.2 (Titik Optimum atau Penyelesaian Optimum)
Titik â dikatakan titik optimum atau penyelesaian optimum dari
masalah optimisasi jika dan hanya jika merupakan penyelesaian layak yang mengoptimumkan fungsi obyektif.
Definisi 2.4.3 (Titik Stasioner atau Titik Kritis)
Titik â dikatakan titik stasioner atau titik kritis untuk f yang terdife-
rensial jika ³# â $ 0.
Definisi 2.4.4 (Himpunan Layak atau Daerah Layak) Himpunan semua titik layak dikatakan himpunan layak atau daerah layak yang dinotasikan dengan X, dimana X didefinisikan sebagai ã ä
l #$ 0, ] 1, … , å æ l #$ - 0, ] å " 1, … ,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
atau
74
8|l #$ 0, ] à; l #$ - 0, ] á<
Definisi 2.4.5 (Peminimum Global dan Peminimum Global Tegas)
Jika â dan jika #$ - # â $, , maka â dikatakan peminimum global dari permasalahan (2.24) – (2.26). Jika â dan jika
#$ ' # â $, , maka â dikatakan peminimum global tegas. Definisi 2.4.6 (Peminimum Lokal dan Peminimum Lokal Tegas)
Jika â dan jika ada suatu kitar B( â , ¡$ dari â sedemikian sehingga
#$ - # â $, è x# â , ¡$, maka â dikatakan peminimum lokal dari permasalahan (2.24) – (2.26), dimana x# â , ¡$ 8|L â L S ¡< dan
¡ ' 0. Jika â dan jika ada suatu kitar B( â , ¡$ dari â sedemikian se-
hingga #$ ' # â $, è x# â , ¡$, â , maka â dikatakan pemi-
nimum lokal tegas.
Definisi 2.4.7 (Himpunan Indeks)
Misalkan á#$ 8]|l #$ 0, ] á<. Untuk sebarang , himpunan é#$ à ê á#$ adalah himpunan indeks dari kendala-kendala aktif di x,
yakni kendala yang memenuhi l #$ 0. Sedangkan, é# â $ adalah himpu-
nan indeks dari kendala aktif dari permasalahan (2.24) – (2.26) di â yang di-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
definisikan
dengan
á# â $ 8]|l # â $ 0, ] á<.
é# â $ à ê á# â $,
75
dimana
Definisi 2.4.8 (Arah Layak)
Misalkan â , 0 ¼ . Jika ada ¡ ' 0 sedemikian sehingga
â " À¼ , À 0, ¡, maka d dikatakan arah layak (feasible direction).
Himpunan dari semua arah layak dari X di â adalah
ëm # â , $ 8¼ | â " À¼ , À 0, ¡<
Definisi 2.4.9 (Arah Layak Terlinearisasi)
Misalkan â dan ¼ . Jika ¼ ³l # â $ 0, ] à, ¼ ³l # â $ - 0,
] á# â $, maka d dikatakan arah layak terlinearisasi (linearized feasible
direction). Himpunan dari semua arah layak terlinearisasi dari X di â adalah ìëm # â , $ ã¼ä
¼ ³l # â $ 0, ] à æ ¼ ³l # â $ - 0, ] á# â $
Definisi 2.4.10 (Arah Layak Terurut)
Misalkan â dan ¼ . Jika ada barisan ¼ #Û 1, 2, … $ dan
¼ ' 0, #Û 1, 2, … $ sedemikian sehingga â " ¡ ¼ , Û dan
¼ ¼, ¡ 0, maka arah limit d dikatakan arah layak terurut (sequential
feasible direction). Himpunan dari semua arah layak terurut dari X di â ada-
lah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
{ëm# â , $ ã¼ä
76
â " ¡ ¼ , Û æ ¼ ¼, ¡ 0
Teorema 2.4.1
Misalkan S ⊂ himpunan konveks tertutup tidak kosong dan B Ö {. Maka ada vektor taknol p dan bilangan real R sedemikan sehingga T B ' R dan T S α, {, yakni T B ' sup8T , {< yang mana mengatakan bahwa ada bidang hiper î 8|T α< sebagai pemisah tegas y dan S.
Bukti:
Karena S himpunan konveks tertutup tidak kosong dan B Ö {, maka berdasar-
kan Teorema Proyeksi ada titik tunggal « {, sedemikian sehingga # «$ #B «$ S 0, {
Bentuk p = B « 0, maka
0 - #B «$ #B « " B$ T #T " B$
T T B " LTL
Oleh karena itu, T B - T " LTL , {.
Bentuk α sup8T | {<, sehingga diperoleh T B ' sup8T , {<. ▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
77
Teorema 2.4.2 (Lemma Farkas)
Misalkan A ∈ dan ï . Maka ada tepat satu dari dua sistem berikut
yang mempunyai penyelesaian: (i) (ii)
S 0, ï ' 0 B ï, B - 0
(2.27) (2.28)
Bukti: (i)
Misalkan sistem 2.28 mempunyai penyelesaian. Akan dibuktikan sistem 2.27 tidak mempunyai penyelesaian. Akan dibuktikan dengan kontradiksi.
Andaikan sistem 2.27 mempunyai penyelesaian, yakni ada ï ' 0 se-
demikian sehingga S 0 saat B ï dan B - 0. Jika sistem 2.27 dan 2.28 dipenuhi, maka ï # B$ B . Karena S 0 dan
B - 0, maka B S 0 yang mana kontradiksi dengan asumsi bahwa
ï ' 0. Karena pengandaian salah, maka haruslah sistem 2.27 tidak
mempunyai penyelesaian.
(ii)
Misalkan sistem 2.28 tidak mempunyai penyelesaian. Akan dibuktikan sistem 2.27 mempunyai penyelesaian.
Misalkan { 8| B, B - 0< adalah himpunan konveks tertutup tidak kosong dan ï Ö {. Berdasarkan Teorema 2.4.1, ada T dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
78
α sedemikian sehingga T ï ' R dan T S α, {. Karena
0 {, maka R - T T 0 0 dan T ï ' 0 sehingga R - T
T B B T, B - 0. Jadi, diperoleh B T S 0. Untuk sebarang y
yang besar diperoleh T S 0, dengan T yang merupakan penye-
lesaian dari sistem 2.27. ▄
Selanjutnya, diberikan Lemma 2.4.1 yang merupakan akibat langsung dari Teorema 2.4.2.
Lemma 2.4.1 Himpunan
¼ ³# â $ o 0 { ð¼ñ ¼ ³l # â $ 0, ] à ò ¼ ³l # â $ - 0, ] á
#2.29$
adalah himpunan kosong jika dan hanya jika ada bilangan real λ , ] à dan
bilangan taknegatif λ - 0, ] á sedemikian sehingga ³# â $ Y λ ³l # â $ " Y λ ³l # â $ à
Bukti: Misalkan bahwa
á
#2.30$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
79
³l # â $ ¼ , ³# â $ ï, F G ,λ ² ³l # â $
Maka, persamaan (2.29) dapat ditulis menjadi (i)
¼ ³# â $ o 0
X ï o 0 X ï'0
(ii)
Xï '0
¼ ³l # â $ 0, ] à dan ¼ ³l # â $ - 0, ] á
X # $ - 0
X # $ - 0 X - 0 X S 0
yang mana S 0 dan ï ' 0 adalah persamaan (2.27).
Sedangkan, persamaan (2.30) dapat ditulis menjadi
³# â $ Y λ ³l # â $ " Y λ ³l # â $ Y λ ³l # â $ Y ³l # â $ λ à
Xï B
á
\
\
yang mana ï B adalah persamaan (2.28).
Melalui Lemma 2.4.1 ini:
(1) Misalkan bahwa persamaan (2.30) mempunyai penyelesaian. Akan dibuktikan bahwa persamaan (2.29) tidak mempunyai penyelesaian.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
80
(2) Misalkan bahwa persamaan (2.30) tidak mempunyai penyelesaian. Akan dibuktikan bahwa persamaan (2.29) mempunyai penyelesaian. Bukti untuk ke dua pernyataan di atas analog dengan bukti pada Teorema 2.4.2. ▄
Berikut ini diberikan teorema tentang syarat optimalitas geometri.
Teorema 2.4.3 (Syarat Optimalitas Geometri)
Misalkan â adalah peminimum lokal dari permasalahan (2.24) – (2.26). Jika f(x) dan ci(x)(i = 1, 2, …, m) terdiferensial di â , maka ¼ ³# â $ - 0, ¼ {ëm# â , $
yang
mana
berarti
{ëm# â , $ è ô# â $ ,
ô# â $ 8¼| ¼ ³# â $ o 0< dan adalah himpunan kosong.
(2.31) di
mana
Bukti:
Untuk sebarang ¼ {ëm# â , $, ada ¡ ' 0#Û 1, 2, … $ dan ¼
#Û 1, 2, … $ sedemikian sehingga â " ¡ ¼ dengan ¡ 0 dan
¼ ¼. Karena â " ¡ ¼ â dan â adalah peminimum lokal, maka ber-
dasarkan Teorema Taylor di untuk k yang cukup besar diperoleh # â $ S # â " ¡ ¼ $ # â $ " ¡ ¼ ³# â $ " Õ#¡ $
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
0 S ¡ ¼ ³# â $ " Õ#¡ $
81
(2.32)
Karena ¡ ' 0 dan Û ∞, maka diperoleh ¼ ³# â $ - 0
(2.33)
Karena d sebarang, maka diperoleh persamaan (2.31).
Persamaan (2.33) juga berarti dÖ ô# â $ 8¼| ¼ ³# â $ o 0<. Oleh karena itu {ëm# â , $ è ô# â $ . ▄
Berikut ini diberikan definisi fungsi Lagrange.
Definisi 2.4.11 (Fungsi Lagrange) Fungsi Lagrange dari permasalahan (2.24) – (2.26) adalah
õ#, ö$ #$ Y λ l #$ #$ Y λ l #$ \
àêá
dimana ö #λ , … , λ $ disebut vektor pengali Lagrange. Teorema 2.4.4 (Teorema Karush Kuhn Tucker)
Misalkan â adalah peminimum lokal dari permasalahan (2.24) – (2.26). Jika himpunan semua arah layak terlinearisasi sama dengan himpunan semua arah layak terurut, yakni
{ëm# â , $ ìëm # â , $
(2.34)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
82
dipenuhi, maka ada pengali Lagrange kâ sedemikian sehingga syarat berikut dipenuhi di ( â , ÷â $:
³ õ# â , öâ $ ³# â $ Y kâ ³l # â $ 0 \
l # â $ 0, ] à
#2.35$ (2.36)
l # â $ - 0, ] á
(2.37)
kâ - 0, ] á
kâ l # â $ 0, ] á
(2.38) (2.39)
Bukti:
Misalkan ¼ {ëm# â , $. Karena â adalah peminimum lokal, maka berda-
sarkan Teorema 2.4.3 diperoleh ¼ ³# â $ - 0. Dari persamaan (2.34) dipe-
roleh ¼ ìëm # â , $. Misalkan ditetapkan vektor kâ dengan kâ ã
k , ] é# â $ ù 0, ] á\á# â $
(2.40)
Maka dengan menggunakan persamaan (2.30) untuk kâ diperoleh ³# â $ Y kâ ³l # â $ " Y kâ ³l # â $ á# â $
à
dimana kâ #] à$ dan kâ - 0#] á# â $$. Bentuk ³#
â$
Y kâ ³l # â $ \
yang mana persamaan (2.41) tidak lain merupakan syarat (2.35).
#2.41$
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
83
Karena â layak, maka syarat (2.36) – (2.37) dipenuhi.
Berdasarkan persamaan (2.30) diperoleh kâ - 0 untuk ] á# â $, sedangkan
dari persamaan (2.40) diperoleh kâ 0 untuk ] á\á# â $. Oleh karena itu, kâ - 0 untuk ] á, sehingga syarat (2.38) dipenuhi.
Untuk ] á# â $ diperoleh l # â $ 0, sedangkan untuk ] á\á# â $ dipero-
leh kâ 0. Oleh karena itu, kâ l # â $ 0 untuk ] á, sehingga syarat (2.39)
dipenuhi. ▄
Berikut ini diberikan definisi titik Karush Kuhn Tucker.
Definisi 2.4.12 (Titik Karush Kuhn Tucker) Suatu titik dikatakan titik Karush Kuhn Tucker (KKT) jika memenuhi syarat KKT, yakni syarat (2.35)-(2.39) yang terdapat dalam Teorema Karush Kuhn Tucker.
Teorema 2.4.5 Titik KKT dari pemrograman konveks merupakan titik peminimum.
Bukti:
Misalkan # â , öâ $ adalah sebarang pasangan KKT dari pemrograman konveks.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
84
Karena #$ dan l #$ merupakan fungsi konveks, maka fungsi Lagrange õ#, öâ $ #$ Y kâ l #$ Y kâ l #$ à
á
#2.42$
adalah konveks untuk x. Dengan menggunakan Teorema 2.3.1 dan Teorema Karush Kuhn Tucker, maka diperoleh untuk sebarang x yang layak
õ#, öâ $ - õ# â , öâ $ " # â $ ³ õ# â , öâ $ õ# â , öâ $ " # â $ 0 õ# â , öâ $
# â $ Y kâ l # â $ \
# â $ 0 # â $
(2.43)
Karena x adalah titik layak, yakni memenuhi persamaan (2.25) dan
kâ - 0, ] á, maka
kâ l #$ 0, ] à dan kâ l #$ - 0, ] á
(2.44)
Oleh karena itu, dengan menggunakan (2.42) dan (2.44) diperoleh õ#, öâ $ #$ Y kâ l #$ Y kâ l #$ S #$
à
á
(2.45)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
85
Dengan menggunakan (2.43) dan (2.45) diperoleh #$ - # â $, yang mana
menunjukkan bahwa titik KKT â merupakan titik peminimum. ▄
E. Metode Newton untuk Sistem Persamaan Nonlinear Metode titik-interior primal-dual menerapkan metode Newton untuk menemukan penyelesaiannya karena menggunakan matriks Jacobi untuk memperoleh arah selidik, serta menggunakan rumus iterasi metode Newton untuk menemukan penyelesaian dari sistem persamaan nonlinear. Metode Newton merupakan salah satu metode numerik yang digunakan untuk menyelesaikan permasalahan dalam mencari akar dari persamaan nonlinear. Persamaan nonlinear adalah negasi dari persamaan linear. Persamaan linear dengan n variabel bebas ! , ! , … , ! mempunyai bentuk
H ! " ! " … " ! . Persamaan nonlinear terbagi menjadi dua,
yakni persamaan nonlinear dengan satu variabel dan persamaan nonlinear
dengan n variabel, dengan ' 1. Bentuk umum persamaan nonlinear dengan
satu variabel adalah #!$ 0 dengan #!$ adalah fungsi nonlinear. Sedang-
kan, bentuk umum persamaan nonlinear dengan n variabel adalah #! , ! , … , ! $ 0 dengan #! , ! , … , ! $ adalah fungsi nonlinear.
Sistem persamaan nonlinear adalah himpunan n persamaan nonlinear,
dengan ' 1. Sistem persamaan nonlinear secara umum berbentuk
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
86
#! , ! , … , ! $ 0
#! , ! , … , ! $ 0
#! , ! , … , ! $ 0
di mana tiap fungsi , ] 1,2, … , merupakan pemetaan vektor
#! , ! , … , ! $ dari ke . Sistem ini dapat ditulis ke dalam bentuk yang lain dengan mendefinisikan fungsi F, yang memetakan ke , yakni
ú#! , ! , … , ! $ # #! , ! , … , ! $, … , #! , ! , … , ! $$ . Dengan meng-
gunakan notasi vektor, sistem di atas dapat diasumsikan dengan bentuk ú#$ 7.
Andaikan bahwa f terdiferensial dua kali secara kontinu pada , 5.
Misalkan !û , 5 menjadi pendekatan untuk p sedemikian sehingga ¢ #!û $ 0 dan |Ô !û | mendekati nol. Dengan mempertimbangkan bentuk de-
ret Taylor untuk #!$ di sekitar !û , yakni
#!$ #!û $ " #! !û $ ¢ #!û $ "
#! !û $ ¢¢ #Ä#!$$ 2
dengan Ä#!$ berada diantara ! dan !û dan karena #Ô$ 0 dengan x = p, maka persamaan akan menjadi
0 #!û $ " #Ô !û $ ¢ #!û $ "
#Ô !û $ ¢¢ #Ä#Ô$$ 2
Karena |Ô !û | mendekati nol, maka #Ô !û $ dapat diabaikan, sehingga dipe-
roleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
87
0 ü #!û $ " #Ô !û $ ¢ #!û $
Ð 0 ü #!û $ " Ô# ¢ #!û $$ !û # ¢ #!û $$ Ð Ô# ¢ #!û $$ ü !û # ¢ #!û $$ #!û $ ÐÔü
!û # ¢ #!û $$ #!û $ ¢ #!û $
Ð Ô ü !û
#!û $ ¢ #!û $
Persamaan tersebut merupakan bentuk penyelesaian untuk metode Newton, dengan pendekatan awal !± dan akan membangkitkan barisan 8! <
\± dengan ! !
#! $ ¢ #! $
#2.46$
untuk - 0. Barisan hampiran akar 8! < dari metode Newton akan konvergen jika |! ! | o .
Persamaan (2.46) dapat ditulis menjadi ! !
X !
#! $ ¢ #! $
! ¢ #! $ #! $ ¢ #! $
X ! ¢ #! $ ! ¢ #! $ #! $
X ! ¢ #! $ ! ¢ #! $ #! $ X ! ! ¢ #! $ #! $
(2.47)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
88
Dengan menerapkan persamaan (2.47), maka rumus iterasi metode Newton untuk menemukan penyelesaian sistem persamaan nonlinear adalah #$ #$ ýþ> #$ ? ú> #$ ?
dengan Û - 0, dimana
¯ #$ ¯ #$ ¯ #$ É Ì ¯! ¯! Ë È ¯! ȯ #$ ¯ #$ Ë È Ë þ#$ ¯! ¯! È Ë È Ë È¯ #$ ¯ #$ ¯ #$Ë ¯! Ç ¯! ¯! Ê
(2.48)
#2.49$
Matriks (2.49) dikenal dengan nama matriks Jacobi. Persamaan (2.48) dapat ditulis pula menjadi #$ #$ ýþ> #$ ? ú> #$ ?
X #$ #$ ýþ> #$ ? ú> #$ ?
X B #$ ýþ> #$ ? ú> #$ ?
X ýþ> #$ ?B #$ ú> #$ ?
#2.50$
Definisi 2.5.1
Misalkan #$ v dan â .
#$ â q-kuadratik jika #$ â dan ada sebuah ' 0 sedemikian sehingga #$ â S #$ â .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
89
Definisi 2.5.2
Misalkan Ω v dan : Ω . memenuhi kondisi kontinu Lipschitz dalam Ω dengan konstanta Lipschitz Ú jika L#$ #B$L S ÚL BL. Asumsi 2.5.1
1. Persamaan ú#$ 7 mempunyai penyelesaian â .
2. ú ¢ : Ω h merupakan kontinu Lipschitz dengan konstanta Lipschitz Ú.
3. ú ¢ # â $ adalah nonsingular. Teorema 2.5.1
Misalkan Asumsi 2.5.1 terpenuhi. Maka ada sebuah ¡ sedemikian sehingga
jika #±$ x#¡$, di mana x#¡$ menyatakan suatu kitar dengan radius ¡ di se-
kitar â , yakni x#¡$ 8|LL o ¡< dengan â. Sehingga iterasi
Newton #$ #$ ýú ¢ > #$ ? ú> #$ ? konvergen q-kuadratik ke â .
Bukti: Bukti Teorema 2.5.1 dapat dilihat pada Tugas Akhir karangan Anggi, M. N. (2007). Penyelesaian Sistem Persamaan Non-linear dengan Metode Newton dan Terapannya. Skripsi. Yogyakarta: FST USD.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
90
Teorema 2.5.2
Misalkan f terdiferensial dua kali secara kontinu pada interval , 5 atau da-
pat ditulis Ï , 5. Jika Ô , 5 sedemikian sehingga #Ô$ 0 dan ¢ #Ô$ 0, maka ada sebuah ¡ ' 0 sedemikian sehingga metode Newton
akan membangkitkan barisan Ô# $ \ konvergen ke p untuk beberapa pendekatan awal Ô#±$ Ô ¡, Ô " ¡.
Bukti: Bukti Teorema 2.5.2 dapat dilihat pada Tugas Akhir karangan Anggi, M. N. (2007). Penyelesaian Sistem Persamaan Non-linear dengan Metode Newton dan Terapannya. Skripsi. Yogyakarta: FST USD.
Teorema 2.5.1 dan Teorema 2.5.2 menyatakan bahwa nilai awal akan berpengaruh terhadap kekonvergenan dan jumlah iterasi yang dihasilkan apabila menggunakan metode Newton. Nilai awal yang berasal dari titik-interior atau cukup dekat dengan penyelesaian yang sebenarnya akan menghasilkan iterasi yang relatif lebih sedikit untuk konvergen. Sedangkan, untuk nilai awal yang berasal dari luar titik-interior atau cukup jauh dengan penyelesaian yang sebenarnya akan menghasilkan iterasi yang relatif lebih banyak untuk konvergen. Selain nilai awal, hal lain yang mempengaruhi adalah syarat bahwa þ#$ 0 harus terpenuhi.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB III METODE TITIK-INTERIOR
A. Pemrograman Kuadratik Konveks Pemrograman nonlinear adalah salah satu bagian penting dari permasalahan optimisasi. Mencari penyelesaian optimum pada pemrograman nonlinear, khususnya dalam bentuk pemrograman kuadratik konveks memerlukan suatu algoritma untuk mendapatkan penyelesaian atau nilai optimum tersebut. Sebelum membahas mengenai pemrograman kuadratik konveks, terlebih dahulu akan dibahas mengenai pemrograman kuadratik karena pemrograman kuadratik konveks merupakan subkelas dari pemrograman kuadratik. Pemrograman kuadratik adalah permasalahan optimisasi berkendala nonlinear yang paling sederhana. Pemrograman kuadratik merupakan kelas khusus dari permasalahan optimisasi berkendala (2.24) – (2.26) dengan fungsi obyektif kuadratik yang dinotasikan dengan f(x) dan kendala-kendala linear yang dinotasikan dengan ci(x) dimana 1, … , . Fungsi kuadratik dengan n variabel , , … , adalah fungsi yang mempunyai bentuk
α
91
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
92
di mana , , … , , A adalah matriks simetrik n x n, B adalah ma-
triks 1 x n, dan α adalah suatu skalar.
Secara umum, pemrograman kuadratik mempunyai bentuk sebagai berikut:
1 minimumkan 2 dengan kendala , " ,
3.1
!
(3.2)
#
(3.3)
dimana G adalah matriks Hesse n x n
! adalah himpunan indeks dari kendala persamaan
# adalah himpunan indeks dari kendala pertidaksamaan , x, dan , dengan
! ' # , adalah vektor di (
Berdasarkan Definisi Fungsi Lagrange, fungsi Lagrange dari permasalahan (3.1)-(3.3) adalah ), *
1 + , λ + 2 !'# -
1 + , λ + 2 .
Dengan menggunakan syarat KKT yang diperoleh dari Teorema Karush Kuhn Tucker ke dalam permasalahan (3.1) – (3.3), maka dapat ditemukan sebarang penyelesaian / dari permasalahan (3.1) – (3.3) untuk suatu pengali Lagrange 0/ . 1, … , 1 yang memenuhi:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
93
-
1 23 ) / , */ 2 4 / / 5 2 / + , 0/ 2 + 0 2 .
-
⇔ / + , 0/ 0 . -
⇔ , 0/ /
.
/ , / " , λ/8 " 0,
#
3.4
!
(3.5)
#
λ/8 / + 0,
(3.6) (3.7) #
(3.8)
Jika matriks Hesse G adalah semidefinit positif, maka permasalahan (3.1) – (3.3) adalah permasalahan pemrograman kuadratik konveks dan peminimum lokal / adalah peminimum global.
Metode yang dapat digunakan untuk menyelesaikan permasalahan optimisasi pada pemrograman kuadratik konveks antara lain adalah metode himpunan aktif dan metode titik-interior. Metode titik-interior pada pemrograman kuadratik terbagi lagi menjadi dua, yakni metode jalan pusat (central path method) dan metode titik-interior primal-dual (primal-dual interior-point method). Namun dalam skripsi ini metode yang akan dibahas hanya metode titikinterior primal-dual.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
94
B. Metode Titik-Interior Metode titik-interior termasuk dalam kelas algoritma yang biasanya digunakan untuk menyelesaikan pemrograman linear dan pemrograman nonlinear, khususnya pemrograman kuadratik konveks. Algoritma ini berasal dari algoritma Karmakar yang diperkenalkan oleh Narendra Karmakar pada tahun 1984 untuk menyelesaikan pemrograman linear. Permasalahan pemrograman linear dapat diselesaikan dengan menggunakan metode grafik dan metode simpleks. Metode grafik biasanya digunakan untuk menyelesaikan permasalahan pemrograman linear yang memuat dua variabel, sedangkan untuk permasalahan pemrograman linear yang memuat dua variabel atau lebih biasanya dapat diselesaikan dengan menggunakan metode simpleks dan metode titikinterior. Titik-interior merupakan titik-titik yang berada di bagian dalam daerah layak. Pada metode simpleks, titik-titik yang dihasilkan dari algoritma berada pada batas dari daerah layak. Berbeda dengan metode simpleks, pada metode titik-interior titik-titik yang dihasilkan dari algoritma berada di bagian dalam dari daerah layak. Pemrograman kuadratik konveks yang memanfaatkan metode titikinterior bertujuan untuk membatasi pergerakan nilai optimum yang dihasilkan pada setiap iterasinya. Pemrograman kuadratik konveks dapat diselesaikan dengan beberapa metode, salah satunya yaitu dengan menggunakan metode titik-interior primal-dual.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
95
Metode titik-interior primal-dual untuk pemrograman linear dapat diterapkan ke dalam pemrograman kuadratik konveks melalui perluasan sederhana dari metode titik-interior primal-dual untuk pemrograman linear. Sebelum membahas mengenai metode titik-interior primal-dual untuk pemrograman kuadratik konveks, akan dibahas secara singkat terlebih dahulu mengenai permasalahan dual pada pemrograman linear. Permasalahan pemrograman linear mempunyai bentuk baku sebagai berikut: minimumkan ; : 9(
dengan kendala = >, " 0
3.9 (3.10)
dimana ;, ?( , >?(- , dan =?(-3 . Setiap permasalahan pemrograman linear selalu mempunyai dua macam permasalahan, yakni permasalahan primal dan permasalahan dual. Permasalahan primal dan permasalahan dual saling berkaitan. Permasalahan dual merupakan kebalikan dari permasalahan primal. Hubungan antara primal dengan dual adalah sebagai berikut: Jika permasalahan primal mempunyai n variabel dan m kendala, maka permasalahan dual mempunyai m variabel dan n kendala. Koefisien-koefisien pada fungsi obyektif dari permasalahan primal adalah koefisien-koefisien sisi kanan pada permasalahan dual. Matriks kendala pada permasalahan dual adalah transpose dari matriks kendala pada permasalahan primal. Dengan mengubah permasalahan primal menjadi permasalahan dual,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
96
maka proses perhitungan untuk permasalahan pemrograman linear akan lebih mudah diselesaikan, khususnya apabila permasalahan primalnya memuat variabel yang lebih banyak dibandingkan dengan kendalanya atau n > m. Permasalahan dual dari persamaan (3.9)-(3.10) adalah sebagai berikut:
3.11
maksimumkan > *
dengan kendala = * A ;
(3.12)
Persamaan (3.11)-(3.12) dapat dinyatakan kembali ke dalam bentuk yang sedikit berbeda dengan menambahkan peubah pengetat (slack variable) yang dinotasikan
dengan
B,
sehingga
dapat
ditulis
sebagai
maksimumkan > *
dengan kendala = * B ;, B " 0
berikut:
3.13 (3.14)
dimana peubah pengetat (slack variable) adalah peubah yang digunakan untuk mengubah sistem pertidaksamaan menjadi suatu sistem persamaan. Pengali Lagrange dari persamaan (3.9)-(3.10) dibagi menjadi dua, yakni vek-
tor * dan vektor B. *?(- adalah vektor pengali Langrange untuk kendala = > dan s ?( adalah vektor pengali Lagrange untuk kendala " 0.
Dengan menggunakan Definisi Fungsi Lagrange, fungsi Lagrange dari persamaan (3.9)-(3.10) dapat ditulis sebagai berikut:
), *, B ; + * = + > + B ; + = + > * + B
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
97
Bila Teorema Karush Kuhn Tucker diterapkan ke dalam persamaan (3.9)(3.10), maka akan ditemukan penyelesaian dari persamaan (3.9)-(3.10) untuk , dimana ada vektor * dan vektor B sedemikian sehingga
23 ), *, B 2; + 2= + > * + 2B 0 ⇔ ; + = * + B 0 ⇔ = * B ; = >
C 0, 1, … , D (x,s) " 0
(3.15) (3.16) (3.17) (3.18)
Permasalahan primal pemrograman kuadratik mempunyai bentuk yang sama seperti pada permasalahan (3.1)-(3.3). Dapat dianggap bahwa matriks G pada persamaan (3.1) adalah matriks semidefinit positif. Menyelesaikan permasalahan (3.1)-(3.3) sama halnya seperti menyelesaikan persamaan (3.4)(3.8). Misalkan ditetapkan bahwa E =F + dan G + ,
mana =
( 3- dan F
(- . Maka dari persamaan (3.4), E dapat dinyatakan
sebagai E , yang diperoleh dari -
, 0/ /
.
-
H , 0/ + /
.
#, di-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
98
-
H / I J, 0/ + K H /
.
I
-
E dimana E , 0/ +
H I E L 0, … , 0
.
Persaman (3.5) dan (3.6) apabila diubah ke dalam bentuk matriks menjadi / / + 0 G 0 O V O V O V P P P N / U N / U N U N -Q -Q U N -Q + -Q 0 U N G-Q 0 U N / " U N / + U NG-QRS " 0U -QRS -QRS " 0 N -QRS U N -QRS U P U P P N U N U N / / M - " - T M - + - " 0 T M G- " 0 T Sehingga persamaan (3.5)-(3.6) dapat ditulis menjadi = + > W0, … , 0, G-QX , … , G- Y
+> += W0, … , 0, G-Q X , … , G- Y
Dengan demikian, persamaan (3.4)-(3.8) dapat ditulis sebagai berikut: Z
+> += ] W0, … , 0, G , … , G- , 0, … , 0Y I [ \ X Q E L
=F + E G " 0,
G 0 0, 0 " 0,
#
(3.19) (3.20) (3.21)
#
#
(3.22) (3.23)
Persamaan (3.19)-(3.23) dapat digunakan untuk menyelesaikan permasalahan berikut:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 2
maksimumkan > F + E^ F,E
^
+1
dengan kendala =F + E 0 " 0,
a F, E E_Q
99
3.24
(3.25)
#
(3.26)
yang mana permasalahan (3.24)-(3.26) merupakan dual dari permasalahan (3.1)-(3.3). Pemrograman kuadratik konveks dengan kendala persamaan mempunyai bentuk baku sebagai berikut: minimumkan : (
1 2
dengan kendala = >, " 0 dimana
(D , >
(1 , =
(1xD , dan
3.27 (3.28)
(DxD matriks simetrik dan
semidefinit positif. Permasalahan dual dari permasalahan (3.27)-(3.28) adalah sebagai berikut:
1 2
maksimumkan > F + E^ 1 D F ( ,E (
^
+1
dengan kendala = F + d A
dimana
(D , >
(1 , =
E
(1xD , dan
3.29 (3.30)
(DxD matriks simetrik dan
semidefinit positif. Persamaan (3.29)-(3.30) dapat dinyatakan kembali ke dalam bentuk yang sedikit berbeda dengan menambahkan peubah pengetat (slack variable) yang
dinotasikan dengan e, sehingga dapat ditulis sebagai berikut:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1 2
maksimumkan > F + E^ 1 D F ( ,E,e (
^
+1
E
100
3.31
dengan kendala = F + d f
(3.32)
Sedangkan, permasalahan pemrograman kuadratik konveks dengan kendala pertidaksamaan adalah sebagai berikut: minimumkan : 9(
1 2
dengan kendala = " >
dimana
(D , >
(1 , =
(1xD , dan
3.33 (3.34)
(DxD dan G merupakan
matriks simetrik dan semidefinit positif. Dengan menggunakan Definisi Fungsi Lagrange, fungsi Lagrange dari persamaan (3.33)-(3.34) dapat ditulis sebagai berikut: ), *
1 + * = + > 2
1 + = + > * 2
Syarat KKT dari persamaan (3.33)-(3.34) adalah sebagai berikut: jika x* adalah penyelesaian optimum dari persamaan (3.33)-(3.34), maka ada vektor pe-
ngali Lagrange */ sedemikian sehingga syarat berikut dipenuhi untuk (x, *) =
(x*,*/ ) :
1 23 ), F 2 4 5 2 + 2= + > * 0 2 ⇔ + = * 0
(3.35)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
= + > " 0
= + > 0 0, 1, 2, … , 1 *"0
101
(3.36) (3.37) (3.38)
Pertidaksamaan (3.36) dapat diubah menjadi persamaan dengan menambahkan vektor pengetat yang dinotasikan dengan E, dimana E = + > dan
E " 0 sehingga diperoleh
+ = * 0 = + E + > 0
g 0 0, 1, 2, … , 1
E, * " 0
(3.39) (3.40) (3.41) (3.42)
Seperti kasus pada pemrograman linear, syarat KKT tidak hanya sebagai syarat perlu melainkan juga sebagai syarat cukup sehingga permasalahan (3.33)(3.34) dapat diselesaikan dengan menemukan penyelesaian dari sistem (3.39) – (3.42). Metode titik-interior primal-dual digunakan untuk menemukan penyelesaian primal-dual dari sistem KKT dengan menerapkan metode Newton yang diperoleh dari persamaan (2.50) ke dalam sistem (3.39)-(3.42) dan memodifikasi arah selidik (search direction) dan panjang langkah (step length) sehingga pertidaksamaan E, * " 0 dipenuhi secara tegas pada setiap iterasi.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
102
Untuk memperoleh metode titik-interior primal-dual, sistem (3.39)(3.42) dinyatakan kembali ke dalam bentuk yang lain dengan mendefinisikan F dari (-X ke (-X , yakni
+ = * h, E, * i = + E + > l 0, E, * " 0 jΛk
(3.43)
dimana j diagg , g , … , g- , Λ diag0 , 0 , … , 0- , k 1, 1, … . , 1 .
Bentuk h, E, * dapat pula dinyatakan ke dalam bentuk
h, E, * m , E, *, m , E, *, mn , E, *
Metode titik-interior primal-dual menghasilkan iterasi o , E o , *o
yang memenuhi batas E, * " 0, dimana E o p 0 dan *o p 0. Sifat ini merupakan sifat dasar dari titik-interior. Metode Newton membentuk model linear dari F di sekitar titik terten-
tu dan memperoleh arah selidik (search direction) ∆, ∆E, ∆* dengan menyelesaikan sistem persamaan linear berikut ∆ r, E, * i∆El +h, E, * ∆*
(3.44)
dimana J adalah matriks Jacobi dari F, yakni
sm , E, * sm , E, * sm , E, * O V s sE s* N U Nsm , E, * sm , E, * sm , E, *U r, E, * N U s sE s* N U Nsmn , E, * smn , E, * smn , E, *U M s sE s* T
3.45
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
103
Bila persamaan (3.45) diterapkan ke dalam persamaan (3.43) , maka diperoleh r, E, * i= 0
0 +L Λ
+= 0 l j
(3.46)
Substitusikan persamaan (3.43) dan persamaan (3.46) ke dalam persamaan (3.44) sehingga diperoleh sistem linear i= 0
0 +L Λ
+uv += ∆ 0 l i∆El i +uw l +jΛk ∆* j
(3.47)
dimana uv + = * , uw = + E + >.
Diberikan iterasi tertentu, yakni (, E, * yang memenuhi (E, * p 0,
sehingga dapat diterapkan ukuran dualitas yang dinotasikan dengan x yang didefinisikan dengan -
1 E * x , g 0 1 1 .
yang mana merupakan ukuran nilai rata-rata dari hasil kali g 0 .
Dengan menentukan x dan menambahkannya ke dalam persamaan (3.47), diperoleh
dengan y dimana |
i= 0
0 +L Λ
+uv += ∆ +uw l 0 l i∆El i +jΛk yxk ∆* j
z0,1{. Iterasi selanjutnya diperoleh dengan membentuk
oX , E oX , *oX , E, * |∆, ∆E, ∆* 0,1{ sehinggaE oX , *oX > 0.
(3.48)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
104
Metode titik-interior primal-dual menerapkan metode Newton untuk menemukan penyelesaiannya. Konvergensi pada metode Newton akan diperoleh jika nilai awal yang dipilih berasal dari titik-interior. Oleh karena itu, berdasarkan Teorema 2.5.1 dan Teorema 2.5.2, dapat disimpulkan bahwa nilai awal yang dipilih dari sebarang titik-interior pasti akan konvergen, sebaliknya apabila nilai awal yang dipilih berada di luar titik-interior, maka konvergensinya belum tentu akan diperoleh. Berikut akan diberikan algoritma dari metode titik-interior primal-dual untuk menyelesaikan permasalahan (3.33)-(3.34). Algoritma 3.2.1
Langkah 1. Diberikan } , E } , *} dengan E } , *} p 0 ; Langkah 2. Untuk 0,1,2, … Selesaikan i= 0
0 +L Λo
dimana yo
+uv += ∆ o o +uw o , 0 l ∆E o o o j ∆* +Yo Λ k yo xo k o
z0,1{ dan xo E o *o /1 ;
Bentuk oX , E oX , *oX o , E o , *o |o ∆ o , ∆E o , ∆*o , dipilih |o sedemikian sehingga E oX , *oX p 0.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
105
Langkah 3. Hitung oX + o .
Jika oX + o
toleransi, maka langkah dihentikan.
Sebaliknya, jika oX + o p toleransi, maka lanjut ke langkah 2. ▄
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Diagram alir dari algoritma metode titik-interior primal-dual.
Start
Masukkan
o , E o , *,o , , =, , > 0
Λo diag*o Yo diagE o yo
z0,1{
xo E o *o /1 F o , E o , *,o =+uv o ; +uw o ; +Yo Λo k yo xo k r o , E o , *,o = 0 += ; = + L 0; 0 Λo Yo ∆ o I ∆E o r o , E o , *,o / F o , E o , *,o ∆*o 1
106
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
107
1 oX , E oX , *oX o , E o , *o |o ∆ o , ∆E o , ∆*o , |o 0,1{ E
oX
,*
oX
p0
Tidak
|o + 0.1
Ya oX + o
!
Tidak
1
Ya
oX Stop
Gambar 3.2.1 Diagram Alir Algoritma Metode Titik-Interior Primal-Dual
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
108
Berikut ini akan diberikan contoh pemrograman kuadratik konveks dengan kendala pertidaksamaan yang diselesaikan dengan menggunakan metode titikinterior primal-dual.
Contoh 3.2.1: Minimumkan + 2 + 5 7.25
3.49
dengan kendala + 2 " +2
3.50
+ + 2 " +6
3.51
, " 0
3.53
+ 2 " +2
3.52
Penyelesaian: Apabila persamaan (3.49)-(3.53) diubah ke dalam bentuk pemrograman kuadratik konveks, maka diperoleh minimumkan 9(
1 2
1 z 2
{ \2 0] \ ] z 0 2
1 +2 +2 dengan kendala = " > atau i+1 +2l \ ] " i+6l. +1 2 +2 Sehingga diperoleh
2 \ 0
1 +2 +2 0 +2 ] , \ ] , = i+1 +2l , > i+6l. 2 +5 +1 2 +2
{ \+2] +5
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
109
Untuk menyelesaikan permasalahanan di atas, ikuti langkah-langkah dari algoritma metode titik-interior primal dual. Iterasi 0 Langkah 1
2 3 2 Misalkan diberikan } \ ] , E } i2l , *} i3l dan toleransi ! 10In. 0 1 1 Langkah 2
Untuk 0, akan diselesaikan sistem
i= 0
+uv += ∆ } +uw } 0 l i∆E } l } } } } j ∆* +Y Λ k y} x} k }
0 +L Λ}
2 3 2 0 Karena E } i2l dan *} i3l, maka j } i0 2 1 1 0 0 3 Λ} i0 0
Sehingga
0 0 3 0l . 0 1
+uv } + } + = *} 2 + J\ 0
0 2 1 +1 ]\ ] + \ 2 0 +2 +2
4 +1 +2 + \ ] + \ ] \ ] 0 +10 +5 3 + \ ] 5 \
+3 ] +5
0 0l dan 1
3 +2 +1 ] i3l \ ]K +5 2 1
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
+uw } += } + E } + >
1 +2 2 +2 2 + Ji+1 +2l \ ] + i2l + i+6lK 0 +1 2 1 +2
2 2 +2 =+ Ji+2l + i2l + i+6lK +2 1 +2 2 =+ Ji 2 lK +1 +2 i+2l 1
x} - E } *} n z2 2
3 1{ i3l 4.333. 1
Misalkan, dipilih y} 0.4, maka 2 0 +j } Λ} k y} x} k + Ji0 2 0 0
6 + Ji0 0
Sehingga } i= 0
0 +L Λ}
0 3 0 0 1 1 0l i0 3 0l i1lK 0.44.333 i1l 1 0 0 1 1 1 0 0 1 1.7332 6 0l i1lK i1.7332l 0 1 1 1.7332
6 1.7332 +4.2668 + i6l i1.7332l i+4.2668l 1 1.7332 0.7332 +uv += ∆ } +uw } 0 l i∆E } l } } j } ∆*} +Y Λ k y} x} k }
110
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
0 0 0 2 0 2 0 0 1 − 2 −1 0 − 1 − 2 0 − 1 ⇔ 0 0 − 1 2 0 0 3 0 0 0 0 3 0 0 0 0
0 −1 1 1 0 2 2 − 2 ∆ } 0 0 0 0 i∆E } l 0 0 0 0 } − 1 0 0 0 ∆* 0 2 0 0 0 0 2 0 1 0 0 1
+3 O +5 V N +2 U N U N +2 U 1 N+4.2668U N+4.2668U M 0.7332 T
Dengan demikian ∆ } i∆E } l ∆*}
0 0 0 2 0 2 0 0 1 − 2 −1 0 − 1 − 2 0 − 1 0 0 − 1 2 0 0 3 0 0 0 0 3 0 0 0 0
+0.4538 O 1.0051 V N+0.4641U N U N 0.4436 U N 1.4641 U N+1.4373U N+2.7987U M+0.7309T
Jadi, diperoleh ∆ } \
0 −1 1 1 0 2 2 − 2 0 0 0 0 0 0 0 0 − 1 0 0 0 0 2 0 0 0 0 2 0 1 0 0 1
111
I
+3 O +5 V N +2 U N +2 U N U 1 N+4.2668U N+4.2668U M 0.7332 T
+0.4641 +1.4373 +0.4538 ] , ∆E } i 0.4436 l , ∆*} i+2.7987l . 1.0051 1.4641 +0.7309
Untuk nilai , E , * diperoleh dari persamaan
, E , * } , E } , *} |} ∆ } , ∆E } , ∆*}
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Untuk |}
112
2 + |} 0.4538 2 +0.4538 O V O 1.0051 V O0V 0 |} 1.0051 N U N+0.4641U N2U 2 + |} 0.4641 N U N U N2U 2 | 0.4436 0.4436 } U UN N U |} N 1 N 1.4641 U N 1 |} 1.4641 U N3U N+1.4373U N3 + |} 1.4373U N3U N+2.7987U N 3 + | 2.7987 U } M1T M+0.7309T M1 + | 0.7309T } 0,1{, maka E , * p 0.
Misalkan dipilih |} 1. Sehingga diperoleh
1.5462 O1.0051V N1.5359U N U , E , * N2.4436U N2.4641U N1.5627U N0.2013U M0.2691T dimana \
Langkah 3
1.5359 1.5627 1.5462 ] , E i2.4436l , * i0.2013l. 1.0051 2.4641 0.2691
Hitung + } 1.5462 + 2 1.0051 + 0 1.1028
Karena + } p toleransi ! 10In , maka dilanjutkan ke iterasi berikutnya.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
113
Iterasi 1 Langkah 2
Untuk 1, akan diselesaikan sistem i= 0
+uv += ∆ +uw 0 l i∆E l j ∆* +Y Λ k y x k
0 +L Λ
Karena j i
1.5359 0 0
Sehingga
1.5359 E i2.4436l 2.4641 0 2.4436 0
dan
1.5627 * i0.2013l, 0.2691
0 1.5627 l dan Λ i 0 0 2.4641 0
+uv + + = * 2 + J\ 0
1.5627 0 1.5462 +2 1 +1 +1 ]\ ]+\ ] i0.2013l \ ]K 2 1.0051 +5 +2 +2 2 0.2691
3.0924 +2 1.0925 + \ ]+\ ] \ ] 2.0102 +5 +2.9898 0.0001 + \ ] 0 \
0 0.2013 0
+0.0001 ] 0
+uw += + E + >
1 +2 +2 1.5359 1.5462 + Ji+1 +2l \ ] + i2.4436l + i+6lK 1.0051 +1 2 +2 2.4641
maka 0 0 l. 0.2691
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
+0.4640 +2 1.5359 =+ Ji+3.5564l + i2.4436l + i+6lK 0.4640 +2 2.4641
0.0001 =+ Ji lK 0 +0.0001 +0.0001 i l 0 0.0001
x E * z1.5359 n
2.4436
Misalkan, dipilih y 0.4, maka +j Λ k y x k 1.5359 0 0
0 2.4436 0
0 1.5627 0 li 0 2.4641 0
2.4002 0 0
0 0.4919 0
0 1 0.4716 0 l i1lK i0.4716l 0.6453 1 0.4716
+ Ji
1 0.41.1791 i1l 1
+ Ji
1.5627 2.4641{ i0.2013l 1.1791. 0.2691
2.4002 0.4716 +1.9286 + i0.4919l i0.4716l i+0.0203l 0.6453 0.4716 +0.1737
Sehingga i= 0
0 +L Λ
+uv += ∆ +uw 0 l i∆E l j ∆* +Y Λ k y x k
0 0.2013 0
1 0 0 l i1lK 0.2619 1
114
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2 0 1 −1 ⇔ −1 0 0 0
0 2
0 0
−2 −2 2
−1 0 0
0 0 −1 1 1 0 0 2 2 −2 −1 0
0 0 0 0 0 0 0 0 0 0 −1
0 0
+0.0001 O V 0 N +0.0001U ∆ N U 0 i∆E l N 0.0001 U ∆* N+1.9286U N+0.0203U M+0.1737T
0 1.5627 0 0 1.5359 0 0 0 0 0.2013 0 0 2.4436 0 0 0 0 0.2619 0 0 2.4641
Dengan demikian ∆ i∆E l ∆*
115
0 0 0 0 −1 1 1 2 0 2 0 0 0 2 2 − 2 1 −2 −1 0 0 0 0 0 − 1 − 2 0 −1 0 0 0 0 0 0 0 0 0 −1 − 1 2 0 0 1.5627 0 0 1.5359 0 0 0 0 0 0.2013 0 0 2.4436 0 2.4641 0 0 0 0.2619 0 0 0
+0.1745 O 0.2965 V N+0.7675U N U N+0.4186U N 0.7675 U N+0.4748U N 0.0262 U M+0.1521T
Jadi, diperoleh ∆ \
+0.0001 V 0 N+0.0001U N U 0 N 0.0001 U N+1.9286U N+0.0203U M+0.1737T
I O
+0.4748 +0.7675 +0.1745 ] , ∆E i+0.4186l , ∆* i 0.0262 l . 0.2965 +0.1521 0.7675
Untuk nilai , E , * diperoleh dari persamaan , E , * , E , * | ∆ , ∆E , ∆*
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Untuk |
116
1.5462 + | 0.1745 1.5462 +0.1745 O V O1.0051V O 0.2965 V 1.0051 | 0.2965 N U N1.5359U N+0.7675U 1.5359 + | 0.7675 N U N U N U 2.4436 + | 0.4186 2.4436 +0.4186 U U | N UN N N2.4641U N 0.7675 U N 2.4641 | 0.7675 U N1.5627U N+0.4748U N1.5627 + | 0.4748U N0.2013U N 0.0262 U N 0.2013 | 0.0262 U M0.2691T M+0.1521T M0.2691 + | 0.1521T 0,1{, maka E , * p 0.
Misalkan dipilih | 1. Sehingga diperoleh
1.3717 O1.3016V N0.7684U N U , E , * N2.0250U N3.2316U N1.0879U N0.2275U M0.1170T
dimana \ Langkah 3
0.7684 1.0879 1.3717 ] , E i2.0250l , * i0.2275l. 1.3016 3.2316 0.1170
Hitung + 1.3717 + 1.5462 1.3016 + 1.0051 0.3440
Karena + p toleransi ! 10In , maka dilanjutkan ke iterasi berikutnya.
Proses iterasi akan terus dilanjutkan sampai +
toleransi ! 10In.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
117
Berikut ini akan diberikan penyelesaian dengan menggunakan program MATLAB. Tabel 3.2.1 Output Penyelesaian Contoh 3.2.1 dengan Matlab. =================================================== Iterasi
x(1)
x(2)
dif
=================================================== 0
2.00000
0.00000
-
1
1.54615
1.00513
1.10284
2
1.37261
1.29865
0.34098
3
1.34579
1.50456
0.20765
4
1.36165
1.61258
0.10918
5
1.38106
1.66296
0.05399
6
1.39212
1.68474
0.02443
7
1.39686
1.69382
0.01024
8
1.39875
1.69751
0.00415
9
1.39950
1.69900
0.00167
10
1.39980
1.69960
0.00067
=================================================== Pada saat iterasi ke-10, oX + o
toleransi ! 10In. Jadi, nilai x yang meminimalkan fungsi adalah: 1.39980 dan 1.69960.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
118
Nilai awal yang digunakan untuk menyelesaikan pemrograman kuadratik konveks dapat diubah-ubah, yakni dengan cara mensubstitusikan E } dan *} yang berbeda-beda dengan tujuan agar iterasi yang dihasilkan lebih se-
dikit. Berikut ini akan diberikan tabel perbandingan pengaruh nilai awal dan jumlah iterasi yang diperlukan oleh metode titik-interior primal-dual untuk menyelesaikan fungsi obyektif m + 2 + 5 7.25 dengan toleransi ! 10In.
Tabel 3.2.2 Tabel Perbandingan Nilai Awal Metode Titik-Interior PrimalDual. No
}
E }
*}
/
Banyaknya Iterasi
1. 2. 3. 4. 5. 6. 7. 8.
2,0 2,0 2,0 2,0 2,0 2,0
2,2,1 5,4,2 6,3,4 7,8,2
9,5,10
14,8,10
2,0 15,12,10 2,0
17,9,15
3,3,1 4,6,3 7,2,5 6,3,7
6,8,11 7,5,9
8,12,15 11,5,9
1.39980 ,1.69960 1.39982 ,1.69964 1.39988,1.69975 1.39985,1.69970 1.39973,1.69946 1.39987,1.69973 1.39984,1.69968 1.39979,1.69959
10 12 13 13 13 14 14 14
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
9. 10.
2,0
20,6,17
7,10,6
2,0 22,17,14 15,19,13
1.39972,1.69943 1.39980,1.69959
119
13 15
Dengan menggunakan Tabel 3.2.2, dapat dilihat bahwa dengan nilai awal
E } dan *} yang berbeda-beda, permasalahan optimisasi ini akan memi-
liki penyelesaian yang sama, yakni mendekati 1.39980 ,1.69960 . Pemili-
han nilai awal E } dan *} yang cukup dekat dengan penyelesaian akan menghasilkan iterasi yang lebih sedikit.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB IV PENUTUP
A. Kesimpulan Berdasarkan pembahasan pada bab-bab sebelumnya, maka dapat ditarik beberapa kesimpulan berikut: Metode titik-interior khususnya metode titik-interior primal dual adalah metode yang digunakan untuk menyelesaikan pemrograman kuadratik konveks. Metode ini merupakan pengembangan lebih lanjut dari metode titikinterior primal-dual untuk pemrograman linear yang bertujuan untuk membatasi pergerakan nilai optimum yang dihasilkan pada setiap iterasinya dengan toleransi tertentu. Metode titik-interior primal-dual digunakan untuk menemukan penyelesaian primal-dual dengan menerapkan metode Newton dan memodifikasi arah selidik dan panjang langkah. Metode titik-interior primal-dual mempunyai kelebihan dan kekurangan. Kelebihan dari metode titik-interior primal-dual adalah pencarian penyelesaian optimum dimulai dari sebarang titik-interior sehingga konvergensinya akan lebih cepat diperoleh. Metode titik-interior memerlukan langkah
120
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
121
yang sedikit, yang mana setiap arah selidik relatif mudah untuk dihitung. Sedangkan, kekurangan dari metode titik-interior primal-dual adalah pemilihan nilai awal yang berada di luar titik-interior mengakibatkan konvergensinya belum tentu akan diperoleh.
B. Saran Berikut ini diberikan beberapa saran yang dapat dijadikan permasalahan untuk dibahas lebih lanjut yang berhubungan dengan metode titik-interior primal-dual: 1. Metode titik-interior primal dual untuk menyelesaikan pemrograman kuadratik konveks dengan kendala nonlinear. 2. Metode titik-interior primal-dual untuk menyelesaikan permasalahan optimisasi seperti Sequential Quadratic Programming.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR PUSTAKA
Anggi, M. N. (2007). Penyelesaian Sistem Persamaan Non-linear dengan Metode Newton dan Terapannya. Skripsi. Yogyakarta: FST USD. Anton, H. and Chris, R. (2004). Aljabar Linear Elementer Versi Aplikasi. Edisi Kedelapan. Jilid 1. (Terjemahan). Jakarta: Erlangga. Bartle, R.G. and Sherbert, D.R. (1999). Introduction to Real Analysis. New York: John Wiley and Sons, Inc. Boyd, S. and Vandenberghe, L. (2004). Convex Optimization. New York: Cambridge University Press. Budhi, W. S. (1995). Aljabar Linear. Jakarta: Gramedia Pustaka Utama. Burden, R.L. and Faires, J. D. (1985). Numerical Analysis. Boston: PWS Publisher. Folland, G.B. (1999). Real Analysis. New York: John Wiley & Sons, Inc. Leon, S. J. (2001). Aljabar Linear dan Aplikasinya. (Terjemahan). Edisi Kelima. Jakarta: Erlangga. Lipschutz, S. and Lipson, M.L. (2001). Matematika Diskret I. Jakarta: Salemba Teknika. Nash, G. S. and Sofer, A. (1996). Linear and Nonlinear Programming. New York: McGraw-Hill Companies, Inc.
122
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
123
Nocedal, J. and Stephen, J.W. (2006). Numerical Optimization 2nd. New York: Springer. Prayudi. (2008). Kalkulus Lanjut. Yogyakarta: Graha Ilmu. Purcell, E.J. dan Dale, V. (1996). Kalkulus. Jilid 1. (Terjemahan). Jakarta: Erlangga. Soemantri, R., dkk. (2006). Diktat Pengantar Analisis Real. Yogyakarta: FMIPA USD. Sun, W. and Ya-Xiang Yuan. (2006). Optimization Theory and Methods. New York: Springer.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
124
LAMPIRAN PROGRAM UTAMA: Listing Program clear clc disp('------------------------------------------------'); disp(' disp('
Metode Titik-Interior Primal-Dual
');
untuk Menyelesaikan Pemrograman Kuadratik Konveks
'); disp('
Q(x)=1/2*(x^T*G*x)+x^T*g
');
disp('
dengan A*x>=b
');
disp('------------------------------------------------'); disp('min x(1)^2+x(2)^2-2*x(1)-5*x(2)+7.25'); disp('dengan x(1)-2x(2)>=-2'); disp('
-x(1)-2x(2)>=-6');
disp('
-x(1)+2x(2)>=-2');
disp('
x(1),x(2)>=0');
disp('permasalahan tersebut diubah ke dalam bentuk'); disp('pemrograman kuadratik konveks, sehingga diperoleh'); disp('G=[2 0;0 2];g=[-2;-5];A=[1 -2;-1 -2;-1 2];b=[-2;6;-2]'); x=input('masukkan x0='); y=input('masukkan y0='); lamda=input('masukkan lamda0='); G=input('masukkan G='); A=input('masukkan A='); g=input('masukkan g='); b=input('masukkan b=');
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
tol=10^(-3); k=1; x0=[x;y;lamda]; dif=1;
disp('Iterasi
x1
x2
while dif>tol n=length(x); m=length(y&lamda); x=x0(1:n,1); y=x0(n+1:m+n,1); lamda=x0(n+m+1:n+2*m,1);
lamdbes=diag(lamda); ybes=diag(y); sigma=0.4; miu=(y'*lamda)/m; e=ones(m,1);
f1=-(G*x-A'*lamda+g); f2=-(A*x-y-b); f3=-(ybes*lamdbes*e)+(sigma*miu*e); fx=[f1;f2;f3];
j11=G; j12=zeros(n,m); j13=-(A'); j21=A; j22=-(eye(m));
dif')
125
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
j23=zeros(m,m); j31=zeros(m,n); j32=lamdbes; j33=ybes; jx=[j11 j12 j13;j21 j22 j23;j31 j32 j33];
del=inv(jx)*fx; alpha=1; x1=x0+(alpha*del);
if x1(n+1:n+2*m,1)<0 alpha=alpha-0.1; x1=x0+(alpha*del); else x1=x1; end
x2=x1(1:n,1);
dif=norm(x1(1:n,1)-x0(1:n,1));
fprintf('\n%3.0f%15.5f%15.5f%15.5f',k,x1(1),x1(2),dif) if dif
126
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
127
x=x2; disp('------------------------------------------------'); disp('Terima kasih anda telah menggunakan program ini.');
OUTPUT --------------------------------------------------Metode Titik-Interior Primal-Dual untuk Menyelesaikan Pemrograman Kuadratik Konveks Q(x)=1/2*(x^T*G*x)+x^T*g dengan A*x>=b --------------------------------------------------min x(1)^2+x(2)^2-2*x(1)-5*x(2)+7.25 dengan x(1)-2x(2)>=-2 -x(1)-2x(2)>=-6 -x(1)+2x(2)>=-2 x(1),x(2)>=0 permasalahan tersebut diubah ke dalam bentuk pemrograman kuadratik konveks, sehingga diperoleh G=[2 0;0 2];g=[-2;-5];A=[1 -2;-1 -2;-1 2]; b=[-2;-6;-2] masukkan x0=[2;0] masukkan y0=[2;2;1] masukkan lamda0=[3;3;1] masukkan G=[2 0;0 2] masukkan A=[1 -2;-1 -2;-1 2] masukkan g=[-2;-5] masukkan b=[-2;-6;-2] Iterasi
x(1)
x(2)
dif
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
1
1.54615
1.00513
1.10284
2
1.37261
1.29865
0.34098
3
1.34579
1.50456
0.20765
4
1.36165
1.61258
0.10918
5
1.38106
1.66296
0.05399
6
1.39212
1.68474
0.02443
7
1.39686
1.69382
0.01024
8
1.39875
1.69751
0.00415
9
1.39950
1.69900
0.00167
10
1.39980
1.69960
0.00067
128
--------------------------------------------------------Terima kasih anda telah menggunakan program ini. Jadi, nilai x yang meminimumkan fungsi adalah: 1.39980,1.69960 .