Wat is lineaire programmering van gehele getallen?

Integer lineaire programmeringsproblemen ontstaan bij het proberen lineaire systemen op te lossen en tegelijkertijd aan te geven dat alle onbekende variabelen gehele getallen of hele getallen moeten zijn.Lineaire systemen zijn sets van vergelijkingen die een situatie beschrijven waarvoor de programmeur probeert een oplossing te vinden.Ze bestaan meestal uit één vergelijking die moet worden gemaximaliseerd of geminimaliseerd en een of meer beperkende vergelijking die limieten stelt op onbekende variabelen.Om het systeem lineair te laten zijn, moet elke beperking een lineaire vergelijking zijn;Dat wil zeggen, het mag geen instanties van de onbekende variabele bevatten met exponenten groter dan één.

Regelmatige lineaire systemen kunnen eenvoudig worden opgelost met behulp van een computer.Het programma kan een oplossing identificeren door het derivaat te vinden en deze gelijk aan nul in te stellen.Vervolgens kan het verifiëren dat het punt een maximum of minimum is door de directe buurt op de functie te controleren.Zolang het derivaat op elk punt langs de functie wordt gedefinieerd, heeft de computer slechts een beperkt aantal mogelijke oplossingen om te controleren.

Lineaire programmering wordt een lineair programmeren van een geheel getal met de toevoeging van de gehele beperking.Dit betekent dat het probleem hetzelfde blijft, maar het antwoord moet bestaan uit gehele waarden voor de onbekende waarden: het moeten hele getallen zijn.Soms betekent dit dat de oplossing suboptimaal zal zijn in vergelijking met het geval waarin breuken zijn toegestaan;Het is echter reflecterend van de echte wereld, waarin items vaak in discrete, ondeelbare eenheden komen.Dit maakt integer lineair programmeren belangrijk voor zakelijke toepassingen, omdat bedrijven de winst zoveel mogelijk willen maximaliseren, maar niet kunnen kiezen om een fractie van een product te verkopen.

Zodra de gehele beperkingen aanwezig zijn, is het probleem van het oplossen van het lineaire systeem NP-compleet.Dit betekent dat de tijd die nodig is voor een computer om het systeem op te lossen, onbepaald is.Met gehele beperkingen kunnen computers het gereedschap van de afgeleide niet gebruiken omdat er geen garantie is dat het nulpunt van de derivaat op een geheel getal zal vallen.De oplossing is het geheel getal met de hoogste of laagste waarde van alle gehele getallen, dus de computer zou ze allemaal moeten controleren mdash;een proces dat een oneindige hoeveelheid tijd kan duren.

Programmeurs hebben heuristiek of methoden voor probleemoplossing ontwikkeld om de complexiteit van deze problemen aan te pakken.Een methode voor het oplossen van integer lineaire programmeringsproblemen is het tak- en gebonden algoritme, waarbij de computer een reeks problemen oplost die verband houdt met de originele om het beschikbare bereik van waarden te beperken tot één oplossing.Voor complexe problemen kan dit echter lang duren.