Aðferð Homori. Leysa heiltölu forritunarmál

Massinn af vandamálum efnahagslegs eðlis, skipulagsvandamál og jafnvel lausn á spurningum frá öðrum sviðum mannlegs lífsstarfsemi tengist breytur sem vísa til heilunar. Sem afleiðing af greiningu þeirra og leit að ákjósanlegu lausnaraðferðum birtist hugtakið geislavandamál. Eiginleikar hennar eru ofangreindir eiginleikar til að taka heiltala og vandamálið sjálft er meðhöndlað í stærðfræði sem heiltalaforritun.

Helsta átt að nota verkefni með breytur sem taka heiltala gildi er hagræðing. A aðferð sem notar heiltala línuleg forritun er einnig kallað úrklippur aðferð.

Aðferðin um Homori fékk nafn sitt með nafni stærðfræðings, sem fyrst þróaði árið 1957-1958 reikniritið, sem enn er mikið notað til að leysa heiltala línuleg forritunarmál. The Canonical form heildar forritun vandamál gerir það mögulegt að fullu uppgötva kosti þessa aðferð.

Gomori aðferðin fyrir línuleg forritun verulega flækir vandamálið við að finna bestu gildi. Eftir allt saman, heiltala er aðalskilyrði, auk allra breytur vandans. Það er ekki óalgengt að það sé vandamál, þegar það er hægt að gera (heiltala) áætlun, ef hlutverkið hefur takmarkanir á viðurkenndum setu, nær lausnin ekki til hámarks. Þetta er vegna skorts á heiltala. Án þessarar sömu ástands, að jafnaði er hentugur vigur í formi lausnar.

Til að rökstyðja tölulegar reiknirit við lausn vandamála verður nauðsynlegt að leggja fram ýmis viðbótarskilyrði.

Með því að nota Gomori-aðferðin er venjulega talið að umfang hugsanlegra áætlana sé takmörkuð svokölluð fjölgun lausna. Í kjölfarið kemur fram að settur af öllum óaðskiljanlegum áætlunum fyrir viðkomandi vandamál hefur endanlegt gildi.

Einnig er gert ráð fyrir að stuðull gildi séu einnig heiltölur til að tryggja heildarhlutverk virkni. Þrátt fyrir alvarleika slíkra aðstæðna er hægt að senda þau svolítið.

Aðferðin við Homori felur í raun í sér byggingu þvingunar sem skera úr ákvörðunum sem eru ekki heiltala. Í þessu tilviki er engin niðurskurður á neinum lausn á heiltala-metin áætlun.

Reikniritið til að leysa vandamálið felur í sér að finna viðeigandi afbrigði með simplex aðferðinni, án þess að taka tillit til heildaraðstæðna. Ef í öllum þáttum ákjósanlegra áætlana eru lausnir sem tengjast heilum, þá getum við gert ráð fyrir að markmiðið með heildarforritun sé náð. Það er mögulegt að undecidability vandamálið verði ljós, þannig að við fáum sönnun þess að heiltala forritunarmálið hafi engin lausn.

Afbrigði er mögulegt þegar ekki eru heilar tölur í hlutum ákjósanlegasta lausnin. Í þessu tilfelli er nýr takmörkun bætt við allar takmarkanir verkefnisins. Ný takmörkun einkennist af því að fjöldi eigna er til staðar. Fyrst af öllu, það verður að vera línulegt, það verður að skera burt heiltala áætlun frá ákjósanlegur sett fannst. Engin ein heildarlausn ætti að týnast, skera burt.

Þegar þú ert að byggja upp þvingunina ættir þú að velja hluti af ákjósanlegri áætluninni með stærsta brothlutanum. Það er þessi takmörkun sem verður bætt við núverandi simplex töflunni.

Við finnum lausnin á því sem fæst með venjulegum einfaldar umbreytingum. Við athugum lausn á vandamálinu fyrir tilvist heiltala ákjósanlegrar áætlunar, ef ástandið er fullnægt þá er vandamálið leyst. Ef aftur var niðurstaðan með nærveru óheilbrigða lausna, þá kynnum við viðbótar takmörkun, og við endurtekum ferlið við útreikninga.

Við höfum náð endanlegum fjölda endurtekninga, við fáum bestu áætlun fyrir vandann sem stafar fyrir heiltalaforritun eða við sönnur á óleysanleika vandans.