Bázismegoldás

Tekintsük a $Px=b_{0}$ $Qx\leq b_{1}$ rendszerrel definiált R poliéder egy $z$ elemét. Jelölje $M_{z}^{=}$ azoknak a P-beli és Q-beli soroknak az összességét, amiket z egyenlőséggel teljesít. $z$ a $Px=b_{0}$ $Qx=b_{1}$ rendszer bázismegoldása, ha az $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.

Tulajdonságok

• 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.

Más alakú egyenlőtlenségrendszerek bázismegoldásai

• Az $Ax=b$ $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 $yA\geq 0$ $yb=-1$ rendszer bázismegoldásai azok az y₀ poliéderbeli elemek, amik merőlegesek $A$ $\mathrm {rang} (A,b)-1$ lineárisan független oszlopára.
• Az x=(x₀,x₁) poliéderbeli elem a $Px_{0}+Ax_{1}=b$ $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 $Bx\leq b$ $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.

Erős bázismegoldás

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 $Px=b_{0}$ $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 $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.

Források

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