Home

Federica EU

1/6

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

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

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$ .