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

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

A lineáris következménye a -nek, ha van olyan és

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ásaSzerkesztés

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

      egyenlőtlenségrendszernek. Megmutatjuk, hogy logikai is.

A következmény lineáris, ezért van        

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

Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\displaystyle \begin{multyline}cx=c_x_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=yMx=y_0[Px_0+Ax_1]+y_1[Qx_0+Bx_1] \leq y_0b_0+y_1b_1=yb \leq \gamma.\end{multyline}}

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,   Ehhez tekintsük először az   poliédert, és tegyük fel, hogy nem üres.

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

     

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

  hogy      

Ha   akkor leosztva feltehető, hogy   Ekkor az egyenlőség ekvivalens a

   

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

Ha feltesszük, hogy   akkor szintén ellentmondást kapunk.

Ekkor ugyanis az egyenlőség ekvivalens a

    rendszerrel.

Ekkor minden   vektorra, és   számra   Így   akármekkora lehet, és   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:

 

és van        

A   egyenlőségrendszert egyenlőtlenségekbe téve     lesz. Felhasználva az egyszerű esetet:

van     és   Ekkor   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 b1 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ásokSzerkesztés