Skip to content
Kembali ke hasil pencarian

Pemrograman Linear Multi-Objektif (MOLP)

Diperkenalkan oleh
Steuer, R. E.; Charnes, A.; Cooper, W. W.
Tahun
1955–1986
Jenis
Mathematical optimization / vector optimization
Keluarga
Simulation / optimization

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Pemrograman Linear Multi-Objektif (MOLP) memperluas pemrograman linear klasik untuk menangani beberapa fungsi tujuan linear yang saling bertentangan secara bersamaan dalam wilayah layak yang didefinisikan oleh kendala linear.

Alih-alih satu solusi optimal, MOLP menghasilkan batas Pareto-efisien dari mana pengambil keputusan memilih pertukaran (trade-off) yang disukai. Ini adalah dasar bagi riset operasi dan ilmu manajemen untuk masalah alokasi sumber daya, perencanaan, dan desain dengan tujuan yang bersaing.

Intuisi di balik metode

Dalam pemrograman linear biasa, Anda meminimalkan satu biaya atau memaksimalkan satu keuntungan, tetapi keputusan nyata hampir selalu melibatkan beberapa tujuan yang bersaing — meminimalkan biaya sambil memaksimalkan tingkat layanan sambil meminimalkan emisi. MOLP mengakui bahwa tidak ada satu solusi pun yang terbaik untuk semua tujuan sekaligus. Ini memetakan seluruh batas solusi non-dominan (Pareto-efisien) di mana peningkatan satu tujuan pasti akan memperburuk tujuan lain. Pengambil keputusan kemudian menggunakan informasi preferensi — bobot, tingkat aspirasi, atau kueri interaktif — untuk memilih solusi akhir dari batas tersebut, membuat pertukaran eksplisit daripada tersembunyi di dalam skor komposit.

Sejarah

Dasar-dasar teoretis pemrograman linear multi-objektif berawal dari karya Charnes dan Cooper pada tahun 1950-an tentang pemrograman tujuan (goal programming) dan Koopmans tentang produksi efisien. Buku teks Steuer tahun 1986 mengkonsolidasikan bidang ini, menstandardisasi metode jumlah tertimbang, epsilon-kendala, dan interaktif yang tetap menjadi standar hingga saat ini. MOLP sekarang menjadi topik inti dalam kurikulum riset operasi di seluruh dunia.

Kapan digunakan

Gunakan MOLP ketika masalah memiliki beberapa tujuan linear yang bersaing dan kendala linear, data bersifat kontinu dan diketahui secara pasti (atau dapat dianggap deterministik), dan pengambil keputusan perlu memahami pertukaran secara eksplisit daripada menerima skor yang telah diagregasi sebelumnya. Pengaturan tipikal meliputi perencanaan produksi, alokasi portofolio, perutean transportasi, dan penganggaran sumber daya publik. JANGAN gunakan ketika tujuan atau kendala bersifat non-linear (gunakan pemrograman non-linear multi-objektif atau metaheuristik sebagai gantinya), ketika data bersifat diskrit atau biner (gunakan pemrograman integer multi-objektif), ketika jumlah tujuan melebihi lima atau enam (batas efisien menjadi sulit dihitung), atau ketika pengambil keputusan tidak bersedia terlibat dalam elisitasi preferensi iteratif.

Batasan dan pertimbangan

  • Terbatas pada fungsi tujuan linear dan kendala linear; masalah dunia nyata seringkali non-linear.
  • Batas efisien dapat berisi jumlah titik ekstrem yang eksponensial dalam dimensi yang lebih tinggi, membuat enumerasi komprehensif menjadi tidak praktis.
  • Membutuhkan data numerik yang tepat; ketidakpastian atau kekaburan dalam koefisien tidak ditangani secara bawaan.
  • Metode interaktif sangat bergantung pada ketersediaan dan kemampuan pengambil keputusan untuk mengartikulasikan preferensi secara konsisten.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Menghasilkan seluruh batas Pareto-efisien, memberikan gambaran lengkap tentang pertukaran kepada pengambil keputusan.
  • Layak secara komputasi untuk ukuran masalah sedang melalui pemecah berbasis simpleks.
  • Menjamin optimalitas matematis dari setiap titik pada batas efisien.
  • Didukung dengan baik oleh perangkat lunak yang matang (CPLEX, Gurobi, alternatif open-source).
  • Pertukaran dibuat eksplisit daripada digabungkan menjadi indeks komposit yang buram.

Penerapan

  • Perencanaan produksi yang menyeimbangkan biaya, throughput, dan utilisasi sumber daya.
  • Optimalisasi portofolio yang memperdagangkan imbal hasil, risiko, dan likuiditas.
  • Desain jaringan transportasi dan logistik dengan tujuan biaya dan layanan yang bersaing.
  • Perencanaan sistem energi yang meminimalkan biaya sambil memenuhi target emisi dan keandalan.
  • Alokasi sumber daya kesehatan yang menyeimbangkan ekuitas, efisiensi, dan kendala anggaran.
  • Manajemen lingkungan yang mengoptimalkan kinerja ekonomi dan ekologi secara bersamaan.

Cara kerjanya

Cara kerjanya

1

Formulasikan k fungsi tujuan linear f1(x) hingga fk(x) dan wilayah layak X yang didefinisikan oleh kendala ketidaksetaraan dan kesetaraan linear (Ax <= b, x >= 0). Identifikasi tujuan mana yang akan diminimalkan dan mana yang akan dimaksimalkan. Konfirmasikan bahwa semua fungsi tujuan dan kendala bersifat linear terhadap variabel keputusan.

Rumus
\min_{x \in X} \mathbf{f}(x) = (f_1(x), f_2(x), \ldots, f_k(x))^T \text{ s.t. } Ax \leq b,\; x \geq 0
2

Hasilkan himpunan solusi Pareto-efisien (non-dominan). Pendekatan umum meliputi metode jumlah tertimbang (weighted-sum method) (memvariasikan bobot di seluruh simpleks), metode epsilon-kendala (epsilon-constraint method) (mengoptimalkan satu tujuan sambil membatasi yang lain), dan metode Chebyshev. Setiap pendekatan menelusuri sebagian atau seluruh batas efisien.

3

Terapkan teknik skalarisasi untuk mengubah masalah vektor menjadi urutan LP berobjektif tunggal. Dalam pendekatan jumlah tertimbang, selesaikan min sum(wi * fi(x)) untuk vektor bobot yang divariasikan secara sistematis. Catat setiap titik ekstrem efisien dari ruang tujuan.

Rumus
\min_{x \in X} \sum_{i=1}^{k} w_i f_i(x), \quad w_i \geq 0, \; \sum w_i = 1
4

Kumpulkan titik-titik ekstrem efisien dan garis-garis yang menghubungkannya untuk mengkarakterisasi batas Pareto. Analisis rentang setiap tujuan di seluruh batas untuk memahami besarnya pertukaran. Sajikan batas kepada pengambil keputusan melalui tabel atau plot bi-objektif.

5

Libatkan pengambil keputusan untuk memilih solusi yang disukai dari himpunan efisien. Metode interaktif (STEM, NIMBUS) bergantian antara menyajikan solusi dan meminta pengambil keputusan untuk menyatakan preferensi, mengkonvergensikan pada pilihan akhir yang paling mencerminkan prioritas mereka.

Kesalahan umum

  • Menggunakan bobot tetap dalam skalarisasi jumlah tertimbang dan hanya melaporkan satu solusi mengaburkan batas dan menggagalkan tujuan MOLP.
  • Membingungkan efisiensi Pareto dengan optimalitas: setiap titik pada batas efisien, tetapi tidak ada yang 'terbaik' secara global tanpa informasi preferensi.
  • Mengabaikan pemeriksaan apakah wilayah layak terbatas; masalah yang tidak terbatas menghasilkan himpunan efisien yang tidak terbatas.
  • Memperlakukan MOLP sebagai kotak hitam tanpa melibatkan pengambil keputusan dalam pemilihan menghasilkan pilihan akhir yang sewenang-wenang.
  • Menerapkan MOLP pada masalah yang secara inheren integer tanpa beralih ke pemrograman integer multi-objektif, menghasilkan solusi yang melanggar integralitas.

Pertanyaan yang sering diajukan

Bagaimana MOLP berbeda dari pemrograman tujuan?

Pemrograman tujuan adalah kasus khusus atau varian: ia mengubah setiap tujuan menjadi tingkat aspirasi dan kemudian meminimalkan deviasi dari target tersebut, menghasilkan satu solusi. MOLP dalam bentuk umumnya berusaha mengkarakterisasi seluruh batas efisien tanpa menentukan tingkat target sebelumnya, memberikan fleksibilitas lebih kepada pengambil keputusan.

Bisakah MOLP menangani lebih dari dua tujuan?

Ya, tetapi batas Pareto menjadi lebih sulit divisualisasikan di luar dua atau tiga tujuan dan jumlah titik ekstrem efisien dapat tumbuh secara eksponensial. Metode interaktif dan teknik subset representatif direkomendasikan untuk empat atau lebih tujuan.

Bagaimana jika data saya tidak pasti?

MOLP standar mengasumsikan koefisien deterministik. Ketidakpastian dapat diatasi dengan memperluas ke pemrograman linear multi-objektif stokastik (kendala peluang, pendekatan berbasis skenario) atau optimasi multi-objektif yang kuat, yang merupakan metode terpisah.

Apakah MOLP sama dengan optimasi multi-objektif?

MOLP adalah kasus khusus dari optimasi multi-objektif di mana semua tujuan dan kendala bersifat linear. Optimasi multi-objektif adalah bidang yang lebih luas yang juga mencakup varian non-linear, integer, dan kombinatorial.

Metode skalarisasi mana yang harus saya gunakan?

Metode jumlah tertimbang sederhana tetapi melewatkan bagian batas yang tidak cembung. Metode epsilon-kendala dapat memulihkan seluruh batas bahkan untuk wilayah yang tidak cembung dan umumnya lebih disukai untuk analisis menyeluruh. Metode interaktif paling baik ketika keterlibatan pengambil keputusan dimungkinkan.

Metode terkait

Sumber

  1. Steuer, R. E. (1986). Multiple Criteria Optimization: Theory, Computation, and Application. John Wiley & Sons, New York.

    ISBN: 9780471888468
    Disalin.
  2. Chankong, V., Haimes, Y. Y. (1983). Multiobjective Decision Making: Theory and Methodology. North-Holland, New York.

    Buka referensi publikasi
    Disalin.