Metode Simpleks
- Diperkenalkan oleh
- George Dantzig
- Tahun
- 1947
- Jenis
- algorithm
- Keluarga
- Optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Metode Simpleks, yang dikembangkan oleh George Dantzig pada tahun 1947, adalah algoritma fundamental untuk menyelesaikan masalah pemrograman linear.
Metode ini secara sistematis menjelajahi titik-titik sudut (verteks) dari daerah layak untuk menemukan solusi optimal di mana fungsi tujuan dimaksimalkan atau diminimalkan dengan batasan-batasan linear.
Intuisi di balik metode
Metode ini bekerja dengan memulai dari titik sudut (verteks) dari daerah layak yang didefinisikan oleh batasan-batasan linear, kemudian bergerak ke verteks yang berdekatan yang meningkatkan nilai fungsi tujuan. Proses ini berlanjut hingga mencapai verteks di mana tidak ada verteks yang berdekatan menawarkan peningkatan lebih lanjut, menjamin optimalitas. Algoritma ini memanfaatkan sifat geometris bahwa program linear memiliki solusi optimalnya pada verteks-verteks politop batasan.
Sejarah
George Dantzig memperkenalkan metode simpleks pada tahun 1947, merevolusi riset operasi dan menjadi algoritma standar untuk pemrograman linear selama beberapa dekade. Klee dan Minty (1972) menunjukkan kompleksitas eksponensial kasus terburuk, namun secara empiris metode ini tetap cepat. Tahun 1980-an menyaksikan pengembangan metode titik interior sebagai alternatif, tetapi metode simpleks tetap dominan untuk banyak aplikasi praktis karena ketahanan dan kecanggihan implementasi modernnya.
Kapan digunakan
Terapkan metode simpleks saat menyelesaikan masalah pemrograman linear dengan daerah layak terbatas dan fungsi tujuan linear. Metode ini sangat efektif untuk masalah dengan ratusan atau ribuan variabel dan batasan. Hindari menggunakannya jika masalahnya non-linear atau tidak terbatas. Metode titik interior mungkin lebih disukai untuk masalah berskala sangat besar.
Batasan dan pertimbangan
- Kompleksitas waktu kasus terburuk eksponensial (meskipun jarang dalam praktik)
- Dapat berkinerja buruk pada masalah yang sangat degeneratif
- Kurang kompetitif dibandingkan metode titik interior pada masalah berskala sangat besar
- Membutuhkan masalah dalam bentuk standar dengan penanganan batasan eksplisit
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Dijamin menemukan solusi optimal dalam waktu terbatas untuk program linear
- Efisien dalam praktik dengan implementasi yang cermat dan penanganan degenerasi
- Diimplementasikan secara luas dan didukung oleh pustaka optimasi yang matang
- Dasar untuk memahami algoritma optimasi yang lebih canggih
Penerapan
- Perencanaan produksi: mengoptimalkan kuantitas produksi untuk meminimalkan biaya sambil memenuhi batasan permintaan
- Transportasi dan logistik: menentukan rute dan kuantitas pengiriman optimal antara gudang dan pusat distribusi
- Optimasi portofolio: mengalokasikan modal di berbagai aset untuk memaksimalkan keuntungan dengan batasan risiko dan anggaran
- Alokasi sumber daya: mendistribusikan sumber daya terbatas seperti tenaga kerja dan bahan baku untuk memaksimalkan output organisasi
- Masalah pencampuran: mencampur bahan baku dalam proporsi optimal untuk memenuhi spesifikasi kualitas dan meminimalkan biaya
- Penjadwalan tenaga kerja: menugaskan pekerja ke shift untuk meminimalkan biaya tenaga kerja sambil memenuhi permintaan
Cara kerjanya
Cara kerjanya
Ubah program linear ke bentuk standar dengan variabel slack, dan identifikasi solusi basis layak awal (biasanya titik asal jika layak).
Lakukan operasi pivot pada tabel simpleks: pilih variabel masuk dengan biaya tereduksi negatif, identifikasi variabel keluar dengan uji rasio minimum, dan perbarui basis.
Periksa kondisi optimalitas menggunakan biaya tereduksi; jika semua biaya tereduksi non-negatif untuk maksimisasi, solusi saat ini optimal; jika tidak, kembali ke langkah pivot.
Kesalahan umum
- Gagal menangani siklus dengan benar saat menghadapi basis degeneratif (gunakan aturan Bland atau metode perturbasi)
- Pemilihan pivot yang salah atau kesalahan aritmatika dalam pembaruan tabel yang menyebabkan ketidakstabilan numerik
- Tidak memeriksa ketidakterbatasan atau ketidaklayakan sebelum memulai algoritma
Pertanyaan yang sering diajukan
Mengapa metode simpleks disebut 'simpleks'?
Istilah 'simpleks' mengacu pada bentuk paling sederhana dari politop dalam dimensi tertentu. Algoritma ini bekerja dengan bergerak di sepanjang tepi dan verteks politop yang didefinisikan oleh batasan-batasan.
Apa perbedaan antara metode simpleks dan metode titik interior?
Metode simpleks tetap berada di batas daerah layak pada verteks, sedangkan metode titik interior melintasi bagian dalam. Metode titik interior memiliki kompleksitas kasus terburuk yang lebih baik, tetapi simpleks seringkali lebih cepat dalam praktik untuk masalah berukuran sedang.
Bagaimana cara menangani ketidaklayakan atau ketidakterbatasan?
Gunakan metode simpleks dua fase: fase satu menyelesaikan masalah bantu untuk menemukan solusi basis layak atau menentukan ketidaklayakan; fase dua menerapkan metode simpleks standar ke masalah asli.
Apa itu degenerasi dan mengapa itu penting?
Degenerasi terjadi ketika solusi basis layak memiliki lebih dari satu representasi basis, yang dapat menyebabkan siklus. Tangani dengan menggunakan aturan Bland (pilih variabel berdasarkan urutan indeks) atau metode perturbasi.
Metode terkait
Sumber
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
Buka referensi DOIDisalin.Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.
Buka referensi DOIDisalin.