Gomory metoade. De oplossing fan integer programmearring problemen

Gewicht problemen fan ekonomyske, planning en sels saken út oare sfearen fan it minsklik libben problemen ferbûn mei fariabelen ferbân mei integers. As gefolch fan harren analyze en it sykjen nei de bêste manieren om te pakken de noasje fan ekstreme útdagings. Syn eigenskippen is de boppesteande funksje nimt in hiele wearde werom, en de opjefte sels wurdt beskôge wiskunde as integer programmearring.

De wichtichste uses fan problemen mei fariabele, in hiel getal, is it optimalisearjen. In metoade dy't brûkt in hiel getal lineêre programmearring, ek neamd de besuniging-off metoade.

Gomory metoade waard neamd nei de wiskundige, earst ûntwikkele yn 1957-1958 algoritme is noch in soad brûkt om te oplosse hiele lineêre programmearring problemen. De kanonike foarm fan 'e hiele programmearring probleem kinne tagonklik en folslein bekend te meitsjen fan de foardielen fan dizze metoade.

Gomori metoade tapast oan in liniearre programmearring sterk complicates de taak fan it finen fan it optimale wearden. Nei yntegraliteit is in fûneminteel eask, fierder alle parameter fan it probleem. Der binne gefallen as it probleem troch it hawwen jildich (hiele) plannen, de oanwêzigens yn 'e objektive funksje fan beheiningen op' e admissible set, it beslút komt te realisearjen fan maksimaal. Dat komt troch it ûntbrekken fan is yntegraal oplossings. Sûnder deselde omstannichheden, as in regel, yn 'e foarm fan in beslút is passend vector.

Om rjochtfeardigje it numerike algoritmen foar oplossen fan problemen is der in ferlet om te fieren ekstra superimposition fan ferskillende omstannichheden.

Mei help fan de metoade fan Gomory, meastal beskôgje in protte plannen foar de saneamde probleem fan beheinde polyhedron oplossingen. Op grûn dêrfan, de dea fan alle yntegraal plan hat in einich wearde foar de taak.

Ek, hwent garantie yntegraal funksje der fan út dat de wearden fan de coefficients binne ek integers. Nettsjinsteande de earnst fan dizze omstannichheden, de swakkere se beheare in pear.

Gomory metoade yn wêzen giet it om gebou beheining, dat snije oplossings dy't net nonintegral. Yn dit gefal, der is gjin cut-off gjin hiel getal oplossingen plan.

De algoritme foar it oplossen fan it probleem dêrby om finen gaadlike opsjes Simplex metoade, sûnder rekken te hâlden mei de betingsten fan de yntegraliteit. As alle ûnderdielen fan it optimale plan befettet besluten yn ferbân mei integers, kin oannommen wurde dat de hiele programmearring doel wurdt berikt. Mooglik dat fûn wurdt insolubility fan it probleem, dus wy hawwe bewiis dat it hiele programmearring probleem hat gjin oplossing.

De fariant, doe't de ûnderdielen fan it optimale oplossing befettet net-hiel getal. Yn dit gefal, in nije beheining wurdt tafoege oan alle beheiningen fan it probleem. De nije beheinings wurde karakterisearre troch in tal eigenskippen. Earst fan alles, it moat wêze strekkende, moatte útroege wirde út it fûn set fan net-lizzende hiele getal optimale plan. Gjin fan beide hiel getal oplossing moat net ferlern, ôfsnien.

By de bou beheining moatte wurde keazen komponint fan in optimale plan mei it heechste fraksje. It is dit beheining sil taheakke wurde oan de besteande Simplex tafel.

Wy fine de oplossing fan it úteinlike probleem mei help fan konvinsjonele Simplex transformaasje. Wy kontrolearje de oplossing fan it probleem op it bestean fan in hiel getal optimale plan, as de foarwearde is tefreden, dan it probleem wurdt oplost. As it resultaat wie verkregen e nij mei de oanwêzigens fan net-hiele oplossingen, dan wy foarstelle in ekstra twang, en werhelje de berekkening proses.

Nei't útfierd in einich oantal werhellings, wy berikke in optimale programma fan it probleem posearre foar oantal hiele wearden programmearring, of bewize de insolubility fan it probleem.