Gomory metode. Opløsningen af heltallige programmeringsproblemer

Vægt problemer med økonomisk, planlægning og endda spørgsmål fra andre områder af menneskelivet problemer forbundet med variabler i relation til heltal. Som et resultat af deres analyse og søgen efter de bedste måder at løse begrebet ekstreme udfordringer. Dens funktioner er den ovennævnte funktion tager et heltal værdi, og opgaven selv betragtes matematik som heltal programmering.

De vigtigste anvendelser af problemer med variabel, et helt tal, er optimering. En fremgangsmåde, der anvender et heltal lineær programmering, også kaldet cut-off-metoden.

Gomory metode blev opkaldt efter matematikeren, først udviklet i 1957-1958 algoritmen stadig i vid udstrækning anvendes til at løse lineære programmeringsproblemer heltal. Den kanoniske form af heltal programmering problemet tillader tilgængelig og fuldt afsløre fordelene ved denne metode.

Gomori metode anvendes på en lineær programmering i høj grad komplicerer opgaven med at finde de optimale værdier. Efter fuldstændige er et grundlæggende krav, yderligere alle parametre for problemet. Der er tilfælde, hvor det problem ved at have gyldige (heltal) planer, tilstedeværelsen i den objektive funktion af restriktionerne for den tilladte sæt, afgørelsen kommer til at opnå maksimal. Dette skyldes mangel på samme er integrerede løsninger. Uden de samme betingelser, som regel i form af en beslutning er passende vektor.

For at retfærdiggøre de numeriske algoritmer til løsning af problemer er der behov for at foretage yderligere overlejring af forskellige forhold.

Anvendelse af fremgangsmåden i Gomory, normalt betragter mange planer for den såkaldte problemet med begrænsede polyhedron løsninger. På dette grundlag, det sæt af alle integreret plan har en endelig værdi for opgaven.

Også for garanti integreret funktion antager, at værdierne af koefficienterne er også heltal. På trods af sværhedsgraden af disse betingelser, jo svagere de administrere et par stykker.

Gomory metode hovedsagelig indebærer bygning begrænsninger, der går på løsninger, som ikke nonintegral. I dette tilfælde er der ingen afskæring ingen heltal løsninger plan.

Algoritmen for at løse problemet indebærer at finde egnede muligheder simplex metode, uden at tage hensyn til de betingelser for fuldstændige. Hvis alle komponenter i den optimale plan indeholder beslutninger relateret til heltal, kan det antages, at der opnås den heltalsprogrammering mål. Måske der findes uopløselighed af problemet, så vi har bevis for, at heltal programmering problemet har ingen løsning.

Varianten, når komponenterne af den optimale løsning indeholder ikke-heltal. I dette tilfælde bliver en ny begrænsning tilsættes alle de begrænsninger af problemet. De nye restriktioner er karakteriseret ved et antal egenskaber. Først og fremmest, det skal være lineær, bør afskåret fra det fundne sæt ikke-heltal optimal plan. Hverken heltal løsning ikke bør gå tabt, afbrød.

Hvornår bør vælges bygning restriktioner komponent i en optimal plan med den højeste fraktion. Det er denne begrænsning vil blive tilføjet til den eksisterende simplex bordet.

Vi finder løsningen af den resulterende problemer ved anvendelse af traditionel simplex transformation. Vi kontrollere løsningen af problemet på eksistensen af et heltal optimal plan, hvis betingelsen er opfyldt, så er problemet løst. Hvis resultatet igen opnåedes med tilstedeværelsen af ikke-heltal løsninger, så vi indføre en yderligere begrænsning, og gentage beregningen proces.

Efter at have gennemført et endeligt antal iterationer, vi opnå en optimal program af det problem foran heltalsprogrammering, eller bevise uopløselighed af problemet.