Appunti per il corso di Ricerca Operativa 1

Appunti per il corso di Ricerca Operativa 1

Capitolo 1

Introduzione

La prima domanda da porsi riguarda gli scopi che si prefigge la Ricerca Operativa. Possiamo definirla come uno strumento per prendere delle deci- sioni che siano le migliori possibili secondo un criterio dato. Ogni volta che dobbiamo prendere una decisione entrano in gioco le seguenti componenti:

DATI , che rappresentano tutti i valori noti a priori.

VARIABILI , che sono le entit`a controllate dal decisore; al variare di esse varia anche il valore del criterio e tra tutti i possibili valori che possono assumere si devono scegliere quelli che forniscono il miglior valore possibile del criterio.

VINCOLI , che limitano le possibili scelte del decisore (i possibili valori delle variabili).

OBIETTIVO , che coincide con il criterio fissato per confrontare le di- verse possibili scelte del decisore.

Facciamo un esempio molto semplice di decisione. Dovete uscire di casa e potete prendere con voi al massimo uno dei seguenti tre oggetti: un libro che vale 10 Euro, una macchina fotografica che vale 100 Euro ed una borsa da 25 Euro. Dovete decidere quale oggetto portare con voi, tenuto conto che vi interessa prendere un oggetto di valore massimo. L’esempio `e molto banale e non c’`e bisogno di scomodare la Ricerca Operativa per capire che occorre prendere la macchina fotografica. Tuttavia in esso sono gi`a presenti tutte le componenti tipiche di una decisione:

DATI : sono i valori dei tre oggetti.

Tabella 1.1:

Farina Acqua Medicinali

TIPO I 10 10 30

TIPO II 30 20 10

TIPO III 20 40 5

Tabella 1.2:

TIPO I 14 TIPO II 5 TIPO III 4

VARIABILI : per ogni oggetto il decisore (cio´e voi) deve decidere se prenderlo oppure no.

VINCOLI : in questo caso `e presente il vincolo che pu`o essere preso al massimo un oggetto.

OBIETTIVO : il criterio di scelta `e rappresentato dal valore e quindi l’obiettivo `e quello di prendere l’oggetto di valore massimo.

Nel nostro esempio `e molto semplice prendere la decisione migliore. Vedre- mo per`o che in molte situazioni non `e per nulla chiaro, a prima vista, capire qual `e la decisione migliore. Ad esempio si consideri il seguente problema.

Supponiamo di dover preparare dei pacchi per inviare degli aiuti. ´E pos- sibile realizzare tre diversi tipi di pacchi con diversi contenuti di sacchetti di farina, bottiglie d’acqua e medicinali. Pi`u precisamente la Tabella 1.1 specifica i contenuti di ogni tipo di pacco. ´E stato inoltre assegnato un indice di utilit`a per un’unit`a di ogni tipo di pacco. Gli indici sono riportati nella Tabella 1.2. Infine `e noto che la disponibilit`a di sacchetti di farina, bottiglie d’acqua e medicinali `e limitata. Pi`u precisamente il numero mas- simo disponibile di farina, acqua e medicinali `e riportata nella Tabella 1.3.

La domanda che ci si pone `e la seguente: quanti pacchi di ciascun tipo oc- corre preparare se si vuole rendere massimo l’indice di utilit`a complessivo?

Rispetto all’esempio iniziale `e ora pi`u difficile stabilire qual `e la cosa giusta

Tabella 1.3:

farina 5100 acqua 8000 medicinali 1805

da fare. Potrei realizzare solo pacchi del tipo I. In tal caso ne potrei rea- lizzare al massimo 60 per il limite di disponibilit`a sui medicinali. L’utilit`a complessiva risulterebbe pari a 60*14=840. Potrei realizzare solo pacchi del tipo II. In tal caso ne potrei realizzare al massimo 170 per il limite di disponibilit`a sui sacchetti di farina. L’utilit`a complessiva risulterebbe pari a 170*5=850. Infine, potrei realizzare solo pacchi del tipo III. In tal caso ne potrei realizzare al massimo 200 per il limite di disponibilit`a sulle bot- tiglie d’acqua. L’utilit`a complessiva risulterebbe pari a 200*4=800. Delle tre possibili soluzioni la migliore `e la seconda. Ma queste tre decisioni non coprono tutti i casi possibili. Infatti, potrei scegliere di fare un po’ di pacchi di ciascun tipo. Quindi, a differenza dell’esempio iniziale non `e per nulla immediato scegliere la decisione migliore.

Un modo per risolvere problemi di decisione complessi ´e quello di rifor- mularli come problemi di Programmazione Matematica ed utilizzare quindi delle tecniche di risoluzione apposite per questi problemi. Come vedremo questo sar´a proprio l’approccio che potremo utilizzare per il nostro esempio.

Nei problemi di Programmazione Matematica sono date n variabili di deci- sione x1, . . . , xn, l’obiettivo ´e rappresentato da una funzione f (x1, . . . , xn) delle n variabili, detta appunto funzione obiettivo, mentre i vincoli sono rappresentati da disequazioni o equazioni di questo tipo:

gi(x1, . . . , xn)≤ (o ≥ o =) 0.

Quindi la generica forma di un problema di Programmazione Matematica

´e la seguente:

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

gi(x1, . . . , xn)≤ 0 i ∈ I¹ gi(x1, . . . , xn)≥ 0 i ∈ I² gi(x1, . . . , xn) = 0 i∈ I³

L’insieme dei punti che soddisfano tutti i vincoli viene chiamato regione ammissibile del problema e nel seguito verr´a indicato con Sa. Abbiamo quindi:

Sa={ (x¹, . . . , xn) : gi(x1, . . . , xn)≤ 0, ∀ i ∈ I¹ gi(x1, . . . , xn)≥ 0, ∀ i ∈ I² gi(x1, . . . , xn) = 0, ∀ i ∈ I³}

Risolvere il problema di Programmazione Matematica vuol dire determinare un punto (x^∗₁, . . . , x^∗_n)∈ Sa, che verr´a detto soluzione ottima del problema, tale che

f (x^∗₁, . . . , x^∗_n)≤ f(x¹, . . . , xn) ∀ (x¹, . . . , xn)∈ S^a,

se il problema ´e di minimo, oppure

f (x^∗₁, . . . , x^∗_n)≥ f(x¹, . . . , xn) ∀ (x¹, . . . , xn)∈ Sa,

se il problema ´e di massimo. La Programmazione Matematica comprende un grande numero di problemi. Tra questi quelli di Programmazione Li- neare (in cui, come vedremo, rientra anche il nostro esempio precedente), della quale ci occuperemo ampiamente nei capitoli successivi.

Capitolo 2

La Programmazione Lineare

La generica forma dei problemi di Programmazione Matematica comprende una grande variet´a di problemi a cui corrispondono livelli di difficolt´a 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). Nei problemi di PL la funzione obiettivo ´e una funzione lineare, ovvero:

f (x1, . . . , xn) = Xn j=1

cjxj

e lo stesso vale per i vincoli, che avranno la seguente forma:

Xn j=1

aijxj≤ (o ≥ o =) bⁱ.

Quindi, il generico problema di PL avr´a la seguente forma:

max (o min) Pn j=1cjxj

Pn

j=1aijxj ≤ bⁱ i∈ I¹ Pn

j=1aijxj ≥ bi i∈ I² Pn

j=1aijxj = bi i∈ I³

Da questa formulazione possiamo notare quali sono le tre principali carat- teristiche dei problemi di PL.

Proporzionalit´a Il contributo di ogni variabile xjnell’obiettivo e nei vin- coli ´e direttamente proporzionale al valore della variabile. Infatti, nell’obiettivo il contributo ´e pari a cjxj mentre nei vincoli ´e aijxj. Additivit´a I contributi delle diverse variabili si sommano tra loro sia nel-

l’obiettivo che nei vincoli (si vedano le sommatorie che definiscono obiettivo e vincoli).

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

I programmi lineari sono molto importanti per almeno due ragioni:

1. molti problemi reali (tra cui, come vedremo fra breve, quello intro- dotto in precedenza) hanno come modello matematico proprio un programma lineare;

2. sono pi`u semplici da risolvere rispetto ad altri modelli dove compaiono termini non lineari. Per i programmi lineari esistono delle procedu- re molto efficienti di risoluzione (come l’algoritmo del simplesso che descriveremo in seguito).

Pi´u avanti vedremo un’altra importante classe di problemi, quelli di Pro- grammazione Lineare Intera, che si differenziano da quelli di PL solo per la rimozione della propriet´a di continuit´a (in essi le variabili potranno assumere solo valori interi).

2.1 Formulazione dell’esempio degli aiuti uma- nitari come problema di PL

Cominciamo con l’individuare le quattro componenti della decisione.

DATI : sono i valori riportati nelle tre tabelle 1.1-1.3.

VARIABILI : per ogni tipo di pacco il decisore deve decidere quanti pacchi di quel tipo realizzare.

VINCOLI : in questo caso sono presenti i vincoli sulla disponibilit`a di farina, acqua e medicinali.

OBIETTIVO : il criterio di scelta `e rappresentato dall’utilit`a complessiva dei pacchi, che si vuole massimizzare.

Un problema di questo tipo viene chiamato problema con vincoli di risorse.

In tali problemi vi sono sempre delle risorse (in questo caso farina, acqua e medicinali) che vengono in qualche modo utilizzate (qui per fare i pacchi)

e delle quali si ha una disponibilit`a limitata.

Vediamo allora di procedere alla formulazione di un modello matematico per questo problema. Indichiamo con:

x1 il numero di pacchi di tipo I da realizzare.

x2 il numero di pacchi di tipo II da realizzare.

x3 il numero di pacchi di tipo III da realizzare.

Queste sono le tre variabili del problema. Ora dobbiamo tradurre i vincoli e l’obiettivo in formule matematiche. Abbiamo un vincolo sulla disponibilit`a di sacchetti di farina. Come si pu`o tradurre in linguaggio matematico? Un pacco di tipo I contiene 10 sacchetti di farina. Quindi x1 pacchi di tipo I richiedono

10x1

sacchetti di farina. Analogamente, un pacco di tipo II contiene 30 sacchetti di farina e quindi x2 pacchi richiedono

30x2

sacchetti di farina. Infine, un pacco di tipo III contiene 20 sacchetti di farina e quindi x3 pacchi richiedono

20x3

sacchetti di farina. La somma di questi tre valori restituisce il numero complessivo di sacchetti utilizzati. Pi`u precisamente, il valore

10x1+ 30x2+ 20x3

rappresenta il numero complessivo di sacchetti di farina utilizzati in corri- spondenza dei valori x1, x2 e x3 delle variabili. Noi sappiamo di non poter utilizzare pi`u di 5100 sacchetti di farina e tale vincolo si traduce quindi nella seguente disequazione

10x1+ 30x2+ 20x3≤ 5100,

che `e proprio la traduzione in linguaggio matematico del vincolo sulla dispo- nibilit`a di sacchetti di farina. In modo completamente analogo si procede per tradurre i vincoli sulla disponibilit`a di bottiglie d’acqua

10x1+ 20x2+ 40x3≤ 8000, e sulla disponibilit`a di medicinali

30x1+ 10x2+ 5x3≤ 1805.

Per essere precisi a questi tre vincoli ne dobbiamo aggiungere altri tre che non abbiamo specificato in precedenza perch´e banali: le quantit`a di pacchi di ciascun tipo non possono essere negative (per esempio, non ha senso parlare di -5 pacchi di tipo I). Mentre in una descrizione a voce del problema questo tipo di vincoli `e del tutto scontato, da un punto di vista matematico non lo ´e e tali vincoli sono essenziali nella definizione del modello. In linguaggio matematico essi si esprimono semplicemente in questo modo:

x1≥ 0 x²≥ 0 x³≥ 0.

L’insieme dei valori che si possono assegnare a x1, x2, x3 senza violare i vincoli introdotti rappresenta l’insieme ammissibile Sa del problema. Ad esempio, x1 = 20, x2 = 20, x3 = 30 `e una soluzione ammissibile, mentre x1 = 50, x2 = 60, x3 = 40 non lo `e (viola il vincolo sulla disponibilit`a di medicinali) e non lo `e neppure x1=−2, x² = 20, x3 = 40 (viola il vincolo di non negativit`a del numero di pacchi di tipo I).

Resta da definire l’obiettivo del problema. Un pacco di tipo I ha utilit`a pari a 14, quindi x1 pacchi hanno utilit`a pari a

14x1.

In modo del tutto analogo si vede che x2pacchi di tipo II hanno utilit`a pari a

5x2

e x3 pacchi di tipo III hanno utilit`a pari a 4x3.

Quindi, sommando le utilit`a di ciascun tipo di pacco si ottiene l’utilit`a complessiva pari a

14x1+ 5x2+ 4x3. Il nostro obiettivo `e massimizzare tale valore.

Riassumendo, il modello matematico del nostro problema `e il seguente:

massimizzare 14x1+ 5x2+ 4x3

tenuto conto che

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

x1≥ 0 x2≥ 0 x3≥ 0

Come si vede, abbiamo a che fare con un problema di PL. Per completezza notiamo che ulteriori vincoli che si potrebbero introdurre sono quelli di interezza delle variabili x1, x2, x3: il numero di pacchi realizzati di ciascun tipo deve essere un valore intero. In tal caso ci troveremmo di fronte ad un problema di Programmazione Lineare Intera (si veda il capitolo 6). Qui per´o tralasceremo tali vincoli, ammettendo quindi anche la realizzazione di un numero frazionario di pacchi di ciascun tipo.

2.2 I problemi di PL in forma canonica

Un tipo particolare di problemi di PL `e rappresentato dai problemi di PL in forma canonica, in cui l’obiettivo `e sempre da massimizzare, i vincoli sono tutti di ≤ e le variabili sono tutte vincolate ad assumere valori non negativi, cio`e

max Pn

j=1cjxj

Pn

j=1aijxj≤ bi i = 1, . . . , m xj≥ 0 j = 1, . . . , n

Possiamo anche scrivere il problema di PL in forma canonica in forma pi´u compatta introducendo vettori e matrici. Qui e nel seguito indicheremo i vettori con lettere minuscole in grassetto e le matrici con lettere maiuscole in grassetto. Indichiamo con:

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

c= (c1 c2 · · · cⁿ);

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

x= (x1 x2 · · · xⁿ);

• aⁱ∈ Rⁿ, i = 1, . . . , m, gli m vettori di dimensione n con componenti aij, j = 1, . . . , n, ovvero:

ai = (ai1 ai2 · · · aⁱⁿ).

Recuperando alcune cose di algebra lineare, ricordiamo che dati due vettori della stessa dimensione n, indicati con p = (p1 · · · pⁿ) e q = (q1 · · · qⁿ),

il prodotto scalare tra questi vettori `e definito come somma dei prodotti delle singole componenti, ovvero:

pq= Xn j=1

pjqj.

Un’importante propriet`a del prodotto scalare `e la seguente. Siano p, q1, q2∈ Rⁿ e α, β∈ R. Allora:

p(αq1+ βq2) = α(pq1) + β(pq2)

Possiamo anche generalizzare questa propriet`a. Infatti, dati i vettori p, q1, q2, . . . , qt∈ Rⁿ e gli scalari α1, α2, . . . , αt∈ R, si ha che

p[α1q1+ α2q2+· · · + α^tqt] = p

" _t X

i=1

αiqi

#

= Xt

i=1

αi(pqi).

Si ricordano infine le definizioni di prodotto di matrice per vettore e di vettore per matrice. Data una matrice A di ordine m× n (m righe e n colonne)





a11 . . . a1n

... ... ... am1 . . . amn





ed un vettore p di dimensione n

p= (p1 · · · pⁿ)

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

Xn j=1

aijpj

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





a11 . . . a1n

... ... ... am1 . . . amn





ed un vettore q di dimensione m

q = (q1 · · · q^m)

Il prodotto vettore-matrice `e un vettore di dimensione n la cui componente j `e il prodotto scalare tra la j-esima colonna di A e il vettore q:

Xm i=1

aijqi

Tenuto conto di tutto questo possiamo riscrivere il problema di PL in forma canonica nella seguente forma:

max cx

aix≤ bⁱ i = 1, . . . , m x≥ 0

Possiamo ulteriormente compattare la rappresentazione con l’introduzione della matrice A∈ R^m×nche ha tante righe quanti sono i vincoli del proble- ma (m) e la cui i-esima riga ´e il vettore ai e del vettore b = (b1 · · · bm)∈ R^mdi dimensione m con componenti bi, i = 1, . . . , m. Con l’introduzione di questi possiamo riscrivere il problema di PL in forma canonica nel seguente modo:

max cx

Ax≤ b x≥ 0

Se apparentemente i problemi di PL in forma canonica rappresentano un sottinsieme dei problemi di PL, `e in realt`a possibile dimostrare che ogni problema di PL ha un problema di PL in forma canonica ad esso equivalente, come dimostra la seguente osservazione.

Osservazione 1 Dato un problema di PL, esiste un problema di PL in forma canonica ad esso equivalente.

DimostrazioneSi pu`o notare che

1. ogni problema di minimo pu`o essere trasformato in un problema di massimo sfruttando la seguente relazione

min cx =− max −cx

2. ogni vincolo di≥ pu`o essere trasformato in un vincolo di ≤ nel modo seguente

aix≥ bi ⇒ −aix≤ −bi

3. ogni vincolo di = pu`o essere trasformato in due vincoli di≤ nel modo seguente

a_ix= bi ⇒ aix≤ bi, −aix≤ −bi

4. se abbiamo una variabile xj ≤ 0 possiamo sostituirla nei vincoli e nell’obiettivo con la variabile

x^′_j=−x^j ≥ 0

5. se abbiamo una variabile xj libera in segno, possiamo sostituirla nei vincoli e nell’obiettivo con una differenza di variabili non negative

xj = x^′_j− x^′′j x^′_j, x^′′_j ≥ 0

Come esercizio, si trasformi il seguente problema di PL in un problema di PL in forma canonica

min x1+ x2+ x3

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

x1− 2x²+ x3≥ 3 x1≥ 0 x2≤ 0 x3 libera in segno

Il risultato appena citato ci consente di concentrare la nostra attenzione sui soli problemi di PL in forma canonica.

2.3 La regione ammissibile S_a

La regione ammissibile di un problema di PL in forma canonica ´e definita nel modo seguente:

Sa={x ∈ Rⁿ: aix≤ bⁱ, i = 1, . . . , m, x≥ 0}.

Dobbiamo ora introdurre alcune definizioni.

Definizione 1 Un insieme C⊆ Rⁿ si dice convesso se

∀ x¹, x2∈ C ∀ λ ∈ [0, 1] : λx¹+ (1− λ)x²∈ C,

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

Definizione 2 Un insieme C si dice limitato se esiste un R > 0 tale che

∀ x ∈ C : kxk ≤ R,

ovvero l’insieme C `e contenuto in una sfera di raggio R.

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

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

Xn j=1

wjxj≤ 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

wjxj= v

(in forma vettoriale: wx = v).

Definizione 5 Si definisce poliedro l’intersezione di un numero finito di semispazi e/o iperpiani. Se il poliedro ´e limitato esso viene chiamato poli- topo.

Questo ci dice che la regione ammissibile Sa di un problema di PL ´e un poliedro. Si noti che ogni iperpiano e ogni semispazio sono insiemi chiusi.

Poich´e un intersezione di un numero finito di insiemi chiusi ´e un insieme chiuso, ogni poliedro ´e un insieme chiuso. In problemi con 2 sole variabili `e possibile rappresentare graficamente le regioni ammissibili Sa. Nel seguente esempio, la rappresentazione grafica ci consentir´a di visualizzare le diverse forme possibili di Sa.

Esempio 1 Rappresentare graficamente le regioni ammissibili Sa per i se- guenti tre problemi e constatare che sono altrettanti esempi di regione am- missibile vuota, di politopo e di poliedro illimitato.

max x1+ x2

x1≤ −1 x1+ x2≤ 1

x1, x2≥ 0

max x1+ x2

x1+ x2≤ 1 x1, x2≥ 0

max x1+ x2

x1− x²≤ 0 x1, x2≥ 0

La seguente osservazione ci mostra anche che la regione ammissibile Sadi un problema in forma canonica ´e un insieme convesso (il risultato ´e facilmente estendibile ad ogni poliedro).

Osservazione 2 La regione ammissibile Sa di un problema di PL in forma canonica ´e un insieme convesso.

DimostrazioneSiano dati due generici punti x1, x2∈ S^a. Si avr´a:

a_ix1≤ bi i = 1, . . . , m x1≥ 0, e

aix2≤ bⁱ i = 1, . . . , m x2≥ 0.

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

ai[λx1+ (1− λ)x²] = λaix1+ (1− λ)aⁱx2≤ λbⁱ+ (1− λ)bⁱ= bi, e

|{z}λ

>0

x1

|{z}

≥0

+ (1− λ)

| {z }

>0

x2

|{z}

≥0

≥ 0,

da cui

λx1+ (1− λ)x²∈ S^a. Ci´o equivale a dire che Sa ´e un insieme convesso.

Vediamo ora di introdurre la definizione di alcuni particolari punti di Sa, i vertici di Sa.

Definizione 6 Si definisce vertice di Sa un punto x ∈ S^a tale che non esistono due punti distinti x1, x2∈ S^a, x16= x², tali che

x=1 2x1+1

2x2.

In problemi con 2 variabili i vertici sono facilmente identificabili, coinciden- do con la usuale definizione di vertice di una figura piana.

Esempio 2 Si verifichi che, dato il problema max x1+ x2

x1+ x2≤ 1

−2x¹− 2x²≤ −2 x1, x2≥ 0

il punto (1/2, 1/2) non `e un vertice di Sa mentre lo `e il punto (1, 0) Un primo importante teorema per la PL ´e il seguente.

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

Si pu´o inoltre dimostrare la seguente osservazione.

Osservazione 3 Sa ha sempre un numero finito di vertici.

Nel caso Sa sia un poliedro illimitato possiamo anche introdurre le defini- zioni di raggio e raggio estremo.

Definizione 7 Si definisce raggio di Sa un vettore r6= 0 tale che

∀ x⁰∈ Sa ∀ λ ≥ 0 : x0+ λr∈ Sa,

cio´e la semiretta con origine in x0e direzione r ´e completamente contenuta in Sa per qualsiasi punto x0 ∈ Sa. Un raggio r di Sa si definisce raggio estremo di Sa se non esistono altri due raggi r1 e r2 di Sa con direzioni distinte, ovvero

r16= µr² ∀ µ ∈ R, tali che

r=1 2r1+1

2r2.

Ovviamente i politopi non hanno alcun raggio. Infatti l’esistenza di un raggio implica che Sa contenga almeno una semiretta, che ´e un insieme illimitato, mentre i politopi sono, per definizione, insiemi limitati. Anche in questo caso in problemi con 2 sole variabili ´e facile riconoscere i raggi estremi, che coincidono con le semirette che delimitano la figura piana.

Esempio 3 Si verifichi che dato il problema max x1+ x2

x1− x²≤ 0 x1, x2≥ 0 i vettori

(1/2, 1) (0, 1) (1, 1)

sono tutti raggi di Sa ma solo gli ultimi due sono raggi estremi.

Come per i vertici, anche per i raggi estremi si pu´o dimostrare che il loro numero ´e sempre finito.

Osservazione 4 Sa ha sempre un numero finito di raggi estremi.

Siamo ora pronti per enunciare un importante teorema che mostra che la regione ammissibile Sa di un problema di PL in forma canonica `e com- pletamente caratterizzata dai suoi vertici e raggi estremi , il teorema di rappresentazione per Sa.

Teorema 2 Sia dato un problema di PL in froma canonica con Sa 6=

∅. Siano v¹, . . . , vk i vertici di Sa e, nel caso in cui Sa sia un poliedro illimitato, siano r1, . . . , rh i raggi estremi di Sa. Allora

x∈ Sa

se e solo se

∃ λ¹, . . . , λk≥ 0, Xk i=1

λi= 1, ∃ µ¹, . . . , µh≥ 0

tali che

x= Xk i=1

λiv_i+ Xh j=1

µjr_j.

Il teorema ci dice che tutti e soli i punti di Sa sono ottenibili come somma di una combinazione convessa (combinazione lineare con coefficienti non negativi e la cui somma `e pari a 1) dei vertici di Sa e di una combinazione lineare con coefficienti non negativi dei raggi estremi di Sa.

2.4 L’insieme delle soluzioni ottime S_ott

Fino a questo momento ci siamo limitati a considerare la regione ammis- sibile Sa di un problema di PL. Ricordiamo per´o che il nostro scopo ´e determinare una soluzione ottima del problema di PL. Quindi dobbiamo trovare almeno un punto all’interno dell’insieme:

Sott={x^∗∈ S^a: cx^∗≥ cx ∀ x ∈ S^a},

detto insieme delle soluzioni ottime del problema. Notiamo immediata- mente che Sott⊆ S^a, il che banalmente implica che se Sa=∅, allora anche Sott=∅. Inoltre, si dimostra la seguente osservazione.

Osservazione 5 Se Sott´e un insieme finito e non vuoto, Sott contiene un solo punto.

Dimostrazione Ragioniamo per assurdo. Supponiamo che Sott sia un insieme finito e contenga pi´u di un punto. Siano x1, x2 ∈ S^ott, x1 6= x², due punti distinti di Sott. Si dovr´a avere cx1 = cx2. Per la convessit´a di Sa si ha che tutti i punti:

λx1+ (1− λ)x² λ∈ (0, 1),

(i punti lungo il segmento che congiunge x1 e x2), appartengono a Sa. Inoltre, la linearit´a della funzione obiettivo implica:

c[λx1+(1−λ)x²] = λcx1+(1−λ)cx²= λcx1+(1−λ)cx¹= cx1 ∀ λ ∈ (0, 1).

Ma allora tutto il segmento che congiunge x1 e x2 ´e contenuto in Sott. Essendo tale insieme costituito da un numero infinito di punti, questo con- traddice l’ipotesi di finitezza dell’insieme Sott.

Prima di addentrarci nell’analisi di Sott introduciamo un metodo di tipo grafico che ci consentir´a di determinare Sott nel caso di problemi con due sole variabili. Nonostante la limitata applicabilit´a di questo metodo di risoluzione (i problemi reali hanno tipicamente molto pi´u di due sole varia- bili), esso ci consentir´a di visualizzare facilmente le diverse possibili forme dell’insieme Sott.

2.4.1 Metodo di risoluzione grafica

Per descrivere la risoluzione grafica consideriamo il seguente esempio:

max x1+ 2x2

x1+ x2≤ 1 x1, x2≥ 0

Per prima cosa disegniamo la regione ammissibile Sa. Poi prendiamo la funzione obiettivo e poniamola uguale a 0, cio´e consideriamo cx = 0 nel caso generale e x1+ 2x2= 0 nell’esempio. Questa ´e una retta che passa per l’origine che contiene tutti i punti in R² con valore della funzione obiettivo pari a 0. Ora voglio individuare qual ´e la direzione di crescita del fascio di rette

cx= k, k∈ R

parallele alla retta cx = 0 passante per l’origine. Nell’esempio avremo x1+ 2x2= k, k∈ R

fascio di rette parallele a x1+ 2x2= 0. Possiamo individuare la direzione di crescita per esempio tracciando la retta cx = 1 (quindi x1+ 2x2 = 1 nel nostro esempio) e la direzione di crescita sar´a quella che va dalla retta cx= 0 verso la retta cx = 1. In Figura 2.1 la direzione di crescita per il nostro esempio ´e indicata con una freccia sulla retta x1+ 2x2= 0. A questo

@@

@@

@@

@@

@@

@@

@@

@@

HHHH

HHHH

HHHH

HHHH

HHHHH

­­

Sa

x1+2x2=0 O

A B (0,1)

(1,0)

Figura 2.1:

punto sono possibili due casi:

Caso 1 Muovendomi dalla retta cx = 0 verso la direzione di crescita ho almeno una retta del fascio con intersezione non vuota con Sa. In tal caso abbiamo due sottocasi possibili.

Caso 1.1 Esiste un valore k tale che la retta cx = k ha intersezione non vuota con Sa mentre tutte le retta cx = k per k > k hanno intersezione vuota con Sa. In tal caso k ´e il valore ottimo del problema e l’intersezione della retta cx = k con Sa costituisce l’insieme Sott.

Caso 1.2 Esiste un K≥ 0 tale che per ogni k ≥ K la retta cx = k ha intersezione non vuota con Sa. In tal caso ci troviamo nella situazione in cui Sott = ∅ in quanto il problema ha obiettivo illimitato.

Caso 2 Muovendomi dalla retta cx = 0 verso la direzione di crescita non ho alcuna retta del fascio con intersezione non vuota con Sa. In tal caso mi muovo nella direzione di decrescita e mi arresto con la prima retta cx = k (k < 0) che ha intersezione non vuota con Sa (quindi per ogni k > k si ha che la retta cx = k ha intersezione vuota con Sa). Il valore k ´e il valore ottimo del problema e l’intersezione della retta cx = k con Sa rappresenta l’insieme Sott.

Nel nostro esempio si pu´o vedere che ci si trova nel Sottocaso 1.1 con k = 2 e Sottristretto al solo punto B di coordinate (0, 1).

2.4.2 Le diverse forme possibili di S_ott

Siamo ora pronti a individuare tutte le forme possibili di Sottal variare di Sa.

Caso 1 Sa =∅. In tal caso, essendo S^ott un sottinsieme di Sa, pu´o solo essere Sott=∅.

Caso 2 Sa 6= ∅ e politopo. Un politopo ´e un insieme chiuso e limitato, mentre la funzione obiettivo ´e lineare e quindi certamente continua.

Di conseguenza, il Teorema di Weierstrass garantisce l’esistenza di almeno una soluzione ottima, ovvero Sott 6= ∅. Sono possibili due sottocasi.

Caso 2.1 Sott´e costituito da un solo punto.

Caso 2.2 Sott´e costituito da un insieme infinito e limitato di punti.

Si noti che l’Osservazione 5 esclude la possibilit´a di un numero finito e maggiore di 1 di punti in Sott, mentre la limitatezza di Sott´e garantita

dal fatto che ´e un sottinsieme di Sa che a sua volta ´e un politopo e quindi ´e limitato.

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

Caso 3.1 Sott = ∅ in quanto l’obiettivo ´e 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 → +∞.

Caso 3.2 Sott´e costituito da un solo punto.

Caso 3.3 Sott´e costituito da un insieme infinito e limitato di punti.

Caso 3.4 Sott´e costituito da un insieme infinito e illimitato di punti.

Come esercizio si applichi ora la risoluzione grafica ai seguenti esempi rico- noscendo in essi molti dei casi possibili per Sott precedentemente elencati.

max x1+ x2

x1+ x2≤ 1 x1, x2≥ 0 max x1+ x2

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

x2≥ 1 x1, x2≥ 0

max −x¹

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

x2≥ 1 x1, x2≥ 0

max −x²

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

x2≥ 1 x1, x2≥ 0

max x1− x²

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

x2≥ 1 x1, x2≥ 0

2.5 Il Teorema Fondamentale della PL

La risoluzione grafica dei precedenti esempi mostra anche che, quando Sott 6= ∅, tale insieme contiene sempre almeno un vertice. Non ´e un caso.

Vale infatti un teorema molto importante noto come Teorema Fondamen- tale della Programmazione Lineare. Prima di dimostrare questo abbiamo bisogno di dimostrare un lemma.

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

cr≤ 0.

Dimostrazione La dimostrazione ´e per assurdo. Supponiamo infatti che esista un raggio estremo r tale che

cr> 0 (2.1)

Notiamo che Sott 6= ∅ implica Sa 6= ∅. Sia allora x⁰ ∈ Sa. Poich´e r `e un raggio, in base alla Definizione 7 di raggio avremo che

∀ λ ≥ 0 : x⁰+ λr∈ S^a.

Calcoliamo ora il valore della funzione obiettivo nei punti x0+ λr:

c(x0+ λr) = cx0+ λcr Ma, in base a (2.1) possiamo concludere che

c(x0+ λr)→ +∞ λ→ +∞,

cio´e Sott =∅ in quanto l’obiettivo ´e illimitato sulla regione ammissibile, il che contraddice Sott6= ∅.

Si noti che la dimostrazione del lemma ci dice anche che qualora esista un raggio estremo r di Sa tale che cr > 0, allora il problema ha obietti- vo illimitato. Si pu´o dimostrare anche il viceversa, cio´e se il problema ha obiettivo illimitato, allora esiste sicuramente un raggio estremo r di Sa tale che cr > 0. Siamo ora pronti a dimostrare il Teorema Fondamentale della PL.

Teorema 3 Dato un problema di PL in forma canonica, se Sott6= ∅, allora Sott contiene almeno un vertice di Sa.

DimostrazioneIndichiamo con v1, . . . , vk i vertici di Sa e, nel caso in cui Sa sia un poliedro illimitato, indichiamo con r1, . . . , rh i raggi estremi di Sa. Se Sott6= ∅, sia x^∗∈ Sott.

Utilizzeremo una dimostrazione per assurdo. Per assurdo supponiamo che v1, . . . , vk6∈ S^ott

cio`e supponiamo che nessun vertice di Saappartenga a Sott. In particolare avremo

cvi< cx^∗ i = 1, . . . , k (2.2) In base al Teorema 2, poich´e x^∗∈ S^a avremo che

∃ λ^∗1, . . . , λ^∗_k≥ 0, Xk i=1

λ^∗_i = 1, ∃ µ^∗1, . . . , µ^∗_h≥ 0 (2.3)

tali che

x^∗= Xk i=1

λ^∗_iv_i+ Xh j=1

µ^∗_jr_j.

Quindi avremo

cx^∗= c



 Xk i=1

λ^∗_iv_i+ Xh j=1

µ^∗_jr_j



 e per la linearit`a della funzione obiettivo

cx^∗= Xk i=1

λ^∗_i(cvi) + Xh j=1

µ^∗_j(crj).

Nel Lemma 1 abbiamo dimostrato che:

cr_j≤ 0 j = 1, . . . , h. (2.4) Ora, in base a (2.3) e (2.4) avremo

cx^∗= Xk i=1

λ^∗_i(cvi) + Xh j=1

µ^∗_j

|{z}

≥0

(crj)

| {z }

≤0

.

da cui

cx^∗≤ Xk i=1

λ^∗_i(cvi).

Ma ora possiamo sfruttare (2.2):

cx^∗≤ Xk i=1

λ^∗_i (cvi)

| {z }

<cx^∗

<

Xk i=1

λ^∗_i(cx^∗).

(si noti che lo strettamente minore vale perch´e almeno uno dei λ^∗_i `e stret- tamente positivo in quanto, in base a (2.3), la loro somma deve essere pari a 1). Poich´e cx^∗ non dipende dall’indice i della sommatoria, lo possiamo portare fuori dalla stessa e quindi

cx^∗< (cx^∗) Xk i=1

λ^∗_i.

Ma ora in base a (2.3) abbiamo chePk

i=1λ^∗_i = 1, da cui cx^∗< cx^∗

il che `e assurdo.

Questo risultato ´e alla base della procedura di risoluzione che descrive- remo, l’algoritmo del simplesso. Infatti, tale algoritmo ricerca la soluzione ottima cercando di spostarsi ad ogni iterazione in modo intelligente da un vertice all’altro di Sa. Per modo intelligente si intende che l’algoritmo ten- ta di spostarsi ad una data iterazione da un vertice a uno con valore della funzione obiettivo maggiore.

2.6 Preparazione al metodo del simplesso

Sappiamo che il nostro scopo ´e trovare almeno un punto in Sott oppure stabilire che Sott=∅ in quanto anche S^a =∅ oppure perch´e l’obiettivo del problema di PL ´e illimitato. Dobbiamo allora individuare un metodo che ci consenta di raggiungere il nostro scopo. Abbiamo gi´a incontrato un tale metodo, quello di risoluzione grafica, la cui applicabilit´a ´e per´o ristretta ai soli problemi con due variabili. Quello che vogliamo ora ´e un metodo che possa essere applicato con un numero qualsiasi di variabili. Questo metodo sar´a il metodo del simplesso. Prima per´o di arrivare a descriverlo avremo bisogno di alcuni passaggi intermedi.

2.6.1 I problemi di PL in forma standard

I problemi di PL in forma standard hanno la seguente formulazione:

max cx

aix= bi i = 1, . . . , m x≥ 0

o, equivalentemente, in forma matriciale:

max cx

Ax= b x≥ 0

dove A ´e la matrice la cui i-esima riga ´e il vettore ai e b ´e il vettore la cui i-esima componente ´e bi. Rispetto alla forma canonica cambia solamente il fatto che i vincoli non sono pi´u di ≤ ma sono di uguaglianza. Vale la seguente osservazione.

Osservazione 6 Ogni problema di PL in forma canonica pu´o essere tra- sformato in uno equivalente in forma standard.

DimostrazioneSia dato il problema di PL in forma canonica

max cx

aix≤ bⁱ i = 1, . . . , m x≥ 0

Con l’aggiunta di una nuova variabile yiper ogni vincolo aix≤ bi, possiamo esprimere tale vincolo attraverso la seguente coppia di vincoli:

aix+ yi= bi, yi≥ 0.

Quindi, il problema di PL in forma canonica ´e equivalente al seguente:

max cx

a_ix+ yi= bi i = 1, . . . , m x≥ 0

yi≥ 0 i = 1, . . . , m

che ´e in forma standard (vincoli di uguaglianza e variabili non negative).

Avendo gi´a dimostrato in precedenza che ogni problema di PL pu´o es- sere ricondotto ad uno equivalente in forma canonica, l’osservazione sopra ci dice anche che ogni problema di PL pu´o essere ricondotto ad uno equi- valente in forma standard.