Lineáris és logikai következmény tétele forrásának megtekintése

A <math>cx \leq \gamma</math> '''logikai következménye''' a <math>Qx \leq b</math>-nek, ha az egyenlőtlenségrendszer minden megoldása az egyenlőtlenségnek is megoldása. Ez azzal egyenértékű, hogy a <math>Qx \leq b</math> megoldáshalmaza teljes egészében a <math>cx \leq \gamma</math> zárt féltérben van.
A <math>cx \leq \gamma</math> '''lineáris következménye''' a <math>Qx \leq b</math>-nek, ha van olyan <math>y \geq 0</math> <math>yQ=c</math> és <math>yb \leq \gamma.</math>
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ás]]ban.
==A tétel bizonyítása==
Tegyük fel, hogy a <math>cx \leq \gamma</math> egyenlőtlenség lineáris következménye az általánosabb
<math>Px-0+Ax_1=b_0</math> <math>Qx_0+Bx_1 \leq b_1</math> <math>x_1 \geq 0</math>
egyenlőtlenségrendszernek. Megmutatjuk, hogy logikai is.
A következmény lineáris, ezért van <math>y \geq 0</math> <math>y_0P+y_1Q=c_0 </math> <math>y_0A+y_1B \geq c_1 y_1 \geq 0</math> <math>yb \leq \gamma.</math>
Ekkor az általánosabb egyenlőtlenségrendszer bármely ''x'' megoldására
<math>cx=c_0x_0+c_1x_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=</math><math>=yMx=y_0[Px_0+Ax_1]+y_1[Qx_0+Bx_1] \leq y_0b_0+y_1b_1=yb \leq \gamma.</math>
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'', <math>y \geq 0</math>
Ehhez tekintsük először az <math>R=\{x: Qx \leq b\}</math> poliédert, és tegyük fel, hogy nem üres.
Ha a logikai következmény lineáris, akkor van ''y'', hogy
<math>y \geq 0</math> <math>yQ=c</math> <math>yb \leq \gamma.</math>
Ha indirekt nincs ilyen ''y'', akkor a [[Farkas-lemma]] balról szorzós alakja miatt van
<math>(x, \alpha),</math> hogy <math>\alpha \geq 0,</math> <math>Qx- \alpha b \leq 0</math> <math>cx- \alpha \gamma >0.</math>
Ha <math>\alpha >0,</math> akkor leosztva feltehető, hogy <math>\alpha =1.</math> Ekkor az egyenlőség ekvivalens a
<math>Qx \leq b</math> <math>cx > \gamma</math>
rendszerrel. De ekkor ''x'' létezése cáfolja, hogy <math>cx \leq \gamma</math> logikai következmény lenne.
Ha feltesszük, hogy <math>\alpha =0,</math> akkor szintén ellentmondást kapunk.
Ekkor ugyanis az egyenlőség ekvivalens a
<math>Qx \leq 0</math> <math>cx > 0</math> rendszerrel.
Ekkor minden <math>z \in R</math> vektorra, és <math>\lambda >0</math> számra <math>z+ \lambda x \in R.</math> Így <math>c(z+\lambda x)</math> akármekkora lehet, és <math>cx \leq \gamma</math> 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:
<math>cx \leq \gamma</math>
és van <math>y=(y_0,y_1)</math> <math>y_1 \geq 0</math> <math>y_0P+y_1Q=c</math> <math>yb \leq \gamma</math>
A <math>Px=b_0</math> egyenlőségrendszert egyenlőtlenségekbe téve <math>Px \leq b_0</math> <math>Px \geq b_0</math> lesz.
Felhasználva az egyszerű esetet:
van <math>(y_0^1,y_0^2,y_1) \geq 0</math> <math>y_0^1P+y_0^2(-P)+y_1Q=c</math> és <math>y_0^1b_0+y_0^2(-b_0)+y_1 \leq \gamma.</math> Ekkor <math>y_0=y_0^1-y_0^2</math> 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''<sub>1</sub> 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==
*[http://www.cs.elte.hu/~frank/jegyzet/opkut/ulin.2008.pdf Frank András: Operációkutatás]
{{Portál|matematika}}
{{DEFAULTSORT:Lineáriséslogikaikövetkezménytétele}}
[[Kategória:Lineáris algebra]]
[[Kategória:Matematikai tételek]]
[[Kategória:Operációkutatás]]