3

Modelli di Programmazione
Lineare

3.1 GENERALITÀ

Come già detto nel capitolo precedente, è possibile classificare i modelli di Pro-
grammazione Matematica in base alla struttura particolare che possono avere
la funzione obiettivo e i vincoli. Riprendiamo qui, espandendola, la definizione
di problemi di Programmazione Lineare nei quali sia la funzione obiettivo, sia i
vincoli sono rappresentati mediante funzioni lineari nelle variabili di decisione.
Preliminarmente, richiamiamo il concetto di funzione lineare.

Definizione 3.1.1 Una funzione reale di n variabili reali f : IRn −→ IR si dice

lineare se valgono le seguenti condizioni:

i) per ogni x, y ∈ IRn si ha f (x + y) = f (x) + f (y);

ii) per ogni x ∈ IRn e λ ∈ IR risulta f (λx) = λf (x).

Una immediata conseguenza di questa definizione è che una funzione è lineare se

e solo se può essere scritta nella forma

c1 x1 + c2 x2 + . . . + cn xn (3.1.1)

con c1 , . . . , cn costanti reali. Infatti è immediato verificare che una funzione della
forma (3.1.1) soddisfa la Definizione 3.1.1; d’altra parte, se una funzione f (x)
è lineare cioè se soddisfa la Definizione 3.1.1, allora si può scrivere nella forma
(3.1.1); infatti se indichiamo con {e1 , e2 , . . . , en } la base canonica di IRn allo-

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

26 MODELLI DI PROGRAMMAZIONE LINEARE

P
ra risulta x = ni=1 xi ei dove le xi sono le componenti del vettore x. Quindi
utilizzando la linearità si ha

f (x) = f (x1 e1 + x2 e2 + · · · + xn en ) = f (x1 e1 ) + f (x2 e2 ) + · · · + f (xn en ) =

= x1 f (e1 ) + x2 f (e2 ) + · · · xn f (en ) = c1 x1 + c2 x2 + · · · + cn xn

dove ci = f (ei ) per i = 1, . . . , n.

Quindi
x1 + 4x2 − 3.5x3
−2x1 + (sin 4)x2 + πx3 − 4x5 ,
sono funzioni lineari, mentre

(x1 )2 + 4x2 − 3.5x3

x1 + 4x2 − 3.5ex3
−2x1 + sin x2 + πx3 − 4x5 ,

non sono funzioni lineari.

3.2 STRUTTURA DI UN MODELLO DI PROGRAMMAZIONE LINEARE

Esaminiamo ora la struttura di un generico modello di Programmazione Lineare.

Un modello di Programmazione Lineare è caratterizzato da

• una singola funzione obiettivo lineare da minimizzare o massimizzare che

può essere quindi scritta nella forma
n
X
f (x) = c1 x1 + . . . + cn xn = cj xj .
j=1

• un numero finito di vincoli lineari che, supponendo siano m, possono essere

scritti nella forma
a11 x1 + ... +a1n xn ≥ b1
a21 x1 + ... +a2n xn ≥ b2
.. .. ..
. ... . .
am1 x1 + ... +amn xn ≥ bm .

Introducendo il vettore c ∈ IRn , definito c = (c1 , . . . , cn )T e x ∈ IRn definito

x = (x1 , . . . , xn )T la funzione obiettivo può essere scritta in notazione vettoriale

cT x.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 STRUTTURA DI UN MODELLO DI PROGRAMMAZIONE LINEARE 27

Inoltre, introducendo la matrice (m × n)

 
a11 . . . a1n
 .. .. 
A= . .
am1 . . . amn

e il vettore b = (b1 , . . . , bm )T la formulazione completa di un generico problema

di Programmazione Lineare può essere scritta nella forma

min cT x
Ax ≥ b.

Osservazione 3.2.1 Come già osservato in relazione ad un generico problema

di Programmazione Matematica, (cfr. Osservazione 2.2.1) non si perde di gene-
ralità formulando un generico problema di Programmazione Lineare con vincoli
di sola diseguaglianza nella forma di maggiore o uguale. Infatti, ogni vincolo di
disuguaglianza nella forma di minore o uguale e ogni vincolo di uguaglianza può
essere ricondotto a questa forma con semplici operazioni algebriche.

Per esempio,
max x1 + x2
x1 + x2 ≥ 1
x1 + x2 ≤ 3
x1 ≥ 0, x2 ≥ 0,
e
min 2x1 − x2 + x3 + 3x4
x1 + x2 − x4 = 1
x1 + 2x2 − x3 + 2x4 ≤ 3
x1 ≥ 0, x2 ≥ 0, x4 ≥ 0,
sono problemi di PL.
Le applicazioni della Ricerca Operativa che possono essere formulate mediante
l’uso di modelli di Programmazione Lineare sono molto frequenti e importanti. In
riferimento alle applicazioni di tipo economico la funzione obiettivo ha di solito
il significato di profitto (da massimizzare) oppure di costo (da minimizzare).
Profitti e costi sono ottenuti come somma dei profitti e costi marginali cioè di quelli
relativi a ciascuna unità di prodotto. Quando è richiesta la massimizzazione di un
profitto, il modello contiene, di solito, vincoli che esprimono limitazioni superiori
sulle risorse (vincoli di capacità produttiva, disponibilità di materie prime); se
invece è richiesta la minimizzazione di un costo sono di solito presenti vincoli sulla
domanda (richieste di mercato) che impongono limitazioni inferiori alle variabili.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

28 MODELLI DI PROGRAMMAZIONE LINEARE

È possibile la presenza di vincoli di continuità che esprimono conservazione o

riduzione di masse o volumi ed hanno spesso la forma di vincoli di uguaglianza.
I modelli di Programmazione Lineare hanno un impiego molto generale non limi-
tato ad applicazioni economiche o progettuali; ad esempio, essi sono usati come
elementi base di procedimenti di soluzione di problemi piú complessi: è il caso di
alcuni algoritmi di ottimizzazione discreta che sono basati sulla soluzione di una
successione di problemi di Programmazione Lineare.

3.3 GENERALITÀ SUI MODELLI DI PROGRAMMAZIONE LINEARE

Mettiamo ora in evidenza le caratteristiche che un problema reale deve possedere

per poter essere formulato come modello di Programmazione Lineare ed i pregi
dei modelli di Programmazione Lineare.
Innanzitutto, chiariamo che le ipotesi che vengono assunte nel formulare un
problema come modello di Programmazione Lineare sono le seguenti:

• proporzionalità: il contributo di una variabile di decisione alla funzione

obiettivo e ai vincoli è proporzionale secondo una costante moltiplicativa
alla quantità rappresentata dalla variabile stessa;

• additività: il contributo delle variabili di decisione alla funzione obiettivo e

ai vincoli è dato dalla somma dei contributi di ogni singola variabile.

• continuità: ogni variabile di decisione può assumere tutti i valori reali nel-
l’intervallo di ammissibilità, e quindi le variabili possono assumere valori
frazionari.

In relazione ad applicazioni reali queste ipotesi non rappresentano una grossa

restrizione nel senso che sono molti gli ambiti e i problemi che sono ben rappre-
sentati da un modello di Programmazione Lineare; si tenga comunque presente
che esistono casi significativi in cui queste ipotesi non sono soddisfatte e quindi
in questi casi è necessario considerare Modelli di Programmazione Non Lineare.

La particolare attenzione dedicata ai modelli di Programmazione Lineare deriva,

comunque, dai numerosi vantaggi che essa presenta e che possono essere cosı̀
sintetizzati:

1. Generalità e flessibilità.
I modelli di Programmazione Lineare possono descrivere moltissime situa-
zioni reali anche assai diverse tra loro e quindi hanno un carattere di uni-
versalità e di adattabilità alle diverse realtà applicative e anche quando
l’ipotesi di linearità non è accettabile, il modello lineare costituisce una
buona base di partenza per successive generalizzazioni.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 29

2. Semplicità.
I modelli di Programmazione Lineare sono espressi attraverso il linguaggio
dell’algebra lineare e quindi sono facilmente comprensibili anche in assenza
di conoscenze matematiche piú elevate.

3. Efficienza degli algoritmi risolutivi.

Come accennato in precedenza i modelli reali hanno dimensioni molto ele-
vate ed è quindi indispensabile l’uso del calcolatore che con opportuni pro-
grammi di calcolo possa rapidamente fornire una soluzione numerica. Rela-
tivamente ai modelli di Programmazione Lineare esistono programmi mol-
to efficienti e largamente diffusi che sono in grado di risolvere rapidamente
problemi con migliaia di vincoli e centinaia di migliaia di variabili.

4. Possibilità di analisi qualitative.

I modelli di Programmazione Lineare permettono di ottenere, oltre la so-
luzione numerica del problema, anche ulteriori informazioni relative alla
dipendenza della soluzione da eventuali parametri presenti, che possono
avere significative interpretazioni economiche.

3.4 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE

Lo scopo di questo paragrafo è quello di illustrare alcune classi di problemi di

Programmazione Lineare tipici che si incontrano frequentemente nelle applicazio-
ni reali. Questa divisione in classi ha uno scopo esclusivamente didattico al fine
di fornire una esposizione sistematica di esempi di modelli di Programmazione
Lineare di tipo generale. Nella realtà, nella maggior parte dei casi, i problemi
che si presentano non sono riconducibili ad una classe specifica, ma possono es-
sere costituiti da molteplici elementi. Tuttavia, la trattazione per grandi classi
di problemi dovrebbe fornire strumenti utili per la modellizzazione di problemi
reali. Tenendo presente questa osservazione, nel seguito esamineremo tre grandi
classi di modelli di Programmazione Lineare che rappresentano situazioni molto
diffuse del mondo reale; si tratta dei

• modelli di allocazione ottima di risorse,

• modelli di miscelazione,

• modelli di trasporto.

Per ciascuna classe di modelli verranno presentati alcuni esempi e una formula-
zione generale. Tale divisione in “classi” di problemi ha il solo scopo permettere
una descrizione schematica di alcune situazioni tipiche che possono essere rap-
presentate attraverso problemi di Programmazione Lineare. È chiaro che nella

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

30 MODELLI DI PROGRAMMAZIONE LINEARE

realtà i problemi si presentano nelle forme piú diverse e sta a colui che costruisce
il modello fornirne una rappresentazione il piú possible completa e significativa
del problema in analisi.

3.4.1 Modelli di allocazione ottima di risorse

Si tratta di modelli che considerano il problema di come dividere (allocare) risorse

limitate tra varie esigenze in competizione fra di loro. Il generico termine “risor-
se” può rappresentare, ad esempio, disponibilità di macchinari, materie prime,
mano d’opera, energia, tempi macchina, capitali, etc.

Esempio 3.4.1 Un colorificio produce due tipi di coloranti C1 e C2 utilizzando

3 preparati base in polvere P1, P2, P3 che vengono sciolti in acqua. La differente
concentrazione dei preparati base dà origine ai due diversi tipi di coloranti. Le
quantità (in ettogrammi) di preparati base necessarie per produrre un litro di
colorante di ciascuno dei due tipi è riportato nella seguente tabella
C1 C2
P1 1 1
P2 1 2
P3 - 1

Ogni giorno la quantità di ciascuno dei preparati base (in ettogrammi) della quale
il colorificio può disporre è la seguente
P1 P2 P3
750 1000 400

Il prezzo di vendita del colorante C1 è di 7 Euro al litro, mentre il colorante C2

viene venduto a 10 Euro al litro. Determinare la strategia ottimale di produzio-
ne giornaliera in modo da massimizzare i ricavi ottenuti dalla vendita dei due
coloranti.

Formulazione.
Si vuole costruire il modello di Programmazione Lineare che rappresenti il pro-
blema in analisi considerando le limitazioni date dalle produzioni effettivamente
realizzabili.
È immediato associare le variabili di decisione ai quantitativi di coloranti pro-
dotti. Siano, quindi, rispettivamente x1 e x2 i quantitativi (in litri) da produrre
giornalmente dei due coloranti.
Nel formulare il modello di Programmazione Lineare si deve verificare che siano
soddisfatte le ipotesi fondamentali:

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 31

• Proporzionalità.
I consumi dei preparati base e i ricavi ottenibili sono proporzionali ai quan-
titativi di coloranti prodotti. Ad esempio, per produrre una quantità x2 di
colorante C2 si consumano 2x2 ettogrammi di P2 e dalla vendita di x2 litri
di C2 si ricavano 10x2 Euro indipendentemente dalla quantità prodotta e
venduta dell’altro tipo di colorante.

• Additività.
I consumi dei preparati base e i ricavi rispettivamente associati alla produ-
zione dei due coloranti sono additivi, nel senso che per produrre x1 litri di
colorante C1 e x2 di C2 si consumano x1 + 2x2 ettogrammi di preparato
di base P2 e si ricavano 7x1 + 10x2 Euro.

• Continuità.
Ogni variabile introdotta nel modello può assumere tutti i valori reali nell’in-
tervallo di ammissibilità.

– Variabili. Come già detto, prendiamo come variabili di decisione x1 e x2 , rispet-

tivamente i quantitativi (in litri) di colorante C1 e C2 da produrre giornalmente.
– Funzione obiettivo. È rappresentata dal profitto totale che per le ipotesi fatte
è dato (in Euro) da 7x1 + 10x2 .
– Vincoli. Poiché il consumo di preparati base non può essere superiore alla
disponibilità si deve avere

x1 + x2 ≤ 750
x1 + 2x2 ≤ 1000
x2 ≤ 400.

Inoltre si deve esplicitare il vincolo di non negatività sulle variabili

x1 ≥ 0, x2 ≥ 0.

Quindi la formulazione finale è


 max (7x1 + 10x2 )



 x1 + x2 ≤ 750
x1 + 2x2 ≤ 1000


 x2 ≤ 400


x1 ≥ 0, x2 ≥ 0.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

32 MODELLI DI PROGRAMMAZIONE LINEARE

Esempio 3.4.2 Una azienda automobilistica produce tre diversi modelli di au-
tovettura: un modello economico, uno normale ed uno di lusso. Ogni autovettura
viene lavorata da tre robot: A, B e C. I tempi necessari alla lavorazione sono
riportati, in minuti, nella tabella seguente insieme al profitto netto realizzato per
autovettura

Economica Normale Lusso

A 20 30 62
B 31 42 51
C 16 81 10
Prezzo 1000 1500 2200

I robot A e B sono disponibili per 8 ore al giorno mentre il robot C è disponibile

per 5 ore al giorno. Il numero di autovetture di lusso prodotte non deve superare il
20% del totale mentre il numero di autovetture economiche deve costituire almeno
il 40% della produzione complessiva. Supponendo che tutte le autovetture prodotte
vengano vendute, formulare un problema di Programmazione Lineare che permet-
ta di decidere le quantità giornaliere (non necessariamente intere) da produrre per
ciascun modello in modo tale da massimizzare i profitti rispettando i vincoli di
produzione.

Formulazione.
È un problema di allocazione ottima di risorse e può essere formulato in termini
di Programmazione Lineare nel seguente modo.
– Variabili. Indichiamo con x1 , x2 , x3 , rispettivamente il numero di autovetture
(assunte non necessariamente intere) del modello economico, normale e di lusso
da produrre giornalmente.
– Funzione obiettivo. La funzione obiettivo è data dal profitto globale ottenuto
dalla vendita delle automobili e quindi può essere scritta

1000x1 + 1500x2 + 2200x3 .

– Vincoli. Ci sono due tipologie di vincoli da considerare:

• i vincoli sulla capacità produttiva; poiché il robot A è disponibile giornal-
mente per 8 ore, cioè per 480 minuti si ha il vincolo

20x1 + 30x2 + 62x3 ≤ 480.

Ragionando in modo analogo si ottengono i vincoli relativi alla disponibilità

dei robot B e C, e quindi si ottengono i seguenti vincoli:

31x1 + 42x2 + 51x3 ≤ 480

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 33

16x1 + 81x2 + 10x3 ≤ 300.

• i vincoli sul numero totale dei singoli tipi di autovetture da fabbricate

giornalmente che possono essere scritti nella forma

x3 ≤ 0.2 (x1 + x2 + x3 )

x1 ≥ 0.4 (x1 + x2 + x3 ) .

Si devono inoltre esplicitare i vincoli di non negatività

x1 ≥ 0 x2 ≥ 0 x3 ≥ 0.

Quindi la formulazione completa può essere scritta


 max (1000x1 + 1500x2 + 2200x3 )



 20x 1 + 30x2 + 62x3 ≤ 480


 31x1 + 42x2 + 51x3 ≤ 480

16x1 + 81x2 + 10x3 ≤ 300



 x 3 ≤ 0.2 (x1 + x2 + x3 )



 x1 ≥ 0.4 (x1 + x2 + x3 )

x1 ≥ 0 x2 ≥ 0 x3 ≥ 0.

Osservazione 3.4.3 Nel modello precedente sono state utilizzate variabili di

decisione continue associate a quantità che possono essere considerate indivisibili
(autovetture). Questa ipotesi potrebbe risultare impropria, tuttavia permette
di formulare il problema come Problema di Programmazione Lineare (e non di
Programmazione Lineare Intera, cioè come un problema piú “trattabile”). D’altra
parte, in generale, tale ipotesi può non far perdere validità al modello soprattutto
se i valori assunti dalle variabili di decisione sono relativamente molto grandi.
Ogni approssimazione a valori interi del valore ottimo delle variabili, ovviamente,
fa perdere l’ottimalità della soluzione cosı̀ ottenuta, ma in molti casi tale soluzione
approssimata può essere efficacemente utilizzata nella pratica.

Esempio 3.4.4 Si consideri la stessa azienda dell’esempio precedente con la sola

differenza che, questa volta, i tre modelli di autovetture possono essere prodot-
te utilizzando uno qualsiasi dei tre robot senza richiedere quindi che per avere
un’autovettura finita sia necessaria la lavorazione di tutti i tre robot.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

34 MODELLI DI PROGRAMMAZIONE LINEARE

Formulazione.
– Variabili. Indichiamo con xij , con i = 1, 2, 3 e j = 1, 2, 3, il numero di
autovetture del modello j-esimo da produrre giornalmente con il robot i-esimo.
– Funzione obiettivo. La funzione obiettivo diventa:

1000(x11 + x21 + x31 ) + 1500(x12 + x22 + x32 ) + 2200(x13 + x23 + x33 )

– Vincoli.

• I vincoli sulla capacità produttiva si esprimono:

20x11 + 30x12 + 62x13 ≤ 480.

31x21 + 42x22 + 51x23 ≤ 480

16x31 + 81x32 + 10x33 ≤ 300.

• i vincoli sul numero totale dei singoli tipi di autovetture da fabbricare

assumono la forma:
3 X
X 3
x13 + x23 + x33 ≤ 0.2 xij
i=1 j=1

3 X
X 3
x11 + x21 + x31 ≥ 0.4 xij .
i=1 j=1

Si devono inoltre esplicitare i vincoli di non negatività

xij ≥ 0 i = 1, 2, 3, j = 1, 2, 3.

Quindi la formulazione finale è la seguente:



 max (1000(x11 + x21 + x31 ) + 1500(x12 + x22 + x32 ) + 2200(x13 + x23 + x33 ))



 20x 11 + 30x12 + 62x13 ≤ 480


 31x21 + 42x22 + 51x23 ≤ 480

16x31 + 81x32 + 10x33 ≤ 300



 x13 + x23 + x33 ≤ 0.2 (x11 + x12 + x13 + x21 + x22 + x23 + x31 + x32 + x33 )



 x11 + x21 + x31 ≥ 0.4 (x11 + x12 + x13 + x21 + x22 + x23 + x31 + x32 + x33 )


xij ≥ 0 i = 1, 2, 3, j = 1, 2, 3.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 35

Formulazione generale di un problema di allocazione ottima di risorse

Per costruire uno schema generale di formulazione per questo tipo di problemi si
assuma di disporre di m risorse R1 , R2 , . . . , Rm e di voler fabbricare n diversi
prodotti P1 , P2 , . . . , Pn .
Le risorse possono essere sia umane (mano d’opera) sia materiali (disponibilità
di macchinari o di materie prime). Il problema della pianificazione delle risorse
consiste nel determinare le quantità da fabbricare di ciascun prodotto P1 , . . . , Pn
in modo da massimizzare il profitto rispettando i vincoli sulle risorse disponibili
o sui livelli di produzione richiesti.
Si indichi con aij , i = 1, . . . , m, j = 1, . . . , n la quantità della risorsa Ri necessaria
per fabbricare una unità del prodotto Pj . Si può cosı̀ costruire la seguente tabella

P1 ··· Pj ··· Pn
R1 a11 ··· a1j ··· a1n
.. .. .. ..
. . . .
Ri ai1 ··· aij ··· ain
.. .. .. ..
. . . .
Rm am1 ··· amj ··· amn

Supponiamo che ciascuna risorsa Ri non possa superare un valore prefissato

bi , i = 1, . . . , m
R1 R2 · · · Rm
b1 b2 · · · bm
e che nella vendita di ciascuna unità di prodotto Pj si ricavi un profitto netto
cj , j = 1, . . . , n
P1 P2 · · · Pn
c1 c2 · · · cn .
È utile ribadire le ipotesi già esposte in precedenza le quali devono valere in
generale per la costruzione di modelli di Programmazione Lineare: proporziona-
lità, additività, continuità cioè i consumi delle risorse e i ricavi ottenibili sono
proporzionali ai quantitativi di prodotto fabbricati; i consumi globali di risorse
e i ricavi totali si ottengono come somma dei consumi e dei ricavi marginali; le
variabili possono assumere valori frazionari.

Formulazione 1: risorse concorrenti.

Esaminiamo prima la situazione in cui il bene fabbricato per essere finito e pronto
per la vendita deve utilizzare tutte le risorse, anche se in misura diversa.
– Variabili di decisione. Si introducono le variabili di decisione x1 , x2 , . . . , xn
rappresentanti (in un’opportuna unità di misura) la quantità di ciascun prodot-
to P1 , P2 , . . . , Pn . Queste saranno le incognite del problema. Tali variabili

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

36 MODELLI DI PROGRAMMAZIONE LINEARE

di decisione sono i cosiddetti livelli di attività. Introducendo come spazio delle

variabili lo spazio delle n−uple reali IRn si può considerare un x ∈ IRn definendo
x = (x1 , . . . , xn )T .
– Funzione obiettivo. Per le ipotesi fatte la funzione obiettivo (da massimizzare)
può essere scritta
Xn
z = c1 x1 + . . . + cn xn = cj xj .
j=1

Introducendo c ∈ IRn , definito c = (c1 , . . . , cn )T la funzione obiettivo può essere

scritta in notazione vettoriale
z = cT x.
– Vincoli. Si devono introdurre i seguenti vincoli:

• Vincoli di capacità produttiva:

tenendo conto delle limitazioni delle risorse si hanno i seguenti m vincoli
a11 x1 + ... +a1n xn ≤ b1
a21 x1 + ... +a2n xn ≤ b2
.. .. ..
. ... . .
am1 x1 + ... +amn xn ≤ bm .

• Vincoli di non negatività:

le variabili devono essere non negative in quanto esse rappresentano livelli
di produzione e quindi si hanno i vincoli

xi ≥ 0, i = 1, . . . , n.

Introducendo la matrice (m × n)
 
a11 ... a1n
. .. 
A =  .. .
am1 ... amn

e il vettore b = (b1 , . . . , bm )T la formulazione completa del problema può essere

scritta nella forma 
 max cT x
Ax ≤ b

x ≥ 0.
È una formulazione generale (con solo vincoli di disuguaglianza e vincoli di non
negatività) in cui si può porre un generico problema di allocazione ottima di
risorse.
Nella pratica, potrebbe essere necessario imporre ulteriori vincoli:

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 37

• Vincoli di domanda
- limitazioni inferiori sulle variabili xi cioè
xi ≥ li i = 1, . . . , n
con li ≥ 0 per assicurare che i prodotti siano fabbricati in quantità
significative. In questo caso, per ogni indice i per il quale li > 0 il
vincolo di non negatività xi ≥ 0 è ridondante.
- limitazioni superiori sulle variabili, cioè
xi ≤ ui i = 1, . . . , n
dovute ad eventuali possibilità limitate di assorbimento dei prodotti
da parte del mercato.
Introducendo le notazioni vettoriali l = (l1 , . . . , ln )T e u = (u1 , . . . , un )T
questi vincoli possono essere scritti nella forma l ≤ x ≤ u, x ∈ IRn .
• Vincoli di interezza.
Se inoltre non ha senso considerare i prodotti quantità divisibili allora si
deve definire un modello di programmazione a numeri interi. Cioè nel caso
in cui non si possa supporre che i livelli di attività siano frazionari (ad es.
se i prodotti sono quantità indivisibili come motori, lavatrici etc.), allora si
deve aggiungere il vincolo che le quantità xi siano intere.

Formulazione 2: risorse alternative.

Si consideri ora invece la situazione in cui il bene fabbricato per essere finito
e pronto per la vendita necessita esclusivamente di una risorsa. Nella pratica
questo può accadere se, ad esempio, ciascun reparto in cui può essere suddivisa
un’industria è in grado di produrre autonomamente ciascuno dei prodotti, ovvero
la lavorazione di un prodotto avviene esclusivamente in uno dei reparti disponibili.
– Variabili di decisione. Si introducono le variabili di decisione xij rappresentanti
la quantità di prodotto Pj da fabbricare utilizzando la risorsa Ri .
– Funzione obiettivo. Per le ipotesi fatte la funzione obiettivo (da massimizzare)
può essere scritta
m
X m
X m
X n
X m
X
c1 xi1 + c2 xi2 + . . . + cn xin = cj xij .
i=1 i=1 i=1 j=1 i=1

– Vincoli. I vincoli di capacità produttiva sono della forma

a11 x11 + ... +a1n x1n ≤ b1
a21 x21 + ... +a2n x2n ≤ b2
.. .. ..
. ... . .
am1 xm1 + ... +amn xmn ≤ bm .

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

38 MODELLI DI PROGRAMMAZIONE LINEARE

Infine si devono esplicitare i vincoli di non negatività della variabili cioè xij ≥ 0,
i = 1, . . . , m, j = 1, . . . , n.
Come si può facilmente osservare la matrice A dei coefficienti delle disequazioni
lineari che descrivono i vincoli è rimasta immutata rispetto alla matrice consi-
derata nella formulazione del caso delle risorse concorrenti già vista, ma c’è una
sostanziale differenza nelle variabili.

Modelli multi–plant
Si tratta di problemi di pianificazione della produzione in cui modelli di grandi
dimensioni sono ottenuti come combinazione di modelli piú piccoli. Tali mo-
delli combinati sono sicuramente piú efficaci dei sottomodelli dai quali essi sono
costituiti. Esaminiamo un esempio di questa situazione.

Esempio 3.4.5 Un’industria manifatturiera possiede due impianti di produzione

e fabbrica due tipi di prodotti P1 e P2 utilizzando due macchine utensili: una
per la levigatura e una per la pulitura. Per avere un prodotto finito è necessaria
l’utilizzazione di entrambe le macchine. Il primo impianto ha una disponibilità
massima settimanale di 80 ore della macchina per la levigatura e di 60 ore della
macchina per la pulitura. Le disponibilità massime orarie delle due macchine nel
secondo impianto sono rispettivamente di 60 e 75 ore settimanali. La tabella che
segue riporta, per ciascun prodotto, il numero di ore di lavorazione necessarie su
ciascuna macchina per ottenere un prodotto finito (poiché le macchine possedute
dal secondo impianto sono piú vecchie, i tempi di utilizzo sono maggiori)

Impianto 1 Impianto 2
P1 P2 P1 P2
levigatura 4 2 5 3
pulitura 2 5 5 6

Inoltre ciascuna unità di prodotto utilizza 4 Kg di materiale grezzo. Il profitto

netto ottenuto dalla vendita di una unità di prodotto P1 e P2 è rispettivamente
di 10$ e 15$.
(a) Costruire un modello lineare che permetta di massimizzare il profitto com-
plessivo ottenuto dalla vendita dei prodotti in ciascun impianto sapendo che
settimanalmente l’industria dispone di 75 Kg di materiale grezzo nel primo
impianto e di 45 Kg di materiale grezzo nel secondo impianto.
(b) Costruire un modello lineare che permetta di massimizzare il profitto com-
plessivo ottenuto dalla vendita dei prodotti supponendo che l’industria non
allochi a priori 75 Kg di materiale grezzo nel primo impianto e di 45 Kg di
materiale grezzo nel secondo impianto, ma lasci al modello la decisione di
come ripartire tra i due impianti 120 Kg complessivi disponibili di questo
materiale grezzo.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 39

Formulazione
– Variabili. Si introducono le variabili x1 e x2 associate alla quantità di prodot-
to P1 e P2 fabbricato settimanalmente dal primo impianto e le variabili x3 e
x4 associate alla quantità di prodotto P1 e P2 fabbricato settimanalmente dal
secondo impianto.
Formulazione del caso (a)
Questo caso, nella pratica, corrisponde a costruire due modelli indipendenti: uno
riferito al primo impianto, uno riferito al secondo impianto. Una “risorsa” (il
materiale grezzo) è già allocata a priori.
Impianto 1: La formulazione relativa al primo impianto è:

 max(10x1 + 15x2 )



 4x1 + 4x2 ≤ 75
4x1 + 2x2 ≤ 80


 2x1 + 5x2 ≤ 60


x1 ≥ 0, x2 ≥ 0

Impianto 2: La formulazione relativa al secondo impianto è:


 max(10x3 + 15x4 )



 4x3 + 4x4 ≤ 45
5x3 + 3x4 ≤ 60



 5x + 6x4 ≤ 75
 3
x3 ≥ 0, x4 ≥ 0

Formulazione del caso (b)

Questo caso corrisponde a costruire un unico modello comprendente entrambi
gli impianti. L’allocazione della “risorsa” data dal materiale grezzo è lasciata al
modello stesso.
La formulazione relativa a questo caso è:


 max (10x1 + 15x2 + 10x3 + 15x4 )



 4x1 + 4x2 + 4x3 + 4x4 ≤ 120



 4x 1 + 2x2 ≤ 80
2x1 + 5x2 ≤ 60



 5x3 + 3x4 ≤ 60



 5x 3 + 6x4 ≤ 75


x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

40 MODELLI DI PROGRAMMAZIONE LINEARE

Osservazione 3.4.6 Nel caso (b) si richiede al modello di ripartire i 120 Kg di

materiale grezzo piuttosto che effettuare un’allocazione arbitraria a priori, quindi
ci si può aspettare una maggiore efficienza nell’allocazione di queste risorse nel
caso (b). Un confronto delle soluzioni ottime di questi problemi conferma questa
intuizione: infatti nel caso (a), ottimizzando la produzione dell’impianto 1 e quella
dell’impianto 2, si ottiene un guadagno complessivo di 225$ + 168.75$ = 393.75$,
mentre nel caso (b) si ottiene un guadagno di 404.15$.

Osservazione 3.4.7 Si osservi la particolare struttura della matrice dei coeffi-

cienti dei vincoli che è tipica dei problemi di questo tipo
 
4 2 0 0
2 5 0 0
 
0 0 5 3
0 0 5 6
Una matrice con questa struttura si chiama matrice a blocchi. Una siffatta strut-
tura permette di utilizzare metodi particolari per la soluzione del problema. Infat-
ti possono essere utilizzate tecniche di decomposizione che consentono di risolvere
efficientemente anche problemi di questo tipo anche di dimensioni molto elevate.
Si osservi che le tecniche di decomposizione non consistono nella suddivisione del
problema in sottoproblemi, ma piuttosto con tale termine ci si riferisce a pro-
cedure computazionali specifiche che pur considerando il problema complessivo
sfruttano la sua particolare struttura. L’importanza della decomposizione non è
soltanto computazionale ma ha anche una significativa interpretazione economica;
infatti essa corrisponde a considerare una pianificazione decentralizzata.

Modelli multiperiodo
Si tratta di problemi di allocazione ottima di risorse limitate analoghi a quelli già
trattati, ma dove la pianificazione è effettuata su un orizzonte temporale compo-
sto da piú periodi elementari; si richiede, cioè, di estendere la programmazione
mensile della produzione di un’azienda in modo da ottenere un piano di produ-
zione semestrale con possibilità di giacenze al termine di ciascun mese. L’esempio
che segue riporta una semplice situazione di questo tipo.

Esempio 3.4.8 Si consideri l’industria manifatturiera vista nel precedente Esem-

pio 3.4.5 nel caso in cui abbia solamente il primo impianto di produzione. In
questo caso si deve programmare la produzione dei due prodotti P1 e P2 nelle
due successive settimane sapendo che nella prima settimana si potranno vendere
al piú 12 prodotti P1 e 4 prodotti P2 , mentre nella seconda si potranno vende-
re al piú 8 prodotti P1 e 12 prodotti P2 . Inoltre nella prima settimana c’è la

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 41

possibiltà di produrre piú prodotti rispetto a quelli che si possono vendere, im-
magazzinando i prodotti in eccesso prevedendo un loro utilizzo nella settimana
successiva. Costruire un modello lineare che permetta di massimizzare il profitto
complessivo ottenuto dalla vendita dei prodotti nelle due settimane sapendo che
settimanalmente l’industria dispone di 75 Kg di materiale grezzo e tenendo conto
che il costo di immagazzinamento di un prodotto (sia di tipo P1 sia di tipo P2 ) è
di 2 $. Si ricorda che il profitto netto ottenuto dalla vendita di 1 unità di prodotto
P1 e P2 è rispettivamente di 10$ e 15$.

Formulazione
– Variabili. Si introducono le variabili x1 e x2 associate alla quantità di prodotti
P1 e P2 fabbricati nella prima settimana, le variabili x3 e x4 associate alla quan-
tità di prodotti P1 e P2 fabbricati nella seconda settimana e le variabili y1 e y2
che indicano le quantità di prodotti P1 e P2 fabbricati nella prima settimana ed
immagazzinati per venderli nella seconda.
– Funzione obiettivo. Nella prima settimana saranno vendute le quantità (x1 −y1 )
di prodotto P1 e (x2 − y2 ) di prodotto P2 , nella seconda le quantità (x3 +
y1 ) di prodotto P1 e (x4 + y2 ) di prodotto P2 . Tenendo conto dei costi di
immagazzinamento si ottiene la seguente funzione obiettivo:

10(x1 − y1 ) + 15(x2 − y2 ) + 10(x3 + y1 ) + 15(x4 + y2 ) − 2(y1 + y2 ) =

10(x1 + x3 ) + 15(x2 + x4 ) − 2(y1 + y2 ).

– Vincoli. In questo problema si hanno nuovamente quattro tipologie di vincoli:

• i vincoli sulle capacità produttive nelle due settimane:
4x1 + 4x2 ≤ 75
4x1 + 2x2 ≤ 80
2x1 + 5x2 ≤ 60
4x3 + 4x4 ≤ 75
4x3 + 2x4 ≤ 80
2x3 + 5x4 ≤ 60

• vincoli che rappresentano il fatto che, alla fine della prima settimana, una
parte dei prodotti può essere immagazzinata
x1 − y1 ≤ 12
x2 − y 2 ≤ 4

• vincoli che rappresentano il fatto che il numero dei prodotti disponibili nella
seconda settimana non deve superare le richieste del mercato
y 1 + x3 ≤ 8

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

42 MODELLI DI PROGRAMMAZIONE LINEARE

y2 + x4 ≤ 12

• vincoli che rappresentano la non negatività delle variabili

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, y1 ≥ 0, y2 ≥ 0.

La formulazione relativa a questo problema è:

  

 max 10(x 1 + x 2 ) + 15(x 3 + x 4 ) − 2(y 1 + y 2 )









 4x1 + 4x2 ≤ 75



 4x 1 + 2x 2 ≤ 80



 2x1 + 5x2 ≤ 60



 4x + 4x ≤ 75

 3 4
4x3 + 2x4 ≤ 80

 2x3 + 5x4 ≤ 60



 x − y ≤ 12

 1 1

 x2 − y2 ≤ 4





 x 3 + y 1 ≤ 8



 x4 + y2 ≤ 12






x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, y1 ≥ 0, y2 ≥ 0.

Osservazione 3.4.9 Se non si fosse prevista la possibilità di poter immagazzi-

nare dei prodotti non venduti, si sarebbe dovuto massimizzare separatamente i
profitti ottenuti dalla vendita dei prodotti fabbricati nella prima e nella seconda
settimana risolvendo i seguenti problemi:
 
 max(10x1 + 15x2 )  max(10x1 + 15x2 )

 


 4x1 + 4x2 ≤ 75 
 4x1 + 4x2 ≤ 75

 

4x1 + 2x2 ≤ 80 4x1 + 2x2 ≤ 80

 2x 1 + 5x 2 ≤ 60 
 2x 1 + 5x2 ≤ 60

 

 
 0 ≤ x1 ≤ 12
  0 ≤ x1 ≤ 8

0 ≤ x2 ≤ 4, 0 ≤ x2 ≤ 12.
In questo caso si sarebbe ottenuto un guadagno complessivo di 180$ + 212$ =
392$. Mentre la soluzione ottima del modello di Programmazione Lineare, descrit-
to precedentemente e che prevedeva anche la possibilità di poter immagazzinare i
prodotti non venduti, porta ad un guadagno di 429.1$. Questo mette in evidenza
la convenienza di effettuare una programmazione complessiva sulle due settima-
ne, prevedendo la possibilità di produrre nella prima settimana di piú di quanto
si possa vendere e considerando anche le spese relative all’immagazzinamento dei
prodotti non venduti.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 43

Osservazione 3.4.10 Si osservi che i primi sei vincoli del precedente modello
multiperiodo presentano una struttura particolare. Infatti possono essere rappre-
sentati da una matrice a blocchi (in particolare nell’esempio considerato tutti i
blocchi sono uguali). Il fatto di avere la maggior parte dei vincoli con una strut-
tura a blocchi è una caratteristica di tutti i modelli multiperiodo. Come detto per
i modelli multi-plan, questa particolare struttura può essere sfruttata attraverso
l’uso di tecniche di decomposizione in modo da risolvere efficientemente anche
problemi di questo tipo di grosse dimensioni.

Esaminiamo ora un altro modello multiperiodo.

Esempio 3.4.11 Una fabbrica produce due tipi di pneumatici A e B ed ha una

gestione trimestrale della produzione. Per i prossimi tre mesi deve soddisfare il
seguente ordine (espresso in numero di pneumatici richiesti ciascun mese)
tipo A tipo B
ottobre 16000 14000
novembre 7000 4000
dicembre 4000 6000

Per la produzione di questi pneumatici la fabbrica dispone di due linee di produ-

zione L1 e L2. Per avere un pneumatico finito e pronto per essere venduto, è
necessaria la lavorazione di materiale grezzo su solo una delle due linee di pro-
duzione. Il numero di ore in cui le linee di produzione sono disponibili ciascun
mese sono riportate nella seguente tabella
L1 L2
ottobre 2000 3000
novembre 400 800
dicembre 200 1000

I tempi necessari per produrre questi pneumatici varia a seconda del tipo e della
linea di produzione usata. Tali tempi sono riportati nella seguente tabella (in ore)
L1 L2
tipo A 0.10 0.12
tipo B 0.12 0.18

Il costo di ogni ora di lavorazione su una linea di produzione è uguale per entrambe
le linee ed è pari a 6 euro. Il costo del materiale grezzo necessario per produrre
ciascun pneumatico è di euro 2.50 per il tipo A e di euro 4.00 per il tipo B.
Nel primo e nel secondo mese del trimestre è possibile produrre più di quanto ri-
chiesto nello stesso mese; la produzione in eccesso deve essere immagazzinata per
essere usata nel mese successivo. Ogni mese, il costo di tale immagazzinamento

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

44 MODELLI DI PROGRAMMAZIONE LINEARE

è di euro 0.35 per ciascun pneumatico immagazzinato. Si assuma che all’inizio

del trimestre non ci sia nessun prodotto immagazzinato e analogamente alla fine
del trimestre non rimanga nessun prodotto immagazzinato.
Costruire un modello lineare che permetta di pianificare la produzione trimestrale
minimizzando il costo complessivo trascurando l’interezza dei prodotti.

Formulazione.
Si tratta di un problema di allocazione ottima di risorse nel quale si deve tenere
presente la possibilità dell’immagazzinamento del prodotto in eccesso (allocazione
ottima multiperiodo).

– Variabili. Si introducono le variabili Aott nov dic

Li , ALi , ALi che indicano la quantità di
pneumatici di tipo A prodotti dalla i−esima linea produzione (i = 1, 2) rispettiva-
mente nei mesi di ottobre, novembre e dicembre. Analogamente BLi ott , B nov , B dic
Li Li
indicheranno le quantità di pneumatici di tipo B prodotti dalla i−esima linea di
produzione (i = 1, 2) rispettivamente nei mesi di ottobre, novembre e dicembre.
Si indichino inoltre con Aott nov ott nov
im , Aim , Bim , Bim le quantità di pneumatici di tipo
A e B da immagazzinare nei mesi di ottobre e novembre.

– Funzione obiettivo. La funzione obiettivo da minimizzare è data dal costo com-

plessivo di produzione. Poiché un’ora di lavorazione su una linea di produzione
costa 6 euro, e poiché i tempi di lavorazione cambiano a seconda della linea di
produzione utilizzata, per produrre ciascun pneumatico di tipo A si spende euro
0.60 se si utilizza la linea L1 e euro 0.72 se si utilizza la linea L2. Analogamente,
il costo di ciascun pneumatico del tipo B è di euro 0.72 se si utilizza la macchina
1, e di euro 1.08 se si utilizza la linea L2. Quindi tenendo conto del costo del
materiale grezzo e dell’immagazzinamento, il costo complessivo sarà

0.6(Aott nov dic ott nov dic

L1 + AL1 + AL1 ) + 0.72(AL2 + AL2 + AL2 )+

ott + B nov + B dic ) + 1.08(B ott + B nov + B dic )+

+0.72(BL1 L1 L1 L2 L2 L2

+2.50(Aott nov dic ott nov dic

L1 + AL1 + AL1 + AL2 + AL2 + AL2 )+

ott + B nov + B dic + B ott + B nov + B dic )+

+4.00(BL1 L1 L1 L2 L2 L2

+0.35(Aott nov ott nov

im + Aim + Bim + Bim ).

– Vincoli. I vincoli dovuti alla disponibilità limitata delle macchine sono

0.10Aott ott
L1 + 0.12BL1 ≤ 2000
0.10Anov nov
L1 + 0.12BL1 ≤ 400
0.10Adic dic
L1 + 0.12BL1 ≤ 200

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 45

0.12Aott ott
L2 + 0.18BL2 ≤ 3000
0.12Anov nov
L2 + 0.18BL2 ≤ 800
0.12Adic dic
L2 + 0.18BL2 ≤ 1000.

Si hanno inoltre i seguenti vincoli dovuti alla richiesta e all’immagazzinamento:

Aott ott ott

L1 + AL2 = 16000 + Aim
Anov nov ott nov
L1 + AL2 + Aim = 7000 + Aim
Adic dic nov
L1 + AL2 + Aim = 4000

ott ott ott

BL1 + BL2 = 14000 + Bim
nov nov ott nov
BL1 + BL2 + Bim = 4000 + Bim
dic dic nov
BL1 + BL2 + Bim = 6000.

Si hanno infine i vincoli di non negatività sulle variabili. Quindi il modello finale
è:  

 min 3.1(Aott nov dic ott nov
L1 + AL1 + AL1 ) + 3.22(AL2 + AL2 + AL2 )+
dic



 +4.72(BL1ott + B nov + B dic ) + 5.08(B ott + B nov + B dic )+

 L1 L1  L2 L2 L2



 ott nov ott
+0.35(Aim + Aim + Bim + Bim ) nov





 0.10Aott ott
L1 + 0.12BL1 ≤ 2000

 nov nov ≤ 400

 0.10AL1 + 0.12BL1

 0.10Adic + 0.12B dic ≤ 200



 L1 L1

 0.12Aott + 0.18BL2ott ≤ 3000

 L2
 0.12Anov + 0.18B nov ≤ 800
L2 L2

 0.12Adic dic
L2 + 0.18BL2 ≤ 1000




ott ott
AL1 + AL2 = 16000 + Aott im

 nov + Anov + Aott = 7000 + Anov

 A

 L1 L2 im im
 Adic + Adic + Anov

 L1 L2 im = 4000

 ott ott ott

 BL1 + BL2 = 14000 + Bim



 nov + B nov + B ott = 4000 + B nov
BL1

 L2 im im

 B dic + B dic + B nov = 6000

 L1 L2 im

 A ott ≥ 0, Anov ≥ 0, Adic ≥ 0, i = 1, 2

 Li Li Li
ott ≥ 0, B nov ≥ 0, B dic ≥ 0, i = 1, 2.
BLi Li Li

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

46 MODELLI DI PROGRAMMAZIONE LINEARE

3.4.2 Modelli di miscelazione

Nei modelli di allocazione ottima le risorse devono essere ripartite mentre nei
modelli di miscelazione le risorse devono essere combinate tra di loro. I modelli
di miscelazione decidono come combinare (miscelare) tali risorse in maniera da
soddisfare al meglio determinati obiettivi rispettando opportune richieste.
Esempio 3.4.12 Un’industria conserviera deve produrre succhi di frutta mesco-
lando polpa di frutta e dolcificante ottenendo un prodotto finale che deve soddi-
sfare alcuni requisiti riguardanti il contenuto di vitamina C, di sali minerali e di
zucchero. La polpa di frutta e il dolcificante vengono acquistati al costo rispet-
tivamente di 4 Euro e 6 Euro ogni ettogrammo. Inoltre dalle etichette si ricava
che 100 grammi di polpa di frutta contengono 140 mg di vitamina C, 20 mg di
sali minerali e 25 grammi di zucchero, mentre 100 grammi di dolcificante conten-
gono 10 mg di sali minerali, 50 grammi di zucchero e non contengono vitamina
C. I requisiti che il prodotto finale (cioè il succo di frutta pronto per la vendita)
deve avere sono i seguenti: il succo di frutta deve contenere almeno 70 mg di
vitamina C, almeno 30 mg di sali minerali e almeno 75 grammi di zucchero. Si
devono determinare le quantità di polpa di frutta e di dolcificante da utilizzare
nella produzione del succo di frutta in modo da minimizzare il costo complessivo
dell’acquisto dei due componenti base.

Formulazione.
Si vuole costruire un modello di Programmazione Lineare che rappresenti il pro-
blema in analisi tenendo presente i requisiti di qualità richiesti. Si verifica facil-
mente che le ipotesi fondamentali di un modello di Programmazione Lineare sono
soddisfatte.
– Variabili. È naturale associare la variabili di decisione alle quantità di polpa di
frutta e di dolcificante da utilizzare per la produzione del succo di frutta. Quindi
siano x1 e x2 rispettivamente le quantità espresse in ettogrammi di polpa di frutta
e di dolcificante che devono essere utilizzate.
– Funzione obiettivo. È rappresentata dal costo complessivo dell’acquisto dei due
componenti base e quindi è data (in centesimi di Euro) da 400x1 + 600x2 . Questa
espressione naturalmente deve essere minimizzata.
– Vincoli. Poiché un ettogrammo di polpa contiene 140 mg di vitamina C e il
dolcificante non contiene vitamina C, il primo vincolo da considerare riguardante
il contenuto di vitamina C del succo di frutta si può scrivere nella forma
140x1 ≥ 70.
Analogamente per rispettare il requisito sul contenuto di sali minerali del succo
di frutta si dovrà imporre il vincolo
20x1 + 10x2 ≥ 30.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 47

Infine il vincolo sul contenuto di zucchero del succo di frutta si può esprimere
nella forma
25x1 + 50x2 ≥ 75.
Infine si deve esplicitare il vincolo di non negatività sulle variabili cioè

x1 ≥ 0, x2 ≥ 0.

Quindi la formulazione finale è


 min(400x1 + 600x2 )



 140x1 ≥ 70
20x1 + 10x2 ≥ 30



 25x 1 + 50x2 ≥ 75

x1 ≥ 0, x2 ≥ 0

Esempio 3.4.13 – Il problema della dieta a costo minimo

Una dieta prescrive che giornalmente devono essere assimilate quantità predeter-
minate di calorie, proteine e calcio, intese come fabbisogni minimi giornalieri,
disponendo di cinque alimenti base (pane, latte, uova, carne, dolce). Tali fabbi-
sogni minimi sono di 2000 calorie, 50 g. di proteine, 700 mg. di calcio. Dalle
tabelle dietetiche si ricavano i seguenti contenuti di calorie (in cal.), proteine (in
g.), calcio (in mg.) per ogni singola porzione di ciascun alimento, intendendo
come porzione una quantità espressa in grammi e quindi frazionabile.

Pane Latte Uova Carne Dolce

calorie 110 160 180 260 420
proteine 4 8 13 14 4
calcio 2 285 54 80 22

I costi (in Euro) e il numero massimo di porzioni tollerate giornalmente sono i

seguenti

Pane Latte Uova Carne Dolce

costo 2 3 4 19 20
porz. 4 8 3 2 2

Determinare una dieta a costo minimo che soddisfi le prescrizioni richieste.

Formulazione.
Poiché si è supposto che le porzioni siano frazionabili ed inoltre valgono le ipo-
tesi di linearità, si può costruire un modello di Programmazione Lineare per
rappresentare il problema in analisi.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

48 MODELLI DI PROGRAMMAZIONE LINEARE

– Variabili. È ovvio introdurre le variabili x1 , x2 , x3 , x4 , x5 indicanti le quantità

di porzioni dei singoli alimenti da includere giornalmente nella dieta.
– Funzione obiettivo. È rappresentata dal costo complessivo ed è quindi data da

2x1 + 3x2 + 4x3 + 19x4 + 20x5 .

– Vincoli. Poiché sono prescritti i fabbisogni minimi giornalieri, si avranno i

seguenti vincoli:

calorie −→ 110x1 + 160x2 + 180x3 + 260x4 + 420x5 ≥ 2000

proteine −→ 4x1 + 8x2 + 13x3 + 14x4 + 4x5 ≥ 50
calcio −→ 2x1 + 285x2 + 54x3 + 80x4 + 22x5 ≥ 700

Inoltre i vincoli sul numero massimo di porzioni giornaliere di ciascun alimento e

di non negatività

0 ≤ x1 ≤ 4, 0 ≤ x2 ≤ 8, 0 ≤ x3 ≤ 3, 0 ≤ x4 ≤ 2, 0 ≤ x5 ≤ 2.

La formulazione completa sarà quindi


 min (2x1 + 3x2 + 4x3 + 19x4 + 20x5 )



 110x1 + 160x2 + 180x3 + 260x4 + 420x5 ≥ 2000
4x1 + 8x2 + 13x3 + 14x4 + 4x5 ≥ 50



 2x + 285x2 + 54x3 + 80x4 + 22x5 ≥ 700
 1
0 ≤ x1 ≤ 4, 0 ≤ x2 ≤ 8, 0 ≤ x3 ≤ 3, 0 ≤ x4 ≤ 2, 0 ≤ x5 ≤ 2.

Se inoltre si vuole supporre, ad esempio, che nella dieta sia presente almeno una
porzione di dolce e due di latte si dovranno imporre i vincoli x5 ≥ 1 e x2 ≥ 2
da aggiungere alla precedente formulazione. In questo caso, i vincoli già presenti
x5 ≥ 0 e x2 ≥ 0 sono ridondanti.

Formulazione generale di un problema di miscelazione

Formalmente, supponiamo di disporre di n sostanze diverse che indichiamo con
S1 , S2 , . . . , Sn ciascuna delle quali contenga una certa quantità di ciascuno degli
m componenti utili che indichiamo con C1 , C2 , . . . , Cm . Supponendo che ogni
sostanza Sj abbia costo unitario cj , j = 1, . . . , n
S1 S2 ··· Sn
c1 c2 ··· cn
si desidera ottenere la miscela piú economica che soddisfi alcuni requisiti quali-
tativi, cioè contenga una quantità non inferiore a bi di ciascun Ci , i = 1, . . . , m
C1 C2 ··· Cm
b1 b2 ··· bm .

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 49

Si indichi con aij , i = 1, . . . , m, j = 1, . . . , n la quantità di componente Ci presente

nella sostanza Sj . Si può cosı̀ costruire la seguente tabella

S1 ··· Sj ··· Sn
C1 a11 ··· a1j ··· a1n
.. .. .. ..
. . . .
Ci ai1 ··· aij ··· ain
.. .. .. ..
. . . .
Cm am1 ··· amj ··· amn

Formulazione.
Supponendo che valgano le ipotesi di proporzionalità, additività ed inoltre assu-
mendo che le quantità di sostanze da utilizzare siano frazionabili, si può formulare
questo problema in termini di un problema di Programmazione Lineare.
– Variabili. È naturale introdurre le variabili di decisione x1 , x2 , . . . , xn rap-
presentanti la quantità di ciascuna sostanza S1 , S2 , . . . , Sn da utilizzare nella
miscela. Queste saranno le incognite del problema. Introducendo come spazio
delle variabili lo spazio delle n−uple reali IRn si può considerare un x ∈ IRn
definendo x = (x1 , . . . , xn )T .
– Funzione obiettivo. Per le ipotesi fatte, la funzione obiettivo può essere scritta
n
X
z = c1 x1 + . . . + cn xn = cj xj .
j=1

Introducendo c ∈ IRn , definito c = (c1 , . . . , cn )T , la funzione obiettivo può essere

scritta in notazione vettoriale
z = cT x.

– Vincoli. Si devono introdurre i seguenti vincoli:

• Vincoli di qualità.
Tenendo conto del fatto che la miscela deve contenere una quantità non
inferiore a bi di ciascun componente Ci si dovrà avere
n
X
aij xj ≥ bi , i = 1, . . . , m.
j=1

• Vincoli di non negatività.

Si devono infatti considerare i vincoli di non negatività sulle variabili cioè
xj ≥ 0, j = 1, . . . , n.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

50 MODELLI DI PROGRAMMAZIONE LINEARE

Introducendo la matrice (m × n)
 
a11 ... a1n
. .. 
A =  .. .
am1 ... amn

e il vettore b = (b1 , . . . , bm )T la formulazione completa del problema può essere

scritta nella forma 
 min cT x
Ax ≥ b

x ≥ 0.

Nella pratica, potrebbe essere necessario introdurre ulteriori vincoli:

• possono essere presenti limitazioni superiori o inferiori sulle variabili cioè

xj ≥ L, xj ≤ M , j = 1, . . . , n;

• se è richiesto anche che la miscela contenga una quantità non superiore ad

un valore di di ciascun componente Ci si dovrà aggiungere alla formulazione
un altro vincolo di qualità:
n
X
aij xj ≤ di , i = 1, . . . , m;
j=1

• in alcuni casi si richiede che una certa sostanza appartenga alla miscela
solo se un’altra sostanza vi appartiene (o non vi appartiene). Questi vincoli
richiedono l’uso di variabili booleane come descritto in seguito.

Esempio 3.4.14 Il prodotto finale di una fabbrica è ottenuto raffinando materie

prime grezze e miscelandole insieme. Queste materie prime possono essere di
due categorie: naturali e sintetizzate. In particolare, sono disponibili tre materie
prime naturali (N1, N2, N3) e due materie prime sintetizzate (S1, S2). Le
materie prime naturali e quelle sintetizzate richiedono differenti linee di produ-
zione. Ogni settimana è possibile raffinare non più di 500 quintali di materie
prime naturali e non più di 300 quintali di materie prime sintetizzate. Si assume
che non ci sia perdita di peso durante la raffinazione e che si possa trascurare il
costo di raffinazione. Inoltre esiste una restrizione tecnologica sulla gradazione
del prodotto finale: nell’unità di misura in cui questa gradazione è misurata, essa
deve essere tra 2 e 7; si assume che tale gradazione nella miscela finale dipen-
da linearmente dalle singole gradazioni delle materie prime componenti. Nella
tabella che segue è riportato il costo (in euro) per quintale e la gradazione delle
materie prime grezze.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 51

N1 N2 N3 S1 S2
costo 300 190 250 200 230
grad. 6.0 1.9 8.5 5.0 3.5

Il prodotto finale viene venduto a 350 euro per quintale. Determinare come va
pianificata la produzione settimanale per massimizzare il profitto netto.

Formulazione.
– Variabili. Introduciamo le variabili di decisione x1 , x2 , x3 , x4 , x5 rappresentanti
le quantità (in quintali) di N1, N2, N3, S1, S2 che devono essere comprate
e raffinate in una settimana. Inoltre introduciamo una ulteriore variabile y che
indica la quantità di prodotto finale che deve essere fabbricato.
– Funzione obiettivo. La funzione obiettivo da massimizzare sarà data dal profitto
netto cioè da

350y − 300x1 − 190x2 − 250x3 − 200x4 − 230x5 .

– Vincoli. Sono presenti tre tipi di vincoli

· capacità di raffinamento

x1 + x2 + x3 ≤ 500

x4 + x5 ≤ 300;

· limitazioni sulla gradazione

6.0x1 + 1.9x2 + 8.5x3 + 5.0x4 + 3.5x5 ≤ 7y

6.0x1 + 1.9x2 + 8.5x3 + 5.0x4 + 3.5x5 ≥ 2y;

· vincolo di continuità

x1 + x2 + x3 + x4 + x5 = y.

Questo vincolo di continuità esprime il fatto che il peso finale del prodotto
deve essere uguale alla somma dei pesi degli ingredienti.
Inoltre si devono esplicitare i vincoli di non negatività delle variabili.
La formulazione finale risulta quindi

 max (−300x1 − 190x2 − 250x3 − 200x4 − 230x5 + 350y)



 x1 + x2 + x3 ≤ 500



 x4 + x5 ≤ 300
6.0x1 + 1.9x2 + 8.5x3 + 5.0x4 + 3.5x5 − 7y ≤ 0



 6.0x1 + 1.9x2 + 8.5x3 + 5.0x4 + 3.5x5 − 2y ≥ 0



 1 + x2 + x3 + x4 + x5 − y = 0
x

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, y ≥ 0

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

52 MODELLI DI PROGRAMMAZIONE LINEARE

Osservazione 3.4.15 Un errore comune è quello di scrivere i vincoli sulla gra-

dazione
6.0x1 + 1.9x2 + 8.5x3 + 5.0x4 + 3.5x5 ≤ 7

6.0x1 + 1.9x2 + 8.5x3 + 5.0x4 + 3.5x5 ≥ 2.

Queste relazioni sono evidentemente dimensionalmente errate: il primo mem-

bro ha le dimensioni di gradazione × quantità mentre il secondo membro ha le
dimensioni della gradazione. Tuttavia, invece delle variabili xi in queste due di-
suguaglianze si potevano usare le variabili xi /y per rappresentare le proporzioni
degli ingredienti, piuttosto che le quantità assolute xi ; ovviamente, in questo caso
si dovevano modificare anche le altre espressioni. Comunque, l’uso delle variabili
xi /y è ovviamente possibile solo nel caso in cui la quantità di prodotto fabbricato
è non nulla, cioè y 6= 0.

Modelli di input–output
I modelli di miscelazione possono essere visti come modelli piú generali in cui le
sostanze Sj e i componenti utili Ci sono genericamente definiti come “input” e
“output”; per ogni input j si deve decidere la quantità xj da utilizzare incorrendo
in un costo cj xj e creando aij xj unità di output i. Lo scopo è quello di deter-
minare la combinazione a più basso costo di input che fornisce, per ogni output
i, una quantità di unità di output compresa tra valori prefissati. Nei modelli di
miscelazione analizzati fino ad ora, gli input sono dati dalle sostanze che devono
essere mescolate, gli output sono dati dalle qualità della miscela risultante.
Un esempio di questa generalizzazione è dato dai problemi di assegnazione di
personale a turni che rappresentano problemi di fondamentale importanza in di-
versi settori applicativi; in questo caso gli output possono corrispondere alle ore
lavorate in un certo giorno i e, per ogni turno lavorativo j, aij rappresenta il
numero di ore che una persona assegnata al turno j lavorerà il giorno i (ponendo
aij = 0 se la persona assegnata al turno j non lavora il giorno i); le cj rappre-
sentano il salario di una persona assegnata al turno j e xj il numero di persone
assegnate a quel turno. In questo contesto, la funzione obiettivo diventa il costo
totale dei salari mensile, mentre i vincoli diventano quelli dovuti al fatto che ogni
giorno i, il numero totale di ore lavorative fornite dalle persone che lavorano quel
giorno deve essere pari ad almeno un valore prefissato bi . Supponendo di voler
considerare n giorni e m possibili turni, un modello di Programmazione Lineare
che rappresenti questa situazione è dato da

min c1 x1 + . . . + cn xn

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 53

a11 x1 + ... +a1n xn ≥ b1

a21 x1 + ... +a2n xn ≥ b2
.. .. ..
. ... . .
am1 x1 + ... +amn xn ≥ bm
xj ≥ 0, j = 1, . . . , n.

In questo caso però, a differenza degli altri casi di miscelazione visti fino ad
ora, l’assunzione di continuità delle variabili non è molto plausibile e potrebbe
risultare necessario introdurre il vincolo di interezza sulle variabili.
Il concetto di modello di “input–output” fu una delle prime applicazioni della
Programmazione Lineare nelle analisi economiche.
Si riporta, di seguito, un semplice esempio di assegnamento di personale a turni
di lavoro.

Esempio 3.4.16 Un catena di ristoranti opera sette giorni alla settimana e

richiede il seguente numero minimo di camerieri:

Lun. Mar. Mer. Giov. Ven. Sab. Dom.

52 50 47 55 70 40 40

Ciascun cameriere lavora seguendo turni cosı́ definiti: cinque giorni lavorativi
ogni settimana e due di riposo; inoltre sono possibili al piú quattro giorni con-
secutivi di lavoro seguiti da uno di riposo; inoltre uno solo dei due giorni del
fine settimana (sabato o domenica) deve far parte del turno di lavoro. I turni
risultanti sono sei e sono schematizzati nella tabella che segue (dove “L” indica
giornata lavorativa e “R” riposo):

Turni: 1o 2o 3o 4o 5o 6o 7o 8o

Lun. L R L L L L L L
Mar. L L R L L R L L
Mer. L L L R L L R L
Giov. L L L L R L L R
Ven. R L L L L L L L
Sab. L R L R L R L R
Dom. R L R L R L R L

Il salario settimanale di un cameriere è pari a 250 Euro se assegnato ad un turno

che non comprende la domenica, mentre è pari a 270 Euro se il turno comprende
anche la domenica. Il gestore di questa catena di ristoranti vuole minimizzare
il costo che deve sostenere per retribuire i camerieri in modo da soddisfare le
richieste giornaliere.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

54 MODELLI DI PROGRAMMAZIONE LINEARE

Formulazione.
–Variabili. Si associano le variabili di decisione xj al numero di camerieri asse-
gnati al turno j, j = 1, . . . , 8.
–Funzione obiettivo. È data dal salario complessivo dei camerieri e quindi può
essere espressa nella forma
250x1 + 270x2 + 250x3 + 270x4 + 250x5 + 270x6 + 250x7 + 270x8 .

–Vincoli. I vincoli sono dovuti al fatto che ogni giorno c’è una richiesta minima
di camerieri. Osservando ogni giorno quale turno prevede il lavoro o il riposo si
ottengono i seguenti vincoli
x1 + x3 + x4 + x5 + x6 + x7 + x8 ≥ 52
x1 + x2 + x4 + x5 + +x7 + x8 ≥ 50
x1 + x2 + x3 + x5 + x6 + x8 ≥ 47
x1 + x2 + x3 + x4 + x6 + x7 ≥ 55
x2 + x3 + x4 + x5 + x6 + x7 + x8 ≥ 70
x1 + x3 + x5 + x7 ≥ 40
x2 + x4 + x6 + x8 ≥ 40

Si deve inoltre esplicitare la non negatività delle variabili xj ≥ 0, j = 1, . . . , 8 e

l’interezza xj ∈ Z, j = 1, . . . , 8.
La formulazione completa sarà quindi

 min (250x1 + 270x2 + 250x3 + 270x4 + 250x5 + 270x6 + 250x7 + 270x8 )



 x1 + x3 + x4 + x5 + x6 + x7 + x8 ≥ 52



 x 1 + x2 + x4 + x5 + x7 + x8 ≥ 50



 x1 + x2 + x3 + x5 + x6 + x8 ≥ 47

x1 + x2 + x3 + x4 + x6 + x7 ≥ 55



 x2 + x3 + x4 + x5 + x6 + x7 + x8 ≥ 70



 x1 + x3 + x5 + x7 ≥ 40



 x + x4 + x6 + x8 ≥ 40

 2
xj ≥ 0, xj ∈ Z, i = 1, . . . , 8

È chiaramente riconoscibile questa formulazione come un modello di miscelazione;

è sufficiente, infatti, introdurre la matrice A che definisce i vincoli di un problema
di miscelazione nel seguente modo:

1 se nel posto (i, j) della tabella c’è la lettera “L”
aij =
0 se nel posto (i, j) della tabella c’è la lettera “R”.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 55

3.4.3 Modelli di trasporto

Si tratta di problemi in cui si hanno un certo numero di località (origini) cia-

scuna delle quali ha una quantità fissata di merce disponibile e un certo numero
di clienti residenti in altre località (destinazioni) i quali richiedono quantitativi
precisi di merce. Quindi conoscendo il costo unitario del trasporto della merce da
ciascuna località origine a ciascuna località destinazione è necessario pianificare
i trasporti, cioè la quantità di merce che deve essere trasportata da ciascuna lo-
calità origine a ciascuna località destinazione in modo da soddisfare l’ordine dei
clienti minimizzando il costo complessivo derivante dai trasporti.

Esempio 3.4.17 Un’industria dell’acciaio dispone di due miniere M1 e M2 e

di tre impianti di produzione P1 P2 P3 . Il minerale estratto deve essere giornal-
mente trasportato agli impianti di produzione soddisfacendo le rispettive richieste.
Le miniere M1 e M2 producono giornalmente rispettivamente 130 e 200 tonnel-
late di minerale. Gli impianti richiedono giornalmente le seguenti quantità (in
tonnellate) di minerale

P1 P2 P3
80 100 150

Il costo (in euro) del trasporto da ciascuna miniera a ciascun impianto di produ-
zione di una tonnellata di minerale è riportato nella seguente tabella

P1 P2 P3
M1 10 8 21
M2 12 20 14

Formulare un modello che descriva il trasporto dalle miniere agli impianti di

produzione in modo da minimizzare il costo globale del trasporto.

Analisi del problema.

È un problema di trasporti con 2 origini (M1 , M2 ) e 3 destinazioni (P1 P2 P3 ).
Si noti che risulta 130 + 200 = 330 e 80 + 100 + 150 = 330, ovvero la somma delle
disponiblità uguaglia la somma delle richieste.

Formulazione.
– Variabili. Associamo le variabili di decisione alle quantità di minerale che deve
essere trasportato; indichiamo con xij i = 1, 2, j = 1, 2, 3, le quantità (in
tonnellate) di minerale da trasportare giornalmente da ciascuna miniera Mi a
ciascun impianto di produzione Pj .

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

56 MODELLI DI PROGRAMMAZIONE LINEARE

– Funzione obiettivo. La funzione obiettivo da minimizzare è data dalla somma

dei costi dei trasporti cioè da

z = 10x11 + 8x12 + 21x13 + 12x21 + 20x22 + 14x23 .

– Vincoli. I vincoli di origine esprimono il fatto che la somma della quantità

di minerale trasportato dalla miniera Mi deve essere uguale alla disponibilità
giornaliera della miniera stessa:

x11 + x12 + x13 = 130

x21 + x22 + x23 = 200.

I vincoli di destinazione esprimono il fatto che la somma delle quantità di mi-

nerale trasportato all’impianto di produzione Pj deve essere pari alla richiesta
giornaliera di tale impianto:

x11 + x21 = 80
x12 + x22 = 100
x13 + x23 = 150.

Infine si devono considerare i vincoli di non negatività xij ≥ 0, i = 1, 2, j =

1, 2, 3.
La formulazione completa è quindi


 min (10x11 + 8x12 + 21x13 + 12x21 + 20x22 + 14x23 )



 x 11 + x12 + x13 = 130



 x21 + x22 + x23 = 200
x11 + x21 = 80



 x 12 + x22 = 100



 x13 + x23 = 150


xij ≥ 0, i = 1, 2, j = 1, 2, 3.

Formulazione generale di un problema di trasporti

Sono definite m località origini indicate con O1 , . . . , Om , e n località destina-
zioni indicate con D1 , . . . , Dn . Ogni origine Oi , (i = 1, . . . , m) può fornire una
certa disponibilità ai ≥ 0 di merce che deve essere trasferita dalle origini alle
destinazioni
O1 · · · Om
a1 · · · am .
Ad ogni destinazione Dj , (j = 1, . . . , n) è richiesta una quantità bj ≥ 0 di merce.

D1 ··· Dn
b1 ··· bn .

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 57

Supponiamo che il costo del trasporto di una unità di merce da Oi a Dj sia

pari a cij . Tali costi nella realtà sono spesso collegati alle distanze tra origini e
destinazioni.
Il problema consiste nel pianificare i trasporti in modo da soddisfare le richieste
delle destinazioni minimizzando il costo del trasporto complessivo nella seguente
ipotesi:
• la disponibilità complessiva uguaglia la richiesta complessiva, cioè
m
X n
X
ai = bj ; (3.4.1)
i=1 j=1

si escludono possibilità di giacenze nelle origini, cioè tutta la merce prodotta

in una origine deve essere trasportata in una delle destinazioni; si escludono
possibilità di giacenze nelle destinazioni, cioè la quantità totale che arriva in una
destinazione Dj deve uguagliare la richiesta bj .
Formulazione.
Si vuole dare una formulazione del problema in esame in termini di un problema
di programmazione lineare supponendo quindi che siano verificate le ipotesi di
linearità e continuità.
– Variabili. Per ogni coppia di origine e destinazione Oi , Dj si introducono le
variabili di decisione xij rappresentanti la quantità di merce da trasportare da
Oi , a Dj . Si tratta di mn variabili
D1 ··· Dj ··· Dn
O1 x11 ··· x1j ··· x1n
.. .. .. ..
. . . .
Oi xi1 ··· xij ··· xin
.. .. .. ..
. . . .
Om xm1 ··· xmj ··· xmn

– Funzione obiettivo. La funzione obiettivo da minimizzare sarà data da costo

totale del trasporto e quindi da
m X
X n
z= cij xij .
i=1 j=1

– Vincoli. Per le ipotesi fatte, si avranno due tipi di vincoli:

• vincoli di origine

n
X
xij = ai i = 1, . . . , m; (3.4.2)
j=1

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

58 MODELLI DI PROGRAMMAZIONE LINEARE

impongono che tutta la merce prodotta in una origine sia trasportata alle
destinazioni; si tratta di m vincoli;

• vincoli di destinazione

m
X
xij = bj j = 1, . . . , n; (3.4.3)
i=1

impongono che la quantità totale di merce che arriva in ciascuna delle

destinazioni uguaglia la richiesta; si tratta si n vincoli.

Si devono infine considerare i vincoli di non negatività delle variabili

xij ≥ 0 i = 1, . . . , n; j = 1, . . . , m.

Si è cosı̀ ottenuta una formulazione del problema dei trasporti con mn variabili
e m + n + mn vincoli:
  

 Xm X n



 min  cij xij 



 i=1 j=1

 Xn

xij = ai i = 1, . . . , m (3.4.4)

 j=1

 m

 X

 xij = bj j = 1, . . . , n



 i=1

xij ≥ 0 i = 1, . . . , n; j = 1, . . . , m.

Osservazione 3.4.18 È chiaro che per le ipotesi fatte dovrà risultare

X n
m X X m
n X m
X n
X
xij = xij = ai = bj .
i=1 j=1 j=1 i=1 i=1 j=1

Esaminiamo, ora, un risultato che è una condizione necessaria e sufficiente af-

finché un generico problema dei trasporti scritto nella forma (3.4.4) con ai ≥ 0
e bj ≥ 0 abbia soluzione; tale risultato chiarisce perché nella formulazione clas-
sica del problema dei trasporti si adotta l’ipotesi (3.4.1) cioè che la disponibilità
complessiva uguagli la richiesta complessiva.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

 CLASSI DI MODELLI DI PROGRAMMAZIONE LINEARE 59

Teorema 3.4.1 Condizione necessaria e sufficiente affinché esista una

soluzione ammissibile per problema (3.4.4), è che risulti
m
X n
X
ai = bj . (3.4.5)
i=1 j=1

Dimostrazione: Dimostriamo innanzitutto la necessità, cioè che se esiste una

soluzione ammissibile che denotiamo con x̄ij , i = 1, . . . , m, j = 1, . . . , n, allora la
condizione (3.4.5) deve essere verificata; poiché x̄ij deve soddisfare i vincoli, dalle
equazioni dei vincoli nella (3.4.4) si ottiene
X n
m X m
X
x̄ij = ai
i=1 j=1 i=1

X m
n X n
X
x̄ij = bj ,
j=1 i=1 j=1

e sottraendo membro a membro si ha

m
X n
X
ai − bj = 0
i=1 j=1

che è la (3.4.5).
Dimostriamo ora la sufficienza; supponiamo quindi che valga la (3.4.5) e poniamo
m
X n
X
ai = bj = A.
i=1 j=1

a i bj
Si vuole allora dimostrare che esiste una soluzione ammissibile; infatti, sia x̄ij := ,
A
i = 1, . . . , m, j = 1, . . . , n; allora x̄ij ora definito è una soluzione ammissibile per il
problema dei trasporti. Infatti risulta innanzitutto x̄ij ≥ 0 per ogni i = 1, . . . , m
e j = 1, . . . , n per la non negatività degli ai e dei bj ; inoltre
P
X n Xn
a i bj ai nj=1 bj
x̄ij = = = ai
A A
j=1 j=1

m
X m
X Pm
ai bj bj i=1 ai
x̄ij = = = bj
A A
i=1 i=1
e quindi x̄ij soddisfando i vincoli del problema è una soluzione ammissibile.

Il teorema appena dimostrato garantisce quindi che, se è soddisfatta l’ipotesi

(3.4.1) allora il problema dei trasporti ammette sempre soluzione.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019

60 MODELLI DI PROGRAMMAZIONE LINEARE

Osservazione 3.4.19 La soluzione ammissibile del teorema, ovviamente, non è

l’unica soluzione ammissibile del problema.

Riportiamo di seguito, senza dimostrazione, un altro risultato di fondamentale

importanza nella trattazione del problema dei trasporti.

Teorema 3.4.2 Se nel problema dei trasporti le ai , i = 1, . . . , m e le bj ,

j = 1, . . . , n sono intere e se il problema ammette soluzione ottima, allora ha
una soluzione ottima intera.

Passiamo, ora, ad analizzare alcune varianti della formulazione classica del pro-
blema dei trasporti; può infatti accadere che non tutte le rotte di trasporto siano
disponibli: se non è possibile il trasporto da una certa origine Oi ad una desti-
nazione Dj si pone, per convenzione, cij = ∞. Oppure possono esistere rotte di
trasporto in cui vi sono limitazioni sulle quantità massima di merci trasportabili.
Infine, si può supporre che la disponibilità complessiva possa essere superiore alla
domanda cioè
Xm Xn
ai ≥ bj . (3.4.6)
i=1 j=1

In tal caso, possono essere ammesse giacenze nelle origini e/o nelle destinazioni;
se si accetta di avere giacenze nelle origini, allora i vincoli di origine diventano
n
X
xij ≤ ai i = 1, . . . , m;
j=1

se si accetta di avere giacenze nelle destinazioni, allora i vincoli di destinazione

diventano m
X
xij ≥ bj j = 1, . . . , n.
i=1

nel caso in cui vale la (3.4.6), per porre il problema dei trasporti nella sua formula-
zione classica, cioè con vincoli di uguaglianza, si può introdurre una destinazione
fittizia che abbia una richiesta pari a
m
X n
X
ai − bj
i=1 j=1

ponendo uguale a zero il costo per raggiungere questa destinazione fittizia da

qualsiasi origine.

M. Roma – RICERCA OPERATIVA – SAPIENZA Università di Roma – a.a. 2018-2019