Program Linear: Konsep, Metode, dan Aplikasi

Pengertian Program Linear

Program linear (linear programming) adalah teknik optimasi yang digunakan untuk menemukan nilai maksimum atau minimum dari suatu fungsi linear yang disebut fungsi objektif, dengan memperhatikan serangkaian kendala linear. Karena semua persamaan dan pertidaksamaan bersifat linear, daerah solusi (feasible region) yang terbentuk berupa himpunan konveks di ruang dimensidimensi yang bersesuaian.

Masalah program linear sangat umum dalam bidang ekonomi, rekayasa, transportasi, logistik, dan manajemen produksi. Contohnya termasuk penentuan kombinasi produksi yang menghasilkan keuntungan terbesar, alokasi sumber daya terbatas, atau penjadwalan tugas.

Model Matematika Program Linear

Secara umum, model program linear dapat ditulis dalam bentuk standar:

maksimis   Z = cx + cx +  + cxs.t.       ax + ax +  + ax  b           ax + ax +  + ax  b                            ax + ax +  + ax  b           x, x, , x  0

Di mana:

• Z = fungsi objektif yang ingin dimaksimalkan (atau diminimalkan).
• x, x, , x = variabel keputusan.
• c, c, , c = koefisien keuntungan atau biaya pada fungsi objektif.
• a = koefisien pada kendala kei untuk variabel kej.
• b = sumber daya terbatas pada kendala kei.

Jika tujuan adalah meminimalkan, kata kunci maksimis diganti menjadi minimis. Kendala dapat berupa , , atau =; dalam bentuk standar biasanya semuanya diubah menjadi dengan menambahkan variabel slack atau surplus.

Metode Penyelesaian

Berbagai algoritma telah dikembangkan untuk menyelesaikan program linear, di antaranya:

1. Metode Simpleks

Metode yang paling terkenal, dikembangkan oleh George Dantzig pada tahun 1947. Simpleks bergerak dari satu titik sudut (basic feasible solution) ke titik sudut berikutnya yang meningkatkan nilai fungsi objektif hingga tidak ada peningkatan lagi.

2. Metode InteriorPoint

Algoritma yang masuk ke dalam kelas metode polinomial, pertama kali dipopulerkan oleh Karmarkar (1984). Pendekatan ini memulai pencarian solusi dari dalam daerah feasible dan bergerak menuju optimum secara langsung.

3. Metode Grafik

Cocok untuk masalah dua variabel (2D). Penyelesaian ditentukan dengan menggambar semua kendala pada bidang koordinat, menemukan daerah feasible, dan mengevaluasi fungsi objektif pada titiktitik sudut.

4. Metode Dual

Setiap program linear memiliki program dual yang mencerminkan nilai marginal sumber daya. Menyelesaikan dual dapat memberi wawasan tentang harga bayangan (shadow price) dan sensitivitas.

5. Algoritma BranchandBound

Digunakan bila variabel keputusan harus integer (program linear integer). Algoritma ini memecah ruang solusi menjadi cabangcabang yang lebih kecil dan memotong cabang yang tidak menjanjikan.

Contoh Aplikasi Program Linear

1. Penentuan Campuran Produk

Sebuah pabrik menghasilkan produk A dan B. Setiap unit produk A memberikan keuntungan Rp5000, sedangkan produk B memberikan Rp3000. Kedua produk membutuhkan bahan baku dan jam kerja mesin yang terbatas. Dengan menyusun model linear, manajer dapat memaksimalkan total keuntungan.

2. Masalah Transportasi

Perusahaan logistik ingin mengirim barang dari tiga gudang ke empat pelanggan dengan biaya pengiriman per unit berbedabeda. Tujuannya meminimalkan total biaya pengiriman sambil memenuhi permintaan tiap pelanggan dan batas kapasitas tiap gudang.

3. Penjadwalan Karyawan

Seorang manajer harus menugaskan karyawan ke shift pagi, siang, dan malam. Setiap shift memerlukan jumlah minimum pekerja dan tiap karyawan memiliki preferensi serta batas maksimal jam kerja per minggu. Model linear membantu menemukan penjadwalan yang meminimalkan biaya lembur.

4. Optimasi Rantai Pasok

Perusahaan multinasional mengoptimalkan aliran bahan mentah, produksi, dan distribusi akhir ke pasar global. Dengan program linear, mereka dapat menentukan volume produksi di tiap pabrik serta rute pengiriman yang menghasilkan biaya total terendah.

Langkah-Langkah Menyelesaikan Program Linear

1. Identifikasi variabel keputusan. Tentukan apa yang akan dicari (misalnya, jumlah produk yang akan diproduksi).
2. Tuliskan fungsi objektif. Apakah ingin memaksimalkan keuntungan atau meminimalkan biaya?
3. Formulasikan kendala. Tuliskan semua batasan dalam bentuk persamaan atau pertidaksamaan linear.
4. Ubah ke bentuk standar. Jika ada kendala atau =, ubah menjadi dengan menambahkan variabel slack, surplus, atau artificial.
5. Pilih metode penyelesaian. Untuk dua variabel gunakan metode grafik; untuk kasus lebih besar gunakan simpleks atau software (mis. LINDO, CPLEX, Gurobi, atau paket lp_solve).
6. Implementasi dan pemecahan. Masukkan koefisien ke dalam tabel simpleks atau ke dalam program komputer.
7. Interpretasi hasil. Nilai optimal dari variabel keputusan dan nilai fungsi objektif memberikan keputusan praktis. Periksa nilai variabel slack untuk mengetahui kendala yang tidak aktif.
8. Analisis sensitivitas. Evaluasi bagaimana perubahan pada koefisien c atau b memengaruhi solusi optimal.

Kesimpulan

Program linear merupakan alat yang sangat kuat untuk memecahkan masalah optimasi yang melibatkan sumber daya terbatas. Dengan memodelkan situasi nyata menjadi fungsi objektif linear dan kendala linear, manajer, insinyur, dan analis dapat membuat keputusan yang berdasarkan perhitungan matematis yang jelas. Berbagai metode, mulai dari simpleks tradisional hingga algoritma interiorpoint modern, memberikan fleksibilitas dalam menangani ukuran dan kompleksitas masalah. Penggunaan software khusus semakin mempermudah implementasi, sementara pemahaman konsep dasar tetap penting untuk interpretasi hasil dan analisis sensitivitas.