Metoda SIMPLEKS

Penyelesaian suatu masalah pemrograman linier dengan menggunakan metoda grafik. Metoda grafik tersebut hanya dapat digunakan untuk menyelesaikan masalah pemrograman linier yang hanya mempunyai 2 variabel, karena untuk pemrograman linier dengan variabel lebih dari 2 akan sulit untuk menggambarkan bentuk grafiknya. Untuk mengatasi kesulitan ini, maka pada tahun 1947 diperkenalkan suatu metode yang dapat digunakan untuk menyelesaikan masalah pemrograman linier oleh Goerge B. Dantzig yang dinamakan Metoda SIMPLEKS.

Algoritma simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linier yang didasarkan pada proses iterasi. Jadi pada prinsipnya prosedur ini diawali dengan penentuan suatu solusi awal yang secara terus-menerus diperbaiki hingga diperoleh solusi yang optimal. Ada tiga ciri utama dari suatu bentuk baku pemrograman linier untuk algoritma simpleks. Ciri pertama adalah semua kendala harus berada dalam bentuk persamaan dengan nilai kanan tidak negatif. Ciri kedua adalah semua variabel tidak yang terlibat tidak dapat bernilai negatif. Dan ciri terakhir adalah fungsi obyektif dapat bernpa maksimisasi maupun minimisasi.
1.Kendala yang berbentuk pertidaksamaan s diubah ke bentuk persamaan denganmenambahkan suatu variabel barn yang disebut dengan variabel slack untuk setiap kendala.
Contoh:
3X1 + 4­2<10 diubah menjadi
3X1 + 4X2 + S1 = 10
2.Kendala yang sudah berbentuk persamaan juga perlu diubah ke bentuk baku persaman dengan menambahkan suatu variabel yang disebut dengan variabel artificial.
Contoh:
3X1 + 4X2 = 10 diubah menjadi
3X1 + 4X2 + A1 = 10
3.Kendala yang berbentuk pertidaksamaan ~ diubah ke bentuk persamaan dengan menambahkan variabel surplus (negatif dari variabel slack) dan variabel artificial.
Contoh:
3X1 + 4X2 < 10 diubah menjadi
3X1 + 4X2 - 51 + A1 =10
4.Kendala yang mempunyai nilai kanan bernilai negatif diubah dengan mengalikannya dengan -1.
Contoh:
3X1 + 4X2 <10 diubah menjadi
3X1 - 4X3 < 10 + 3X1 - 4X2 + 51 = 10