Farkasin lemma

Farkasin lemma on lause lineaaristen epäyhtälöiden ominaisuuksista. Sen muotoili ja todisti Gyula Farkas vuonna 1902 [1] . Käytetään geometrisessa ohjelmoinnissa .

Sanamuoto

Olkoon ja olla homogeenisia reaalimuuttujien lineaarisia funktioita . Oletetaan, että suhteet sisältävät epätasa-arvon . Sitten on ei-negatiivisia vakioita , joille identiteetti $f_{1}(x), f_{2}(x), ..., f_{r}(x)$ $g(x)$ $m$ $x_{1}, x_{2}, ..., x_{m}$ $f_{1}(x)\geqslant 0,f_{2}(x)\geqslant 0,...,f_{r}(x)\geqslant 0$ $g(x) \geqslant 0$ $y_{1}, y_{2}, ..., y_{r}$

y_{1}f_{1}(x)+y_{2}f_{2}(x)+...+y_{r}f_{r}(x)\equiv g(x).

Todiste

Todiste on kirjassa [2] .

Vastaavat formulaatiot

Seuraavassa tarkoitamme, että vektorin jokainen komponentti on positiivinen ; muut epätasa-arvot määritellään samalla tavalla. $\mathbf {x} >0$

Galen, Kuhnin ja Tuckerin muotoilu

Anna . Sitten joko on olemassa vektori , joka on ja , tai on olemassa vektori kuten ja [3] . ${\displaystyle \mathbf {A} \in \mathbb {R} ^{m\times n},\mathbf {x} \in \mathbb {R} ^{m))$ ${\mathbf {x}}\in {\mathbb {R}}^{n}$ $\mathbf {A} \mathbf {x} =\mathbf {b}$ $x \geqslant 0$ ${\displaystyle \mathbf {y} \in \mathbb {R} ^{m))$ $\mathbf {A} ^{\mathrm {T} }\mathbf {y} \geqslant 0$ $\mathbf {b} ^{\mathrm {T} }\mathbf {y} <0$

Tässä muotoilussa matriisin sarakkeet näyttelevät lineaarisia funktioita , sarake toimii funktiona , vektori sisältää kertoimia, jotka ovat samanlaisia kuin . Vektorin olemassaolo tarkoittaa, että alkuperäiset epäyhtälöt eivät tarkoita . $\mathbf {A}$ $f_{i}(x)$ ${\mathbf {b}}$ $g(x)$ $\mathbf {x}$ $y_{1}, y_{2}, ..., y_{r}$ $\mathbf {y}$ $g(x) \geqslant 0$

Geometrinen tunne

Olkoon matriisin sarakkeiden luoma kupera kartio . Sitä voidaan kuvata setiksi . Sitten Gale-Kuhn-Tucker-formulaatio voidaan muotoilla uudelleen seuraavasti: joko vektori sijaitsee kartiossa tai on hypertaso (ortogonaalinen vektoriin nähden ), joka erottaa kartiosta ja vektorista . $C(\mathbf {A} )$ $\mathbf {A}$ ${\displaystyle \{\mathbf {A} \mathbf {x} \mid \mathbf {x} \geqslant 0\))$ ${\mathbf {b}}$ $C(\mathbf {A} )$ $\mathbf {y}$ $C(\mathbf {A} )$ ${\mathbf {b}}$

Gordanin lause

Vuonna 1873 P. Gordan julkaisi lauseen, joka vastaa myöhemmin löydettyä, mutta paremmin tunnettua Farkas-lemmaa [4] .

Nykyaikaisin termein se kuulostaa tältä: joko epäyhtälöön on ratkaisu tai yhtälön nollasta poikkeava ratkaisu , niin että . $\mathbf {x}$ $\mathbf {A} \mathbf {x} <0$ $\mathbf {y}$ $\mathbf {A} ^{\mathrm {T} }\mathbf {y} =0$ $\mathbf {y} \geqslant 0$

Toisin sanoen joko sarakkeiden määrittelemä kartio on terävä ja siinä on tukihypertaso tai se ei ole terävä ja sen määrittelee ei-triviaali konveksi vektoreiden yhdistelmä, joka on yhtä suuri kuin nolla. $\mathbf {A}$

Muistiinpanot

↑ Farkas, J. Theorie der Einfachen Ungleichungen (saksa) // Journal für die reine und angewandte Mathematik . - 1902. - Bd. 124. - S. 1-27 . - doi : 10.1515/crll.1902.124.1 .
↑ Geometrinen ohjelmointi, 1972 , s. 263.
↑ Gale, D. , Kuhn, H. , Tucker, A. W. Lineaarinen ohjelmointi ja peliteoria - Luku XII // Tuotannon ja allokoinnin toimintoanalyysi (englanniksi) / Koopmans (toim.). - Wiley , 1951. - s. 318.
↑ Cherng-Tiao Perng. Huomautus Gordanin lauseeseen // British Journal of Mathematics & Computer Science. – 10.1.2015. — Voi. 10 , iss. 5 . - s. 1-6 . - doi : 10.9734/BJMCS/2015/19134 . Arkistoitu alkuperäisestä 14. syyskuuta 2021.

Kirjallisuus

R. Duffin, E. Peterson, K. Zener. Geometrinen ohjelmointi. - M . : Mir, 1972. - 311 s.