PENGGUNAAN ALGORITMA NONLINEAR PROGRAMMING ?· pertidaksamaan nonlinear. (Bertsekas, 1999) Algoritma…

  • Published on
    10-Mar-2019

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

<p>1 </p> <p>PENGGUNAAN ALGORITMA NONLINEAR PROGRAMMING UNTUK MENGOPTIMALKAN PARAMETER DALAM METODE PEMULUSAN </p> <p>EKSPONENSIAL SATU PARAMETER </p> <p>Nama Mahasiswa : Eka Novi Nurhidayati </p> <p>NRP : 1208 100 040 </p> <p>Jurusan : Matematika </p> <p>Abstrak Ada beberapa parameter yang harus dievaluasi pada metode pemulusan eksponensial sehingga didapatkan parameter yang optimal yang memberikan ukuran kesalahan peramalan yang paling kecil. Untuk mendapatkan parameter yang optimal biasanya dicari dengan menggunakan metode coba dan salah (trial and error). Beberapa algoritma nonlinear programming dapat digunakan untuk menyelesaikan masalah optimasi tersebut. Dalam tugas akhir ini dicari parameter yang optimal dalam metode pemulusan eksponensial tunggal dengan menggunakan metode dichotomous search dan interpolasi kuadrat dengan bantuan software Matlab. Proses untuk mendapatkan nilai optimal dengan menggunakan metode dichotomous search membutuhkan 23 iterasi hingga didapatkan nilai optimal sebesar 0,2648 dan MAPE sebesar 11,8261%. Sedangkan dengan menggunakan metode interpolasi kuadrat membutuhkan empat iterasi dengan hasil yang optimal sebesar 0,2649 dan MAPE sebesar 11,8261%. Dapat dilihat dari hasil tersebut bahwa metode interpolasi kuadrat lebih efektif karena jumlah iterasi yang dibutuhkan lebih sedikit sehingga waktu yang dibutuhkan juga lebih efisien. </p> <p> Kata kunci : nonlinear programming, metode pemulusan eksponensial </p> <p> 1. Pendahuluan Menurut Makridakis (1989), peramalan (forecasting) merupakan kegiatan memprediksi nilai-nilai sebuah variabel berdasarkan nilai yang diketahui dari variabel tersebut atau variabel yang berhubungan. Salah satu metodenya adalah metode pemulusan eksponensial. Beberapa metode yang umum digunakan dalam pemulusan eksponensial, yaitu: metode pemulusan eksponensial satu parameter (metode pemulusan eksponensial tunggal, metode pemulusan eksponensial ganda satu parameter dari Brown dan metode pemulusan eksponensial tripel satu parameter dari Brown), metode pemulusan eksponensial dua parameter (metode pemulusan eksponensial tunggal: pendekatan adaptif dan metode pemulusan ganda dua parameter dari Holt) dan metode pemulusan eksponensial tripel (tiga parameter) dari Winter.. </p> <p>Ada beberapa parameter yang harus dievaluasi dalam tiap metode pemulusan eksponensial. Pendekatan untuk menentukan parameter yang optimal biasanya dilakukan secara coba dan salah (trial and error). Makridakis (1999) menyatakan bahwa </p> <p> algoritma nonlinear programming dapat </p> <p>menyelesaikan masalah optimasi parameter ini dengan baik. Metode yang digunakan dalam algoritma nonlinear programming pada pengerjaan tugas akhir ini adalah metode dichotomous search (pencarian dikotomis) dan metode interpolasi kuadrat. Studi kasus pada tugas akhir difokuskan untuk mendapatkan parameter yang optimal pada metode pemulusan eksponensial tunggal dengan menggunakan algoritma nonlinear programming. Untuk mengevaluasi nilai parameter peramalan, digunakan ukuran error peramalan, yaitu persentase error absolut rata-rata (mean absolute percentage error). Harga parameter peramalan yang terbaik adalah harga yang memberikan nilai error peramalan yang terkecil. 2. Metode Pemulusan Eksponensial Menurut Makridakis (1999), metode pemulusan eksponensial adalah metode yang menunjukkan penurunan secara eksponensial terhadap pembobotan pada observasi yang </p> <p>2 </p> <p>lebih tua. Metode pemulusan eksponensial yang digunakan dalam pengerjaan tugas akhir ini adalah metode pemulusan eksponensial tunggal. 2.1 Metode Pemulusan Eksponensial </p> <p>Tunggal Metode ini menggunakan sebuah parameter yang dibobotkan kepada data yang paling baru dan membobotkan nilai (1- ) kepada hasil peramalan periode sebelumnya (The Jin Ai, 1999) di mana harga terletak antara 0 dan 1. Persamaan umum yang digunakan dalam metode ini adalah: (1) dengan: : ramalan untuk periode waktu (t+1) : data pada periode waktu ke-t : ramalan untuk periode waktu ke-t Menurut (Makridakis, 1999), karena nilai tidak diketahui, maka nilai ini dapat didekati dengan menggunakan nilai observasi pertama dan kemudian dilanjutkan dengan menghitung pada persamaan (1). Kemungkinan lainnya adalah merata-ratakan empat atau lima nilai pertama dalam kelompok data dan menggunakannya sebagai ramalan pertama. 2.2 Ukuran Error Peramalan Ukuran error peramalan digunakan untuk mengevaluasi harga parameter peramalan. Harga parameter peramalan yang terbaik adalah harga yang memberikan nilai error peramalan yang terkecil. Dalam tugas akhir ini, ukuran error peramalan yang akan digunakan adalah persentase error absolut rata-rata (Mean Absolute Pecentage Error). Rumus umum yang digunakan adalah: </p> <p>MAPE = </p> <p>Suatu model mempunyai kinerja sangat baguss jika nilai MAPE berada di bawah 10%, dan mempunyai kinerja bagus jika nilai MAPE berada di antara 10% dan 20% (Zainun dan Majid, 2003). 3. Algoritma Nonlinear Programming </p> <p>Nonlinear programming dapat diaplikasikan pada suatu kasus dimana fungsi f(x) merupakan nonlinear atau nilai x ditentukan oleh persamaan atau pertidaksamaan nonlinear. (Bertsekas, 1999) </p> <p>Algoritma nonlinear programming yang digunakan pada tugas akhir ini adalah sebagai berikut: 3.1 Metode Dichotomous Search (Pencarian </p> <p>Dikotomis) </p> <p>Langkah-langkah pengerjaan pada metode dichotomous search (pencarian dikotomis) untuk meminimalkan nilai f(x) dalam selang [ ] adalah sebagai berikut (Sharma, 2006): 1. Titik dan dipilih sedemikian hingga, = (2) dan anggap bahwa, = (3) 2. Dengan menyelesaikan persamaan (2) dan (3) didapatkan, </p> <p>3. Setelah mendapatkan nilai dan , berlaku tiga kasus yaitu: a. Jika f , maka (x yang </p> <p>optimum) terdapat di antara dan . b. Jika f , maka . c. Jika f , maka . </p> <p>Proses untuk mencari nilai x yang optimal yang meminimalkan nilai f(x) merupakan suatu proses iterasi, di mana proses akan berhenti ketika selisih nilai dan sangat kecil. Saat selisihnya sangat kecil, maka didapatkan nilai x yang optimal sama dengan ( )/2. 3.2 Metode Interpolasi Kuadrat </p> <p> Dari persamaan umum fungsi kuadrat , dipilih tiga titik , , sehingga didapatkan: </p> <p> (4) </p> <p> (5) </p> <p> (6). Kemudian dengan menyelesaikan persamaan (4), (5) dan (6) diperoleh nilai a dan b sebagai berikut: a= </p> <p> (7) </p> <p> b= </p> <p> (8). </p> <p>Untuk mendapatkan nilai minimum dari persamaan umum fungsi kuadrat dapat diperoleh dengan menggunakan turunan pertama: </p> <p>3 </p> <p> Nilai x yang minimum disimbolkan dengan , maka . Langkah selanjutnya substitusikan persamaan (7) dan (8) ke , didapatkan: </p> <p> Sebuah titik pendekatan awal diberikan dan , dengan adalah panjang langkah. Telah disebutkan di awal bahwa tujuan algoritma ini adalah untuk meminimalkan fungsi f(x), maka titik ketiga dipilih berdasarkan syarat berikut: 1. , jika f( ) &lt; f( ) 2. , jika f( ) &gt; f( ). </p> <p>Proses untuk mencari nilai yang meminimalkan nilai f(x) merupakan suatu proses iterasi. Untuk mendapatkan keakuratan yang diinginkan, proses iterasi akan berhenti saat nilai yang berurutan selisihnya sangat kecil. 4. Metodologi Penelitian Obyek penelitian yang difokuskan pada tugas akhir ini adalah mendapatkan parameter yang optimal dalam metode pemulusan eksponensial tunggal dengan menggunakan algoritma nonlinear programming. Langkah pengerjaan yang dilakukan dalam tugas akhir ini adalah sebagai berikut: a. Studi Pendahuluan Menurut The Jin Ai (1999), evaluasi parameter peramalan dalam peramalan pemulusan eksponensial dengan satu parameter merupakan permasalahan nonlinear programming yang amat khusus. Fungsi obyektifnya adalah ukuran kesalahan peramalan, masalah yang dihadapi adalah minimasi. Variabel yang ada hanya satu yaitu parameter peramalan, kendala yang ada harga variabel terletak antara 0 dan 1. Secara umum evaluasi parameter peramalan dalam metode pemulusan eksponensial dapat dituliskan sebagai: </p> <p>Minimasi: y = f() Kendala: 0 1 dengan: y : ukuran error peramalan : parameter peramalan </p> <p> Untuk menghitung fungsi obyektif pada suatu harga variabel (y = f()) diperlukan </p> <p>langkah perhitungan yang panjang. Dari semua data pada periode waktu yang diketahui, nilai ramalan untuk masing-masing periode dihitung menggunakan kumpulan persamaan metode yang dikehendaki. Kemudian ukuran kesalahan peramalan dihitung berdasarkan pada periode waktu yang dapat diramalkan dan yang datanya ada. b. Mendapatkan Parameter yang Optimal </p> <p>Langkah-langkah yang dikerjakan untuk mendapatkan nilai parameter yang optimal adalah sebagai berikut: i. Mendapatkan data, di mana data yang </p> <p>digunakan pada pengerjaan tugas akhir ini berasal dari Tabel 3-10 buku Metode dan Aplikasi Peramalan (Makridakis, 1999). </p> <p>ii. Membuat program untuk metode dichotomous search dan interpolasi kuadrat dengan bantuan software matlab R2010a dan netbook Acer Aspire One Happy dengan CPU Intel Atom N550 serta memori 1GB DDR3. </p> <p>iii. Memasukkan data ke dalam program sehingga didapatkan output berupa nilai parameter yang optimal. </p> <p>c. Analisis Hasil Pada tahap ini dilakukan analisis hasil dari metode-metode dalam nonlinear programming yang dipakai, metode manakah yang paling efektif sehingga didapatkan parameter yang paling optimal. Keefektifan program dapat dilihat dari jumlah iterasi. d. Kesimpulan dan Saran. </p> <p>Pada tahap akhir pengerjaan ini dilakukan penarikan kesimpulan dari hasil pembahasan sebelumnya. Selanjutnya diberikan saran untuk perbaikan pada penelitian berikutnya. 5. Hasil Penelitian </p> <p>Data yang digunakan pada tugas akhir terdapat pada Tabel 1 yang berasal dari Tabel 3-10 buku Metode dan Aplikasi Peramalan (Makridakis, 1999). Data tersebut merupakan data ekspor kuartalan perusahaan Perancis tahun 1970 sampai 1975. </p> <p>4 </p> <p>Tabel 1. Tabel Data Penelitian </p> <p> Berikut ini adalah penjelasan singkat algoritma untuk mencari parameter optimal dan hasil running program yang telah dibuat dengan metode dichotomous search dan interpolasi kuadrat. 5.1 Metode Dichotomous Search </p> <p>Langkah pertama untuk mendapatkan parameter yang optimal adalah memasukkan nilai (delta) dan e. Nilai dan adalah interval di mana terdapat yang optimal. Nilai e nantinya akan menjadi pembatas berhentinya iterasi, di mana iterasi akan berhenti saat nilai </p> <p>kurang dari nilai e yang telah ditentukan. Sedangkan (delta) adalah selisih panjang antara dan . Kemudian didapatkan nilai </p> <p> dan </p> <p> yang akan </p> <p>dimasukkan ke dalam fungsi f . Variabel dan yang dimasukkan ke dalam fungsi sama dengan membandingkan dua parameter yang berbeda yang akan dimasukkan pada metode pemulusan eksponensial tunggal dan kemudian dihitung nilai ramalan dan MAPE dari masing-masing masukkan. </p> <p> Nilai MAPE merupakan nilai f pada metode ini. Kemudian langkah selanjutnya adalah membandingkan (hasil MAPE dari ) dan (hasil MAPE dari ). </p> <p>Hanya terdapat dua kasus dari hasil perbandingan tersebut, yaitu: 1. Jika kurang dari maka nilai </p> <p> akan menggantikan nilai pada iterasi selanjutnya. </p> <p>2. Jika lebih dari maka nilai akan menggantikan nilai pada iterasi selanjutnya, </p> <p>3. Jika sama dengan maka nilai akan menggantikan nilai dan nilai akan menggantikan nilai pada iterasi selanjutnya. </p> <p> Selanjutnya akan dilakukan pengujian perubahan nilai pada dan untuk mendapatkan nilai error (E). Jika (nilai yang baru) sama dengan (nilai yang lama) maka didapatkan nilai </p> <p> , jika nilai (nilai yang </p> <p>baru) sama dengan (nilai yang lama) maka nilai </p> <p> , dan jika </p> <p>sama dengan maka nilai . Tetapi jika tidak memenuhi ketiga pengujian tersebut maka nilai </p> <p> . </p> <p> Kemudian pada tiap iterasi akan diuji apakah nilai E kurang dari e. Jika nilai tersebut kurang dari e maka iterasi akan berhenti dan didapatkan nilai yang optimal sama dengan . Setelah itu didapatkan hasil peramalan dengan menggunakan nilai yang optimal. Tetapi jika belum memenuhi syarat berhentinya iterasi, maka langkah selanjutnya adalah kembali ke langkah pertama. Berdasarkan hasil running program yang telah dilakukan dengan menggunakan software Matlab R2010a, dapat dihitung jumlah iterasi hingga mendapatkan nilai optimal, didapatkan nilai MAPE dari optimal, serta hasil plot antara nilai pada matriks alpha dan MAPE pada Gambar 1 dan plot antara data penelitian dan hasil peramalan dengan optimal pada Gambar 2. </p> <p>Tahun Kuartal Periode Penjualan </p> <p>1970 </p> <p>1 1 362000 2 2 385000 3 3 432000 4 4 341000 </p> <p>1971 </p> <p>1 5 382000 2 6 409000 3 7 498000 4 8 387000 </p> <p>1972 </p> <p>1 9 473000 2 10 513000 3 11 582000 4 12 474000 </p> <p>1973 </p> <p>1 13 544000 2 14 582000 3 15 681000 4 16 557000 </p> <p>1974 </p> <p>1 17 628000 2 18 707000 3 19 773000 4 20 592000 </p> <p>1975 </p> <p>1 21 627000 2 22 725000 3 23 854000 4 24 661000 </p> <p>5 </p> <p> Gambar 1. Plot optimal dan MAPE </p> <p> Gambar 2. Plot Data Penelitian dan Hasil </p> <p>Peramalan dengan optimal </p> <p> Jumlah iterasi program dengan metode dichotomous search dapat dilihat pada Tabel 2. Tabel 2. Tabel Hasil Running Program dengan </p> <p>Metode Dichotomous Search Iterasi ke- alpha1 alpha2 error (%) </p> <p>1 0 0,5050 98,0198 2 0,2475 0,5050 104,0404 3 0,2475 0,3812 32,4590 4 0,2475 0,3194 19,3738 5 0,2475 0,2884 10,7259 6 0,2475 0,2730 5,6669 7 0,2552 0,2730 6,9483 8 0,2591 0,2730 5,3520 9 0,2591 0,2710 0,7134 10 0,2591 0,2701 0,3580 11 0,2590 0,2701 4,0385 12 0,2598 0,2701 3,9417 13 0,2598 0,2699 0,0448 14 0,2598 0,2699 0,0224 15 0,2598 0,2699 0,0112 16 0,2598 0,2698 0,0056 17 0,2598 0,2698 0,0028 18 0,2598 0,2698 3,8501 19 0,2598 0,2698 3,8494 20 0,2598 0,2698 3,8490 21 0,2598 0,2698 3,8488 22 0,2598 0,2698 3,8487 23 0,2598 0,2698 4,3737. </p> <p> Pada iterasi ke-23 nilai error kurang dari 0,001%, maka iterasi berhenti setelah iterasi </p> <p>ke-23 dengan nilai optimal adalah , dengan MAPE sama dengan 11,8261%. Jadi jumlah iterasi pada program dengan metode dichotomous search adalah 23. 5.2 Metode Interpolasi Kuadrat </p> <p> Langkah pertama adalah memasukkan nilai dan e (error). Nilai adalah titik pendekatan awal, adalah panjang langkah perhitungan dan nilai e akan menjadi pembatas berhentinya proses iterasi. Kemudian didapatkan nilai . Semua variabel pada fungsi harus terletak antara 0 dan 1, selanjutnya akan diuji nilai , ketika nilainya kurang dari 0 atau lebih dari 1 maka proses akan berhenti. Pengujian tersebut juga berlaku pada . </p> <p> Nilai pada metode ini merupakan hasil perhitungan MAPE, dengan masukka...</p>