Optimasi Multikriteria

Optimasi Multikriteria (juga pemrograman multikriteria, Ingg. multi-objective optimization, multi-criteria optimization) — adalah cabang optimasi matematis yang mempelajari masalah optimasi simultan berdasarkan dua atau lebih fungsi tujuan (kriteria) yang pada umumnya saling bertentangan satu sama lain. Secara formal, masalah ini dituliskan sebagai minimisasi fungsi tujuan vektor pada himpunan solusi yang layak.

Definisi dan Terminologi

Masalah optimasi multikriteria dalam bentuk umum dituliskan sebagai berikut: $\underset{x\in S}{min}\{f_1(x),f_2(x),\dots ,f_k(x)\}$ di mana $S\subseteq {ℝ}^n$ — himpunan solusi layak yang tidak kosong, dan $f_i:S\to ℝ$ — fungsi-fungsi tujuan ($k\ge 2$). Vektor $f(x)=(f_1(x),\dots ,f_k(x))$ disebut vektor tujuan.

Berbeda dengan optimasi skalar, dalam rumusan multikriteria biasanya tidak terdapat satu solusi tunggal yang memperbaiki nilai semua kriteria secara bersamaan. Oleh karena itu, konsep klasik optimalitas digeneralisasi menggunakan konsep optimalitas Pareto.

• Solusi Pareto (solusi optimal Pareto atau solusi efisien): solusi layak $x^{\ast }\in S$ yang tidak memiliki solusi lain $x\in S$ sedemikian sehingga $f_i(x)\le f_i(x^{\ast })$ untuk semua $i=1,\dots ,k$, dan sekaligus $f_j(x)<f_j(x^{\ast })$ untuk setidaknya satu indeks $j$. Dengan kata lain, suatu solusi dikatakan optimal Pareto jika tidak ada nilai kriteria yang dapat diperbaiki tanpa memperburuk setidaknya satu kriteria lainnya.
• Front Pareto (atau himpunan Pareto): himpunan semua vektor tujuan yang berkorespondensi dengan solusi-solusi optimal Pareto.
• Solusi lemah optimal Pareto: solusi $x^{\ast }\in S$ yang tidak memiliki solusi lain $x\in S$ sedemikian sehingga $f_i(x)<f_i(x^{\ast })$ untuk semua $i$.

Sifat-Sifat dan Teorema Utama

• Teorema jumlah berbobot: Dalam masalah konveks (di mana semua fungsi $f_i(x)$ dan himpunan $S$ konveks), setiap solusi optimal Pareto $x^{\ast }$ merupakan solusi dari masalah skalar minimisasi jumlah berbobot kriteria $\underset{x\in S}{min}\sum _{i=1}^k{w}_i{f}_i(x)$ untuk suatu himpunan bobot non-negatif tertentu $w_i\ge 0$. Namun, pada masalah non-konveks, metode ini mungkin tidak dapat menemukan sebagian bagian dari front Pareto.

• Kondisi optimalitas Karush-Kuhn-Tucker (KKT): Kondisi optimalitas yang diperlukan untuk masalah halus digeneralisasi ke kasus multikriteria. Pada titik optimum Pareto, terdapat sekumpulan pengali (bobot) non-negatif yang tidak nol, di mana gradien fungsi tujuan dan kendala aktif saling bergantung secara linear.

• Sifat-sifat himpunan solusi: Front Pareto memiliki sejumlah karakteristik kualitatif yang penting. Batasnya dibatasi oleh titik ideal (yang dibentuk dari minimum per elemen semua kriteria) dan titik nadir (dari maksimum per elemen pada front).

Contoh-Contoh

• Masalah linear: Minimalkan $f_1(x)=-x_1$ dan $f_2(x)=-x_2$ dengan kendala $x_1+x_2\le 1$, $x_1,x_2\ge 0$. Di sini, perbaikan satu kriteria (misalnya, peningkatan $x_1$) secara tak terelakkan menyebabkan perburukan kriteria lainnya (penurunan $x_2$). Himpunan solusi optimal Pareto adalah segmen garis $x_1+x_2=1$.
• Masalah non-konveks: Minimalkan $f_1(x)=x^2$ dan $f_2(x)=(x-2{)}^2$ pada segmen $[0,2]$. Front Pareto bersifat non-konveks. Metode jumlah berbobot dengan bobot positif tidak akan mampu menemukan solusi di bagian dalam segmen tersebut (misalnya, pada titik $x=1$), karena kombinasi linear kriteria hanya akan mencapai minimum di titik-titik ekstrem $x=0$ atau $x=2$.

Konsep Terkait dan Penerapan

Optimasi multikriteria berkaitan erat dengan pengambilan keputusan multikriteria (MCDM), yang mempelajari pemilihan alternatif terbaik dengan mempertimbangkan preferensi pengambil keputusan. Metode utama transformasi masalah multikriteria menjadi skalar (skalarisasi) meliputi:

• Metode jumlah berbobot.
• Metode kendala $\epsilon$: Satu kriteria dioptimalkan, sementara kriteria lainnya diubah menjadi kendala berbentuk $f_i(x)\le {\epsilon }_i$. Metode ini mampu menemukan solusi pada bagian non-konveks dari front.

Optimasi multikriteria memiliki penerapan yang luas dalam perancangan rekayasa, ekonomi (misalnya, optimasi portofolio), manajemen, dan ekologi.

Lihat Pula

• Optimalitas Pareto
• Optimasi vektor
• Teori pengambilan keputusan
• Sistem pendukung pengambilan keputusan
• Riset operasi