Metode Simpleks: Contoh Perhitungan Program Linear Lengkap

Metode Simpleks adalah algoritma optimasi untuk menyelesaikan masalah program linear dengan banyak variabel dan kendala. Metode ini bergerak dari satu solusi layak ke solusi layak lain melalui proses pivot sampai tidak ada lagi perbaikan pada fungsi objektif.

Tutorial ini menggunakan contoh maksimisasi keuntungan dengan dua variabel keputusan dan tiga kendala. Perhitungan dilakukan lengkap mulai dari membentuk model matematis, menambahkan variabel slack, membuat tabel simpleks awal, menentukan kolom pivot, menentukan baris pivot, melakukan eliminasi, sampai memperoleh solusi optimal.

---

Daftar Isi

• Pengertian Metode Simpleks
• Konsep Program Linear
• Komponen Model Simpleks
• Bentuk Standar
• Variabel Slack
• Istilah Penting
• Aturan Pivot
• Kondisi Optimal
• Contoh Kasus Metode Simpleks
  • #01 Menentukan Variabel Keputusan
  • #02 Menentukan Fungsi Objektif
  • #03 Menentukan Kendala
  • #04 Mengubah ke Bentuk Standar
  • #05 Membentuk Tabel Simpleks Awal
  • #06 Menentukan Kolom Pivot Iterasi 1
  • #07 Menentukan Baris Pivot Iterasi 1
  • #08 Operasi Pivot Iterasi 1
  • #09 Menentukan Pivot Iterasi 2
  • #10 Tabel Optimal
  • #11 Menentukan Nilai Variabel
  • #12 Menghitung Nilai Maksimum
• Validasi Solusi
• Pseudocode Simpleks
• Simpleks vs Metode Grafik
• Simpleks vs Integer Programming
• Kelebihan dan Kekurangan
• Kapan Simpleks Cocok Digunakan?
• Kesalahan Umum
• Ringkasan
• FAQ Metode Simpleks
• Referensi
• Source Code Metode Simpleks

---

Pengertian Metode Simpleks

Metode Simpleks adalah metode iteratif untuk menyelesaikan masalah linear programming.

Bentuk umum masalah maksimisasi:

dengan kendala:

dan:

Metode Simpleks mengevaluasi titik-titik sudut wilayah feasible secara sistematis sampai ditemukan solusi optimal.

---

Konsep Program Linear

Program linear memiliki tiga komponen utama:

Variabel keputusan
+
Fungsi objektif
+
Kendala

Contoh:

x1 = jumlah produk A
x2 = jumlah produk B

Fungsi objektif:

Maksimalkan keuntungan

Kendala:

bahan baku
waktu produksi
kapasitas mesin

Semua hubungan harus berbentuk linear.

---

Komponen Model Simpleks

---

Bentuk Standar

Misalnya:

ditambahkan variabel slack:

dengan:

---

Variabel Slack

Jika kendala:

maka bentuk standar:

Variabel slack menunjukkan sisa sumber daya.

---

Istilah Penting

---

Aturan Pivot

Untuk tabel dengan:

pada masalah maksimisasi:

1. pilih koefisien paling negatif pada baris Z sebagai kolom pivot;
2. hitung ratio RHS terhadap koefisien positif pada kolom pivot;
3. pilih ratio positif terkecil sebagai baris pivot;
4. ubah elemen pivot menjadi 1;
5. eliminasi elemen lain pada kolom pivot menjadi 0.

---

Kondisi Optimal

Pada format tabel artikel ini, solusi maksimum optimal ketika baris Z tidak lagi mempunyai koefisien negatif pada kolom variabel keputusan.

---

Contoh Kasus Metode Simpleks

Sebuah perusahaan memproduksi dua produk:

Produk A
Produk B

Keuntungan per unit:

Produk A = 3
Produk B = 5

#01 Menentukan Variabel Keputusan

dengan:

---

#02 Menentukan Fungsi Objektif

---

#03 Menentukan Kendala

---

#04 Mengubah ke Bentuk Standar

Tambahkan variabel slack:

Fungsi objektif:

---

#05 Membentuk Tabel Simpleks Awal

Solusi awal:

x1 = 0
x2 = 0
s1 = 4
s2 = 12
s3 = 18
Z  = 0

---

#06 Menentukan Kolom Pivot Iterasi 1

Baris Z:

Paling negatif:

Maka:

x2 = entering variable

---

#07 Menentukan Baris Pivot Iterasi 1

Ratio test:

Ratio positif terkecil:

Maka:

s2 = leaving variable

Elemen pivot:

---

#08 Operasi Pivot Iterasi 1

Baris pivot:

Bagi 2:

Eliminasi x2 pada baris s3:

Eliminasi x2 pada baris Z:

Tabel iterasi 1:

Solusi sementara:

x1 = 0
x2 = 6
Z  = 30

---

#09 Menentukan Pivot Iterasi 2

Koefisien negatif pada baris Z:

Maka:

x1 = entering variable

Ratio:

dan:

Ratio terkecil:

Maka:

s3 = leaving variable

Elemen pivot:

Baris pivot dibagi 3:

Eliminasi x1 pada baris s1:

Eliminasi x1 pada baris Z:

---

#10 Tabel Optimal

Tidak terdapat lagi koefisien negatif pada baris Z untuk variabel keputusan.

---

#11 Menentukan Nilai Variabel

Variabel basis:

Variabel non-basis:

Jadi:

---

#12 Menghitung Nilai Maksimum

Hasil:

Produk A = 2 unit
Produk B = 6 unit
Keuntungan maksimum = 36

---

Validasi Solusi

Kendala 1:

Sisa:

Kendala 2:

maka:

Kendala 3:

maka:

Semua kendala terpenuhi.

---

Pseudocode Simpleks

input:
    fungsi_objektif
    kendala

ubah kendala ke bentuk standar
tambahkan slack variable
buat tableau awal

while ada koefisien negatif
      pada baris Z:

    pivot_column =
        koefisien paling negatif

    hitung ratio =
        RHS / koefisien positif

    pivot_row =
        ratio positif terkecil

    jadikan pivot = 1

    eliminasi kolom pivot
    pada baris lain

return:
    variabel basis
    nilai fungsi objektif

---

Simpleks vs Metode Grafik

---

Simpleks vs Integer Programming

Simpleks standar menyelesaikan linear programming kontinu.

Jika variabel harus bilangan bulat, dapat digunakan metode tambahan seperti:

• Branch and Bound,
• Cutting Plane,
• Mixed Integer Programming.

---

Kelebihan dan Kekurangan

Kelebihan

• Dapat menangani banyak variabel.
• Cocok untuk optimasi linear.
• Memberikan solusi optimal jika model memenuhi syarat.
• Mudah diimplementasikan secara komputasional.
• Menampilkan informasi slack dan basis.

Kekurangan

• Perhitungan manual panjang untuk masalah besar.
• Sensitif terhadap kesalahan pivot.
• Model harus linear.
• Tidak langsung menangani variabel integer.
• Kendala \(\geq\) atau \(=\) dapat memerlukan Big M atau Two-Phase.

---

Kapan Simpleks Cocok Digunakan?

Contoh penggunaan:

• maksimisasi keuntungan;
• minimisasi biaya;
• alokasi sumber daya;
• perencanaan produksi;
• optimasi kapasitas;
• distribusi sumber daya;
• kombinasi produk.

---

Kesalahan Umum

1. Salah menentukan tanda fungsi objektif

Jika:

maka x1 dan x2 masuk tabel dengan koefisien negatif.

2. Salah memilih kolom pivot

Untuk format artikel ini, pilih koefisien paling negatif pada baris Z.

3. Menggunakan ratio negatif

Ratio test hanya untuk koefisien positif pada kolom pivot.

4. Elemen pivot tidak dibuat 1

Baris pivot harus dibagi elemen pivot.

5. Kolom pivot tidak dieliminasi

Elemen lain pada kolom pivot harus dibuat 0.

6. Salah membaca solusi akhir

Variabel basis mengambil nilai RHS, sedangkan variabel non-basis bernilai 0.

---

Ringkasan

Model:

dengan:

Proses:

Tabel Awal
Z = 0
↓
x2 masuk basis
Z = 30
↓
x1 masuk basis
Z = 36
↓
Optimal

Solusi:

---

FAQ Metode Simpleks

Apa itu metode Simpleks?

Metode Simpleks adalah algoritma untuk mencari solusi optimal pada masalah program linear.

Apakah Simpleks termasuk metode optimasi?

Ya.

Apa itu variabel slack?

Variabel tambahan untuk mengubah kendala \(\leq\) menjadi persamaan.

Apa itu entering variable?

Variabel yang masuk menjadi variabel basis.

Apa itu leaving variable?

Variabel yang keluar dari basis saat pivot.

Bagaimana memilih kolom pivot?

Pada format tabel artikel ini, pilih koefisien paling negatif pada baris Z.

Bagaimana memilih baris pivot?

Gunakan ratio test dan pilih ratio positif terkecil.

Kapan proses berhenti?

Ketika tidak ada lagi koefisien negatif pada baris Z untuk variabel keputusan.

Apakah Simpleks dapat digunakan untuk minimisasi?

Bisa, tetapi formulasi tabel dapat memerlukan penyesuaian.

Apakah Simpleks bisa untuk variabel integer?

Simpleks standar menghasilkan solusi kontinu. Untuk integer diperlukan metode tambahan.

Apa itu unbounded?

Kondisi ketika nilai fungsi objektif dapat meningkat tanpa batas karena kendala tidak membatasi arah peningkatan.

Apa itu infeasible?

Kondisi ketika tidak ada solusi yang memenuhi seluruh kendala.

---

Referensi

1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
2. Taha, H. A. (2017). Operations Research: An Introduction. 10th Edition. Pearson.
3. Hillier, F. S., & Lieberman, G. J. (2021). Introduction to Operations Research. McGraw-Hill.

---

Source Code Metode Simpleks

Berikut source code yang menggunakan metode Simpleks pada RumahSourceCode.

Source Code Simplex Maksimasi PHP

Rp350,000