Capitolo 4

Soluzione grafica di problemi PM

in 2 variabili

In questo paragrafo si vuole fornire una interpretazione geometrica di un problema di Program-

mazione matematica. In particolare, quando un problema di Programmazione matematica è
definito solamente in due variabili, si può rappresentare efficacemente il problema sul piano
cartesiano e si può determinare una sua soluzione in maniera elementare con semplici deduzioni
geometriche. Le situazioni che verranno presentate nel seguito vogliono rappresentare un punto
di partenza intuitivo per la trattazione di problemi di Programmazione Lineare in n variabili; i
risultati che verranno dedotti per via elementare nel caso bidimensionale trovano, infatti, una
generalizzazione consistente nel caso di un generico problema di Programmazione Lineare.

4.1 Rappresentazione di vincoli nel piano cartesiano

In questo paragrafo si richiamano le rappresentazioni geometriche nel piano di alcune curve
note in modo analitico.

4.1.1 Vincoli lineari

Nel piano cartesiano Ox1 x2 l’equazione lineare
a1 x1 + a2 x2 = c (4.1)
rappresenta una retta che partiziona il piano in due semipiani. Ciascun semipiano è caratter-
izzato da punti P (x1 , x2 ) che soddisfano la disequazione ax1 + bx2 ≥ c oppure la disequazione
ax1 + bx2 ≤ c. Quindi ogni disequazione del tipo
ax1 + bx2 ≥ c oppure ax1 + bx2 ≤ c
individua univocamente un semipiano. Si riporta, ora, un semplice risultato geometrico che
verrà utilizzato nel seguito.

Lemma 4.1.1 Si considera una famiglia di rette parallele

a1 x1 + a2 x2 = c (4.2)

42
  
a1
con a1 , a2 ∈ IR fissati e con c ∈ IR. Il vettore a = individua una direzione ortogonale alle
a2
rette della famiglia (4.2) ed è orientato dalla parte in cui sono le rette della famiglia ottenute
per valori crescenti della c, cioè verso il semipiano in cui risulta a1 x1 + a2 x2 ≥ c.

Dimostrazione. Sia x un vettore di componenti x1 e x2 . La famiglia di rette (4.2) può essere

scritta in forma vettoriale
aT x = c.
Siano ora x̄ e z̄ due punti appartenenti alla retta aT x = c. Risulta quindi
aT z̄ = c e aT x̄ = c
e sottraendo membro a membro queste due uguaglianze si ottiene
aT (z̄ − x̄) = 0.
Quindi il vettore a è ortogonale al vettore z̄ − x̄ che individua la direzione della famiglia di rette
cioè il vettore a rappresenta una direzione ortogonale alla famiglia di rette (4.2).
Si consideri ora un punto x̄ = (x1 , x2 )T appartenente alla retta aT x = c e un punto
ȳ = (y1 , y2 )T tale che aT y ≥ c. Si vuole dimostrare che il punto ȳ appartiene al semipiano
individuato dalla retta aT x = c verso il quale è orientato il vettore a. Infatti, per le ipotesi
fatte, si ha
aT ȳ ≥ c e aT x̄ = c
e sottraendo membro a membro queste due relazioni si ottiene
aT (ȳ − x̄) ≥ 0
e questo significa che l’angolo θ che il vettore ȳ − x̄ forma con il vettore a deve essere acuto
e quindi il vettore a deve essere orientato verso il semipiano ove si trova il punto ȳ, cioè il
semipiano individuato dalla diseguaglianza aT x ≥ c. (Figura 4.1)

Come esempio del risultato riportato dallemma  appena dimostrato, si consideri la disug-
3
uaglianza lineare 3x1 +x2 ≥ 6. Il vettore a = individua una direzione ortogonale alla retta
1
3x1 + x2 = 6 ed è orientato verso il semipiano individuato dalla disuguaglianza 3x1 + x2 ≥ 6
(Figura 4.2).
Nella pratica, per determinare quale dei due semipiani è individuato dalla disuguaglianza
lineare a1 x1 +a2 x2 ≥ c si può procedere semplicemente in questo modo: dopo aver rappresentato
la retta a1 x1 + a2 x2 = c per individuare qual è il semipiano di interesse, si può scegliere un
punto P del piano (l’origine degli assi è il piú semplice) e valutare l’espressione a1 x1 + a2 x2 in
questo punto; se il valore cosı̀ ottenuto è maggiore o uguale di c allora il semipiano individuato
dalla disuguaglianza lineare a1 x1 + a2 x2 ≥ c è quello contenente il punto P ; in caso contrario
è quello opposto.

4.1.2 Vincoli quadratici

Nel piano cartesiano Ox1 x2 le equazioni quadratiche rappresentano delle coniche. Consideriamo
delle equazioni del tipo h(x1 , x2 ) = 0 polinomi di grado massimo pari a due. Ci limiteremo a
richiamare le equazioni h = 0 della circonferenza e della parabola.

43
 x
2

T
ax> C

-
y

θ
a
_
x
T
ax ≤ C

x
1

Figura 4.1: Interpretazione geometrica del Lemma 4.1.1

3x 1+ x2 > 6
3x 1+ x2 ≤ 6

1111111
0000000
0000000 a
1111111
0000000
1111111
2

Figura 4.2: Rappresentazione del vincolo lineare 3x1 + x2 ≥ 6

44
Nel piano cartesiano Ox1 x2 l’equazione quadratica

h(x1 , x2 ) = (x1 − a1 )2 + (x2 − a2 )2 − r2 = 0 (4.3)

rappresenta una circonferenza di centro C=(a1 a2 )T e raggio fissato r. Il gradiente di h è dato

     
2(x1 − a1 ) x1 a1
∇h(x) = =2 −
2(x2 − a2 ) x2 a2

Ad una circonferenza possono essere associati due insiemi

S ≤ = {x ∈ IR2 : (x1 − a1 )2 + (x2 − a2 )2 ≤ r2 }

S ≥ = {x ∈ IR2 : (x1 − a1 )2 + (x2 − a2 )2 ≥ r2 }

la cui intersezione è la circonferenza stessa. S ≤ è l’insieme dei punti ”interni“ alla circonferenza,
mentre S ≥ rappresenta i punti “esterni”.
Nel piano cartesiano Ox1 x2 le equazioni quadratiche riconducibili alla forma


h(x1 , x2 ) = x2 − a1 x21 + a2 x1 + a3
= 0
h(x1 , x2 ) = x1 − a1 x22 + a2 x2 + a3 = 0

rappresentano rispettivamente una parabola con asse parallelo all’asse delle ordinate e ascissa
a2
del vertice pari a − 2a 1
e una parabola con asse parallelo all’asse delle ascisse e ordinata del
a2
vertice pari a − 2a1 . Consideriamo senza perdere di generalità la prima delle due equazioni e
gli insiemi individuati dai due vincoli di disuguaglianza corrispondenti

S ≤ = {x ∈ IR2 : x2 ≤ a1 x21 + a2 x1 + a3 }
S ≥ = {x ∈ IR2 : x2 ≥ a1 x21 + a2 x1 + a3 }

S ≤ è l’insieme dei punti che si trova “internamente” alla parabola stessa e S ≥ è l’insieme dei
punti “esterni”.

4.2 Rappresentazione di funzioni obiettivo

Quanto esposto nel paragrafo precedente è utile anche per esaminare la variazione di una fun-
zione lineare/quadratica che rappresenta la funzione obiettivo di un problema di Program-
mazione Matematica. In particolare, data una generica funzione obiettivo f (x1 , x2 ), si rappre-
sentano le curve di livello della funzione ovvero le curve

f (x1 , x2 ) = k (4.4)

ottenuta al variare di k. Se il problema è di minimizzazione, si cercherà di ottenere un valore

piú basso possibile per la k in corrispondenza di valori ammissibili per x1 e x2 ; viceversa, se il
problema è di massimizzazione, si cercherà ottenere un valore piú alto possibile per la k.

4.2.1 Funzioni lineari

In due variabili, la funzione obiettivo di un problema di Programazione Lineare è un’espressione
del tipo f (x1 , x2 ) = c1 x1 + c2 x2 da massimizzare o da minimizzare. Per rappresentare questa

45
funzione obiettivo su un piano cartesiano Ox1 x2 si considera la famiglia di rette parallele (k =
C)
c1 x1 + c2 x2 = C (4.5)
ottenuta al variare di C, che rappresentano le rette di livello della funzione. Sulla base di quanto
esposto nel paragrafo precedente,
 valori
 superiori della C si determinano traslando le rette nel
c1
verso individuato dal vettore che rappresenta, quindi, una direzione di crescita per la
c2
funzione c1 x1 + c2 x2 . Ovviamente, la direzione opposta sarà una direzione di decrescita.
Quindi, geometricamente, un problema di massimizzazione consisterà nel considerare la
traslazione nel verso della direzione di crescita della funzione obiettivo, mentre in un problema
di minimizzazione si considera la traslazione nel verso opposto (Figura 4.3)

x2

12

11
direzione di crescita
10

7
6

1 2 3 4 5 6 2 x +x =12 x1
1 2
2 x 1 +x 2=8 2 x 1 +x 2=10

Figura 4.3: Rette di livello della funzione 2x1 + x2

4.2.2 Funzioni quadratiche

In due variabili, consideriamo la funzione obiettivo quadratica

f (x1 , x2 ) = (x1 − a1 )2 + (x2 − a2 )2 (4.6)

Per rappresentare questa funzione obiettivo su un piano cartesiano Ox1 x2 si considera la famiglia
di curve (k = r2 )
(x1 − a1 )2 + (x2 − a2 )2 = C 2 (4.7)

46
ottenuta al variare di C, che rappresentano circonferenze concentriche di raggio variabile C.
Se il problema è di massimizzazione si vuole trovare il massimo valore di raggio ottenibile
in corrispondenza di valori ammissibili per x1 e x2 ; viceversa se si tratta di minimizzazione.
Osserviamo che se il centro della circonferenza base è ammissibile, esso costituisce il punto di
minimo globale.

4.3 Esempi di risoluzione grafica

Verranno considerati alcuni esempi di problemi di Programmazione Matematica.

Esempio 4.3.1 Sia la funzione obiettivo da minimizzare:

f (x) = x1
e sia l’insieme ammissibile F definito dai vincoli:
2 2
(x1 − 3) + (x2 − 2) = 13
2
(x1 − 4) + x2 2 ≤ 16
Determinare graficamente, se esiste, un punto di minimo.
Soluzione. Questo esempio evidenzia geometricamente la definizione di minimo locale vinco-
lato in un problema a 2 variabili.
L’insieme ammissibile F , rappresentato in Figura (4.4), ed è dato dall’arco di circonferenza
d (tratteggiato in verde). Poiché esso è compatto e f è continua, in base al Teorema di
ACB
Weierstrass, l’esistenza di un minino globale è assicurata.
Le curve di livello x1 = k sono rette parallele all’asse delle ordinate con valore crescente
all’aumentare di k. Si determina il punto di minimo globale nel punto A = (0, 0)T di valore
f ∗ = 0. Si osserva che il punto C è un massimo globale, mentre il punto B risulta essere un
minimo locale.

Esempio 4.3.2 Sia dato il problema di ottimizzazione vincolata

min 2x1 + 3x2
6x1 + x22 − x2 ≤ 12
x1 − 4x2 ≤ −2
x1 , x2 ≥ 0
Determinare, se esiste, un punto di minimo globale.

Esempio 4.3.3 Si consideri la funzione obiettivo:

1
f (x) = (x1 2 + x2 2 )
2
e sia l’insieme ammissibile F definito dai vincoli:
x1 + x2 = 1
(x1 − 1)2 + x2 2 ≤ 1
4

Determinare se esiste un punto di minimo.

47
 x2

A x1

Figura 4.4: Soluzione grafica in IR2 dell’Esempio 4.3.1.

Soluzione. L’insieme ammissibile F é dato dal segmento di retta che ha per estremi i punti
 T  
1 1 1 1
x̃ = 1 − 2√ , √
2 2 2
e x̄ = 1 + √ , √
2 2 2 2
T.

L’esistenza di una soluzione è garantita dal Teorema di Weierstrass poiché la funzione

obiettivo è continua e l’insieme ammissibile é compatto.
Le curve di livello della funzione obiettivo
1
(x1 2 + x2 2 ) = r2
2
sono circonferenze di centro l’origine e raggio r.

Esempio 4.3.4
Si consideri ora il problema di allocazione ottima di risorse del Paragrafo 2.4.1 che è rappresen-
tato dal seguente problema di Programmazione Lineare:

max 7x1 + 10x2

x1 + x2 ≤ 750
x1 + 2x2 ≤ 1000
x2 ≤ 400
x1 ≥ 0, x2 ≥ 0.

48
 Figura 4.5: Soluzione grafica in IR2 dell’Esempio 4.3.3.

Sul piano cartesiano Ox1 x2 ciascun vincolo individua un semipiano. In particolare, in Figura 4.6
è evidenziato il semipiano individuato dal primo vincolo x1 + x2 ≤ 750.
In Figura 4.7 è evidenziato il semipiano individuato dal secondo vincolo x1 + 2x2 ≤ 1000.
Infine in Figura 4.8 è evidenziato il semipiano individuato dal terzo vincolo x2 ≤ 400.
Ovviamente i vincoli di non negatività delle variabili x1 ≥ 0 e x2 ≥ 0 rappresentano
rispettivamente il semipiano delle ascisse non negative e il semipiano delle ordinate non negative.
L’insieme ammissibile del problema di Programmazione Lineare che stiamo esaminando è
dato quindi dall’intersezione di tali semipiani e si può indicare con

n o
S = (x1 , x2 ) ∈ IR2 | x1 + x2 ≤ 750, x1 + 2x2 ≤ 1000, x2 ≤ 400, x1 ≥ 0, x2 ≥ 0 .

Tale regione di piano prende nome di regione ammissibile, è un insieme convesso ed è rappre-
sentato in Figura 4.9.
Tutti i punti P (x1 , x2 ) appartenenti a questa regione sono punti dell’insieme ammissibile
del problema e quindi tutti i punti di questa regione costituiscono soluzioni ammissibili del
problema.
Si consideri ora la funzione obiettivo 7x1 + 10x2 e si consideri la famiglia di rette

7x1 + 10x2 = C

49
Figura 4.6: Semipiano individuato dal vincolo x1 + x2 ≤ 750

50
Figura 4.7: Semipiano individuato dal vincolo x1 + 2x2 ≤ 1000

51
 Figura 4.8: Semipiano individuato dal vincolo x2 ≤ 400

ottenute al variare del parametro C. Esse costituiscono le curve di livello della funzione in
due variabili f (x1 , x2 ) = 7x1 + 10x2 che sono ovviamente delle rette come rappresentato in
Figura 4.10.
In riferimento al problema di allocazione ottima rappresentato dal problema di Program-
mazione Lineare che stiamo esaminando, il parametro C rappresenta il profitto totale che deve
essere massimizzato. Per C = 0 si ottiene la linea di livello passante per l’origine del piano
Ox1 x2 . Ovviamente, scegliendo x1 = 0 e x2 = 0 (che è un punto ammissibile in quanto
(0, 0) ∈ S) si ottiene il profitto totale nullo. All’aumentare del valore di tale profitto, cioè
all’aumentare del valore della costante C, graficamente si ottengono rette parallele alla retta
di livello passante perl’origine traslate nella direzione di crescita della funzione 7x1 + 10x2
7
data dal vettore (Figura 4.10). Poiché si desidera massimizzare la funzione obiettivo,
10
si cercherà di raggiungere il valore piú alto per la C ottenuto scegliendo per x1 e x2 valori
ammissibili cioè tali che (x1 , x2 ) ∈ S. Osservando la rappresentazione grafica della regione
ammissibile S si deduce che all’aumentare di C, le rette di livello della funzione obiettivo inter-
secano la regione ammissibile finché C ≤ 6000. Tale valore è ottenuto per x1 = 500 e x2 = 250
e non esistono altri punti della regione ammissibile in cui la funzione obiettivo assume valori
maggiori. Il valore 6000 è, quindi, il massimo valore che la funzione obiettivo può raggiungere
soddisfacendo i vincoli. Tale soluzione ottima è raggiunta in corrispondenza del punto P di
coordinate (x1 , x2 ) = (500, 250); tale punto non è un punto qualsiasi, ma costituisce quello che
nella geometria piana viene detto vertice del poligono convesso che delimita la regione ammissi-
bile. Il fatto che l’ottimo del problema è raggiunto in corrispondenza di un vertice della regione
ammissibile non è casuale, ma come si vedrà in seguito, è una caratteristica fondamentale di
un generico problema di Programmazione Lineare. Si osservi fin d’ora che la frontiera della

52
Figura 4.9: La regione ammissibile S

53
Figura 4.10: Curve di livello della funzione f (x1 , x2 ) = 7x1 + 10x2 e punto di ottimo

54
regione ammissibile è definita dalle rette

x1 + x2 = 750, x1 + 2x2 = 1000, x2 = 400, x1 = 0, x2 = 0

e che ogni intersezione di due di queste rette è un vertice della regione ammissibile; il numero di
queste possibili intersezioni (non tutte necessariamente appartenenti alla regione ammissibile)
è ovviamente pari al piú a 10. Si osservi, infine, che nel punto di ottimo sono attivi i vincoli
x1 + x2 ≤ 750 e x1 + 2x2 ≤ 1000 mentre non è attivo il vincolo x2 ≤ 400.

Figura 4.11: Esempio di soluzione non unica

Nel caso particolare che abbiamo esaminando, la soluzione ottima determinata è unica,
ma in generale può accadere che le rette di livello della funzione obiettivo siano parallele ad

55
un segmento del perimetro del poligono che delimita la regione ammissibile; in questo caso
potrebbe accadere che esistano piú punti ammissibili in cui la funzione assume lo stesso valore
ottimo e quindi la soluzione non sarebbe piú unica; nel problema in esame, ciò accadrebbe, ad
esempio, se la funzione obiettivo fosse cx1 + 2cx2 con c costante reale positiva (Figura 4.11);
infatti, tutti i punti del segmento AB rappresentano soluzioni ottime.
Tuttavia, anche in questo caso si può sempre trovare un vertice che costituisce una soluzione
ottima.

Esempio 4.3.5
Consideriamo ora un problema di miscelazione descritto nel paragrafo 3.3.1 che è rappresentato
dal seguente problema di Programmazione Lineare:

 min(400x1 + 600x2 )


 140x1 ≥ 70
20x1 + 10x2 ≥ 30



 25x 1 + 50x2 ≥ 75
x1 ≥ 0, x2 ≥ 0
Nelle figure che seguono rappresentati i vincoli lineari di questo problema; In particolare nella
Figura 4.12 è evidenziato il semipiano individuato dal vincolo 140x1 ≥ 70. Nella Figura 4.13
e nella Figura 4.14 sono evidenziati rispettivamente i semipiani individuati dai vincoli 20x1 +
10x2 ≥ 30 e 25x1 + 50x2 ≥ 75.
Ovviamente i vincoli di non negatività delle variabili x1 ≥ 0 e x2 ≥ 0 rappresentano rispettiva-
mente il semipiano delle ascisse non negative e il semipiano delle ordinate non negative.
L’insieme ammissibile del problema di Programmazione Lineare che stiamo esaminando è
dato quindi dall’intersezione di tali semipiani e si può indicare con
n o
Se = (x1 , x2 ) ∈ IR2 | 140x1 ≥ 70, 20x1 + 10x2 ≥ 30, 25x1 + 50x2 ≥ 75, x1 ≥ 0, x2 ≥ 0 .

L’insieme Se rappresenta la regione ammissibile del problema di Programmazione Lineare in

esame ed è rappresentata in Figura 4.15.
Tutti i punti P (x1 , x2 ) appartenenti a questa regione sono punti dell’insieme ammissibile del
problema e quindi tutti i punti di questa regione costituiscono soluzioni ammissibili del prob-
lema. Si osservi che, a differenza della regione ammissibile del problema considerato nell’esempio
precedente, la regione ammissibile Se è illimitata.
Ora, tracciando le curve di livello della funzione obiettivo 400x1 +600x2 si ottiene la famiglia
di rette
400x1 + 600x2 = C.
Trattandosi di un problema di minimizzazione si vuole determinare il valore piú basso di C
ottenuto scegliendo per x1 e x2 valori ammissibili cioè tali che (x1 , x2 ) ∈ S. e Osservando la
rappresentazione grafica della regione e
 ammissibile S e osservando che la direzione di decrescita
400
è quella opposta al vettore , si deduce che al diminuire di C, le rette di livello della
600
funzione obiettivo intersecano la regione ammissibile finché C ≥ 1000 (Figura 4.16)
Tale valore è ottenuto per x1 = 1 e x2 = 1 e non esistono altri punti della regione ammissibile
in cui la funzione obiettivo assume valori minori. Il valore 1000 è, quindi, il minimo valore che

56
Figura 4.12: Semipiano individuato dal vincolo 140x1 ≥ 70

57
Figura 4.13: Semipiano individuato dal vincolo 20x1 + 10x2 ≥ 30

58
Figura 4.14: Semipiano individuato dal vincolo 25x1 + 50x2 ≥ 75

59
Figura 4.15: La regione ammissibile Se

60
Figura 4.16: Curve di livello della funzione 400x1 + 600x2 e punto di ottimo

61
la funzione obiettivo può raggiungere soddisfacendo i vincoli. Tale soluzione ottima è raggiunta
in corrispondenza del punto P di coordinate (x1 , x2 ) = (1, 1); si osservi che anche in questo
caso tale punto è un punto particolare della regione ammissibile. Si osservi, infine che in questo
punto sono attivi i vincoli 20x1 + 10x2 ≥ 30 e 25x1 + 50x2 ≥ 75 mentre risulta non attivo il
vincolo 140x1 ≥ 70.

Abbiamo esaminato due esempi di interpretazione geometrica e soluzione grafica di prob-

lemi di Programmazione Lineare in due variabili. In entrambe i problemi è stato possibile
determinare una soluzione ottima. Tuttavia è facile dedurre, sempre per via geometrica, che
un problema di Programmazione Lineare può non ammettere soluzione ottima. Ad esempio, se
nell’Esempio 4.3.4 sostituiamo il vincolo x2 ≤ 400 con il vincolo x2 ≥ 1000, la regione ammis-
sibile sarebbe vuota nel senso che non esisterebbe nessun punto del piano che soddisfa tutti i
vincoli. In questo caso il problema risulterebbe inammissibile e questo indipendentemente dalla
funzione obiettivo e dal fatto che il problema è in forma di minimizzazione o massimizzazione.
Un altro esempio di problema di Programmazione Lineare che non ammette soluzione ot-
tima si può ottenere considerando il problema dell’Esempio 4.3.5 e supponendo che la funzione
obiettivo debba essere massimizzata anziché minimizzata. In questo caso nella regione ammis-
sibile (che è illimitata) la funzione obiettivo può assumere valori arbitrariamente grandi cioè
tali che comunque scelto un valore M > 0 esiste un punto in cui la funzione obiettivo assume
valore maggiore di M ; questo significa che il problema è illimitato superiormente e quindi non
può esistere una soluzione ottima.
Sulla base di queste considerazioni sulla geometria di un problema di Programmazione
Lineare (PL) in due variabili si può intuire che le situazioni che si possono verificare sono le
seguenti:

• il problema di PL ammette soluzione ottima (che può essere o non essere unica) in
un vertice del poligono convesso che delimita la regione ammissibile;
• il problema di PL non ammette soluzione ottima perché

– la regione ammissibile è vuota

– la regione ammissibile è illimitata e la funzione obiettivo è illimitata superi-
ormente (se il problema è di massimizzazione) o illimitata inferiormente (se il
problema è di minimizzazione).

Quindi se si suppone che esiste un punto ammissibile, cioè che la regione ammissibile sia
non vuota, allora sembrerebbe di poter dedurre che o il problema di Programmazione Lineare
ammette soluzione ottima in un vertice del poligono convesso che delimita la regione ammissibile
oppure è illimitato.
Questi asserti, ora semplicemente dedotti intuitivamente per via geometrica, hanno in effetti
una validità generale e verranno enunciati e dimostrati in maniera rigorosa nel capitolo 10.

62
 x 2

11111111111111111111111111111
00000000000000000000000000000
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111 x 1

00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111
00000000000000000000000000000
11111111111111111111111111111

Figura 4.17: Regione ammissibile costituita da una striscia di piano

Come ultima considerazione intuitiva si vuole citare la possibilità che la regione ammissibile sia
costituita da una striscia di piano, cioè dalla porzione di piano compresa tra due rette parallele
(Figura 4.17). In questo caso non esistono vertici per la regione ammissibile e il problema risulta
illimitato ad eccezione del caso particolare in cui le rette di livello della funzione obiettivo sono
parallele alle rette che delimitano la striscia di piano; in questo caso si hanno infinite soluzioni.
La non esistenza di vertici in questo caso si intuisce essere legata al fatto che la regione
ammissibile costituita da una striscia di piano contiene rette. Infatti nei casi delle regioni am-
missibili S e Se dei problemi di Programmazione Lineare dell’Esempio 4.3.4 e dell’Esempio 4.3.5
non esistono rette interamente contenute in S o in S. e Anche la regione illimitata Se può contenere
semirette, ma non rette.
Nel caso in cui la regione ammissibile non contiene nemmeno semirette (che è il caso della
regione S dell’Esempio 4.3.4), cioè la regione ammissibile sia chiusa e limitata, è possibile
garantire l’esistenza di un minimo (e un massimo) assoluto per funzioni continue grazie al
teorema di Weierstrass.

63