Riset Operasi Tugas 4: Metode Simplex & Contoh Kasusnya

1.       Pengertian Metode Dual Simpleks

Metode simpleks adalah teknik untuk menyelesaikan program linier yang tidak mampu diselesaikan oleh metode grafis. Metode simpleks sendiri memiliki kerangka berpikir beberapa macam yaitu dengan menggunakan BFS (basis fesibel solution) dan metode simpleks dengan menggunakan tabel. Metode simpleks dengan menggunakan tabel hanya memuat tiga informasi penting yaitu koefisien pada variabel, konstanta pada ruas kanan persamaan dan variabel basis yang muncul untuk setiap persamaan.

Langkah langkah metode simpleks tabel:

1)    Inisialisasi

Langkah pertama yaitu memasukkan variabel slack. Kemudian pilihlah variabel keputusan yang kemudian akan dijadikan sebagai variabel nonbasis awal. Lalu pilihlah varibel slack yang akan dijadikan sebagai variabel basis awal.

2)    Uji Optimalitas

Dalam uji optimalitas, BFS saat ini dapat dikatakan optimal apabila setiap koefisien dalam baris nol adalah nonnegatif, sehingga langkah-langkah dalam metode simpleks tabel dapat selesai. Namun apabila setiap koefisien dalam baris nol adalah  bukan nonnegatif, maka langkah selanjutnya adalah iterasi untuk mendapatkan BFS berikutnya.

3)    Iterasi

• Langkah 1:

Tentukanlah variabel basis yang masuk dengan memilih variabel dengan koefisien negatif yang mempunyai nilai absolut paling besar (paling negatif). Kemudian letakkanlah kotak di sekitar kolom dibawah koefisien tersebut, kolom ini sering disebut kolom sumbu atau pivot column.

• Langkah 2:

Langkah selanjutnya yaitu dengan menentukan variabel basis yang keluar. Hal ini dapat dilakukan dengan menerapkan uji rasio minimum yaitu dengan cara:

·         Mengambil masing-masing koefiien dalam kolom sumbu yang positif

·         Membagi masing-masing angka pada ruas kanan dengan koefisien pada kolom sumbu dalam baris yang sama

·         Tentukanlah baris mana yang mempunyai rasio yang paling kecil

·         Variabel basis pada baris adalah variabel basis yang keluar, kemudian gantilah variabel itu dengan variabel basis yang masuk dalam kolom variabel basis tabel simpleks yang berikutnya.

Kemudian letakkanlah kota disekitar baris ini yang biasa disebut baris sumbu (pivot row) dan angka yang berada dalam baris sumbu dan kolom sumbu disebut angka sumbu (pivot number).

• Langkah 3:

Langkah selanjutnya adalah carilah BFS baru dengan   menggunakan operasi baris dasar. Hal ini dimaksudkan untuk membentuk tabel simpleks yang baru.

Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.

2.       Contoh & Kasus Metode Dual Simpleks

Min z = 21x1 + 18x2 + 15x3

Terhadap 90x1 + 20x2 + 40x3 ≥ 200 30x1 + 80x2 + 60x3 ≥ 180

10x1 + 20x2 + 60x3 ≥ 150 x1, x2, x3 ≥ 0

semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:

Min z = 21x1 + 18x2 + 15x3

Terhadap -90x1 - 20x2 - 40x3 ≤ -200 -30x1 - 80x2 - 60x3 ≤ -180 -10x1 - 20x2 - 60x3 ≤ -150 x1, x2, x3 ≥ 0

Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.

Bentuk Baku/standar:

Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3

	Terhadap		-90x1 - 20x2 - 40x3 + s1 = -200
		-30x1		- 80x2 - 60x3 + s2 = -180
		-10x1		- 20x2 - 60x3 + s3 =	-150
		x1, x2, x3, s1, s2, s3 ≥ 0

Tabel di atas optimal tapi tidak layak (ingat, untuk fungsi tujuan minimisasi, tabel sudah optimal jika semua koefisien baris tujuan sudah negatif atau 0). Untuk membuat tabel tersebut layak, kita harus gunakan metode dual simpleks. Langkah-langkah penyelesaian simpleks menggunakan metode dual adalah:

1.     Tentukan baris pivot. Baris pivot adalah baris dengan nilai kanan negatif terbesar. Jika negatif terbesar lebih dari satu, pilih salah satu sembarang.

2.     Tentukan kolom pivot. Kolom pivot diperoleh dengan terlebih dahulu membagi nilai baris z dengan baris pivot. Dalam hal ini, semua nilai baris pivot dapat menjadi pembagi kecuali nilai 0. Kolom pivot adalah kolom dengan rasio pembagian mutlak terkecil. Jika rasio pembagian mutlak terkecil lebih dari satu, pilih salah satu secara sembarang.

3.     Pembentukan tabel berikutnya sama dengan prosedur dalam primal simpleks.

Gunakan tabel awal simpleks di atas.

¾    Baris pivot adalah baris S1, baris dengan nilai kanan negatif terbesar.

¾ Kolom pivot adalah kolom X1

 sumber :

http://drs-saukanihasan.blogspot.co.id/2012/06/operation-research.html