Algoritma Simpleks

Langkah-langkah dalam algoritma simpleks untuk mencari solusi optimal dari suatu masalah pemrograman linier adalah sebagai berikut :

1)      Langkah Pertama

Langkah pertama yang dilakukan adalah menentukan kolom kerja (work column). Kolom kerja ditentukan berdasarkan nilai yang paling negatif dan nilai-nilai yang berada pada baris fungsi obyektif (Z) pada tabel simpleks. Variabel yang berada pada kolom kerja ini akan menjadi entering variabel menggantikan salah satu variabel dasar sebelumnya. Variabel dasar mana yang akan digantikan oleh entering variabel ini ditentukan pada langkah kedua.

2)      Langkah Kedua

Langkah kedua adalah membuat nilai perbandingan antara nilai kanan (NK) dengan nilai pada kolom kerja dari setiap baris, kecuali baris fungsi obyektif. Baris dengan nilai perbandingan yang terkecil akan berperan sebagai baris pivot. Variabel dasar yang berada pada baris pivot akan menjadi leaving variabel yang akan digantikan oleh entering variable.

3)      Langkah Ketiga

Langkah ketiga adalah langkah pertama dari langkah-langkah perbaikan solusi. Pada langkah ketiga ini dilakukan perubahan nilai pada baris pivot dengan cara membagi setiap elemen dari baris pivot ini dengan pivot elemen. Nilai pivot elemen ini adalah nilai perpotongan antara baris pivot dengan kolom kerja.

4)      Langkah Keempat

Langkah keempat adalah merubah variabel dasar, yang berarti entering variable untuk menggantikan leaving variable.

5)      Langkah Kelima

Langkah kelima adalah merubah semua nilai pada baris selain baris pivot dengan cara berikut :

Nilai baru = Nilai lama – (Nilai pada kolom kerja x Nilai baru pada baris pivot).

6)      Langkah Keenam

Langkah keenam adalah memeriksa apakah masih terdapat nilai negatif pada baris fungsi obyektif. Bila ternyata ada nilai negatif pada baris tersebut, berarti tabel belum optimal, sehingga perlu dilakukan kembali langkah-langkah penyelesaian diatas hingga diperoleh solusi yang optimal.

Sumber : Media Anugerah Ayu, Pengantar Riset Operasional Seri Diktat Kuliah, Universitas Gunadarma, Jakarta, 1996.