Ricerca Operativa

Ricerca Operativa

Ricerca Operativa

Disciplina basata sulla modellizzazione e la risoluzione tramite strumenti automatici di problemi di decisione complessi.

In tali problemi la complessità è determinata dall’ampiezza dello spazio delle scelte possibili.

Ricerca Operativa – p. 2/64

Problema di decisione : componenti

Dati - tutto ciò che è noto a priori e non è sotto il controllo del decisore

Problema di decisione : componenti

Dati - tutto ciò che è noto a priori e non è sotto il controllo del decisore

Variabili - le quantità sotto il diretto controllo del decisore

Ricerca Operativa – p. 3/64

Problema di decisione : componenti

Dati - tutto ciò che è noto a priori e non è sotto il controllo del decisore

Variabili - le quantità sotto il diretto controllo del decisore

Vincoli - condizioni che limitano le possibili scelte del decisore

Problema di decisione : componenti

Dati - tutto ciò che è noto a priori e non è sotto il controllo del decisore

Variabili - le quantità sotto il diretto controllo del decisore

Vincoli - condizioni che limitano le possibili scelte del decisore

Obiettivo - criterio attraverso cui le scelte del decisore vengono confrontate

Ricerca Operativa – p. 3/64

Un (banale) esempio

In casa con voi avete:

una borsa del valore di 25 Euro

una macchina fotografica del valore di 100 Euro

un libro del valore di 10 Euro

Potete portare fuori di casa al massimo un oggetto. Volete portare con voi il massimo valore possibile

Un (banale) esempio - continua

Dati - i valori dei tre oggetti

Ricerca Operativa – p. 5/64

Un (banale) esempio - continua

Dati - i valori dei tre oggetti

Variabili - per ogni oggetto dovete decidere se portarlo con voi oppure no

Un (banale) esempio - continua

Dati - i valori dei tre oggetti

Variabili - per ogni oggetto dovete decidere se portarlo con voi oppure no

Vincolo - potete portare con voi al massimo uno dei tre oggetti

Ricerca Operativa – p. 5/64

Un (banale) esempio - continua

Dati - i valori dei tre oggetti

Variabili - per ogni oggetto dovete decidere se portarlo con voi oppure no

Vincolo - potete portare con voi al massimo uno dei tre oggetti

Obiettivo - il valore che portate con voi, da massimizzare

Un esempio più complesso

Table 1:

Farina Acqua Medicinali Utilità

TIPO I 10 10 30 14

TIPO II 30 20 10 5

TIPO III 20 40 5 4

Disp.max 5100 8000 1805

Problema: individuare quanti pacchi di ciascun tipo realizzare, tenuto conto delle disponibilità massime di

risorse, in modo da massimizzare l’utilità totale dei pacchi realizzati.

Ricerca Operativa – p. 6/64

Un esempio più complesso - continua

Dati - i valori nella tabella

Un esempio più complesso - continua

Dati - i valori nella tabella

Variabili - per ogni tipo di pacco dovete decidere quanti pacchi di quel tipo realizzare

Ricerca Operativa – p. 7/64

Un esempio più complesso - continua

Dati - i valori nella tabella

Variabili - per ogni tipo di pacco dovete decidere quanti pacchi di quel tipo realizzare

Vincoli - non superare la disponibilità massima di risorse disponibili

Un esempio più complesso - continua

Dati - i valori nella tabella

Variabili - per ogni tipo di pacco dovete decidere quanti pacchi di quel tipo realizzare

Vincoli - non superare la disponibilità massima di risorse disponibili

Obiettivo - il valore di utilità totale, da massimizzare

Ricerca Operativa – p. 7/64

La programmazione matematica

Problemi di decisione come quello precedentemente descritto possono essere riformulati in modelli di

Programmazione Matematica. Un modello di

Programmazione Matematica è una traduzione del problema di decisione in linguaggio matematico

Variabili - ad ogni variabile viene associata una variabile matematica (ad esempio x1, x2, . . . , x_n se abbiamo n

variabili)

Vincoli - I vincoli vengono espressi tramite equazioni e disequazioni in cui compaiono variabili e dati del

problema

Obiettivo - L’obiettivo viene tradotto in una funzione matematica delle variabili del problema

Prog. Matematica : il problema generico

max (o min) f(x1, . . . , x_n)

g_i(x1, . . . , x_n) ≤ 0 i ∈ I1

g_i(x1, . . . , x_n) ≥ 0 i ∈ I2

g_i(x1, . . . , x_n) = 0 i ∈ I3

Ricerca Operativa – p. 9/64

Il modello dell’esempio

Dati - i valori numerici nella tabella

Il modello dell’esempio

Dati - i valori numerici nella tabella

Variabili - x_i =quantità di pacchi di tipo i che decidete di realizzare (i = 1, 2, 3)

Ricerca Operativa – p. 10/64

Il modello dell’esempio

Dati - i valori numerici nella tabella

Variabili - x_i =quantità di pacchi di tipo i che decidete di realizzare (i = 1, 2, 3)

Vincoli -

10x1 + 30x2 + 20x3 ≤ 5100 (disp. max farina) 10x1 + 20x2 + 40x3 ≤ 8000 (disp. max acqua) 30x¹ + 10x² + 5x³ ≤ 1805 (disp. max medicinali)

x1, x2, x3 ≥ 0 quantità di pacchi non negativa

Il modello dell’esempio

Dati - i valori numerici nella tabella

Variabili - x_i =quantità di pacchi di tipo i che decidete di realizzare (i = 1, 2, 3)

Vincoli -

10x1 + 30x2 + 20x3 ≤ 5100 (disp. max farina) 10x1 + 20x2 + 40x3 ≤ 8000 (disp. max acqua) 30x¹ + 10x² + 5x³ ≤ 1805 (disp. max medicinali)

x1, x2, x3 ≥ 0 quantità di pacchi non negativa

Obiettivo -

14x1 + 5x2 + 4x3

Ricerca Operativa – p. 10/64

Modello matematico dell’esempio

max 14x1 + 5x2 + 4x3

tenuto conto che

10x1 + 30x2 + 20x3 ≤ 5100 10x1 + 20x2 + 40x3 ≤ 8000 30x1 + 10x2 + 5x3 ≤ 1805

x1, x2, x3 ≥ 0

La Programmazione Lineare

La generica forma dei problemi di Programmazione

Matematica comprende una grande varietá di problemi a cui corrispondono livelli di difficoltá molto diversi e anche tecniche risolutive molto diverse. Qui ci concentreremo su una importante sottoclasse di problemi di programmazione matematica che si incontra in molte applicazioni pratiche, la classe dei problemi di Programmazione Lineare (abbreviata

con PL nel seguito).

max (o min) Pn

j=1 c_jx_j Pn

j=1 a_ijx_j ≤ b_i i ∈ I1

Pn

j=1 a_ijx_j ≥ bi i ∈ I² Pn

j=1 a_ijx_j = b_i i ∈ I³

Ricerca Operativa – p. 12/64

Caratteristiche dei modelli di PL

Proporzionalit ´a Il contributo di ogni variabile x_j

nell’obiettivo e nei vincoli é direttamente proporzionale al valore della variabile.

Caratteristiche dei modelli di PL

Proporzionalit ´a Il contributo di ogni variabile x_j

nell’obiettivo e nei vincoli é direttamente proporzionale al valore della variabile.

Additivit ´a I contributi delle diverse variabili si sommano tra loro sia nell’obiettivo che nei vincoli

Ricerca Operativa – p. 13/64

Caratteristiche dei modelli di PL

Proporzionalit ´a Il contributo di ogni variabile x_j

nell’obiettivo e nei vincoli é direttamente proporzionale al valore della variabile.

Additivit ´a I contributi delle diverse variabili si sommano tra loro sia nell’obiettivo che nei vincoli

Continuit ´a Le variabili x_j possono assumere tutti i valori reali.

Importanza della PL

I programmi lineari sono molto importanti per almeno due ragioni:

molti problemi reali (tra cui, come vedremo fra breve, quello introdotto in precedenza) hanno come modello matematico proprio un programma lineare;

Ricerca Operativa – p. 14/64

Importanza della PL

I programmi lineari sono molto importanti per almeno due ragioni:

molti problemi reali (tra cui, come vedremo fra breve, quello introdotto in precedenza) hanno come modello matematico proprio un programma lineare;

sono più semplici da risolvere rispetto ad altri modelli dove compaiono termini non lineari. Per i programmi lineari esistono delle procedure molto efficienti di

risoluzione (come l’algoritmo del simplesso che descriveremo in seguito).

I problemi di PL in forma canonica

In forma scalare:

max Pn

j=1 c_jx_j Pn

j=1 a_ijx_j ≤ b_i i = 1, . . . , m x_j ≥ 0 j = 1, . . . , n

Ricerca Operativa – p. 15/64

Prodotto scalare tra vettori

Vettore di dimensione n

p = (p1 · · · p_n) Dato un altro vettore di dimensione n

q = (q1 · · · q_n)

Il prodotto scalare tra i due vettori è un valore scalare:

pq =

Xn j=1

p_jq_j

Esempio:

p = (2 3 6) q = (3 8 7) pq = 2 ∗ 3 + 3 ∗ 8 + 6 ∗ 7 = 72

Proprietà

Siano p, q1, q2 ∈ Rⁿ e α, β ∈ R. Allora:

p(αq¹ + βq²) = α(pq¹) + β(pq²)

Ricerca Operativa – p. 17/64

Proprietà

Siano p, q1, q2 ∈ Rⁿ e α, β ∈ R. Allora:

p(αq¹ + βq²) = α(pq¹) + β(pq²) Esempio:

p = (2 3 6) q1 = (1 2 5) q2 = (6 0 3) α = 2 β = 3

Proprietà

Siano p, q1, q2 ∈ Rⁿ e α, β ∈ R. Allora:

p(αq¹ + βq²) = α(pq¹) + β(pq²) Esempio:

p = (2 3 6) q1 = (1 2 5) q2 = (6 0 3) α = 2 β = 3

αq1 + βq2 = 2(1 2 5) + 3(6 0 3) = (2 4 10) + (18 0 9) = (20 4 19)

Ricerca Operativa – p. 17/64

Proprietà

Siano p, q1, q2 ∈ Rⁿ e α, β ∈ R. Allora:

p(αq¹ + βq²) = α(pq¹) + β(pq²) Esempio:

p = (2 3 6) q1 = (1 2 5) q2 = (6 0 3) α = 2 β = 3

αq1 + βq2 = 2(1 2 5) + 3(6 0 3) = (2 4 10) + (18 0 9) = (20 4 19)

p(αq1 + βq2) = 2 ∗ 20 + 3 ∗ 4 + 6 ∗ 19 = 166

Proprietà

Siano p, q1, q2 ∈ Rⁿ e α, β ∈ R. Allora:

p(αq¹ + βq²) = α(pq¹) + β(pq²) Esempio:

p = (2 3 6) q1 = (1 2 5) q2 = (6 0 3) α = 2 β = 3

αq1 + βq2 = 2(1 2 5) + 3(6 0 3) = (2 4 10) + (18 0 9) = (20 4 19)

p(αq1 + βq2) = 2 ∗ 20 + 3 ∗ 4 + 6 ∗ 19 = 166

pq1 = 2 ∗ 1 + 3 ∗ 2 + 6 ∗ 5 = 38 pq2 = 2 ∗ 6 + 3 ∗ 0 + 6 ∗ 3 = 30

Ricerca Operativa – p. 17/64

Proprietà

Siano p, q1, q2 ∈ Rⁿ e α, β ∈ R. Allora:

p(αq¹ + βq²) = α(pq¹) + β(pq²) Esempio:

p = (2 3 6) q1 = (1 2 5) q2 = (6 0 3) α = 2 β = 3

αq1 + βq2 = 2(1 2 5) + 3(6 0 3) = (2 4 10) + (18 0 9) = (20 4 19)

p(αq1 + βq2) = 2 ∗ 20 + 3 ∗ 4 + 6 ∗ 19 = 166

pq1 = 2 ∗ 1 + 3 ∗ 2 + 6 ∗ 5 = 38 pq2 = 2 ∗ 6 + 3 ∗ 0 + 6 ∗ 3 = 30

Prodotto matrice-vettore

Data una matrice A di ordine m × n (m righe e n colonne)





a11 . . . a1n

... ... ... a_m1 . . . a_mn





ed un vettore p di dimensione n

p = (p1 · · · p_n)

Il prodotto matrice-vettore è un vettore di dimensione m la cui componente i è il prodotto scalare tra la i-esima riga di A e il vettore p:

Xn j=1

a_ijp_j

Ricerca Operativa – p. 18/64

Prodotto vettore-matrice

Data una matrice A di ordine m × n (m righe e n colonne)





a11 . . . a1n

... ... ... a_m1 . . . a_mn





ed un vettore q di dimensione m

q = (q1 · · · q_m)

Il prodotto vettore-matrice è un vettore di dimensione n la cui componente j è il prodotto scalare tra la j-esima

colonna di A e il vettore q:

Xm

a q

Esempi

A =

"

7 6 3 2 4 8

#

p = (3 8 7) q = (4 5)

Ap = (7 ∗ 3 + 6 ∗ 8 + 3 ∗ 7 2 ∗ 3 + 4 ∗ 8 + 8 ∗ 7) = (90 94) qA = (4 ∗ 7 + 5 ∗ 2 4 ∗ 6 + 5 ∗ 4 4 ∗ 3 + 5 ∗ 8) = (38 44 52)

Ricerca Operativa – p. 20/64

PL in forma canonica

Introduciamo i seguenti vettori:

c ∈ Rⁿ: vettore di dimensione n con componenti c_j, j = 1, . . . , n, ovvero:

c = (c¹ c2 · · · c_n);

PL in forma canonica

Introduciamo i seguenti vettori:

c ∈ Rⁿ: vettore di dimensione n con componenti c_j, j = 1, . . . , n, ovvero:

c = (c¹ c2 · · · c_n);

x ∈ Rⁿ: vettore di variabili di dimensione n con componenti x_j, j = 1, . . . , n, ovvero:

x = (x1 x2 · · · x_n);

Ricerca Operativa – p. 21/64

PL in forma canonica

Introduciamo i seguenti vettori:

c ∈ Rⁿ: vettore di dimensione n con componenti c_j, j = 1, . . . , n, ovvero:

c = (c¹ c2 · · · c_n);

x ∈ Rⁿ: vettore di variabili di dimensione n con componenti x_j, j = 1, . . . , n, ovvero:

x = (x1 x2 · · · x_n);

a_i ∈ Rⁿ, i = 1, . . . , m: m vettori di dimensione n con componenti a_ij, j = 1, . . . , n, ovvero:

a_i = (a_i1 a_i2 · · · a_in).

PL in forma canonica

Osservando che

cx =

Xn j=1

c_jx_j

e

a_ix =

Xn j=1

a_ijx_j

abbiamo la seguente rappresentazione vettoriale per un problema di PL in forma canonica:

max cx

a_ix ≤ b_i i = 1, . . . , m x ≥ 0

Ricerca Operativa – p. 22/64

PL in forma canonica

Si consideri la matrice A ∈ R^m×n che ha tante righe quanti sono i vincoli del problema (m) e la cui i-esima riga é il

vettore a_i e del vettore b = (b1 · · · b_m) ∈ R^m di dimensione m con componenti b_i, i = 1, . . . , m. Osservando che

Ax = (a1x, . . . , a_mx)

possiamo scrivere la rappresentazione matriciale del problema di PL in forma canonica:

max cx

Ax ≤ b x ≥ 0

Esempio degli aiuti umanitari

Il vettore c = (14 5 4)

Il vettore di variabili x = (x¹ x2 x3) I vettori a_i, i = 1, 2, 3

a1 = (10 30 20) a2 = (10 20 40) a3 = (30 10 5) Il vettore b = (5100 8000 1805)

La matrice A





10 30 20 10 20 40 30 10 5





Ricerca Operativa – p. 24/64

PL canonici ≡ PL generici

Osservazione Ogni problema di PL in forma generica può essere trasformato in uno equivalente in forma canonica.

Trasformazione da min ^a max

min cx = − max −cx

PL canonici ≡ PL generici

Osservazione Ogni problema di PL in forma generica può essere trasformato in uno equivalente in forma canonica.

Trasformazione da min ^a max

min cx = − max −cx

Trasformazione vincolo ≥ ^{in vincolo} ≤

a_ix ≥ b_i ⇔ −a_ix ≤ −b_i

Ricerca Operativa – p. 25/64

PL canonici ≡ PL generici

Osservazione Ogni problema di PL in forma generica può essere trasformato in uno equivalente in forma canonica.

Trasformazione da min ^a max

min cx = − max −cx

Trasformazione vincolo ≥ ^{in vincolo} ≤

a_ix ≥ b_i ⇔ −a_ix ≤ −b_i

Trasformazione vincolo = in due vincoli ≤

a_ix = b_i ⇔ a_ix ≤ b_i, a_ix ≥ b_i ⇔ a_ix ≤ b_i, −a_ix ≤ −b_i

PL canonici ≡ PL generici

Sostituzione variabile ≤ 0 con variabile ≥ 0 Data x_i ≤ 0, effettuare il cambio di variabile x_i = −x^′_i, dove x^′_i ≥ 0

Ricerca Operativa – p. 26/64

PL canonici ≡ PL generici

Sostituzione variabile ≤ 0 con variabile ≥ 0 Data x_i ≤ 0, effettuare il cambio di variabile x_i = −x^′_i, dove x^′_i ≥ 0

Sostituzione variabile libera in segno con due variabili ≥ 0 Data x_i libera in segno, effettuare il cambio di variabile x_i = x^′′_i − x^′_i, dove x^′_i, x^′′_i ≥ 0

Un esempio

Si trasformi il seguente problema di PL in forma generica in un problema di PL in forma canonica

min x1 + x2 + x3

x1 + 2x2 − x3 ≤ 3 x1 + 4x2 + 5x3 = 5

x1 − 2x² + x3 ≥ 3 x1 ≥ 0

x2 ≤ 0

x3 libera in segno

Ricerca Operativa – p. 27/64

Insiemi convessi

Un insieme C si dice convesso se

∀ x1, x2 ∈ C ∀ λ ∈ [0, 1] : λx1 + (1 − λ)x2 ∈ C,

ovvero se dati due punti qualsiasi in C, il segmento che li congiunge è anch’esso completamente contenuto in C.

Insiemi limitati e chiusi

Un insieme C si dice limitato se esiste una sfera di raggio finito R che lo contiene.

Un insieme C si dice chiuso se contiene la sua frontiera.

Ricerca Operativa – p. 29/64

Semispazi e semipiani

Si definisce semispazio in Rⁿ l’insieme di punti che soddisfa una disequazione lineare in Rⁿ:

Xn j=1

w_jx_j ≤ v

(in forma vettoriale: wx ≤ v).

Si definisce iperpiano in Rⁿ l’insieme di punti che soddisfa un’equazione lineare in Rⁿ:

Xn j=1

w_jx_j = v

Poliedri e politopi

Si definisce poliedro l’intersezione di un numero finito di

semispazi e/o iperpiani. Se il poliedro é limitato esso viene chiamato politopo.

Ricerca Operativa – p. 31/64

La regione ammissibile S

La regione ammissibile S_a di un problema di PL in forma canonica

S_a = {x ∈ Rⁿ : a_ix ≤ b_i, i = 1, . . . , m, x ≥ 0}.

é un poliedro.

Semispazi e iperpiani sono insiemi chiusi

L’intersezione di un numero finito di insiemi chiusi é un insieme chiuso

⇓

I poliedri (e quindi S_a) sono insiemi chiusi

Convessitá

Siano x, y ∈ S_a, ovvero

a_ix ≤ b_i i = 1, . . . , m x ≥ 0, e

a_iy ≤ b_i i = 1, . . . , m y ≥ 0.

Per ogni λ ∈ (0, 1) e per ogni i ∈ {1, . . . , m} avremo:

a_i[λx + (1 − λ)y] =

Ricerca Operativa – p. 33/64

Convessitá

Siano x, y ∈ S_a, ovvero

a_ix ≤ b_i i = 1, . . . , m x ≥ 0, e

a_iy ≤ b_i i = 1, . . . , m y ≥ 0.

Per ogni λ ∈ (0, 1) e per ogni i ∈ {1, . . . , m} avremo:

a_i[λx + (1 − λ)y] =

= λ|{z}

>0

a_ix

|{z}

≤bⁱ

+ (1 − λ)

| {z }

>0

a_iy

|{z}

≤bⁱ

≤

Convessitá

Siano x, y ∈ S_a, ovvero

a_ix ≤ b_i i = 1, . . . , m x ≥ 0, e

a_iy ≤ b_i i = 1, . . . , m y ≥ 0.

Per ogni λ ∈ (0, 1) e per ogni i ∈ {1, . . . , m} avremo:

a_i[λx + (1 − λ)y] =

= λ|{z}

>0

a_ix

|{z}

≤bⁱ

+ (1 − λ)

| {z }

>0

a_iy

|{z}

≤bⁱ

≤

λb_i + (1 − λ)b_i = b_i.

Ricerca Operativa – p. 33/64

Continua

Inoltre:

|{z}λ

>0

|{z}x

≥0

+ (1 − λ)

| {z }

>0

y

|{z}

≥0

≥ 0.

Quindi:

Continua

Inoltre:

|{z}λ

>0

|{z}x

≥0

+ (1 − λ)

| {z }

>0

y

|{z}

≥0

≥ 0.

Quindi:

λx + (1 − λ)y ∈ S_a.

Ricerca Operativa – p. 34/64

Continua

Inoltre:

|{z}λ

>0

|{z}x

≥0

+ (1 − λ)

| {z }

>0

y

|{z}

≥0

≥ 0.

Quindi:

λx + (1 − λ)y ∈ S_a.

⇓

La regione ammissibile S_a é un insieme convesso.

Limitatezza e illimitatezza

La regione ammissibile S_a puó essere:

= ∅

max x1 + x2

x1 ≤ −1 x1 + x2 ≤ 1

x1, x2 ≥ 0

Ricerca Operativa – p. 35/64

Limitatezza e illimitatezza

La regione ammissibile S_a puó essere:

= ∅

max x1 + x2

x1 ≤ −1 x1 + x2 ≤ 1

x1, x2 ≥ 0 un poliedro limitato (politopo)

max x1 + x2

x1 + x2 ≤ 1 x1, x2 ≥ 0

Continua

un poliedro illimitato

max x1 + x2

x1 − x2 ≤ 0 x1, x2 ≥ 0

Ricerca Operativa – p. 36/64

Ricapitolando ...

... la regione ammissibile S_a di un problema di PL é un poliedro e come tale é un iniseme chiuso e convesso.

Inoltre, puó essere un insieme vuoto, un insieme limitato (politopo) oppure un insieme illimitato.

Vertici di S

Si definisce vertice di S_a un punto x ∈ S_a tale che non esistono due punti distinti x1, x2 ∈ S_a, x1 6= x2, tali che

x = 1

2x1 + 1

2x2.

ovvero x é il punto medio del segmento che congiunge x1 e x2.

Ricerca Operativa – p. 38/64

Alcuni risultati

Teorema 1 Dato un problema di PL in forma canonica, se S_a 6= ∅, allora S_a contiene almeno un vertice.

Alcuni risultati

Teorema 2 Dato un problema di PL in forma canonica, se S_a 6= ∅, allora S_a contiene almeno un vertice.

Osservazione 2 S_a ha sempre un numero finito di vertici.

Ricerca Operativa – p. 39/64

Raggi

Nel caso S_a sia un poliedro illimitato possiamo anche introdurre le definizioni di raggio e raggio estremo.

Si definisce raggio di S_a un vettore r tale che

∀ x⁰ ∈ Sa ∀ λ ≥ 0 : x0 + λr ∈ S_a, cioé la semiretta con origine in x0 e direzione r é

completamente contenuta in S_a per qualsiasi punto x0 ∈ S_a.

Raggi estremi

Un raggio r di S_a si definisce raggio estremo di S_a se non esistono altri due raggi r1 e r2 di S_a con direzioni distinte, ovvero

r1 6= µr2 ∀ µ ∈ R, tali che

r = 1

2r1 + 1 2r2.

Osservazione 3 S_a ha sempre un numero finito di raggi estremi.

Ricerca Operativa – p. 41/64

Teorema di rappresentazione di S

Teorema 3 Sia dato un problema di PL in forma canonica con S_a 6= ∅. Siano v1, . . . , v_k i vertici di S_a e, nel caso in cui S_a sia un poliedro illimitato, siano r1, . . . , r_h i raggi estremi di S_a. Allora

x ∈ S_a se e solo se

∃ λ1, . . . , λ_k ≥ 0,

Xk i=1

λ_i = 1, ∃ µ1, . . . , µ_h ≥ 0

tali che

x =

Xk i=1

λ_iv_i +

Xh j=1

µ_jr_j.

Ovvero ...

... i punti in S_a sono tutti e soli i punti ottenibili come somma di

una combinazione convessa dei vertici di S_a

una combinazione lineare con coefficienti non negativi dei raggi estremi di S_a

Quindi un numero finito di oggetti (vertici e raggi estremi) mi permettono di rappresentare tutto l’insieme S_a.

Ricerca Operativa – p. 43/64

L’insieme delle soluzioni ottime S

Insieme soluzioni ottime

S_ott = {x^∗ ∈ S_a : cx^∗ ≥ cx ∀ x ∈ S_a}, S_ott ⊆ S_a, quindi S_a = ∅ ⇒ S_ott = ∅.

Una, nessuna, infinite

Osservazione 4 Se S_ott é un insieme finito e non vuoto, S_ott contiene un solo punto.

Dimostrazione Per assurdo sia S_ott un insieme finito e

contenga piú di un punto. Siano x1, x2 ∈ S_ott, x1 6= x², due punti distinti di S_ott.

Ricerca Operativa – p. 45/64

Continua

Per l’ottimalitá di x1 e x2 si deve avere cx1 = cx2.

Continua

Per l’ottimalitá di x1 e x2 si deve avere cx1 = cx2. Per la convessitá di S_a e x1, x2 ∈ S_a:

λx1 + (1 − λ)x2 ∈ Sa ∀ λ ∈ (0, 1),

Ricerca Operativa – p. 46/64

Continua

Per l’ottimalitá di x1 e x2 si deve avere cx1 = cx2. Per la convessitá di S_a e x1, x2 ∈ S_a:

λx1 + (1 − λ)x2 ∈ Sa ∀ λ ∈ (0, 1),

Per la linearitá della funzione obiettivo ∀ λ ∈ (0, 1):

c[λx1 + (1 − λ)x2] = λcx1 + (1 − λ)cx2 = λcx1 + (1 − λ)cx1 = cx1.

Continua

Per l’ottimalitá di x1 e x2 si deve avere cx1 = cx2. Per la convessitá di S_a e x1, x2 ∈ S_a:

λx1 + (1 − λ)x2 ∈ Sa ∀ λ ∈ (0, 1),

Per la linearitá della funzione obiettivo ∀ λ ∈ (0, 1):

c[λx1 + (1 − λ)x2] = λcx1 + (1 − λ)cx2 = λcx1 + (1 − λ)cx1 = cx1. Quindi:

λx1 + (1 − λ)x2 ∈ S_ott ∀ λ ∈ (0, 1)

cioé tutto il segmento che congiunge x1 e x2 é contenuto in S_ott, il che contraddice la finitezza dell’insieme S_ott.

Ricerca Operativa – p. 46/64

Le diverse forme possibili di S

Caso 1 S_a = ∅ ⇒ S_ott = ∅.

Le diverse forme possibili di S

Caso 1 S_a = ∅ ⇒ S_ott = ∅.

Caso 2 S_a 6= ∅ e politopo.

Politopo é insieme chiuso e limitato, funzione obiettivo é lineare e quindi continua ⇒ (Teorema di Weierstrass) S_ott 6= ∅.

Sono possibili due sottocasi.

Ricerca Operativa – p. 47/64

Le diverse forme possibili di S

Caso 1 S_a = ∅ ⇒ S_ott = ∅.

Caso 2 S_a 6= ∅ e politopo.

Politopo é insieme chiuso e limitato, funzione obiettivo é lineare e quindi continua ⇒ (Teorema di Weierstrass) S_ott 6= ∅.

Sono possibili due sottocasi.

Caso 2.1 S_ott é costituito da un solo punto.

max 2x1 + x2

x1 + x2 ≤ 1 x1, x2 ≥ 0

Continua

Caso 2.2 S_ott é costituito da un insieme infinito e limitato di punti.

max x1 + x2

x1 + x2 ≤ 1 x1, x2 ≥ 0

Ricerca Operativa – p. 48/64

Continua

Caso 3 S_a 6= ∅ e poliedro illimitato. Sono possibili quattro sottocasi.

Caso 3.1 S_ott = ∅ in quanto l’obiettivo é illimitato, ovvero esiste una sequenza infinita di punti {x_k} di S_a lungo cui la funzione obiettivo cresce a +∞. Formalmente:

∃ {x_k} : x_k ∈ S_a ∀ k e cx_k → +∞ k → +∞.

max x1 + x2

−x1 + x2 ≤ 0 x1 − x² ≤ 1

x2 ≥ 1 x1, x2 ≥ 0

Continua

Caso 3.2 S_ott é costituito da un solo punto.

max −x¹

−x1 + x2 ≤ 0 x1 − x2 ≤ 1

x2 ≥ 1 x1, x2 ≥ 0

Ricerca Operativa – p. 50/64

Continua

Caso 3.3 S_ott é costituito da un insieme infinito e limitato di punti.

max −x²

−x1 + x2 ≤ 0 x1 − x2 ≤ 1

x2 ≥ 1 x1, x2 ≥ 0

Continua

Caso 3.4 S_ott é costituito da un insieme infinito e illimitato di punti.

max x1 − x²

−x1 + x2 ≤ 0 x1 − x2 ≤ 1

x2 ≥ 1 x1, x2 ≥ 0

Ricerca Operativa – p. 52/64

Un lemma

Lemma 1 Dato un problema di PL in forma canonica, se S_ott 6= ∅, allora per ogni raggio estremo r di S_a si ha:

cr ≤ 0.

Dimostrazione

Per assurdo supponiamo esista un raggio estremo r tale che

cr > 0

Ricerca Operativa – p. 54/64

Dimostrazione

Per assurdo supponiamo esista un raggio estremo r tale che

cr > 0 S_ott 6= ∅ ⇒ S_a 6= ∅.

Dimostrazione

Per assurdo supponiamo esista un raggio estremo r tale che

cr > 0 S_ott 6= ∅ ⇒ S_a 6= ∅.

Sia x0 ∈ S_a. Per definizione di raggio avremo che

∀ λ ≥ 0 : x0 + λr ∈ S_a.

Ricerca Operativa – p. 54/64

Dimostrazione

Per assurdo supponiamo esista un raggio estremo r tale che

cr > 0 S_ott 6= ∅ ⇒ S_a 6= ∅.

Sia x0 ∈ S_a. Per definizione di raggio avremo che

∀ λ ≥ 0 : x0 + λr ∈ S_a. Valore funzione obiettivo in punti x0 + λr:

c(x0 + λr) = cx0 + λ cr

|{z}

>0

|{z}→

λ→+∞

+∞