Kompleksitas dari algoritma simpleks

Apa batas atas pada algoritma simpleks untuk menemukan solusi untuk Program Linear?

Bagaimana saya mencari bukti untuk kasus seperti itu? Sepertinya kasus terburuk adalah jika setiap titik harus dikunjungi yaitu . Namun dalam praktiknya, algoritma simpleks akan berjalan secara signifikan lebih cepat daripada ini untuk masalah yang lebih standar.$O(2^n)$

Bagaimana saya bisa memberi alasan tentang kompleksitas rata-rata masalah yang diselesaikan dengan menggunakan metode ini?

Setiap informasi atau referensi sangat dihargai!

Algoritma simpleks memang kunjungan semua $2^n$ simpul dalam kasus terburuk ( Klee & Minty 1972 ), dan ternyata ini menjadi benar untuk setiap aturan poros deterministik. Namun, dalam makalah tengara menggunakan analisis dihaluskan, Spielman dan Teng (2001) membuktikan bahwa ketika input ke algoritma sedikit acak terganggu, waktu berjalan yang diharapkan dari algoritma simpleks adalah polinomial untuk setiap input - ini pada dasarnya mengatakan bahwa untuk setiap masalah ada yang "dekat" yang metode simpleks efisien akan menyelesaikan, dan itu cukup banyak mencakup setiap program linear dunia nyata yang ingin Anda pecahkan. Setelah itu, Kelner dan Spielman (2006) diperkenalkan Algoritma simpleks acak waktu polinomial yang dapat bekerja pada input apa pun, bahkan yang buruk untuk algoritma simpleks asli.

Seperti yang dikatakan Lev, dalam kasus terburuk algoritma mengunjungi semua simpul $2^d$ mana $d$ adalah jumlah variabel. Namun, kinerja algoritma simpleks juga sangat bergantung pada aturan pivot spesifik yang digunakan. Sejauh yang saya ketahui, ini masih menjadi pertanyaan terbuka jika ada aturan indivinistik deterministik khusus dengan waktu berjalan kasus terburuk sub-eksponensial. Banyak kandidat telah dikesampingkan oleh hasil batas bawah. Baru-baru ini, Friedmann, Hansen, dan Zwick juga menunjukkan batas bawah non-polinomial pertama untuk beberapa aturan pivot acak alami dengan beberapa koreksi yang diberikan kemudian .

Namun, menambah hasil analisis yang dihaluskan yang disebutkan oleh Lev: Setelah kertas mani Spielman dan Tengs memperkenalkan analisis yang diperhalus, Vershynin meningkatkan batasan mereka lebih lanjut pada tahun 2006. Dia menunjukkan bahwa waktu berjalan yang diharapkan pada contoh yang sedikit terganggu hanya poli-logaritmik dalam jumlah kendala $n$ , turun dari $n^{86}$ .

Untuk memperoleh wawasan tentang analisis kasus simpleks kasus terburuk dan rata-rata, Anda harus membaca "Analisis Lancar: Mengapa Algoritma Simpleks Biasanya Membutuhkan Waktu Polinomial." oleh Spielman dan Teng.

Referensi yang baik tentang mengapa simplex tidak berjalan dalam waktu polinomial, daripada mengapa eksponensial adalah Papadimitriou & Steiglitz Combinatorial Optimization, Bagian 8.6 di mana mereka menunjukkan bahwa Simplex bukan algoritma waktu polinomial.

$D=200$

GLPK Simplex Optimizer, v4.65
200 rows, 200 columns, 20100 non-zeros
Preprocessing...
199 rows, 200 columns, 20099 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.607e+60  ratio =  1.607e+60
...
Constructing initial basis...
Size of triangular part is 199
*     0: obj =   0.000000000e+00 inf =   0.000e+00 (200)
*     1: obj = -6.223015278e+139 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 3.4 Mb

Adakah yang bisa menyarankan cara lain untuk membangun masalah yang sulit untuk metode simpleks, lambat tapi tidak terikat memori?

Ditambahkan: kotak Latin alias 3d-permutasi-matriks tampaknya memiliki banyak simpul - berapa banyak?
_{Teori dan praktik lebih dekat dalam teori daripada praktik.}

The original algoritma Simplex mungkin menyimpang; itu siklus pada contoh tertentu. Karenanya, tidak ada batasan umum. Jawaban lain memberi Anda jawaban untuk berbagai modifikasi dari algoritma Simplex.