ProgrammazioneLineare Capitolo1

Capitolo 1

Programmazione Lineare

1.1 Modelli di Programmazione Lineare

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 uno solo dei seguenti tre oggetti: un libro che vale 20.000 lire, una macchina fotografica che vale 200.000 lire ed una borsa da 50.000 lire. 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:

1

DATI : sono i valori dei tre oggetti.

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 un solo 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. Ve- dremo per` o che in molte situazioni non ` e per nulla chiaro, a prima vista, capire qual ` e la decisione migliore. In generale, l’individuazione delle quat- tro componenti descritte sopra ` e solo il primo, importante, passo per trovare la decisione giusta. Un modo per arrivare ad essa ` e quello rappresentato in Figura 1.1. In essa si ha che, dopo l’individuazione delle quattro compo-

Formulazione del modello matematico

Procedura di

risoluzione

Validazione del

modello - obiettivi

- vincoli - variabili - dati

Individuazione di:

Figura 1.1: Passaggi per la risoluzione di un problema

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

nenti, si passa alla formulazione di un modello matematico del problema. Il modello viene quindi passato ad una procedura di risoluzione od algoritmo che fornisce la soluzione. Infine la soluzione ottenuta viene utilizzata per la validazione del modello, ovvero per verificare se il modello ` e aderente al problema reale che rappresenta oppure va modificato per renderlo tale.

Noi ci concentreremo in particolare sulla procedura di risoluzione ma pri- ma vedremo un paio di esempi di modelli con anche un piccolo esempio di validazione del modello.

1.1.1 Problemi con vincoli di risorse: un caso partico- lare e la formulazione generale

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-

Tabella 1.3:

farina 5100

acqua 8000

medicinali 1805

corre preparare se si vuole rendere massimo l’indice di utilit` a complessivo?

Cominciamo con l’individuare le quattro componenti della decisione.

DATI : sono i valori riportati nelle tre tabelle.

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.

Rispetto all’esempio iniziale ` e ora pi` u difficile stabilire qual ` e la cosa giusta 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 sul- le bottiglie 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. Vediamo allora di procede- re al secondo passo, la formulazione di un modello matematico per questo problema.

Modello matematico del problema Indichiamo con:

x ₁ il numero di pacchi di tipo I da realizzare.

x 2 il numero di pacchi di tipo II da realizzare.

x 3 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 x ₁ pacchi di tipo I richiedono

10x 1

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

30x ₂

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

20x ₃

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

10x 1 + 30x 2 + 20x 3

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

10x 1 + 30x 2 + 20x 3 ≤ 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

10x 1 + 20x 2 + 40x 3 ≤ 8000, e sulla disponibilit` a di medicinali

30x 1 + 10x 2 + 5x 3 ≤ 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:

x 1 ≥ 0 x 2 ≥ 0 x 3 ≥ 0.

L’insieme dei valori che si possono assegnare a x 1 , x 2 , x 3 senza violare i vincoli introdotti sopra viene detto insieme ammissibile. Ad esempio, x 1 = 20, x 2 = 20, x 3 = 30 ` e una soluzione ammissibile, mentre x 1 = 50, x 2 = 60, x <sub>3</sub> = 40 non lo ` e (viola il vincolo sulla disponibilit` a di medicinali) e non lo ` e neppure x ₁ = −2, x 2 = 20, x ₃ = 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 x <sub>1</sub> pacchi hanno utilit` a pari a

14x 1 .

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

5x ₂ e x ₃ pacchi di tipo III hanno utilit` a pari a

4x 3 .

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

14x ₁ + 5x ₂ + 4x ₃ . Il nostro obiettivo ` e massimizzare tale valore.

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

massimizzare 14x 1 + 5x 2 + 4x 3

tenuto conto che

10x 1 + 30x 2 + 20x 3 ≤ 5100 10x ₁ + 20x ₂ + 40x ₃ ≤ 8000 30x 1 + 10x 2 + 5x 3 ≤ 1805

x 1 ≥ 0 x ₂ ≥ 0 x 3 ≥ 0

In questo caso il modello risultante si definisce un programma lineare. Un

programma lineare ` e un modello in cui sia i vincoli che l’obiettivo sono

lineari, ovvero

1. i contributi delle diverse variabili si sommano tra loro;

2. i contributi delle variabili sono direttamente proporzionali al valore delle stesse.

Ad esempio, una formula del tipo

(14x ₁ ) ∗ (5x 2 ) + 4x ₃

non ` e lineare in quanto i contributi della variabile x 1 e della variabile x 2 si moltiplicano tra loro. Una formula del tipo

14x ² ₁ + 5x ₂ + 4x ₃

`

e anch’essa non lineare. Infatti, se ` e vero che i contributi delle diverse variabili si sommano tra loro, possiamo per` o anche notare che il contributo della variabile x 1 non ` e direttamente proporzionale a x 1 ma ` e direttamente proporzionale al quadrato di x ₁ . I programmi lineari sono molto importanti per almeno due ragioni:

1. molti problemi reali (come, ad esempio, il nostro) hanno come modello matematico proprio un programma lineare;

2. sono pi` u semplici da risolvere rispetto ad altri modelli dove compa- iono termini non lineari. Per i programmi lineari esistono delle pro- cedure molto efficienti di risoluzione (come il cosidetto algoritmo del simplesso).

L’operazione che abbiamo appena compiuto, ovvero quella di essere passati dal nostro problema inizialmente descritto a parole alla sua traduzione in un modello matematico ed aver riconosciuto che si tratta di un programma lineare, ` e un passo molto importante: ora sappiamo con che tipo di pro- blema abbiamo a che fare e che esistono apposite procedure efficienti per risolvere tale problema restituendoci le risposte che cerchiamo.

Al momento non siamo ancora in grado di risolvere il problema. Quando lo saremo potremo verificare che la soluzione ottima ` e data dai seguenti valori delle variabili:

x ₁ = 28 x ₂ = 0 x ₃ = 193,

con utilit` a pari a 1164. Come si vede si ottiene una soluzione ben diversa da una delle tre analizzate inizialmente (quelle in cui si utilizza un solo tipo di pacco).

Una volta ottenuta la soluzione mi devo chiedere se questa ` e sensata. Que-

sta fase si chiama validazione del modello. Nel formulare il problema potrei

essermi dimenticato di introdurre dei vincoli, ottenendo in questo modo una soluzione poco realistica. Nel nostro esempio possiamo notare che re- stano inutilizzati ben 960 sacchi di farina (se ne usano solo 4140 dei 5100 disponibili). Possiamo considerare questo spreco eccessivo. In realt` a noi non vorremmo sprecare pi` u del 10% di ogni risorsa. Ma questo introduce dei nuovi vincoli che modificano il modello. Oltre ai vincoli di disponibilit` a avremo ora anche dei vincoli di uso minimo di ciascuna risorsa. Per esempio la formula, precedentemente derivata, sulla quantit` a di sacchetti di farina utilizzati ` e la seguente:

10x ₁ + 30x ₂ + 20x ₃ .

Ci` o che si richiede ` e che il numero di sacchetti utilizzati sia non inferiore al 90% della disponibilit` a totale e quindi:

10x ₁ + 30x ₂ + 20x ₃ ≥ 0.9 ∗ 5100.

In modo del tutto analogo si derivano i vincoli per l’acqua e i medicinali:

10x 1 + 20x 2 + 40x 3 ≥ 0.9 ∗ 8000.

30x 1 + 10x 2 + 5x 3 ≥ 0.9 ∗ 1805.

Con l’aggiunta di questi vincoli la nuova soluzione diventa:

x ₁ = 21.72 x ₂ = 24.07 x ₃ = 182.53,

con utilit` a pari a 1154.58. Si pu` o notare come queste soluzioni siano dei valori decimali. Non ha molto senso parlare di una quantit` a decimale di un pacco (il numero di pacchi deve essere un valore intero). In questo caso si pu` o ottenere una soluzione semplicemente arrotondando i valori decimali.

Pi` u avanti vedremo che questo metodo vale solo per questo tipo di problemi in cui i valori delle variabili sono relativamente grandi. Vedremo in seguito esempi con obiettivo e vincoli che sono funzioni affini ma dove ` e necessario imporre esplicitamente tra i vincoli che i valori delle variabili devono essere delle quantit` a intere (si parler` a in tal caso di programmi lineari interi).

Come vedremo, questo render` a pi` u complessa la risoluzione del problema.

Il problema appena visto ` e un caso particolare di problema con vincoli

di risorse. Nei problemi con vincoli di risorse abbiamo un insieme RISOR-

SE di risorse (farina, acqua e medicinali nell’esempio). Di ogni risorsa j

si ha a disposizione una quantit` a limitata b j (i valori in Tabella 1.3 nel-

l’esempio). Inoltre si ha un insieme PRODOTTI di prodotti (i tre tipi di

pacco nell’esempio) realizzabili con le risorse. A ogni prodotto i ` e associato

un profitto p i per unit` a di prodotto (i valori in Tabella 1.2 nell’esempio).

Infine, un’unit` a di prodotto i consuma una quantit` a a _ij di risorsa j (i valori in Tabella 1.1 nell’esempio). Le quantit` a da decidere sono le quantit` a di ciascun prodotto i da realizzare, che indicheremo con le variabili x _i . Per ogni risorsa j avremo un vincolo che impone di non superare la disponibilit` a massima b <sub>j</sub> di tale risorsa. Il vincolo ` e espresso dalla disequazione:

X

i ∈P RODOT T I

a _ij x _i ≤ b j .

Il profitto totale, che si vuole massimizzare, ` e rappresentato dall’espressione X

i ∈P RODOT T I

p i x i .

Quindi, il modello per il generico problema con vincoli di risorse ` e il se- guente:

max P

i ∈P RODOT T I p _i x _i P

i ∈P RODOT T I a ij x i ≤ b j j ∈ RISORSE x _i ≥ 0 i ∈ P RODOT T I

Si noti che sia l’obiettivo che i vincoli sono funzioni affini e quindi il modello

`

e un programma lineare.

1.1.2 Problemi della dieta

Nel generico problema della dieta abbiamo un insieme CIBI di cibi (ad esempio, carne, pesce, ecc.) (farina, acqua e medicinali nell’esempio) e un insieme ELEMENTI di elementi nutritivi (ad esempio, vitamine, proteine, ecc.). Di ogni elemento nutritivo j si ha una richiesta minima b _j che deve essere assunta in una giornata. A ogni cibo i ` e associato un costo c <sub>i</sub> per unit` a di cibo. Infine, un’unit` a di cibo i apporta una quantit` a a _ij di ele- mento nutritivo j. Le quantit` a da decidere sono le quantit` a di ciascun cibo i da inserire nella dieta girornaliera, che indicheremo con le variabili x _i . Per ogni elemento nutritivo j avremo un vincolo che impone che la dieta contenga almeno la quantit` a b j di tale elemento. Il vincolo ` e espresso dalla disequazione:

X

i ∈CIBI

a ij x i ≥ b j .

Il costo totale della dieta, che si vuole minimizzare, ` e rappresentato dall’e- spressione

X

i ∈CIBI

c i x i .

Quindi, il modello per il generico problema con vincoli di risorse ` e il se- guente:

max P

i ∈CIBI c i x i

P

i ∈CIBI a ij x i ≥ b j j ∈ ELEMEN T I x _i ≥ 0 i ∈ CIBI

Si noti che sia l’obiettivo che i vincoli sono funzioni affini e quindi il modello

`

e un programma lineare.

1.2 Teoria della Programmazione lineare

Un generico problema di programmazione lineare ha la seguente forma min( oppure max) c ^T x

a ^T _i x ≤ b i i = 1, . . . , m ₁ a ^T _i x ≥ b i i = m 1 + 1, . . . , m 2

a ^T _i x = b i i = m 2 + 1, . . . , m 3

x _j ≥ 0 j = 1, . . . , n ₁ x j ≤ 0 j = n 1 + 1, . . . , n 2

x _j libera in segno j = n ₂ + 1, . . . , n ₃

Ci` o che caratterizza i problemi di Programmazione Lineare (PL nel seguito)

´ e

• il fatto che sia la funzione obiettivo che quelle che definiscono i vincoli sono funzioni affini (ovvero funzioni lineari pi` u un termine noto);

• il fatto che le variabili possono assumere valori reali.

Mentre queste sono caratteristiche fisse dei problemi di PL, altre caratte- ristiche potranno variare di problema in problema: l’obiettivo potr` a essere minimizzato o massimizzato; i vincoli potranno essere di ≥, ≤ oppure = (ma non di > e <); le variabili potranno essere vincolate ad assumere solo valori non negativi oppure non positivi oppure potranno indifferentemente assumere valori sia negativi che positivi.

Un tipo particoalre 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 c ^T x

a ^T _i x ≤ b i i = 1, . . . , m x j ≥ 0 j = 1, . . . , n o, in forma matriciale,

max c ^T x A ^T x ≤ b

x ≥ 0

dove A = [a 1 · · · a n ] ∈ R ^{n ×m} ´ e una matrice le cui colonne sono i vettori a i

che definiscono i vincoli, b ∈ R ^m ` e il vettore con i-esima componente b <sub>i</sub> e x ∈ R <sup>n</sup> . 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.

Dimostrazione Si pu` o notare che

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

min c ^T x = − max −c ^T x

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

a ^T _i x ≥ b i ⇒ −a ^T i x ≤ −b i

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

a ^T _i x = b i ⇒ a ^T i x ≤ b i , −a ^T i x ≤ −b i

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

x ⁰ _j = −x j ≥ 0

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

x _j = 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 x ₁ + x ₂ + x ₃ x 1 + 2x 2 − x 3 ≤ 3 x ₁ + 4x ₂ + 5x ₃ = 5

x 1 − 2x 2 + x 3 ≥ 3 x 1 ≥ 0 x ₂ ≤ 0 x 3 libera in segno

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

Definizione 1 Dato un problema di PL in forma canonica, l’insieme S a

di punti che soddisfano i suoi vincoli, ovvero l’insieme S a = {x ∈ R ⁿ : A ^T x ≤ b, x ≥ 0}

viene detto regione ammissibile del problema di PL. L’insieme S _ott dei punti in S _a con valore della funzione obiettivo non inferiore rispetto a tutti gli altri punti in S _a , ovvero l’insieme

S ott = {x ^∗ ∈ S a : c ^T x ^∗ ≥ c ^T x ∀ x ∈ S a } ⊆ S a

viene detto insieme delle soluzioni ottime del problema di PL.

Nel seguito ci occuperemo di carratterizzare prima la regione ammissibile S a e poi l’insieme delle soluzioni ottime S ott .

1.2.1 La regione ammissibile S a

Definizione 2 Un insieme C si dice convesso se

∀ x 1 , x 2 ∈ C ∀ λ ∈ [0, 1] : λx 1 + (1 − λx 2 ) ∈ C,

ovvero se dati due punti qualsiasi in C, il segmento che li congiunge ` e

anch’esso completamente contenuto in C.

Definizione 3 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 4 Un insieme C si dice chiuso se contiene la sua frontiera.

La regione ammissibile S a del problema di PL ` e ottenuta come intersezione di m + n semispazi

a ^T _i x ≤ b i i = 1, . . . , m x j ≥ 0 j = 1, . . . , n.

L’intersezione di un numero finito di semispazi ` e sempre un insieme chiuso e convesso e quindi S <sub>a</sub> stesso ` e sempre un insieme chiuso e convesso. Possiamo classificare le possibili forme di S _a nei seguenti tre modi.

S a = ∅ In tal caso si parla di regione ammissibile vuota.

S _a 6= ∅ e limitato In tal caso S a viene detto poliedro convesso.

S a 6= ∅ e illimitato In tal caso S a viene detto troncone.

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

max x ₁ + x ₂ x 1 ≤ −1 x ₁ + x ₂ ≤ 1

x 1 , x 2 ≥ 0

max x ₁ + x ₂ x 1 + x 2 ≤ 1

x 1 , x 2 ≥ 0

max x 1 + x 2

x 1 − x 2 ≤ 0

x ₁ , x ₂ ≥ 0

Diamo ora la definizione di iperpiano generatore.

Definizione 5 Gli m + n iperpiani

a ^T _i x = b _i i = 1, . . . , m x _j = 0 j = 1, . . . , n

corrispondenti alle disequazioni che definiscono S _a vengono detti iperpiani generatori di S _a .

Particolare importanza all’interno di S _a rivestono alcuni punti che chiame- remo vertici, definiti nel modo seguente.

Definizione 6 Un punto x ∈ R ⁿ viene detto vertice di S a se soddisfa le seguenti condizioni:

1. x ∈ S a

2. ` E intersezione unica di almeno n iperpiani generatori, di cui n line- ramente indipendenti.

Si verifichi che, dato il problema

max x 1 + x 2

x 1 + x 2 ≤ 1

−2x 1 − 2x 2 ≤ −2 x 1 , x 2 ≥ 0

il punto (1/2, 1/2) non ` e un vertice di S a mentre lo ` e il punto (1, 0). Una definizione equivalente di vertice ci ` e data dalla seguente osservazione.

Osservazione 2 Un punto x ∈ S a ` e un vertice di S a se e solo se 6 ∃ x 1 , x 2 ∈ S a , x 1 6= x 2

tali che

x = 1 2 x ₁ + 1

2 x ₂

Un primo teorema ci dice che in un problema di PL in forma canonica, se esiste almeno una soluzione ammissibile, allora la regione ammissibile ha almeno un vertice.

Teorema 1 Dato un problema di PL in forma canonica, se S a 6= ∅, allora S a ha almeno un vertice.

Vale inoltre la seguente osseravzione.

Osservazione 3 Il numero di vertici di S a ` e finito.

Introduciamo ora la definizione di spigolo.

Definizione 7 L’intersezione di almeno n − 1 iperpiani generatori, di cui esattamente n − 1 linearmente indipendenti `e una retta. Se l’intersezione di tale retta con S a ` e non vuota e non si riduce a un solo punto, allora tale intersezione verr` a detta spigolo. Uno spigolo pu` o essere limitato o illimitato.

Come esercizio, si verifichi graficamente che, dato il problema max x 1 + x 2

x 1 + x 2 ≤ 1

−2x 1 − 2x 2 ≤ −2 x 1 , x 2 ≥ 0

l’intersezione degli iperpiani generatori x ₁ + x ₂ = 1 e −2x 1 − 2x 2 = −2 definisce uno spigolo limitato, mentre dato il problema

max x 1 + x 2

x 1 − x 2 ≤ 0 x 1 , x 2 ≥ 0

l’iperpiano generatore x 1 − x 2 = 0 definisce uno spigolo illimitato. Come i vertici, anche gli spigoli sono in numero finito, come stabilito nella seguente osservazione.

Osservazione 4 Il numero di spigoli di S a ` e finito.

Introduciamo ora la definizione di raggio di S a .

Definizione 8 Un vettore r ∈ R ⁿ , r 6= 0, si definisce raggio di S a se

∀ x 0 ∈ S a ∀ λ ≥ 0 : x 0 + λr ∈ S a ,

ovvero se dato qualsiasi punto x 0 in S a , la semiretta con origine in x 0 e direzione r ` e contenuta in S a .

Si noti che l’esistenza di un raggio di S a ` e possibile solo se S a ` e illimitato,

ovvero ` e un troncone. Questo ` e una conseguenza del fatto che dato un

raggio r e un punto x 0 ∈ S a , la semiretta con origine in x 0 e direzione r

(che ` e un insieme ilimitato) ` e contenuta in S a , che a sua volta deve quindi

essere un insieme illimitato. Tra i raggi ve ne sono alcuni particolari che

vengono detti raggi estremi.

Definizione 9 Un vettore r ∈ R ⁿ si dice raggio estremo di S a se ` e un raggio di S _a e inoltre

6 ∃ r 1 , r ₂ raggi di S _a , r ₁ 6= µr 2 ∀ µ ∈ R, tali che

r = 1 2 r 1 + 1

2 r 2

In pratica i raggi estremi coincidono con i vettori che definiscono la direzione delle semirette corrispondenti a spigoli illimitati. Come esercizio, si verifichi che dato il problema

max x 1 + x 2

x ₁ − x 2 ≤ 0 x 1 , x 2 ≥ 0 i vettori

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

sono tutti raggi di S a ma solo gli ultimi due sono raggi estremi. Un impor- tante risultato mostra che la regione ammissibile S a di un problema di PL in forma canonica ` e completamente caratterizzata dai suoi vertici e raggi estremi.

Teorema 2 Sia dato un problema di PL in froma canonica con S a 6= ∅.

Siano v 1 , . . . , v k i vertici di S a e, nel caso in cui S a sia un troncone, siano r 1 , . . . , r h i raggi estremi di S a . Allora

x ∈ S a

se e solo se

∃ λ 1 , . . . , λ k ≥ 0,

k

X

i=1

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

tali che

x =

k

X

i=1

λ i v i +

h

X

j=1

µ j r j .

Il teorema ci dice che tutti e soli i punti di S a 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 S a e di una combinazione

lineare con coefficienti non negativi dei raggi estremi di S a .

1.2.2 L’insieme delle soluzioni ottime S _ott

In precedenza abbiamo ristretto l’atenzione alla sola regione ammissibile S a . Ora prenderemo in esame l’insieme S ott e quindi entrer´ a in gioco anche la funzione obiettivo. Prima di elencare tutti le possibili forme di S ott , dimostriamo la seguente osservazione,

Osservazione 5 Se x ₁ , x ₂ ∈ S ott , x ₁ 6= x 2 , allora l’intero segmento tra x ₁ e x ₂ ´ e contenuto in S _ott , cio´ e

∀ λ ∈ [0, 1] λx 1 + (1 − λ)x 2 ∈ S ott .

Dimostrazione Per prima cosa notiamo che x 1 , x 2 ∈ S ott implica x 1 , x 2 ∈ S _a e quindi, essendo S _a un insieme convesso si ha

∀ λ ∈ [0, 1] λx 1 + (1 − λ)x 2 ∈ S a ,

cio´ e l’intero segmento tra x 1 e x 2 appartiene a S a . Inoltre x 1 , x 2 ∈ S ott

implica c ^T x 1 = c ^T x 2 (il valore della funzione obiettivo ´ e lo stesso nei due punti) e quindi, sfruttando la linearit´ a della funzione obiettivo si ha

∀ λ ∈ [0, 1] c ^T (λx 1 + (1 − λ)x 2 ) = λc ^T x 1 + (1 − λ)c ^T x 2 =

= λc ^T x 1 + (1 − λ)c ^T x 1 = c ^T x 1 ,

ovvero lungo tutti i punti del segmento il valore della funzione obiettivo ´ e lo stesso di x 1 e x 2 e quindi anche tali punti appartengono a S ott come si voleva dimostrare.

Siamo ora pronti a individuare tutte le forme possibili di S _ott al variare di S _a .

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

Caso 2 S a 6= ∅ e poliedro convesso. Un poliedro convesso ´e un insie- me chiuso e limitato, mentre la funzione obiettivo ´ e lineare e quindi certamente continua. Di conseguenza, il Teorema di Weierstrass ga- rantisce l’esistenza di almeno una soluzione ottima, ovvero S _ott 6= ∅.

Sono possibili due sottocasi.

Caso 2.1 S ott ´ e costituito da un solo punto.

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

Si noti che l’Osservazione 5 esclude la possibilit´ a di un numero finito di punti in S _ott , mentre la limitatezza di S _ott ´ e garantita dal fatto che

´

e un sottinsieme di S _a che a sua volta ´ e un poliedro convesso e quindi

´

e limitato.

Caso 3 S a 6= ∅ e troncone. Sono possibili quattro sottocasi.

Caso 3.1 S _ott = ∅ 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 c ^T x _k → +∞ k → +∞.

Caso 3.2 S ott ´ e costituito da un solo punto.

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

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

Per illustrare tramite esempi tutti i vari casi e sottocasi, introduciamo la risoluzione grafica dei problemi di Programmazione Lineare, utilizzabile per problemi con due sole variabili. Per quanto i problemi reali abbiano molto pi´ u di due variabili e non si possono risolvere graficamente, la risoluzione grafica aiuta a visualizzare e a meglio comprendere tutti i casi possibili. Per descrivere la risoluzione grafica consideriamo il seguente esempio:

max x 1 + 2x 2

x 1 + x 2 ≤ 1 x ₁ , x ₂ ≥ 0

Per prima cosa disegniamo la regione ammissibile S a . Poi prendiamo la funzione obiettivo e poniamola uguale a 0 e quindi c ^T x = 0 nel caso generale e x 1 + 2x 2 = 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

c ^T x = k, k ∈ R

parallele alla retta c ^T x = 0 passante per l’origine. Nell’esempio avremo x 1 + 2x 2 = k, k ∈ R

fascio di rette parallele a x 1 + 2x 2 = 0. Possiamo individuare la direzione

di crescita per esempio tracciando la retta c ^T x = 1 e la direzione di crescita

sar´ a quella che va dalla retta c ^T x = 0 verso la retta c ^T x = 1. In Figura

1.2 la direzione di crescita per il nostro esempio ´ e indicata con una freccia

sulla retta x 1 + 2x 2 = 0. A questo punto sono possibili due casi:

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@ H H

H H H H

H H H H

H H H H

H H H H

H H H

Sa

x1+2x2=0 O

A B (0,1)

(1,0)

Figura 1.2:

Caso 1 Muovendomi dalla retta c ^T x = 0 verso la direzione di crescita ho almeno una retta del fascio con intersezione non vuota con S a . In tal caso abbiamo due sottocasi possibili.

Caso 1.1 Esiste un valore k tale che la retta c ^T x = k ha intersezione non vuota con S _a mentre tutte le retta c ^T x = k per k > k hanno intersezione vuota con S _a . In tal caso k ´ e il valore ottimo del problema e l’intersezione della retta c ^T x = k con S a costituisce l’insieme S ott .

Caso 1.2 Esiste un K ≥ 0 tale che per ogni k ≥ K la retta c ^T x = k ha intersezione non vuota con S a . In tal caso ci troviamo nella situazione in cui S ott = ∅ in quanto il problema ha obiettivo illimitato.

Caso 2 Muovendomi dalla retta c ^T x = 0 verso la direzione di crescita non

ho alcuna retta del fascio con intersezione non vuota con S a . In tal

caso mi muovo nella direzione di decrescita e mi arresto con la prima

retta c ^T x = k che ha intersezione non vuota con S a (quindi per ogni k > k si ha che la retta c ^T x = k ha intersezione vuota con S _a ). Il valore k ´ e il valore ottimo del problema e l’intersezione della retta c ^T x = k con S _a rappresenta l’insieme S _ott .

Nel nostro esempio si pu´ o vedere che ci si trova nel Sottocaso 1.1 con k = 2 e S ott ristretto al solo punto B di coordinate (0, 1). Come esercizio si applichi ora la risoluzione grafica ai seguenti esempi riconoscendo in essi tutti i casi possibili per S ott precedentemente elencati.

max x ₁ + x ₂ x 1 + x 2 ≤ 1

x ₁ , x ₂ ≥ 0 max x 1 + x 2

−x 1 + x ₂ ≤ 0 x 1 − x 2 ≤ 1

x ₂ ≥ 1 x 1 , x 2 ≥ 0

max −x 1

−x 1 + x 2 ≤ 0 x 1 − x 2 ≤ 1

x 2 ≥ 1 x 1 , x 2 ≥ 0

max −x 2

−x 1 + x 2 ≤ 0 x 1 − x 2 ≤ 1

x 2 ≥ 1 x ₁ , x ₂ ≥ 0 max x 1 − x 2

−x 1 + x ₂ ≤ 0 x 1 − x 2 ≤ 1

x ₂ ≥ 1

x 1 , x 2 ≥ 0

La risoluzione grafica di questi esempi mostra anche che, quando S ott 6= ∅, tale insieme contiene sempre almeno un vertice. Non ´ e un caso. Vale infatti il seguente teorema molto importante e noto come Teorema Fondamentale della Programmazione Lineare.

Teorema 3 Sia dato un problema di PL in forma canonica. Se S ott 6= ∅ allora almeno un punto di S ott ` e un vertice di S a .

Dimostrazione Indichiamo con v ₁ , . . . , v _k i vertici di S _a e, nel caso in cui S _a sia un troncone, indichiamo con r ₁ , . . . , r _h i raggi estremi di S _a . Se S _ott 6= ∅, sia x ^∗ ∈ S ott .

Utilizzeremo una dimostrazione per assurdo. Per assurdo supponiamo che v ₁ , . . . , v _k 6∈ S ott

cio` e supponiamo che nessun vertice di S a appartenga a S ott . In particolare avremo

c ^T v _i < c ^T x ^∗ i = 1, . . . , k (1.1) In base al Teorema 2, poich´ e x ^∗ ∈ S a avremo che

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

k

X

i=1

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

tali che

x ^∗ =

k

X

i=1

λ ^∗ _i v i +

h

X

j=1

µ ^∗ _j r j .

Quindi avremo

c ^T x ^∗ = c ^T





k

X

i=1

λ ^∗ _i v i +

h

X

j=1

µ ^∗ _j r j



 e per la linearit` a della funzione obiettivo

c ^T x ^∗ =

k

X

i=1

λ ^∗ _i (c ^T v i ) +

h

X

j=1

µ ^∗ _j (c ^T r j ).

Per prima cosa dimostriamo che

c ^T r _j ≤ 0 j = 1, . . . , h. (1.3)

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

c ^T r _j > 0 (1.4)

Poich´ e r _j ` e un raggio, in base alla Definizione 8 di raggio avremo che

∀ λ ≥ 0 : x ^∗ + λr _j ∈ S a . In particolare, se fisso λ = 1, ottengo un punto

x = x ^∗ + r _j ∈ S a .

Calcoliamo ora il valore della funzione obiettivo in x:

c ^T x = c ^T (x ^∗ + r _j ) = c ^T x ^∗ + c ^T r _j Ma, in base a (1.4) possiamo concludere che

c ^T x > c ^T x ^∗ , il che contraddice l’ottimalit` a di x ^∗ . Ora, in base a (1.2) e (1.3) avremo

c ^T x ^∗ =

k

X

i=1

λ ^∗ _i (c ^T v i ) +

h

X

j=1

µ ^∗ _j

|{z}

≥0

(c ^T r j )

| {z }

≤0

.

da cui

c ^T x ^∗ ≤

k

X

i=1

λ ^∗ _i (c ^T v i ).

Ma ora possiamo sfruttare (1.1):

c ^T x ^∗ ≤

k

X

i=1

λ ^∗ _i (c ^T v i )

| {z }

<c

x

<

k

X

i=1

λ ^∗ _i (c ^T x ^∗ ).

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

c ^T x ^∗ < (c ^T x ^∗ )

k

X

i=1

λ ^∗ _i .

Ma ora in base a (1.2) abbiamo che P k

i=1 λ ^∗ _i = 1, da cui c ^T x ^∗ < c ^T x ^∗

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 S a . 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.

1.3 L’algoritmo del simplesso

Prima di poter descrivere l’algoritmo del simplesso avremo bisogno di in- trodurre alcune definizioni. Supponiamo di avere un generico problema di PL in forma canonica:

max c ^T x

a ^T _i x ≤ b i i = 1, . . . , m x j ≥ 0 j = 1, . . . , n

A tale formulazione possiamo aggiungere una variabile u _i per ogni vincolo definita nel modo seguente

u _i = b _i − a ^T i x

e vincolata ad assumere valori ≥ 0. Si noti che u i = b i − a ^T i x e u i ≥ 0 ´e del tutto equivalente a scrivere a ^T _i x ≤ b i . Inoltre u i = 0 equivale all’iperpiano a ^T _i x = b i . Aggiungiamo inoltre una variabile z per l’obiettivo definita nel modo seguente

z = c ^T x.

Quindi possiamo riformulare il nostro problema nel modo che segue:

max z = c ^T x

u i = b i − a ^T i x i = 1, . . . , m

x _j ≥ 0 j = 1, . . . , n

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

Diamo ora la seguente definizione.

Definizione 10 Un sottinsieme {y 1 , . . . , y n } delle n+m variabili {x 1 , . . . , x n , u 1 , . . . , u m } tale che gli iperpiani

y 1 = 0, · · · , y n = 0

sono tra loro linearmente indipendenti, viene detto base del problema di PL.

Le variabili y 1 , . . . , y n vengono dette variabili in base, mentre le rimanenti variabili, indicate con y n+1 , . . . , y n+m , vengono dette variabili fuori base.

Si consideri il seguente esempio:

max x 2

−x 1 + x 2 ≤ 1 x 1 + x 2 ≤ 3

x ₁ ≤ 3 x 1 , x 2 ≥ 0

Con l’introduzione delle variabili u 1 , u 2 , u 3 relative ai vincoli e della varia- bile z relativa all’obiettivo, il problema viene riscritto nel modo seguente:

max z = x 2

u ₁ = x ₁ − x 2 + 1 u 2 = −x 1 − x 2 + 3

u ₃ = −x 1 + 3 x 1 , x 2 ≥ 0 u 1 , u 2 , u 3 ≥ 0

Si verifichi che {x 1 , x 2 }, {x 2 , u 1 }, {x 2 , u 2 } e {x 2 , u 3 } sono basi, mentre {x 1 , u 3 } non ´e una base.

Data una base {y 1 , . . . , y n } ´e sempre possibile esprimere tutte le variabili fuori base y n+1 , . . . , y n+m e la variabile z dell’obiettivo come combinazione lineare delle variabili in base pi´ u un termine noto, ovvero

y n+1 = α 11 y 1 + · · · + α 1n y n + β 1

.. . = .. . (1.5)

y _n+m = α _m1 y ₁ + · · · + α mn y _n + β _m z = γ 1 y 1 + · · · + γ n y n + γ 0

Queste m + 1 equazioni vengono rappresentate tramite la Tabella 1.4. Per

Tabella 1.4:

y 1 · · · y h · · · y n

y _n+1 α ₁₁ · · · α _1h · · · α _1n β ₁ .. . .. . .. . .. . .. . .. . .. . y _n+k α _k1 · · · α _kh · · · α _kn β _k

.. . .. . .. . .. . .. . .. . .. . y n+m α m1 · · · α mh · · · α mn β m

z γ 1 · · · γ h · · · γ n γ 0

Tabella 1.5:

x 1 x 2

u ₁ 1 -1 1

u ₂ -1 -1 3

u ₃ -1 0 3

z 0 1 0

le base {x 1 , x ₂ } dell’esempio abbiamo

u ₁ = x ₁ − x 2 + 1 u 2 = −x 1 − x 2 + 3

u 3 = −x 1 + 3 z = x ₂

con la relativa Tabella 1.5. Per la base {x 2 , u 1 } avremo x 1 = x 2 + u 1 − 1

u 2 = −2x 2 − u 1 + 4 u ₃ = −x 2 − u 1 + 4

z = x 2

con la relativa Tabella 1.6. Per la base {x 2 , u ₂ } avremo x 1 = −x 2 − u 2 + 3

u ₁ = −2x 2 − u 2 + 4 u 3 = x 2 + u 2 + 0

z = x ₂

Tabella 1.6:

x 2 u 1

x ₁ 1 1 -1

u ₂ -2 -1 4 u ₃ -1 -1 4

z 0 1 0

Ricavare la tabella relativa. Per la base {x 2 , u 3 } avremo x ₁ = −u 3 + 3

u 1 = −x 2 − u 3 + 4 u ₂ = −x 2 + u ₃ + 0

z = x 2

Ricavare la tabella relativa.

Diamo ora la definizione di basi adiacenti.

Definizione 11 Due basi si definiscono adiacenti se differiscono per una sola variabile in base.

Nell’esempio le basi {x 1 , x 2 } e {x 2 , u 1 } sono adiacenti. Diamo ora l’impor- tante definizione di soluzione di base.

Definizione 12 Ad una base {y 1 , . . . , y _n } ´e associato un punto detto solu- zione di base, ottenuto ponendo a 0 tutte le variabili in base, ovvero

y j = 0 j = 1, . . . , n.

Dalle equazioni (1.5) si ha che

y _n+i = β _i i = 1, . . . , m

mentre il valore dell’obiettivo in corrispondenza di tale soluzione di base ´ e z = γ ₀ .

La soluzione di base viene detta ammissibile (ovvero ´ e un punto in S a ) se β i ≥ 0 i = 1, . . . , m.

Se

β i 6= 0 i = 1, . . . , m

si parla di soluzione di base non degenere, altrimenti si parla di soluzione

di base degenere.

Vale la seguente osservazione.

Osservazione 6 Non c’´ e corrispondenza biunivoca tra basi e soluzioni di base. Infatti, nel caso degenere (e solo in quello), a basi distinte pu` o corrispondere la stessa soluzione di base.

Nell’esempio, alla base {x 1 , x 2 } corrisponde la soluzione di base ammissibile e non degenere

x ₁ = x ₂ = 0 u ₁ = 1, u ₂ = 3, u ₃ = 3

con z = 0; alla base {x 2 , u 1 } `e associata la soluzione di base non ammissibile u 1 = x 2 = 0 x 1 = −1, u 2 = 4, u 3 = 4

con z = 0; alla base {x 2 , u 2 } ´e associata la soluzione di base ammissibile e degenere

u ₂ = x ₂ = 0 x ₁ = 3, u ₁ = 4, u ₃ = 0

con z = 0; alla base {x 2 , u 3 } ´e associata la soluzione di base ammissibile e degenere

u 3 = x 2 = 0 x 1 = 3, u 1 = 4, u 2 = 0

con z = 0. Si noti che le due basi degeneri rappresentano la stessa soluzione di base.

Le soluzioni di base ammissibili sono importanti per il seguente risultato.

Osservazione 7 Le soluzioni di base ammissibili coincidono con i vertici di S a .

Dimostrazione Le soluzioni di base sono ottenute ponendo a 0 le n varia- bili in base y 1 , . . . , y n e quindi una soluzione di base appartiene a n iperpiani generatori y 1 = 0, . . . , y n = 0 che, per definizione di base, sono tra loro li- nearmente indipendenti. Inoltre l’ammissibilit´ a garantisce che la soluzione di base appartenga a S _a e quindi ` e un vertice di S _a .

In Figura 1.3 si vede come la soluzione di base O ammissibile relativa alla base {x 1 , x ₂ } `e un vertice di S a e lo stesso per la soluzione di base A cor- rispondente alle basi {x 2 , u <sub>2</sub> } e {x 2 , u <sub>3</sub> }. Notiamo anche che dal punto di vista geometrico le soluzioni di base degeneri coincidono con i vertici che appartengono a pi` u di n iperpiani generatori. Nell’esempio, dove n = 2, il vertice degenere A appartiene a 3 iperpiani generatori.

Vogliamo ora vedere come ci si pu` o spostare da una base verso una ad

essa adiacente. Ci` o corrisponde all’operazione di cardine.

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@

@ @

Sa

O

A B

C

U1=0 U3=0 U2=0

Figura 1.3:

1.3.1 L’operazione di cardine

Suppponiamo di avere una base

{y 1 , . . . , y _{h −1} , y _h , y _h+1 , . . . , y _n }

cui ` e associata la Tabella 1.7. Supponiamo ora di voler creare una base adiacente a questa togliendo y h dalla base e sostituendolo con y n+k . Per prima cosa ci si deve chiedere se l’insieme di variabili

{y 1 , . . . , y h −1 , y n+k , y h+1 , . . . , y n }

`

e una base (si ricordi che non ` e sufficiente che sia formata da n variabili, ma

occorre anche che sia soddisfatta una condizione di indipendenza lineare tra

Tabella 1.7:

y 1 · · · y h · · · y n

y _n+1 α ₁₁ · · · α _1h · · · α _1n β ₁ .. . .. . .. . .. . .. . .. . .. . y _n+k α _k1 · · · α _kh · · · α _kn β _k

.. . .. . .. . .. . .. . .. . .. . y n+m α m1 · · · α mh · · · α mn β m

z γ 1 · · · γ h · · · γ n γ 0

gli iperpiani corrispondenti). Si pu` o dimostrare che ` e una base se e solo se α _kh 6= 0. Vogliamo ora determinare la nuova tabella relativa a questa base.

Dall’equazione

y n+k = α k1 y 1 + · · · + α kh y h + · · · + α kn y n + β k

possiamo ricavare y h come combinazione lineare delle variabili y ₁ , . . . , y _{h −1} , y _n+k , y _h+1 , . . . , y _n

pi` u un termine noto:

y h = − α k1

α kh

y 1 − · · · + 1 α kh

y n+k − · · · − α kn

α kh

y n − β k

α kh

. (1.6) A questo punto possiamo prendere le altre equazioni per i 6= k

y n+i =

n

X

j=1,j 6=h

α ij y j + α ih y h + β i ,

e quella per la variabile z z =

n

X

j=1,j 6=h

γ _j y _j + γ _h y _h + γ ₀

e sostituire le occorrenze di y h con la formula (1.6). Fatti un po’ di calcoli si ottiene per i 6= k

y _n+i =



α _i1 − α ih

α _k1 α kh



y ₁ + · · ·+ α _ih α kh

y _n+k + · · ·+



α _in − α ih

α _kn α kh

 y _n +



β _i − α ih

β _k α kh

 , e, per la variabile z,

z =

 γ ₁ − γ h

α _k1 α kh



y ₁ + · · ·+ γ _h α kh

y _n+k + · · ·+

 γ _n − γ h

α _kn α kh

 y _n +

 γ ₀ − γ h

β _k α kh



.

La nuova tabella sar` a quindi la Tabella 1.8.

Tabella 1.8:

y 1 · · · y n+k · · · y n

y n+1

h

α 11 − α 1h α

α

i · · · ^α _α

· · · h

α 1n − α 1h α

α

i h

β 1 − α 1h β

α

i

.. . .. . .. . .. . .. . .. . .. .

y h − _α ^α

· · · _α ¹

· · · − ^α _α

− _α ^β

.. . .. . .. . .. . .. . .. . .. .

y _n+m h

α _m1 − α mh α

α

i · · · ^α _α

· · · h

α _mn − α mh α

α

i h

β _m − α mh β

α

i

z h

γ 1 − γ h α

α

i · · · _α ^γ

· · · h

γ n − γ h α

α

i h

γ 0 − γ h β

α

i

1.3.2 I passi dell’algoritmo del simplesso

Siamo ora pronti a descrivere una generica iterazione dell’algoritmo del sim- plesso. Si suppone di avere a disposizione la base ammissibile {y 1 , . . . , y _n } (β _i ≥ 0, i = 1, . . . , m) con la relativa Tabella 1.7. Non sempre si avr`a su- bito a disposizione una base ammissibile. Ci porremo per` o solo in seguito il problema di trovarne una. Per ora supporemo che la nostra base sia gi` a ammissibile.

Passo 1 - Verifica di ottimalit` a Si verifichi se la soluzione di base cor- rente sia ottima o meno. La verifica si effettua controllando i valori γ <sub>j</sub> , j = 1, . . . , n, dell’ultima riga, detti anche coefficienti di costo ridotto delle variabili in base. Condizione sufficiente perch´ e la soluzione sia ottima ` e che essi siano tutti ≤ 0. Se la condizione

γ _j ≤ 0 j = 1, . . . , n

`

e soddisfatta restituisco la soluzione di base corrente y j = 0 j = 1, . . . , n y n+i = β i i = 1, . . . , m

come soluzione ottima. Se la condizione non ` e soddisfatta, si vada al Passo 2.

Motivazione Dalla tabella sappiamo che

z = γ ₁ y ₁ + · · · + γ n y _n + γ ₀ (1.7) Nella soluzione di base corrente il valore dell’obiettivo z ` e pari a γ 0 , ottenuto sostituendo y j = 0, j = 1, . . . , n, in (1.7). Inoltre, in S a , dove y j ≥ 0, j = 1, . . . , n, si ha

z = γ 1

|{z}

≤0

y 1

|{z}

≥0

+ · · · + γ n

|{z}

≤0

y n

|{z}

≥0

+γ 0 ≤ γ 0

e quindi γ 0 ` e il valore massimo dell’obiettivo raggiungibile in S a . Passo 2 - Scelta della colonna del cardine Se non possiamo conclu-

dere che la soluzione ` e ottima, esiste almeno un γ i > 0. In particolare consideriamo

γ h = max {γ j } > 0.

(se pi` u γ i assumono il valore massimo si seleziona, per convenzione, il primo da sinistra). La variabile y h sar` a la variabile da far uscire di base e quindi la colonna h ` e la colonna del cardine.

Motivazione Se voglio far crescere z devo selezionare una variabile y _h con γ _h > 0.

Passo 3 - Verifica di illimitatezza Verifico se il problema non ha solu- zioni ottime in quanto l’obiettivo ` e illimitato. Una condizione suffi- ciente per l’illimitatezza dell’obiettivo ` e che

α _ih ≥ 0 i = 1, . . . , m,

cio` e tutti gli elementi lungo la colonna del cardine sono non negativi.

Se la condizione ` e soddisfatta, posso concludere che S ott = ∅ in quanto l’obiettivo ` e illimitato. Se la condizione non ` e soddisfatta, si vada al Passo 4.

Motivazione Se faccio crescere y h e tengo fisso le altre variabili in base, cio` e y j = 0, j = 1, . . . , n, j 6= h, avr`o:

y _n+i = α _ih

|{z} ≥0

y _h

|{z}

≥0

+β _i ≥ β i ≥ 0 ∀ y h ≥ 0

z = γ h

|{z}

>0

y h + γ 0 −→

|{z}

y

→+∞

+ ∞.

Passo 4 - Scelta della riga del cardine Sia y _n+k una variabile fuori ba- se con α kh < 0 e tale che

β k

−α kh

= min

 β i

−α ih

: α _ih < 0



(se il minimo ` e ottenuto in corrispondenza di pi` u di una variabile si sceglie, per convenzione, la prima dall’alto). La variabile y n+k sar` a la variabile da far entrare in base e quindi la riga relativa sar` a la riga del cardine.

Motivazione Facendo crescere y _h avr` o per α _ih ≥ 0 y n+i = α ih

|{z}

≥0

y h

|{z}

≥0

+β i ≥ β i ≥ 0 ∀ y h ≥ 0

ma per le variabili y n+i con α ih < 0, si ha che y _n+i = α _ih

|{z}

<0

y _h

|{z}

≥0

+β _i ≥ 0 solo per 0 ≤ y h ≤ − β _i α ih

.

Se voglio rimanere in S a posso far crescere y h solo fino al minimo dei valori − _α ^β

per α _ih < 0.

Passo 5 - operazione di cardine Eseguo l’operazione di cardine con car- dine α kh (che ` e < 0 e quindi, come richiesto, anche 6= 0). Ottengo la Tabella 1.8 e con la nuova tabella e la nuova base ritorno al Passo 1.

La seguente osservazione mostra la situazione al termine di un’iterazione dell’algoritmo del simplesso.

Osservazione 8 Si noti che al termine di un’iterazione dell’algoritmo del simplesso si ha che:

1. la nuova base ` e adiacente alla precedente;

2. la nuova base ` e anch’essa ammissibile (si veda la motivazione del Passo 4);

3. se β k > 0, la soluzione di base (il vertice) relativo alla nuova base (quella ottenuta sostituendo y h con y n+k ) ` e diversa dalla soluzione di base relativa alla vecchia base. Se β k = 0, allora la nuova e la vecchia base rappresentano la stessa soluzione di base.

4. Se β _k > 0, il valore dell’obiettivo per la nuova soluzione di base ` e su- periore rispetto al valore dell’obiettivo γ 0 della vecchia base. Infatti, il nuovo valore dell’obiettivo, che si legge in basso a destra nella Tabella 1.8, ` e:

γ 0 − γ h

|{z}

>0

z}|{ β k

>0

α kh

|{z}

<0

> γ 0 .

Una conseguenza di questa osservazione ` e la seguente.

Osservazione 9 Se non ci sono vertici degeneri, allora l’algoritmo del simplesso termina in un numero finito di iterazioni.

Dimostrazione Se non ci sono vertici degeneri, allora ad ogni iterazione

β k > 0 e quindi in base ai punti 3. e 4. dell’Osservazione 8 si ha che il nuovo

vertice ` e distinto e con valore dell’obiettivo strettamente maggiore rispetto

al precedente. Essendo finito il numero di vertici (si veda l’Osseravzione 3), anche l’algoritmo del simplesso deve terminare in un numero finito di iterazioni.

Nel caso ci siano vertici degeneri si pu` o verificare la situazione di ciclaggio.

Nell’esempio in Figura 1.4 trovandoci nel vertice degenere A rappresenta- to dalla base {u 1 , u 2 }, l’algoritmo del simplesso pu`o generare la seguente sequenza di basi che rappresentano tutte lo stesso vertice A:

{u 1 , u ₂ } → {u 1 , u ₄ } → {u 2 , u ₄ } → {u 2 , u ₃ } → {u 1 , u ₂ }.

Una volta tornato nella base {u 1 , u 2 } questa sequenza di basi verr`a di nuovo ripetuta all’infinito senza che l’algoritmo termini. Anche se non le vedremo, esistono comunque delle regole particolari per la scelta del cardine, dette regole anticiclaggio, che consentono all’algoritmo di terminare in un numero finito di iterazioni.

J

J J

J J

J J

J J

J J

J J











 J 

J

z

Sa

U1=0 U2=0 U3=0

U4=0

A

Figura 1.4:

1.3.3 Interpretazione geometrica del cambio di base nel simplesso

Da un punto di vista geometrico il passaggio dalla base {y 1 , . . . , y h , . . . , y n } alla base {y 1 , . . . , y n+k , . . . , y n } ha la seguente interpretazione. Facciamo crescere la sola variabile y h mentre teniamo tutte le altre variabili y j , j = 1, . . . , n, j 6= h, fisse a 0. Quindi ci spostiamo sullo spigolo di S a individuato dagli n − 1 iperpiani generatori

y j = 0, j = 1, . . . , n, j 6= h.

Muovendoci lungo questo spigolo ci arrestiamo solo quando una variabile furoi base y _n+k diventa uguale a 0, ovvero quando incontriamo l’iperpiano y _n+k = 0. Quindi ci arrestiamo in corrispondenza del vertice intersezione dei seguenti iperpiani generatori

y n+k = 0, y j = 0, j = 1, . . . , n, j 6= h.

1.3.4 Sufficienza della condizione di ottimalit` a

Descrivendo la condizione di ottimalit` a γ _j ≤ 0, j = 1, . . . , n, al Passo 1.

dell’algoritmo del simplesso, si ` e detto che ` e solo una condizione sufficiente.

Infatti, (nel solo caso degenere) pu` o succedere che una base abbia come soluzione di base una soluzione ottima ma non soddisfi tale condizione. Nel seguente esempio

max x 1

x ₁ ≤ 0 x 2 ≤ 1 x 1 , x 2 ≥ 0

si pu` o verificare che la base {x 1 , x 2 } corrsiponde a una soluzione di base che ` e anche soluzione ottima, ma non soddisfa le condizioni di ottimalit` a.

D’altra parte la base {u 1 , x 2 } che rappresenta la stessa soluzione di base, soddisfa tali condizioni. Vale la seguente osservazione.

Osservazione 10 Dato un vertice ottimo, esiste sempre almeno una base che lo rappresenta che soddisfa le condizioni di ottimalit` a.

1.3.5 Unicit` a della soluzione ottima

Quando l’algoritmo del simplesso termina, ci restituisce una soluzione di

base (un vertice) ottimo. Ci si pu` o chiedere se tale soluzione ottima sia

unica oppure no. Nella tabella ottima si ha che la condizione di ottimalit` a γ j ≤ 0 j = 1, . . . , n,

`

e soddisfatta, ma sono possibili i seguenti casi.

Caso 1 γ _j < 0, j = 1, . . . , n : in tal caso si ha per l’obiettivo z z = γ 1

|{z}

<0

y 1

|{z}

≥0

+ · · · + γ n

|{z}

<0

y n

|{z}

≥0

+γ 0 ≤ γ 0

e il valore γ 0 ` e raggiungibile solo se tutte le variabili y j sono pari a 0 e quindi solo in corrispondenza del vertice ottimo. Di conseguenza, tale vertice ` e anche l’unica soluzione ottima.

Caso 2 Esiste h tale che γ _h = 0. In tal caso si possono avere i seguenti sottocasi:

Caso 2.1 α _ih ≥ 0 per ogni i = 1, . . . , m. In tal caso y n+i = α ih

|{z}

≥0

y h

|{z}

≥0

+β i ≥ β i ≥ 0 ∀ y h ≥ 0

z = γ h

|{z}

=0

y h + γ 0 = γ 0 ∀ y h ≥ 0

quindi posso far crescere y h all’infinito senza mai uscire da S a e con l’obiettivo sempre pari al valore ottimo γ 0 . Quindi abbiamo uno spigolo illimitato di soluzioni ottime.

Caso 2.2 Esistono α _ih < 0 ma per ogni α _ih < 0 si ha β _i > 0. In tal caso non posso far crescere y _h all’infinito ma fino ad un certo valore positivo (il valore dato dal criterio dei minimi rapporti visto nel Passo 4. dell’algoritmo del simplesso). Quindi esiste certamente uno spigolo limitato di soluzioni ottime.

Caso 2.3 esiste k tale che α kh < 0 e β k = 0. In tal caso non possia- mo dire nulla sull’esistenza di altre soluzioni ottime senza altre informazioni.

Come esercizio si riconoscano nelle Tabelle 1.9-1.13, tutte ottime, i casi

descritti sopra.

Tabella 1.9:

x 1 x 2

u ₁ -1 -1 1

u ₂ -1 0 1

z -1 -1 0

Tabella 1.10:

x 1 x 2

u ₁ 1 1 1

u ₂ 1 0 2

z -1 0 0

Tabella 1.11:

x ₁ x ₂ u 1 -1 -1 1

u 2 -1 0 1

z -1 0 0

Tabella 1.12:

x ₁ x ₂ x ₃

u 1 -1 1 0 0

u 2 1 -1 0 0

u 3 0 0 -1 2

z 0 0 -1 0

Tabella 1.13:

x 1 x 2 x 3

u ₁ -1 0 0 0

u 2 0 -1 0 0

u 3 0 0 -1 0

z 0 -1 -1 0

1.3.6 Come ottenere una soluzione di base ammissibile

L’algoritmo del simplesso richiede di avere all’inizio una soluzione di base ammissibile. Non sempre per` o questa ` e a disposizione (e a volte non esiste neppure). Vedremo ora due procedure, la fase di avvicianmento a S a e il metodo due fasi, che consentono di determinere (se esiste) una base ammi- sibile con cui cominciare ad utilizzare l’algoritmo del simplesso. Per prima vedremo la fase di avvicinamento a S a .

Fase di avvicinamento a S a

Supponiamo di avere una base {y 1 , . . . , y n } non ammissibile (cio´e con al- meno un valore β _i negativo). Vogliamo ora descrivere una procedura che ci consenta di stabilire se S _a = ∅ oppure che ci restituisca una base ammissi- bile, la fase di avvicinamento a S _a (in seguito vedremo anche il metodo due fasi). Un’iterazione della fase di avvicinamento a S _a segue i seguenti passi.

Passo 1 Si scelga la riga r con β r < 0 il pi´ u piccolo possibile (se vi ´ e pi´ u di una riga con β i minimo si seleziona, per convenzione, la prima tra queste dall’alto).

Passo 2 Se

α _rj ≤ 0 j = 1, . . . , n (1.8) allora possiamo concludere che S a = ∅. Infatti si avrebbe in S a che

y n+r = α r1

|{z}

≤0

y 1

|{z}

≥0

+ · · · + α rn

|{z}

≤0

y n

|{z}

≥0

+β r ≤ β r < 0,

da cui y n+r non pu´ o mai essere ≥ 0 come invece ´e richiesto per l’ap- partenenza a S a . Se invece la condizione (1.8) non ´ e soddisfatta si vada al Passo 3.

Passo 3 Si scelga come colonna del cardine la prima colonna h da sinistra tale che α rh > 0.

Passo 4 Come riga del cardine si scelga la seguente:

• Se esiste almeno una riga i tale che α ih < 0 e β i ≥ 0, allora si selezioni come riga del cardine la riga k tale che α kh < 0 e β k ≥ 0 e

− β k

α kh

= min



− β i

α ih

, α ih < 0, β i ≥ 0

 .

(se il minimo si trova in corrispondenza di pi´ u righe si sceglie,

per convenzione, la prima dall’alto).