Home

Federica EU

1/6

Paola Festa » 11.Problemi di Programmazione Lineare Intera

Problema di Programmazione Lineare Intera (PLI)

Un generico problema di Programmazione Lineare Intera (PLI) in forma standard è un problema del tipo

$\begin{array}{lllll} \mbox{{\rm (Pli)}} & \mbox{{\rm min}} & z(x)& =& c'x \\ & \mbox{{\rm s.a}} \\ & & Ax & =& b \\ & &\ \ x&\geq& 0\ \mbox{{\rm ed intero}}, \end{array}$

dove

$A\in {\mathbb R}^{m\times n}$ è la matrice dei coefficienti tecnologici;

$b\in {\mathbb R}^m$ è il vettore dei termini noti;

$c\in {\mathbb R}^n$ è il vettore dei coefficienti della funzione obiettivo che possono essere coefficienti di costo (problema di minimo) oppure coefficienti di profitto (problemi di massimo);

$x\in {\mathbb Z}^n$ è il vettore delle variabili di decisione vincolate ad essere nonnegative ed intere.

Programmazione Lineare Intera, 2

Il vincolo di interezza sulle variabili di decisione definisce un reticolo di punti in ${\mathbb R}^n$ , alcuni dei quali costituiscono la regione ammissibile del problema (Pli) e cioè quelli che soddisfano $x\geq 0$ e $Ax=b$ .

In particolare, la regione ammissibile per il problema (Pli) sarà l’insieme

$X=P\cap {\mathbb Z}^n\subset P,$

dove
$P=\{x\in {\mathbb R}^n\ \vert\ Ax=b,\ x\geq 0\}.$

Rappresentazione grafica della regione ammissibile di un generico problema di PLI. Disegnata da Paola Festa

Rilassamento continuo, 1

A differenza dei problemi di Programmazione Lineare Continua, non esiste un unico metodo in grado di risolvere tutta la classe dei problemi di Programmazione Lineare Intera (vedi il Metodo del Simplesso).

Un semplice procedimento per tentare di risolvere il problema (Pli) è il seguente.

Si ignora il vincolo di interezza imposto alle variabili di decisione, ottenendo il seguente problema di PL in forma standard:
$\begin{array}{lllll} \mbox{{\rm (Pli-c)}} & \mbox{{\rm min}} & z(x)& =& c'x \\ & \mbox{{\rm s.a}} \\ & & Ax & =& b \\ & &\ \ x&\geq& 0. \end{array}$

(Pli-c) è detto rilassamento continuo di (Pli) e può essere risolto applicando il Metodo del Simplesso.

Rilassamento continuo, 2

Dal momento che $X\subset P$ , si ha che
$z^*_{\mbox{{\rm (Pli-c)}}}=\min\{c'x\ \vert\ x\in P\}\leq \min\{c'x\ \vert \ x\in X\}=z^*_{\mbox{{\rm (Pli)}}}.$
Dunque, $z^*_{\mbox{{\rm (Pli-c)}}}$ è un limite inferiore (lower bound) per $z^*_{\mbox{{\rm (Pli)}}}$ .

Sia $x^*$ la soluzione ottima di (Pli-c) cui corrisponde il valore ottimo della f.o. $z^*_{\mbox{{\rm (Pli-c)}}}$ .

Se tutte le componenti di $x^*$ sono intere, allora $x^*$ è soluzione ottima anche per il problema (Pli), cioè

$z^*_{\mbox{{\rm (Pli-c)}}}=z^*_{\mbox{{\rm (Pli)}}}.$

Matrice dei vincoli unimodulare, 1

E’ chiaro che il procedimento appena descritto è in generale destinato a fallire, fatta eccezione di un caso particolare che per essere descritto e compreso necessita della seguente definizione.

Definizione. Una matrice $A\in {\mathbb Z}^{m\times n},\ m\leq n$ , si dice unimodulare se per ogni sua sottomatrice quadrata $B\in {\mathbb Z}^{m\times m}$ risulta che
$\det(B)\in\{-1,0,1\}.$

Teorema. Sia $A\in {\mathbb Z}^{m\times n}$ una matrice unimodulare e sia $b\in {\mathbb Z}^m$ , allora il poliedro $P=\{x\in {\mathbb R}^n\ \vert\ Ax=b,\ x\geq 0\}$ ha solo vertici interi.

Dim. Sia $x^*$ una generica soluzione di base ammissibile per $P$ e sia $B$ la matrice di base ad essa associata.
Sappiamo che

$\begin{displaymath}x^*=\left( \begin{array}{c}x^*_B\\x^*_N\end{array}\right)=\left( \begin{array}{c}B^{-1}b\\\overline{0}\end{array}\right).\end{displaymath}$

Matrice dei vincoli unimodulare, 2

Dunque, $x^*$ ha componenti intere se $B^{-1}b$ ha componenti intere.
Dal momento che il vettore dei termini noti $b$ ha componenti intere per ipotesi, rimane solo da analizzare in quale caso $B^{-1}$ abbia tutti elementi interi.

Per definizione, si ha che
$B^{-1}\stackrel{\mbox{def}}{=}\frac{1}{\det(B)}\left[\begin{array}{rrrr}\alpha_{11}&\alpha_{12}&\cdots&\alpha_{1m}\\\alpha_{21}&\alpha_{22}&\cdots&\alpha_{2m}\\\cdots&\cdots&\cdots \cdots\\\alpha_{m1}&\alpha_{m2}&\cdots&\alpha_{mm}\end{array}\right]^T,$

dove $\alpha_{ij}=(-1)^{i+j}\det (M_{ij})$ e $M_{ij}$ è la sottomatrice di $B$ ottenuta eliminando da $B$ la riga i.ma e la colonna j.ma.

Ora, poiché $A$ ha componenti intere per ipotesi, anche $B$ ha tutti elementi interi e dunque anche gli $\alpha_{ij},\ i,j=1,2,\ldots,m$ , sono interi.
In conclusione, risulta che $B^{-1}$ ha tutti elementi interi se $\det(B)\in \{-1,1\}$ ; condizione quest’ultima verificata, dato che $A$ è unimodulare.