Oszlopgenerálás

Oszlopgenerálás vagy késleltetett oszlopgenerálás hatékony algoritmus nagy lineáris programok megoldására.

az átfogó elképzelés az, hogy sok lineáris program túl nagy ahhoz, hogy az összes változót kifejezetten figyelembe vegye. Az előfeltevés az, hogy a legtöbb változó nem alapszintű lesz, és az optimális megoldásban nulla értéket feltételez. Emiatt a probléma megoldása során elméletileg csak a változók egy részét kell figyelembe venni. Az oszlopgenerálás ezt az ötletet arra használja fel, hogy csak azokat a változókat generálja, amelyek képesek javítani az objektív függvényt—vagyis negatív csökkentett költségű változókat találni (feltételezve, hogy az általánosság elvesztése nélkül a probléma minimalizálási probléma).

a megoldandó probléma két problémára oszlik: a fő problémára és az alproblémára. A fő probléma az eredeti probléma, csak a változók egy részhalmazát veszik figyelembe. Az alprobléma egy új probléma, amelyet egy új változó azonosítására hoztak létre. Az alprobléma objektív funkciója az új változó költségének csökkentése a jelenlegi kettős változókhoz képest, a korlátok pedig megkövetelik, hogy a változó engedelmeskedjen a természetben előforduló korlátoknak.

a folyamat a következőképpen működik. A mester probléma megoldódott—ebből a megoldásból kettős árakat tudunk elérni a mester probléma minden korlátozásához. Ezt az információt ezután felhasználják az alprobléma objektív funkciójában. Az alprobléma megoldódott. Ha az alprobléma objektív értéke negatív, akkor egy negatív csökkentett költségű változót azonosítottak. Ez a változó ezután hozzáadódik a master problémához, és a master probléma újra megoldódik. A master probléma újbóli megoldása új kettős értékeket hoz létre, és a folyamatot addig ismételjük, amíg nem azonosítunk negatív csökkentett költségváltozókat. Az alprobléma nem negatív csökkentett költségű megoldást ad vissza, arra a következtetésre juthatunk, hogy a mesterprobléma megoldása optimális.

sok esetben ez lehetővé teszi a korábban megoldhatatlannak tartott nagy lineáris programok megoldását. A probléma klasszikus példája, ahol ezt sikeresen alkalmazzák, a vágási készlet problémája. A lineáris programozás egyik sajátos technikája, amely ezt a fajta megközelítést alkalmazza, a Dantzig–Wolfe bomlási algoritmus. Ezenkívül az oszlopgenerálást számos problémára alkalmazták, mint például a személyzet ütemezése, a jármű útválasztása és a kapacitált p-medián probléma.

ez az alkalmazott matematikával kapcsolatos cikk egy csonk. Segíthetsz a Wikipédián, ha kibővíted.