Kolumn generation

kolumn generation eller fördröjd kolumn generation är en effektiv algoritm för att lösa stora linjära program.

den övergripande tanken är att många linjära program är för stora för att ta hänsyn till alla variabler uttryckligen. Utgångspunkten är att de flesta variablerna kommer att vara icke-grundläggande och anta ett värde på noll i den optimala lösningen. På grund av detta måste endast en delmängd av variabler beaktas i teorin när man löser problemet. Kolumngenerering utnyttjar denna ide för att generera endast de variabler som har potential att förbättra objektivfunktionen—det vill säga att hitta variabler med negativ reducerad kostnad (förutsatt utan förlust av generalitet att problemet är ett minimeringsproblem).

problemet som löses är uppdelat i två problem: huvudproblemet och delproblemet. Huvudproblemet är det ursprungliga problemet med endast en delmängd av variabler som beaktas. Delproblemet är ett nytt problem som skapats för att identifiera en ny variabel. Delproblemets objektiva funktion är den minskade kostnaden för den nya variabeln med avseende på de nuvarande dubbla variablerna, och begränsningarna kräver att variabeln följer de naturligt förekommande begränsningarna.

processen fungerar enligt följande. Huvudproblemet är löst-från denna lösning kan vi få dubbla priser för var och en av begränsningarna i huvudproblemet. Denna information används sedan i delproblemets objektiva funktion. Delproblemet är löst. Om delproblemets objektiva värde är negativt har en variabel med negativ reducerad kostnad identifierats. Denna variabel läggs sedan till i huvudproblemet och huvudproblemet löses igen. Att lösa huvudproblemet kommer att generera en ny uppsättning dubbla värden, och processen upprepas tills inga negativa reducerade kostnadsvariabler identifieras. Delproblemet returnerar en lösning med icke-negativ reducerad kostnad, vi kan dra slutsatsen att lösningen på huvudproblemet är optimal.

i många fall tillåter detta stora linjära program som tidigare ansetts vara otänkbara att lösas. Det klassiska exemplet på ett problem där detta framgångsrikt används är skärningsproblemet. En speciell teknik i linjär programmering som använder denna typ av tillvägagångssätt är Dantzig–Wolfe sönderdelningsalgoritm. Dessutom har kolumngenerering tillämpats på många problem som besättningsschemaläggning, fordonsdirigering och det kapaciterade p-medianproblemet.

denna artikel om tillämpad matematik saknar väsentlig information. Du kan hjälpa Wikipedia genom att utöka det.