Konvexita množin řešení
Úloha číslo: 3255
Ukažte, že pro úlohu LP ve tvaru \(\max \mathbf c^T\mathbf x\) za podmínek \(A\mathbf x\le \mathbf b\) je množina přípustných řešení i množina optimálních řešení konvexní.
Řešení
Konvexita množiny přípustných řešení: poloprostor daný jednou nerovností je konvexní, jsou-li v něm dva vektory \(\mathbf x,\mathbf x'\) potom z \(\mathbf a_i\mathbf x\le b_i\) a \(\mathbf a_i\mathbf x'\le b_i\) potom platí: \[\mathbf a_i(\alpha \mathbf x + (1-\alpha)\mathbf x')=\alpha \mathbf a_i\mathbf x + (1-\alpha)\mathbf a_i\mathbf x'\le \alpha b_i+(1-\alpha)b_i=b_i\]
Podobně pro množinu optimálních řešení, jsou-li \(\mathbf x,\mathbf x'\) dvě optimální řešení, platí \(\mathbf c^T\mathbf x=\mathbf c^T\mathbf x'=z\) a tudíž \[\mathbf c^T(\alpha \mathbf x + (1-\alpha)\mathbf x')=\alpha\mathbf c^T\mathbf x +(1-\alpha)\mathbf c^T\mathbf x'=\alpha z+(1-\alpha)z=z\]
