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
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Paola Festa » 2.Introduzione ai Problemi di PL


Problemi di Programmazione Lineare

Un problema di Programmazione Matematica è detto di Programmazione Lineare (PL) se ciascuna delle funzioni z(x) e \{g_i(x):{\mathbb R}^n\rightarrow {\mathbb R},\i=1,2,\ldots,m\} e lineare rispetto alla variabile x, cioè se

\begin{array}{lll}z(x) & = & c_1x_1 + c_2x_2 + \cdots + c_nx_n \\g_i(x) & = & a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n,\ i=1,2,\ldots,m,\end{array}

dove c_j,\ j=1,2,\ldots,n e a_{ij},\ i=1,2,\ldots,m,\ j=1,2,\ldots,n sono costanti scalari date.

Riassumendo, un problema di PL e un problema del tipo

\begin{array}{llllll}\mbox{{\rm min (risp. max)}} & z(x) & = & c_1x_1 + c_2x_2 + \cdots + c_nx_n\\\mbox{{\rm s.a}} \\& & & a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n & \approx & b_1\\& & & a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n & \approx & b_2\\& & & \cdots & \approx & \cdots\\& & & a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n & \approx & b_m\end{array}

Definizione. Per problema di programmazione lineare (PL) s’intende il problema di minimizzare o massimizzare una funzione costo lineare in presenza di vincoli di disuguaglianza e/o uguaglianza lineari.

Esempi di PL: un problema di trasporto, 1

Si immagini un’industria che produce un bene di consumo in due diversi stabilimenti di produzione, situati rispettivamente a Pomezia e a Caserta.

La distribuzione alla rete di vendita avviene da due depositi situati rispettivamente a Roma e a Napoli.

Nell’immagine della Tabella per ogni unità di prodotto è riportato il costo legato al trasporto dal sito di produzione (Pomezia o Caserta) al deposito (Roma o Napoli). Inoltre, lo stabilimento di Pomezia non può produrre più di 10000 unità di bene, mentre quello di Caserta non ne può produrre più di 8000.
Da statistiche fatte sulle vendite, risulta che ogni settimana vengono vendute almeno 11000 unità di bene tramite il deposito situato a Roma e almeno 4600 unità tramite il deposito situato a Napoli.

Obiettivo dell’industria:
minimizzare il costo totale del trasporto della merce dagli stabilimenti ai depositi, assicurando al tempo stesso che ciascun deposito riceva settimanalmente le quantità medie su indicate.

Tabella tratta – costo del trasporto. Disegnata da Paola Festa

Tabella tratta - costo del trasporto. Disegnata da Paola Festa


Esempi di PL: un problema di trasporto, 2

Come costruire il modello logico-matematico a partire da questa descrizione verbale del problema e delle sue caratteristiche?

In questo caso, occorre definire 4 variabili di decisione indicanti le quantità di bene trasportate settimanalmente dagli stabilimenti ai depositi:

\begin{array}{lll}x_1 & = & \mbox{{\rm quantit\`a di bene trasportata da Pomezia a Roma;}} \\x_2 & = & \mbox{{\rm quantit\`a di bene trasportata da Pomezia a Napoli;}} \\x_3 & = & \mbox{{\rm quantit\`a di bene trasportata da Caserta a Napoli;}} \\x_4 & = & \mbox{{\rm quantit\`a di bene trasportata da Caserta a Roma.}}\end{array}

La funzione obiettivo sarà il costo totale sostenuto settimanalmente per il trasporto dagli stabilimenti ai depositi:

z(x_1,x_2,x_3,x_4) = 10x_1 + 30x_2 + 5x_3 + 35x_4.

I due stabilimenti hanno capacità produttiva limitata e tali limitazioni si traducono formalmente nell’imposizione dei vincoli

x_1 + x_2 \leq 10000 \ \mbox{e}\ x_3 + x_4 \leq 8000,

mentre il rifornimento medio settimanale ai depositi è garantito dall’imposizione dei vincoli

x_1 + x_4 \geq 11000 \ \mbox{e}\ x_2 + x_3 \geq 4600.

Esempi di PL: un problema di trasporto, 3

Infine, è più che evidente che ciascuna quantità x_j,\ j=1,2,3,4 non può essere negativa.

Dunque, il modello logico-matematico del problema di trasporto descritto verbalmente è il seguente:

\begin{array}{lll}\mbox{{\rm min}} & z(x) = & 10x_1 + 30x_2 + 5x_3 + 35x_4 \\\mbox{{\rm s.a}} \\& x_1 + x_2 & \leq 10000\\& x_3 + x_4 & \leq 8000 \\& x_1 + x_4 & \geq 11000\\& x_2 + x_3 & \geq 4600 \\& x_i\geq 0 & \mbox{{ed intero}},\ i=1,2,3,4.\end{array}

Esempi di PL: il problema della dieta, 1

Supponiamo di disporre di n alimenti caratterizzati da m fattori nutrizionali diversi.

Il generico elemento a_{ij} riportato in Tabella esprime il contenuto nutrizionale di tipo i di un’unità dell’alimento di tipo j.

Supponiamo che ad ogni unità di alimento di tipo j sia associato un costo c_j (prezzo al supermercato).

Indicato con b=(b_1,b_2,\ldots,b_m) il vettore contenente i valori nutrizionali di una dieta ideale per un adulto maschio di 30 anni, si vuole trovare la combinazione di alimenti x=(x_1,x_2,\ldots,x_n) che abbia il costo totale minimo e che al contempo soddisfi le esigenze nutrizionali contenute in b.

Tabella del contenuto nutrizionale. Disegnata da Paola Festa

Tabella del contenuto nutrizionale. Disegnata da Paola Festa


Esempi di PL: il problema della dieta, 2

Come costruire il modello logico-matematico a partire da questa descrizione verbale del problema e delle sue caratteristiche?

Ebbene, tale problema è matematicamente formulabile come segue:

\begin{array}{llll}\mbox{{\rm min}} & z(x) = \displaystyle{\sum_{j=1}^n c_j x_j} \\\mbox{{\rm s.a}} \\& a_{11}x_1 + a_{12} x_2 + \ldots + a_{1n} & = b_1 & (1.1)\\& a_{21}x_1 + a_{22} x_2 + \ldots + a_{2n} & = b_2 & (1.2)\\& \ldots \ldots \ldots \ldots & & \ldots\\& a_{m1}x_1 + a_{m2} x_2 + \ldots + a_{mn} & = b_m & (1.m)\\& x_j\geq 0\ \ j=1,2,\ldots,n.\end{array}

In una variante del problema descritto, b potrebbe rappresentarei l vettore dei fattori nutrizionali minimi richiesti affinchè unadieta si possa definire “equilibrata” . In tal caso i vincoli del problema diventano vincoli di \geq.

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 ed Appunti del Corso.

  • 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