Metode Simpleks Rangkuman

METODE SIMPLEKS

Metode simpleks adalah suatu metode yang secara sistematis penyelesaian pemrograman linear dimulai dari suatu penyelesaian basis yang fisibel ke penyelesaian dasar fisibel lainnya, yang dilakukan berulang-ulang (iteratif) sehingga tercapai suatu penyelesaian optimum.

Pemograman Linier Menggunakan Metode Simpleks

Langkah-langkah awal sebelum menggunakan metode simpleks :

1. Mengonversi pertidaksamaan (≤ atau ≥) menjadi persamaan

Untuk mengonversi pertidaksamaan (≤) menjadi persamaan, sebuah variabel slack nonnegative ditambahkan pada sisi kiri constraint. Misalnya pada kasus Reddy Mikks, constraint yang menyatakan penggunakan bahan baku M1 diberikan oleh :

6x₁ + 4x₂ ≤ 24

Definisikan s₁ sebagai variabel slack dari M1, maka constraint dapat dikonversi menjadi :

6x₁ + 4x₂ + s₁ = 24, s₁ ≥ 0

Selanjutnya, untuk constraint dengan tanda ≥, menyatakan batas terendah aktivitas model program linear, sehingga jumlah yang dinyatakan disisi kiri melewati batas minimal yang direpresentasikan sebagai surplus. Konversi dari ≥ ke = dicapai dengan mengurangi dengan variabel surplus non negatif dari sisi kiri pertidaksamaan. Misalnya, dalam kasus Ozark Farm, constraint yang menyatakan kebutuhan makanan :

x₁ + x₂ ≥ 800

Definisikan r₁ sebagai variabel surplus, constraint dapat dikonversi menjadi persamaan berikut :

x₁ + x₂ – r₁ = 800, r₁ ≥ 0

Sedangkan untuk kasus dimana sisi kanan constraint bernilai negatif, maka harus dilakukan perkalian kedua sisi dengan -1 setelah langkah diatas dilakukan. Misalnya constraint :

-x₁ + x₂ ≤ -3

Maka bentuk persamaannya menjadi :

-x₁ + x₂ + r₁ = -3, r₁ ≥ 0

Selanjutnya kedua sisi dikalikan dengan -1, sehingga sisi kanan bernilai positif :

x₁ – x₂ – r₁ = 3

2. Menambahkan variabel slack ke fungsi tujuan dengan koefisien nol

Pada kasus model Reddy Mikks, fungsi tujuan Z = 5x₁ + 4x₂ dengan 4 variabel slack menjadi Z = 5x₁ + 4x₂ + 0s₁ + 0s₂ + 0s₃ + 0s₄.

3. Memindahkan komponen sisi kanan fungsi tujuan ke sisi kanan

Pada kasus model Reddy Mikks, fungsi tujuan Z = 5x₁ + 4x₂ + 0s₁ + 0s₂ + 0s₃ + 0s₄ menjadi Z – 5x₁ – 4x₂ – 0s₁ – 0s₂ – 0s₃ – 0s₄ = 0.

Dalam menyelesaikan kasus pemrograman linier, metode simpleks memberikan langkah-langkah penyelesaian sebagai berikut :

1.       Menentukan awal basis solusi layak

2.       Memilih variabel masuk menggunakan syarat keoptimalan. Berhenti jika tidak ada lagi variabel masuk, solusi terakhir adalah solusi optimal. Jika tidak maka ke langkah 3.

3.       Memilih variabel keluar menggunakan syarat kelayakan.

4.       Menentukan solusi dasar yang baru menggunakan perhitungan Gauss-Jordan. Kembali ke langkah 2.

Syarat keoptimalan (optimality condition). Variabel masuk dalam kasus pemaksimalan (peminimalan) adalah variabel nonbasis yang mempunyai koefisien negatif terbesar (pemaksimalan) atau positif terbesar (peminimalan) dalam baris ­z-row. Syarat optimal dicapai pada iterasi dimana semua koefisien z-row dari variabel nonbasis tidak negatif (pemaksimalan) atau tidak positif (peminimalan)

Syarat kelayakan (feasibility condition). Untuk kedua masalah pemaksimalan dan peminimalan, variabel keluar adalah variabel basis yang dikaitkan dengan rasio non negatif terkecil.

Operasi baris Gauss-Jordan :

1. Menentukan baris kunci :

a.      Gantilah variabel keluar dalam kolom basis dengan variabel masuk

b.      Baris kunci baru = Baris kunci ¸ elemen kunci.

2. Mengganti nilai baris yang lain :

Baris baru = Baris lama – koefisien kolom kunci ´ Baris kunci baru

Variabel basis adalah variabel yang berkontribusi (mempunyai nilai) memberikan solusi yang diminta. Variabel nonbasis adalah variabel yang tidak berkontribusi (bernilai 0) dalam pemberian solusi. Inisialisasi dalam metode simpleks :

1.       x₁, x₂, … adalah variabel non basis

2.       s₁, s₂, … adalah variabel basis

Dalam iterasi metode simpleks, satu persatu variabel slack akan berubah menjadi variabel non basis karena keluar dari solusi dasar (variabel keluar), dan variabel keputusan akan berubah menjadi variabel basis karena masuk ke basis solusi (variabel masuk).