Dull Gomory. Ddatrys problemau rhaglennu gyfanrif

Problemau Pwysau o economaidd, cynllunio a hyd yn oed materion o gylchoedd eraill o broblemau bywyd dynol sy'n gysylltiedig â newidynnau sy'n gysylltiedig â gyfanrifau. O ganlyniad i'w dadansoddiad a'r ymchwil am y ffyrdd gorau o fynd i'r afael â'r syniad o heriau eithafol. Mae ei nodweddion yn nodwedd uchod yn cymryd gwerth cyfanrif, ac mae'r dasg ei hun yn cael ei ystyried fel mathemateg rhaglennu cyfanrif.

Y prif ddefnydd o broblemau gyda amrywiol, yn gyfanrif, yw'r optimization. Dull sy'n defnyddio cyfanrif rhaglennu llinol, a elwir yn y dull torbwynt hefyd.

Dull Gomory ei enwi ar ôl y mathemategydd, a ddatblygwyd gyntaf yn 1957-1958 algorithm yn dal i defnyddio'n eang i ddatrys problemau rhaglennu llinol cyfanrif. Mae ffurf canonaidd y broblem rhaglennu cyfanrif caniatáu hygyrch a datgelu yn llawn fanteision y dull hwn.

Dull Gomori gymhwyso i raglennu llinellol cymhlethu'r fawr y dasg o ddod o hyd i'r gwerthoedd gorau posibl. Ar ôl integrality yn ofyniad sylfaenol, ymhellach pob paramedr o'r broblem. Mae yna achosion pan fydd y broblem drwy gael cynlluniau dilys (gyfanrif), presenoldeb yn y swyddogaeth gwrthrychol o gyfyngiadau ar y set dderbyniol, mae'r penderfyniad yn dod i gyflawni uchafswm. Mae hyn oherwydd y diffyg ei fod yn atebion annatod. Heb yr un amodau, fel rheol, ar ffurf penderfyniad yn fector priodol.

Er mwyn cyfiawnhau y algorithmau rhifiadol ar gyfer datrys problemau, mae angen i gyflawni superimposition ychwanegol o gyflyrau gwahanol.

Gan ddefnyddio'r dull o Gomory, fel arfer yn ystyried llawer o gynlluniau ar gyfer y broblem yn hyn a elwir o atebion polyhedron cyfyngedig. Ar y sail hon, mae'r set o bob cynllun integrol werth cyfyngedig ar gyfer y dasg.

Hefyd, ar gyfer swyddogaeth hanfodol warant cymryd yn ganiataol bod y gwerthoedd y cyfernodau hefyd gyfanrifau. Er gwaethaf difrifoldeb y cyflyrau hyn, mae'r wannach maent yn eu rheoli ychydig.

Dull Gomory ei hanfod yn golygu cyfyngiadau adeiladu, sy'n torri ar atebion nad ydynt yn nonintegral. Yn yr achos hwn, nid oes terfyn oes cynllun atebion cyfanrif.

Mae'r algorithm ar gyfer datrys y broblem yn ymwneud â dod o hyd i opsiynau addas dull simplecs, heb gymryd i ystyriaeth yr amodau integrality. Os yw pob elfen o'r cynllun gorau posibl yn cynnwys penderfyniadau sy'n ymwneud â gyfanrifau, gellir cymryd yn ganiataol bod y nod rhaglennu cyfanrif yn cael ei gyflawni. Efallai sydd i'w gael anhydoddedd y broblem, felly mae gennym brawf bod y broblem rhaglennu cyfanrif nid oes ateb.

Mae'r amrywiad, pan fydd y cydrannau o'r ateb gorau posibl yn cynnwys rhif di-cyfanrif. Yn yr achos hwn, mae cyfyngiad newydd yn cael ei ychwanegu at yr holl gyfyngiadau y broblem. Mae'r cyfyngiadau newydd yn cael eu nodweddu gan nifer o eiddo. Yn gyntaf oll, dylai fod yn llinol, gael eu torri i ffwrdd o'r set o hyd nad ydynt yn cyfanrif cynllun gorau posibl. Ni ddylai Nid ateb cyfanrif yn cael ei golli, ei dorri i ffwrdd.

Pryd y dylid cyfyngiadau adeiladu yn cael eu dewis elfen o'r cynllun gorau posibl gyda'r ffracsiwn uchaf. Mae'n Bydd cyfyngiad hwn yn cael ei ychwanegu at y tabl simplex presennol.

Rydym yn dod o hyd i'r ateb y broblem yn deillio gan ddefnyddio trawsnewid simplex confensiynol. Rydym yn gwirio yr ateb y broblem ar fodolaeth cynllun gorau posibl cyfanrif, os yw'r cyflwr yn cael ei fodloni, yna bydd y broblem wedi'i datrys. Os bydd y canlyniad cafwyd eto gyda phresenoldeb atebion nad ydynt yn cyfanrif, yna rydym yn cyflwyno cyfyngiad ychwanegol, ac ailadrodd y broses gyfrifo.

Ar ôl cynnal nifer cyfyngedig o iteriadau, rydym yn cyflawni rhaglen gorau posibl o'r broblem a achosir o flaen raglennu cyfanrif, neu brofi anhydoddedd y broblem.