METODE DUAL SIMPLEX


Prosedur perhitungan yang dibicarakan sejauh ini bergerak dari solusi dasar layak yang belum optimum ke solusi layak yang lain. Apakah proses tersebut akhirnya akan mencapai suatu solusi layak optimum, adalah tergantung pada kemampuan untuk mendapatkan suatu solusi dasar awal yang layak. Dalam kaitan ini, artificial variabel kadang-kadang digunakan untuk menemukan solusi awal layak. Jika formulasi LP mengandung sejumlah besar artificial variable, maka membutuhkan banyak perhitungan untuk memperoleh solusi awal layak. Karena itu, akan dijelaskan suatu prosedur perhitungan yang memberikan suatu solusi layak optimum, meskipun solusi awalnya tidak layak. Prosedur itu dinamakan dual simplex algorithm yang pertama kali disusun oleh Lemke. Algoritma ini tidak banyak digunakan di antara program-program komputer yang ada. Namun ia memainkan peranan penting dalam post optimality analysis.