Gomory paraan. Ang solusyon ng integer problema programming

Timbang problema ng pang-ekonomiya, pagpaplano at kahit na mga isyu mula sa iba pang mga spheres ng tao ang mga problema sa buhay na nauugnay sa mga variable na may kaugnayan sa integer. Bilang resulta ng kanilang pag-aaral at ang paghahanap para sa ang pinakamahusay na paraan upang matugunan ang paniwala ng matinding hamon. mga tampok nito ay ang tampok na ito sa itaas ay tumatagal ng isang integer value, at ang gawain mismo ay regarded matematika bilang integer programming.

Ang pangunahing gamit ng problema sa variable, isang integer, ay ang pag-optimize. Ang isang pamamaraan na gumagamit ng isang integer linear programming, tinatawag din na ang cut-off na paraan.

Gomory paraan ay pinangalanang matapos ang mathematician, unang binuo sa 1957-1958 algorithm pa rin ang malawakang ginagamit upang malutas ang integer problema sa guhit programming. Ang canonical form ng problema integer programming nagbibigay-daan sa madaling i-access at ganap na ibunyag ang mga bentahe ng ang paraan na ito.

Gomori pamamaraan na inilapat sa isang linear programming lubos na complicates ang gawain ng paghahanap ng optimal na halaga. Pagkatapos ng pagkabuo ay isang pangunahing kinakailangan, karagdagang ang lahat ng mga parameter ng problema. May mga kaso kapag ang problema sa pamamagitan ng pagkakaroon ng wasto (integer) plano, ang presensya sa ang layunin function ng mga paghihigpit sa admissible set, ang desisyon pagdating sa pagkamit ng maximum. Ito ay dahil sa ang kakulangan ng ito ay integral solusyon. Kung wala ang parehong mga kondisyon, bilang isang panuntunan, sa anyo ng isang desisyon ay angkop vector.

Upang bigyang-katwiran ang de-numerong algorithm para sa paglutas ng mga problema diyan ay a kailangan upang magsagawa ng mga karagdagang superimposition ng iba't ibang mga kundisyon.

Paggamit ng mga pamamaraan ng Gomory, kadalasang isaalang-alang ang maraming mga plano para sa ang tinatawag na problema ng limitadong solusyon polyhedron. Sa batayan na ito, ang hanay ng lahat ng mahalagang plano ay may takda na halaga para sa gawain.

Gayundin, para sa warranty integral function na ipinapalagay na ang mga halaga ng mga coefficients ay integers din. Sa kabila ng kalubhaan ng mga kondisyon, ang weaker pinamamahalaan nila ang ilang.

Gomory paraan mahalagang nagsasangkot paghihigpit gusali, na kung saan i-cut mga solusyon na ay hindi nonintegral. Sa kasong ito, walang cut-off walang integer solusyon plano.

Ang algorithm para sa paglutas ng problema ay nagsasangkot ng paghahanap ng mga naaangkop na mga pagpipilian simplex method, nang hindi isinasaalang-alang ang mga kondisyon ng pagkabuo. Kung ang lahat ng mga bahagi ng ang pinakamainam na plano ay naglalaman ng mga desisyon na may kaugnayan sa integer, maaari itong ipinapalagay na ang integer programming layunin ay nakakamit. Marahil na natagpuan kawalan ng kayang matutunaw ang problema, kaya kami ay may patunay na ang integer programming problema ay walang solusyon.

Ang variant, kapag ang mga bahagi ng ang pinakamainam na solusyon ay naglalaman na numero non-integer. Sa kasong ito, ang isang bagong paghihigpit ay idinagdag sa lahat ng mga hadlang ng problema. Ang bagong mga paghihigpit ay nailalarawan sa pamamagitan ng isang bilang ng mga katangian. Una sa lahat, dapat itong maging linear, ay dapat na i-cut off mula sa mga nahanap na hanay ng mga non-integer optimal plano. Wala alinman sa integer solusyon ay hindi dapat mawala, gupitin off.

Kapag bumuo ng mga paghihigpit ay dapat na pinili sangkap ng isang pinakamainam na plano na may pinakamataas na bahagi. Ito ay ang limitasyong ito ay idadagdag sa mga umiiral simplex table.

Nakakatagpo kami ng mga solusyon sa mga nagresultang problema sa paggamit ng maginoo simplex transformation. Nagsusuri kami ang solusyon ng problema sa pag-iral ng isang integer pinakamainam na plano, kung ang mga kondisyon ay nasiyahan, pagkatapos ay ang problema ay malulutas. Kung ang resulta ay natamo muli sa pagkakaroon ng mga solusyon non-integer, at pagkatapos ay kami ay kitang ipakilala sa isang karagdagang pagpilit, at ulitin ang proseso ng pagkalkula.

Ang pagkakaroon ng isinasagawa ng isang may hangganan bilang ng mga iteration, kami makamit ang isang pinakamainam na programa ng problema na ibinabanta sa harap ng integer programming, o patunayan ang kawalan ng kayang matutunaw ang problema.