Stabilitas numerik metode Simplex

12

Algoritma simpleks sering diperlakukan baik dalam aritmatika nyata, atau dalam dunia diskrit dengan perhitungan yang tepat. Namun, tampaknya paling sering diterapkan dengan aritmatika floating-point.

Ini mengarah pada pertanyaan apakah algoritma simpleks harus dianggap sebagai algoritma numerik, khususnya bagaimana kesalahan pembulatan mempengaruhi perhitungan. Saya tidak tertarik pada implementasi praktis, tetapi lebih pada fondasi teoritis.

Apakah Anda mengetahui adanya penelitian tentang masalah ini?

ds.algorithms reference-request optimization linear-programming na.numerical-analysis shuhalo
sumber
1
Jika Anda tertarik pada implementasi algoritma simpleks, maka saya akan menyarankan Anda untuk mengajukan pertanyaan di or-exchange.com
Snowie
@Snowie: Pertanyaan ini kurang tentang implementasi praktis tetapi lebih pada aspek teoritis. Telah ada pekerjaan dalam dasar-dasar teoritis analisis numerik, dan saya bertanya-tanya apakah itu telah mempengaruhi teori algoritma simpleks. Bagaimanapun, terima kasih untuk tautannya.
shuhalo
Saya telah mengedit pertanyaan untuk membuat minat saya lebih jelas.
shuhalo
3
Sudahkah Anda melihat analisis yang dihaluskan ? Pekerjaan ini tidak hanya membahas waktu berjalan rata-rata kasus, tetapi juga stabilitas kasus rata-rata.
Peter Shor

Jawaban:

3

Ya, ada penelitian tentang masalah ini.

Metode Simplex Tidak Selalu Berperilaku Baik , Wlodzimierz Ogryczak

retroLP, Implementasi Metode Simpleks Standar , Gavriel Yarmish dan Richard Van Slyke

Suatu Bentuk Algoritma Simplex yang Numerik Stabil , Philip E. Gill dan Walter Murray

Anda mungkin juga tertarik dengan metode simpleks yang direvisi . Metode ini dapat memanfaatkan sparsity matriks; itu tidak menyimpan representasi dari seluruh matriks. Tesis ini sangat menarik bagi saya: Perbandingan Algoritma Metode Simpleks .

jnm2
sumber