Metode Simpleks: Pengertian dan Penyelesaian Linear Programming

Metode Simpleks: Pengertian dan Penyelesaian Linear Programming

Metode Simpleks: Pengertian dan Penyelesaian Linear Programming
6 menit baca

Metode simpleks adalah prosedur aljabar untuk menyelesaikan masalah linear programming (program linear), yaitu mengoptimalkan (memaksimalkan atau meminimalkan) fungsi tujuan linear dengan batasan berupa pertidaksamaan linear. Metode ini dikembangkan oleh George Dantzig pada 1947 dan menjadi dasar banyak perangkat lunak optimasi. Berbeda dengan metode grafik yang hanya praktis untuk dua variabel, simpleks dapat menangani banyak variabel.

Konsep dasar

Solusi masalah program linear berada pada titik sudut (extreme point) dari daerah layak. Simpleks bergerak dari satu titik sudut ke titik sudut tetangga yang memperbaiki nilai fungsi tujuan, sampai tidak ada perbaikan lagi. Titik terakhir adalah solusi optimal.

Langkah-langkah

  • Ubah ke bentuk standar: untuk batasan ≤, tambahkan variabel slack sehingga menjadi persamaan. Fungsi tujuan maksimasi ditulis Z - c1x1 - c2x2 = 0.

  • Susun tabel simpleks awal dengan variabel basis (awalnya slack).

  • Tentukan kolom pivot: kolom dengan nilai paling negatif pada baris Z (variabel masuk).

  • Tentukan baris pivot dengan uji rasio: bagi nilai kanan (NK) dengan elemen positif pada kolom pivot, pilih rasio terkecil (variabel keluar).

  • Lakukan operasi baris (eliminasi Gauss-Jordan) agar elemen pivot menjadi 1 dan elemen lain pada kolom pivot menjadi 0.

  • Cek optimalitas: jika tidak ada nilai negatif pada baris Z (untuk maksimasi), solusi sudah optimal. Jika masih ada, ulangi langkah 3.

Contoh soal

Maksimumkan Z = 3x1 + 2x2 dengan batasan:

  • x1 + x2 ≤ 4

  • x1 + 3x2 ≤ 6

  • x1 ≤ 3

  • x1, x2 ≥ 0

Bentuk standar

Tambahkan slack s1, s2, s3: x1 + x2 + s1 = 4, x1 + 3x2 + s2 = 6, x1 + s3 = 3, dan Z - 3x1 - 2x2 = 0.

Iterasi 1

  • Kolom pivot: x1 (koefisien -3 paling negatif).

  • Uji rasio: 4/1 = 4, 6/1 = 6, 3/1 = 3. Terkecil 3 pada baris ketiga, sehingga s3 keluar dan x1 masuk.

  • Hasil: x1 = 3, s1 = 1, s2 = 3, dan Z = 9.

Iterasi 2

  • Baris Z masih memuat x2 dengan koefisien -2, sehingga x2 masuk.

  • Uji rasio: baris s1 = 1/1 = 1, baris s2 = 3/3 = 1 (nilai sama, kasus degenerasi, pilih salah satu).

  • Hasil: x2 = 1 dan Z = 9 + 2 × 1 = 11.

Tidak ada lagi koefisien negatif pada baris Z, sehingga solusi optimal: x1 = 3, x2 = 1, Z = 11. Hasil ini dapat dicek: 3 + 1 = 4 (memenuhi), 3 + 3 = 6 (memenuhi), dan 3 ≤ 3 (memenuhi).

Kasus khusus

  • Batasan ≥ atau persamaan memerlukan variabel artifisial dengan metode Big-M atau dua fase.

  • Untuk minimisasi, bisa diubah menjadi maksimasi dengan mengalikan fungsi tujuan dengan -1, atau memakai metode dual.

  • Solusi tak terbatas terjadi jika tidak ada rasio positif pada kolom pivot. Solusi optimal ganda terjadi jika ada variabel non-basis dengan koefisien 0 di baris Z pada tabel optimal.

Kelebihan dan kekurangan

  • Kelebihan: dapat menyelesaikan masalah dengan banyak variabel dan batasan, sistematis, dan menghasilkan informasi tambahan seperti nilai slack dan harga bayangan (shadow price).

  • Kekurangan: perhitungan manual panjang, hanya berlaku untuk model linear, dan pada kasus tertentu kinerja terburuknya eksponensial meskipun praktiknya umumnya efisien.

Kesimpulan

Metode simpleks adalah alat utama riset operasi untuk optimasi linear, misalnya alokasi produksi, campuran bahan, dan penjadwalan sumber daya. Dalam skripsi, tunjukkan perumusan model, tabel tiap iterasi, dan verifikasi hasil dengan perangkat lunak seperti Excel Solver atau pustaka optimasi.

Bagikan:

Rekomendasi untuk Anda