LINEAR PROGRAMMING DENGAN METODE SIMPLEX (Persoalan Minimisasi)

LINEAR PROGRAMMING DENGAN

METODE SIMPLEX

(Persoalan Minimisasi)

Soal.

Galuh Chemical Company harus membuat 1000 unit campuran phospate dan postassium. Biaya per unit phospate adalah $5, sedangkan biaya per unit postassium $6. Jumlah phospate yang dapat digunakan tidak lebih dari 300 unit sedangkan postassium harus digunakan minimal 150 unit. Berapa masing-masing jumlah phospate dan postassium yang harus digunakan agar biaya total minimum ?

Permasalahan Galuh Chemical Company dapat kita formulasikan ke dalam bentuk LP sebagai berikut:

Fungsi Tujuan : Minimisasikan Cost Z = 5X1 + 6X2

Fungsi kendala :

X1 + X2 = 1000

X1         ≤   300

X2         ≥   150

X1, X2 ≥ 0 

Dimana :

X1 = jumlah phospate dalam unit

X2 = jumlah postassium dalam unit

Untuk menyelesaikan permasalahan tersebut dengan metode simplex, kita harus memformulasikan kembali permasalahan tersebut sesuai dengan standard simpleks. Formulasi sesuai standard simpleks artinya kita harus merubah tanda pertidaksamaan (≤ maupun ≥ ) menjadi persamaan.

Untuk kendala dengan tanda = kita hanya menambahkan artificial variabel (Ai) saja. Sehingga kendala yang pertama akan menjadi:

X1 + X2 + A1 = 1000

Kendala kedua, X1 ≤ 300 , kita tambahkan slack variabel (Si) sehingga menjadi:

X1 + S1 = 300

Sedangkan kendala ketiga, X2 ≥ 150, harus dikurangi dengan surplus variabel dan ditambah dengan artificial variabel, sehingga menjadi :

          X2 – S2 + A2 = 150

Terakhir kita harus menuliskan fungsi tujuan. Karena dalam fungsi kendala ada artificial variabel, maka kita harus memberikan koefisien +M untuk artificial variable tersebut di fungsi tujuannya. Koefisien +M ini menunjukkan angka yang sangat besar nilainya, sehingga dalam kasus ini dapat diinterpretasikan biaya yang sangat tinggi.

Fungsi tujuan dalam permasalahan Galuh Chemical Company akan menjadi :

Min Biaya Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

Formulasi sesuai standard simpleks dari permasalahan Galuh Chemical Company secara lengkap adalah :

Fungsi Tujuan : Min Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

Fungsi kendala :

X1 + X2  +           A1                = 1000

X1         + S1                                      = 300

        X2       – S2        + A2       = 150

Dimana  X1, X2, S1, S2, A1, A2 ≥ 0

Tabel Awal Simplex

Angka pada baris Cj (5, 6, 0, 0, +M, +M) tersebut adalah koefisien pada fungsi tujuan. Sedangkan angka (1, 1, 0, 0, 1, 0) pada baris A1 serta angka (1, 0, 1, 0 0, 0) pada baris S1 dan angka (0, 1, 0, -1, 0, 1) pada baris A2 adalah koefisien pada kendala 1, 2 dan 3.

Angka pada baris Zj (+M, 2M, 0, -M , +M, +M ) diperoleh dari penjumlahan hasil kali kolom Cj dengan kolom yang bersesuaian. Sebagai contoh kita akan menentukan nilai Zj kolom X1 = (M x 1) + (0 x 1) + (M x 0) = M. Dengan cara yang sama kita peroleh nilai Zj pada kolom yang lain. Angka pada baris Cj – Zj diperoleh dari angka pada baris Cj dikurangi dengan angka pada baris Zj. Sebagai contoh kita akan menghitung nilai Cj – Zj pada kolom X1 = 5 (yaitu angka pada baris Cj) – M (angka pada baris Zj) = 5 - M . Demikian juga untuk menghitung nilai Cj – Zj untuk kolom-kolom yang lain digunakan cara yang sama.

Untuk melakukan perbaikan tabel kita harus menentukan pivot column dan pivot row seperti yang telah kita bahas pada kasus maksimisasi. Hanya saja penentuan pivot column pada kasus minimisasi berbeda dengan kasus maksimisasi. Pada kasus minimisasi, kolom kunci / pivot column ditentukan dengan cara memilih angka pada baris CJ – Zj yang mempunyai tanda negatif serta angkanya paling besar.

Langkah-langkah yang harus dilakukan dalam perbaikan tabel adalah sebagai-berikut:

1. Menentukan pivot column/ Kolom Kunci (variabel yang akan masuk ke dalam kolom Product Mix), yaitu dengan memilih variable yang mempunyai nilai Cj – Zj negatif serta angkanya paling besar. Pivot column ini disebut juga optimal column atau kolom kunci.

2.  Menentukan pivot row/ Baris Kunci (variable yang akan keluar dari kolom Product Mix), yaitu dengan membagi kolom quantitas dengan optimal column atau pivot column kemudian pilih hasil bagi non-negatif terkecil.

Tabel Simplex ke II

Dari tabel di atas dapat dilihat bahwa variable yang mempunyai nilai Cj – Zj negatif dan angkanya paling besar adalah variabel X2, karena M menyatakan bilangan yang sangat besar nilainya. Dengan demikian variabel X2 disebut sebagai Kolom Kunci / Pivot Column. Untuk menentukan pivot row, kita akan membagi angka pada kolom kuantitas dengan pivot column (kolom X2), kemudian kita pilih hasil bagi non-negatif terkecil. Pada kasus Galuh Chemical Company, variabel yang merupakan baris kunci / pivot row adalah variabel A2. Oleh karena itu pada tabel berikutnya (Tabel 2), variabel A2 akan keluar dan digantikan oleh variabel X2.

Dalam baris Cj – Zj tabel simpleks II, dapat kita lihat terdapat 2 variabel yang mempunyai nilai negatif yaitu X1 dan X2. Dalam aturan permasalahan minimisasi, apabila pada baris Cj-Zj masih terdapat nilai negtif maka tabel tersebut belum optimal, oleh karena itu kita perlu melakukan iterasi.  

Setelah kolom kunci dan baris kunci ditentukan maka kita akan menghitung baris X2 untuk tabel simplex III ini yaitu dengan cara baris A2 tabel awal dibagi pivot number (angka kunci), yaitu 1.   

Langkah selanjutnya adalah mengisi baris yang lain yang bukan merupakan pivot row, yaitu angka pada baris lama tabel sebelumnya dikurangi dengan hasil perkalian antara angka pada pivot column baris bersangkutan, dengan angka pada baris baris yang menggantikan. Dalam kasus Galuh Chemical Company ada 2 variabel yang akan dihitung nilai pada baris yang baru yaitu baris A1 dan S1.  

 

Tabel Simplex Ke III

Perbaikan tabel ini akan kita lakukan hingga kita memperoleh tabel optimal, yaitu apabila baris Cj – Zj sudah positif atau nol. Karena pada tabel 2 ini masih kita jumpai angka yang bertanda negatif pada baris Cj-Zj yaitu angka pada kolom X1 (5-M) dan kolom S2 (6-M), maka kita akan melakukan perbaikan tabel dengan membuat tabel 3 dan seterusnya hingga memperoleh tabel optimal. Langkah-langkah yang harus dilakukan untuk membuat tabel perbaikkan sama dengan langkah-langkah yang telah kita lakukan pada saat membuat tabel 2 yaitu: tentukan pivot column, pivot row, pivot number, kemudian hitung angka pada baris yang menggantikan serta angka pada baris yang lainnya.

Pivot column pada tabel 2 di atas adalah kolom X1 (karena mempunyai angka negatif terbesar yaitu 5-M), dan pivot row adalah baris S1 (karena merupakan hasil bagi non-negatif terkecil).

Untuk lebih jelasnya perhatikan perhitungan untuk menentukan pivot row berikut ini:

Untuk baris A1 : 850/1 = 850

Untuk baris S1 : 300/1 = 300 à rasio non-negatif terkecil à pivot row

Untuk baris X2: 150/0 àabaikan rasio seperti ini

Seperti halnya pada saat kita membuat tabel ke II, untuk membuat tabel ke III ini setelah kita menentukan pivot column / kolom kunci dan pivot row / baris kunci maka kita akan menentukan pivot number / angka kunci dan kemudian akan mengisi angka pada baris yang menggantikan yaitu baris X1. Pivot number pada tabel 2 adalah 1, yaitu angka pada perpotongan kolom X1 dan baris S1. Angka-angka pivot column, pivot row serta pivot number dapat dilihat pada tabel berikut ini :

Untuk mengisi angka-angka pada baris X1 tabel 3 kita akan membagi angka-angka pada baris S1 tabel 2 dengan pivot number. Perhitungan selengkapnya adalah sebagai berikut :

Setelah mengisi angka-angka pada baris X1 maka untuk melengkapi tabel 3 kita harus mengisi angka-angka pada baris A1 dan X2. Cara untuk mengisi angka-angka pada baris A1 dan X2 sama dengan cara untuk mengisi baris lainnya pada tabel 2 di atas. Perhitungan secara lengkap dapat dilihat pada tabel berikut ini :

Tabel Simplex ke IV

Dari tabel diatas ternyata belum optimal karena pada baris Cj-Zj masih kita jumpai angka negatif yaitu pada kolom S2. Oleh karena itu kita akan membuat tabel yang ke V. Kolom kunci pada tabel simplex ke III adalah kolom S2 sedangkan baris kunci adalah baris A1. Perhatikan hasil perhitungan berikut ini.

Baris A1: 550/1 = 550 Baris Kunci

Baris X1 = 300/0 = 0 abaikan

Baris X2 = 150/ -1 = -150 abaikan

Dari informasi di atas berarti variabel yang akan masuk ke tabel 4 adalah variabel S2 sedangkan variabel yang akan keluar adalah variabel A1. untuk membuat tabel 4 kita akan mengisi angka pada baris S2 terlebih dahulu baru kemudian angka pada baris X1 dan X2.

Tabel Simplex Optimal

Kesimpulan :

Karena pada baris Cj – Zj pada tabel 4 tersebut sudah positif dan nol maka tabel 4 merupakan tabel optimal. Dari tabel 4 dapat kita simpulkan bahwa jumlah X1 yang diproduksi 300 unit, X2 700 unit dengan biaya total $ 5.700. S2 (sisa Bahan) sebesar 550 menunjukkan bahwa jumlah postassium yang dipakai lebih dari yang tersedia. Besarnya kelebihan tersebut adalah 550.