Ano ang integer linear programming?

Ang mga problema sa pag -programming ng integer ay lumitaw kapag sinusubukan na malutas ang mga linear system habang tinukoy na ang lahat ng hindi kilalang mga variable ay dapat na mga integer, o buong numero.Ang mga linear system ay mga hanay ng mga equation na naglalarawan ng isang sitwasyon kung saan sinusubukan ng programmer na makahanap ng solusyon.Karaniwan silang binubuo ng isang equation na dapat na ma -maximize o mai -minimize at isa o higit pang paghihigpit na equation na naglalagay ng mga limitasyon sa hindi kilalang mga variable.Para maging linear ang system, ang bawat paghihigpit ay dapat na isang linear equation;Iyon ay, hindi ito dapat maglaman ng mga pagkakataon ng hindi kilalang variable na may mga exponents na mas malaki kaysa sa isa.

Ang mga regular na linear system ay maaaring malutas nang madali gamit ang isang computer.Ang programa ay maaaring makilala ang isang solusyon sa pamamagitan ng paghahanap ng derivative at pagtatakda nito na katumbas ng zero.Pagkatapos ay maaari itong i -verify na ang punto ay isang maximum o minimum sa pamamagitan ng pagsuri sa agarang kapitbahayan nito sa pagpapaandar.Hangga't ang derivative ay tinukoy sa bawat punto kasama ang pag -andar, ang computer ay may isang limitadong bilang lamang ng mga posibleng solusyon upang suriin.Nangangahulugan ito na ang problema ay nananatiling pareho, ngunit ang sagot ay dapat na binubuo ng mga halaga ng integer para sa mga hindi kilalang mga halaga: dapat silang maging buong numero.Minsan, nangangahulugan ito na ang solusyon ay magiging suboptimal kumpara sa kaso kung saan pinapayagan ang mga praksyon;Ito ay sumasalamin, gayunpaman, ng totoong mundo, kung saan ang mga item ay madalas na nagmumula sa mga yunit na hindi mahahati.Ginagawa nitong mahalaga ang integer linear programming para sa mga aplikasyon ng negosyo, dahil nais ng mga kumpanya na i -maximize ang kita hangga't maaari ngunit hindi mapili na magbenta ng isang bahagi ng isang produkto.

Kapag ang mga paghihigpit ng integer ay nasa lugar, ang problema sa paglutas ng linear system ay NP-Plete.Nangangahulugan ito na ang oras na kinakailangan para sa isang computer upang malutas ang system ay hindi tiyak.Sa mga paghihigpit ng integer, hindi maaaring gamitin ng mga computer ang tool ng derivative dahil walang garantiya na ang zero point ng derivative ay mahuhulog sa isang integer.Ang solusyon ay ang integer na may pinakamataas o pinakamababang halaga sa lahat ng mga integer, kaya kailangang suriin ng computer ang lahat ng mga ito at mdash;Ang isang proseso na maaaring tumagal ng isang walang hanggan na oras.Ang isang paraan ng paglutas ng mga problema sa pag -programming ng integer ay ang sangay at nakatali sa algorithm, kung saan nalulutas ng computer ang isang serye ng mga problema na may kaugnayan sa orihinal na isa upang paliitin ang magagamit na hanay ng mga halaga sa isang solusyon.Para sa mga kumplikadong problema, gayunpaman, maaari itong tumagal ng mahabang panahon.