Hvad er heltal lineær programmering?

Lineære programmeringsproblemer med heltal opstår, når man prøver at løse lineære systemer, mens man 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 programmereren 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 ligninger, 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, den må ikke indeholde forekomster af den ukendte variabel med eksponenter, der er større end én.

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 sætte det lig med nul. Det kan derefter bekræfte, at punktet er et maksimum eller et 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øjelsen af ​​heltalets begrænsning. 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 løsningen vil være suboptimal sammenlignet med det tilfælde, hvor fraktioner er tilladt; det reflekterer dog den virkelige verden, hvor genstande ofte kommer i diskrete, udelelige enheder. Dette gør heltal lineær programmering vigtig for forretningsapplikationer, da virksomhederne ønsker at maksimere overskuddet så meget som muligt, men ikke kan vælge at sælge en brøkdel af et produkt.

Når heltalets begrænsninger 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 det heltal med den højeste eller laveste værdi ud af alle heltalene, så computeren bliver nødt til at kontrollere dem alle - en proces, der kan tage en uendelig lang tid.

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