Hva er heltall lineær programmering?

Heltall lineære programmeringsproblemer oppstår når du prøver å løse lineære systemer mens de spesifiserer at alle de ukjente variablene må være heltall, eller hele tall.Lineære systemer er sett med ligninger som beskriver en situasjon som programmereren prøver å finne en løsning for.De består vanligvis av en ligning som må maksimeres eller minimeres og en eller flere begrensende ligning som setter grenser for ukjente variabler.For at systemet skal være lineært, må hver begrensning være en lineær ligning;Det vil si at den må ikke inneholde forekomster av den ukjente variabelen med eksponenter som er større enn ett.

Vanlige lineære systemer kan løses enkelt ved bruk av en datamaskin.Programmet kan identifisere en løsning ved å finne derivatet og sette det lik null.Det kan da bekrefte at punktet er et maksimum eller minimum ved å sjekke det umiddelbare nabolaget på funksjonen.Så lenge derivatet er definert på hvert punkt langs funksjonen, har datamaskinen bare et begrenset antall mulige løsninger for å sjekke.

Lineær programmering blir heltall lineær programmering med tilsetning av heltallbegrensningen.Dette betyr at problemet forblir det samme, men svaret må bestå av heltallverdier for de ukjente verdiene: de må være hele tall.Noen ganger betyr dette at løsningen vil være suboptimal sammenlignet med tilfellet der brøkene er tillatt;Det er imidlertid reflekterende av den virkelige verden, der gjenstander ofte kommer i diskrete, udelelige enheter.Dette gjør heltall lineær programmering viktig for forretningsapplikasjoner, siden firmaer ønsker å maksimere fortjenesten så mye som mulig, men ikke kan velge å selge en brøkdel av et produkt.

Når heltallbegrensningene er på plass, er problemet med å løse det lineære systemet NP-fullstendig.Dette betyr at tiden som er nødvendig for at en datamaskin skal løse systemet er ubestemmelig.Med heltallbegrensninger kan datamaskiner ikke bruke verktøyet til derivatet fordi det ikke er noen garanti for at nullpunktet for derivatet vil falle på et heltall.Løsningen vil være heltallet med den høyeste eller laveste verdien av alle heltallene, så datamaskinen må sjekke dem alle mdash;En prosess som kan ta en uendelig tid.

Programmerere har utviklet heuristikk, eller metoder for problemløsing, for å håndtere kompleksiteten i disse problemene.En metode for å løse heltall lineære programmeringsproblemer er grenen og den bundne algoritmen, der datamaskinen løser en serie problemer relatert til den opprinnelige for å begrense det tilgjengelige verdiene til en løsning.For komplekse problemer kan dette imidlertid ta lang tid.