Lexicographic Order: Metode Optimasi Multitujuan Januari 20, 2009

Beberapa saat yang lalu saya mendapat tugas kuliah tentang metode-metode penyelesaian masalah optimasi multitujuan. Betapa beruntungnya saya yang jatah tugasnya cukup simpel, paling simpel sekelas malah..  Jadi semangat. Makanya kemudian saya dengan pedenya memposting hasil karya saya di sini. Lumayan lah.. Kapan lagi saya bisa narsis seperti ini. Kesempatan langka..

Tapi karena saya gaptek, saya gak bisa menampilkan math equation di postingan saya ini. Tampak amburadul bukan? (bukan..) Untuk itu saya sertakan file aslinya. Silakan download bagi yang membutuhkan…

lexicographic-ordering

LEXICOGRAPHIC ORDERING

(Pengurutan Lexicographic)

Oleh: Siti Nurazhima Firmanti (05/186188/PA/10553)

I. Dasar Teori

Dalam matematika lexicographic order (LO), biasa juga disebut dengan alphabetic order atau dictionary order, ialah struktur urutan asli dari Cartesian product dua himpunan terurut.

Seandainya diberikan dua himpunan terurut parsial, A dan B, LO pada Cartesian product A × B didefinisikan sebagai (a,b) ≤ (a′,b′) jika dan hanya jika a < a′ atau (a = a′ dan b ≤ b′).

Secara bahasa, lexicographic berarti pengurutan kata atau huruf seperti pada penyusunan kamus.

Ilustrasinya, a₁a₂ … a_k muncul sebelum b₁b₂ … b_k jika dan hanya jika a_i pertama, yang mana berbeda dengan b_i muncul sebelum a_i dalam alfabet. Diasumsikan barisan-barisan huruf (kata) tersebut mempunyai panjang yang sama. Kata yang lebih pendek berarti menggunakan karakter spasi ” “, yang bernilai paling minimum.

Andaikan

Adalah himpunan n-tuple, dengan pengurutan total

Lexicographic ordering

dari

menjadi

jika salah satu dari

dan semua bagian sebelumnya sama

Dapat juga dikatakan menyatakan huruf pertama, dan menyatakan huruf kedua, begitu seterusnya.

Secara umum hal ini dapat juga dinyatakan dengan mendefinisikan secara rekursif pengurutan setiap himpunan

Dinyatakan sebelumnya oleh

Hal ini memenuhi

Di mana

Agar lebih sederhana, bandingkan bagian pertama elemen-elemen tersebut. Jika sama, bandingkan dengan yang kedua, dan seterusnya. Keadaan bagian pertama yang tidak sama menentukan hubungan antara seluruh elemen tersebut.

II. Algoritma dan Penjelasan

Dalam optimisasi multitujuan, LO dapat menjadi suatu metode untuk menghasilkan solusi optimal Pareto dari suatu bentuk optimal Pareto lemah.

Langkah pertama optimisasi multitujuan dengan cara LO yaitu Decission Maker (DM) harus mengurutkan fungsi-fungsi sasaran yang ingin dicapai berdasarkan tingkat kepentingannya. Pengurutan ini berarti sasaran yang lebih penting diprioritaskan jauh di atas sasaran yang dianggap kurang penting. Setelah itu, barulah dicari optimisasi dari fungsi-fungsi sasaran yang dikerjakan berdasarkan hasil pengurutan DM tersebut.

Ilustrasi:

Andai diberikan suatu masalah minimisasi yang mempunyai sejumlah k fungsi sasaran. Dengan syarat domain harus memenuhi suatu keadaan S.

Dengan metode penyelesaian LO, fungsi-fungsi tersebut diurutkan oleh DM mulai dari fungsi sasaran yang paling diutamakan, ditulis, hingga fungsi yang paling dikesampingkan, ditulis . Setelah fungsi-fungsi sasaran terurut sesuai LO, dicari nilai minimum yang memenuhi kendala awal dari masing-masing fungsi tersebut. Proses ini dikerjakan sesuai urutan fungsi sasaran.

Masalah Lexicographic sesuai ilustrasi dapat ditulis sebagai berikut:

Lex minimize ,,…., ………( * )

Dengan x € S

Algoritma:

1. Pertama-tama, cari elemen-elemen yang memenuhi kendala awal permasalahan lexicographic tersebut. Dengan demikian didapat vektor sasaran awal Misalkan …., .

2. Dari , cari nilai optimal dari fungsi . Jika elemen pembentuk nilai optimal tunggal, elemen itulah yang merupakan solusi optimal masalah Lexicographic. Jika tidak, nyatakan elemen-elemen pembentuk nilai optimal dengan …., , m≤n.

3. Lanjutkan dengan mencari nilai optimal , , dan seterusnya hingga diperoleh solusi tunggal untuk masalah Lexicographic tersebut. Proses ini dapat berhenti pada suatu fungsi sasaran sebelum ketika telah didapat solusi tunggal yang diharapkan.

Solusi tunggal masalah tersebut merupakan solusi optimal Pareto.

Teorema:

Solusi dari masalah Lexicographic adalah optimal Pareto.

Bukti:

Diberikan x* solusi dari masalah Lexicographic ( * ).

Asumsikan bahwa solusi x* bukan optimal Pareto.

Berarti ada x € S sehingga untuk semua i = 1, 2, …, k dan harus ada paling tidak satu j sehingga .

Diberikan i = 1. Berdasarkan definisi LO, kita tahu bahwa mencapai minimum di x*. Memandang , maka kemungkinannya hanyalah .

Dalam kasus selanjutnya, di mana i = 2, kita pun akan mendapatkan .

Dengan cara yang sama akan diperoleh untuk setiap i = 1, 2, …, k.

Hal ini kontradiktif dengan asumsi awal yang menyatakan harus ada paling tidak satu j sehingga . Berarti pengandaian salah. Yang benar: x* optimal Pareto.

Di sisi lain, jika LO berhenti sebelum semua fungsi sasaran didapatkan hasilnya berarti solusi unik x* telah dicapai untuk . Asumsi berakibat untuk setiap i = 1, 2, …, k sehingga terjadi kontradiksi. Dengan demikian, x* optimal Pareto.

Modifikasi Metode LO

Metode LO tak hanya dapat digunakan dalam pencarian nilai optimal tunggal suatu permasalahan optimisasi multitujuan, namun dapat juga digunakan untuk membuat ranking dari suatu fungsi sasaran. Misalkan kita membutuhkan beberapa solusi optimal, dengan metode LO kita dapat mengoptimalkan fungsi-fungsi sasaran terurut hingga mendapatkan sejumlah solusi optimal yang diinginkan. Dalam hal ini, solusi-solusi masalah LO tersebut otomatis juga terurut menurut tingkat optimalitasnya.

Dalam kehidupan nyata, nilai fungsi sasaran dapat dikonversikan dalam bentuk peringkat atau range. Dengan demikian metode LO tak hanya mengacu pada penyelesaian masalah optimisasi multitujuan yang bersifat numerik, namun menjadi lebih fleksibel dan realistis sehingga hasil pengembangannya dapat diterapkan dalam permasalahan hidup sehari-hari.

Kelebihan dan kekurangan

Kelebihan dari metode LO terutama kepastiannya dalam mencapai solusi optimal Pareto. Selain itu, algoritma LO tergolong sederhana dibanding algoritma optimisasi multitujuan yang lain sehingga mudah dipahami dan diterapkan untuk menyelesaikan permasalahan-permasalahan di berbagai bidang, bahkan di kehidupan nyata yang jauh dari perhitungan matematis sekalipun.

Meski demikian metode ini tetap mempunyai kekurangan. Hal ini nyata pada kesulitan yang dialami DM dalam mengurutkan fungsi sasaran berdasarkan tingkat kepentingan yang absolut. Tetap saja DM yang secara umum adalah manusia memiliki tingkat subjektivitas tertentu, sehingga dalam permasalahan yang sama DM yang berbeda akan menghasilkan solusi optimal pareto yang berbeda pula. Hal ini dikarenakan pertimbangan dan tujuan masing-masing DM yang memang berbeda satu sama lain.

III. Permasalahan

Sebuah perusahaan menginginkan karyawan baru yang kompeten, dengan syarat harus memenuhi kualifikasi sebagai berikut:

1. Lulusan S1 Perguruan Tinggi Terakreditasi

2. Memiliki kemampuan bahasa Inggris yang baik (melampirkan hasil tes TOEFL)

3. Pengalaman kerja minimal 1 tahun.

4. Pernah mengikuti training soft skill.

Diasumsikan, kualifikasi yang harus dipenuhi calon karyawan telah diurutkan oleh tim HRD (sebagai DM) berdasarkan LO dan skor TOEFL yang diperhitungkan dibuat range per 50 skor.

Dari sejumlah lamaran yang masuk terdapat beberapa calon karyawan yang memenuhi kualifikasi, antara lain:

Parjo : PT akreditasi A, skor TOEFL 551, P.kerja 3 th, training 2x.

Tini : PT akreditasi B, skor TOEFL 627, P.kerja 2 th, training 3x.

Budi : PT akreditasi A, skor TOEFL 579, P.kerja 1 th, training 5x.

Cempluk: PT akreditasi A , skor TOEFL 567, P.kerja 6 th, training 3x.

Joko : PT akreditasi A, skor TOEFL 501, P.kerja 7 th, training 2x.

Pertanyaan:

Jika dibutuhkan 2 orang terbaik yang akan diberi gaji $5000 dan $4000 sesuai rankingnya, siapa yang mendapatkannya?

Pemodelan:

Berdasarkan soal di atas dapat dibuat pemodelan soal:

Lex minimixe ,

Subject to x S

dengan

=

Dengan konversi: =

=

=

=

Dan S={calon karyawan yang memenuhi ketiga kualifikasi}

Penyelesaian :

Berdasarkan algoritma LO:

Vektor sasaran awal

Setelah mengoptimalkan , didapat vektor sasaran

Setelah mengoptimalkan , didapat

(Ket: elemen-elemen memenuhi range skor tertinggi yang tersisa yaitu 551-600. Tini yang skor TOEFLnya teartinggi, 627, telah gugur pada saat optimisasi , jadi tidak diperhitungkan)

Setelah mengoptimalkan , didapat

Cempluk merupakan solusi optimal Pareto masalah perekrutan karyawan baru.

Karena masih membutuhkan 1 karyawan baru lagi, pandang dan kerjakan lagi . Selanjutnya didapat Parjo sebagai calon karyawan peringkat kedua.

Fungsi sasaran tidak digunakan karena kita sudah mendapatkan solusi optimal pada saat , sehingga proses berhenti.

Hasilnya:

Karyawan baru: Cempluk gaji $5000, Parjo gaji $4000

Daftar Pustaka:

Miettinen, Kaisa M; Nonlinear Multiobjective Optimization; 2004; Norwel Massachusetts; Kluwer Academic Publishers.

http://en.wikipedia.org/wiki/Lexicographical_order

http://mathworld.wolfram.com/LexicographicOrder.html