Hilbertův základ (lineární programování) - Hilbert basis (linear programming)
The Hilbertův základ a konvexní kužel C je minimální množina celého čísla vektory takový, že každý celočíselný vektor v C je kónická kombinace vektorů na Hilbertově bázi s celočíselnými koeficienty.
Definice
Vzhledem k mříž a konvexní mnohostěnný kužel s generátory
považujeme za monoidní . Podle Gordanovo lemma tento monoid je definitivně generován, tj. existuje konečná sada mřížových bodů tak, že každý mřížový bod je celočíselná kónická kombinace těchto bodů:
Kužel C se nazývá špičatý, pokud naznačuje . V tomto případě existuje jedinečná minimální generující sada monoidu - Hilbertův základ z C. Je to dáno množinou neredukovatelných mřížových bodů: Prvek se nazývá ireducibilní, pokud jej nelze zapsat jako součet dvou nenulových prvků, tj. naznačuje nebo .
Reference
- Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert (1999), „Protiklad celočíselného analogu Carathéodoryho věty“, Journal für die reine und angewandte Mathematik, 1999 (510): 179–185, doi:10.1515 / crll.1999.045
- Cook, William John; Fonlupt, Jean; Schrijver, Alexander (1986), "Celočíselný analog Carathéodoryho věty", Journal of Combinatorial Theory, Series B, 40 (1): 63–70, doi:10.1016 / 0095-8956 (86) 90064-X
- Eisenbrand, Friedrich; Shmonin, Gennady (2006), „Carathéodory bounds for integer cones“, Dopisy o operačním výzkumu, 34 (5): 564–568, doi:10.1016 / j.orl.2005.09.008
- D. V. Pasechnik (2001). „Při výpočtu Hilbertových základen pomocí Elliottovo-MacMahonova algoritmu“. Teoretická informatika. 263 (1–2): 37–46. doi:10.1016 / S0304-3975 (00) 00229-2.
Tento aplikovaná matematika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |