ANALISIS METODE SIMPLEX SEBAGAI ALGORITMA EKSPONENSIAL

Metode Simplex merupakan salah satu metode yang digunakan untuk mencari penyelesaiaan optimum dari pemrograman linier dengan kendala (constraints) berbentuk pertidaksamaan kurang dari sama dengan (≤). Penelitian ini bertujuan untuk mengetahui jawaban terhadap pertanyaan mengapa metode simplex merupakan algoritma eksponensial, yaitu bilamana pemrograman linier berukuran n variabel akan menemukan solusi optimal sebanyak-banyaknya dalam n 2 tahapan (iterasi). Penelitian ini mengexplore delapan problem program linier dengan jumlah variabel keputusan tidak lebih dari lima variabel. Hasil yang diperoleh dari beberapa contoh permasalahan menunjukkan bahwa metode simplex dalam kasus sederhana merupakan algoritma eksponensial, kemudian hasil yang ditunjukkan pada pemrograman linier kasus terburuk juga menunjukkan bahwa metode simplex merupakan algoritma eksponensial