8) Operaciokutatas

Lienaris egyenletrendszerek

Tetel: Egy $Ax=0$ homogen egyenletrendszer megoldas-halmaza eloall $\{yB:y\in {\mathbb{R}}^2\}$ alakban.
Tetel: Ha $Ax=b$ egyenletrendszernek $x_0$ egy megoldasa, akkor a megoldashalmaz eloall $\{yB+x_0:y\in {\mathbb{R}}^n\}$ alakban.

Tetel: (Fredholm alternativa tetel) Az $Ax=b$ rendszernek akkor es csak akkor van megoldasa, ha nem letezik olyan $y$, amelyre $yA=0$ es $yb\ne 0$.
Megj.: A Gauss eliminacio vegen vagy egy redukalt lepcsos alakot kapunk vagy van tilos sor.

Linearis egyenlotlensegrendszerek tulajdonsagai

A tovabbiakban a

$$Ax\le b$$

rendszert vizsgaljuk. Felmerul a kerdes, hogy van-e megoldasa ennek a rendszernek, erre a Farkas lemma ad valaszt. Felmerul a kerdes hogy milyen alaku a megoldashazlma, erre a politederek adnak valaszt. Hogyan lehet megadni a rendzsernek megoldashalmazat parameteresen, erre valaszt ad majd az hogy minden korlatos polieder politop es forditva.

Kupok

Def.: (kup) A $C$ nemures halmaz kup ha $\alpha \cdot x\in C$ minden $\alpha \in {\mathbb{R}}^{+}$ es $x\in C$-re.
Def.: (konvex kup) A $C$ kup konvex ha $x+y\in C$ minden $x,y\in C$-re.
Def.: (generalt kup) A $C$ nemures halmaz generalt kup ha letezik $a_1,\dots ,a_n\in {\mathbb{R}}^m$ vektor melyre $C=\left\{\sum {\lambda }_i{a}_i:{\lambda }_i\ge 0\right\}$.
Tehat $n$ vektor nemnegativ linearis kombinacioinak halmaza egy generalt kup.
Megj.: Elkepzelhetjuk az $A\in {\mathbb{R}}^{m\times n}$ matrixot ahol $A$ oszlopai $a_i$ vektorok. Ekkor a kovetkezokeppen is tudjuk definialni $C$-t:

$$C=\{Ax:x\ge 0\}.$$

Def.: (metszet kup) A $C$ nemures halmaz metszet kup, ha letezik $b_1,\dots ,b_m\in {\mathbb{R}}^n$ melyre $C=\{x:b_{1}x\le 0,\dots ,b_{m}x\le 0\}$.
Megj.: Elkepzelhetjuk a $B\in {\mathbb{R}}^{m\times n}$ matrixot ahol $B$ sorai a $b_i$ vektorok. Ekkor a kovetkezokeppen is tudjuk definialni $C$-t:

$$C=\{x:Bx\le 0\}.$$

Def.: Egy $q\ne 0$ vektor eseten a $\{\lambda q:\lambda \in {\mathbb{R}}^{+}\}$ halmazt iranynek nevezunk.
Def.: Egy felegyenesen egy irany eltoltjat ertjuk.
Def.: Egy kup polarisan azon vektorok halmazat ertjuk, melyeknek a skalaris szorzata minden kupbeli elemmel nem pozitiv, tehat

$$K^{\ast }=\{x:x\cdot z\le 0\forall z\in K\}.$$

Politopok

Def.: Veges sok pont konvex burka politop.

Poliederek

Def.: Veges sok felter metszete polieder. $R=\{x:Qx\le b\}$, ahol $Q\in {\mathbb{R}}^{m\times n}$ es $b\in {\mathbb{R}}^m$. Tehat egy linearis egyenlotlensegrendszer megoldashalmaza.
Def.: Azt mondjuk, hogy a $q$ vektor mozgasvektora a $z\in R$ polieder elemenek, ha letezik $\lambda >0$ melyre $z+\lambda q\in R$ es $z-\lambda q\in R$.
Def.: Azt mondjuk, hogy a $z\in R$ a polieder relativ belso pontja ha van mozgasvektora, es azt mondjuk, hogy extrem pont ha nincs.
Def.: Ha minden vektor mozgasvektora $z\in R$-nek, akkor belso pont.
Megj.: A kulonbseg a relativ belso pont es a belso pont kozott az hogy a relativ belso pont lehet egy egyenesen vagy egy sikon, mig a belso pont korul van egy kicsi sugaru gomb mely a poliederben van.
Def.: Egy $R\subseteq {\mathbb{R}}^n$ nemures polieder $F$ oldala $R$-nek egy

$$F=\{x\in R:cx=\delta \}$$

alaku nemures reszhalmaza, ahol $\delta =\max \{cx:x\in R\}$ valamely $cx$ linearis celfuggvenyre, melyre a maximum letezik.
Def.: Egy polieder valodi oldalan olyan oldalt ertunk, mely nem az egesz polieder.
Def.: Egy polieder csucsan egy egyelemu oldalt ertunk.

Felbontasi tetelek

Tetel: Egy politop es egy generalt kup osszege polieder. Specialisan, minden politop korlatos polieder es minden generalt kup eloall metszetkupkent.
Tetel: Minden metszetkup eloall generalt kupkent.
Tetel: Minden nemures polieder eloall mint egy politop es egy generalt kup osszege. Specialisan, minden korlatos polieder politop.
Megj.:

• polieder = politop + generalt kup
• metszet kup = generalt kup
• politop = korlatos polieder

Bazismegoldasok, eros bazismegoldasok

Def.: Az $R=\{x:Qx\le b\}$ polieder egy $z$ elemere nezve a $Q$ matrix egy sorat $z$-aktivnak hivjuk, ha $z$ egyenloseggel teljesul. A $z$-re nezve aktiv sorok reszmatrixat a $Q$ $z$-aktiv reszmatrixanak nevezzuk es $Q_z^{=}$-fel jeloljuk
Def.: A $z\in R$ elem szintjen a $\sigma (z)=r(Q)-r(Q_z^{=})$ szamot ertjuk.
Def.: A $Qx\le b$ rendszer $z$ megoldasat bazismegoldasnak nevezzuk, ha a $z$-aktiv $Q_z^{=}$ reszmatrix rangja $r(Q)$, mas szoval ha $\sigma (z)=0$.
Def.: Ha egy bazis megoldas ezen felul olyan, hogy a $z$ nem nulla komponenseinek megfelelo $Q$ oszlopai linearisan fuggetlenek, akkor eros bazis megoldasnak hivjuk.
Megj.: Ha $Q$ teljes rangu, tehat oszlopai linearisan fuggetlenek, akkor minden bazis megoldas eros bazis megoldas.

Tetel:

1. Minden megoldhato linearis egyenlotlenseg rendszernek letezik bazis megoldasa, nevezetesen barmely minimalis szintu $z$ megoldas bazis megoldas.
2. Letezik eros bazis megoldas is, nevezetesen egy maximalisan sok $0$ komponenst tartalmazo $z$ bazis megoldas eros.

Tetel: A $Qx\le b$ egyenlotlenseg rendszer egy $z$ megoldasa akkor es csak akkor eros bazis megoldas, ha letezik $Q$-nak egy olyan $r(Q)$ sorbol es $r(Q)$ oszlopbol allo nem szingularis $Q^{\prime }$ reszmatrixa, amelyre $z$ a $Q^{\prime }{x}^{\prime }=b^{\prime }$ egyertelmu $x^{\prime }$ megoldasabol allo elo $0$ komponensek kiterjesztesevel.
Kov.: Legfeljebb veges sok eros bazis megoldas van.

Farkas-lemma

Tetel: $\exists x:Ax\le b⟺\nexists y:yA=0,yb<0,y\ge 0$.
Tetel: Az $\{Ax=b:x\ge 0\}$ rendszernek pontosan akkor van megoldasa, ha az $\{yA\ge 0:yb<0\}$ rendszernek nincs.

Alkalmazasai

Nem tudom, van egy kovetelmeny rendszered es megnezed hogy lehet-e kielegiteni. Peldaul van egy szoftver csomagod ami csak ennek ezzel a verziojaval mukodik es annak azzal a verziojaval stb., ekkor meg kell oldanod egy linearis egyenlotlenseg rendszert. (Dependency resolution.)

Linearis optimalizalas

Tetel: (Iranymenti korlatossag tetele) …
Def.: Linearis programozasi feladat

$$\begin{array}{r}\text{s.t.}Ax\le b\\ \max cx\end{array}$$

Tehat keresunk egy olyan $x$-et amelyre teljesul egy egyenlotlenseg rendszer es maximalizalja a $c\cdot x$ celfuggvenyt.
Megj.: Meglepoen sok dolog irhato fel ebben az egyszeru alakban. Sajat tapasztalatbol: sudoku, kakuro, mosaic.

Dualitas

Tetel: (Gyenge dualitas)

$$\max \{cx:Qx\le b\}\le \min \{yb:yQ=c,y\ge 0\}.$$

Biz.:

$$yb-cx=yb-yQx=y(b-Qx)\ge 0$$

mert $y\ge 0$ es $Qx\le b⟹b-Qx\ge 0$. Tehat $yb-cx\ge 0⟹yb\ge cx$.

Tetel: (Eros dualitas) Ha $\exists x:Qx\le b$ es $\exists y:yQ=c,y\ge 0$, azaz a primal es dual feladat is megoldhato, akkor

$$\max cx=\min yb.$$

Szimplex modszer

Huh… Vizualok nelkul nehez leirni szoban, de

Ismetlesul: $x$ bazis megoldas $⟺$ letezik $B$ az $A$ oszlopainak reszhalmaza, melyre $B$ az oszlopter egy bazisa.

Celunk az, hogy talaljunk egy $x$ vektort melyre $Ax=b$ es $x\ge 0$. Feltesszuk hogy $A$ oszlopai fuggetlenek.
Mivel $x\ge 0$ ezert vannak azok az elemei melyek $0$-ak es azok melyek $>0$, tehat felirhatjuk a kovektezo alakban $x$-et:

$$x=(0\dots 0z0\dots 0).$$

Legyen $B$ azon reszmatrix mely tartalmazza azon oszlopokat melyre $x_i\ne 0$. Ekkor nyilvan $\exists !z:Bz=b$.
A szimplex modszer ugy fog menni, hogy egy bazist iteralunk addig ameddig el nem jutunk egy megengedett megoldasig.

Altalanos lepes:
A $B$ bazist vizsgaljuk.
Megoldjuk a $Bz=b$ egyenletet amibol magkapjuk a $z$ vektort.
Ha $z\ge 0$, akkor keszen vagyunk mert $x=(0\dots 0z0\dots 0)\ge 0$ es megoldasa $Ax=b$ rendszernek.
Ha $z\ngeqq 0$, akkor letezik $z_i$ melyre $z_i<0$.
Most jon a trukk: Vegyuk a $w=(0\dots 010\dots 0)$ vektort, ami akkora mint $B$ szelteben es pont ott van $1$-es ahol $z_i<0$.
Ekkor oldjuk meg az $yB=w$ rendszert es megkapjuk az $y$ vektort.
Nezzuk meg hogy $yb$ mire jon ki:

$$yb=y(Ax)=z_i<0.$$

Tehat azt kapjuk, hogy $yb<0$. Innen megint kette agazunk.
Ha $yA\ge 0$, akkor $y$ a dualis feladat megoldasa, tehat a Farkas lemma miatt a primalnak nincs megoldasa.
Ha $yA\ngeqq 0$, akkor letezik $j$ mire $y{a}_j<0$, es ekkor csereljuk fel az $a_i$ es $a_j$ oszlopvektorokat es folytassuk ezzel az uj bazissal az iteracoit.

Megj.: (Bland szabaly) Tobb serto index esetben a minimalis indexet valasztjuk.
Lemma: A Bland szabaly mellett veges az algoritmus.

Teljesen unimodularis (TU) matrixok

Def.: Azt mondjuk, hogy a $Q$ egeszerteku matrix teljesen unimodularis, ha minden aldeterminansa $0$, $-1$, vagy $+1$.
Tetel: Ha $Q$ TU matrix, akkor $(Q,I)$ is TU matrix, ahol $(A,B)$ azt jeloli hogy $A$ belle konkatenaljuk $B$-t.
Tetel: Ha $Q$ TU matrix, akkor $(Q,-Q)$ is TU matrix.

TU matrixok alkalmazasai

Tetel: Tetszoleges $M$ TU matrixszal megadott egyenlotlenseg rendszer eseten, ha a $b$ jobboldali korlatozo vektor egesz ($Ax\le b$), akkor minden eros bazis megoldas egesz
Tetel: Digraf incidencia matrixa TU matrix.
Tetel: Paros graf incidencia matrixa TU matrix.