Penyelesaian Program Linear Dengan Metode Simpleks

Metode simpleks adalah salah satu teknik pemecahan program linear selain metode grafik, Bedanya dengan metode grafik, metode simpleks dapat dimanfaatkan untuk persamaan yang memiliki variabel lebih dari 2 sedangkan grafik tidak.

 images-36 Penyelesaian Program Linear Dengan Metode Simpleks
Sama seperti metode grafik, diperlukan juga formulasi program linear agar dapat dipecahkan dengan metode grafiknya. Untuk lebih jelas tentang metode grafik dan program linear dapat dilihat pada :
  • Program Linear
  • Pemecahan Program Linear Metode Grafik
Sebelum masuk ke cara pemecahan program linear dengan metode simpleks, perlu anda ketahui sebelumnya tentang bentuk standar model program linear.

Bentuk Standar Model Program Linear

Seperti yang sudah diuarikan pada artikel sebelumnya pada program  linear, bahwa model program linear dapat memiliki pembatas-pembatas yang bertanda ≤, ≥, dan =. Demukian juga variabel-variabelnya yang dapat berupa variabel non-negatif, dapat pula berupa variabel-variabel yang tidak terbatas dalam tanda.
Dalam penyelesaian program linear dengan metode simpleks, bentuk dasar yang digunakan haruslah bentuk standar. Formulasi bentuk standar memiliki sifat-sifat sebagai berikut :
  1. Fungsi tujuanya dapat berupa maksimasi atau minimasi.
  2. Seluruh pembatas sudah dalam bentuk persamaan (tanda = ) dengan ruas kanan persamaan yang non-negatif.
  3. Seluruh variabelnya harus merupakan variabel non-negatif.
Untuk mengubah suatu bentuk formulasi yang belum standar ke dalam bentuk standar dapat dilakukan dengan cara berikut:

1. Pembatas

    • Pembatas yang bertanda ≤ atau ≥ dapat dijadikan suatu persamaan (tanda = ) dengan menambahkan suatu variabel slack (S) atau mengurangkan dengan suatu variabel surplus (S)
      • Contoh 1: X1 + X2 ≤ 8
Kita tambahkan slack S1 pada ruas kiri persamaan tersebut sehingga diperoleh persamaan: X1 + X2 + S1 = 8, S1 ≥ 0.
Jika pembatas diatas menyatakan batas penggunaan suatu sumber daya, maka S1 merupakan banyaknya sumber daya yang tidak terpakai.
      • Contoh 2: X1 + 2 X2 ≥ 5
Karena bertanda ≥ maka harus dikurangi dengan variabel S2 pada ruas kiri persamaan sehingga diperoleh persamaan: X1 + 2X2 -S2 = 5, dimana S2 ≥ 0.
    • Ruas kanan dari suatu persamaan dapat dijadikan bilangan non-negatif dengan mengalikan kedua ruas dengan -1.
      • Contoh : X1 – 5 X2 = -7, secara matematis adalah sama dengan persamaan -X1 + 5 X2 = 7.
  • Arah ketidaksamaan dapat berubah apabila kedua ruas dikalikan -1.
    • Contoh :  X1 – X2 ≤ -8, adalah sama dengan -X1 + X2 ≥ 8.

2. Variabel

Suatu variabel Xi yang tidak terbatas oleh tanda dapat dinyatakan sebagai dua variabel non-negatif dengan menggunakan substitusi: Xi = Xi’ – Xi” dimana Xi’ dan Xi” ≥ 0. Substitusi seperti ini harus dilakukan pada seluruh pembatas dan fungsi tujuanya.

3. Fungsi tujuan

Maksimasi dari sebuah fungsi adalah sama dengan minimasi dari negatif fungsi yang sama.
Contoh : Maksimumkan Z = X1 + 2 X2 secara matematis sama dengan : Minimumkan (-Z) = -X1 – 2 X2.

Metode Simpleks

Pada topik sebelumnya tentang metode grafik, sudah dijelaskan pemecahan program linear yang digunakan untuk menyelesaikan masalah 2 variabel. Untuk menyelesaikan masalah program linear berdimensi lebih besar dari 2 dikenal metode yang lazim disebut metode simpleks.
Metode simpleks dikembangkan pertama kali oleh George dantzing pada tahun 1947, sifat dari metode ini adalah iterative, dimana penyelesaian masalah melaui tahapan perhitungan yang berulang-ulang sampai tercapai solusi optimum.
Untuk lebih jelasnya dapat dilihat dari contoh soal dibawah :

Contoh Metode Simpleks

Maksimumkan : Z = 15 X1 + 18 X2 + 12 X3
Kendala :
10 X1 + 12 X2 + 8 X3 ≤ 120
18 X1 + 15 X2 + 6 X3 ≤ 135
12 X1 + 16 X2 + 6 X3 ≤ 150
X1, X2, X3 ≥ 0

Langkah 1 : Mengubah fungsi tujuan dan fungsi kendala

Fungsi tujuan diubah menjadi bentuk implisit dengan jalan menggeser fungsi tujuan ke Z, yaitu Z = 15 X1 + 18 X2 + 12X3 dirubah menjadi Z – 15 X1 – 18 X2 – 12X3 = 0.Sedangkan fungsi kendala (selain kendala non-negatif) dirubah menjadi bentuk persamaan dengan menambahkan variabel slack, yaitu suatu variabel yang mewakili tingkat pengangguran kapasitas yang merupakan batasan.

Fungsi kendala pada soal tersebut diatas berubah menjadi :

10 X1 + 12 X2 + 8 X3 + S1 = 120
18 X1 + 15 X2 + 6 X3 + S2 = 135
12 X1 + 16 X2 + 6 X3 + S3 = 150
X1, X2, X3, S1, S2, S3 0

 

Langkah 2 : Mentabulasikan persamaan-persamaan fungsi tujuan dan kendala yang telah dirubah seperti pada langkah 1 diatas.

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z 1 -15 -18 -12 0 0 0 0
S1 0 10 12 8 1 0 0 120
S2 0 18 15 6 0 1 0 135
S3 0 12 16 6 0 0 1 150

 

Kolom basis menunjukan variabel yang sedang menjadi basis yaitu S1, S2, S3 yang nilainya ditunjukan oleh kolom solusi. Secara tidak langsung ini menunjukkan bahwa variabel non-basis X1, X2, X3 (yang tidak masuk pada kolom basis) sama dengan nol.Hal ini bisa dimengerti, karena belum ada kegiatan/produksi X1, X2, X3 masing-masing nilainya nol yang berarti juga kapasitas masih menganggur yang ditunjukan oleh nilai S1, S2, S3.

Langkah 3 : Menentukan kolom pivot

Setelah kita mentabulasikan persamaan menjadi bentuk tabel simpleks, langkah selanjutnya adalah memilih kolom pivot. Kolom pivot (entering variabel) dipilih dari baris Z dengan angka negatif terbesar untuk masalah maksimasi. Jadi sesuai soal diatas didapatkan bahwa kolom pivotnya adalah X2.
Sehingga jika digambarkan dalam tabel menjadi :
Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z 1 -15 -18 -12 0 0 0 0
S1 0 10 12 8 1 0 0 120
S2 0 18 15 6 0 1 0 135
S3 0 12 16 6 0 0 1 150
Pada tabel diatas kolom X2 adalah kolom yang dipilih karena memiliki nilai -18 (nilai negatif terbesar).

Langkah 4 : Menentukan baris pivot

Setelah kita mendapatkan kolom pivot, langkah selanjutnya adalah menentukan baris pivot (leaving variabel). Untuk mengetahui baris mana yang pilih dapat dilakukan dengan membagi solusi dengan kolom pivot pada setiap baris.Setelah itu dipilihlah angka dengan rasio terkecil, namun jika terdapat angka negatif dan tidak hingga kolom pivot maka tidak masuk dalam perhitungan rasio, jadi jika terdapat angka negatif atau tak hingga maka diberi tanda strip pada kolom rasio. Setelah mendapat rasio maka kita harus memindahkan variabel pada kolom pivot ke baris pivot.

Sehingga bedasarkan soal diatas menjadi :
Basis Z X1 X2 X3 S1 S2 S3 Solusi Rasio
Z 1 -15 -18 -12 0 0 0 0
S1 0 10 12 8 1 0 0 120 10
X2 0 18 15 6 0 1 0 135 9
S3 0 12 16 6 0 0 1 150 9.375

 

Langkah 5 : Menentukan persamaan pivot baru

Rumus untuk menentukan persamaan pivot baru adalah = baris pivot lama : elemen pivot. Elemen pivot adalah perpotongan antara kolom dan baris pivot. Jadi setiap baris pivot yang telah ditentukan dibagi dengan elemen pivot sehingga dihasilkan persamaan pivot baru.
Sehingga dari bedasarkan soal diatas menjadi :
Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z 1
S1 0
X2 0 18/15 1 6/15 0 1/15 0 9
S3 0

 

Bedasarkan tabel diatas semua baris pivot dibagi dengan elemen pivot yaitu 15. Sehingga dihasilkan persamaan pivot yang baru.

Langkah 6 : Menentukan persamaan baru selain persamaan pivot baru

Setelah mendapat persamaan pivot baru, langkah selanjutnya adalah mengisi persamaan lainya yang masih kosong. Rumus untuk menentukan persamaan baru selain persamaan pivot baru adalah sebagai berikut :
Persamaan baru = (persamaan lama) – (persmaan pivot baru x koefisien kolom pivot)
Jadi persamaan baru yang dicari dari persoalan diatas adalah persamaan baru untuk basis Z, S1, dan S3. Sedangkan S2 sudah diganti oleh persamaan pivot baru X2.
 
Persamaan Z baru :
(-15) – (18/15 x -18) = 33/5
(-18) – (1 x -18) = 0
(-12) – (6/15 x -18) = -24/5
(0) – (0 x -18) = 0
(0) – (1/15 x -18) = 6/5
(0) – (0 x -18) = 0
(0) – (9 x -18) = 162
Persamaan S1 baru :
(10) – (18/15 x 12) = -22/5
(12) – (1 x 12) = 0
(8) – (6/15 x 12) = 16/5
(1) – (0 x 12) = 1
(0) – (1/15 x 12) = -4/5
(0) – (0 x 12) = 0
(120) – (9 x 12) = 12
Persamaan S3 baru :
(12) – (18/15 x 16) = -36/5
(16) – (1 x 16) = 0
(6) – (6/15 x 16) = -2/5
(0) – (0 x 16) = 0
(0) – (1/15 x 16) = -16/5
(1) – (0 x 16) = 1
(150) – (9 x 16) = 6
Persamaan pivot baru, Z baru, S1 baru, dan persamaan S3 baru yang sudah dicari nilainya kemudian ditabulasikan dalam tabel simpleks baru sebagai berikut :
Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z 1 33/5 0 -24/5 0 6/5 0 162
S1 0 -22/5 0 16/5 1 -4/5 0 12
X2 0 18/15 1 6/15 0 1/15 0 9
S3 0 -36/5 0 -2/5 0 -16/5 1 6

Langkah 7 : Lanjutkan perbaikan-perbaikan

Periksa kembali tabel simpleks anda, apakah pada baris Z angkanya sudah positif semua (≥ 0) untuk kasus maksimasi, jika sudah positif semua berarti solusi optimal sudah didapatkan.Terlihat pada langkah 6 diatas baris Z masih ada yang negatif yaitu kolom X3. Maka perlu dilakukan perbaikan untuk mencapai nilai optimal.

Maka dari itu diperlukan perbaikan. Dalam perbaikan anda hanya perlu mengulangi kembali dari langkah 3 dari tabel yang sudah anda hitung. Lakukan secara terus menerus hingga baris Z bernilai positif semua.

Setelah dilakukan perbaikan, maka tabel optimal dari contoh diatas akan didapatkan sebagai berikut :

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z 1 0 0 0 3/2 0 0 180
S1 0 -11/8 0 1 5/16 -1/4 0 15/4
X2 0 7/4 1 0 -1/8 1/6 0 15/2
S3 0 -31/4 0 0 1/8 -7/6 1 15/2
Bedasarkan tabel hasil perbaikan diatas dapat disimpulkan bahwa hasil iterasi ini telah mencapai kondisi optimal, karena nilai pada baris fungsi tujuan Z sudah tidak ada yang negatif.Sehingga dari persoalan diatas untuk kasus maksimasi ini didapatkan nilai :
Z = 180,
X1 = 0 (tidak diproduksi),
X2 = 15/2,
X3 =15/4,
S3 = 15/2 (merupakan kapasitas yang menganggur dari batasan ke 3).

Pada soal berikut, sudah diketahui persamaan-persamaan yang ada. Tetapi, perlu anda ketahui, bentuk soal program linear ada juga yang berbentuk soal cerita, sehingga anda perlu melakukan formulasi terlebih dahulu untuk mendapatkan bentuk persamaan seperti di atas.

Menghitung Simpleks Dengan Mudah

Bagi anda yang malas untuk menggunakan metode simpleks, sekarang ini sudah ada software yang dapat anda gunakan untuk menyelesaikan persamaan simpleks dengan mudah.Jadi kita hanya perlu menentukan fungsi tujuan dan kendala, setelah itu masukkan fungsi-fungsi tersebut ke program untuk diproses, maka secara otomatis anda dapat mengetahui langkah-langkah penyelesaian dan hasil dari solusi optimalnya.

Nama salah satu dari software yang cukup terkenal untuk menyelesaikan masalah simpleks adalah TORA. Selain untuk masalah simpleks, TORA juga bisa digunakan untuk menyelesaikan program program lainya yang berkaitan dengan riset operasi seperti transportasi, dan lain sebagainya.

Tags: