Maafkan pertanyaan gondrong, itu hanya perlu penjelasan untuk sampai ke masalah yang sebenarnya. Mereka yang akrab dengan algoritma yang disebutkan mungkin bisa melompat langsung ke tablau simpleks pertama.
Untuk memecahkan masalah deviasi absolut minimal (alias -optimasi), algoritma Barrodale-Roberts adalah metode simpleks tujuan khusus yang membutuhkan penyimpanan jauh lebih sedikit dan upaya komputasi untuk menemukan minimum yang sesuai.
Implementasi saya terhadap algoritma berakhir pada contoh sederhana sebelum minimum yang tepat tercapai. Namun, mungkin izinkan saya menyatakan masalah dengan cara yang lebih rumit terlebih dahulu:
Diberikan data , optimasi mencoba menemukan yang meminimalkan mana adalah matriks yang tergantung pada . Masalah ini dapat dinyatakan sebagai program linier dan oleh karena itu antara lain dipecahkan menggunakan metode simplex-like.L 1 c ∈ m n ∑ i = 1 | y i - f ( x i ) |A x n × m x
Barrodale dan Roberts menyarankan modifikasi metode simpleks (yang tampaknya banyak digunakan) yang secara radikal menyederhanakan metode simpleks menggunakan struktur khusus masalah . Terutama, ini adalah bahwa solusi optimal interpolasi setidaknya dari titik data yang diberikan. Mereka yang memiliki akses Jstor dapat menemukan artikel yang sesuai di sini .r a n k ( A )
Lei dan Anderson pada tahun 2002 mengusulkan modifikasi kecil yang seharusnya meningkatkan stabilitas numerik dan karenanya untuk mengatasi masalah yang diketahui dengan algoritma simpleks.
Pada dasarnya, algoritma ini mengasumsikan bahwa Anda mulai dengan satu set poin tertentu yang harus diinterpolasi, menggunakan prosedur yang diberikan untuk membangun tabau simpleks dan kemudian menggunakan aturan Barrodale dan Roberts untuk memutuskan variabel basis mana yang akan diubah dan karenanya memodifikasi set datapoints yang diperkirakan.
Barrodale dan Roberts memberikan contoh kecil yang saya coba untuk reproduksi. Ia mencoba untuk memperkirakan poin dengan fungsi a 1 + a 2 x . Selesaikan algoritme mereka dengan tablo simpleks kental berikut:
Karena semua vektor nonbasic memiliki biaya marginal nonpositif [...]
iterasi selesai dan optimal tercapai.
Info tambahan: Jika saya mulai dengan tablo awal yang diberikan oleh Barrodale dan Roberts, saya juga dapat mereproduksi tablo di atas dengan langkah-langkah simpleks biasa, jadi saya cukup yakin bahwa nilai numerik aktual sudah benar dan interpretasi saya terhadap aturan pemilihan pivot salah.
Ada pemikiran tentang ini?
Saya menyadari bahwa pertanyaan itu sendiri cukup rumit dan mungkin membutuhkan pengetahuan setidaknya algoritma Barrodale dan Roberts untuk dijawab secara memadai. Algoritma secara keseluruhan adalah panjang untuk mengulanginya di sini dengan detail lengkap. Namun, jika Anda memiliki pertanyaan tambahan tentang langkah-langkah yang saya ambil atau informasi yang hilang, jangan ragu untuk bertanya dan saya dengan senang hati akan menambah pertanyaan.
Jawaban:
Selesaikan itu. Sebenarnya, Barrodale dan Roberts menyelesaikannya dan saya tidak membaca dengan cermat.
Jadi, tablo simpleks saya di atas harus dianggap sebagai berikut:
Terima kasih telah membaca dan memberi saya tempat untuk menuliskan masalah saya, yang biasanya membantu mempersempit solusinya secara signifikan. Semoga jawaban ini terkadang bermanfaat bagi siapa pun yang mencoba menerapkan Barrodale & Roberts.
sumber