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

A ${\displaystyle cx\leq \gamma }$ logikai következménye a ${\displaystyle 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 ${\displaystyle Qx\leq b}$ megoldáshalmaza teljes egészében a ${\displaystyle cx\leq \gamma }$ zárt féltérben van.

A ${\displaystyle cx\leq \gamma }$ lineáris következménye a ${\displaystyle Qx\leq b}$-nek, ha van olyan ${\displaystyle y\geq 0}$ ${\displaystyle yQ=c}$ és ${\displaystyle 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 ${\displaystyle cx\leq \gamma }$ egyenlőtlenség lineáris következménye az általánosabb

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

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

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

${\displaystyle 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}=}$${\displaystyle =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, ${\displaystyle y\geq 0}$ Ehhez tekintsük először az ${\displaystyle 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

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

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

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

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

${\displaystyle Qx\leq b}$ ${\displaystyle cx>\gamma }$

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

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

Ekkor ugyanis az egyenlőség ekvivalens a

${\displaystyle Qx\leq 0}$ ${\displaystyle cx>0}$ rendszerrel.

Ekkor minden ${\displaystyle z\in R}$ vektorra, és ${\displaystyle \lambda >0}$ számra ${\displaystyle z+\lambda x\in R.}$ Így ${\displaystyle c(z+\lambda x)}$ akármekkora lehet, és ${\displaystyle 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:

${\displaystyle cx\leq \gamma }$

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

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

van ${\displaystyle (y_{0}^{1},y_{0}^{2},y_{1})\geq 0}$ ${\displaystyle y_{0}^{1}P+y_{0}^{2}(-P)+y_{1}Q=c}$ és ${\displaystyle y_{0}^{1}b_{0}+y_{0}^{2}(-b_{0})+y_{1}\leq \gamma .}$ Ekkor ${\displaystyle 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