Ako používať Integer Linear Programming

celočíselného lineárneho programovania je veda o modelovanie problém , ktorý buď minimalizuje alebo maximalizuje lineárnej účelovej funkcie , v sade obmedzenia vyjadrených ako lineárna nerovnosti . Pri úplne vyriešený , riešenie celé číslo lineárneho programu zaručuje optimálne riešenie problému . Avšak , zložitosť problému váhy exponenciálne s veľkosťou problému . Preto , to môže trvať dlhú dobu , aby sa dospelo na konečné riešenie . Alternatívne , môže byť problém vyriešený čiastočne a rôzne heuristiky môžu byť preskúmané za účelom získania sub - optimálne riešenie v kratšom čase . Veci , ktoré budete potrebovať
lineárneho programovania riešiteľom
počítač s dostatočnou pamäťou a výpočtový výkon
Zobraziť ďalšie inštrukcie
Formulácia a riešenia lineárne programy na
1

Rozhodnite , či problém je v tom " maximalizácie " problém , alebo " minimalizácia " problém . Problém maximalizácia snaží nájsť riešenie , také , kde účelová funkcia je maximalizovaný . Problém minimalizácia snaží nájsť riešenie , kde je minimalizovaná účelová funkcia . Napríklad , je problém , ako nájsť najkratšiu cestu medzi dvoma bodmi je problém minimalizácia . Na druhej strane , problém balenie maximálny počet rôzne veľké okruhliaky vo fľaši , je problém maximalizácia .
2.

rozhodnúť premenné potrebné pre formuláciu . Výber správnej súbor premenných je potrebné minimalizovať zložitosť problému , a zodpovedajúcim spôsobom sa dospelo k riešeniu rýchlejšie . Typicky , každý subjekt , ktorého hodnota má vplyv na konečné riešenie je variabilné .
3

Model objektívne funkcie . Cieľom funkcie je modelovaný ako súčet produktov premenných a ich vplyv na konečné riešenie . Napríklad , v prípade , že problém je minimalizovať vzdialenosť medzi dvoma uzlami v grafe , pričom spojenie medzi dvoma uzlami bude premenná , ktorá má hodnotu 0 alebo 1 , a jeho prínos pre cieľové funkcie bude vzdialenosť medzi uzlami . V tomto prípade , premenná môže byť nazývaný " X ( i , j ) , , " , kde " i " a " j " sú ľubovoľné dva uzly v grafe , a vzdialenosť medzi dvoma uzlami môže byť " V ( i , j ) . " X ( i , j ) bude 1 , ak pripojenie je súčasťou záverečnej cesty medzi dvoma uzlami . Z tohto dôvodu bude objektívna funkcia je minimalizovať súčty V ( i , j ) * X ( i , j ) , kde zhrnutie je u všetkých pripojení .
4

Nastavenie obmedzení . Obmedzenie by malo zachytiť všetky obmedzenia uložené problému . Pre najkratšie napríklad cesty , sú k dispozícii nasledujúce obmedzenia :

X ( i , j ) , môže byť buď 0 alebo 1. . Z tohto dôvodu, X ( i , j ) , by mala byť väčšia ako alebo rovné 0 , a X ( i , j ) , by mala byť menšia ako alebo rovný 1. Celým

Ak zvolená spojenie X ( i , j ) , práve jedno pripojenie od uzla " j " , na iné ako uzle " i " by mal byť zvolený . Takže , X ( i , j ) , by mala byť väčšia ako alebo rovná súčtu všetkých premenných typu X ( j , k ) , kde " k " nie je presne " i " .

Pripojenie od predvolené uzol by mal byť vybraný . Z toho dôvodu , súčet X (n , k ) by mal byť 1 , kde " n" je predvolené uzol . Podobne , súčet X ( k , m ) , by mala byť 1 , kde " m " je koniec uzol .
5

Model problém buď v matematickej programovanie systému formáte ( MPS ) , alebo lineárne programovanie ( LP ) formát .
6

Buď kúpiť komerčné riešič ako Fico alebo CLPEX , alebo zadarmo stiahnuť solver ako GLPK . Poznámka voľné riešitelia sú oveľa pomalšie než komerčné riešiteľov , a nemusia byť vhodné pre riešenie veľkých problémov .
7

Ak riešiteľ nebude konvergovať ku konečnému riešeniu v primeranej lehote , skúste heuristiky . Jeden heuristickej by mohlo byť odstránenie celočíselné obmedzení na premenných , a priblížiť premenné na najbližšie celé číslo k získaniu sub - optimálne riešenie .

• Predchádzajúca strana: TurboCAD Obmedzenie Tutorial 
• Ďalšia strana: Ako používať Punch Home Design Software