Lineáris és logikai következmény tétele

A $cx\leq \gamma$ logikai következménye a $Qx\leq b$-nek, ha az egyenlőtlenségrendszer minden megoldása az egyenlőtlenségnek is megoldása. Ez azzal egyenértékű, hogy a $Qx\leq b$ megoldáshalmaza teljes egészében a $cx\leq \gamma$ zárt féltérben van.

A $cx\leq \gamma$ lineáris következménye a $Qx\leq b$-nek, ha van olyan $y\geq 0$ $yQ=c$ és $yb\leq \gamma .$

A lineáris és logikai következmények tétele azt mondja ki, hogy ez a két fogalom ekvivalens. A tételnek számos alkalmazása van a lineáris optimalizálásban.

A tétel bizonyítása

Tegyük fel, hogy a $cx\leq \gamma$ egyenlőtlenség lineáris következménye az általánosabb

$Px-0+Ax_{1}=b_{0}$ $Qx_{0}+Bx_{1}\leq b_{1}$ $x_{1}\geq 0$ egyenlőtlenségrendszernek. Megmutatjuk, hogy logikai is.

A következmény lineáris, ezért van $y\geq 0$ $y_{0}P+y_{1}Q=c_{0}$ $y_{0}A+y_{1}B\geq c_{1}y_{1}\geq 0$ $yb\leq \gamma .$

Ekkor az általánosabb egyenlőtlenségrendszer bármely x megoldására

$cx=c_{0}x_{0}+c_{1}x_{1}\leq [(y_{0},y_{1}){\begin{pmatrix}P\\Q\end{pmatrix}}]x_{0}+[(y_{0},y_{1}){\begin{pmatrix}A\\B\end{pmatrix}}]x_{1}=$$=yMx=y_{0}[Px_{0}+Ax_{1}]+y_{1}[Qx_{0}+Bx_{1}]\leq y_{0}b_{0}+y_{1}b_{1}=yb\leq \gamma .$

Tehát a lineáris következmény logikai is.

A másik irány bizonyítása nehezebb. Először az egyszerűbb rendszerre látjuk be, hogy a logikai következmény lineáris is, majd ezt általánosítjuk tovább.

A logikai következmény lineáris, ha van y, $y\geq 0$ Ehhez tekintsük először az $R=\{x:Qx\leq b\}$ poliédert, és tegyük fel, hogy nem üres.

Ha a logikai következmény lineáris, akkor van y, hogy

$y\geq 0$ $yQ=c$ $yb\leq \gamma .$

Ha indirekt nincs ilyen y, akkor a Farkas-lemma balról szorzós alakja miatt van

$(x,\alpha ),$ hogy $\alpha \geq 0,$ $Qx-\alpha b\leq 0$ $cx-\alpha \gamma >0.$

Ha $\alpha >0,$ akkor leosztva feltehető, hogy $\alpha =1.$ Ekkor az egyenlőség ekvivalens a

$Qx\leq b$ $cx>\gamma$

rendszerrel. De ekkor x létezése cáfolja, hogy $cx\leq \gamma$ logikai következmény lenne.

Ha feltesszük, hogy $\alpha =0,$ akkor szintén ellentmondást kapunk.

Ekkor ugyanis az egyenlőség ekvivalens a

$Qx\leq 0$ $cx>0$ rendszerrel.

Ekkor minden $z\in R$ vektorra, és $\lambda >0$ számra $z+\lambda x\in R.$ Így $c(z+\lambda x)$ akármekkora lehet, és $cx\leq \gamma$ nem logikai következmény.

Ezzel kész az egyszerűbb rendszer esete.

Ha P is van, akkor a lineáris következmény alakja:

$cx\leq \gamma$

és van $y=(y_{0},y_{1})$ $y_{1}\geq 0$ $y_{0}P+y_{1}Q=c$ $yb\leq \gamma$

A $Px=b_{0}$ egyenlőségrendszert egyenlőtlenségekbe téve $Px\leq b_{0}$ $Px\geq b_{0}$ lesz. Felhasználva az egyszerű esetet:

van $(y_{0}^{1},y_{0}^{2},y_{1})\geq 0$ $y_{0}^{1}P+y_{0}^{2}(-P)+y_{1}Q=c$ és $y_{0}^{1}b_{0}+y_{0}^{2}(-b_{0})+y_{1}\leq \gamma .$ Ekkor $y_{0}=y_{0}^{1}-y_{0}^{2}$ jó lesz.

Az általános alakhoz a B mátrix alá az egységmátrix negatívját, a Q mátrix alá a megfelelő méretű nullmátrixot írjuk, és a b₁ vektort nulla koordinátákkal egészítjük ki. Az előző esetet alkalmazva éppen az általános alakú lineáris következménnyel ekvivalens.

Források

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