Gomory metode. Løsningen av heltall programmeringsproblemer

Vekt problemer av økonomisk, planlegging og til og med problemer fra andre områder av menneskelige livsproblemer forbundet med variabler knyttet til heltall. Som et resultat av deres analyse og jakten på de beste måtene å håndtere begrepet ekstreme utfordringer. Dens funksjoner er over funksjonen tar en heltallsverdi, og oppgaven i seg selv anses matematikk som heltall programmering.

Den viktigste bruk av problemene med variabel, et helt tall, er optimaliseringen. En fremgangsmåte som benytter et helt tall lineær programmering, også kalt cut-off-metode.

Gomory metoden ble oppkalt etter matematikeren, først utviklet i 1957-1958 algoritmen er fortsatt mye brukt for å løse heltall lineær programmering problemer. Kanonisk form av heltallsprogrammering problem lar tilgjengelig og fullt ut beskriver fordelene ved denne metode.

Gomori-metoden anvendes på en lineær programmering kompliserer sterkt oppgaven med å finne de optimale verdier. Etter integrality er et grunnleggende krav, videre alle parametere av problemet. Det finnes tilfeller der problemet ved å ha gyldige (heltall) planer, tilstedeværelse i objektivfunksjonen av restriksjoner på tillatte settet, kommer beslutningen om å oppnå maksimal. Dette er på grunn av mangel på det er integrerte løsninger. Uten de samme betingelser, som regel i form av en avgjørelse er egnet vektor.

For å rettferdiggjøre de numeriske algoritmer for å løse problemer er det behov for å gjennomføre ytterligere superimposition av ulike forhold.

Bruke metoden for Gomory, vanligvis vurdere mange planer for den såkalte problemet med begrenset polyhedron løsninger. På bakgrunn av dette settet med alle integrert plan har en begrenset verdi for oppgaven.

Også for garanti integral funksjon antar at verdiene av koeffisientene er også heltall. Til tross for alvorlighetsgraden av disse forholdene, jo svakere de klarer noen.

Gomory metoden innbefatter i det vesentlige byggerestriksjoner som skjærer løsninger som ikke er nonintegral. I dette tilfellet er det ingen cut-off ingen heltallsløsninger plan.

Algoritmen for å løse problemet består i å finne egnede alternativer Simpleksmetoden omfatter, uten å ta hensyn til betingelsene for integrality. Dersom alle komponentene i den optimale plan inneholder beslutninger knyttet til heltall, kan det antas at heltallet programmering målet er oppnådd. Kanskje det er funnet insolubility av problemet, så vi har bevis på at heltallet programmering problemet har ingen løsning.

Varianten, når komponentene i den optimale løsningen inneholder ikke-heltall. I dette tilfellet blir en ny begrensning tilsatt til alle begrensninger av problemet. De nye begrensninger er kjennetegnet ved en rekke egenskaper. Først av alt, det bør være lineær, bør være avskåret fra den funne sett av ikke-heltall optimal plan. Verken heltallsløsning bør ikke gå tapt, avskåret.

Når det skal bygges begrensninger bør velges komponent av en optimal plan med den høyeste fraksjon. Det er denne begrensningen vil bli lagt til den eksisterende simplex tabellen.

Vi finner løsningen av den resulterende problemet ved hjelp av konvensjonelle simplex transformasjon. Vi sjekker løsningen av problemet på eksistensen av et heltall optimal plan, hvis betingelsen er tilfredsstilt, så problemet er løst. Hvis resultatet ble oppnådd igjen med tilstedeværelse av ikke-heltallsløsninger, så vi innføre en ekstra begrensning, og gjenta beregningen prosessen.

Etter å ha gjennomført et endelig antall gjentakelser, oppnår vi et optimalt program av problemet poserte foran heltall programmering, eller bevise insolubility av problemet.