Teorema Astratto di Equivalenza tra PL e PLI

uni

Prefazione

Prendiamo il Poliedro del rilassato continuo di un Problema di Programmazione Lineare Intera (PLI), quindi $Ax\le b;x\ge 0$.
Disegniamo i punti a componenti intere dentro il poliedro, questo insieme è la Regione Ammissibile del problema PLI.
Adesso unisco i vertici dell’insieme di punti disegnato, otteniamo una regione ammissibile, che è la più piccola regione ammissibile che contiene le soluzioni ammissibili del PLI, ovvero $convS$ (Teorema di Rappresentazione dei Poliedri (di Weyl)).
Quindi abbiamo i punti $S=\{x\in Z_{+}^n:Ax\le b\}$ e $p=\{Ax\le b,x\ge 0\}$
Dato il Th di Weyl abbiamo che ogni poliedro è $convS+conoE$ e ogni $convS+conoE$ è poliedro.
Quindi abbiamo il più piccolo poliedro che contiene $S$.
Quindi $convS\le P$ quindi

$$\{\begin{array}{l}max{c}^{T}x\\ x\in S\end{array}\le \{\begin{array}{l}max{c}^{T}x\\ x\in convS\end{array}\le \{\begin{array}{l}max{c}^{T}x\\ x\in P\end{array}$$

dove:

• $S$ è l’insieme dei punti a componenti intere dentro il poliedro del rilassato continuo.
• $convS$ è il convesso generato dai punti di $S$
• $P$ è il poliedro del rilassato continuo

Teorema

dati $A,b\in Z$

$$ma{x}_{x\in S}{c}^{T}x=ma{x}_{x\in convS}{c}^{T}x$$

questo perché i vertici di questi due insiemi sono gli stessi! E sappiamo che l’ottimo sta sui vertici.

Dimostrazione

a inizio quaderno