Integer lineaire programmering is de wetenschap van het modelleren van een probleem dat zowel minimaliseert of maximaliseert een lineaire doelfunctie , onder een set van randvoorwaarden uitgedrukt als lineaire ongelijkheden . Wanneer het volledig opgelost , de oplossing voor de integer lineaire programma waarborgt de optimale oplossing voor het probleem . Echter , de complexiteit van de probleemschalen exponentieel probleem formaat . Daarom kan het een lange tijd om te komen tot de uiteindelijke oplossing nemen . Alternatief kan het probleem gedeeltelijk opgelost en verschillende heuristieken worden onderzocht om een suboptimale oplossing te verkrijgen op een kortere tijd . Wat je
Lineaire programmering solver
computer moeten met voldoende geheugen en processorkracht
Toon Meer Aanwijzingen
formuleren en oplossen van lineaire programma
1 Bepaal of het probleem is een " maximalisering " probleem of een ' minimalisering ' probleem . Een maximalisatie probleem probeert een oplossing zoals waar de doelfunctie wordt gemaximaliseerd vinden . Een minimaliseringsprobleem probeert een oplossing waarbij de doelfunctie geminimaliseerd zijn. Bijvoorbeeld , het probleem van het vinden van de kortste weg tussen twee punten is een minimaliseringsprobleem . Aan de andere kant , het probleem om het maximale aantal verschillende maten steentjes in een fles te pakken is een maximalisatie probleem . Kopen van 2 Bepaal de variabelen die nodig zijn voor de formulering . De juiste verzameling variabelen nodig om de complexiteit van het probleem te minimaliseren , en dienovereenkomstig komen tot de oplossing sneller . Typisch , elke entiteit waarvan de waarde van invloed op de uiteindelijke oplossing is een variabele .
Model 3 de doelfunctie . De doelfunctie wordt gemodelleerd als een som van producten van variabelen en hun impact op de uiteindelijke oplossing . Bijvoorbeeld , als het probleem is de afstand tussen twee knooppunten in een grafiek minimaliseren elke verbinding tussen twee knooppunten een variabele die een waarde van 0 of 1 is , en de bijdrage aan de doelfunctie is de afstand tussen de knooppunten . In dit geval kan de variabele " X ( i , j ) , " waarbij " i" en " j " zijn twee willekeurige knooppunten in de grafiek en de afstand tussen de knopen kan " V ( i , j ) worden genoemd . " X ( i , j ) gelijk aan 1 als de verbinding deel van het laatste pad tussen de twee knooppunten . Daarom zal de doelfunctie om de som van V ( i , j ) * X ( i , j ) , waarbij de som is over alle verbindingen .
4 Stel de beperkingen te minimaliseren . De beperkingen moeten alle beperkingen opgelegd door het probleem vast te leggen . Voor de kortste weg voorbeeld zijn de volgende beperkingen :
X ( i , j ) kan ofwel 0 of 1 . Vandaar , X ( i , j ) moet groter dan of gelijk aan 0
zijn , en X ( i , j ) moet kleiner zijn dan of gelijk zijn aan 1 . Indien de verbinding X ( i , j ) wordt gekozen precies een verbinding van knooppunt " j " om een ander knooppunt , andere dan " i" worden gekozen . Dus , X ( i , j ) moet groter dan of gelijk aan de som van alle variabelen van het type X ( j , k ) , waarin " k " is niet gelijk aan een verbinding van zijn ' i . "
de start knooppunt worden gekozen . Daarom moet som van X ( n , k ) worden 1 , waarbij " n " het uitgangspunt knooppunt . Evenzo moet som van X ( k , m ) zijn 1 , waarbij " m " is het einde knooppunt .
Model 5 het probleem in een van beide de Mathematical Programming System ( MPS ) -indeling , of het Linear programmering ( LP ) -formaat .
6 Ofwel koopt een commerciële solver zoals FICO of CLPEX , of download een gratis oplosser zoals GLPK . Let op de vrije solvers zijn veel trager dan de commerciële solvers en mogelijk niet geschikt voor het oplossen van grote problemen .
7 Als de solver niet convergeren naar de uiteindelijke oplossing in een redelijke tijd , probeer heuristiek . Een heuristische zou kunnen zijn om de gehele restricties op de variabelen , en bij benadering de variabelen op een geheel getal tot een sub - optimale oplossing te verkrijgen verwijderen .
|
