Cara Gomory. Penyelesaian masalah pengaturcaraan integer

masalah berat badan ekonomi, perancangan dan juga isu-isu dari bidang lain masalah kehidupan manusia yang dikaitkan dengan pembolehubah yang berkaitan dengan bilangan bulat. Hasil daripada analisis dan pencarian cara terbaik untuk menangani tanggapan cabaran yang melampau. ciri-fiturnya ciri di atas mengambil nilai integer, dan tugas itu sendiri dianggap matematik sebagai pengaturcaraan integer.

Kegunaan utama masalah dengan pembolehubah, integer, adalah pengoptimuman. Satu kaedah yang menggunakan integer pengaturcaraan linear, ia juga dipanggil kaedah cut-off.

Cara Gomory dinamakan sempena ahli matematik, mula dibangunkan pada 1957-1958 algoritma masih digunakan secara meluas untuk menyelesaikan integer masalah pengaturcaraan linear. Bentuk berkanun daripada masalah pengaturcaraan integer membolehkan diakses dan mendedahkan sepenuhnya kelebihan kaedah ini.

Cara Gomori digunakan untuk pengaturcaraan linear amat merumitkan tugas mencari nilai optimum. Selepas keutuhan adalah keperluan asas, selanjutnya semua parameter masalah. Terdapat kes di mana masalah dengan mempunyai sah (integer) pelan, kehadiran dalam fungsi objektif sekatan ke atas set yang boleh diterima, keputusan datang untuk mencapai maksimum. Ini adalah disebabkan oleh kekurangan itu adalah penyelesaian yang penting. Tanpa keadaan yang sama, sebagai peraturan, dalam bentuk keputusan adalah vektor sesuai.

Untuk membenarkan algoritma berangka untuk menyelesaikan masalah terdapat keperluan untuk menjalankan superimposition tambahan keadaan yang berbeza.

Menggunakan kaedah Gomory, biasanya kira banyak rancangan untuk masalah yang dipanggil penyelesaian polihedron terhad. Atas dasar ini, set semua pelan penting mempunyai nilai terhingga untuk tugas itu.

Juga, untuk jaminan fungsi penting menganggap bahawa nilai pekali juga integer. Walaupun keterukan keadaan ini, yang lebih lemah mereka menguruskan beberapa.

Cara Gomory dasarnya melibatkan sekatan bangunan, yang memotong penyelesaian yang tidak nonintegral. Dalam kes ini, tidak ada cut-off tidak ada pelan penyelesaian integer.

Algoritma untuk menyelesaikan masalah tersebut melibatkan mencari pilihan yang sesuai kaedah simplex, tanpa mengambil kira syarat-syarat keutuhan. Jika semua komponen pelan optimum mengandungi keputusan yang berkaitan dengan bilangan bulat, ia boleh dianggap bahawa matlamat pengaturcaraan integer dicapai. Mungkin yang terdapat tdk dpt memecahkan masalah ini, jadi kami mempunyai bukti bahawa masalah pengaturcaraan integer tidak mempunyai penyelesaian.

Varian, apabila komponen penyelesaian optimum mengandungi nombor bukan integer. Dalam kes ini, sekatan baru ditambah kepada semua kekangan masalah. Sekatan baru ini disifatkan oleh beberapa ciri-ciri. Pertama sekali, ia perlu linear, perlu dipotong dari set yang terdapat pelan yang optimum bukan integer. Tidak penyelesaian integer tidak boleh hilang, terputus.

Apabila membina sekatan harus dipilih komponen pelan optimum dengan pecahan tertinggi. Ia adalah had ini akan ditambah ke meja simplex yang sedia ada.

Kita dapati penyelesaian masalah yang terhasil menggunakan transformasi simplex konvensional. Kami menyemak penyelesaian masalah pada kewujudan pelan optimum integer, jika keadaan ini berpuas hati, maka masalah itu tidak diselesaikan. Jika keputusan telah diperolehi lagi dengan kehadiran penyelesaian bukan integer, maka kita memperkenalkan kekangan tambahan, dan mengulangi proses pengiraan.

Telah dijalankan beberapa terhingga lelaran, kita mencapai program optimum masalah yang ditimbulkan di hadapan pengaturcaraan integer, atau membuktikan tdk dpt memecahkan masalah.