Metoda simplex masalah minimisasi

Untuk menyelesaikan permasalahan tersebut dengan metode simpleks 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 saja. Sehingga kendala yang pertama akan menjadi :

X1 + X2 + A1 = 1000

Kendala kedua, X1 ≤ 300 , kita tambahkan slack variabel 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 tujuan. Koefisien +M ini menunjukkan angka yang sangat besar nilainya, sehingga dalam kasus ini dapat diinterpretasikan biaya yang sangat tinggi. Fungsi tujuan dalam permasalahan Putra Chemical Company akan menjadi :

Minimisasikan biaya Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

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

Fungsi Tujuan :

Minimisasikan biaya Z = 5X1 + 6X2 + 0S1 + 0S2 + MA1 + MA2

Fungsi kendala :

X1 + X2 + A1 = 1000

X1 + S1 = 300

X2 – S2 + A2 = 150

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

1.      Menyusun table awal

Langkah selanjutnya untuk menyelsesaikan permasalahan LP dengan metode simpleks adalah membuat tabel awal. Hanya saja karena pada permasalahan Putra Chemical Company kita mengenal variabel lain selain slack variabel yaitu surplus variabel dan artificial variabel, maka variabel yang boleh masuk ke kolom product mix pada tabel awal ini hanyalah slack variabel dan artificial variabel.

	Cj	5	6	0	0	+M	+M
Product mix		X1	X2	S1	S2	A1	A2	Q
A1	+M	1	1	0	0	1	0	1000
S1	0	1	0	1	0	0	0	300
A2	+M	0	1	0	-1	0	1	150
	Zj	+M	2M	0	-M	+M	+M	1050M
	Cj-Zj	5-M	6-2M	0	M	0	0

2.      Menentukan Kolom Pivot

Pada kasus minimisasi, 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 :

a.       Menentukan pivot column (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.

b.      menentukan pivot row (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.

Untuk lebih memahami bagaimana kita menentukan pivot column dan pivot row, marilah kita lihat kembali tabel awal Putra Chemical Company.

	Cj	5	6	0	0	+M	+M
Product mix		X1	X2	S1	S2	A1	A2	Q
A1	+M	1	1	0	0	1	0	1000
S1	0	1	0	1	0	0	0	300
A2	+M	0	1	0	-1	0	1	150	Pivot row
	Zj	+M	2M	0	-M	+M	+M	1050M
	Cj-Zj	5-M	6-2M	0	M	0	0
			Pivot coloum

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 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 Putra Chemical Company, variabel yang merupakan pivot row (baris kunci) adalah variabel A2.

3.      Melakukan Iterasi

Dalam baris Cj – Zj, 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 pivot column dan pivot row ditentukan maka kita akan menghitung baris X2 untuk tabel 2 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.

Angka baru = angka lama- angka pada coloum pivot x angka pada baris pivot yang bersesuaian

	Cj	5	6	0	0	+M	+M
Product mix		X1	X2	S1	S2	A1	A2	Q
A1	+M	1	0	0	1	1	-1	850
S1	0	1	0	1	0	0	0	300
X2	6	0	1	0	-1	0	1	150
	Zj	+M	6	0	M-6	+M	6-M	900+850M
	Cj-Zj	5-M	0	0	6-M	0	-6+2M

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 iterasi kembali 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  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).