Integer lineær programmering er videnskaben om at modellere et problem, enten minimerer eller maksimerer en lineær objektive funktion , under et sæt af begrænsninger udtrykt som lineære uligheder. Når løst fuldstændigt , at løsningen på heltal lineært program garanterer den optimale løsning på problemet . Men kompleksiteten af problemet skalaer eksponentielt med problemet størrelse. Derfor kan det tage lang tid at nå frem til den endelige løsning . Alternativt kan problemet løses delvist og forskellige heuristik kan udforskes for at opnå en optimal løsning på kortere tid. Ting du skal
lineær programmering Solver
Computer med tilstrækkelig hukommelse og regnekraft
Vis Flere Instruktioner
formulering og løsning af lineære programmer
1

Beslut, om problemet er en " maksimering " problem eller en " minimering " problem . En maksimering problem forsøger at finde en løsning, hvor den objektive funktion er maksimeret . En minimering problem forsøger at finde en løsning, hvor den objektive funktion er minimeret. For eksempel er problemet med at finde den korteste vej mellem to punkter et minimering problem . På den anden side , er problemet at pakke det maksimale antal forskellige størrelser småsten i en flaske et maksimering problem .
2

Bestem de variabler, der kræves for formuleringen . At vælge den rigtige kombination af variabler er nødvendig for at minimere problemets kompleksitet , og tilsvarende ankommer til løsningen hurtigere. Typisk hver enhed, hvis værdi påvirker den endelige løsning er en variabel .
3

Model den objektive funktion . Den objektive funktion er modelleret som en sum af produkter af variabler og deres indvirkning på den endelige løsning . For eksempel, hvis problemet er at minimere afstanden mellem to knudepunkter i en graf vil hver forbindelse mellem to knudepunkter være en variabel som antager en værdi på 0 eller 1 , og dens bidrag til den objektive funktion bliver afstanden mellem knudepunkterne . I dette tilfælde kan den variable kaldes "X ( i, j ) ", hvor "i" og "j" er to vilkårlige knuder i grafen , og afstanden mellem de to knudepunkter kan være " V ( i, j ) . " X ( i, j ), vil være 1 , hvis forbindelsen er en del af den endelige sti mellem de to knudepunkter . Derfor vil den objektive funktion være at minimere summation af V ( i, j ) * X ( i, j ), hvor summation er over alle forbindelser.
4

Opsætning af begrænsninger. De begrænsninger skal fange alle de restriktioner, som problemet. For den korteste vej eksempel er der følgende begrænsninger : Hej

X ( i, j ), kan enten være 0 eller 1 . Derfor bør X ( i, j ) være større end eller lig med 0 , og X ( i, j ), bør være mindre end eller lig med 1. .
P Hvis forbindelse X ( i, j ) er valgt , præcis en forbindelse fra node " j" til nogle andre node andet end " jeg " bør vælges. Så bør X ( i, j ) være større end eller lig med summen af alle variabler af typen X ( j, k) , hvor " k" er ikke lig med "i ".

Én forbindelse fra start node bør vælges . Derfor bør summen af ​​X ( n , k) være 1 , hvor "n " er udgangspunktet node . Tilsvarende bør summen af ​​X ( k , m) være 1, hvor " m" er sidste node.
5.

Model problemet i enten Matematisk programmering System ( MPS ) format eller Linear Programmering ( LP ) format .
6

Enten købe en kommerciel solver såsom Fico eller CLPEX , eller downloade en gratis solver såsom GLPK . Bemærk de frie løsere er meget langsommere end de kommercielle løsere og kan ikke være egnet til at løse store problemer.
7

Hvis løseren ikke konvergerer til den endelige løsning i rimelig tid , så prøv heuristik . Et heuristisk kunne være at fjerne de heltal begrænsninger på de variabler, og tilnærme de variabler til nærmeste heltal for at opnå en optimal løsning.