Mettiamo in luce le proprietà geometriche della regione ammissibile.
Iperpiano
L’insieme delle soluzioni di un’equazione lineare in
variabili.
Semispazio
L’insieme delle soluzioni di una disequeazione lineare in n variabili.
O, per riassumere:
| retta | iperpiano |
| semipiano | semispazi |
Problema di PL
Sistema di equazioni e diseguazioni lineari in
Poliedro
Intersezione di un numero finito di iperpiani e semispazi chiusi. Alias: un insieme convesso (vedi sotto)
Combinazione convessa
Sia
, è il punto con Propria
- La combinazione convessa di 2 punti dà il segmento che ha per estremi i due punti considerati;
- La combinazione convessa di 3 punti dà il triangolo
Combinazione convessa generale
Siano
, il punto si chiama combinazione convessa di questi punti. Con e la somma di tutti i
Insieme convesso
Un insieme
si dice convesso se anche il punto appartiene a Cioè dati due punti di k, il segmento ottenuto è tutto convenuto in .
Vertice
Un Vertice di un poliedro è un punto che non può essere espresso come combinazione convessa propria (cioè con
) di altri punti del poliedro. Un Vertice è un estremo di un segmento non può trovarsi “dentro” un segmento generato da altri punti.
Per riassumere
- La regione ammissibile di un problema di PL è un poliedro
è convessa; - I problemi di PL sono problemi convessi
Gli ottimi locali sono globali.
Teorema Fondamentale della PL
Dato il problema:
Teorema Fondamentale della PL
Se ha una soluzione ottima, allora esiste un vertice ottimo.
Conseguenza: La soluzione ottima va cercata fra i vertici
Esistono sempre vertici?
Risulta che un poliedro ha vertici
non contiene rette. C’è una sola situazione nella quale la regione ammissibile non ha vertici, contiene rette, e ha soluzioni ottime.
Il poliedro è una striscia.
Ci sono