Hvad er heltal lineær programmering?

Heltal Lineære programmeringsproblemer opstår, når man prøver at løse lineære systemer, mens de specificerer, at alle de ukendte variabler skal være heltal eller hele tal.Lineære systemer er sæt ligninger, der beskriver en situation, som programmøren forsøger at finde en løsning.De består normalt af en ligning, der skal maksimeres eller minimeres og en eller flere begrænsende ligning, der sætter grænser for ukendte variabler.For at systemet skal være lineært, skal hver begrænsning være en lineær ligning;Det vil sige, det må ikke indeholde tilfælde af den ukendte variabel med eksponenter, der er større end et.

Regelmæssige lineære systemer kan let løses ved hjælp af en computer.Programmet kan identificere en løsning ved at finde derivatet og indstille den lig med nul.Det kan derefter verificere, at pointen er et maksimum eller minimum ved at kontrollere dets umiddelbare kvarter på funktionen.Så længe derivatet er defineret på hvert punkt langs funktionen, har computeren kun et begrænset antal mulige løsninger til kontrol.

Lineær programmering bliver heltal lineær programmering med tilføjelse af heltalbegrænsningen.Dette betyder, at problemet forbliver det samme, men svaret skal bestå af heltalværdier for de ukendte værdier: de skal være hele tal.Nogle gange betyder dette, at opløsningen vil være suboptimal sammenlignet med det tilfælde, hvor fraktioner er tilladt;Det reflekterer imidlertid over den virkelige verden, hvor genstande ofte findes i diskrete, udelelige enheder.Dette gør heltal lineær programmering vigtig for forretningsapplikationer, da virksomheder ønsker at maksimere overskuddet så meget som muligt, men ikke kan vælge at sælge en brøkdel af et produkt.

Når heltalbegrænsningerne er på plads, er problemet med at løse det lineære system NP-komplet.Dette betyder, at den tid, der er nødvendig for en computer til at løse systemet, er ubestemt.Med heltalbegrænsninger kan computere ikke bruge værktøjet til derivatet, fordi der ikke er nogen garanti for, at derivatets nulpunkt falder på et heltal.Løsningen vil være heltalet med den højeste eller laveste værdi ud af alle heltal, så computeren bliver nødt til at tjekke dem alle mdash;En proces, der kan tage en uendelig mængde tid.

Programmerere har udviklet heuristik eller metoder til problemløsning for at håndtere kompleksiteten af disse problemer.En metode til løsning af heltal lineære programmeringsproblemer er grenen og den bundne algoritme, hvor computeren løser en række problemer relateret til den originale til at indsnævre det tilgængelige interval af værdier til en løsning.For komplekse problemer kan dette imidlertid tage lang tid.