Gomory арга. бүхэл програмчлалын асуудлын шийдэл

эдийн засаг, төлөвлөлт жин асуудал, тэр ч байтугай бүхэл холбоотой хувьсагч холбоотой хүний амь нас асуудлын бусад салбарт нь асуудал. Тэдний судалгааны үр, нэн тулгамдсан ойлголтыг шийдвэрлэх хамгийн сайн арга замыг хайж байна. Түүний онцлог нь дээр дурдсан онцлог нь бүхэл утга авдаг бөгөөд ажил нь өөрөө бүхэл програмчлал зэрэг математик үздэг.

хувьсагч нь бүхэл тоо нь асуудлын гол хэрэглээ, оновчтой юм. бүхэл тоо ашигладаг арга шугаман програмчлал, мөн захын арга гэж нэрлэдэг.

Gomory аргыг анх одоо ч гэсэн өргөн бүхэл шугаман програмчлалын асуудлыг шийдэхийн тулд ашиглаж байгаа 1957-1958 алгоритм боловсруулж, математикч нэрэмжит юм. бүхэл програмчлалын асуудлын Дүрмийн дагуу ийм хэлбэртэй хялбар боломжийг олгодог ба бүрэн Энэ аргын давуу талыг тодруулах.

Шугаман програмчлалын хэрэглэж Gomori арга нь хамгийн оновчтой утгыг олох ажлыг ихээхэн төвөгтэй болгодог. integrality дараа нь үндсэн шаардлага, асуудал улам л параметрүүд байдаг. хүчинтэй (бүхэл тоо) төлөвлөгөө байснаар асуудал-д оролцох үед тохиолдол байдаг бодит үйл ажиллагаа боломжийн багц дээр хязгаарлалт, шийдвэр хамгийн их хүрэх ирдэг. нь энэ тухай байхгүй салшгүй арга зам байна Энэ нь холбоотой юм. ижил нөхцөлд ямар ч ёс мэт, шийдвэрийн хэлбэрээр зохих вектор юм.

асуудлыг шийдвэрлэх янз бүрийн нэмэлт нөхцөл давхцсан хэрэгжүүлэх шаардлага гарч тоон алгоритмыг зөвтгөх.

Gomory аргыг ашиглах нь, ихэвчлэн хязгаарлагдмал polyhedron шийдлийн асуудал гэж нэрлэгддэг олон төлөвлөгөөг авч үзье. Үүний үндсэн дээр бүх салшгүй төлөвлөгөөний багц үүрэг нь хязгаарлагдмал утгатай байна.

Мөн баталгаат салшгүй үйл ажиллагаанд итгэлцүүрийн утга нь мөн бүхэл тоо байна гэж бодъё. Эдгээр нөхцөл байдал ноцтой байгаа хэдий ч, сул дорой нь тэд хэд хэдэн удирдах.

Gomory арга нь үндсэндээ барилгын хязгаарлалт, nonintegral биш юм шийдлүүдийг бууруулах явдал юм. Энэ тохиолдолд, ямар ч тасалбар ямар ч бүхэл шийдэл төлөвлөгөө байдаг.

асуудлыг шийдвэрлэх алгоритм тохиромжтой хувилбаруудыг олох явдал , Энгийн арга нь харгалзан integrality нөхцөл авахгүйгээр. оновчтой төлөвлөгөөний бүх бүрэлдэхүүн хэсэг бүхэл холбоотой шийдвэр агуулж байвал энэ нь бүхэл програмчлалын зорилго хүрч байна гэж үзэж болох юм. Магадгүй тэр асуудлын insolubility байдаг, тиймээс бид бүхэл програмчлалын асуудал нь ямар ч шийдэл гэдгийн баталгаа юм.

хувилбар, оновчтой шийдэл бүрэлдэхүүн хэсэг бус бүхэл тоог агуулна. Энэ тохиолдолд, шинэ хязгаарлах асуудлын бүх саад нэмж байна. Шинэ хязгаарлалт шинж чанар нь хэд хэдэн онцлогтой байна. Юуны өмнө, энэ нь шугаман байх ёстой, төрийн бус бүхэл оновчтой төлөвлөгөөний олж багц таслагдах ёстой. Аль аль нь бүхэл шийдэл таслагдах, алдаж болохгүй.

Барилгын хязгаарлалт хамгийн фракц нь оновчтой төлөвлөгөөний бүрэлдэхүүн сонгосон үед байх ёстой. Энэ хязгаарлалт нь одоо байгаа Энгийн ширээн нэмэгдэх болно юм.

Бид уламжлалт Энгийн өөрчлөлтийг ашиглан үр дүнд асуудлын шийдлийг олж болно. Бид бүхэл оновчтой төлөвлөгөөний үндсэн дээр асуудлын шийдлийг шалгаж, нөхцөл байдал сэтгэл хангалуун байгаа бол, дараа нь асуудал шийдэгдээгүй байна. үр дүн бус бүхэл шийдэл байлцуулан дахин авч байсан бол, дараа нь бид нэмэлт хязгаарлалт нэвтрүүлэх, тооцоо үйл явцыг давтана.

давталтаас нь хязгаарлагдмал тооны явуулж дараа бид бүхэл програм өмнө тавьсан асуудлыг оновчтой хөтөлбөрийг хэрэгжүүлэх, эсвэл асуудлын insolubility харуулж байна.