Metode Simpleks Solusi Tak Terbatas

𝕸𝖆𝖘 𝕬𝖓𝖉𝖞 𝕯𝖎𝖌𝖎𝖙𝖆𝖑 𝕸𝖊𝖉𝖎𝖆

3 min read

·

Apr 17, 2025

35

Share

Resep Lengkap: Metode Simpleks dan Solusi Tak Terbatas

Metode Simpleks adalah algoritma iteratif yang digunakan dalam pemrograman linier untuk menemukan solusi optimal untuk masalah optimisasi. Namun, tidak semua masalah pemrograman linier memiliki solusi optimal yang tunggal. Beberapa masalah memiliki solusi tak terbatas, di mana terdapat banyak kombinasi variabel yang memenuhi kendala dan menghasilkan nilai fungsi objektif yang sama (atau terus meningkat tanpa batas). Memahami bagaimana mengidentifikasi solusi tak terbatas dalam metode Simpleks sangat penting. Artikel ini akan memberikan panduan lengkap untuk mengidentifikasi dan menginterpretasikan solusi tak terbatas menggunakan metode Simpleks.

Mengenali Solusi Tak Terbatas

Solusi tak terbatas terjadi ketika, selama iterasi metode Simpleks, terdapat variabel non-basis dengan koefisien nol dalam baris objektif (baris z). Ini berarti bahwa kita dapat meningkatkan variabel tersebut tanpa membatasi nilai fungsi objektif. Dengan kata lain, kita dapat menemukan kombinasi solusi yang menghasilkan nilai fungsi objektif yang semakin besar tanpa batas.

Berikut langkah-langkah mengenali solusi tak terbatas:

1. Bentuk Standar: Pastikan masalah pemrograman linier Anda sudah dalam bentuk standar, dengan fungsi objektif yang akan dimaksimalkan (atau diminimalkan) dan semua kendala berbentuk persamaan dengan variabel slack (variabel longgar).

2. Tabel Simpleks: Selesaikan masalah tersebut menggunakan metode Simpleks dan buat tabel Simpleks.

3. Kolom Variabel Non-Basis: Perhatikan baris objektif (baris z). Jika terdapat variabel non-basis dengan koefisien nol pada baris tersebut, dan semua elemen di kolom variabel tersebut tidak negatif, maka solusi tersebut adalah tak terbatas.

4. Interpretasi: Kehadiran variabel non-basis dengan koefisien nol di baris objektif menunjukkan bahwa kita dapat memasukkan variabel tersebut ke dalam basis solusi tanpa mempengaruhi nilai fungsi objektif. Karena semua elemen di kolom tersebut tidak negatif, berarti kita dapat meningkatkan variabel tersebut secara tak terbatas tanpa melanggar kendala. Ini menandakan adanya solusi tak terbatas.

Contoh Kasus: Mengidentifikasi Solusi Tak Terbatas

Mari kita lihat contoh sederhana. Misalkan kita memiliki masalah berikut:

Maksimalkan: Z = x₁ + 2x₂

Terkendala oleh:

• x₁ + x₂ ≤ 4
• 2x₁ + x₂ ≤ 5
• x₁, x₂ ≥ 0

Setelah melakukan iterasi Simpleks, mari asumsikan kita mencapai sebuah tabel Simpleks dengan baris objektif yang menunjukkan koefisien nol untuk variabel x₂ dan semua elemen di kolom x₂ non-negatif. Ini menandakan adanya solusi tak terbatas.

Cara Mengatasi Solusi Tak Terbatas

Jika metode Simpleks menunjukkan solusi tak terbatas, hal ini berarti model pemrograman linier Anda mungkin perlu ditinjau kembali. Beberapa penyebab yang mungkin:

• Kendala yang kurang ketat: Model Anda mungkin memiliki kendala yang terlalu longgar, memungkinkan peningkatan variabel tanpa batas. Periksa kembali formulasi kendala Anda.
• Kesalahan dalam model: Periksa kembali formulasi model Anda, terutama dalam fungsi objektif dan kendala. Pastikan semua variabel dan koefisien telah didefinisikan dengan tepat.
• Data yang salah: Pastikan data input Anda akurat dan konsisten. Kesalahan kecil dalam data dapat menghasilkan solusi yang salah, termasuk solusi tak terbatas.

Kesimpulan

Mengidentifikasi solusi tak terbatas dalam metode Simpleks membutuhkan pemahaman yang baik tentang interpretasi tabel Simpleks. Dengan mengikuti langkah-langkah di atas dan memahami penyebab yang mungkin, Anda dapat mengatasi masalah ini dan mendapatkan model pemrograman linier yang lebih akurat dan representatif. Ingatlah untuk selalu memeriksa dan memvalidasi model Anda untuk memastikan akurasi dan reliabilitas hasilnya.