METODE FUNGSI QUASI-FILLED SATU PARAMETER UNTUK MENYELESAIKAN MASALAH PROGRAM INTEGER TAK LINEAR Ria Hardiyati (M0101042) ABSTRAK Dalam kehidupan sehari-hari sering dijumpai masalah optimasi yang membutuhkan hasil integer. Masalah tersebut dapat diselesaikan dengan bentuk program integer. Tujuan dari penulisan skripsi ini adalah mengkaji langkah-langkah memperoleh minimum global dalam program integer tak linear dengan menggunakan metode fungsi quasi-filled satu parameter dan menerapkannya dalam menyelesaikan masalah program integer tak linear. Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur. Berdasarkan hasil pembahasan diperoleh bahwa penyelesaian masalah program integer tak linear menggunakan metode fungsi quasi-filled satu parameter terdiri dari dua fase yaitu fase minimisasi fungsi objektif dan fase minimisasi fungsi quasi-filled satu parameter. Proses penghitungan berhenti jika jumlah iterasi di fase kedua lebih besar dari nilai parameter toleransi, N L . Titik minimum lokal fase pertama pada iterasi terakhir merupakan titik minimum global. Pengambilan titik awal hanya mempengaruhi hasil titik minimum lokal tetapi tidak mempengaruhi hasil titik minimum global Kata kunci: program integer, minimum lokal, minimum global, fungsi quasi-filled satu parameter.
1. PENDAHULUAN Secara umum minimisasi masalah program integer tak linear berbentuk : min f x dengan kendala x X I
(1.1)
dengan X I I n adalah himpunan kotak terbatas dan tertutup yang berisi lebih dari satu n
n
titik; dengan I yang berupa himpunan titik integer dalam R . Definisi 1.1 (Zhu, 2000: 2) Untuk sebarang x I n , didefinisikan persekitaran dari x yaitu N ( x ) {x, x ei : i 1,2,..., n} dengan ei adalah vektor dimensi-n dengan semua komponen sama dengan nol kecuali komponen ke-i sama dengan satu. N 0 x N x \ x . Definisi 1.2 (Zhu, 2000: 2) Integer x 0 X I disebut minimum lokal dari fungsi (1.1) jika terdapat persekitaran N ( x 0 ) untuk sebarang x N ( x0 ) X I , berlaku f ( x) f ( x 0 ) . Integer x 0 X I disebut minimum global dari fungsi (1.1) jika untuk sebarang x X I , berlaku
f ( x) f ( x 0 ) .
Sebagai
tambahan,
jika
f(x)> f ( x0 )
untuk
setiap
0
x N ( x0 ) X I atau x X I \ {x0} , maka x0 disebut minimum lokal (global) tegas dari f. Teorema 1.1 (Zhang et al., 1999: 3) Jika x 0 X I adalah minimum global dari fungsi (1.1), maka x 0 X I pasti minimum lokal dari f. Berikut ini diberikan Algoritma 1.1 untuk mencari titik minimum lokal Algoritma 1.1 (Zhu, 2000: 3) Langkah 1 : Pilih sebarang titik integer x 0 X I . Langkah 2 : Jika x0 adalah minimum lokal dari f(x) maka STOP. Selain itu, didapatkan x N ( x0 ) X I dengan f ( x) f ( x 0 ) . Langkah 3 : Diambil x0 : x , kembali ke Langkah 2. 2. METODE PENELITIAN Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur. Langkahlangkah yang diperlukan untuk mencapai tujuan dalam skripsi ini adalah: 1. menjabarkan definisi fungsi quasi-filled dan fungsi quasi-filled satu parameter,
1
2. memberikan algoritma fungsi quasi-filled satu parameter secara umum , 3. menerapkan metode fungsi quasi-filled satu parameter dalam contoh kasus, 4. menganalisis pengambilan titik awal yang berbeda terhadap hasil akhir, seluruh perhitungan dalam contoh dilakukan menggunakan program Matlab. 3. PEMBAHASAN Dalam bab ini diberikan definisi fungsi quasi-filled, fungsi quasi-filled satu parameter dan algoritma umum metode fungsi quasi-filled satu parameter. 3.1 Fungsi Quasi-Filled dan Sifatnya Dalam subbab ini dikenalkan fungsi quasi-filled satu parameter di titik minimum lokal x1* dan membahas sifatnya. Titik x1* yang diperoleh dari Algoritma 1.1. Dibentuk
S1 {x X I : f ( x) f ( x1* )} X I S 2 {x X I : f ( x) f ( x1* )} X I . Definisi 3.1 Fungsi Px * ( x) disebut fungsi quasi-filled dari f(x) di minimum lokal x1* jika 1
Px * ( x) mempunyai sifat berikut : 1
(i) Px * ( x) tidak mempunyai minimum lokal dalam himpunan S1 \ {x0 } . Titik awal 1
x0 dalam S1 . (ii) Jika x1* bukan minimum global dari f(x) maka terdapat minimum lokal x1 dari
Px * ( x) , sedemikian hingga f ( x1 ) f ( x1* ) dengan x1 S 2 . 1
Definisi 3.1 didasarkan pada himpunan dalam ruang Euclid dan x0 tidak harus minimum lokal dari Px * ( x) . 1
3.2 Fungsi Quasi-Filled Satu Parameter Mirip dengan Zhu (2003), diberikan fungsi quasi-filled satu parameter dari fungsi objektif di titik minimum lokal x1* sebagai berikut :
PA, x* , x ( x ) ( x x 0 ) ( A (exp([min{ f ( x) f ( x1* ),0}] 2 ) 1)) , 1
(3.1)
0
dengan A>0 adalah parameter, titik awal x0 X I memenuhi f ( x0 ) f ( x1* ) . Untuk membentuk Px * ( x) yang memenuhi sifat seperti yang disebutkan pada Definisi 1
3.1, maka harus dipilih fungsi (t ) dan (t ) yang memenuhi kondisi berikut ini : (a) (t ) dan (t ) fungsi monoton naik tegas untuk setiap t 0, (b) (0) 0 dan (0) 0 (c) (t ) C B max ( x x0 ) , dengan x . x X I
Selanjutnya dibuktikan bahwa bentuk fungsi PA, x* , x ( x) memenuhi kondisi (i) dan (ii) 1
0
dari Definisi 3.1. Pertama diberikan Lema berikut ini, Lema 3.1 Untuk setiap bilangan bulat x X I , jika
x x0
maka terdapat
d D { ei : i 1,2,..., n} , sedemikian hingga x d x0 x x0 Bukti
(3.2)
Untuk x x0 , terdapat sebuah i {1,2,..., n} sedemikian hingga xi x0i . Jika
xi x0i maka d=-ei. Di sisi lain, jika xi x0i maka d=ei.
2
Teorema 3.1 PA, x* , x ( x) tidak mempunyai minimum lokal pada himpunan S1 \ {x0 } untuk 1
0
setiap A>0. Bukti Untuk setiap xS1 dan x x0 , dengan menggunakan Lema 3.1 diketahui bahwa terdapat dD, sedemikian hingga
x d x0 x x0 . Dipertimbangkan dua kasus berikut ini : (1) Jika f ( x1* ) f ( x d ) f ( x) atau f ( x1* ) f ( x) f ( x d ) maka
PA, x* , x ( x d ) ( x d x 0 ) ( A (exp([min{ f ( x d ) f ( x1* ),0}]2 ) 1)) 1
0
( x d x0 ) ( x x0 ) PA, x* , x ( x ) 1
0
Jadi, x bukan minimum lokal dari fungsi PA, x* , x ( x) . 1
0
* 1
(2) Jika f ( x d ) f ( x ) f ( x ) maka
PA, x* , x ( x d ) ( x d x 0 ) ( A (exp([min{ f ( x d ) f ( x1* ),0}]2 ) 1)) 1
0
( x d x0 ) ( A (exp([ f ( x d ) f ( x1* )]2 ) 1)
( x d x0 ) ( x x0 ) PA, x* , x ( x ) 1
0
Jadi, x bukan minimum lokal dari fungsi PA, x* , x ( x) . 1
0
Dua kasus di atas menunjukkan bahwa x bukan minimum lokal dari fungsi PA, x* , x ( x) . 1
0
Dari Teorema 3.1, diketahui bahwa bentuk fungsi PA, x* , x ( x) memenuhi kondisi 1
0
pertama dari Definisi 3.1 tanpa asumsi lebih lanjut terhadap parameter A. Selama X I S1 S 2 , Teorema 3.1 memberikan akibat berikut ini Akibat 3.2 Untuk sebarang minimum lokal dari fungsi PA, x* , x ( x) kecuali x0, pasti berada 1
0
dalam himpunan S2. Oleh karena itu, jika A=0 maka PA, x* , x ( x ) ( x x0 ) mempunyai minimum lokal 1
0
unik x0 di dalam X I . Karena berlaku f ( x0 ) f ( x1* ) dengan x0 S1 , berarti PA, x* , x ( x) 1
0
tidak mempunyai minimum lokal dalam himpunan S2 dan PA, x* , x ( x) bukan fungsi quasi1
* 1 .
filled dari f(x) di minimum lokal x
0
Kemudian muncul pertanyaan bagaimana syarat
parameter A agar minimum lokal berada dalam himpunan S 2 . Untuk menjawab pertanyaan tersebut diberikan teorema berikut. Teorema 3.3 PA, x* , x ( x) mempunyai minimum lokal dalam himpunan bilangan bulat S 2 1
0
jika S 2 dan A>0 memenuhi kondisi
A
1 B
exp f ( x * ) f ( x1* )
(3.3)
1 2
dengan x * adalah minimum global dari f(x). Bukti Karena S 2 dan x * adalah minimum global dari f(x) maka f ( x * ) f ( x1* ) dan
PA, x* , x ( x * ) ( x * x 0 ) ( A (exp([min{ f ( x * ) f ( x1* ),0}] 2 ) 1)) 1
0
1
x * x 0 A exp f x * f x1*
3
2
1
B A exp f x * f x1*
2
jika A>0 dan memenuhi persamaan (3.3), maka PA, x* , x x 0 . 1
Di sisi lain, untuk setiap y S1 berlaku
0
1
PA, x* , x y y x0 A exp min f y f x1* ,0 1
0
2
y x0 0 Sehingga minimum global dari PA, x* , x ( x) pasti berada dalam himpunan S 2 . Akibatnya, 1
0
PA, x* , x ( x) mempunyai minimum lokal dalam himpunan S 2 . 1
0
Dari Teorema 3.1 dan 3.3, jika parameter A cukup besar maka bentuk fungsi PA, x* , x ( x) 1
0
memenuhi sifat pada Definisi 3.1, dengan kata lain fungsi PA, x* , x ( x) adalah fungsi quasi1
0
tetapi belum diketahui nilai minimum * 1
filled. Dari Algoritma 1.1 dapat diketahui nilai f x
global dari f x , jadi sulit untuk menentukan batas bawah dari parameter A pada Teorema 3.3. Masalah minimisasi fungsi (1.1) dapat diselesaikan jika diperoleh x X I sedemikian
hingga memenuhi f x f x * , dengan f x*
adalah nilai minimum global dari
masalah PI dan adalah toleransi maksimal yang diberikan. Jadi, jika minimum lokal
terakhir x1* maka memenuhi f x1* f x* .
1 B . Untuk exp 2 1 setiap minimum lokal terakhir x1* dari f x yang memenuhi f x1* f x* , fungsi quasi-filled PA, x* , x ( x) mempunyai minimum lokal dalam himpunan S 2 , dengan x * adalah Teorema 3.4
Diberikan konstanta positif yang kecil dan A
1
0
minimum global dari f(x). Bukti Untuk expt 1 fungsi monoton naik tegas untuk sebarang t 0, dan
f x1* f x* , diperoleh
1 exp 1 ,
exp f x* f x1*
2
2
kemudian
1 B
1
exp f x* f x1*
2
1 B . exp 2 1
Jika
A
1 B , exp 2 1
maka
A
1 B
1
exp f x* f x1*
2
.
Karena parameter A memenuhi kondisi pada Teorema 3.3 maka fungsi quasi-filled PA, x* , x ( x) mempunyai minimum lokal dalam himpunan S 2 . 1
0
Teorema 3.4 memberikan batas bawah dari parameter A yang hanya bergantung pada toleransi maksimal yang diberikan, .
4
Titik awal x0 S I adalah minimum lokal dari PA, x* , x ( x) jika x0 adalah
Teorema 3.5
1
0
minimum lokal dari f x . Bukti Jika x0 S I adalah minimum lokal dari f x , maka terdapat persekitaran N x0
sedemikian hingga untuk setiap x N x0 X I berlaku f x f x0 f x1* , sehingga * 1
2
PA, x* , x ( x ) ( x x 0 ) ( A (exp([min{ f ( x) f ( x ),0}] ) 1)) 1
0
x x0 x0 x0 PA, x * , x x0 1
0
berlaku untuk setiap x N x0 X I . Jadi x0 S I adalah minimum lokal dari PA, x* , x ( x) . 1
0
Dibentuk masalah program integer tak linear bantuan yang berhubungan dengan masalah minimisasi fungsi (1.1) sebagai berikut (3.4) min P * ( x) , A , x1 , x 0
dengan x X I Dari uraian di atas diketahui bahwa untuk sembarang toleransi 0 yang diberikan,
1 B maka PA, x* , x ( x) adalah fungsi quasi-filled dari f x di titik 1 0 exp 2 1 minimum lokal terakhir x1* yang memenuhi f x1* f x* . Jadi jika digunakan suatu jika A
metode peminimuman lokal untuk menyelesaikan masalah minimisasi fungsi (3.4) dari sembarang titik awal pada X I , maka dengan sifat dari fungsi quasi-filled diperoleh bahwa barisan titik minimum konvergen ke titik awal x0 atau ke titik x X I sehingga
f x f x1* . Jika diperoleh titik minimum x maka titik x dipakai sebagai titik awal untuk meminimumkan kembali f x pada X I , sehingga diperoleh x X I yang memenuhi f x f x yang lebih baik dari x1* . 3.3 Algoritma Fungsi Quasi-Filled Satu Parameter Algoritma fungsi quasi-filled satu parameter diberikan sebagai berikut : Langkah 1: Diberikan sebuah konstanta N L 0 sebagai parameter toleransi untuk mengakhiri proses peminimuman dari masalah minimisasi fungsi (1.1) dan konstanta kecil 0 sebagai toleransi optimal yang diinginkan. Dipilih sembarang x10 X I . Langkah 2: Langkah 3:
Diawali dengan x10 X I dicari minimum lokal x1* dari f x dengan menggunakan Algoritma 1.1. Bentuk fungsi quasi-filled PA, x* , x ( x) seperti berikut : 1
0
PA, x* , x1 ( x) ( x x ) ( A (exp([min{ f ( x ) f ( x1* ),0}]2 ) 1)) , 1
1 0
0
A 0 dan memenuhi kondisi pertidaksamaan (3.3) atau B A . Diberikan N 0 . exp 2 1 Jika N N L , dilanjutkan ke Langkah 7. Ditentukan N N 1 . Dipilih sebuah titik awal yang berada di X I untuk mulai meminimumkan PA, x* , x ( x) pada X I , dengan menggunakan sembarang dengan
1
Langkah 4: Langkah 5:
1
0
metode peminimuman lokal. Diperoleh x1 , minimum lokal dari PA, x* , x ( x) . 1
5
0
Jika x1 x10 maka kembali ke Langkah 4. Selain itu dilanjutkan ke Langkah 6. Diawali dengan titik x1 dicari minimum f x pada X I . Kemudian diperoleh
Langkah 6:
minimum lokal x2* dari f x . Dimisalkan x1* x2* , lalu kembali ke Langkah 3. Langkah 7: STOP algoritma, hasil x1* dan f x1* adalah penyelesaian pendekatan dan nilai minimum global dari masalah minimisasi fungsi (1.1). 3.4 Penerapan Metode Fungsi Quasi-Filled Satu Parameter Berikut ini disajikan contoh kasus optimasi fungsi integer tak linier dan penerapan pendekatan fungsi quasi-filled dalam penyelesaiannya. Diberikan masalah program integer tak linear berikut (Shang dan Han, 2005)
2
2
min f x x1 1 x n 1 n
n 1
n i x
2 i
xi 1
2
(3.5)
i 1
xi 5 , i 1,2, , n
kendala
xi : integer Penyelesaian n Masalah (3.5) mempunyai 11 titik fisibel dan mempunyai beberapa titik minimum lokal. Untuk n=2 mempunyai 4 minimum lokal, n=3 mempunyai 6 titik minimum lokal, n=4 mempunyai 7 minimum lokal n=5 mempunyai 10 minimum lokal dan seterusnya. Dipilih t t dan t t , sehingga dapat dibentuk fungsi quasi-filled:
PA, x* , x1 ( x) x x10 A (exp([min{ f ( x ) f ( x1* ),0}]2 ) 1) 1
0
dan diberikan 0.05 , A
B 1 , B max x x0 1 10 n 1 dan 2 xX I exp 1
parameter toleransi N L 10 n . Untuk n=2 Diberikan 0.05 , A 6.0503 10 3 , B 10 2 1 dan N L 10 2 . Dan masalah (3.5) menjadi 2
2
min f x x1 1 x2 1 2 x12 x2
2
(3.6)
xi 5 , i=1,2.
kendala
xi : integer Dipilih titik awal yang fisibel x 4,3 . Proses 1 Fase 1. Pencarian titik minimum lokal f(x) diawali dengan x01 4,3 Dicari minimum lokal dari masalah (3.6) dengan menggunakan Algoritma 1.1. 1 0
4 5 3 4 4 3 3 3 4 2
4 3
Dibentuk persekitaran titik awal, N x01 , , , , . Untuk x01 , maka diperoleh
f x10 4 12 3 12 2 4 2 3
2
2
32 2 2 213 9 4 338 351
6
4 3
Dengan cara perhitungan yang sama, nilai fungsi untuk persekitaran x01 dapat dilihat pada Tabel 3.1.
4 3
Tabel 3.1 Nilai fungsi untuk titik persekitaran dari x01 x
f(x)
5 3
988
3 3
80
4 4 4 2
306 402
4 f x10 f x , x N x10 X I tidak dipenuhi maka x01 bukan titik 3 minimum lokal. Kemudian dipilih x N x10 X I , dengan f x f x10 . Dari Tabel 3.1
Karena
3 3
diperoleh x . Selanjutnya proses pencarian minimum lokal diulang sebanyak 2 iterasi sehingga
2 3
2 3
menghasilkan titik minimum lokal yaitu x1* . Dari x1* diperoleh f x1* 7 . Fase 2. Kemudian dibentuk fungsi quasi-filled berikut:
P
2 4 6.0503103 , , 3 3
x
4 2 x 6.0503 10 3 exp min f x 7,0 1 . 3
Dibentuk masalah program integer tak linear bantuan yaitu minimisasi
P
2 4 6.050310 , , 3 3 3
x
4 2 x 6.0503 10 3 exp min f x 7,0 1 3
kendala
(3.7)
xi 5 , i=1,2.
Diberikan N=0. Karena N < NL maka proses dilanjutkan dengan mencari titik minimum lokal
2 2
dari masalah (3.7). Diberikan N=1. Dipilih titik awal x01 p . Untuk mencari titik minimum lokal analog seperti pada fase 1. Diperoleh titik minimum lokal untuk P
2 4 6.0503103 , , 3 3
x
1 2
yaitu x1 dengan f x1 3 . Karena x1 x 10 maka
7
1 2
proses dilanjutkan dengan mengulangi proses 1 dengan mengambil titik x1 sebagai titik awal. Proses 2
1 2
Fase 1. Pencarian titik minimum lokal f(x) diawali dari titik x02 Untuk mencari titik minimum lokal analog seperti pada proses sebelumnya. Diperoleh titik
1 1
1 1
minimum lokal yaitu x2* . Dari x2* diperoleh f x2* 0 . Fase 2. Dimisalkan x1* x2* , kemudian dibentuk kembali fungsi quasi-filled baru yaitu
P
1 1 6.0503103 , , 1 2
x
1 2 x 6.0503 10 3 exp min f x 0,0 1 . Diberikan N=0. 2
Karena N 0 N L maka proses dilanjutkan dengan diberikan N 0 1 1 . Dicari titik
1 1
minimum lokalnya dan iperoleh titik minimum lokal x 2 dan f x 2 0 . Proses penghitungan diulang sampai diperoleh N= 10 2 1 sehingga dihasilkan
1 x *global dan f x *global 0 . Penghitungan berhenti pada N 10 2 1 , karena N N L . 1 Diperoleh x *global 1,1 dengan f x *global 0 . Jadi meskipun diambil titik awal berbeda dan untuk n berbeda tetap diperoleh hasil akhir yang sama yaitu x *global 1,1,1 ,1 dengan f x *global 0 .
3. KESIMPULAN Dari keseluruhan pembahasan dapat diperoleh kesimpulan sebagai berikut. 1. Metode fungsi quasi-filled satu parameter digunakan untuk mencari titik minimum global dari masalah program integer tak linear. Penyelesaian masalah program integer tak linear menggunakan metode fungsi quasi-filled satu parameter terdiri dari dua fase yaitu fase minimisasi fungsi objektif dan fase minimisasi fungsi quasi-filled satu parameter. Proses penghitungan berhenti jika jumlah iterasi di fase kedua lebih besar dari nilai parameter toleransinya, N L . Titik minimum lokal fase pertama pada iterasi terakhir merupakan titik minimum global. 2. Berdasarkan eksperimen dari contoh diperoleh kesimpulan bahwa pengambilan titik awal yang berbeda-beda pada Algoritma 2.1 mempengaruhi hasil titik minimum lokal tetapi tidak mempengaruhi hasil titik minimum global masalah semula. DAFTAR PUSTAKA Shang, Y. and Han, B. (2005). One-Parameter Quasi-Filled Function Algorithm for Nonlinear Integer Programming, J. Zhejiang Univ. SCI., Vol.6A(4), pp: 305-310. Zhang, L.S., Gao, F., Zhu, W. X. (1999). Nonlinear Integer Programming and Global Optimization, Journal of Computational Mathematics, pp: 179-190. Zhu, W.X. (2000). A Filled Function Method for Nonlinear Integer Programming, ACTA of Mathematicae Applicatae Sinica (in Chinese), pp: 481-487. Zhu, W.X. (2003). On the Globally Convexized Filled Function Method for Box Constrained Continuous Global Optimization, It Appeared in Optimization. http://www.optimization-online.org/DB-FILE/2004/03/846.pdf.
8
