Matematické Fórum

Hertas · 05. 10. 2014 17:04

Zdravím,

mám tady větu z lineárního programování a nerozumím dvěma krokům v důkazu, věta zní:

Buď $P\subseteq \mathbb{R}^n$ mnohostěn a P definováno jako: $P = \{x\in \mathbb{R}^n|Ax\le b\}$ , kde $A\in \mathbb{R}^{m\text{ x }n}$ a $b\in \mathbb{R}^m$ . Bod $x_0\in P$ je extrém v P právě když $x_0$ je průsečíkem n lineárně nezávislých nadrovin z množiny definující P

dk: předp., že $x_0$ je průsečíkem n nadrovin, potom $x_0$ leží v n nadrovinách
pro spor předpokládejme, že $x_0$ není extrém, potom musí existovat body $x_1, x_2 \in P$ a $\lambda \in (0,1)$ tak, že $x_0 = \lambda x_1+(1-\lambda )x_2$
pak pro nějaké $G \in \mathbb{R}^{n\text{ x }n}$ jehož řádky jsou vzaty z A a vector g jehož prvky jsou prvky z b, je $Gx_0 = g$ a tedy
(1.0) $g = Gx_0=\lambda Gx_1+(1-\lambda )Gx_2$
a $Gx_1\le g$ a $Gx_2\le g$ . Ale aby splňovaly (1.0) musí platit $Gx_1= g$ a $Gx_2= g$ což vede ke sporu

čemu nerozumím je:
1. jak se získá G a g, pokud m < n?
2. proč musí platit $Gx_1= g$ a $Gx_2= g$ ?

Za každou radu budu vděčný

Rumburak · 06. 10. 2014 10:47

↑ Hertas:

Ahoj. Co to znamená (tedy jak je definováno) , že

Bod $x_0\in P$ je extrém v P

?

Hertas · 06. 10. 2014 14:53 — Editoval Hertas (06. 10. 2014 22:03)

$x_0$ je extrém v P právě když neexistuje žádná dvojice $x_1, x_2\in P$ $x_1, x_2 \not =x_0$ a $\lambda \in (0,1)$ tak, že $x_0 = \lambda x_1+(1-\lambda )x_2$
(tzn. $x_0$ se nedá zapsat jako konvexní kombinace dvou jiných bodů z P)

Brano · 06. 10. 2014 15:33 — Editoval Brano (06. 10. 2014 15:37)

1) ak mas $m<n$ tak tam nemozes mat asi ziaden extrem - predstav si, ze v $R^2$ mas iba jednu hranicnu priamku
- potrebujes aspon 2 aby si tam mal extremny bod

2) ak by trebars $Gx_1< g$ tak z toho, ze $Gx_2\le g$ a $g = Gx_0=\lambda Gx_1+(1-\lambda )Gx_2$ dostanes, ze $g<g$ co je spor

Hertas · 06. 10. 2014 22:10 — Editoval Hertas (06. 10. 2014 22:11)

dobře, mějme omezení v $\mathbb{R}^2$ $x_1+x_2\le 1$ $x_1, x_2\ge 0$
m = 1 < 2 = n
jestli dobře koukám, tak body x = (0, 1), nebo x = (1, 0) nelze nakombinovat za daných podmínek