Baza e Hilbertit (programimi linear)

Baza Hilbert e një koni konveks C është një grup minimal i vektorëve të plotë në C i tillë që çdo vektor numër i plotë në C është një kombinim konik i vektorëve në bazën e Hilbertit me koeficientët e numrave të plotë.

Përkufizimi

Vizualizimi i bazës së Hilbertit. Dy rreze në rrafsh përcaktojnë një kon të pafund të të gjitha pikave që shtrihen midis tyre. Pikat unike të bazës Hilbert të konit janë të rrethuara në të verdhë. Çdo pikë numër i plotë në kon mund të shkruhet si një shumë e këtyre elementeve bazë. Ndërsa ndryshoni kon duke lëvizur njërën nga rrezet, ndryshon edhe baza Hilbert.

Jepet një laticë $L\subset \mathbb {Z} ^{d}$ dhe një kon shumëkëndor konveks me gjeneratorë $a_{1},\ldots ,a_{n}\in \mathbb {Z} ^{d}$

$C=\{\lambda _{1}a_{1}+\ldots +\lambda _{n}a_{n}\mid \lambda _{1},\ldots ,\lambda _{n}\geq 0,\lambda _{1},\ldots ,\lambda _{n}\in \mathbb {R} \}\subset \mathbb {R} ^{d},$

konsiderojmë monoidin $C\cap L$ . Nga lema e Gordanit, ky monoid gjenerohet përfundimisht, dmth, ekziston një grup i kufizuar pikash rrjetë.

$\{x_{1},\ldots ,x_{m}\}\subset C\cap L$ të tillë që çdo pikë rrjetë $x\in C\cap L$ është një kombinim konik numër i plotë i këtyre pikave:

$x=\lambda _{1}x_{1}+\ldots +\lambda _{m}x_{m},\quad \lambda _{1},\ldots ,\lambda _{m}\in \mathbb {Z} ,\lambda _{1},\ldots ,\lambda _{m}\geq 0.$

Koni C quhet i mprehtë nëse $x,-x\in C$ nënkupton $x=0$ . Në këtë rast ekziston një grup unik gjenerues minimal i monoidit $C\cap L$ -baza e Hilbertit e C. Ai jepet nga bashkësia e pikave të rrjetës së pareduktueshme: Një element $x\in C\cap L$ quhet i pakalueshëm nëse nuk mund të shkruhet si shuma e dy elementeve jozero, dmth. $x=y+z$ nënkupton $y=0$ ose $z=0$ .