Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

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.

Nota: essendo B una matrice di base \det(B)\not= 0 .

I materiali di supporto della lezione

D. Bertsimas e J.N. Tsitsiklis, Introduction to Linear Optimization, Belmont - Massachusetts (USA), Dynamic Ideas and Athena Scientific, 2008.

M. Fischetti, Lezioni di Ricerca Operativa, Padova, Edizioni Libreria Progetto Padova, 1999.

S. Martello, Fondamenti di Ricerca Operativa L-A, Bologna, Società Editrice Esculapio, 2004.

S. Martello, Ricerca Operativa LS, Bologna, Società Editrice Esculapio, 2004.

Dispense del Corso di Ricerca Operativa presso l'Università degli Studi di Pisa.

Dispense ed Appunti del Corso prodotte da Paola Festa.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion