Problema di Programmazione Lineare (PL)

uni
Un problema di programmazione lineare segue il seguente Modello Matematico:

$$\{\begin{array}{l}min/max{c}^T\cdot x\\ A\cdot x\le b\\ B\cdot x\ge d\\ C\cdot x=e\\ \text{se non cooperativo aggiungere}x\in Z^n\end{array}$$

Ogni problema PL può essere portato nella seguente forma standard.

Un problema di Programmazione Lineare (PL) consiste nel trovare il massimo o il minimo di una funzione lineare soggetta ad un insieme finito di vincoli lineari di disuguaglianza o di uguaglianza.

Forma Standard

Una forma standard è un formato in cui possono essere portati TUTTI i problemi attraverso le trasformazioni equivalenti. Ciò si fa per semplicizzare oppure perché programmi come MatLab accettano solo alcuni formati standard.

Formato Primale Standard

$$\{\begin{array}{l}max{c}^T\cdot x\\ Ax\le b\end{array}$$

Formato Duale Standard

$$\{\begin{array}{l}min{b}^{T}y\\ A^{T}y=c\\ y\ge 0\end{array}$$

altro modo di scrivere il poliedro: $y^{T}A=c^T$
una sol è ammissibile se ogni comp è $\ge 0$
una sol è degenere se almeno una $x_B=0$

Formato Linprog Standard

$$\{\begin{array}{l}min{c}^{T}x\\ Ax\le b\\ A_{eq}=b_{eq}\\ LB\le x\le UB\end{array}$$

Trasformazioni Equivalenti

1. i $\ge$ diventano $\le$
2. i $=$ diventano un sistema $\{\begin{array}{l}\le \\ \le \end{array}$ RADDOPPIO DEI VINCOLI
3. i $min$ diventano $max$, poiché $\overline{x}\in argmaxf\leftrightarrow \overline{x}\in argmax-f$
4. $Ax\le b$ diventano un sistema $\{\begin{array}{l}Ax+S=b\\ S\ge 0\end{array}$ con $S$ dicesi $slack$ AGGIUNGO VARIABILE
5. $x\ge 0$ diventa $x_i=x_i^{++}-x_i^{+}$ RADDOPPIO DELLE VARIABILI

Soluzione Ottima

La Regione Ammissibile di un problema $(P)$ di programmazione lineare è un Poliedro $P$.

1. Il $max$ se esiste, appartiene al bordo (Teorema di Fermat)
2. Il $max$ può essere $+\infty$ (con $P$ illimitati)
3. La Soluzione Ottima non è per forza unica
4. $P$ può essere vuoto ($\to$ ranking dei vincoli)
5. Almeno un vertice è soluzione ottima
6. se la regione ammissibile si restringe i minimi salgono (Rilassamento)

Cono di Competenza = insieme di vettori $c$ che hanno tra le soluzioni ottimali lo stesso vertice. Si dice cono di competenza relativo ad un vertice.
Proposizione:
$(P)\in PL$:

1. se $maxcx=-\infty$ $⟹$ ha $P$ vuoto
2. può avere $P$ illimitato
3. se ha $2$ soluzioni ottime $⟹$ ha illimitate soluzioni ottime

Risoluzione di un Problema di Programmazione Lineare

Il Teorema Fondamentale dei Problemi PL ci dice che dato un problema con Poliedro non vuoto e soluzione limitata, la soluzione ottima esiste, inoltre, se il poliedro non è privo di vertici, per il Teorema di Fermat sappiamo che deve essere sul bordo e quindi almeno un vertice è soluzione.

Problemi

Problema di Produzione
Problema di Assegnamento
Problema di Trasporto