Mange oppgaver av økonomisk art, problemerplanlegging og til og med å løse problemer fra andre områder av menneskelivet er assosiert med variabler relatert til heltall. Som et resultat av deres analyse og jakten på optimale løsninger dukket konseptet med et ekstremt problem opp. Funksjonene ovenfor er funksjonen ovenfor for å ta en heltallverdi, og selve oppgaven blir i matematikk betraktet som heltallsprogrammering.
Som den viktigste bruksretningenoppgaver med variabler som tar heltallverdier er optimalisering. En metode som bruker hel-lineær programmering kalles også en klippemetode.
Gomori-metoden fikk navnet ved navnmatematikk, den første som utviklet en algoritme i 1957-1958, som fremdeles er mye brukt for å løse heltallige lineære programmeringsproblemer. Den kanoniske formen for helhetsprogrammeringsproblemet gjør det mulig for oss å avsløre fordelene ved denne metoden fullt ut.
Gomori-metode som anvendt på lineærprogrammering kompliserer oppgaven med å finne optimale verdier betydelig. Tross alt er heltall hovedbetingelsen, i tillegg til alle parametere for problemet. Det er hyppige tilfeller når et problem, med tillatte planer (heltall), hvis de objektive funksjonene har begrensninger på et tillatt sett, ikke når maksimalt i løsningen. Dette skyldes fraværet av heltaleløsninger. Uten denne tilstanden, som regel, finnes en passende vektor i form av en løsning.
For å underbygge numeriske algoritmer for å løse problemer, blir det nødvendig å stille forskjellige tilleggsvilkår.
Ved hjelp av Gomori-metoden, mangeproblemplaner begrenset av den såkalte polyhedron av løsninger. Basert på dette følger det at settet med alle heltallsplaner for oppgaven har en endelig verdi.
For å garantere funksjonens integritet antas det også at koeffisientene til verdiene også er heltall. Til tross for alvorlighetsgraden av slike forhold, er det mulig å slappe av dem litt.
Gomori-metoden innebærer i det vesentlige å konstruere begrensninger som kutter av løsninger som ikke er heltallverdige. Samtidig kuttes ingen løsninger av helhetsplanen.
Algoritmen for å løse problemet inkludererå finne egnede varianter ved simplex-metoden, uten å ta hensyn til heltallforholdene. Hvis det i alle komponentene i den optimale planen er løsninger relatert til heltall, kan vi anta at målet med heltaleprogrammering oppnås. Det er mulig at en uløsbarhet av problemet blir oppdaget, så vi får bevis på at helhetsprogrammeringsproblemet ikke har noen løsning.
Det er en mulighet når du er i komponenteneDen optimale løsningen inneholder ikke-heltallstall. I dette tilfellet blir en ny begrensning lagt til alle begrensningene for oppgaven. En ny begrensning er preget av tilstedeværelsen av et antall egenskaper. Først av alt, det må være lineært, må kutte en heltalfri plan fra det funnet optimale settet. Ingen heltalløsning skal gå tapt, avkortet.
Når man konstruerer begrensninger, bør man velge komponenten i den optimale planen med den største brøkdel. Denne begrensningen vil bli lagt til den eksisterende enkle-tabellen.
Находим решение полученной задачи, используя ordinære simplex-transformasjoner. Vi sjekker løsningen av problemet for eksistensen av en helhetlig optimal plan, hvis betingelsen er oppfylt, blir problemet løst. Hvis det igjen ble oppnådd et resultat med nærvær av ikke-heltall-løsninger, innfører vi en ekstra begrensning og gjentar beregningsprosessen.
Etter å ha fullført et begrenset antall iterasjoner, oppnår vi den optimale planen for problemet med heltaleprogrammering, eller vi beviser at problemet ikke kan løses.
