Habka Gomory. Xalka dhibaatooyinka barnaamijyada abyoonaha

Dhibaatooyinka Miisaanka of dhaqaalaha, qorshaynta iyo xitaa arrimaha ka dhinacyo kale oo dhibaatooyinka nolosha aadanaha la xidhiidha doorsoomayaasha la xiriira abyoonayaasha. Sidaas darteed ka mid ah falanqaynta iyo search for hababka ugu fiican ee si wax looga qabto fikradda ah caqabado xad-dhaaf ah. Tilmaamo Its waa feature kor ku qaadataa qiimaha abyoonaha ah, iyo hawl laftiisa waxaa loo arkaa xisaabta sida barnaamij abyoonaha.

The isticmaalka ugu weyn ee dhibaatooyinka la variable, abyoonaha ah, waa ayna ku. Habka A isticmaala ah abyoonaha barnaamijyada toosan, sidoo kale loo yaqaan habka cut-off.

Habka Gomory ayaa loo magacaabay ka dib markii xisaabyahan ah, hore u samaysay 1957-1958 geynta ayaa weli si weyn loo isticmaalaa in lagu xalliyo dhibaatooyinka barnaamijyada toosan abyoonaha. Foomka qaadanin ee dhibaatada barnaamijyada abyoonaha ogol yahay la heli karo oo si buuxda shaaca uga faa'iidooyinka ee habkan.

Habka Gomori codsatay in barnaamijyada toosan si weyn u adkaynaysaa hawsha helo qiimaha fiicnayn. Ka dib markii integrality waa shardi asaasi ah, dheeraad ah kasta oo lagu cabbiro dhibaatada. Waxaa jira xaalado marka dhibaatada adigoo sax ah qorshaha (abyoonaha), joogitaanka ee shaqada Ujeedada of xayiraad on set ah oggolaan karo, go'aanka u imanayaa inuu gaaro ugu badnaan. Tan waxa u sabab la'aanta ah waxaa ka mid ah waa xal lagama maarmaan. Haddii aan isla shuruudaha, sida caadiga ah, oo ah qaab go'aan waa dulinka ku haboon.

Si aad qiil u algorithms tiro xallinta dhibaatooyinka waxaa loo baahan yahay si ay u fuliyaan superimposition dheeraad ah oo xaaladaha kala duwan.

Isticmaalka habka of Gomory, sida caadiga ah ka fiirsan qorshayaal badan oo dhibaato loogu yeero of xal polyhedron kooban. Iyadoo ku saleysan, set qorshaha muhiim oo dhan uu qiimo ah uguna waayo hawsha.

Sidoo kale, waayo, damaanad shaqo muhiim u qaadan in qiyamka horgalaha ah ayaa sidoo kale abyoonayaasha. Inkastoo darnaanta xaaladahan, taagta daran ay u maareeyaan yar.

Habka Gomory muhiimad ku lug xayiraad dhismaha, taas oo xal aan nonintegral gooyay. Xaaladdan oo kale, ma jiraan wax cut-off ma xal abyoonaha qorshaha.

geynta ee xalinta dhibaatada saabsantahay helitaanka fursadaha ku haboon habka simplex, iyada oo aan la tixgelinayo shuruudaha integrality. Haddii dhammaan qaybaha qorshaha fiicnayn ka kooban yahay go'aamada la xiriira abyoonayaasha, waxa la malaysan karo in goolkii barnaamijyada abyoonaha la gaaray. Waxaa laga yaabaa in la helay insolubility dhibaatada, sidaasi darteed waa inaan cadeyn u tahay in dhibaato barnaamijyada abyoonaha uu leeyahay xal lahayn.

duwanaansho The, marka qaybaha oo xal ah aan fiicnayn ku jira tiro aan abyoonaha. Xaaladdan oo kale, xannibaad cusub ku daray in ay dhammaan caqabadaha dhibaatada. The xayiraad cusub waxaa lagu gartaa tiro ka mid ah guryaha. First of dhan, waa inay noqdaan toosan, waa in laga gooyaa ballamay ka heshay oo ah non-abyoonaha qorshe aan fiicnayn. xal abyoonaha Midkoodna waa in aan la lumay, iska jar.

Marka xayiraad dhismaha waa in la doortay qaybaha kala duwan ee qorshaha fiicnayn la jajab ugu sareeya. Waa xaddidaadda this lagu dari doonaa miiska simplex jira.

Waxaan ka heli xalka dhibaatada keentay iyadoo la isticmaalayo Isbadal simplex caadiga ah. Waxaan ku baarnaa xalka dhibaatada on jiritaanka qorshe fiicnayn abyoonaha ah, haddii xaaladda ka dherga, ka dibna dhibaatada la xalin. Haddii natiijada waxaa mar kale helay iyadoo ay goobjoog ka ahaayeen xal aan abyoonaha, ka dibna aan soo bandhigno caqabadda oo dheeraad ah, oo ay ku soo celiyaan nidaamka xisaabinta.

Iyadoo ay fuliyeen dhowr uguna of iterations, waxaan gaaro barnaamij aan fiicnayn ee dhibaatada ku hayaan hore ee barnaamijyada abyoonaha, ama caddeeyaan insolubility dhibaatada.