| Bahasa : |
|
| Masyarakat ensiklopedia |Ensiklopedia Jawaban |Kirim pertanyaan |Pengetahuan kosakata |Upload pengetahuan |
Pemotongan Metode Pesawat |
|
Pemotongan Metode Pesawat Pemotongan Pesawat Ikhtisar Metode Pemotongan Metode Pesawat 1958 oleh ilmuwan Amerika Gao Morley (REGoMory) diusulkan untuk memecahkan seluruh metode integer programming relatif sederhana. Ide dasar dan metode branch and bound pada dasarnya sama, yang tidak dianggap kendala pembulatan variabel, sesuai dengan metode simpleks untuk memecahkan program linear. Jika menghasilkan solusi bilangan bulat yang optimal, maka itu juga asli masalah integer programming 3 Jika solusi optimal bukanlah solusi bilangan bulat yang optimal, maka metode branch and bound adalah untuk mengambil mengambil nilai pecahan dari variabel asli Xk = bk Pemrograman Integer dibagi menjadi dua, dan esensinya adalah dengan menggunakan dua sumbu tegak lurus paralel Xk = [bk] dan Xk = [bk] 1 original layak daerah R dibagi menjadi dua wilayah layak R1 dan R2, dan dua antara pesawat paralel tidak mengandung solusi bilangan bulat untuk menghapus bagian dari daerah feasible untuk mempersempit daerah feasible. Metode Pesawat pemotongan adalah dengan menggunakan pesawat (tidak harus tegak lurus terhadap sumbu), yang akan berisi titik solusi optimal, tetapi tidak berisi solusi layak integer yang merupakan bagian dari daerah layak dipotong, yang selama integer programming asli berdasarkan peningkatan kendala pertidaksamaan linear sesuai (kita sebut memotong ketidaksetaraan, ketika memotong ketika ketidaksetaraan dengan kesetaraan, disebut bidang pemotongan). Kemudian lanjutkan baru ini solusi integer programming, dan kemudian di integer programming baru berdasarkan kenaikan yang sesuai kendala pertidaksamaan linear, sampai mendapatkan solusi bilangan bulat yang optimal sejauh ini. Dengan kata lain, dengan membangun serangkaian pesawat untuk memotong solusi yang layak tidak berisi bagian bilangan bulat dan, pada akhirnya, sebuah sudut dengan bilangan bulat koordinat daerah layak, yang kebetulan integer solusi optimal asli vertex.Kunci untuk memotong metode pesawat, bagaimana membangun memotong kesenjangan, sehingga meningkatkan kendala dapat dicapai setelah memotong dan tidak memotong nyata dari setiap solusi layak integer. Langkah-langkah dasar untuk metode pemotongan pesawat (1) tidak dianggap kendala pembulatan variabel, sesuai dengan metode simpleks untuk memecahkan masalah pemrograman linear, jika masalahnya adalah bukan solusi yang layak atau solusi optimal bulat kemudian berhenti, jika tidak pergi ke langkah berikutnya. Dalam menyelesaikan program linier yang sesuai, pertama model asli matematika untuk standardisasi. Di sini "standar" memiliki dua makna: pertama penuh semua kendala ketimpangan menjadi kendala kesetaraan, itu karena Anda ingin dihitung dengan menggunakan demi tablo simpleks. Yang kedua adalah integer programming semua koefisien non-bulat semua dikonversi ke integer, yang dibuat dari "pemotongan ketidaksetaraan" kebutuhan. (2) mencari "ketidaksetaraan pemotongan" dan ditambahkan ke kendala integer programming untuk pergi, itu adalah linier pemrograman masalah layak daerah "cut", dan kemudian kembali ke langkah 1. Ide dasar dari metode pemotongan pesawat Dengan metode pesawat pemotongan untuk memecahkan bilangan bulat pemrograman Ide dasarnya adalah: kendala integer tidak dianggap, mencari relaksasi dari solusi optimal, jika integer memperoleh solusi optimal yang dicari, berhenti op. Jika solusi optimal bilangan bulat tidak memenuhi kendala, di mana solusi non-bilangan bulat berdasarkan menambahkan kendala baru kembali pemecahan. Ini peran baru meningkat kendala masalah relaksasi yang sesuai untuk memotong daerah feasible, yang memotong bagian dari slack solusi non-bilangan bulat masalah (termasuk yang asli telah menjadi solusi optimal non-integer). Dan semua solusi bilangan bulat yang diawetkan, sehingga kendala tambahan memotong pesawat. Setelah beberapa potong, itu akan membuat cut setelah ditahan daerah layak memiliki koordinat vertex adalah bilangan bulat, itu hanya pertanyaan yang diajukan untuk solusi optimal integer. Yaitu relaksasi yang sesuai setelah memotong masalah, dengan masalah pemrograman bilangan bulat asli telah solusi optimal yang sama. |
| Pemakai Ulasan |
|
Belum ada komentar |
