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

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

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

$Px-0+A{x}_1=b_0$ $Q{x}_0+B{x}_1\le b_1$ $x_1\ge 0$ egyenlőtlenségrendszernek. Megmutatjuk, hogy logikai is.

A következmény lineáris, ezért van $y\ge 0$ $y_{0}P+y_{1}Q=c_0$ $y_{0}A+y_{1}B\ge c_1{y}_1\ge 0$ $yb\le \gamma .$

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

$cx=c_0{x}_0+c_1{x}_1\le [(y_0,y_1)\left(\begin{array}{c}P\\ Q\end{array}\right)]x_0+[(y_0,y_1)\left(\begin{array}{c}A\\ B\end{array}\right)]x_1=$$=yMx=y_0[P{x}_0+A{x}_1]+y_1[Q{x}_0+B{x}_1]\le y_0{b}_0+y_1{b}_1=yb\le \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\ge 0$ Ehhez tekintsük először az $R=\{x:Qx\le b\}$ poliédert, és tegyük fel, hogy nem üres.

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

$y\ge 0$ $yQ=c$ $yb\le \gamma .$

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

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

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

$Qx\le b$ $cx>\gamma$

rendszerrel. De ekkor x létezése cáfolja, hogy $cx\le \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\le 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\le \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\le \gamma$

és van $y=(y_0,y_1)$ $y_1\ge 0$ $y_{0}P+y_{1}Q=c$ $yb\le \gamma$

A $Px=b_0$ egyenlőségrendszert egyenlőtlenségekbe téve $Px\le b_0$ $Px\ge b_0$ lesz. Felhasználva az egyszerű esetet:

van $(y_0^1,y_0^2,y_1)\ge 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\le \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