Kolonnegenerering
Kolonnegenerering eller forsinket kolonnegenerering er en effektiv algoritme til løsning af store lineære programmer.
den overordnede ide er, at mange lineære programmer er for store til at overveje alle variablerne eksplicit. Forudsætningen er, at de fleste af variablerne vil være ikke-basale og antage en værdi på nul i den optimale løsning. På grund af dette skal kun en delmængde af variabler overvejes i teorien, når problemet løses. Kolonnegenerering udnytter denne ide til kun at generere de variabler, der har potentialet til at forbedre den objektive funktion—det vil sige at finde variabler med negative reducerede omkostninger (forudsat uden tab af generalitet, at problemet er et minimeringsproblem).
det problem, der løses, er opdelt i to problemer: masterproblemet og underproblemet. Masterproblemet er det oprindelige problem, hvor kun en delmængde af variabler overvejes. Underproblemet er et nyt problem oprettet for at identificere en ny variabel. Delproblemets objektive funktion er de reducerede omkostninger ved den nye variabel med hensyn til de nuværende dobbelte variabler, og begrænsningerne kræver, at variablen overholder de naturligt forekommende begrænsninger.
processen fungerer som følger. Masterproblemet er løst-fra denne løsning er vi i stand til at opnå dobbeltpriser for hver af begrænsningerne i masterproblemet. Disse oplysninger bruges derefter i underproblemets objektive funktion. Delproblemet er løst. Hvis delproblemets objektive værdi er negativ, er der identificeret en variabel med negative reducerede omkostninger. Denne variabel føjes derefter til masterproblemet, og masterproblemet løses igen. Genløsning af masterproblemet genererer et nyt sæt dobbeltværdier, og processen gentages, indtil der ikke identificeres negative reducerede omkostningsvariabler. Underproblemet returnerer en løsning med ikke-negative reducerede omkostninger, vi kan konkludere, at løsningen på masterproblemet er optimal.
i mange tilfælde tillader dette store lineære programmer, der tidligere var blevet betragtet som uhåndterlige, at blive løst. Det klassiske eksempel på et problem, hvor dette med succes anvendes, er skærebeholdningsproblemet. En særlig teknik inden for lineær programmering, der bruger denne form for tilgang, er dantsig–Ulf-nedbrydningsalgoritmen. Derudover er kolonnegenerering blevet anvendt på mange problemer såsom besætningsplanlægning, køretøjsrute og det kapaciterede p-medianproblem.
 |
denne artikel om anvendt matematik er kun påbegyndt. Du kan hjælpe |
