ANALISIS KARAKTERISTIK FUNGSI LAGRANGE
TESIS
Oleh
ANDY SAPTA 067021012/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
ANALISIS KARAKTERISTIK FUNGSI LAGRANGE
TESIS
Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara
Oleh
ANDY SAPTA 067021012/MT
SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2008
Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi
: : : :
ANALISIS KARAKTERISTIK FUNGSI LAGRANGE Andy Sapta 067021012 Matematika
Menyetujui, Komisi Pembimbing
(Drs. Opim Salim S, MIKom, Ph.D.) Ketua
(Dr. Saib Suwilo, M.Sc) Anggota
Ketua Program Studi
Direktur
(Prof. Dr. Herman Mawengkang)
(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)
Tanggal lulus: 4 Juni 2008
Telah diuji pada Tanggal 4 Juni 2008
PANITIA PENGUJI TESIS
Ketua
:
Drs. Opim Salim S, MIKom, Ph.D.
Anggota
:
Dr. Saib Suwilo, M.Sc Prof. Dr. Herman Mawengkang Drs. Sawaluddin, MIT
ABSTRAK Masalah fungsi Lagrange, dengan fungsi objektif tidak linier, biasanya diselesaikan dengan menggunakan metode subgradien, yang konfergensinya dijamin jika nilai optimasi dari dua fungsi objektif diketahui. Pada prkateknya nilai optimal kurang diketahui dalam menghitung batas sebelumnya. Dalam penelitian ini, kita menggabungkan metode subgradein dengan pilihan dari nilai optimal. Biasanya kita menambahkan daya gerak pada arah subgradien yang proses akselerasinya dipusatkan ke dalam masalah yang umum dan untuk uraian dari algoritma yang baru, kita selesaikan dengan komponen Lagrange dengan program bilangan bulat. Faktanya, kita menyajikan hasil dari sekumpulan masalah dan masalah umum. Kata kunci : Lagrange, Lagrange dual, Optimasi Subgradein, Relaksasi Lagrange
i
ABSTRACT The Lagrange problem, with a non-differentiable convex objective function, is usually solved by using the subgradient method, whose convergence is guaranteed if the optimal value of the dual objective function is know. In practice, this optimal value is approximated by a previously computed bound. In this work, we combine the subgradient method with a different choice of steplength, based on the recently developed spectral projected gradient method, that does not require either exact or approximated estimates of the optimal value. We also add a momentum term to the subgradient dirction that accelerates the convergence process towards global solutions. To illustrate the behavior of our new algoritm we solve Lagrange problem associated with integer programming problem. In particular, we present encouraging numerical result for set covering problems and generalzed assignment problems. Keywords : Lagrangean, Lagrangean dual, Subgradient Optimization, Lagrange Relaxation
ii
KATA PENGANTAR Puji dan syukur penulis haturkan kehadirat Allah SWT. yang memberikan Rahmat dan Ridha-Nya sehingga penulis dapat menyelesaikan tesis ini. Dalam penulisan tesis ini, penulis banyak menghadapi kendala dan hambatan. Namun berkat motivasi serta bantuan dari berbagai pihak akhirnya penulisan tesis ini dapat diselesaikan. Untuk itu penulis menghaturkan terima kasih kepada: Bapak Prof. Dr. Chairuddin P. Lubis, DTM&H Sp. Ak, selaku Rektor Universitas Sumatera Utara yang telah memberi kesempatan kepada penulis untuk mengikuti perkuliahan di Program Pascasarjana Universitas Sumatera Utara. Ibu Prof. Dr. Ir. T. Cairun Nisa selaku Direktur Pascasarjana Universitas Sumatera Utara yang telah banyak memberikan bantuan dalam segala urusan administrasi di Program Pascasarjana Universitas Sumatera Utara. Bapak Prof. Dr. Herman Mawengkang dan bapak Dr. Saib Suwilo, M.Sc. Selaku ketua dan sekretaris Program Studi Matematika Program Pascasarjana Universitas Sumatera Utara. Bapak Drs. Opim Salim S, MIKom, Ph.D. dan bapak Dr. Saib Suwilo, M.Sc. selaku dosen pembimbing yang selalu memberikan pengarahan serta bimbingan kepada penulis sehingga terselesaikannya tesis ini. Bapak Prof. Dr. Herman Mawengkang dan bapak Drs. Sawaluddin, MIT. selaku dosen pembanding yang telah memberikan masukan guna perbaikan dan kesempurnaan tesis ini.
iii
Seluruh staf pengajar dan tenaga administrasi Program Studi Matematika Program Pascasarjana Universitas Sumatera Utara. BAPEDA Sumatera Utara yang telah memberikan bantuan finansial dalam mengikuti perkualiahan di Program Studi Matematika Program Pascasarjana Universitas Sumatera Utara. Seluruh civitas akademika Sekolah Pascasarjana Universitas Sumatera Utara yang telah membantu penulis dalam penyelesaian tesis ini. Istri tercinta Suri Rikawati, S.Pd. dan ananda Khayla Utami S.P. yang telah memberikan dorongan moril. Semoga hasil penelitian ini dapat bermanfaat bagi pengembangan pendidikan di masa datang.
Medan, September 2008 Penulis,
Andy Sapta
iv
RIWAYAT HIDUP Andy Sapta, lahir di Kisaran 8 September 1978.
Setelah lulus sekolah
menengah di Kisaran tahun 1996, melanjutkan ke Universitas Negeri Medan (UNIMED) program studi Pendidikan Matematika dan pada tahun 2002 memperoleh gelar Sarjana Pendidikan. Melanjutkan kuliah Program Pascasarjana pada tahun 2004 di UNIMED Program Studi Teknologi Pendidikan, dan pada tahun 2007 memperoleh gelar Magister Pendidikan. Mengawali karir pada tahun 2002 sebagai staf pengajar Matematika di SMA Swasta Harapan Medan. Tahun 2004 diangkat sebagai PNS di SMA Negeri 1 Buntu Pane, Kabupaten Asahan. Tahun 2008 sebagai staf pengajar di Universitas Asahan, dan pada tahun yang sama juga sebagai staf pengajar di Universitas Terbuka UPBJJ-Medan.
v
DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . .
iii
RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . .
v
DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vi
DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . .
viii
BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . .
1
1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . .
1
1.2 Perumusan Masalah . . . . . . . . . . . . . . . . . . . .
3
1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . .
3
1.4 Metodologi Penelitian . . . . . . . . . . . . . . . . . . .
3
1.5 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . .
3
BAB 2 KAJIAN PUSTAKA FUNGSI LAGRANGE . . . . . . . . . .
5
BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . .
10
3.1 Definisi . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3.2 Relaksasi Lagrange Untuk Masalah Bilangan Bulat Linier .
11
3.3 Penafsiran Geometris . . . . . . . . . . . . . . . . . . .
11
3.4 Fungsi Lagrange dan Kondisi Optimal . . . . . . . . . . .
13
vi
3.5 Titik Pusat Analitik
. . . . . . . . . . . . . . . . . . .
16
BAB 4 KARAKTERISTIK FUNGSI LAGRANGE PADA PENENTUAN TITIK PUSAT ANALITIK POLYTOPE . . . . . . . . . . .
18
4.1 Analisis Karakteristik . . . . . . . . . . . . . . . . . . .
18
4.2 Karakteristik Fungsi Lagrange . . . . . . . . . . . . . . .
22
BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . .
26
DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . .
27
vii
DAFTAR GAMBAR
Nomor
Judul
Halaman
3.1
Penafsiran Geometri dari Relaksasi Lagrange . . . . . . . . .
12
4.1
Fungsi Lagrange . . . . . . . . . . . . . . . . . . . . . . .
23
4.2
Contur Fungsi Lagrange . . . . . . . . . . . . . . . . . . .
24
viii
BAB 1 PENDAHULUAN
1.1 Latar Belakang Misalkan suatu fungsi f (x) = axn +bxn−1 +cxn−2 +· · · +G dengan membuat f 0 (x) = 0 akan diperoleh jenis-jenis dari nilai stasioner dengan menguji tandatanda f 0 (x) di sekitar nilai-nilai stasionernya. Cara ini dikenal dengan tes turunan pertama, cara lain untuk menentukan nilai stasioner dapat digunakan tes turunan kedua yang dirumuskan sebagai berikut: Misalkan fungsi f(x) kontinu dalam interval b < x < c yang memuat x = a. Turunan pertama f 0 (x) dan turunan kedua f 00 (x) terdefinisi dalam interval itu dan f 0 (a).
(i) Jika f 00(a) < 0, maka f(a) adalah nilai balik maksimum fungsi f . (ii) Jika f 00(a) > 0, maka f(a) adalah nilai balik minimum fungsi f .
Bila diperhatikan fungsi di atas hanya memuat satu variabel saja. Permasalahan yang muncul adalah bagaimana menentukan nilai stasioner bila fungsinya lebih dari satu variabel. Menentukan nilai optimum (nilai maksimum atau nilai minimum) suatu fungsi matematik multivariabel dalam teori optimasi dengan domain atau kendala (constrains) berupa suatu persamaan adalah suatu masalah optimasi yang sering ditemukan dalam teori maksimum dan minimum yang terdapat dalam kalkulus. Metoda matematik yang digunakan dalam menyelesaikan masalah tersebut adalah dengan menggunakan metoda fungsi Lagrange. 1
2 Untuk memecahkan masalah optimasi dengan menggunakan fungsi Lagrange dilakukan dengan beberapa langkah sebagai berikut: Pertama, Membentuk suatu ”Lagrange” L, maka dapat dihitung titik-titik kritisnya dan akhirnya dapat diuji nilai untuk fungsi objektif pada setiap titik-titik kritis tersebut dan menentukan titik dari titik-titik kritis tersebut yang membuat nilai fungsi objektif optimum. Jadi dalam hal ini dibentuk suatu fungsi L : Rn → l P λi hi (x). Selanjutnya, fungsi Rl , yang didefinisikan dengan L : (x, λ) = f (x) + i=I
objektif f (x) dioptimumkan terhadap x ∈ ∆. Kedua, mencari semua solusi (x, λ) dalam himpunan persamaan ∂L (x, λ) = 0, j = 1, . . . , n ∂ xj Dimana ∂L ∂ xi
λi
(x, λ) ≥ 0, λ ≥ 0 ∂L ∂ xi
(x, λ) = 0, i = 1, . . . , l
Setiap solusi dari sistem persamaan ini disebut titik kritis dari L. Ketiga, Menghitung nilai dari f pada setiap titik x dalam himpunan {x| ada λ sedemikian hingga (x, λ) ∈ M}. Dari uraian singkat di atas terlihat bahwa fungsi Lagrange bermanfaat dalam menstransformasi ke persoalaan optimisasi berkendala menjadi persoalaan optimisasi tanpa kendala. Perlu diperhatikan bahwa pada kebanyakan persoalanpersoalan optimisasi dengan kendala dapat diselesaikan setelah persoalan tersebut diubah menjadi persoalan optimisasi tanpa kendala (Kojiwa et al, 1992), atau dengan merelaksasikan kendala yang menyulitkan dengan fungsi Lagrange (Rong et al, 2008). Metode yang menggunakan fungsi Lagrange selalu disebut sebagai
3 metode relaksasi Lagrange.
1.2 Perumusan Masalah Fungsi Lagrange sering dipakai menyelesaikan permasalahan optimisasi, dalam penggunaannya fungsi Lagrange memiliki beberapa karakteristik. Untuk itu perlu dianalisis karakteristik tersebut.
1.3 Tujuan Penelitian Untuk menganalisa karakteristik dari fungsi Lagrange.
1.4 Metodologi Penelitian Metode penelitian yang digunakan adalah dengan menggunakan metode studi literatur yang bersifat penjelasan dan uraian. Dalam penelitian ini diuraikan tentang analisis karateristik dari fungsi Lagrange yang dinyatakan dalam bentuk Relaksasi Lagrange untuk menyelesaikan persoalan penentuan titik pusat analitik dari suatu polytope.
1.5 Kontribusi Penelitian Sebagai bahan kajian analisis dalam mengembangan metode penyelesaian persoalan optimisasi berkendala. Seperti yang telah diuraikan sebelumnya, bahwa fungsi Lagrange melalui metode relaksasi Lagrange perlu dipergunakan dalam
4 persoalan optimisasi berkendala sehingga memudahkan penyelesaian persoalan. Begitupun perlu dianalisis karakteristik dari fungsi Lagrange ini agar apa yang disebut memudahkan persoalan dapat tercapai.
BAB 2 KAJIAN PUSTAKA FUNGSI LAGRANGE
Dalam bagian ini dikaji secara singkat tentang fungsi Lagrange yang dipergunakan dalam penyelesaian persoalaan optimisasi berkendala. Crema et al. (2007) mengajukan pendekatan dual Lagrange untuk menyelesaikan program integer. Program integer yang mereka bahas ditulis dalam bentuk (P ): maksimal cT x dengan kendala Ax ≤ b Dx ≤ e x ∈ Zn , x ≥ 0 dimana Z menyajikan bilangan integer c, b, dan e vector. A dan D matriks dengan dimensi bersesuaian. Relaksasi Lagrange dari P dengan memperhatikan kendala sulit Ax ≤ b dapat ditulis sebagai P λ: maksimum cT x + λT (b − Ax) dengan kendala x ∈ X dimana X = {x ∈ Zn , x ≥ 0; Dx ≤ e}, λ ≥ 0, c dan λ adalah vector dengan dimensi bersesuaian. Formulasi dual Lagrange dari P dengan masalah (D) dinyatakan dengan minimum Z(λ) kendala λ ≥ 0 dimana Z(λ) = maksimum {cT x + λT (b − Ax), x ∈ X} 5
6 Walaupun demikian, karakteristik dari fungsi Lagrange yang dihasilkan merupakan fungsi yang non-diferensiabel. Metode subgradien dapat dipergunakan untuk menyelesaikan metode Lagrange yang diperoleh. Pendekatan relaksasi Lagrange terhadap kendala yang menyulitkan juga diajukan oleh Eliiyi and Melih (2008). Pendekatan ini dipergunakan untuk menyelesaikan masalah proses aliran produksi yang dimodelkan sebagai program integer 0 − 1. Karakteristik dari model optimisasi fungsi Lagrange merupakan fungsi konveks. Dalam hal ini terdapat bentuk model optimisasi linier dengan kendala hanya mencakup batas bawah dan batas atas, sehingga metode simpleks dapat menyelesaikan model relaksasi Legrange tersebut. Harris (2007) menyatakan Lagrange adalah suatu metoda untuk menentukan nilai optimum (maksimum dan minimum) suatu kurva. Untuk menemukan optimisasi beberapa fungsi f = (x, y), dimana variabel x dan y tidak bebas. Sebagai gantinya diberikan variabel g(x, y) = 0 sebagai batasan. max z = f (x, y) dengan g(x, y) = 0 x,y
Cara umum untuk memecahkan masalah ini adalah dengan mengasumsikan satu variabel bebas dan lainnya terikat. Jika memilih x sebagai variabel bebas, maka selanjutnya menghitung
dy dx
dari batasan fungsi:
∂g ∂x
+
∂g ∂y ∂y ∂x
∂y ∂x
=−
∂z ∂x
=
=0
∂g/ ∂x ∂g/ ∂y
∂f ∂x
+
∂f ∂y
=0
7
dz dx
=
∂f ∂x
−
∂f ∂y
∂g/ ∂x = 0 ∂g/ ∂y
F (x, y, λ) = f (x, y) + λ g (x, y)
∂F ∂x
=
∂f ∂x
+ λ ∂g =0 ∂y
∂F ∂x
=
∂f ∂y
+ λ ∂g =0 ∂y
∂F ∂λ
= g (x, y) = 0
Francesc (2005) mengemukakan suatu optimasi dibatasi oleh permasalahan dengan format berikut: max f (x1, x2, . . . , xn )
x1 ,...,xn
g1 (x1, x2 , . . . , xn ) = 0 g2 (x1, x2, . . . , xn ) = 0 ··· gm (x1 , x2, . . . , xn ) = 0 Variabel kendali dalam masalah ini, sebelum ke dalam Lagrange adalah (x1 , x2, . . . , xn ), dan m penghambat, g1 (x1 , x2, . . . , xn ) = 0 sampai gm (x1, x2 , . . . , xn ) = 0, adalah mungkin suatu variabel pengendali dari fungsi n. Dalam memecahkan masalah ini, ditulis fungsi Lagrange, L adalah suatu modifikasi sasaran yang menyertakan batasan. L(x1 , x2, . . . , xn , λ1 , λ2 , . . . , λm ) =f (x1, x2 , . . . , xn ) − λ1 g1 (x1 , x2, . . . , xn ) − λ2 g2 (x1, x2, . . . , xn ) − · · · − λm gm (x1, x2 , . . . , xn ) Variabel λj dikenal sebagai Lagrange multipliers, selanjutnya variabel tersebut sebagai variabel pelengkap untuk memecahkan masalah. Tidak diketahui nilai dari Lagrange multipliers. Dapat ditunjukkan gi (x1, x2 , . . . , xn ) = 0 untuk i =
8 1, . . . , m. Persamaan λm gm (x1, x2 , . . . , xn ) dalam L(x1, x2 , . . . , xn , λ1 , λ2 , . . . , λm ) = f (x1 , x2, . . . , xn )−λ1 g1 (x1, x2 , . . . , xn )−λ2 g2 (x1, x2 , . . . , xn )−· · ·−λm gm (x1, x2 , . . . , xn ) akan hilang untuk nilai λi . Kemudian L akan serupa dengan f . Cara yang dapat digunakan adalah menambahkan Lagrange multipliers ke dalam variabel kendali dan memaksimalkan nilai Lagrange. Kondisi pertama yang memerlukan bahwa masing-masing derivatif Lagrange adalah nol dengan solusi: δL δx1
=
δL δx2
=
δL δxn
=
δL(x∗1 ,x∗2 ,...,x∗m ) δL(
δx1 x∗1 ,x∗2 ,...,x∗m
)
∂x2
δL(
x∗1 ,x∗2 ,...,x∗m ∂xn
)
− λ∗1
δgm (x∗1 ,x∗2 ,...,x∗m )
∂x1 ∗ ,x∗ ,...,x∗ δg x m m 1 2 ∗
− λ1
(
)
∂x2
(
− · · · − λ∗m − · · · − λ∗m
δgm (x∗1 ,x∗2 ,...,x∗m ) ∂x1 δgm x∗1 ,x∗2 ,...,x∗m
(
∂x2
)
=0 =0
··· δgm (x∗1 ,x∗2 ,...,x∗m ) ) − · · · − λ∗m =0 ∂xn
∗ ∗ ∗ ∗ δgm x1 ,x2 ,...,xm
− λ1
∂xn
δL δλ1
= g1 (x∗1 , x∗2, ...., x∗n) = 0
δL δλ2
= g2 (x∗1 , x∗2, ...., x∗n) = 0 .........
δL δλm
= gm (x∗1, x∗2 , ...., x∗n) = 0
Persamaan m + n tidak diketahui, akan diselesaikansistem persamaan tersebut untuk (x∗1, x∗2, . . . , x∗n , λ∗1 , λ∗2 , . . . , λ∗m ) Contoh: Terdapat masalah max x1 x2 x1 ,x2
dengan kendala x21 + x22 = 2 Lagrange untuk masalah ini adalah L(x1 , x2, λ) = x1x2 − λ(x21 + x22 − 2)
9 Dimana f (x) = x1x2 dan g(x) = x21 + x22 − 2. Pengambilan pertama derivatif untuk Lagrange dengan x1 , x2 dan λ: x∗2 − λ∗ (2x∗1 ) = 0 x∗2 − λ∗ (2x∗2 ) = 0 (x∗1 )2 + (x∗2 )2 − 2 = 0 Didapat x∗2 λ∗ (2x∗1 ) = ∗ x∗1 λ (2x∗2 ) yang mengisyaratkan x∗1 = x∗2 atau x∗1 = −x∗2 dengan mensubsitusi didapat 2(x∗1 )2 = 2 atau x∗1 = ±1 Oleh karena itu ada 4 calon solusi untuk masalah tersebut, yaitu: (1, 1), (−1, −1), (1, −1), (−1, 1). Dengan menggantikan nilai fungsi sasaran f (x1 , x2) = x1 x2,
BAB 3 LANDASAN TEORI
3.1 Definisi Guignard (2008) menyatakan jika (P ) adalah masalah optimisasi, dapat digunakan notasi berikut: Dengan menggunakan suatu masalah optimisasi (P )
max{f(x)|x ∈ X}
dan masalah (RP )
max{g(x)|y ∈ Y }
(RP ) adalah relaksasi dari (P ) jika:
(i) Y ⊃ X, dan (ii) ∀ x ∈ X, g(x) ≥ f(x)
sehingga v(RP ) ≥ v(P ) dengan v(P ) adalah nilai optimal dari (P ) dan v(RP ) adalah nilai optimal relaksasi dari (P ).
10
11 3.2 Relaksasi Lagrange Untuk Masalah Bilangan Bulat Linier Dengan menggunakan suatu masalah optimisasi max{f x|Ax ≤ b, Cx ≤ d, x ∈ X}
(P )
x
Masalah ini dapat diselesaikan menggunakan Relaksasi Lagrange dari (P ) dengan cara berikut. Misalkan λ ≥ 0, dan misalkan (LRλ ) sehingga didapat: (LRλ ) :
max{f x + λ(b − Ax)|Cx ≤ d, x ∈ X} x
(LRλ ) adalah relaksasi dari (P ), karena kemungkinan penyelesaian (KP ):
(i) KP (LRλ ) ⊃ KP (P ) (ii) ∀x ∈ KP (P ), fx + λ(b − Ax) ≥ f x
Oleh karena itu v(LRλ) ≥ v(P ) , untuk setiap λ ≥ 0. Dapat dikatakan Lagrange adalah solusi optimal dari (LRλ )
3.3 Penafsiran Geometris Wu and Ierapetriou (2006) menyataka Relaksasi Lagrange (LR) sama dengan Relaksasi Primal (P R) (P R)
max{f x|Ax ≤ b, x ∈ Co{x ∈ X|Cx ≤ d}} x
v(LR) = v(P R)
12 Bukti: v(LR) = min v(LRλ) λ≥0
= min max{f x + λ(b − Ax)|Cx ≤ d, x ∈ X} λ≥0
x
= min max{f x + λ(b − Ax)|x ∈ Co{x ∈ X|Cx ≤ d}} λ≥0
x
= max{fx|Ax ≤ b, x ∈ Co{x ∈ X|Cx ≤ d}} x
= v(P R)
Gambar 3.1 : Penafsiran Geometri dari Relaksasi Lagrange Jika Co {x ∈ X|Cx ≤ d} = {x|Cx ≤ d}, maka v(P ) ≤ v(P R) = v(LR) = v(LR) Jika Co {x ∈ X|Cx ∈ d} ⊂ {x|Cx ≤ d}, maka v(P ) ≤ v(P R) = v(LR) ≤ v(LR)
13 3.4 Fungsi Lagrange dan Kondisi Optimal Van and Saglam (2004) menyatakan yang menjadi masalah dalam kondisi optimal adalah:
Program Non Linier (PNL)
min f (x) x
subjek dari
gi (x) = 0, i ∈ E gi (x) ≥ 0, i ∈ I
dimana f : Rn → R, fungsi objektif, dan gi : Rn → R, fungsi pembatas, secara terus menerus dan terbatas. Antara pembatas E dan I dimungkinkan tidak ada, dan bila kedua pembatas E dan I tidak ada maka PNL adalah pemasalahan optimisasi yang tidak terbatas. Dari semua poin dapat dinyatakan oleh: R = {x|gi (x) = 0, i ∈ E dan gi (x) ≥), i ∈ I} dan disebut daerah kemungkinan Suatu titik x0 yang memenuhi semua batasan disebut titik kemungkinan dan suatu titik kemungkinan x∗ disebut daerah terkecil, jika dan hanya jika: f (x∗ ) ≤ f (x), ∀x ∈ N(x∗ ) ∩ R dimana N(x∗ ) adalah neighbourhood dari x∗. Titik x∗ disebut global terkecil, jika dan hanya jika: f (x∗ ) ≤ f (x), ∀x ∈ R Penemuan masalah dalam global minimum sangat sulit dan diharapkan PNL adalah suatu pemecahan masalah. Kumpulan index i ∈ I ∪ E merupakan batasan persamaan dari suatu titik kemungkinan x0 disebut kumpulan aktif dan dinotasikan dengan X 0 = {i|i ∈ E ∪ I dan gi (x0 ) = 0}
14 dengan E ⊂ A untuk titik semua titik yang mungkin. Fungsi Lagrange dapat digunakan untuk memperoleh titik kemungkinan untuk PNL, sama dengan menentukan titik kondisi dalam optimisasi tidak terbatas (∇f = 0). Dalam melakukan optimalisasi bahwa penting disadari hanya batasan yang aktif pada mereka, karena untuk setiap batasan non aktif terdapat suatu neighbourhood N (x∗) seperti pada gi (x) > 0 ∀x ∈ N (x∗ ). Misalkan x∗ adalah suatu lokal minimum dan misalkan A∗ adalah set aktif. Dengan pengambangan Taylor dari gi disekitar x∗, dimana δ adalah suatu langkah tambahan, diberikan: Gi (x∗ + δ) = gi∗ + δ T a∗i + o(kδk) = 0 + δ T a∗i + o(kδk) ∀i ∈ A∗ dimana a∗i = ∇gi∗. Karena gi (x∗ + δ) = 0 untuk i ∈ E dan positif untuk i ∈ A ∩ I, itu perlu untuk δ berada sepanjang garis s memenuhi sT
a∗i ≥ 0
∀i ∈ A∗ ∩ I
sT
a∗i = 0
∀i ∈ E
Setiap s yang memenuhi kondisi tersebut disebut arah yang mungkin. Jika diperoleh suatu asumsi, ditemukan suatu langkah tambahan δ sepanjang arah yang mungkin s, kemudian Lemma berikut menyatakan optimalisasi untuk kondisi daerah terkecil
Lemma 1 Misalkan F ∗ := { s| s T a∗i = 0, ∀i ∈ E sT
a∗i ≥ 0, ∀i ∈ A∗ ∩ I
sT
∇f ∗ < 0 }
15 Kemudian f ∗ = ∅ jika dan hanya jika terdapat fungsi Lagrange λ∗i , i ∈ A∗ seperti pada
P
∇f ∗ =
i∈A∗
λ∗i ∇gi∗
λ∗i ≥ 0, ∀i ∈ A∗ ∩ I Suatu kondisi yang mengisyaratkan keteraturan asumsi disebut suatu batas ketidakpastian. Suatu batas ketidakpastian sederhana adalah bahwa semua {a∗i , i ∈ A∗ } berdiri sendiri secara linier. Lemma di atas memberikan suatu kondisi, yang mengisyaratkan bahwa tidak ada arah turunan yang mungkin, jika dan hanya jika gradien dari fungsi objek adalah suatu kombinasi linier dari gradien pembatas dimana bobot diberikan oleh masing-masing fungsi Lagrange . Sebelum menyatakan optimalisasi dari PNL, fungsi Lagrange merupakan suatu kombinasi linier yang dihargai sebagai fungsi sasaran dan fungsi pembatas, digambarkan sebagai (x, λ) = f (x) −
X
λi gi (x) −
i∈I
X
λi gi (x)
i∈E
Teorema 1 Misalkan x∗ adalah daerah terkecil dari PNL dan jika diperoleh suatu asumsi pada x∗ , kemudian terdapat fungsi Lagrange λ∗ seperti pada: X
λ∗i ∇ gi∗ = 0
(3.1)
i∈A∗ gi∗ =
0, ∀i ∈ E
(3.2)
gi∗ ≥ 0, ∀i ∈ I
(3.3)
λ∗i ≥ 0, ∀i ∈ I
(3.4)
λ∗i gi∗ = 0, ∀i
(3.5)
∇f ∗ −
16 Kondisi (3.1) sering dikenal sebagai kondisi pertama, (3.2) dan (3.3) adalah kelayakan terpenting (3.4) adalah kelayakan rangkap dan (3.5) sebagai kondisi pelengkap. Fumero (2001) menyatakan Fungsi Lagrange tidak hanya berperan penting dalam kondisi optimalisasi, tetapi juga memberi tingkat perubahan solusi, jika batasan gi tidak jelas. Ini sering dimanfaatkan dalam optimalisasi atau analisis kepekaan.Jika ci (x) = 0, ci (x) = i , kemudian x = x(), adalah penyelesaian dari masalah, selanjutnya bahwa f (x()) = £(x(, λ(), ) dan menggunakan aturan rantai dapat menaksir perubahan dalam f dengan gangguan kecil dalam batasan sebagai d£ ∂xT ∂λT ∂£ df = = ∇x £ + ∇λ £ + = λi dεi dεi ∂εi ∂εi ∂εi Karena optimalisasi dari x mengisyaratkan bahwa ∇x£ = 0 dan ∇λ£ = 0.
3.5 Titik Pusat Analitik Masalah penentuan titik pusat analitik dari suatu polytope menjadi dasar utama pada algoritma titik interior dari program linier (Todd, 1989). Untuk maksimum polytope P didefinisikan oleh aTi x = αi (i = 1, 2, 3, . . . , l) dan bTj x ≤ βi (j = 1, 2, 3, . . . , m) Titik pusat analisis x adalah maksimum dari m X j=1
log (βi − bTj x)
17 dengan kendala aTi x = αi (i = 1, 2, 3, . . . , l) dan bTj x ≤ βi(j = 1, 2, 3, . . . , m) dimana ai ∈ Rn , αi ∈ R, bj ∈ Rn dan βj ∈ R.
BAB 4 KARAKTERISTIK FUNGSI LAGRANGE PADA PENENTUAN TITIK PUSAT ANALITIK POLYTOPE
Dalam bagian ini dianalisis karakteristik dari fungsi Lagrange yang dinyatakan dalam bentuk relaksasi Lagrange untuk menyelesaikan persoalan penentuan titik pusat analitik dari suatu polytope.
4.1 Analisis Karakteristik Andaikan A ∈ Rm×n , b ∈ Rn dan e = (1, . . . , 1)T ∈ Rn Pandang polytope berbentuk P+ = {x ∈ Rn : Ax = b, eT x = 1, x ≥ 0} Setiap daerah terbatas tak kosong dapat ditransformasikan menjadi bentuk deret himpunan. Diandaikan P+ memenuhi kondisi berikut:
i) P++ ≡ {x ∈ P+ A ii) Baris dari eT
: x > 0} tak kosong
∈ R (m+1) × n bebas linier
Pusat analitik dari P+ didefinisikan sebagai maksimum dari
m P
log xj dalam P++ .
j=1
Didifenisikan: S+ = {x ∈ xn : eT x = 1, x ≥ 0} S++ = {x ∈ S+ : x > 0} g(x, y) = y T (Ax − b) +
n X
(4.1)
log xj , ((x, y) ∈ S++ × R n )
j=1
18
19 Disini y ∈ Rn merupakan fungsi Lagrange yang dikaitkan dengan Ax = b. Fungsi δ merupakan fungsi Lagrange vector x ¯ merupakan pusat analitik dari P+ jika dan hanya jika terdapat suatu y¯ ∈ Rn sehingga kondisi titik sadel G(x, y¯) ≤ g(¯ x, y¯) ≤ (¯ x, y)∀ y ∈ Rn dan x ∈ S++
(4.2)
definisikan: φ(y) = maksimum {g(x, y) : x ∈ S++ } f(y) = maksimum {g(x, y) : x ∈ S++ } maka F (y) = g(φ(y), y) = y T (A 6⊂ (y) − b) +
m X
log φi (y) ∀ j ∈ Rn
j=1
(4.3)
F (¯ y) = g(¯ x, y¯) ≤ g(x, y) ≤ f(y), ∀ j ∈ Rm dan x ¯ = φ(¯ y) Fungsi f memiliki karakteristik yang diberikan dalam teorema berikut:
Teorema 2
i) f merupakan C ∞
ii) ∇f(y) = Aφ(y) − b
iii) Jika x = φ(y) dan X = diagonal x (yaitu X matriks diagonal dengan kom XxT 2 ponen x dalam diagonalnya), maka ∇ f (y) = AX I − X T x AT iv) ∇2 f(y) definit positif pada setiap y ∈ Rm . Jadi f benar-benar konveler.
Bukti:
i) Perhatikan bahwa x = φ(y), maksimum tunggal dari g(·, y) dalam x ∈ S++ memenuhi syarat stasioner F (φ(y), φ(y), y) = 0 dan φ(y) > 0. Matriks
20 Jakobi DF (x, n, y) dari f terhadap (x, n) adalah −2 e −x DF (x, n, y) = 0 eT yang non-singular untuk x ∈ Rn++ . Jadi, oleh teorema fungsi implisit φ adalah C ∞, dan g adalah C ∞, akibatnya f adalah C ∞ . ii) Differensialkan persamaan ke dalam (3) terhadap y diperoleh ∂f (y) ∂yi
=
n P
=
j=1 n P j=1
∂g(φ(y)y) ∂xj (y) ∂xj ∂yi
+
∂g(φ(y)y) ∂xj (y) ∂xj ∂yi
+ Ai(φ(y)) − bi
∂g(φ(y)y) ∂yi
dimana Ai baris ke i dari A. Sebaliknya dilihat dari syarat stasioner bahwa ∂g( φ(y)y) + φ (y) = 0 j = ( 1, 2, ......, n ) ∂xi ∀y ∈ Rm T ∂φ(y) i = (1, 2, ........., s) e ∂yi
Karena itu ∂f (y) ∂yi
= −φ (y)
n P i=1
∂φi (y) ∂yi
+ Aiφ (y) = bi
= Aiφ (y) − bi iii) Differensialkan persamaan ke dalam syarat stasioner terhadap − 2 ∂φ(y) + ∂φ(y) e + ATi ∂F (φ (y) , φ (y) y) − (φ (y)) ∂yi ∂yi = ∂yi eT ∂φ(y) ∂yi
yi
=0
disini φ(y) = diagonal (φ(y)). Selesaikan persamaan linier untuk ∂φ(y) , ∂yi
∂φ(y) ∂yi
dan
terdapat T
φ (y) ∂φ (y) = φ (y) ATi T ∂yi φ (y) φ (y)
φ(y)T φ(y)T φ(y)
∂φ(y) ∂yi
=
∂φ(y) ∂yi
= φ (y)
φ (y) ATi
I−
φ(y)φ(y)T φ(y)T φ(y)
φ (y) ATi
i = (1, 2, . . . , m)
21 Sebaliknya, lihat dari ii) bahwa ∂f (φ (y)) = Aφ (y) − bi ∂yi
( i = 1, 2, . . . , m )
Jadi, untuk setiap i(i = 1, 2, . . . , m) dan k(k = 1, 2, . . . , m) ∂ 2 f (φ(y)) ∂yi ∂yk
= Ai ∂φ(y) ∂yk = Ai φ (y)
I−
∂φ(y)∂φ(y)T ∂φ(y)T ∂φ(y)
φ (y) ATk
Ini mengakibatkan ii) iv) Andaikan y ∈ Rn dan x = φ(y). Jelas, ∇2f (y) simetri dan positif semi definit. Cukup diperlihatkan bahwa tidak terdapat 0 6= v ∈ Rm untuk xT X AT v XxT T T XA v=X A v− e 0= I− T X x XT x Sebaliknya, andaikan v demikian ada. Karena X = diagonal (x) AT v = e
xT X AT v xT X
=0 Kontradiksi dengan kondisi ii)
Sekarang diperlihatkan bagaimana menentukan φ(y) untuk setiap (x, n, y) ∈ n × R 1 + m , definisikan R++
∇x g (x, y) + ne F (x, n, y) = eT x − 1 −1 T x e + A j + ne = eT x − 1
(4.4)
Maka maksimum φ(y) dari g(·, y) kalau S++ dikarakterisasi dalam syarat stasioner F (φ(y), φ(y), y) = 0 dan φ(y) > 0
(4.5)
22 Dimana φ(y) menyatakan fungsi Lagrange yang dikaitkan dengan eT x = 1. Bentuk ini direduksi menjadi:
n X j=1
1 dj (y) − φy
(j = 1, 2, . . . , n)
(4.6)
1 = 1 dan dj (y) − φ(y) > 0 (j = 1, 2, . . . , n) dj (y) − φ (y)
(4.7)
φj (y) =
Dimana d(y) = −AT y. Penyelesaian φ(y) dari persamaan (4.7) terletak dalam selang [dmin (y) − n, dmin (y) − 1], dimana dmin (y) = min{dj (y) : j = 1, 2, . . . , n}, dan dapat ditentukan dengan pencarian biner pada [dmin (y) − n, dmin (y) − 1]. Karena itu , diketahui y ∈ Rm , mudah untuk menentukan φ(y).
4.2 Karakteristik Fungsi Lagrange Dari masalah max{f x|Ax ≤ b, Cx ≤ d, x ∈ X}
(P )
x
Suatu konsep Relaksasi Lagrange (LRλ ) max{f x + λ(b − Ax)|Cx ≤ d, x ∈ X} x
(diasumsikan mempunyai penyelesaian) dan sesuai dengan Lagrange dual (LR)
min v(LRλ) λ≥0
Fungsi Lagrange adalah z(λ) = v(LRλ )
23 Fungsi implikasi dari λ Misalkan {x ∈ X|Cx ≤ d} = {x1, x2, . . . , xk ), maka
(LRλ ) max{fx + λ(b − Ax)|Cx ≤ d, x ∈ X} = max {f xk + λ(b − Axk )} x
k=1,...,k
(LR) min v(LRλ) = min z(λ) λ≥0
λ≥0
= min max {f xk + λ(b − Axk )} λ≥0 k=1,...,k
= min {ν|ν ≥ f xk + λ(b − Axk ), k = 1, . . . , k} λ≥0,ν
V (LR) adalah nilai minimum dari sebuah perpotongan garis lengkung, secara mutlak. Fungsi z(λ) mempunyai titik potong yang tidak berbeda. Tingkatannya ditentukan oleh C(α) = {λ ≥ 0|z(λ) ≤ α}, α adalah skalar, dan tingkat kelengkungannya. Yang perlu dilihat dalam menentukan titik terkecilnya adalah α yang mengandung C(α). Misal λ∗ merupakan bagian terkecil dari z(λ), dan misal ν ∗ = z(λ∗ ).
Gambar 4.1 : Fungsi Lagrange
24 Misal λk merupakan taksiran pada λ∗ dan misal νk = z(λk ). Misal Hk = {λ|fxk + λ(b − Axk ) = ν k } menjadi sebuah tingkatan yang melewati λk . H k menetapkan bagian dari batas C(ν k ). Jika z(λ) merupakan turunan dari λk , ia merupakan gradien dari ∇z(λk ) pada λk : ∇z(λk ) = (b − Axk )⊥Hk Jika z(λ) bukan merupakan turunan dari λk , ia merupakan sub gradien dari sk pada λk : sk = (b − Axk )⊥Hk
Gambar 4.2 : Contur Fungsi Lagrange
25 Dengan kata lain metode relaksasi Lagrange mentransformasikan persoalan penentuan titik analitik menjadi minimisasi tanpa kendala f pada Rn , sehingga x ¯ merupakan pusat analitik jika dan hanya jika y¯ minimum dari f dan x ¯ = φ(¯ y) maksimum dari g(x, y) dalam S++ .
BAB 5 KESIMPULAN
Relaksasi Lagrange adalah alat yang sangat baik untuk pemecahan masalah perkiraan bilangan bulat, dalam menetapkan:
a. Batas yang kuat dari fungsi Lagrange ketika permasalahan tersebut tidak memiliki integral. b. Langkah awal yang baik untuk pencarian heuristik.
Fungsi f memiliki karakeristik:
a. f merupakan C ∞ b. ∇ f(y) = Aφ(y) − b c. Jika x = φ(y) dan X = diagonal x
Metode Relaksasi Lagrange mentranformasi persoalan penentuan titik analitik menjadi minimisasi tanpa kendala f kepada Rn .
26
DAFTAR PUSTAKA
Crema A, M. Loreto, and M. Reydan. 2007. Spectral Projected Subgradiend With A Momentum Term For The Lagrangean Dual Approach. Computers and Operations Research. vol. 34. pp. 3174 3186. Eliiyi D. T. and Melih . 2008. A Lagrange Relaxation Approach for the MixedModel Flow Line Sequencing Problem. Computers and Operations Research. vol. 35. pp. 933 943. Francesc M. T. 2005, Notes on Optimization. Working Paper. Januari 12, 2005. Fumero F. 2001. A Modified Subgradient Algoritm For Lagrangean Relaxation. Computers and Operations Research. vol 28. pp. 33 52. Guignard M. 2008. Lagrange Relaxation. Working Paper. Februari 2008. The Wharton School. University of Pennsylvania, Philadelphia. Harris B. 2007. Langrange: A Well-Behaved Function, Journal of The Montana Mathematics Enthusiast. vol. 4. pp. 128 137. Kojiwa M, N. Megiddo, and S. Mizuno. 1992. A Lagrangian Relaxation Method For Approximation The Analytic Centre of A Polytope. Working Paper. Tokyo Institute of Technology. Luenberger D.G. 1984. Linear and Nonlinear Programming. California: Akdisa Wesley. Rong A, R. Lahdelana, and P. B. Luh. 2008. Lagrangian Relaxation Based Algorithm For Trigonometri Planning With Storages. European Journal of Operational Research. vol. 88. pp. 240 -257. Todd M. J. 1989. Recent Development and New Directions in Linear programming. In: N. Iri and K. Tanabe. Mathematical Programming, Recent Developments and Applications. Kluwa Ac. Pub. London. pp. 109 157. Ven C. L, and Saglam H. C. 2003. Optimal Growth Models and the Lagrange Multifiplier. Journal of Mathematical Economics. vol. 40. pp. 393 410 Wu D, Ierapetritou M. 2006. Lagrangean Decomposition Using an Improved Nelder Mead Approach for Lagrangean Multiplier Update. Computers and Chemical Engineering. vol. 30. pp. 778 789.
27
