Pengguna:Kekavigi/bak pasir

Pemrograman tujuan (Goal Programming, GP) adalah sebuah metode optimisasi multiobjektif, dalam bidang analisis keputusan multi-kriteria (multi-criteria decision analysis, MCDA). Metode ini dapat dianggap sebagai perumuman dari pemrograman linear, agar dapat menangani beberapa objektif yang umumnya saling berkonflik, contohnya meningkatkan keuntungan bersih sekaligus mengurangi besarnya ongkos usaha. GP melakukan optimisasi dengan mencatat target nilai yang ingin dicapai setiap objektif, lalu meminimumkan besar penyimpangan-penyimpangan yang tidak diinginkan dari nilai target-target tersebut. Fungsi objektif yang disebut fungsi pencapaian digunakan untuk menghampiri preferensi pengambil keputusan terkait caranya meminimumkan penyimpangan-penyimpangan tersebut. Fungsi ini dapat bernilai skalar maupun vektor, tergantung varian GP yang digunakan.

GP menggunakan filosofi satisficing ketimbang optimising dalam pengambilan solusi. GP dapat digunakan untuk melakukan analisis terkait: daftar sumberdaya yang diperlukan untuk memenuhi suatu kumpulan objektif, besarnya ketercapaian (atau kompromi) setiap objektif yang dihasilkan suatu kombinasi sumberdaya, dan solusi terbaik dari berbagai kendala dan tingkat kepentingan setiap objektif. GP telah diterapkan dalam pemilihan portofolio, perencanaan agrikultur, sampai masalah penjadwalan.

Sejarah

Formulasi goal programming paling awal diperkenalkan oleh Charnes et al. dalam permasalahan menentukan kompensasi untuk manajer. Walaupun pada saat itu model dianggap sebagai adaptasi dari pemrograman linear (LP), formulasi tersebut menampilkan konsep "regresi terbatas" yang menjadi dasar minimisasi dalam GP. Istilah goal programming baru muncul pada buku teks oleh Charnes dan Cooper pada tahun 1961. Tetapi sama seperti sebelumnya, model masih disajikan sebagai perumuman pemrograman linear (LP) untuk menyelesaikan masalah LP yang infeasible (tidak memiliki solusi). Pengembangan model GP lebih lanjut yang dilakukan oleh oleh Ijiri, buku teks oleh Lee dan Ignizio, membuat model ini menjadi umum digunakan sebagai alat riset operasi.

Jones menyebut faktor formulasi yang sederhana dan kemiripannya dengan LP, membuat model GP menjadi salah satu teknik paling populer dalam MCDM. Dalam masa ini pula, berbagai varian GP juga dikembangkan untuk menyelesaikan masalah dalam banyak bidang. Akan tetapi banyak kritik disampaikan terkait GP pada tahun 1980-an, yang menurut Jones terjadi karena kesalahan mendasar yang disebabkan oleh kurangnya pemahaman praktek MCDM. Perdebatan terkait fundamental model GP selanjutnya menghasilkan publikasi buku teks oleh Romero pada tahun 1991, yang menunjukkan masalah yang terjadi lebih diakibatkan oleh praktik pemodelan yang buruk, dan memberikan praktik-praktik GP yang baik.

Schniederjans merangkum perkembangan GP sampai tahun 1995, dan mencatat bibliografi banyak artikel yang berkaitan dengan GP. Sedangkan Jones dan Tamiz memberikan bibliografi serta deskripsi untuk artikel periode 1990-2000. Sebuah buku teks tahun 2010 oleh Jones dan Tamiz berisi penjelasan komprehensif terkait metode GP yang terbaru.

Pendahuluan

Karena model GP dibuat dari adaptasi model pemrograman linear (LP), perumusan model GP dapat dihasilkan dari mengubah notasi dan asumsi-asumsi model LP. Model LP dapat dinyatakan dalam bentuk kanonik sebagai

$${\begin{aligned}\min &\;Z=\sum _{j=1}^{n}c_{j}x_{j}\\{\text{dengan kendala}}&\;\sum _{j=1}^{n}a_{ij}x_{j}\geq b_{i};\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;x_{j}\geq 0;\;\;{\text{untuk }}j=1,\,\dots ,\,n\end{aligned}}$$

dengan $m$ menyatakan banyaknya kendala, $x_{j}$ disebut variabel keputusan, dan $Z$ disebut fungsi objektif. Bentuk kendala model di atas memungkinkan ruas sisi kiri dapat bernilai lebih besar (memiliki deviasi bernilai positif) dibandingkan target $b_{i}$. Dengan bantuan aritmetika dasar, model LP tersebut juga dapat menyertakan kendala dalam bentuk 'kurang dari' dan 'sama dengan'. Akan tetapi, terlepas dari jenis kendala yang digunakan, LP hanya mempertimbangkan solusi yang memenuhi semua kendala. Ketika kendala-kendala dalam model LP tidak semuanya dapat saling dipenuhi, model LP disebut infeasible dan tidak memiliki solusi. Agar tetap menghasilkan solusi yang wajar dalam kondisi infeasible, Charnes dan Cooper menganggap masing-masing kendala yang menyusun model LP sebagai sebuah fungsi

$$f_{i}(\mathbf {x} )={\Bigg |}\sum _{i=1}^{n}a_{ij}x_{j}-b_{i}{\Bigg |};\;\;{\text{untuk }}i=1,\,\dots ,\,m$$

dan dianggap sebagai sebuah tujuan (goal) yang perlu dipenuhi agar menghasilkan solusi feasible. Dengan kata lain, solusi feasible dihasilkan ketika $f_{i}(\mathbf {x} )=0$. Pada keadaan hal ini tidak mungkin (karena model bersifat infeasible), solusi 'terbaik' adalah solusi yang terletak sedekat mungkin dengan tujuan-tujuan yang ditetapkan, dan dapat dicari dengan melakukan optimisasi

$${\begin{aligned}\min &\;Z=\sum _{i=1}^{m}(d_{i}^{+}+d_{i}^{-})\\{\text{dengan kendala}}&\;\sum _{j=1}^{n}a_{ij}x_{j}-d_{i}^{+}+d_{i}^{-}=b_{i};\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;d_{i}^{+},\,d_{i}^{-}\geq 0;\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;\;\;\;\;\;\;\;x_{j}\geq 0;\;\;{\text{untuk }}j=1,\,\dots ,\,n\end{aligned}}$$

dengan $d_{i}^{+}$ disebut variabel deviasi positif dan $d_{i}^{-}$ disebut variabel deviasi negatif. Bentuk ini adalah dasar dari model GP. Untuk membedakannya dengan LP, fungsi $Z$ selanjutnya disebut dengan fungsi pencapaian. Fungsi ini hanya menyertakan variabel-variabel deviasi yang ingin diminimumkan dan tidak melibatkan variabel-variabel keputusan. Sedangkan variabel-variabel deviasi tersebut dapat dihasilkan dari $f_{i}(\mathbf {x} )$ menggunakan hubungan

$$d_{i}^{+}={\frac {1}{2}}{\Big [}|f_{i}(\mathbf {x} )|+f_{i}(\mathbf {x} ){\Big ]}={\begin{cases}\sum a_{ij}-b_{i}&{\text{jika }}\sum a_{ij}\geq b_{i}\\0&{\text{lainnya.}}\\\end{cases}}$$

dan

$$d_{i}^{-}={\frac {1}{2}}{\Big [}|f_{i}(\mathbf {x} )|-f_{i}(\mathbf {x} ){\Big ]}={\begin{cases}b_{i}-\sum a_{ij}&{\text{jika }}\sum a_{ij}\leq b_{i}\\0&{\text{lainnya.}}\\\end{cases}}$$

Definisi variabel-variabel deviasi di atas mengartikan sebuah kendala tidak dapat mengalami pencapaian melebihi target (nilai deviasi positif $d_{i}^{+}>0$) sekaligus pencapaian dibawah target (nilai deviasi $d_{i}^{-}>0$) secara bersamaan. Kendala-kendala pada model GP disebut dengan kendala lunak (soft constraint, juga disebut goal constraint) untuk membedakannya dengan kendala pada model LP; yang selanjutnya dirujuk sebagai kendala tegas (hard constraint). Kendala tegas dapat disertakan dalam model GP namun disarankan tidak dalam jumlah yang banyak, karena dapat meniadakan solusi-solusi alternatif yang mungkin menarik bagi pengambil keputusan.

Normalisasi

Dalam proses penyelesaian model GP, peran variabel-variabel deviasi dalam fungsi pencapaian perlu dinormalisasi. Normalisasi menyebabkan variabel-variabel deviasi memiliki satuan dan magnitudo yang sama, sehingga perhitungan antar variabel-variabel deviasi masuk akal dilakukan dan hasilnya dapat dibandingkan. Menggunakan masalah

$${\begin{aligned}\min &\;d_{1}^{+}+d_{2}^{-}+d_{3}^{-}+d_{4}^{-}\\{\text{dengan kendala}}&\;\;\;\;\,3x_{1}+\;\;\;\,4x_{2}-d_{1}^{+}+d_{1}^{-}=560\\&\;100x_{1}+150x_{2}-d_{2}^{+}+d_{2}^{-}=7800\\&\;\,\;\;\;\;\;x_{1}\;\;\;\;\;\;\;\;\;\;\;\;\;-d_{3}^{+}+d_{3}^{-}=80\\&\;\,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x_{2}-d_{4}^{+}+d_{4}^{-}=90\\&\;\,\;\;\;\;\;x_{1}+\;\;\;\;\;x_{2}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\leq 160\\&\;d_{i}^{+},\,d_{i}^{-}\geq 0;\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;\;\;\;\;\;\;\;x_{j}\geq 0;\;\;{\text{untuk }}j=1,\,\dots ,\,n\end{aligned}}$$

sebagai contoh, berikut beberapa teknik normalisasi yang umum dilakukan. Walaupun juga terdapat banyak metode normalisasi lainnya, perlu diingat bahwa pilihan dari normalisasi yang sesuai tergantung pada situasi masalah yang terjadi dan preferensi pengambil keputusan.

Normalisasi persentase

Normalisasi ini akan menskala setiap variabel deviasi sehingga kontribusinya di fungsi pencapaian menyatakan persen penyimpangan dari nilai target yang ditetapkan. Secara matematis, fungsi pencapaian pada model di atas akan berubah menjadi

$$\min {\frac {d_{1}^{+}}{560}}+{\frac {d_{2}^{-}}{7800}}+{\frac {d_{3}^{-}}{80}}+{\frac {d_{4}^{-}}{90}}.$$

Normalisasi jenis ini mudah diterapkan dan konsep total persentase penyimpangan sederhana untuk diartikan. Akan tetapi, metode ini tidak cocok jika pengambil keputusan ingin membandingkan secara langsung beberapa tujuan yang diukur dalam unit satuan yang sama. Sebagai contoh, misalkan masalah GP dengan dua tujuan berikut yang dinyatakan dalam satuan rupiah:

$${\begin{aligned}x_{1}+3x_{2}-d_{1}^{+}+d_{1}^{-}&=1000\\2x_{1}+x_{2}-d_{1}^{+}+d_{2}^{-}&=500\end{aligned}}$$

Menerapkan normalisasi persentase akan menghasilkan fungsi pencapaian

$$\min {\frac {d_{1}^{-}}{1000}}+{\frac {d_{2}^{-}}{500}}$$

yang mengartikan penyimpangan seribu rupiah dari tujuan pertama, setara dengan setengah penyimpangan seribu rupiah dari tujuan kedua. Sudut pandang ini benar jika  persentase penyimpangan yang ingin dibandingkan, namun tidak sesuai jika penyimpangan kedua tujuan dibandingkan dalam satuan rupiah.

Normalisasi nol-satu

Normalisasi ini akan menskala setiap variabel deviasi sehingga bernilai di antara 0 sampai 1 dalam fungsi pencapaian. Dengan kata lain, normalisasi ini mengukur penyimpangan terburuk yang dapat terjadi untuk setiap variabel deviasi. Suatu nilai batas yang realistis dapat ditetapkan bagi variabel deviasi yang *unbounded (tidak memiliki batas). Fungsi pencapaian pada model akan berubah menjadi

$$\min {\frac {d_{1}^{+}}{\max d_{1}^{+}}}+{\frac {d_{2}^{-}}{\max d_{2}^{-}}}+{\frac {d_{3}^{-}}{\max d_{3}^{-}}}+{\frac {d_{4}^{-}}{\max d_{4}^{-}}}$$

dengan masing-masing nilai $\max$ didapatkan dari optimisasi satu-objektif (model LP standar) dari kendala-kendala model GP di atas. Metode ini cocok pada kasus permasalahan dengan setiap objektif memiliki interval nilai yang jelas, dan setiap solusi pada ruang solusi ingin diperhatikan pengambil keputusan. Tapi, tujuan yang tidak terbatas (tidak memiliki batas penyimpangan terburuk), atau masalah dengan banyak ruang solusi yang unbounded, dapat menghasilkan solusi-solusi yang tidak relevan ketika menggunakan normalisasi ini. Disamping itu, normalisasi nol-satu memerlukan optimisasi satu-objektif sebanyak variabel deviasi yang disertakan dalam fungsi pencapaian. Hal ini mungkin tidak praktis pada masalah yang kompleks dengan waktu komputasi yang lama.

Normalisasi Euklides

Normalisasi ini akan menskala setiap variabel deviasi dengan rerata Euklides dari tujuannya. Pada masalah GP di atas, fungsi pencapaian pada model akan berubah menjadi

$$\min {\frac {d_{1}^{+}}{\sqrt {4^{2}+3^{2}}}}+{\frac {d_{2}^{-}}{\sqrt {100^{2}+150^{2}}}}+{\frac {d_{3}^{-}}{\sqrt {1^{2}}}}+{\frac {d_{4}^{-}}{\sqrt {1^{2}}}}$$

Normalisasi Euklides kokoh (robust) secara komputasi; karena dapat dilakukan untuk setiap tujuan dan nilai target, dan tidak memerlukan optimisasi atau perhitungan yang kompleks untuk mendapatkan konstanta normalisasi. Akan tetapi, dua jenis permasalahan terkait metode ini terlihat jelas dari fungsi pencapaian yang dihasilkan. Pertama, normalisasi ini tidak mempertimbangkan nilai target sehingga menghasilkan konstanta yang rendah untuk tujuan ke-3 dan ke-4. Sedangkan permasalahan kedua, berbeda dengan kedua normalisasi sebelumnya, nilai optimal yang dihasilkan oleh fungsi pencapaian tidak memiliki makna yang jelas. Karena dua hal tersebut, Jones menyarankan normalisasi ini sebaiknya digunakan untuk kasus permasalahan yang tidak praktis untuk menggunakan normalisasi persentase maupun nol-satu.

Varian

GP Berbobot

$${\begin{aligned}\min &\;Z=\sum _{i=1}^{m}{\frac {1}{k_{i}}}{\Big (}w_{i}^{+}d_{i}^{+}+w_{i}^{-}d_{i}^{-}{\Big )}\\{\text{dengan kendala}}&\;\sum _{j=1}^{n}a_{ij}x_{j}-d_{i}^{+}+d_{i}^{-}=b_{i};\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;d_{i}^{+},\,d_{i}^{-}\geq 0;\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;\;\;\;\;\;\;\;x_{j}\geq 0;\;\;{\text{untuk }}j=1,\,\dots ,\,n\end{aligned}}$$

GP Leksikografik

$${\begin{aligned}{\text{lex min}}&\;{\Big [}h_{1}(\mathbf {d} ^{+},\,\mathbf {d} ^{-}),\,\dots ,h_{L}(\mathbf {d} ^{+},\,\mathbf {d} ^{-}){\Big ]}\\{\text{dengan kendala}}&\;\sum _{j=1}^{n}a_{ij}x_{j}-d_{i}^{+}+d_{i}^{-}=b_{i};\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;d_{i}^{+},\,d_{i}^{-}\geq 0;\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;\;\;\;\;\;\;\;x_{j}\geq 0;\;\;{\text{untuk }}j=1,\,\dots ,\,n\end{aligned}}$$

dengan

$h_{l}(\mathbf {d} ^{+},\,\mathbf {d} ^{-})=\sum _{i=1}^{m}{\frac {1}{k_{i}}}{\Big (}w_{il}^{+}d_{i}^{+}+w_{il}^{-}d_{i}^{-}{\Big )}$

GP Chebyshev

$${\begin{aligned}\min &\;\lambda \\{\text{dengan kendala}}&\;\sum _{j=1}^{n}a_{ij}x_{j}-d_{i}^{+}+d_{i}^{-}=b_{i};\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;\sum _{i=1}^{m}{\frac {1}{k_{i}}}{\Big (}w_{i}^{+}d_{i}^{+}+w_{i}^{-}d_{i}^{-}{\Big )}\leq \lambda \\&\;d_{i}^{+},\,d_{i}^{-}\geq 0;\;\;{\text{untuk }}i=1,\,\dots ,\,m\\&\;\;\;\;\;\;\;\;x_{j}\geq 0;\;\;{\text{untuk }}j=1,\,\dots ,\,n\end{aligned}}$$

Restorasi solusi

by contoh aja.

Lihat pula

Compromise programming

Constraint satisfaction problem