Pemrograman Linear Deterministik — LP Klasik dengan Parameter Pasti
- Diperkenalkan oleh
- George B. Dantzig
- Tahun
- 1947
- Jenis
- Deterministic mathematical optimization
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Linear Deterministik (DLP) adalah bentuk klasik dari pemrograman linear di mana semua koefisien fungsi tujuan, koefisien kendala, dan nilai sisi kanan diketahui secara pasti.
Model ini menemukan alokasi sumber daya optimal untuk memaksimalkan atau meminimalkan tujuan linear di bawah kendala linear, memberikan solusi yang tepat dan dapat direproduksi di bawah data yang tetap dan pasti.
Intuisi di balik metode
Bayangkan mengalokasikan anggaran tetap ke berbagai proyek, masing-masing dengan biaya dan pengembalian yang diketahui, tunduk pada batas sumber daya yang Anda ketahui secara presisi. DLP mengkodekan ini sebagai sistem pertidaksamaan linear dan menemukan solusi titik sudut yang menghasilkan nilai paling banyak dari kendala tersebut. Karena setiap parameter pasti — tidak ada distribusi probabilitas, tidak ada ambiguitas — pemecah (solver) mengembalikan satu rencana optimal yang tepat daripada distribusi hasil. Kejelasan ini menjadikan DLP model pilihan pertama yang alami ketika data terukur dengan baik dan ketidakpastian bukan perhatian utama.
Sejarah
Pemrograman linear diformalkan oleh George B. Dantzig pada tahun 1947 dengan pengembangan algoritma Simplex saat bekerja untuk Angkatan Udara AS. Monograf Dantzig tahun 1963 menjadi referensi kanonik. Kualifikasi 'deterministik' muncul ketika varian LP stokastik diperkenalkan (Dantzig dan Beale, 1950-an–1960-an) untuk membedakan model parameter pasti asli dari perluasan probabilistiknya.
Kapan digunakan
Gunakan LP Deterministik ketika masalah keputusan dapat dimodelkan dengan tujuan linear dan kendala linear, dan ketika semua parameter diketahui dengan kepastian yang cukup untuk memperlakukannya sebagai konstanta tetap. Pengaturan ideal meliputi perencanaan produksi, transportasi dan logistik, masalah diet dan pencampuran, serta aliran jaringan dalam kondisi stabil. JANGAN gunakan DLP ketika parameter benar-benar tidak pasti dan risiko menjadi perhatian — lebih pilih LP Stokastik atau LP Robust. Hindari DLP ketika tujuan atau kendala non-linear, ketika variabel harus integer (gunakan MIP), atau ketika beberapa tujuan yang saling bertentangan harus diseimbangkan secara bersamaan tanpa mengagregasikannya menjadi satu jumlah tertimbang (gunakan LP multi-tujuan atau pemrograman tujuan).
Batasan dan pertimbangan
- Memerlukan semua hubungan harus benar-benar linear — kurva biaya non-linear atau pengembalian yang menurun tidak dapat ditangkap tanpa aproksimasi.
- Semua parameter harus diketahui dan tetap; model tidak menyediakan mekanisme bawaan untuk menangani ketidakpastian atau kesalahan estimasi parameter.
- Solusi optimal mungkin tidak unik (degenerasi), membuat pilihan basis pelaporan menjadi ambigu tanpa kriteria tambahan.
- Persyaratan integer atau kombinatorial (misalnya, keputusan ya/tidak) memerlukan perluasan ke pemrograman campuran integer, yang secara komputasi lebih sulit.
- Masalah skala besar dengan matriks kendala yang padat dapat memakan banyak memori bahkan untuk pemecah modern.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Solusi optimal global dijamin untuk setiap instans LP yang layak dan terbatas karena sifat cembung.
- Sangat terukur — pemecah modern menangani jutaan variabel dan kendala dalam hitungan detik.
- Variabel dual dan analisis sensitivitas memberikan interpretasi ekonomi yang kaya tentang harga bayangan dan rentang (ranging).
- Formulasi yang transparan dan dapat diaudit: setiap asumsi eksplisit dalam matriks kendala.
- Ekosistem perangkat lunak yang matang (CPLEX, Gurobi, HiGHS, GLPK) dengan implementasi yang andal dan teruji dengan baik.
- Sinyal kelayakan lulus/gagal yang jelas: ketidaklayakan segera mengungkapkan kesalahan spesifikasi model.
Penerapan
- Penjadwalan produksi dan manufaktur dengan kapasitas sumber daya tetap dan permintaan yang diketahui.
- Transportasi dan logistik: menemukan rute pengiriman biaya minimum melintasi jaringan.
- Masalah diet dan pencampuran: memformulasikan campuran nutrisi atau kimia berbiaya terendah yang memenuhi kendala komposisi.
- Optimalisasi portofolio keuangan di bawah pengembalian linear dan kendala anggaran.
- Perencanaan sistem energi: pengiriman optimal unit pembangkit listrik dengan biaya dan kapasitas yang diketahui.
- Desain jaringan rantai pasokan ketika permintaan dan waktu tunggu diperlakukan sebagai konstanta yang diketahui.
Cara kerjanya
Cara kerjanya
Definisikan variabel keputusan x (misalnya, kuantitas produksi, jumlah aliran), fungsi tujuan c^T x untuk diminimalkan atau dimaksimalkan, dan himpunan kendala Ax <= b dengan x >= 0. Semua koefisien dalam c, A, dan b diperlakukan sebagai konstanta yang tepat dan diketahui — inilah yang membuat model menjadi deterministik. Tulis LP bentuk standar: min c^T x tunduk pada Ax = b, x >= 0.
Rumus
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0Sebelum mengoptimalkan, verifikasi bahwa daerah layak tidak kosong (himpunan kendala memiliki setidaknya satu solusi) dan bahwa tujuan terbatas. Jika daerah layak kosong, masalahnya tidak layak (infeasible); jika tujuan tidak terbatas, model salah spesifikasi. Pemeriksaan ini dilakukan secara otomatis oleh pemecah tetapi harus ditafsirkan oleh analis untuk menangkap kesalahan formulasi.
Selesaikan LP menggunakan algoritma Simplex (melakukan pivot di sepanjang tepi politop cembung menuju verteks optimum) atau metode titik interior (mengikuti jalur melalui interior daerah layak). Kedua pendekatan memanfaatkan kecembungan himpunan layak dan linearitas tujuan, menjamin bahwa setiap optimum lokal adalah optimum global. Pemecah modern (CPLEX, Gurobi, HiGHS) menangani jutaan variabel dan kendala secara efisien.
Pemecah mengembalikan vektor keputusan optimal x* dan nilai tujuan optimal c^T x*. Karena daerah layak adalah politop cembung dan tujuan adalah linear, optimum selalu tercapai pada verteks (solusi layak dasar). Catat x* dan verifikasi bahwa ia memenuhi semua kendala, lalu terjemahkan kembali ke dalam istilah manajerial (misalnya, unit yang akan diproduksi, rute yang akan digunakan).
Rumus
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}Setelah mendapatkan x*, lakukan analisis sensitivitas (pasca-optimalitas) untuk menentukan seberapa besar setiap koefisien dalam c atau b dapat berubah sebelum basis saat ini — dan dengan demikian solusi optimal — berubah. Harga bayangan (variabel dual) mengukur nilai marjinal dari pelonggaran setiap kendala. Meskipun modelnya deterministik, analisis sensitivitas mengungkapkan ketahanan solusi terhadap kesalahan estimasi parameter tanpa meninggalkan kerangka kerja deterministik.
Kesalahan umum
- Memperlakukan parameter yang tidak pasti sebagai estimasi titik tetap tanpa analisis sensitivitas selanjutnya dapat menghasilkan solusi yang optimal di atas kertas tetapi rapuh dalam praktik.
- Melupakan untuk memasukkan kendala non-negativitas atau batas logis dapat menghasilkan solusi yang optimal secara matematis tetapi tidak layak secara operasional (misalnya, kuantitas produksi negatif).
- Salah menafsirkan harga bayangan sebagai nilai marjinal yang dijamin di luar rentang validitas yang diidentifikasi dalam analisis rentang.
- Menggunakan DLP ketika masalah sebenarnya memiliki struktur integer (misalnya, jumlah truk) dan membulatkan solusi LP — ini dapat melanggar kendala atau melewatkan optimum yang sebenarnya.
- Mengagregasi tujuan secara berlebihan menjadi satu jumlah tertimbang tanpa memvalidasi bahwa bobot secara akurat mencerminkan preferensi pemangku kepentingan, menyembunyikan trade-off penting.
Pertanyaan yang sering diajukan
Apa yang membuat LP 'deterministik' berbeda dari 'stokastik'?
Dalam LP deterministik, setiap koefisien dalam fungsi tujuan, matriks kendala, dan vektor sisi kanan adalah konstanta yang diketahui. Sebaliknya, LP Stokastik memperlakukan beberapa atau semua koefisien ini sebagai variabel acak dengan distribusi probabilitas, mencari solusi yang berkinerja baik dalam ekspektasi atau dengan probabilitas tinggi di berbagai skenario.
Apakah algoritma simplex selalu efisien?
Dalam praktik, ya — metode Simplex menyelesaikan hampir semua LP dunia nyata dengan sangat cepat. Secara teoritis, metode ini dapat memakan waktu eksponensial dalam kasus terburuk (contoh Klee–Minty), tetapi metode titik interior (misalnya, algoritma Karmarkar) berjalan dalam waktu polinomial dan kompetitif untuk instans yang sangat besar.
Bisakah saya menggunakan DLP jika beberapa variabel keputusan saya harus berupa bilangan bulat?
Tidak. Jika variabel harus integer (misalnya, jumlah mesin yang akan dibeli), model tersebut menjadi program campuran integer atau integer murni. Menyelesaikan relaksasi LP dan membulatkan dapat melanggar kendala atau melewatkan optimum integer yang sebenarnya; gunakan pemecah MIP khusus sebagai gantinya.
Bagaimana harga bayangan membantu setelah penyelesaian?
Harga bayangan (variabel dual) dari suatu kendala memberi tahu Anda seberapa besar nilai tujuan akan meningkat jika sisi kanan kendala tersebut dilonggarkan sebesar satu unit, dalam interval rentang yang valid. Ini memandu keputusan tentang di mana harus berinvestasi untuk memperluas kapasitas yang paling hemat biaya.
Kapan saya harus meningkatkan dari DLP ke LP Robust atau Stokastik?
Tingkatkan ketika ketidakpastian parameter tidak sepele dan biaya solusi yang tidak layak atau buruk di bawah nilai parameter yang terealisasi signifikan. Jika penyimpangan 10–20% pada koefisien kunci akan mengubah solusi yang disukai atau menyebabkan pelanggaran kendala, asumsi kepastian LP deterministik terlalu kuat.
Metode terkait
Sumber
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press, Princeton, NJ.
ISBN: 9780691059136Disalin.Linear programming. Wikipedia.
Buka referensi publikasiDisalin.