P.L.I.

Programmazione lineare intera

Molti processi decisionali affrontati per la gestione di un' impresa si basano sull'utilizzo di modelli quantitativi detti di ottimizzazione in quanto il decisore sceglie, tra un insieme di decisioni attuabili, quella più conveniente economicamente.

Tra i modelli quantitativi la programmazione matematica,ossia la pianificazione delle azioni necessarie ad individuare la soluzione ottima, costituisce la metodologia di supporto alla decisione più efficace e più utilizzata nelle applicazioni di natura gestionale.
Un problema di ottimizzazione è di programmazione lineare se la funzione in n variabili da ottimizzare detta funzione obiettivo è lineare ed è sottoposta a un sistema di vincoli lineari e può essere espresso nella forma

MAX o MIN z=c^tx

Ax≤ b

x≥0;

In molti problemi concreti di scelta, cui è associato un modello di ottimizzazione, le variabili sono caratterizzate dal fatto di poter assumere soltanto valori interi. Tale tipologia di ottimizzazione è detta discreta o programmazione lineare intera e fu introdotta nel 1920 da Dickson .

Un problema di programmazione lineare intera (PLI) è del tipo:

z=c^tx

Ax≤ b

x≥0; x intero

La risoluzione di tali problemi può essere effettuata mediante gli algoritmi della programmazione lineare, rilassando il problema al continuo e arrotondando le soluzioni per difetto o per eccesso
In questo caso, però`, non e` garantito l'ottimalità della soluzione.

Rilassare al continuo significa rimuovere il vincolo di interezza., in questo modo si aggiungono soluzioni al problema originale e si può trovare un valore di ottimo( detto upper bound in un problema di max ) maggiore o uguale al valore ottimo di un problema di P.L.I. o un valore di ottimo (detto lower bound in un problema di minimo)minore o uguale al valore ottimo di un problema di P.L.I. Si possono verificare i seguenti casi:

se la soluzione del problema di P.L. è intera, essa è anche soluzione del problema di P.L.I;
le soluzioni di un problema di P.L. risultano inammissibili al corrispondente problema di P.L.I. se le soluzioni intere, ottenute arrotondando le precedenti, non appartengono alla regione ammissibile

Esistono diversi metodi per la risoluzione di problemi di P.L.I.: metodi esatti ( es. Branch and Bound) e metodi euristici( forniscono soluzioni che possono non essere ottime )
I problemi di programmazione lineare intera possono essere visionati come "alberi" decisionali dove ogni "foglia" rappresenta una possibile soluzione.
Un caso particolare di programmazione lineare intera si ha quando le variabili decisionali possono assumere valori 0; 1 e tale problema si dice di programmazione lineare binaria (ZOLP- zero-one linear program).