Tekintsük a ${\displaystyle Px=b_{0))$ ${\displaystyle Qx\leq b_{1))$ rendszerrel definiált R poliéder egy ${\displaystyle z}$ elemét. Jelölje ${\displaystyle M_{z}^{=))$ azoknak a P-beli és Q-beli soroknak az összességét, amiket z egyenlőséggel teljesít. ${\displaystyle z}$ a ${\displaystyle Px=b_{0))$ ${\displaystyle Qx=b_{1))$ rendszer bázismegoldása, ha az ${\displaystyle M_{z}^{=))$ mátrix rangja megegyezik a P és a Q összes sorából alkotott M mátrix rangjával.

Bár egy, a poliédert leíró egyenlőtlenségrendszerrel szokás definiálni, a bázismegoldás nem függ a poliéder megadásának módjától. A lineáris optimalizálás szempontjából fontos, hogy az adott poliéderen értelmezett lineáris függvények szélsőértéküket valamelyik bázismegoldáson veszik fel.

A lineáris optimalizálásban poliéderen lineáris egyenlőtlenségrendszerek megoldáshalmazát értenek. Ezzel a terminológiával élve egy lineáris altér, egy féltér ugyanúgy poliéder, mint például a kocka. Mivel a lineáris egyenlőtlenségrendszerek megoldáshalmaza félterek metszeteként áll elő, ezért ezek a poliéderek mind konvexek.

• Ha a poliédernek vannak csúcsai, akkor a csúcsai bázismegoldások.
• Megfordítva, egy csúcsos poliéder egy pontja bázismegoldás, ha csúcs.
• Minden nem üres poliédernek van bázismegoldása.
• A poliéderen értelmezett lineáris függvények, ha van szélsőértékük, akkor szélsőértéküket valamelyik bázismegoldáson veszik fel.

• Az ${\displaystyle Ax=b}$ ${\displaystyle x\geq 0/}$ rendszer bázismegoldásai azok a z poliéderbeli elemek, amik pozitív koordinátáihoz tartozó A-beli oszlopok lineárisan függetlenek.
• Az ${\displaystyle yA\geq 0}$ ${\displaystyle yb=-1}$ rendszer bázismegoldásai azok az y₀ poliéderbeli elemek, amik merőlegesek ${\displaystyle A}$ ${\displaystyle \mathrm {rang} (A,b)-1}$ lineárisan független oszlopára.
• Az x=(x₀,x₁) poliéderbeli elem a ${\displaystyle Px_{0}+Ax_{1}=b}$ ${\displaystyle x_{1}\geq 0}$ rendszer bázismegoldása, ha az xben az x₀ nem nulla elemeihez tartozó P-beli oszlopokhoz az A oszlopaiból rangnyi függetlent választva lineárisan független rendszerhez jutunk.
• A ${\displaystyle Bx\leq b}$ ${\displaystyle x\geq 0}$ rendszer bázismegoldásai azok az z poliéderbeli elemek, amikhez van B-nek egy nem szinguláris részmátrixa, amire a hozzá tartozó egyenletrendszert megoldva megkapjuk z összes nem nulla koordinátáját.

Ha az egyenlőtlenségrendszerrel leírt poliédernek vannak csúcsai, akkor véges sok csúcsa van, ezáltal véges sok bázismegoldása. De ha az egyenlőtlenségrendszer olyan poliédert ír le, aminek nincsenek csúcsai, akkor a poliéder összes pontja bázismegoldás, így a fogalom használhatatlanná válhat az optimalizálás szempontjából. Ezért vezetik be az erős bázismegoldást:

Definíció: A z bázismegoldás erős, ha a ${\displaystyle Px=b_{0))$ ${\displaystyle Qx\leq b_{1))$ rendszerben a z nem nulla koordinátáihoz tartozó oszlopok lineárisan függetlenek.

Az erős bázismegoldásra is igaz, hogy csak a poliédertől függ, és nem az azt leíró egyenlőtlenségrendszer alakjától, és ha egy lineáris függvénynek van szélsőértéke a poliéderen, akkor azt erős bázismegoldáson veszi fel.

A ${\displaystyle Qx\leq b_{1))$ rendszer erős bázismegoldásai pontosan azok a poliéderben levő pontok, amik megkaphatók a következő módon: Vesszük a Q mátrix egy rang x rang méretű részmátrixát, és megoldjuk a hozzá tartozó egyenlőtlenségrendszert. A megoldást kiegészítve megkapjuk a pontot.

Frank András: Operációkutatás