Jelaskan Gambaran umum dari Metode simpleks

Algoritma simpleks bekerja pada program linear dalam bentuk kanonik (baku):

Dalam bentuk ini, vektor  adalah koefisien dari fungsi objektif,  adalah operasi transpos, dan  adalah variabel-variabel dari masalah. Selain itu,  adalah matriks berukuran  dan . Ada cara mudah untuk menyusun sebarang program linear menjadi bentuk bakunya, sehingga penggunaan bentuk ini tidak mengurangi keumuman dari pembahasan. Dalam konteks geometri, daerah feasibel nilai  yang memenuhi kendala  dan  adalah sebuah politop konveks, yang mungkin tidak terbatas (unbounded). Sebuah titik ekstrem atau rusuk dari politop ini dikenal sebagai solusi feasibel sederhana (basic feasible solution, BFS).

Dapat ditunjukkan untuk program linear dalam bentuk baku, jika fungsi objektif mempunyai nilai maksimum di daerah feasibel, maka nilai maksimum ini terletak di (setidaknya satu) titik ekstrem. Hal ini menyederhanakan program linear menjadi sebuah masalah komputasi yang berhingga, karena hanya terdapat terhingga banyaknya titik ekstrem; walaupun banyaknya titik ekstrem dapat terlalu besar untuk dapat ditangani. Selain itu, juga dapat dibuktikan jika sebuah titik ekstrem tidak memberikan fungsi objektif nilai yang maksimum, maka ada rusuk dari titik tersebut yang "mengarahkan" fungsi objektif ke nilai yang lebih tinggi. Pada kasus panjang rusuk terhingga, maka rusuk akan terhubung dengan sebuah titik ekstrem lain yang memiliki nilai fungsi objektif lebih tinggi; namun jika panjang rusuk tak hingga, nilai fungsi objektif akan tidak terbatas dan program linear tidak memiliki solusi. Algoritma simpleks menerapkan wawasan ini, dengan "berjalan" sepanjang rusuk-rusuk dari politop untuk mencapai titik ekstrem dengan nilai fungsi objektif paling besar; atau berhenti ketika mencapai rusuk dengan panjang tak terbatas. Algoritma selalu berakhir (terminates) karena ada terhingga banyaknya rusuk pada politop. Selain itu, karena kita menelurusi rusuk-rusuk dalam "arah yang sama" dengan fungsi objektif, kita berharap hanya sedikit rusuk yang perlu dikunjungi.

Solusi dari program linear dikerjakan dalam dua tahap. Pada Tahap I, sebuah titik ekstrem ditentukan. Tergantung dari program yang dikerjakan, hal ini dapat dilakukan secara trivial, atau dengan menerapkan algoritma simpleks ke suatu modifikasi dari program semula. Tahap ini dapat menghasilkan sebuah solusi feasibel sederhana, atau tidak sama sekali (karena daerah feasibel kosong). Untuk kasus kedua, program linear dikatakan tidak feasibel. Selanjutnya pada Tahap II, algoritma simpleks diterapkan pada solusi feasibel sederhana yang didapat pada Tahap I sebagai titik mulai pengerjaan. Hasil dari Tahap II adalah sebuah solusi feasibel yang optimal, atau sebuah rusuk dengan panjang terbatas (yang menyebabkan nilai fungsi tidak terbatas dari atas).