Metode van Homori. Oplossing van heelgetalprogrammeringsprobleme

Die massa probleme van ekonomiese aard, beplanningsprobleme en selfs die oplossing van vrae uit ander sfere van menslike lewensaktiwiteit hou verband met veranderlikes wat verwys na heelgetalle. As gevolg van hul analise en die soeke na optimale oplossingsmetodes, het die konsep van 'n ekstrem probleem verskyn. Sy eienskappe is die bogenoemde kenmerk om 'n heelgetalwaarde te neem en die probleem self word in wiskunde as integerprogrammering behandel.

Die hoof rigting van die gebruik van take met veranderlikes wat integerwaardes neem, is optimalisering. 'N Metode wat integer lineêre programmering gebruik, staan ook bekend as die knip metode.

Die metode van Homori het sy naam gekry onder die naam van wiskundige, wat in 1957-1958 die algoritme ontwikkel het, wat nog wyd gebruik word vir die oplos van integer lineêre programmeringsprobleme. Die kanonieke vorm van die integerprogrammeringsprobleem maak dit moontlik om die voordele van hierdie metode ten volle te ontdek.

Die Gomori-metode vir lineêre programmering kompliseer die probleem van optimale waardes aansienlik. Na alles, integer is die hoofvoorwaarde, benewens al die parameters van die probleem. Dit is nie ongewoon vir 'n probleem nie. As 'n uitvoerbare (heelgetal) plan bestaan, kan die oplossing nie die maksimum bereik as die objektiewe funksie beperk is tot 'n toelaatbare stel nie. Dit is as gevolg van die afwesigheid van heelgetaloplossings. Sonder dieselfde toestande is 'n geskikte vektor in die vorm van 'n oplossing.

Om numeriese algoritmes in die oplossing van probleme te staaf, word dit nodig om verskeie addisionele toestande te oorbrug.

Met behulp van die Gomori-metode word die stel probleemoplossings gewoonlik beskou as 'n begrensde sogenaamde polytoop van oplossings. Daaruit volg dat die stel van alle integrale planne vir die betrokke probleem 'n eindige waarde het.

Om die integeriteit van 'n funksie te verseker, word ook aanvaar dat die koëffisiëntwaardes ook heelgetalle is. Ten spyte van die erns van sulke toestande, kan hulle na 'n bietjie gestuur word.

Die metode van Homori behels inderdaad die konstruksie van beperkings wat besluite wat nie-heelgetal is, afsny. In hierdie geval is daar geen oplossing vir die integer-gewaardeerde plan nie.

Die algoritme vir die oplossing van die probleem behels die vind van die toepaslike variante deur die simplex-metode, sonder om die integer-toestande in ag te neem. As daar in alle komponente van die optimale plan oplossings is wat verband hou met heelgetalle, dan kan ons aanvaar dat die doel van heelgetalprogrammering behaal is. Dit is moontlik dat 'n onbeslisbaarheid van die probleem bekend sal word, so ons kry 'n bewys dat die integerprogrammeringsprobleem geen oplossing het nie.

'N Variant is moontlik as daar nie-heelgetalle in die komponente van die optimale oplossing is nie. In hierdie geval word 'n nuwe beperking bygevoeg aan al die beperkinge van die taak. 'N nuwe beperking word gekenmerk deur die teenwoordigheid van 'n aantal eienskappe. Eerstens moet dit lineêr wees, dit moet die nie-heelgetalplan afsny van die optimale stel wat gevind word. Geen enkele heelgetal oplossing moet verlore gaan nie, afgesny word.

By die konstruksie van die beperking, moet u die komponent van die optimale plan kies met die grootste breukdeel. Dit is hierdie beperking wat by die bestaande simplex-tabel gevoeg sal word.

Ons vind die oplossing van die opgeloste probleem met behulp van gewone simplex-transformasies. Ons kyk na die oplossing van die probleem vir die teenwoordigheid van 'n integer-optimale plan, indien die toestand tevrede is, dan is die probleem opgelos. As die resultaat weer verkry is met die teenwoordigheid van nie-heelgetalle oplossings, dan stel ons 'n addisionele beperking in, en ons herhaal die proses van berekeninge.

Nadat ons 'n eindige aantal iterasies uitgevoer het, kry ons 'n optimale plan vir die probleem wat voor integerprogrammering gestel word, of die onoplosbaarheid van die probleem bewys.