Kolom generatie

kolom generatie of vertraagde kolom generatie is een efficiënt algoritme voor het oplossen van grote lineaire programma ‘ s.

het overkoepelende idee is dat veel lineaire programma ‘ s te groot zijn om alle variabelen expliciet te beschouwen. Het uitgangspunt is dat de meeste variabelen niet-basisch zullen zijn en een waarde van nul in de optimale oplossing aannemen. Daarom hoeft slechts een deelverzameling van variabelen in theorie te worden overwogen bij het oplossen van het probleem. Kolomgeneratie maakt gebruik van dit idee om alleen de variabelen te genereren die het potentieel hebben om de objectieve functie te verbeteren—dat wil zeggen, om variabelen te vinden met negatieve gereduceerde kosten (ervan uitgaande dat zonder verlies van algemeenheid het probleem een minimalisatieprobleem is).

het probleem dat wordt opgelost is opgesplitst in twee problemen: het hoofdprobleem en het subprobleem. Het hoofdprobleem is het oorspronkelijke probleem waarbij slechts een deelverzameling van variabelen wordt overwogen. Het subprobleem is een nieuw probleem gecreëerd om een nieuwe variabele te identificeren. De objectieve functie van het subprobleem is de lagere kosten van de nieuwe variabele ten opzichte van de huidige dubbele variabelen, en de beperkingen vereisen dat de variabele voldoet aan de natuurlijk voorkomende beperkingen.

het proces werkt als volgt. Het hoofdprobleem is opgelost-vanuit deze oplossing kunnen we Dubbele prijzen verkrijgen voor elk van de beperkingen in het hoofdprobleem. Deze informatie wordt vervolgens gebruikt in de objectieve functie van het subprobleem. Het subprobleem is opgelost. Indien de objectieve waarde van het subprobleem negatief is, is een variabele met negatieve lagere kosten geïdentificeerd. Deze variabele wordt dan toegevoegd aan het masterprobleem, en het masterprobleem wordt opnieuw opgelost. Het opnieuw oplossen van het masterprobleem zal een nieuwe set van dubbele waarden genereren, en het proces wordt herhaald totdat er geen negatieve gereduceerde kostenvariabelen worden geïdentificeerd. Het subprobleem retourneert een oplossing met niet-negatieve gereduceerde kosten, kunnen we concluderen dat de oplossing voor het masterprobleem optimaal is.

in veel gevallen maakt dit het mogelijk om grote lineaire programma ‘ s op te lossen die eerder als onhandelbaar werden beschouwd. Het klassieke voorbeeld van een probleem waarbij dit met succes wordt gebruikt, is het probleem van het snijden van de voorraad. Een bepaalde techniek in lineair programmeren die dit soort benadering gebruikt is het Dantzig–Wolfe ontledingsalgoritme. Bovendien, kolom generatie is toegepast op vele problemen zoals bemanning planning, voertuig routing, en de capacitated p-mediaan probleem.

dit artikel over toegepaste wiskunde is een stub. U kunt Wikipedia helpen door het uit te breiden.