|
Ez a szócikk vagy szakasz lektorálásra, tartalmi javításokra szorul. A felmerült kifogásokat a szócikk vitalapja részletezi (vagy extrém esetben a szócikk szövegében elhelyezett, kikommentelt szövegrészek). Ha nincs indoklás a vitalapon (vagy szerkesztési módban a szövegközben), bátran távolítsd el a sablont! Csak akkor tedd a lap tetejére ezt a sablont, ha az egész cikk megszövegezése hibás. Ha nem, az adott szakaszba tedd, így segítve a lektorok munkáját! |
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ása
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 (ismeretlen „\begin{multyline}” függvény): {\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ások