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