Vad är heltal linjär programmering?

Heltal Linjära programmeringsproblem uppstår när man försöker lösa linjära system medan de anger att alla okända variabler måste vara heltal eller hela siffror.Linjära system är uppsättningar av ekvationer som beskriver en situation för vilken programmeraren försöker hitta en lösning.De består vanligtvis av en ekvation som måste maximeras eller minimeras och en eller flera begränsande ekvation som sätter gränser för okända variabler.För att systemet ska vara linjärt måste varje begränsning vara en linjär ekvation;Det vill säga, det får inte innehålla några fall av den okända variabeln med exponenter större än en.

Regelbundna linjära system kan enkelt lösas med en dator.Programmet kan identifiera en lösning genom att hitta derivatet och ställa in det lika med noll.Den kan sedan verifiera att punkten är ett maximum eller minimum genom att kontrollera dess omedelbara grannskap på funktionen.Så länge derivatet definieras vid varje punkt längs funktionen har datorn endast ett begränsat antal möjliga lösningar att kontrollera.

Linjär programmering blir heltal Linjär programmering med tillägget av heltalsbegränsningen.Detta innebär att problemet förblir detsamma, men svaret måste bestå av heltal för de okända värdena: de måste vara hela siffror.Ibland betyder detta att lösningen kommer att vara suboptimal jämfört med fallet där fraktioner är tillåtna;Det är emellertid reflekterande av den verkliga världen, där föremål ofta finns i diskreta, odelbara enheter.Detta gör heltal linjär programmering viktigt för affärsapplikationer, eftersom företag vill maximera vinsten så mycket som möjligt men inte kan välja att sälja en bråkdel av en produkt.

När heltalsbegränsningarna är på plats är problemet med att lösa det linjära systemet NP-komplett.Detta innebär att tiden som är nödvändig för att en dator ska lösa systemet är obestämd.Med heltalsbegränsningar kan datorer inte använda derivatverktyget eftersom det inte finns någon garanti för att nollpunkten för derivatet kommer att falla på ett heltal.Lösningen kommer att vara heltalet med det högsta eller lägsta värdet av alla heltal, så datorn måste kontrollera dem alla mdash;En process som kan ta en oändlig tid.

Programmerare har utvecklat heuristik, eller metoder för problemlösning, för att hantera komplexiteten i dessa problem.En metod för att lösa heltal Linjära programmeringsproblem är gren och bunden algoritm, där datorn löser en serie problem relaterade till den ursprungliga för att begränsa det tillgängliga värdenområdet till en lösning.För komplexa problem kan det dock ta lång tid.