heltalsprogrammering är vetenskapen om att modellera ett problem som antingen minimerar eller maximerar en linjär målfunktion , enligt en uppsättning begränsningar uttryckta som linjära olikheter . När löst helt , garanterar lösningen på heltalsprogrammering programmet den optimala lösningen på problemet . Men problemets komplexitet skalor exponentiellt med problemet storlek . Därför kan det ta lång tid att komma fram till den slutliga lösningen. Alternativt , kan problemet lösas delvis och olika heuristik kan utforskas för att få en sub - optimal lösning vid en kortare tid . Saker du behöver
Linjär programmering lösare
dator med tillräckligt minne och processorkraft
Visa fler instruktioner
formulera och lösa linjära program
1
Bestäm om problemet är en " maximering " problem eller ett " minimering " problem. En maximering problem försöker hitta en sådan lösning där målfunktionen är maximerad . Ett minimeringsproblem försöker att finna en lösning där målfunktionen minimeras. Till exempel är problemet med att hitta den kortaste vägen mellan två punkter en minimeringsproblem . Å andra sidan , är problemet att packa det maximala antalet olika stora stenar i en flaska en maximering problem .
2
Bestäm de variabler som krävs för formuleringen . Att välja rätt uppsättning av variabler är nödvändigt att minimera problemets komplexitet , och på motsvarande sätt komma fram till lösningen snabbare. Typiskt är varje enhet vars värde påverkar den slutliga lösningen en variabel .
3
Model målfunktionen . Målfunktionen modelleras som en summa av produkter av variabler och deras inverkan på den slutliga lösningen . Till exempel , om problemet är att minimera avståndet mellan två noder i en graf , kommer varje förbindelse mellan två noder vara en variabel som tar ett värde av 0 eller 1 , och dess bidrag till målet funktion kommer att vara avståndet mellan noderna . I detta fall kan den rörliga kallas " X ( i, j) , " där "i " och " j" är två valfria noder i grafen , och avståndet mellan de två noderna kan vara "V ( i, j) . " X (i, j ) kommer att vara 1 om anslutningen är del av den slutliga banan mellan de två noderna . Därför kommer målfunktionen vara att minimera summan av V ( i, j ) * X ( i, j ) , där summan är över alla anslutningar .
4
Ställ in begränsningar . Begränsningarna ska fånga alla de begränsningar som problemet . För den kortaste vägen exempel finns följande begränsningar :
X ( i, j) kan antingen vara 0 eller 1 . Därför bör X ( i, j) vara större än eller lika med 0 , och X ( i, j) bör vara mindre än eller lika med 1 .
Om anslutningen X ( i, j) som väljs, exakt en anslutning från nod " j " till någon annan nod annat än " jag " bör väljas . Så ska X ( i, j ) vara större än eller lika med summan av alla variabler av typ X ( j , k ) , där " k " är inte lika med " jag . "
En anslutning från start nod väljas . Därför bör summan av X ( n, k ) vara ett , där "n" är utgångspunkten noden. Likaså bör summan av X ( k , m ) vara 1 , där " m " är den avslutande noden .
5
Model problemet i antingen Mathematical Programming System ( MPS ) format , eller Linear Programmering ( LP ) -format .
6
antingen köpa en kommersiell lösare såsom FICO eller CLPEX , eller ladda ner en gratis lösare såsom glpk . Notera de fria lösare är mycket långsammare än de kommersiella lösare och får inte vara lämpliga för att lösa stora problem .
7
Om Problemlösaren inte konvergerar till den slutliga lösningen i rimlig tid , prova heuristik . En heuristisk skulle kunna vara att ta bort de heltal begränsningar för de variabler , och ungefärliga variablerna till närmaste heltal för att få en sub - optimal lösning .
