Teorema Fondamentale dei Problemi PL

uni
Se $P$ è limitato e non vuoto allora (almeno) un vertice di $P$ è ottimo.
Sia dato $(P)\{\begin{array}{l}max{c}^T\cdot x\\ Ax\le b\end{array}$ e la sua Rappresentazione di Weyl Teorema di Rappresentazione dei Poliedri (di Weyl).
supponiamo che il Poliedro $P$ sia non vuoto e che la soluzione sia limitata
Allora

$$\exists r\in \{1,..,k\}:ma{x}_{x\in P}{c}^{T}x=c^T{v}^r$$

Osservazioni

1. se $P$ è limitato allora $E=\{\vec{0}\}$
2. se $P$ ha vertici $V=\{vertP\}$
   tutti i poliedri limitati hanno vertici
   Tutti i poliedri senza vertici sono: semipiani, strisce e rette.

Quindi tolti questi 3 casi patologici:
1. poliedro vuoto
2. poliedro senza vertici
3. poliedro illimitato
Allora almeno un vertice è soluzione ottima.

Dimostrazione

copia da quaderno