PROGRAM linear (LP) adalah alat analisis yang digunakan untuk mengoptimalkan fungsi linear dengan variabel non-negatif yang dibatasi oleh pertidaksamaan atau persamaan linear. Istilah “linear” mengacu pada hubungan proporsional antarfaktor dalam model, di mana perubahan satu faktor akan mengakibatkan perubahan faktor lain secara linier (Mas’ud & Halim, 2023). Dalam konteks riset operasi, LP telah banyak diterapkan di berbagai bidang untuk membantu pengambilan keputusan yang optimal, mulai dari optimasi produksi, manajemen rantai pasok, perencanaan keuangan, hingga penjadwalan tenaga kerja.
Metode simplex merupakan algoritma yang dikembangkan oleh George Dantzig pada tahun 1947 dan hingga kini masih menjadi salah satu metode paling efektif untuk menyelesaikan permasalahan LP. Dalam dunia bisnis, setiap pelaku usaha dihadapkan pada masalah optimasi yang meliputi meminimumkan biaya atau memaksimumkan keuntungan dengan mempertimbangkan berbagai kendala, seperti keterbatasan kapasitas sumber daya yang tersedia (Tamiza, 2023). Metode simplex unggul dalam kemampuannya menyelesaikan permasalahan LP dengan dua atau lebih variabel keputusan, tidak seperti metode grafik yang terbatas hanya pada dua variabel (Jurnal Manajemen UNMUL, 2021).
Kasus Minimasi dalam Program Linear
Permasalahan minimasi dalam program linear pada umumnya berkaitan dengan upaya menekan biaya-biaya yang berkaitan dengan produksi, distribusi, atau operasional. Secara matematis, fungsi tujuan minimasi dinyatakan sebagai Min Z = c₁X₁ + c₂X₂ + … + cₙXₙ, di mana cᵢ adalah koefisien biaya per unit dari variabel keputusan Xᵢ. Permasalahan minimasi sering kali disertai oleh fungsi batasan bertanda ≥, yang menyatakan bahwa kebutuhan atau standar minimum tertentu harus dipenuhi. Kondisi inilah yang menjadi pembeda utama antara kasus minimasi dan maksimasi dalam penerapan metode simplex.
Metode Big-M dalam Penanganan Variabel Artifisial
Metode Big-M (atau dikenal juga sebagai Metode Penalti) merupakan teknik yang dikembangkan untuk mengatasi masalah solusi basis awal yang tidak fisibel dalam metode simplex. Metode ini bekerja dengan menambahkan variabel artifisial ke dalam setiap batasan yang tidak memiliki variabel slack awal yang bernilai positif, seperti batasan bertanda ≥ dan =. Variabel artifisial ini kemudian diberikan koefisien penalti yang sangat besar (M) di dalam fungsi tujuan, sehingga proses optimasi akan secara otomatis mendorong variabel artifisial keluar dari solusi basis (Fadhilah, Prihandono, & Yudhi, 2023).
Algoritma Metode Simplex untuk Fungsi Tujuan Minimum (Fungsi Batasan ≥)
Prinsip Dasar Transformasi
Penyelesaian permasalahan minimasi dengan fungsi batasan ≥ menggunakan metode simplex diawali dengan serangkaian transformasi aljabar untuk mengubah model program linear ke dalam bentuk standar yang dapat diolah oleh tabel simplex. Proses transformasi ini berbeda dari kasus maksimasi dengan fungsi batasan ≤ karena memerlukan beberapa tahapan tambahan yang harus dilakukan dengan urutan yang tepat.
Langkah pertama adalah mengidentifikasi fungsi tujuan dan semua variabel keputusan, lalu memformulasikannya dalam simbol matematis yang jelas. Selanjutnya, setiap fungsi batasan bertanda ≥ harus diubah ke dalam bentuk ≤ terlebih dahulu, yang dilakukan dengan cara mengalikan seluruh suku dalam persamaan tersebut dengan (−1). Akibat perkalian ini, seluruh koefisien variabel berubah tanda dan nilai sisi kanan (RHS) menjadi negatif. Untuk mengeliminasi tanda negatif pada RHS, persamaan dikali lagi dengan (−1) dan ditambahkan sebuah variabel artifisial dengan koefisien M yang sangat besar dalam fungsi tujuan (Mas’ud & Halim, 2023; Fadhilah, Prihandono, & Yudhi, 2023).
Penerapan: Contoh Kasus Numerik
Contoh Kasus
Diberikan permasalahan program linear sebagai berikut:
Fungsi Tujuan: Min Z = 8X₁ + 10X₂
Fungsi Batasan: 3X₁ ≤ 10
4X₁ + 6X₂ ≥ 15
Langkah 1 – Transformasi
Model ini mengandung satu batasan ≤ dan satu batasan ≥. Batasan pertama cukup ditambahkan variabel slack S₁, sedangkan batasan kedua memerlukan pengurangan variabel surplus S₂ dan penambahan variabel artifisial S₃ dengan koefisien penalti M. Setelah transformasi, persamaan yang terbentuk adalah:
-Z + 8X₁ + 10X₂ + MS₃ = 0
3X₁ + S₁ = 10
4X₁ + 6X₂ – S₂ + S₃ = 15
Langkah 2 – Iterasi dan Solusi Optimal
Pada tabel simplex awal, kolom kunci adalah kolom X₂ karena memiliki koefisien (10 − 6M) dengan nilai M paling besar. Nilai indeks baris S₁ adalah tak hingga (karena koefisien X₂ pada baris ini nol), sedangkan baris S₃ menghasilkan indeks 15/6 = 2,5. Dengan demikian, baris S₃ menjadi baris kunci dan X₂ menggantikan S₃ sebagai variabel dasar. Setelah satu iterasi transformasi, diperoleh nilai pada baris NKj − Zj yang seluruhnya tidak ada yang bernilai positif di depan konstanta M. Proses iterasi dinyatakan selesai.
Kesimpulan
Metode simplex merupakan alat yang powerful dan sistematis untuk menyelesaikan permasalahan program linear, termasuk kasus minimasi fungsi tujuan dengan fungsi batasan bertanda ≥. Kunci keberhasilan penerapan metode ini terletak pada pemahaman yang benar tentang tahapan transformasi model, mulai dari pengubahan tanda pertidaksamaan, penambahan variabel slack, pengurangan variabel surplus, hingga penambahan variabel artifisial melalui pendekatan Metode Big-M.
Algoritma yang terdiri dari sepuluh tahapan yang telah diuraikan dalam artikel ini memberikan panduan yang komprehensif dan terstruktur bagi mahasiswa dan praktisi. Dua contoh kasus numerik yang disajikan secara lengkap dan detail memperlihatkan bahwa metode simplex mampu menghasilkan solusi optimal yang tepat melalui proses iterasi yang terkontrol dan logis.
Penulis:
Diana Fadilla Anwar
Dwi Firli Intiani
Dosen Pengampu: Chandra Fitra Arifianto S.Psi., MM
Mahasiswa Program Studi Manajemen Fakultas Ekonomi dan Bisnis Universitas Pamulang
