Pemrograman Linear — Mengoptimalkan Objektif Linear di Bawah Kendala Linear
- Diperkenalkan oleh
- George B. Dantzig
- Tahun
- 1947
- Jenis
- Mathematical programming / continuous optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman linear (LP), yang dipelopori oleh George B. Dantzig pada tahun 1947, adalah metode matematis untuk menemukan nilai terbaik dari fungsi objektif linear — seperti biaya minimum atau laba maksimum — yang tunduk pada serangkaian kendala ketidaksetaraan dan kesetaraan linear.
Ini adalah teknik dasar dalam riset operasi dan mendasari perencanaan produksi, alokasi sumber daya, logistik, masalah diet, dan berbagai skenario pengambilan keputusan lainnya di bidang teknik, ekonomi, dan ilmu alam.
Intuisi di balik metode
Bayangkan Anda menjalankan pabrik kecil yang memproduksi dua produk. Setiap produk memberi Anda keuntungan tertentu, tetapi pembuatannya mengonsumsi bahan baku dan waktu mesin yang terbatas. Pemrograman linear menemukan campuran produk yang tepat yang menghasilkan keuntungan paling besar dari sumber daya tetap Anda — tanpa melanggar batas fisik atau kontrak apa pun. Bagian 'linear' berarti keuntungan dan konsumsi sumber daya berskala dalam hubungan garis lurus dengan kuantitas yang Anda hasilkan. Pilihan yang layak membentuk poligon (dalam dua dimensi) atau polihedron (dalam dimensi yang lebih tinggi), dan jawaban optimal selalu berada di salah satu sudutnya.
Sejarah
Pengembangan sistematis pemrograman linear dimulai pada tahun 1947 ketika George B. Dantzig, yang bekerja untuk Angkatan Udara AS, menemukan algoritma Simplex untuk mengotomatiskan perencanaan logistik militer. Dantzig menerbitkan teori dasar dalam monografnya tahun 1963, yang tetap menjadi referensi kanonik. Pekerjaan independen dan paralel oleh Leonid Kantorovich di Uni Soviet (1939) membahas perencanaan produksi menggunakan ide-ide matematika yang serupa, dan Kantorovich dianugerahi Hadiah Nobel Ekonomi pada tahun 1975 sebagian atas kontribusinya ini. Pertanyaan teoretis tentang kelayakan waktu polinomial diselesaikan oleh metode elipsoid Khachian (1979) dan kemudian oleh metode titik interior Karmarkar (1984), yang terbukti cepat secara praktis untuk masalah skala besar. Saat ini, pemecah LP komersial dan sumber terbuka tertanam dalam perencanaan sumber daya perusahaan, penjadwalan maskapai, dan sistem energi di seluruh dunia.
Kapan digunakan
Pemrograman linear sesuai kapan pun Anda perlu mengoptimalkan kuantitas yang bergantung secara linear pada sekumpulan variabel keputusan, dan semua kendala juga linear. Ini tidak memerlukan asumsi distribusi dan tidak ada ukuran sampel minimum — ini adalah model matematika deterministik, bukan estimator statistik. Metode ini berlaku ketika variabel keputusan kontinu (nilai pecahan bermakna); jika variabel harus berupa bilangan bulat atau biner, pemrograman integer diperlukan sebagai gantinya. LP banyak digunakan dalam penjadwalan produksi, logistik rantai pasokan, masalah diet dan pencampuran, optimasi portofolio keuangan, masalah transportasi dan penugasan, serta pengiriman energi.
Batasan dan pertimbangan
- Persyaratan linearitas: jika objektif atau kendala apa pun bersifat non-linear, model LP salah spesifikasi dan solusinya mungkin salah atau tidak layak.
- Variabel kontinu saja: ketika variabel keputusan harus mengambil nilai integer atau biner, relaksasi LP memberikan batas bawah tetapi bukan solusi yang valid; pemrograman integer harus digunakan.
- Deterministik: LP tidak memodelkan ketidakpastian dalam parameter; pemrograman stokastik atau optimasi robust diperlukan ketika data tidak pasti.
- Degenerasi dan siklus: dalam kasus yang jarang terjadi, metode Simplex dapat berputar di antara basis degeneratif tanpa konvergensi, meskipun aturan anti-siklus (misalnya, aturan Bland) menyelesaikannya.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Optimum global terjamin: karena wilayah layak adalah polihedron cembung, setiap optimum lokal juga merupakan optimum global, tanpa risiko terjebak dalam solusi sub-optimal.
- Sangat terukur: pemecah modern (HiGHS, Gurobi, CPLEX) menangani model dengan jutaan variabel dan kendala dalam hitungan detik.
- Informasi pasca-solusi yang kaya: harga bayangan dan rentang sensitivitas memberikan wawasan yang dapat ditindaklanjuti tentang nilai sumber daya dan ketahanan solusi tanpa menjalankan tambahan.
- Tidak ada asumsi distribusi: LP adalah model aljabar murni, sehingga tidak memerlukan normalitas atau properti statistik data apa pun.
Penerapan
- Perencanaan produksi: menemukan bauran produk optimal yang memaksimalkan laba sambil menghormati kapasitas mesin dan batas bahan baku.
- Logistik rantai pasokan dan transportasi: meminimalkan biaya pengiriman di seluruh jaringan gudang dan pelanggan.
- Masalah diet dan pencampuran: memilih kuantitas bahan yang memenuhi persyaratan nutrisi dengan biaya minimum.
- Optimasi portofolio keuangan: mengalokasikan modal di berbagai aset untuk memaksimalkan pengembalian yang diharapkan dengan tunduk pada kendala risiko dan peraturan.
- Pengiriman energi dan penjadwalan jaringan listrik: meminimalkan biaya bahan bakar sambil memenuhi permintaan listrik dan batas kapasitas generator.
- Penjadwalan staf dan tenaga kerja: menugaskan giliran kerja kepada pekerja untuk memenuhi permintaan dengan biaya tenaga kerja minimum.
Cara kerjanya
Cara kerjanya
Masalah keputusan dunia nyata diterjemahkan ke dalam simbol matematika. Anda mengidentifikasi variabel keputusan (kuantitas yang dapat Anda kendalikan), menulis fungsi objektif (apa yang ingin Anda maksimalkan atau minimalkan) sebagai kombinasi linear dari variabel-variabel tersebut, dan menulis setiap kendala — batas sumber daya, kapasitas maksimum, persyaratan permintaan — sebagai ketidaksetaraan atau kesetaraan linear. LP yang terstruktur dengan baik memiliki tujuan yang jelas, batas variabel yang eksplisit, dan setiap kendala struktural yang diekspresikan secara linear.
Model dibawa ke dalam bentuk kanonik atau standar yang dapat diproses oleh pemecah (solver). Ketidaksetaraan diubah menjadi kesetaraan dengan memperkenalkan variabel slack atau surplus non-negatif, dan variabel apa pun yang tidak dibatasi diganti dengan selisih dua variabel non-negatif. Langkah mekanis ini menghasilkan representasi tableau atau matriks yang digunakan algoritma, dan tidak mengubah masalah — hanya membentuk ulang untuk komputasi.
Pemecah mencari polihedron yang layak untuk sudut optimal. Metode Simplex klasik berputar dari simpul ke simpul di sepanjang tepi polihedron, selalu meningkatkan (atau mempertahankan) objektif, sampai tidak ada tetangga yang lebih baik. Metode titik interior (penghalang) malah bergerak melalui interior wilayah layak di sepanjang jalur pusat, yang sangat efisien untuk model yang sangat besar. Kedua keluarga dijamin menemukan optimum global ketika ada, karena wilayah layak adalah cembung.
Pemecah mengembalikan nilai optimal variabel keputusan dan nilai objektif optimal, bersama dengan variabel dual (harga bayangan) dan rentang sensitivitas. Harga bayangan mengukur seberapa besar objektif akan meningkat jika kendala yang mengikat dilonggarkan sebesar satu unit — secara langsung memberi tahu pengambil keputusan di mana sumber daya tambahan akan paling berharga. Analisis sensitivitas mengidentifikasi seberapa besar koefisien biaya atau nilai sisi kanan dapat berubah sebelum basis saat ini tidak lagi optimal.
Kesalahan umum
- Menerapkan LP ketika kendala atau objektif bersifat non-linear — solusi akan salah atau pemecah akan menolak model.
- Mengabaikan persyaratan integritas: membulatkan solusi LP kontinu ke bilangan bulat umumnya tidak menghasilkan solusi integer yang layak atau optimal; gunakan pemrograman integer sebagai gantinya.
- Model tidak layak atau tidak terbatas: jika wilayah layak kosong (kendala bertentangan) atau objektif tidak terbatas (kendala batas hilang), pemecah akan melaporkan kegagalan — selalu periksa struktur model sebelum menjalankan.
- Memperlakukan keluaran LP sebagai rekomendasi tanpa analisis sensitivitas: solusi yang secara teknis optimal mungkin berada di tepi yang sangat tipis di mana perubahan kecil pada data membalikkan rekomendasi — rentang sensitivitas harus selalu diperiksa.
Pertanyaan yang sering diajukan
Apa yang membuat suatu masalah 'linear' untuk keperluan LP?
Baik fungsi objektif maupun setiap kendala harus linear — artinya setiap suku adalah konstanta yang dikalikan dengan satu variabel keputusan, tanpa perkalian antar variabel, tanpa eksponen, dan tanpa fungsi non-linear. Jika bahkan satu kendala atau objektif melibatkan, katakanlah, x dikalikan y atau x kuadrat, LP standar tidak berlaku lagi dan pemecah pemrograman non-linear atau kuadratik diperlukan.
Mengapa solusi optimal selalu terletak di sudut wilayah layak?
Wilayah layak yang didefinisikan oleh kendala linear adalah polihedron (atau politop) cembung. Fungsi objektif linear itu sendiri linear, sehingga tidak dapat 'ditarik' ke arah interior himpunan cembung — ia selalu mencapai nilai ekstremnya di batas, dan khususnya di simpul (titik sudut). Ini adalah wawasan geometris yang mendasari strategi Simplex dari simpul ke simpul.
Kapan saya harus menggunakan pemrograman integer sebagai ganti LP?
Kapan pun satu atau lebih variabel keputusan harus mengambil nilai integer atau biner (0/1) — misalnya, apakah akan membuka fasilitas (ya/tidak), berapa banyak truk yang akan dikirim (bilangan bulat), atau item mana yang akan dimasukkan dalam pilihan. Cukup menyelesaikan LP dan membulatkan solusi kontinu tidak dapat diandalkan: solusi yang dibulatkan bisa tidak layak atau jauh dari optimal. Pemrograman integer menangani integritas dengan benar, dengan biaya komputasi yang lebih besar.
Apa yang diberitahukan oleh harga bayangan kepada saya?
Harga bayangan (variabel dual) untuk kendala yang mengikat menunjukkan seberapa besar nilai objektif optimal akan meningkat jika sisi kanan kendala tersebut dilonggarkan sebesar satu unit, dengan menjaga semua hal lain tetap konstan. Misalnya, harga bayangan 3 pada kendala jam kerja berarti bahwa menambahkan satu jam kerja lagi akan meningkatkan objektif sebesar 3 unit. Kendala yang tidak mengikat memiliki harga bayangan nol — mereka tidak membatasi optimum saat ini.
Metode terkait
Sumber
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
ISBN: 9780691059136Disalin.Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.
Buka referensi DOIDisalin.