Generování sloupců

generování sloupců nebo zpožděné generování sloupců je efektivní algoritmus pro řešení velkých lineárních programů.

zastřešující myšlenkou je, že mnoho lineárních programů je příliš velké na to, aby explicitně zvážilo všechny proměnné. Předpokladem je, že většina proměnných bude nezákladní a v optimálním řešení bude mít hodnotu nula. Z tohoto důvodu je třeba při řešení problému teoreticky zvážit pouze podmnožinu proměnných. Sloupec generace využívá tento nápad generovat pouze proměnné, které mají potenciál zlepšit objektivní funkce—to je, najít proměnné s negativní sníženou cenu (za předpokladu, že bez újmy na obecnosti, že problém je minimalizace problém).

řešený problém je rozdělen na dva problémy: hlavní problém a podproblém. Hlavní problém je původní problém, přičemž se zvažuje pouze podmnožina proměnných. Podproblém je nový problém vytvořený k identifikaci nové proměnné. Cílem funkce podproblémem je snížení nákladů na nové proměnné s ohledem na současný duální proměnné, omezení, která vyžadují, aby proměnné se řídí přirozeně se vyskytující omezení.

proces funguje následovně. Hlavní problém je vyřešen-z tohoto řešení jsme schopni získat dvojí ceny za každé omezení v hlavním problému. Tyto informace jsou pak využity v objektivní funkci podproblemu. Dílčí problém je vyřešen. Pokud je objektivní hodnota podproblemu záporná, byla identifikována proměnná se zápornými sníženými náklady. Tato proměnná je pak přidána do hlavního problému a hlavní problém je znovu vyřešen. Opětovné řešení hlavního problému vygeneruje novou sadu duálních hodnot a proces se opakuje, dokud nejsou identifikovány žádné negativní proměnné se sníženými náklady. Subproblém vrací řešení s negativními sníženými náklady, můžeme usoudit, že řešení hlavního problému je optimální.

v mnoha případech to umožňuje vyřešit velké lineární programy, které byly dříve považovány za neřešitelné. Klasickým příkladem problému, kde se to úspěšně používá, je problém řezných zásob. Jedna konkrétní technika v lineárním programování, která používá tento druh přístupu je Dantzig-Wolfe rozklad algoritmus. Kromě toho byla generace sloupců aplikována na mnoho problémů, jako je plánování posádky, směrování vozidel a kapacitní problém p-medián.

Tento aplikované matematiky související článek je pahýl. Wikipedii můžete pomoci tím, že ji rozšíříte.