Pengantar Program Linear
Program Linear (Linear Programming LP) adalah metode matematika yang digunakan untuk menemukan nilai optimal (maksimum atau minimum) dari sebuah fungsi tujuan dengan syaratsyarat berupa pertidaksamaan linear. LP banyak diterapkan dalam bidang logistik, manufaktur, keuangan, transportasi, dan perencanaan produksi.
Elemenelemen Utama
- Fungsi Tujuan: Persamaan linear yang ingin dioptimalkan, misalnya profit total atau biaya total.
- Variabel Keputusan: Nilainilai yang belum diketahui dan harus dicari, biasanya mewakili kuantitas produksi, alokasi sumber daya, dsb.
- Kendala: Persamaan atau pertidaksamaan linear yang membatasi nilai variabel keputusan, misalnya kapasitas mesin atau batas bahan baku.
- Batasan NonNegatif: Kebanyakan model LP mengharuskan semua variabel keputusan 0.
Formulasi Umum
Model umum LP dapat dituliskan dalam bentuk standar:
Maksimalkan z = cx + cx + + cx dengan syarat ax + ax + + ax b ax + ax + + ax b ax + ax + + ax b x, x, , x 0
Jika fungsi tujuan ingin diminimalkan, tanda Maksimalkan diganti menjadi Minimalkan. Model di atas dapat juga ditulis dalam bentuk matriks cx, Ax b, x 0.
Metode Penyelesaian
Berbagai algoritma telah dikembangkan untuk menyelesaikan masalah LP, di antaranya:
- Metode Simpleks: Algoritma iteratif yang bergerak dari satu titik ekstrem ke titik ekstrem lain pada bidang feasible sampai menemukan optimum.
- Metode Titik Dalam (InteriorPoint): Menyusuri interior daerah feasible dan biasanya lebih efisien pada masalah berukuran sangat besar.
- Dual Simpleks: Menyelesaikan masalah dual sekaligus, berguna ketika jumlah kendala jauh lebih banyak daripada variabel.
Software populer seperti IBM CPLEX, Gurobi, serta pustaka opensource COINOR CLP dan SciPy menyediakan implementasi algoritmaalgoritma ini.
Konstruksi Model: Contoh Kasus Produksi
Misalkan sebuah pabrik menghasilkan dua produk, A dan B. Setiap unit A membutuhkan 2 jam mesin dan 3 jam tenaga kerja, sementara tiap unit B membutuhkan 1 jam mesin dan 2 jam tenaga kerja. Kapasitas harian mesin adalah 100 jam dan tenaga kerja 120 jam. Profit per unit A adalah Rp40.000, dan per unit B Rp30.000. Model LP-nya:
Maksimalkan Z = 40.000x + 30.000x dengan syarat 2x + 1x 100 (mesin) 3x + 2x 120 (tenaga kerja) x, x 0
Solusi optimal (dihitung dengan metode simpleks) menghasilkan x = 20 unit, x = 60 unit dengan profit maksimum Rp2.800.000.
Masalah Dualitas
Setiap LP memiliki masalah dual yang memberikan batas atas (untuk maksimisasi) atau batas bawah (untuk minimisasi) nilai fungsi tujuan. Pada contoh di atas, masalah dualnya adalah:
Minimalkan W = 100y + 120y dengan syarat 2y + 3y 40.000 (koefisien x) 1y + 2y 30.000 (koefisien x) y, y 0
Jika nilai optimal dual sama dengan nilai optimal primal, maka keduanya saling melengkapi (teorema dualitas kuat).
Aplikasi Lainnya
- Transportasi: Menentukan rute pengiriman barang dengan biaya minimal.
- Penjadwalan: Mengalokasikan mesin atau karyawan pada shift yang optimal.
- Keuangan: Memilih portofolio optimal dengan batas risiko.
- Energi: Menyeimbangkan produksi dan konsumsi listrik dalam jaringan.
Keterbatasan dan Perluasan
LP hanya berlaku bila semua hubungan bersifat linear. Jika terdapat hubungan nonlinear, integer, atau stokastik, maka diperlukan metode lain seperti Program Linear Integer (ILP), Program NonLinear (NLP), atau Stochastic Programming.
Ringkasan
Program Linear adalah alat kuat yang memungkinkan pengambilan keputusan optimal dengan cara matematika yang terstruktur. Dengan memahami unsurunsurnyafungsi tujuan, variabel keputusan, kendala, dan batas nonnegatifserta metode penyelesaian yang tersedia, siapa pun dapat memodelkan dan menyelesaikan masalah nyata yang melibatkan alokasi sumber daya terbatas. Implementasi komersial maupun opensource membuat LP dapat diakses oleh semua kalangan, menjadikannya salah satu teknik paling penting dalam operasi riset dan manajemen.
