Capitolo 1 Introduzionetiziano19661.interfree.it/pdf0910/ricerca0910.pdf · La nascita della...

Capitolo 1

Introduzione

1.1 Introduzione storica

La nascita della Ricerca Operativa e dovuta ad esigenze di tipo militare,durante gli anni che precedettero la seconda guerra mondiale. Infatti la dis-ciplina si occupa essenzialmente della pianificazione ottimale di un progettoche consiste nel migliore uso possibile delle risorse disponibili. Fu in GranBretagna che, negli anni compresi tra il 1935 ed il 1937, si inizio a stu-diare la possibilita di applicare modelli di tipo matematico a problemi diordine strategico e tattico collegati alla difesa nazionale. In particolare ilprimo problema considerato fu legato all’istallazione dei primi radar nelladifesa antiaerea, in particolare era vitale studiare la localizzazione di tali ap-parati in modo tale che fosse garantita la massima copertura del territorioma fosse anche reso minimo il numero di istallazioni. Fu proprio durantel’attuazione di tale progetto, detto Biggin Hill Experiment, che A.P. Rowe,soprintendente della Bawdsey Research Station, nel 1938, nel descrivere inuna relazione tecnica conclusiva del progetto, il tipo di attivita sviluppata,utilizzo l’espressione Operational Research. Nel 1939, Patrick Maynard Stu-art Blackett, fisico e professore presso l’Universita di Manchester, fu chiamatoa costituire un gruppo di ricerca, composto da scienziati e militari, impeg-nato nella lotta contro i sommergibili tedeschi. In questo caso il problemaera quello di determinare il numero e la posizione delle navi militari impeg-nate nella scorta dei convogli civili. Il successo ottenuto da questo gruppo,passato alla storia, produsse il risultato di moltiplicare, nel Regno Unitoe negli altri Paesi alleati, gruppi di ricerca aventi caratteristiche simili. Si

1

CAPITOLO 1. INTRODUZIONE 2

Materiale ferroso A B CSilicio (%) 4.00 1.00 0.60Manganese (%) 0.45 0.50 0.40Costo (Euro / kg.) 0.025 0.030 0.018

Tabella 1.1: Caratteristiche dei materiali ferrosi.

stima che nel corso della seconda guerra mondiale furono complessivamenteimpegnati, nel Regno Unito, in Canada e negli USA, oltre 700 scienziati; iltermine del conflitto dunque determino una riconversione dell’approccio, finoad allora usato per soli fini bellici, orientandolo verso problematiche di tipocivile (come la localizzazione dei depositi industriali, il mixing di carico diun servizio di autotrasporto). Nei settori piu propriamente civili, la Ricer-ca Operativa riprese tecniche note nel settore industriale, migliorandole edarricchendole con l’uso di strumenti matematici e di conoscenze organizza-tive: si occupo della standardizzazione della produzione, di problemi connessialla pianificazione e programmazione industriale. Nel Regno Unito la ricon-versione avvenne prevalentemente nel settore pubblico, con studi relativi aitrasporti ferroviari, stradali ed urbani. Attualmente le tematiche inerenti laRicerca Operativa, ed in particolare la parte che viene detta programmazionelineare, costituiscono uno dei piu importanti aspetti della Matematica Appli-cata. Nei paragrafi successivi saranno descritti alcuni problemi classici dellaprogrammazione lineare.

Un problema di miscelazione

Una fonderia deve produrre 1000 pezzi del peso ciascuno di un chilogrammo.Il ferro con cui tali pezzi sono fatti dovra contenere manganese e silicio nelleseguenti quantita:

0, 45% ≤manganese, 3, 25% ≤ silicio ≤ 5.5%.

Sono disponibili tre tipi di materiale ferroso le cui caratteristiche sono ripor-tate nella tabella 1.1. Inoltre si puo aggiungere direttamente manganese alcosto di 10 Euro al kg. Il problema che si vuole modellare e quello di deter-minare il piano di produzione che minimizza il costo del materiale utilizzato.Si vuole cioe individuare le quantita di materiale per ciascuno dei tre tipi A,B, o C e di manganese puro da acquistare per produrre i 1000 pezzi richiesti,


spendendo il meno possibile. Proviamo a costruire un modello analitico peril problema. A questo scopo introduciamo le variabili x1, x2, x3, x4, aventi ilseguente significato:x1(≥ 0): la quantita in kg di materiale ferroso A da utilizzare;x2(≥ 0): la quantita in kg di materiale ferroso B da utilizzare;x3(≥ 0): la quantita in kg di materiale ferroso C da utilizzare;x4(≥ 0): la quantita in kg di manganese da utilizzare.Abbiamo imposto che le quantita di prodotto acquistate siano dei valori nonnegativi (vincoli di nonnegativita). Esistono poi altri vincoli che dovrannoessere rispettati e che descriviamo di seguito. Il numero totale di kg prodottideve essere 1000:

x1 + x2 + x3 + x4 = 1000.

La quantita di silicio, in kg, presente nel prodotto risultante e data da

0.04x1 + 0.01x2 + 0.006x3

che deve essere tale da essere compresa nei limiti voluti (cioe deve esseresuperiore a 32.5 kg su 1000 kg di prodotto finito e inferiore a 55 kg nellastessa quantita di prodotto):

32.5 ≤ 0.04x1 + 0.01x2 + 0.006x3 ≤ 55.

Possiamo quindi esprimere la condizione sulla percentuale di silicio mediantei due vincoli lineari

4x1 +x2 +0.6x3 ≥ 32504x1 +x2 +0.6x3 ≤ 5500.

Analogamente, per la condizione sulla percentuale di manganese (che deveessere superiore a 4.5 kg su 1000 kg di prodotto) si ottiene

0.0045x1 + 0.005x2 + 0.004x3 + x4 ≥ 4.5

e quindi0.45x1 + 0.5x2 + 0.4x3 + 100x4 ≥ 450.

Infine il costo complessivo del prodotto risultante e

0.025x1 + 0.030x2 + 0.018x3 + 10x4.


Il problema della determinazione di un piano di produzione che minimizza ilcosto puo quindi essere formulato come segue:

min Z = 0.025x1 + 0.030x2 + 0.018x3 + 10x4

4x1 +x2 +0.6x3 ≥ 32504x1 +x2 +0.6x3 ≤ 55000.45x1 +0.5x2 +0.4x3 +100x4 ≥ 450x1 +x2 +x3 +x4 = 1000

xi ≥ 0, i = 1, 2, 3, 4.

Le variabili x1, x2, x3 e x4 corrispondono alle scelte operative che il problemareale richiede di compiere, e ciascun vincolo del modello corrisponde ad unacondizione imposta dal problema reale. Determinare i valori delle variabili inmodo che i vincoli siano soddisfatti e la funzione obiettivo assuma il minimovalore fornisce il miglior piano di produzione.

Il problema della dieta

Supponiamo di avere n alimenti (o classi di alimenti, carne, pesce, uova,legumi e altri) ed m sostanze nutritive che essi contengono (per esempioproteine, vitamine, carboidrati e altre). Si vuole determinare la quantitagiornaliera che una persona deve assumere di ciascun alimento in modo taleche venga minimizzato il costo giornaliero del cibo ma che sia salvaguardatala quantita minima di ogni sostanza nutriente di cui un uomo ha bisogno. Atal scopo definiamo le variabili decisionali del problema:xj = quantita giornaliera del j−esimo alimento, per j = 1, . . . , n.I dati del problema sono i seguenti:cj = costo unitario del j−esimo alimento, per j = 1, . . . , n;aij = quantita dell’i−esimo nutriente presente nel j−esimo alimento, peri = 1, . . . ,m e j = 1, . . . , n.bi = fabbisogno minimo giornaliero dell’i−esimo nutriente, per i = 1, . . . ,m.Il costo complessivo degli alimenti e

Z =n

∑

j=1

cjxj.


L’obiettivo e quello di determinare le quantita xj, j = 1, . . . , n, in modo taleche venga minimizzato il valore di Z, purche le quantita dell’i−esimo nutri-ente sia superiore al valore minimo giornaliero bi. In definitiva il problemapuo essere formulato nel seguente modo:

min Z =n

∑

j=1

cjxj

Soggetto a:

n∑

j=1

aijxj ≥ bi, i = 1, . . . ,m

xj ≥ 0, j = 1, . . . , n.

Il problema dello zaino

Sia dato un insieme E di n elementi, a ciascuno dei quali sia assegnato unpeso ai ed un valore ci, i = 1, . . . , n, interi e positivi. Il problema dellozaino (KP, da Knapsack Problem) consiste nel determinare un sottoinsiemedi elementi che abbia valore totale massimo ed il cui peso totale non superiun prefissato intero b. Il nome deriva dal fatto che viene usualmente descrittocome il problema di scegliere quali oggetti di un dato insieme mettere in unozaino in modo da non superare un dato peso (o capacita) e da massimizzareappunto il valore complessivo degli oggetti selezionati. Si assume che sia

0 < b <n

∑

i=1

ai,

altrimenti il problema sarebbe banale e che inoltre sia

ai ≤ b, i = 1, . . . , n

in quanto nessun elemento di peso superiore alla capacita b puo far parte diuna soluzione e quindi ogni elemento di peso superiore a b puo essere eliminatoda E. Il problema puo essere scritto come un problema di massimo. Possiamoformulare il problema come uno di programmazione lineare introducendo, perogni oggetto i = 1, 2, . . . , n, una variabile xi ∈ {0, 1}, con il significato che


la variabile assume valore 1 se l’elemento i-esimo appartiene al sottoinsiemeselezionato, e 0 altrimenti (si decide cioe se inserire o meno l’oggetto). Lacondizione relativa alla capacita dello zaino diviene

n∑

i=1

aixi ≤ b

infatti, dato che ciascuna xi puo assumere solo i valori 0 o 1, nella som-ma vengono considerati i pesi dei soli oggetti selezionati. Analogamente, lafunzione obiettivo, da massimizzare, e

Z =n

∑

i=1

cixi

nella funzione obiettivo si somma il valore dei soli oggetti selezionati. Laformulazione finale del problema e la seguente

max Z =n

∑

i=1

cixi

n∑

i=1

aixi ≤ b

xi ∈ {0, 1}.

Un problema di scheduling del personale

Una fabbrica sta riorganizzando il proprio personale su 5 turni di lavoroche coprono l’intero arco delle 24 ore. Non appare chiaro tuttavia quantopersonale deve essere assegnato a ciascun turno considerando che, duranteil giorno, le esigenze richieste dai servizi offerti sono diverse in funzione deidiversi momenti della giornata. In prima analisi sono stati definiti i seguentiturni:Turno 1: dalle 6.00 alle 14.00Turno 2: dalle 8.00 alle 16.00Turno 3: dalle 12.00 alle 20.00Turno 4: dalle 16.00 alle 24.00Turno 5: dalle 22.00 alle 6.00.Inoltre, per il numero minimo di lavoratori che devono essere presenti nellediverse fasce orarie della giornata e per i relativi costi di un’unita di personalesono stati individuati i seguenti dati:


TurnoFascia oraria 1 2 3 4 5 Addetti

6.00-8.00 × 408.00-10.00 × × 7010.00-12.00 × × 6512.00-14.00 × × × 8014.00-16.00 × × 6516.00-18.00 × × 7018.00-20.00 × × 8020.00-22.00 × 4022.00-24.00 × × 5024.00-6.00 × 15

Costo per addetto 170$ 160$ 175$ 180$ 200$

Il problema e determinare il numero di dipendenti che devono essere assegnatia ciascun turno in modo tale da minimizzare il costo complessivo e superandoil numero minimo di persone che devono essere presenti in ciascuna fasciaoraria.E evidente in questo caso definire le seguenti variabili:

xj = numero di dipendenti assegnati al turno j, j = 1, 2, 3, 4, 5.

Il vincolo principale per i possibili valori di queste variabili e che il loronumero presente durante ogni intervallo di tempo deve superare i valori ri-portati nell’ultima colonna. Per esempio dalle 8.00 alle 10.00 sono in servizioi dipendenti del secondo e del terzo turno e la loro somma deve superare 70:

x2 + x3 ≥ 70.

La funzione da minimizzare e il costo complessivo giornaliero che e la sommadei costi relativi ai dipendenti assegnati a ciascun turno, quindi:

minimizzare Z = 170x1 + 160x2 + 175x3 + 180x4 + 200x5


mentre i vincoli sono:

x1 ≥ 40x1 +x2 ≥ 70x1 +x2 ≥ 65x1 +x2 +x3 ≥ 80

x2 +x3 ≥ 65x3 +x4 ≥ 70x3 +x4 ≥ 80

x4 ≥ 40x4 +x5 ≥ 70

x5 ≥ 15

e inoltrexj ≥ 0, j = 1, . . . , 5

ed xj variabile intera per ogni j. Si puo osservare come alcuni vincoli nonsiano necessari. Per esempio i vincoli di nonnegativita per x1 e x4 sonoridondanti in virtu del primo e dell’ottavo vincolo, cosı come anche il terzovincolo, a causa della presenza del secondo (se la somma tra x1 e x2 devesuperare 70 e chiaro che supera anche 65).

Capitolo 2

Programmazione lineare

2.1 Introduzione

Gli esempi esaminati nel capitolo introduttivo definiscono problemi di pro-grammazione lineare. In questo caso il termine programmazione deve essereinteso come sinonimo di pianificazione, mentre la parola lineare indica chetutte le funzioni matematiche che compaiono nel modello sono di tipo lineare.La programmazione lineare riguarda quindi la pianificazione di alcune attiv-ita al fine di ottenere il risultato migliore, ovvero l’uso ottimale delle risorsedisponibili. Dal punto di vista matematico il modello consiste nel deter-minare il valore assunto da un determinato insieme di variabili, x1, x2, . . . , xn,dette variabili decisionali, in modo tale che sia massimizzato il valore assuntoda una funzione lineare

Z = c1x1 + c2x2 + · · · + cnxn

detta funzione obiettivo. Sulle variabili decisionali sono posti una serie divincoli anch’essi di tipo lineare, detti vincoli funzionali (o strutturali):

a11x1 +a12x2 + . . . +a1nxn ≤ b1

a21x1 +a22x2 + . . . +a2nxn ≤ b2

......

......

am1x1 +am2x2 + . . . +amnxn ≤ bm.

A questo si aggiungono vincoli di nonnegativita per le variabili decisionali:xi ≥ 0, i = 1, . . . , n. Il numero di variabili decisionali e indipendente dalnumero di vincoli strutturali. Il tipo di problema appena definito viene detto

9

CAPITOLO 2. PROGRAMMAZIONE LINEARE 10

in forma standard quando bi ≥ 0 per ogni i. E possibile ovviamente definireproblemi che hanno caratteristiche differenti da quanto visto, per esempiosi potrebbe porre il problema di minimizzare la funzione obiettivo, oppurequalche vincolo potrebbe essere in forma di uguaglianza

ai1x1 + ai2x2 + · · · + ainxn = bi

oppure con differente verso nella disuguaglianza

ai1x1 + ai2x2 + · · · + ainxn ≥ bi,

oppure potrebbe mancare qualche vincolo di nonnegativita oppure si potrebberichiedere che una variabile sia intera oppure binaria. Una qualunque asseg-nazione di valore alle variabili decisionali e detta soluzione. Una soluzioneammissibile e una soluzione che soddisfa tutti i vincoli (sia funzionali che dinonnegativita). Una soluzione non ammissibile e una soluzione che viola al-meno un vincolo. La soluzione ottima e quella che fornisce il valore miglioreper la funzione obiettivo (cioe il massimo o il minimo in funzione del tipodi problema da risolvere). L’insieme delle soluzioni ammissibili e detto re-gione ammissibile, o regione di ammissibilita, e costituisce un sottoinsiemedello spazio R

n, se n e il numero di variabili decisionali. Tale regione puoessere un sottoinsieme limitato, illimitato o addirittura vuoto se non ci sonosoluzioni ammissibili.

2.2 Il metodo grafico

Quando un problema ha soltanto due variabili decisionali, per esempio x1 ex2, allora e possibile risolverlo per via grafica. Tale tecnica consiste nel trac-ciare, nel piano (x1, x2) (cioe x1 ascissa e x2 ordinata), i contorni della regioneammissibile. Si considerano quindi i vincoli uno per uno e si identificano leregioni del piano contenenti i punti che soddisfano tale vincolo e che vengonointesecate con la regione gia identificata. I vincoli di nonnegativita x1, x2 ≥ 0restringono la ricerca della regione di ammissibilita al primo quadrante delpiano cartesiano.


Consideriamo ora il seguente problema di programmazione lineare:

max Z = 3x1 + 5x2

x2 ≤ 3x1 +x2 ≤ 5

−x1 +x2 ≤ 2x1 ≥ 0, x2 ≥ 0.

Rappresentiamo graficamente le regioni del piano (x1, x2) che sono identifi-cate dai vincoli del problema.

x2 ≤ 3

x1

x2

x1 + x2 ≤ 5

x1

x2

(5, 0)

(2, 3)


−x1 + x2 ≤ 2

x1

x2

(5, 0)

(2, 3)(1, 3)

(0, 2)

x1

x2

Z = 10

Z = 15

Z = 18

Z = 21

Si ricava ora la variabile x2 dall’espressione della funzione obiettivo

Z = 3x1 + 5x2 ⇒ x2 = −3

5x1 +

1

5Z.


L’equazione della funzione obiettivo in forma esplicita rappresenta un fasciodi rette parallele aventi coefficiente angolare −3/5 ed ordinata del punto diintersezione con l’asse x2 pari a Z/5. Assegnando qualche valore a Z si puodeterminare in quale direzione di tale fascio il valore aumenta. In questo mo-do il valore massimo della funzione obiettivo viene assunto necessariementenel vertice della regione ammissibile che viene incontrato per ultimo proce-dendo nella direzione del fascio di rette che aumenta il valore di Z. PonendoZ = 0 la retta del fascio passa per l’origine del riferimento cartesiano mentrela retta passante per il punto (0, 2) ha valore Z = 10. I valori di Z crescono(come era prevedibile) in corrispondenza di rette del fascio che si muovonoverso la direzione delle ordinate crescenti. Quindi:nel punto (1, 3) si ha Z = 18;nel punto (5, 0) si ha Z = 15;nel punto (2, 3) si ha Z = 21.La soluzione ottima e proprio il punto (2, 3) in cui la funzione obiettivo as-sume valore Z = 21.Osserviamo che se nell’esempio precedente il problema fosse stato

max x1 + x2

soggetto ai medesimi vincoli allora tutte le soluzioni sarebbero state i pun-ti appartenenti al segmento congiungente (5, 0) e (2, 3), cioe le soluzionesarebbero state infinite.

2.2.1 Alcune osservazioni sul metodo grafico

Come abbiamo avuto modo di osservare il metodo grafico si puo applicarequando il problema ha due variabili (o anche tre, ma in questo caso e ben piucomplesso). Esso consente tuttavia una serie di osservazioni che sono valideanche nel caso in cui le variabili decisionali sono di piu. Infatti la soluzione sitrova sempre sulla frontiera della regione ammissibile ed e localizzata in unvertice. Inoltre le soluzioni possono essere infinite (cioe possiamo avere unospigolo della regione ammissibile composto da soluzioni ottime). Se i vincolifossero stati i seguenti:

−x1 +x2 ≤ 12x1 −3x2 ≤ 4

x1 ≥ 0, x2 ≥ 0.

allora la regione ammissibile sarebbe stata la seguente


x1

x2

(0, 1)

(2, 0)

cioe una regione illimitata superiormente allora anche la funzione obiettivosarebbe stata illimitata e quindi la soluzione sarebbe stata Z = +∞, quindiil problema di massimo non avrebbe avuto soluzione. Se invece si fosseroconsiderati i vincoli opposti, cioe

−x1 +x2 ≥ 12x1 −3x2 ≥ 4

x1 ≥ 0, x2 ≥ 0.

allora la regione ammissibile sarebbe stata vuota e quindi anche in questocaso non ci sarebbe stata soluzione.


2.3 Il Metodo del Simplesso

Il metodo del simplesso e una procedura di tipo algebrico che si applica aproblemi di programmazione lineare in forma standard, cioe tali che

1. Funzione obiettivo da massimizzare2. Vincoli funzionali (o strutturali) nella forma ≤3. Vincoli di nonnegativita per le variabili decisionali4. Termini noti bi nonnegativi.

In termini matematici il problema e il seguente

max Z = c1x1 + c2x2 + · · · + cnxn

a11x1 +a12x2 + . . . +a1nxn ≤ b1

a21x1 +a22x2 + . . . +a2nxn ≤ b2

......

......

am1x1 +am2x2 + . . . +amnxn ≤ bm

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

ed inoltre bi ≥ 0 (o, meglio bi > 0), i = 1, . . . ,m.Si definisce frontiera del vincolo la retta (o meglio l’iperpiano se abbiamo nvariabili decisionali) che segna il confine tra i punti che soddisfano il vincolostesso e quelli che non lo soddisfano. I punti di intersezione tra le frontieredei vincoli sono detti vertici. I vertici ammissibili sono i vertici che apparten-gono alla regione ammissibile mentre i vertici non ammissibili sono quelli chenon appartengono alla regione ammissibile. Le variabili xi che definiscono leincognite del problema sono dette, come abbiamo visto variabili decisionali.In un problema di programmazione lineare con n variabili decisionali, duevertici si dicono adiacenti se condividono le frontiere di n − 1 vincoli. Duevertici adiacenti sono collegati attraverso un segmento che giace sulla fron-tiera comune e che viene detto spigolo della regione ammissibile. Una delleidee alla base del metodo del simplesso e la proprieta che la soluzione ottimae sempre uno dei vertici della regione ammissibile, e inoltre se si consideraun qualsiasi problema di programmazione lineare che possiede almeno unasoluzione ottima allora se un vertice non ha vertici adiacenti migliori (val-utati attraverso la funzione obiettivo), allora deve essere necessariamente lasoluzione ottima.


2.3.1 Risoluzione del problema

Il metodo del simplesso opera, a grandi linee, nel seguente modo:1. Si sceglie uno dei vertici della regione ammissibile;2. Si verifica se tale vertice e una soluzione ottima;3. Se il vertice non e una soluzione ottima allora si sposta l’analisi consideran-do il vertice adiacente ammissibile migliore e ripetendo il procedimento.Consideriamo il seguente problema di programmazione lineare:

max Z = 3x1 + 5x2

x1 ≤ 42x2 ≤ 12

3x1+ 2x2 ≤ 18x1 ≥ 0, x2 ≥ 0.

Tracciamo la regione ammissibile ed identifichiamo i suoi vertici.

x1

x2

(4, 0)

(4, 3)

(2, 6)(0, 6)

(0, 0)

(0, 9)

(6, 0)

(4, 6)


Chiaramente solo i vertici (0, 0), (4, 0), (4, 3), (0, 6) e (2, 6) sono ammissibili,mentre gli altri tre (6, 0), (4, 6) e (0, 9) non lo sono.In questo esempio il metodo del simplesso effettua i seguenti passi:1) Si sceglie il vertice (0, 0) come vertice ammissibile iniziale;2) In (0, 0) il valore della funzione obiettivo e Z = 0. I vertici adiacentiammissibili sono (4, 0) e (0, 6). Nel primo vertice il valore della funzione obi-ettivo e Z = 12, mentre nel secondo e Z = 30. Quindi (0, 0) non e soluzioneottima.3) Si sceglie (0, 6) come vertice ammissibile.4) Vertici adiacenti ammissibili sono (0, 0) e (2, 6). Ovviamente si deve con-trollare il valore della funzione obiettivo solo nel secondo vertice in cui Z =36. Quindi (0, 6) non e soluzione ottima.5) Si sceglie (2, 6) come vertice ammissibile.6) Vertici adiacenti ammissibili sono (0, 6) e (4, 3). Si deve controllare il val-ore della funzione obiettivo solo nel secondo vertice in cui Z = 27. Poichein (0, 6) il valore della fuzione obiettivo e Z = 30 allora il vertice (2, 6) esoluzione ottima.Il metodo del simplesso si basa sulle seguenti idee chiave:

1. Il metodo del simplesso concentra la sua attenzione esclusivamente suivertici.

2. Il metodo del simplesso e un algoritmo di tipo iterativo.

3. Ogni volta che e possibile si sceglie come vertice iniziale l’origine (tuttele variabili decisionali sono poste uguali a zero).

4. Considerato un determinato vertice risulta piu conveniente, da un pun-to di vista computazionale, ottenere informazioni sui vertici adiacenti.Passando da un vertice all’altro la procedura per trovare la soluzioneottima si snoda attraverso gli spigoli della regione ammissibile.

5. Dopo aver identificato il vertice ammissibile la procedura si muovelungo lo spigolo dove il tasso di incremento di Z e maggiore.

6. Un tasso di miglioramento positivo implica che il vertice adiacentee migliore di quello attuale, un tasso negativo indica invece che epeggiore. Se nessuno dei vertici adiacenti produce un tasso positivosignifica che e stata raggiunta la soluzione ottima.


2.3.2 Forma algebrica del metodo del simplesso

La procedura algebrica del metodo del simplesso si basa sulla risoluzione diun sistema di equazioni lineari. Il primo passo di inizializzazione del metodoconsiste nel convertire i vincoli funzionali di disuguaglianza in equivalen-ti vincoli di uguaglianza. Questa trasformazione avviene introducendo lecosiddette variabili slack (scarto). Per esempio

x1 ≤ 4 ⇒ 4 − x1 ≥ 0.

Ponendox3 = 4 − x1

risultax3 ≥ 0

mentre le variabili x1 e x3 soddisfano la relazione di uguaglianza

x1 + x3 = 4.

In questo modo il problema di programmazione lineare

max Z = 3x1 + 5x2

x1 ≤ 42x2 ≤ 12

3x1+ 2x2 ≤ 18x1 ≥ 0, x2 ≥ 0

diventa, in forma aumentata,

max Z = 3x1 + 5x2

x1 +x3 = 42x2 +x4 = 12

3x1+ 2x2 +x5 = 18xi ≥ 0, i = 1, 2, 3, 4, 5.

Se una variabile slack e uguale a zero, allora la soluzione corrente appartienealla frontiera del vincolo, mentre il valore della variabile slack e positivo allorala soluzione corrente si trova all’interno della regione ammissibile rispetto atale vincolo. Si definisce soluzione aumentata quella soluzione per cui allevariabili decisionali sono state aggiunte le variabili slack.


Si definisce soluzione di base (basica) un vertice cui sono stati aggiunti ivalori delle variabili slack.Si definisce soluzione basica ammissibile (in breve BFS=Basic Feasible Solu-tion) un vertice ammissibile cui sono state aggiunte le variabili slack.Osserviamo che se una soluzione ha una variabile uguale a zero questo vuoldire che appartiene ad uno degli spigoli che delimitano la regione ammissibile:

x1

x2

(4, 0)

(4, 3)

(2, 6)(0, 6)

(0, 0) x2 = 0

x4 = 0

x1 = 0

x3 = 0

x5 = 0

Quindi ogni BFS ha due variabili uguali a zero poiche soddisfa due vincoli:

(0, 0, 4, 12, 18) (0, 6, 4, 0, 6) (2, 6, 2, 0, 0)(4, 3, 0, 4, 0) (4, 0, 0, 12, 6)

Il motivo di questa proprieta sta nel fatto che, nella forma aumentata, si deverisolvere un sistema di 3 equazioni lineari in 5 incognite. Il sistema presenta,quindi, 2 gradi di liberta, cioe a due variabili possono essere assegnati valoriarbitrari. Come valore arbitrario viene scelto zero.Le due variabili poste uguali a zero sono dette variabili non di base (o nonin base) mentre le altre tre variabili sono dette variabili di base.La soluzione del sistema (cioe l’insieme delle variabili di base) e detta soluzionedi base.In una soluzione di base ogni variabile puo essere di base o non di base.


Il numero di variabili di base e uguale al numero di vincoli funzionali, mentreil numero di variabili non di base e la differenza tra il numero di variabili ed ilnumero di vincoli. Se le variabili di base soddisfano i vincoli di nonnegativitaallora la soluzione di base e una BFS. Due BFS si dicono adiacenti se tutti ivalori delle variabili non di base sono uguali (a zero) tranne uno. Per passareda una BFS (quella corrente) ad una adiacente e necessario quindi che unavariabile non di base lo diventi e viceversa.Per esempio se (0, 0, 4, 12, 18) e la BFS corrente allora (0, 6, 4, 0, 6) e adia-cente ad essa, mentre la BFS (2, 6, 2, 0, 0) non lo e.Cerchiamo ora di descrivere matematicamente, sempre facendo riferimentoall’esempio introdotto in precedenza, i passi delle singole iterazioni previstedal metodo del simplesso per risolvere un problema di programmazione li-neare. Il primo passo e quello di riscrivere le equazioni del modello, scrivendoanche la fuzione obiettivo come se fosse un vincolo:

(0) Z− 3x1− 5x2 = 0(1) x1 +x3 = 4(2) 2x2 +x4 = 12(3) 3x1+ 2x2 +x5 = 18.

Si parte da una soluzione base e si usa l’equazione (0) per calcolare il valoredella funzione obiettivo. Anche Z viene considerata come variabile semprein base.Il problema cosı come e stato scritto viene detto in forma canonica, cioe:1) Nella funzione obiettivo ci sono solo variabili non in base;2) Ogni variabile in base e presente solo in un’equazione con coefficienteuguale a 1.Il vantaggio offerto dalla prima proprieta sara chiaro tra poco mentre la se-conda proprieta consente di ottenere immediatamente il valore della variabilein base presente nell’equazione che e uguale al termine noto (poiche tutte lealtre variabili che compaiono nell’equazione hanno valore zero).Scegliere l’origine come vertice ammissibile significa porre x1 = x2 = 0 cioesi considera come soluzione basica ammissibile (0, 0, 4, 12, 18). Appare chiarocome i valori delle variabili slack di questa soluzione basica vengono calcolatisfruttando le equazioni (1), (2) e (3). La funzione obiettivo calcolata nellaBFS vale 0 e, poiche le variabili slack non compaiono nel’espressione di Z, icoefficienti delle variabili non di base x1, x2 indicano il tasso di incrementodella funzione obiettivo prodotto da un eventuale aumento del valore di talivariabili. Poiche i tassi di miglioramento, cioe i coefficienti di x1 e x2, sono


positivi si puo concludere che (0, 0, 4, 12, 18) non e soluzione ottima.Passo 1 della singola iterazione: Stabilire la direzione dello spostamen-to.Incrementare il valore di una variabile non di base rispetto al valore zerocorrente (pur adattando i valori in modo tale da soddisfare i vincoli) cor-risponde a muoversi lungo uno spigolo che inizia dal vertice ammissibile. Lascelta della variabile non di base viene fatta osservando l’espressione dellafunzione obiettivo:

Z = 3x1 + 5x2.

Aumentare x1 significa che il tasso di miglioramento della funzione obiettivoe 3, mentre per x2 e 5. Appare chiaro che conviene scegliere x2 come variabileentrante in base.Passo 2 della singola iterazione: Criterio di arresto.Bisogna ora determinare il valore da assegnare alla variabile entrante senzache la nuova soluzione basica esca dalla regione di ammissibilita. Il valoredella variabile non di base x1 resta zero.

(1) x1 +x3 = 4 x3 = 4(2) 2x2 +x4 = 12 x4 = 12 − 2x2

(3) 3x1 +2x2 +x5 = 18 x5 = 18 − 2x2.

La nonnegativita delle variabili impone dei vincoli sulle relazioni appenascritte:

x3 = 4 ≥ 0 Nessun limite su x2

x4 = 12 − 2x2 ≥ 0 x2 ≤ 12/2 = 6

x5 = 18 − 2x2 ≥ 0 x2 ≤ 18/2 = 9.

Quindi il valore di x2 puo essere incrementato fino a 6, valore che rende lavariabile attualmente in base x4 = 0. Oltre tale valore x4 assume valore neg-ativo violando l’ammissibilita della soluzione. Questi calcoli costituisconoquello che e noto come test del minimo rapporto. Obiettivo di tale test edeterminare quale variabile di base assume per prima il valore zero all’au-mentare del valore della variabile entrante. Si possono escludere da tale testtutte quelle variabili associate ad equazioni in cui il coefficiente della varia-bile entrante e zero oppure negativo. Quindi per ogni equazione in cui ilcoefficiente della variabile entrante e strettamente positivo, il test calcola il


rapporto tra il termine noto ed il coefficiente della variabile entrante. La va-riabile di base nell’equazione con il minimo rapporto e quella che raggiungeper prima il valore 0 e quindi rappresenta, di fatto, la variabile uscente dallabase. Nell’esempio fatto entra x2 ed esce x4.Passo 3 della singola iterazione: Ottenere la nuova BFS.La situazione determinata dal passo 2 del metodo del simplesso e schematiz-zata nella seguente tabella:

BFS iniziale Nuova BFSVariabili di base x3 = 4, x4 = 12, x5 = 18 x2 = 6, x3 =?, x5 =?

Variabili non di base x1 = 0, x2 = 0 x1 = 0, x4 = 0

Il sistema

(0) Z −3x1 −5x2 = 0(1) x1 +x3 = 4(2) 2x2 +x4 = 12(3) 3x1 +2x2 +x5 = 18

deve essere scritto ora in forma canonica, cioe ogni variabile in base devecomparire solo in un’equazione e con coefficiente uguale a 1 e nell’equazione(0) i coefficienti delle variabili in base devono essere uguali a zero. La trasfor-mazione puo avvenire effettuando delle opportune combinazioni lineari tra leequazioni del problema attraverso il cosiddetto metodo di Gauss-Jordan.Innanzitutto dividiamo l’equazione (2) per 2 ottenendo la nuova secondaequazione:

(2′) x2 +1

2x4 = 6.

Per eliminare il coefficiente di x2 dall’equazione (3) sottraiamo dall’equazione(3) l’equazione (2) (oppure l’equazione (2′) moltiplicata per 2):

(3) 3x1 +2x2 +x5 = 18 −

(2) 2x2 x4 = 12

(3′) 3x1 −x4 +x5 = 6.

L’equazione (1) resta invariata perche il coefficiente di x2 e gia uguale azero. Ora dobbiamo eliminare il coefficiente della variabile entrante in base


dall’equazione (0), sommando all’equazione (0) l’equazione (2′) moltiplicataper 5 :

(0) Z −3x1 −5x2 = 0 +

5x2 +5

2x4 = 30

(0′) Z −3x1 +5

2x4 = 30.

Il sistema e diventato quindi

(0) Z −3x1 +5

2x4 = 30

(1) x1 +x3 = 4

(2) x2 +1

2x4 = 6

(3) 3x1 −x4 +x5 = 6.

Dalle equazioni (1) e (2) rispettivamente si ricava che x5 = 6 e x3 = 4. Quindila nuova BFS e (0, 6, 4, 0, 6). Si osservi che le variabili di base appaiono soloognuna in un’equazione con coefficiente 1.Test di ottimalita:Effettuando il test di ottimalita sulla nuova funzione obiettivo

Z = 3x1 −5

2x4 + 30

si deduce che e necessaria una seconda iterazione poiche il coefficiente di x1

e positivo, infatti la variabile entrante deve essere proprio x1. Per calcolarela variabile uscente dobbiamo effettuare il test del rapporto tra le equazioni(1), (2) e (3).

(1) x3 = 4 − x1 ≥ 0 x1 ≤ 4

(2) x2 = 6 ≥ 0 Nessun limite su x2

(3) x5 = 6 − 3x1 ≥ 0 x1 ≤ 6/3 = 2.

Da tale test risulta che la variabile uscente e x5.


BFS precedente Nuova BFSVariabili di base x2 = 6, x3 = 4, x5 = 6 x1 = 2, x2 = 6, x3 =?

Variabili non di base x1 = 0, x4 = 0 x4 = 0, x5 = 0

Il sistema

(0) Z −3x1 +5

2x4 = 30

(1) x1 +x3 = 4

(2) x2 +1

2x4 = 6

(3) 3x1 −x4 +x5 = 6

deve essere trasformato in modo tale che i coefficienti della colonna relativaalla variabile entrante x1 siano uguali a quelli della colonna relativa alla va-riabile uscente x5, quindi bisogna rendere 1 il coefficiente di x1 nell’equazione(3) ed eliminare quelli di x1 dalle equazioni (0) e (1). L’equazione (3) vienedivisa per 3 e diventa:

(3) x1 −1

3x4 +

1

3x5 = 2.

Il sistema e diventato

(0) Z −3x1 +5

2x4 = 30

(1) x1 +x3 = 4

(2) x2 +1

2x4 = 6

(3) x1 −1

3x4 +

1

3x5 = 2.


Sottraiamo l’equazione (3) dalla (1):

(1) x1 +x3 = 4 −

(3) x1 −1

3x4 +

1

3x5 = 2

(1′) x3 +1

3x4 −

1

3x5 = 2

e sommiamo all’equazione (0) la (3) moltiplicata per 3:

(0) Z −3x1 +5

2x4 = 30 +

(3) 3x1 −x4 +x5 = 6

(0′) Z +3

2x4 +x5 = 36.

Il sistema e diventato

(0) Z +3

2x4 +x5 = 36

(1) x3 +1

3x4 −

1

3x5 = 2

(2) x2 +1

2x4 = 6

(3) x1 −1

3x4 +

1

3x5 = 2

Dalla (1) segue che x3 = 2 quindi la nuova BFS e (2, 6, 2, 0, 0) da cui siottiene il valore della funzione obiettivo Z = 36 che e ottimo perche tutti icoefficienti dell’equazione (0)

Z = −3

2x4 − x5 + 36

sono negativi quindi non e possibile trovare nessuna direzione di ulteriorecrescita.


2.3.3 Forma tabellare del metodo del simplesso

La forma tabellare del metodo del simplesso consente di organizzare i datidel problema in modo sintetico e avendo in forma compatta tutte le infor-mazioni che consentono di effettuare le iterazioni previste dal metodo. Nellatabella, detta anche tableau, compaiono, riga per riga, i coefficienti di tuttele equazioni del problema, compresa l’equazione (0) (che sarebbe la funzioneobiettivo). In ogni colonna sono riportati tutti i coefficienti relativi ad unastessa variabile ed i termini noti bi. Nella prima colonna e specificata la va-riabile in base presente nell’equazione riportata nella riga, ovviamente perl’equazione (0) si suppone che la variabile in base sia Z. Consideriamo ilseguente problema:

max Z = x1 + 2x2 + x3

x1 +x2 +3x3 ≤ 62x1 +3x2 +x3 ≤ 15

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Introduciamo le variabili slack x4 e x5, cosicche, in forma aumentata, ilsistema algebrico diventa:

(0) Z −x1 −2x2 −x3 = 0(1) x1 +x2 +3x3 +x4 = 6(2) 2x1 +3x2 +x3 +x5 = 15,

con vincolo di nonnegativita su tutte le variabili. Il tableau iniziale delmetodo del simplesso e il seguente

Tableau iniziale

Var.base Eq. Z x1 x2 x3 x4 x5 bi

Z

x4

x5

(0)

(1)

(2)

1

0

0

−1

1

2

−2

1

3

−1

3

1

0

1

0

0

0

1

0

6

15

Identifichiamo in x2 la variabile entrante in base, in quanto il coefficientenegativo dell’equazione (0) piu grande in modulo e proprio quello di x2.Evidenziamo la colonna relativa alla variabile entrante in base, che vienedetta colonna pivot:


Tableau iniziale


Z

x4

x5

(0)

(1)

(2)

1

0

0

−1

1

2

−2

1

3

−1

3

1

0

1

0

0

0

1

0

6

15

A questo punto applichiamo il criterio del minimo rapporto per deciderequale variabile deve uscire dalla base attraverso i seguenti passi:1. si individuano nella colonna pivot tutti i coefficienti strettamente positivi;2. si divide il termine noto per tale coefficiente;3. si identifica il piu piccolo tra tali rapporti;4. la variabile di base corrispondente a tale riga (detta riga pivot) e quellauscente.

Tableau iniziale


Z

x4

x5

(0)

(1)

(2)

1

0

0

−1

1

2

−2

1

3

−1

3

1

0

1

0

0

0

1

0

6 → 6/1 = 6

15 → 15/3 = 5

Il criterio del minimo rapporto stabilisce che dalla base deve uscire deve uscirex5. Evidenziamo tutti i coefficienti dell’equazione relativa alla riga di x5:

Tableau iniziale


Z

x4

x5

(0)

(1)

(2)

1

0

0

−1

1

2

−2

1

3

−1

3

1

0

1

0

0

0

1

0

6

15


La colonna relativa alla variabile entrante in base deve essere resa ugualea quella della variabile uscente. Dividiamo l’equazione (2) per l’elementoche si trova all’intersezione tra le righe e le colonne evidenziate (cioe 3) edazzeriamo, con opportune combinazioni lineari tra le equazioni, i coefficientidi x2 nelle equazioni (0) e (1):

Iterazione 1


Z

x4

x2

(0)

(1)

(2)

1

0

0

1

3

1

3

2

3

0

0

1

−1

3

8

3

1

3

0

1

0

2

3

−1

3

1

3

10

1

5

Effettuiamo un’altra iterazione perche il test di ottimalita non e verificatoin quanto nell’equazione (0) e presente un coefficiente negativo. Variabileentrante e x3 mentre variabile uscente e x4 (applicando il test del minimorapporto):

Iterazione 1


Z

x4

x2

(0)

(1)

(2)

1

0

0

1

3

1

3

2

3

0

0

1

−1

3

8

3

1

3

0

1

0

2

3

−1

3

1

3

10

1

5

Dopo la seconda iterazione abbiamo il seguente tableau.

Iterazione 2


Z

x3

x2

(0)

(1)

(2)

1

0

0

3

8

1

8

5

8

0

0

1

0

1

0

1

8

3

8

−1

8

5

8

−1

8

3

8

81

8

3

8

39

8


Siamo arrivati alla soluzione ottima (0, 39/8, 3/8, 0, 0) in cui la funzione obi-ettivo vale Z = 81/8.Terminiamo questo paragrafo analizzando alcune situazioni che si possonoverificare applicando il metodo del simplesso ad un problema di program-mazione lineare.

Scelta della variabile entrante e di quella uscente

Se due, o piu, variabili non di base hanno lo stesso coefficiente negativo,massimo in valore assoluto, allora la scelta della variabile entrante puo es-sere fatta in modo arbitrario e non c’e alcun modo di sapere se tale sceltainfluenzera il numero di iterazioni necessarie a trovare la soluzione ottima.Quando invece due o piu quozienti soddisfano il test del minimo rapportovuol dire che, incrementando il valore di una variabile non in base, ci saran-no piu variabili di base che raggiungeranno simultaneamente il valore zero.Di tali variabili solo una uscira dalla base mentre l’altra, o le altre, rester-anno in base avendo un valore nullo. Tali variabili, cosı come la relativaBFS, sono dette degeneri. In presenza di BFS degeneri il cambiamento dibase puo non migliorare il valore della funzione obiettivo poiche il minimorapporto puo essere uguale a zero anche nelle iterazioni successive pertantopossono entrare in base variabili con valore uguale a zero. Una conseguenzadi tale situazione e che potrebbe percorrersi ciclicamente (e cioe all’infinito)una sequenza di basi degeneri associate allo stesso vertice. Questi casi, chein verita non derivano da problemi reali, possono essere evitati applicandoalcune regole cosiddette anticiclo che cambiano il criterio per la scelta dellevariabili entranti o uscenti dalla base. La piu nota e senz’altro la Regoladi Bland che impone di scegliere, tra le variabili candidate ad entrare o aduscire, sempre quella che ha indice minore. E possibile dimostrare che, ap-plicando la regola di Bland, il metodo del simplesso converge sempre in unnumero finito di iterazioni.

Nessuna variabile di base uscente-Z illimitata

Questa situazione si verifica quando nel tableau del metodo del simplesso adun coefficiente negativo dell’equazione (0) corrispondente ad una variabilenon di base e associata una colonna di coefficienti tutti nulli o negativi.Questo vuol dire che la variabile entrante puo essere incrementata all’infinitosenza uscire dalla regione di ammissibilita e lasciando che anche Z puo essere


aumentata all’infinito, cioe Z = +∞. Una situazione del genere si veri-fica quando e stato commesso qualche errore nella definizione del modelloutilizzato per descrivere il problema reale.

Il caso di soluzioni ottime multiple

Puo verificarsi che un problema ammetta infinite soluzioni tutte ottime (eil caso in cui due vertici adiacenti sono entrambi ottimi e quindi anche ilrelativo spigolo che li congiunge e costituito da soluzioni ottime). Questo casosi verifica quando il coefficiente di una variabile non di base nell’equazione (0)e uguale a zero e nella colonna ci sono coefficienti positivi relativi a variabiliche potrebbero uscire dalla base. Volendo si potrebbe effettuare un’ulterioreiterazione del metodo del simplesso, verificando che la funzione obiettivo noncambia valore, e trovando un altro vertice ammissibile.

2.4 Problemi di programmazione lineare in

forma non standard

Un problema di programmazione lineare in forma standard ha le seguentiproprieta:1. massimizzare Z2. vincoli ≤3. nonnegativita delle variabili3′. termini noti positivi.Se il problema non e in forma standard allora il problema principale e quello ditrovare una soluzione basica ammissibile iniziale. Infatti nella forma standardquesta viene trovata ricorrendo all’uso delle variabili slack, scegliendole comevariabili di base e ponendole uguali ai termini noti non negativi. L’approccioutilizzato nella forma non standard e l’introduzione delle variabili artificiali,che definiscono un vero e proprio problema artificiale. Analizziamo ora idiversi modi di affrontare il problema in base alle possibili difformita delproblema rispetto alla forma standard.


Termini noti negativi

Se uno dei termini noti e negativo allora l’intero vincolo puo essere moltipli-cato per −1, quindi

x1 − x2 ≤ −1

diventa−x1 + x2 ≥ 1.

Considereremo come si tratta il vincolo funzionale nella forma ≥ nei succes-sivi paragrafi, adesso analizziamo il caso di un vincolo di uguaglianza. D’orain poi si continuera a supporre che il termine noto di un vincolo sia semprepositivo (oppure nullo) e a considerare i vincoli in modo tale che rispettinosempre questa proprieta.

2.4.1 Vincoli di uguaglianza

Quando il vincolo si presenta nella forma

ai1x1 + ai2x2 + · · · + ainxn = bi

allora ci sono due possibili modi per affrontare il problema. Il primo e quellodi imporre due distinti vincoli di disuguaglianza:

ai1x1 + ai2x2 + · · · + ainxn ≤ bi

ai1x1 + ai2x2 + · · · + ainxn ≥ bi

che devono essere soddisfatti contemporaneamente. Questa tecnica sfortu-natamente ha lo svantaggio di aumentare il numero dei vincoli. Il secondometodo per affrontare i vincoli di uguaglianza e quello descritto nel seguenteparagrafo.

Il Metodo del Big M

Consideriamo ora il seguente problema in cui uno dei vincoli e di uguaglianza:

max Z = x1 + 4x2

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

x1 ≥ 0, x2 ≥ 0


che diventa, in forma aumentata,

max Z = x1 + 4x2

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

x1, x2, x3 ≥ 0.

E chiaro che non abbiamo a disposizione una BFS iniziale perche in questocaso l’origine non e un vertice ammissibile (infatti non soddisfa il secondovincolo). Per ottenere una soluzione ammissibile siamo costretti ad intro-durre una variabile x4, detta appunto variabile artificiale ed indicata in mododiverso dalle altre variabili, nel secondo vincolo.

x1 + x2 + x4 = 5.

Poiche tale variabile dovra avere valore uguale a zero nella soluzione finale(affinche il vincolo sia soddisfatto) aggiungiamo alla funzione obiettivo untermine che contiene tale variabile:

max Z = x1 + 4x2 − Mx4

dove M indica un numero molto grande. E chiaro che volendo massimizzare ilvalore della funzione obiettivo l’ultimo termine tende a decrementarlo, quindisara naturale che per neutralizzarlo la soluzione dovra essere tale che x4 = 0.Il problema modificato nel seguente modo viene detto problema artificiale:

max Z = x1 + 4x2 − Mx4

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

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

Il sistema algebrico da risolvere e:

(0) Z −x1 −4x2 +Mx4 = 0(1) −3x1 +2x2 +x3 = 4(2) x1 +x2 +x4 = 5.

Poniamo il problema in forma canonica eliminando x4 dalla funzione obi-ettivo, moltiplichiamo quindi l’equazione (2) per −M e sommiamola all’e-quazione (0):

(0) Z −x1 −4x2 +Mx4 = 0−Mx1 −Mx2 −Mx4 = −5M

(0′) −(M + 1)x1 −(M + 4)x2 = −5M


ottenendo

(0) Z −(M + 1)x1 −(M + 4)x2 = −5M(1) −3x1 +2x2 +x3 = 4(2) x1 +x2 +x4 = 5.

Applichiamo ora il metodo del simplesso a tale problema:

Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 bi

Z

x3

x4

(0)

(1)

(2)

1

0

0

−(M + 1)

−3

1

−(M + 4)

2

1

0

1

0

0

0

1

−5M

4

5

Iterazione 1


Z

x2

x4

(0)

(1)

(2)

1

0

0

−5

2M + 7

−3

2

5

2

0

1

0

M2

+ 2

1

2

−1

2

0

0

1

8 − 3M

2

3

Iterazione 1


Z

x2

x1

(0)

(1)

(2)

1

0

0

0

0

1

0

1

0

3

5

1

5

−1

5

M + 14

5

3

5

2

5

82

5

19

5

6

5

La BFS ottima e (6/5, 19/5, 0, 0) mentre il valore della funzione obiettivo eZ = 82/5.Osserviamo che se il problema fosse stato quello di minimizzare la funzione


allora la penalizzazione sulla funzione obiettivo sarebbe stata con il segnoopposto:

min Z = x1 + 4x2 + Mx4

in quanto in questo caso il termine deve penalizzare il calcolo del minimodella funzione obiettivo.Osserviamo che il metodo del Big M inizia con le variabili artificiali in base (equindi hanno inizialmente un valore diverso da zero) e termina, se il problemaammette soluzione, con le variabili artificiali fuori dalla base. Si puo pertantointerpretare il metodo del Big M come composto da due diverse fasi. Nellaprima tutte le variabili artificiali sono portate a zero in modo tale da giungeread una BFS iniziale per il problema di partenza. Nella seconda fase tutte levariabili artificiali sono mantenute a zero ed il metodo del simplesso generauna sequenza di BFS per il problema originale fino a giungere alla soluzioneottima. Il metodo del simplesso a due fasi e una procedura semplificata pereseguire le due fasi senza introdurre il valore M in modo esplicito.

2.5 Il metodo del simplesso a due fasi

Vediamo come operano le due fasi considerando il problema di program-mazione lineare introdotto nel paragrafo precedente:

max Z = x1 + 4x2

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

x1 ≥ 0, x2 ≥ 0.

Scriviamo quindi il problema nella forma aumentata introducendo una va-riabile slack e una variabile artificiale:

max Z = x1 + 4x2

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

x1, x2, x3, x4 ≥ 0.

Il problema che definisce la prima fase del metodo a due fasi deve esseretale che la sua soluzione abbia tutte le variabili artificiali (in questo caso x4)


uguali a zero, quindi:

I Fasemax Z = −x4

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

x1, x2, x3, x4 ≥ 0.

Nella seconda fase, avendo gia una BFS ammissibile, calcolata nella primafase, non e necessario l’uso di alcuna variabile artificiale, pertanto possiamoapplicare il metodo del simplesso alla funzione obiettivo del problema dipartenza:

II Fasemax Z = x1 + 4x2

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

x1, x2, x3 ≥ 0.

Applichiamo ora il metodo del simplesso al problema definito nella I fase,considerando che le variabili di base sono x3 e x4, e che la BFS iniziale e(0, 0, 4, 5). Le equazioni della I fase sono

(0) Z +x4 = 0(1) −3x1 +2x2 +x3 = 4(2) x1 +x2 +x4 = 5.

Poniamo il problema in forma canonica eliminando il coefficiente della varia-bile di base x4 dalla funzione obiettivo. Per questo sottraiamo dall’equazione(0) l’equazione (2), ottenendo le nuove equazioni:

(0) Z −x1 −x2 = −5(1) −3x1 +2x2 +x3 = 4(2) x1 +x2 +x4 = 5.

Scriviamo il tableau della iterazioni del metodo del simplesso applicato allaI fase:


Iterazione 0


Z

x3

x4

(0)

(1)

(2)

1

0

0

−1

−3

1

−1

2

1

0

1

0

0

0

1

−5

4

5

Iterazione 1


Z

x3

x1

(0)

(1)

(2)

1

0

0

0

0

1

0

5

1

0

1

0

1

3

1

0

19

5

Abbiamo ottenuto la soluzione ottima della I fase in cui il valore della funzioneobiettivo e 0 (come era atteso), la BFS (5, 0, 19) e quella iniziale per la IIfase, quindi eliminiamo la colonna relativa alla variabile x4 e sostituendol’equazione (0):

(0) Z −x1 −4x2 = 0

Tableau finale I Fase con funzione obiettivo II Fase

Var.base Eq. Z x1 x2 x3 bi

Z

x3

x1

(0)

(1)

(2)

1

0

0

−1

0

1

−4

5

1

0

1

0

0

19

5

A questo punto si elimina il coefficiente della variabile di base x1 dallafunzione obiettivo e si ottiene il tableau iniziale della II fase:


Iterazione 0


Z

x3

x1

(0)

(1)

(2)

1

0

0

0

0

1

−3

5

1

0

1

0

5

19

5

Iterazione 1


Z

x3

x1

(0)

(1)

(2)

1

0

0

0

0

1

0

1

0

3

5

1

5

−1

5

82

5

19

5

6

5

Osserviamo che la soluzione trovata coincide con quella calcolata con ilmetodo del Big M.

Minimizzazione della funzione obiettivo

Quando il problema da risolvere e la minimizzazione della funzione obiettivopuo essere trasformato in forma standard facendolo diventare di massimo.Infatti il punto in cui viene assunto il valore minimo di una funzione coincidecon quello in cui viene raggiunto il massimo dalla medesima funzione ma conil segno cambiato. Quindi

min Z =n

∑

j=1

cjxj ⇔ max −Z =n

∑

j=1

(−cj)xj

ed applicare il metodo del simplesso a tale funzione obiettivo. Si deve poiconsiderare che, una volta trovato il valore massimo di tale funzione obiettivo,per ottenere il valore del minimo voluto si dovra cambiare il suo segno.


Vincoli funzionali nella forma ≥

Consideriamo il seguente problema di programmazione lineare:

max Z = 6x1 + x2

x1 ≤ 310x1 −2x2 = 15−x1 +x2 ≥ 1

x1 ≥ 0, x2 ≥ 0.

Il problema aumentato viene definito introducendo la variabile slack x3 nelprimo vincolo e la variabile artificiale x4 nel secondo vincolo. Il terzo vin-colo viene modificato in uno di uguaglianza definendo la variabile x5, dettavariabile surplus posta uguale a:

x5 = −x1 + x2 − 1, x5 ≥ 0.

In questo modo il vincolo diventa di uguaglianza

−x1 + x2 − x5 = 1

ed e necessario aggiungere un’ulteriore variabile artificiale x6 poiche x5 nonpuo essere usata come variabile di base perche nell’equazione ha coefficiente−1 mentre la forma canonica del problema prevede che le variabili in basedebbano avere necessariamente coefficiente 1. Il problema nella forma au-mentata e il seguente:

max Z = 6x1 + x2

x1 +x3 = 310x1 −2x2 +x4 = 15−x1 +x2 −x5 +x6 = 1

x1, x2, x3, x4, x5, x6 ≥ 0.

Risolviamo prima il problema applicando il metodo del Big M introducendoinnanzitutto due termini che penalizzino le due variabili artificiali x4 e x6:

Z = 6x1 + x2 − Mx4 − Mx6

dove M rappresenta un numero positivo molto grande.Adesso e possibile applicare il metodo del simplesso con la BFS iniziale:

x1 = x2 = 0, x3 = 3, x4 = 15, x6 = 1.


Il problema artificiale e il seguente

max Z = 6x1 + x2 − Mx4 − Mx6

x1 +x3 = 310x1 −2x2 +x4 = 15−x1 +x2 −x5 +x6 = 1

x1, x2, x3, x4, x5, x6 ≥ 0.

Prima di procedere all’applicazione del metodo del simplesso e necessarioannullare, nella funzione obiettivo, i coefficienti delle variabili di base x4 ex6. Riscriviamo le 4 equazioni in forma aumentata

(0) Z −6x1 −x2 +Mx4 +Mx6 = 0(1) x1 +x3 = 3(2) 10x1 −2x2 +x4 = 15(3) −x1 +x2 −x5 +x6 = 1

e sottraiamo dall’equazione (0) l’equazione (3) moltiplicata per −M , otte-nendo

Z −6x1 −x2 +Mx4 +Mx6 = 0Mx1 −Mx2 +Mx5 −Mx6 = −M

Z +(M − 6)x1 −(M + 1)x2 +Mx4 +Mx5 = −M.

Sottraiamo dall’equazione (0) appena modificata l’equazione (2) moltiplicataper −M :

Z +(M − 6)x1 −(M + 1)x2 +Mx4 = −M−10Mx1 +2Mx2 −Mx4 = −15M

Z −(9M + 6)x1 +(M − 1)x2 +Mx5 = −16M.

Applichiamo ora i diversi passi del metodo del simplesso al seguente tableau:

Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 x5 x6 bi

Z

x3

x4

x6

(0)

(1)

(2)

(3)

1

0

0

0

−(9M + 6)

1

10

−1

M − 1

0

−2

1

0

1

0

0

0

0

1

0

M

0

0

−1

0

0

0

1

−16M

3

15

1


Iterazione 1


Z

x3

x1

x6

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

−4M+11

5

1

5

−1

5

4

5

0

1

0

0

9M+6

10

− 1

10

1

10

1

10

M

0

0

−1

0

0

0

1

−5M+18

2

3

2

3

2

5

2

Iterazione 2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

M + 7

8

−1

8

1

8

1

8

−11

4

1

4

−1

4

−5

4

M + 11

4

−1

4

1

4

5

4

127

8

7

8

17

8

25

8

Iterazione 3


Z

x5

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

11

4

1

5

M − 1

2

−1

2

0

−5

8

0

1

0

0

M

−1

0

0

51

2

7

2

3

15

2

Soluzione ottima e (3, 15/2, 0, 0, 7/2, 0) in cui la funzione obiettivo assumevalore Z = 51/2.Obiettivo della prima fase del metodo e:

Massimizzare Z = −x4 − x6


fino ad ottenere x4 = x6 = 0. Nella seconda fase invece si vuole

Massimizzare Z = 6x1 + x2

con x4 = x6 = 0. La soluzione ottima della prima fase viene utilizzata comeBFS iniziale per la seconda. L’inizializzazione del problema, che precede laprima fase, e la stessa vista per il metodo del Big M, che prevede l’intro-duzione delle variabili slack e delle variabili artificiali.Riscriviamo ora i problemi che devono essere risolti nelle due fasi.

I Fase:

max Z = −x4 − x6

x1 +x3 = 310x1 −2x2 +x4 = 15−x1 +x2 −x5 +x6 = 1

x1, x2, x3, x4, x5, x6 ≥ 0;

II Fase

max Z = 6x1 + x2

x1 +x3 = 310x1 −2x2 = 15−x1 +x2 −x5 = 1

x1, x2, x3, x5 ≥ 0.

I Fase-Iterazione 0


Z

x3

x4

x6

(0)

(1)

(2)

(3)

1

0

0

0

−9

1

10

−1

1

0

−2

1

0

1

0

0

0

0

1

0

1

0

0

−1

0

0

0

1

−16

3

15

1


I Fase-Iterazione 1


Z

x3

x1

x6

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

−4

5

1

5

−1

5

4

5

0

1

0

0

9

10

− 1

10

1

10

1

10

1

0

0

−1

0

0

0

1

−5

2

3

2

3

2

5

2

I Fase-Iterazione 2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

−1

8

1

8

1

8

0

1

4

−1

4

−5

4

1

−1

4

1

4

5

4

0

7

8

17

8

25

8

Terminata la prima fase del metodo del simplesso, prima di procedere allasuccessiva, si devono effettuare alcune operazioni sul tableau che e stato ot-tenuto. Innanzitutto devono essere eliminate le colonne relative alle variabiliartificiale, deve essere sostituita la funzione obiettivo ed il problema deveessere posto in forma canonica (cioe devono essere azzerati i coefficienti dellafunzione obiettivo relativi alle variabili in base).


Tableau Finale I Fase


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

−1

8

1

8

1

8

0

1

4

−1

4

−5

4

1

−1

4

1

4

5

4

0

7

8

17

8

25

8

Eliminazione variabili x4, x6


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

0

1

4

−1

4

−5

4

0

7

8

17

8

25

8

Sostituzione funzione obiettivo


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

−6

0

1

0

−1

0

0

1

0

1

0

0

0

1

4

−1

4

−5

4

0

7

8

17

8

25

8


Ripristino forma canonica della funzione obiettivo-Eliminaz. coeff. di x1


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

−1

0

0

1

0

1

0

0

−3

2

1

4

−1

4

−5

4

51

4

7

8

17

8

25

8

Ripristino forma canonica della funzione obiettivo-Eliminaz. coeff. di x2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

−11

4

1

4

−1

4

−5

4

127

8

7

8

17

8

25

8

A questo punto, poiche non e verificato il test di ottimalita si deve applicareil metodo del simplesso. Potrebbe anche accadere che la soluzione trovataal termine della prima fase sia gia ottima e quindi non sarebbero richiesteulteriori operazioni.

II Fase-Iterazione 0


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

−11

4

1

4

−1

4

−5

4

127

8

7

8

17

8

25

8




Z

x5

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

11

4

1

5

0

1

0

0

51

2

7

2

3

15

2

La soluzione ottima trovata e la stessa ottenuta con il metodo Big M.

Il metodo del simplesso a due fasi per problemi di minimo

Supponiamo di dover risolvere il seguente problema di minimo:

min Z = x1 + 5x2 + 4x3

x1 +3x3 = 6x1 +x2 +x3 ≥ 4

xi ≥ 0, i = 1, 2, 3.

Scriviamo quindi il problema nella forma aumentata introducendo una va-riabile surplus e due variabili artificiali:

min Z = x1 + 5x2 + 4x3

x1 +3x3 +x4 = 6x1 +x2 +x3 −x5 +x6 = 4

x1, x2, x3, x4, x5, x6 ≥ 0.

Il problema che definisce la prima fase del metodo a due fasi deve essere taleche la sua soluzione abbia tutte le variabili artificiali (in questo caso x4 e x6)uguali a zero, quindi:

I Fasemin Z = x4 + x6

x1 +3x3 +x4 = 6x1 +x2 +x3 −x5+ x6 = 4

x1, x2, x3, x4, x5, x6 ≥ 0.


Nella seconda fase si puo applicare il metodo del simplesso alla funzioneobiettivo del problema di partenza:

II Fasemin Z = x1 + 5x2 + 4x3

x1 +3x3 = 6x1 +x2 +x3 −x5 = 4

x1, x2, x3, x5 ≥ 0.

Poiche il problema e di minimo dobbiamo trasformarlo in un problema dimassimo cambiando il segno ai due membri della funzione obiettivo in en-trambi i problemi:

I Fasemax −Z = −x4 − x6

x1 +3x3 +x4 = 6x1 +x2 +x3 −x5+ x6 = 4

x1, x2, x3, x4, x5, x6 ≥ 0.

II Fasemax −Z = −x1 − 5x2 − 4x3

x1 +3x3 = 6x1 +x2 +x3 −x5 = 4

x1, x2, x3, x5 ≥ 0.

Le equazioni della I fase sono

(0) −Z +x4 +x6 = 0(1) x1 +3x3 +x4 = 6(2) x1 +x2 +x3 −x5+ x6 = 4.

Per porre in problema in forma canonica bisogna prima sottrarre dall’e-quazione (0) l’equazione (1), ottenendo le nuove equazioni:

(0) −Z −x1 −3x3 +x6 = −6(1) x1 +3x3 +x4 = 6(2) x1 +x2 +x3 −x5+ x6 = 4


e poi sottrarre dall’equazione (0) l’equazione (2), ottenendo la nuova equazione:

(0) −Z −2x1 −x2 −4x3 +x5 = −10(1) x1 +3x3 +x4 = 6(2) x1 +x2 +x3 −x5+ x6 = 4.

Adesso possiamo scrivere il tableau del metodo del simplesso:

Iterazione 0


Z

x4

x6

(0)

(1)

(2)

−1

0

0

−2

1

1

−1

0

1

−4

3

1

0

1

0

1

0

−1

0

0

1

−10

6

4

Iterazione 1


Z

x3

x6

(0)

(1)

(2)

−1

0

0

−2

3

1

3

2

3

−1

0

1

0

1

0

4

3

1

3

−1

3

1

0

−1

0

0

1

−2

2

2

Iterazione 2


Z

x3

x2

(0)

(1)

(2)

−1

0

0

0

1

3

2

3

0

0

1

0

1

0

1

1

3

−1

3

0

0

−1

1

0

1

0

2

2

Ora eliminiamo dal tableau finale della I fase le colonne relative alle variabiliartificiali e sostituiamo i coefficienti dell’equazione obiettivo della II fase:


Tableau II Fase


Z

x3

x2

(0)

(1)

(2)

−1

0

0

1

1

3

2

3

5

0

1

4

1

0

0

0

−1

0

2

2

II Fase-Eliminaz. coeff. Equazione (0)


Z

x3

x2

(0)

(1)

(2)

−1

0

0

−7

3

1

3

2

3

0

0

1

4

1

0

5

0

−1

−10

2

2



Z

x3

x2

(0)

(1)

(2)

−1

0

0

−11

3

1

3

2

3

0

0

1

0

1

0

5

0

−1

−18

2

2



Z

x3

x1

(0)

(1)

(2)

−1

0

0

0

0

1

11

2

−1

2

3

2

0

1

0

−1

2

1

2

−3

2

−7

1

3




Z

x5

x1

(0)

(1)

(2)

−1

0

0

0

0

1

5

−1

3

4

1

2

3

2

0

1

0

−6

2

6

La BFS ottima e (6, 0, 0, 0, 2, 0) mentre il valore minimo della funzione obi-ettivo e:

Z = 6.

Soluzioni non ammissibili

Nel metodo del simplesso il problema fondamentale e l’identificazione di unaBFS iniziale quando una soluzione semplice non e disponibile. L’uso di va-riabili artificiali consente di trasformare il problema in uno artificiale e lastessa tecnica consente di ottenere una BFS iniziale per tale problema. Ilmetodo del simplesso a due fasi consente di ottenere una soluzione ottimapartendo dalla BFS iniziale del problema artificiale. Tale tecnica tuttaviacontiene una possibile minaccia. Infatti potrebbe essere difficile trovare unasoluzione ammissibile perche non ce ne sono, cio nonostante, trasformandoil problema e applicando il metodo del simplesso, questo trova una soluzioneapparentemente ottima. Esiste un modo per verificare quando tale situazionesi verifica: infatti se il problema originale non ha soluzioni ammissibili, allorasia il metodo del Big M che la prima fase del metodo del simplesso a duefasi forniscono una soluzione finale che ha almeno una variabile artificialemaggiore di zero. In caso contrario queste devono essere tutte uguali a zero.Consideriamo per esempio il seguente problema di programmazione lineare:

max Z = 6x1 + x2

x1 +x2 ≥ 52x1 +x2 = 2

x1 ≥ 0, x2 ≥ 0


e scriviamo direttamente il problema artificiale

max Z = 6x1 + x2

x1 +x2 −x3 +x4 ≥ 52x1 +x2 +x5 = 2

x1, x2, x3, x4, x5 ≥ 0.

L’applicazione del metodo del simplesso a due fasi implica la risoluzione deiseguenti problemi:

I Fasemax Z = −x4 − x5

x1 +x2 −x3 +x4 ≥ 52x1 +x2 +x5 = 2

x1, x2, x3, x4, x5 ≥ 0;

II Fasemax Z = 6x1 + x2

x1 +x2 −x3 ≥ 52x1 +x2 = 2

x1, x2, x3 ≥ 0.

Le equazioni della prima fase sono:

(0) Z +x4 +x4 = 0(1) x1 +x2 −x3 +x4 = 5(2) 2x1 +x2 +x5 = 2

Trasformiamo il problema della prima fase in forma canonica eliminandodalla funzione obiettivo i coefficienti delle variabili di base x4 e x5. Primasottraiamo dall’equazione (0) l’equazione (1)

Z +x4 +x5 = 0−x1 −x2 +x3 −x4 = −5

Z −x1 −x2 +x3 +x5 = −5.

Poi sottraiamo dall’equazione (0) l’equazione (2)

Z −x1 −x2 +x3 +x5 = −5−2x1 −x2 −x5 = −2

Z −3x1 −2x2 +x3 = −7.

Applichiamo il metodo del simplesso al problema definito nella prima fase:


I Fase-Iterazione 0


Z

x4

x5

(0)

(1)

(2)

1

0

0

−3

1

2

−2

1

1

1

−1

0

0

1

0

0

0

1

−7

5

2

I Fase-Iterazione 1


Z

x4

x1

(0)

(1)

(2)

1

0

0

0

0

1

−1

2

1

2

1

2

1

−1

0

3

2

−1

2

1

2

3

2

0

1

−4

4

1

I Fase-Iterazione 2


Z

x4

x1

(0)

(1)

(2)

1

0

0

1

−1

2

0

0

1

1

−1

0

2

−1

1

2

−1

1

−3

3

2

Il test di ottimalita e verificato quindi il metodo ha trovato (apparente-mente) la soluzione per il problema definito nella prima fase, soluzione otti-ma che e (2, 0, 0, 3, 0). Tuttavia La variabile artificiale x4 e rimasta in base equesto vuol dire che il problema di partenza non ammette alcuna soluzioneammissibile e quindi neanche quella ottima.


2.5.1 Variabili che possono assumere valori negativi

Nella maggior parte dei problemi che si presentano nella pratica valori ne-gativi per le variabili decisionali non hanno senso, tuttavia possono essercideterminati modelli in cui cio e possibile. Esiste una tecnica molto sempliceper convertire tale problema in forma canonica e con vincoli di nonnegativitaper le variabili.

Variabili con un limite inferiore

Supponiamo che sia definito il seguente vincolo

xj ≥ Lj

dove Lj < 0. Effettuiamo il seguente cambio di variabile

x′

j = xj − Lj,

in modo tale che x′

j ≥ 0. Al posto di xj viene usato x′

j +Lj in ogni equazionedel modello. La stessa tecnica puo essere usata se Lj e positivo. Vediamoneun esempio: sia assegnato il seguente problema:

max Z = 3x1 + 5x2

x1 ≤ 42x2 ≤ 12

3x1+ 2x2 ≤ 18x1 ≥ −10, x2 ≥ 1.

Definiamo le variabili

x′

1 = x1 + 10, x′

2 = x2 − 1, x′

1, x′

2 ≥ 0,

cosicchex1 = x′

1 − 10, x2 = x′

2 + 1

ed il problema diventa

max Z = 3(x′

1 − 10) + 5(x′

2 + 1)x′

1 − 10 ≤ 42(x′

2 + 1) ≤ 123(x′

1 − 10) + 2(x′

2 + 1) ≤ 18x′

1 ≥ 0, x′

2 ≥ 0


e quindimax Z = 3x′

1 + 5x′

2 − 25x′

1 ≤ 142x′

2 ≤ 103x′

1+ 2x′

2 ≤ 46x′

1 ≥ 0, x′

2 ≥ 0.

Variabili senza un esplicito limite inferiore

Se la variabile xj non ha un esplicito limite inferiore allora e necessariosostituire ad xj la differenza tra due nuove variabili nonnegative

xj = x+

j − x−

j , x+

j , x−

j ≥ 0.

Ogni BFS per la nuova forma del modello ha la proprieta che x+

j = 0 oppurex−

j = 0 (oppure possono essere entrambe nulle). Nella soluzione ottenuta conil metodo del simplesso si ha:

x+

j =

xj se xj ≥ 0;

0 altrimenti,x−

j =

|xj| se xj ≤ 0;

0 altrimenti.

Per esempio nel problema di programmazione lineare

max Z = 3x1 + 5x2

x1 ≤ 42x2 ≤ 12

3x1+ 2x2 ≤ 18x2 ≥ 0

poniamo x1 = x+1 − x−

1 cosicche il problema diventa

max Z = 3x+1 − 3x−

1 + 5x2

x+1 −x−

1 ≤ 42x2 ≤ 12

3x+1 −3x−

1 + 2x2 ≤ 18x+

1 , x−

1 , x2 ≥ 0.

Questa tecnica ha lo svantaggio di incrementare il numero di variabili de-cisionali rispetto al problema originale. Infatti se nessuna variabile avesse


limite inferiore il loro numero raddoppierebbe. Questo approccio puo es-sere modificato in modo tale da aggiungere solo una variabile decisionale almodello. Infatti ad ogni variabile non limitata inferiormente si puo sostituire

xj = x′

j − x′′, x′

j, x′′ ≥ 0,

in cui x′′ rappresenta sempre la stessa variabile. L’interpretazione di x′′ inquesto caso e che −x′′ rappresenta il valore attuale della piu grande (in ter-mini assoluti) variabile originale negativa, cosicche x′

j rappresenta di quantoxj eccede tale valore.

Capitolo 3

Analisi Postottimale

3.1 Introduzione

I problemi di programmazione lineari che vengono studiati dalla ricerca op-erativa non sono altro se non modelli matematici che descrivono casi reali ela cui soluzione deve fornire utili informazioni per poter migliorare processidi produzione oppure ottenere un aumento degli utili a parita di risorse. Ilprocesso che e stato brevemente accennato nel primo capitolo prevede chesiano effettuati una serie di passi che possono essere riassunti nel seguenteelenco:1. Definizione del problema e raccolta dati;2. Formulazione del modello matematico;3. Sviluppo di un metodo per determinare la soluzione del modello;4. Test del modello ed eventuali variazioni del modello.Le fasi 2, 3 e 4 devono essere viste come se fossero inserite in un loop cheprevede che il modello matematico sia soggetto ad una serie di raffinamentisuccessivi che lo rendano il piu aderente possibile al caso reale in modo taleche le sue soluzioni coincidano con quelle reali. In questa prima parte delcapitolo cercheremo di capire quali sono le informazioni che si possono es-trarre dall’applicazione del metodo del simplesso ad un problema di program-mazione lineare nell’ottica di effettuare variazioni al modello matematico inesame.

55

CAPITOLO 3. ANALISI POSTOTTIMALE 56

3.2 Prezzi ombra

I problemi di programmazione lineare sono la formulazione matematica dimodelli di situazioni reali che richiedono un’opportuna sperimentazione perpoter arrivare alla definizione finale del problema che tenga conto corretta-mente di tutti i parametri reali e che fornisca, una volta risolto, la soluzioneottima del caso pratico. Tale periodo sperimentale significa che spesso saranecessario risolvere un problema, valutare i risultati, verificare l’aderenza diquesti al caso reale, modificare opportunamente il modello e ripetere lo stes-so procedimento finche i risultati sono quelli attesi. Appare chiaro che taleprocesso richiede la risoluzione di una serie di problemi matematici che spessohanno dimensioni molto elevate e sono molto simili tra loro. Pertando risultamolto conveniente valutare, spesso a posteriori, come varia la soluzione di unproblema di programmazione lineare al variare di alcuni parametri. Le causeche richiedono tale analisi a posteriori possono essere, tra le altre, le seguenti:

1. Debugging del modello (cioe trovare eventuali debolezze o errori nelmodello)

2. Validazione del modello (cioe verificare se i risultati sono aderenti allarealta)

3. Decisioni del management sull’allocazione delle risorse (prezzi ombra)

4. Valutazione delle stime dei parametri del modello.

Un approccio molto utilizzato per affrontare questi problemi e quello dellacosiddetta Riottimizzazione, che consiste nel dedurre come le variazioni nelladefinizione del modello influenzano il risultato ottenuto. Se si risolve il pro-blema di programmazione lineare utilizzando il metodo del simplesso allorasi puo cercare di dedurre la variazione nella soluzione ottima studiando iltablaeu finale oppure utilizzando la soluzione ottima del modello precedentecome BFS iniziale per quello modificato (purche risulti ancora ammissibile).Un classico problema di programmazione lineare prevede la risoluzione delproblema di massimo

max Z = c1x1 + c2x2 + · · · + cnxn

che puo essere interpretato come la volonta di rendere massimo il profittoZ, in funzione delle quantita xi (n e il numero di delle merci che vengono


prodotte ed xi e la quantita prodotta, mentre ci e il profitto della singolaunita di merce prodotta). Ovviamente le quantita prodotte devono esserevincolate alle risorse disponibili. Le risorse sono m e, per ognuna di queste,vale il seguente vincolo

ai1x1 + ai2x2 + · · · + ainxn ≤ bi

in cui bi rappresenta la disponibilita della i−esima risorsa: per esempio setale risorsa e una fabbrica oppure il reparto di un’azienda allora bi puo essereil tempo il management aziendale destina affinche questa risorsa produca edi valori aij sono il tempo che tale risorsa usa per produrre la j−esima merce.I valori dei parametri appena indicati potrebbero essere soggetti a variazionipoiche potrebbe essere scopo dell’azienda quello di valutare l’opportunitadi modificare il loro valore e valutare il conseguente tasso di variazione delprofitto.A questo scopo consideriamo ora il seguente problema di programmazionelineare:

max Z = x1 + x2

20x1 +3x2 ≤ 5010x1 +3x2 ≤ 30

x2 ≤ 4x1 ≥ 0, x2 ≥ 0.

Tracciamo ora nel piano (x1, x2) la regione ammissibile di tale problema:


• •

•

••

x1

x2

(5/2, 0)

(2, 10/3)

(9/5, 4)(0, 4)

(0, 0)

Secondo vincolo

Primo vincolo

Terzo vincolo

Per risolvere il problema calcoliamo il valore della funzione obiettivo neivertici della regione ammissibile

(0, 4) Z = 4

(

9

5, 4

)

Z =29

5

(

2,10

3

)

Z =16

3.

Il vertice (9/5, 4) e soluzione ottima in quanto il valore della funzione obi-ettivo nei suoi vertici adiacenti e inferiore al valore Z = 29/5. Risolviamoora lo stesso problema applicando il metodo del simplesso. Introduciamo tre


variabili slack (una per ogni vincolo) e risolviamo il problema aumentato:

max Z = x1 + x2

20x1 +3x2 +x3 = 5010x1 +3x2 +x4 = 30

x2 +x5 = 4xi ≥ 0, i = 1, 2, 3, 4, 5.

Iterazione 0


Z

x3

x4

x5

(0)

(1)

(2)

(3)

1

0

0

0

−1

20

10

0

−1

3

3

1

0

1

0

0

0

0

1

0

0

0

0

1

0

50

30

4

Iterazione 1


Z

x3

x4

x2

(0)

(1)

(2)

(3)

1

0

0

0

−1

20

10

0

0

0

0

1

0

1

0

0

0

0

1

0

1

−3

−3

1

4

38

18

4

Iterazione 2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

10

−2

1

10

0

7

10

3

− 3

10

1

29

5

2

9

5

4


Soluzione ottima, come atteso, in forma aumentata, e:

(

9

5, 4, 2, 0, 0

)

ed il valore della funzione obiettivo e Z = 29/5. Poniamo attenzione aicoefficienti delle variabili slack del tableau finale (evidenziati in rosso) eponiamo

y∗

1 = 0, y∗

2 =1

10, y∗

3 =7

10,

e ricordiamo che ogni variabile slack viene associata ad un determinato vin-colo.Risolviamo ora lo stesso problema, cambiando pero il termine noto dell’ulti-mo vincolo, che diventa 5:

max Z = x1 + x2

20x1 +3x2 ≤ 5010x1 +3x2 ≤ 30

x2 ≤ 5x1 ≥ 0, x2 ≥ 0.

Tracciamo ora nel piano (x1, x2) la regione ammissibile di tale problema,evidenziando in blu la parte di tale regione che e stata aggiunta rispetto alproblema precedente:


• •

•

••

x1

x2

(5/2, 0)

(2, 10/3)

(3/2, 5)(0, 5)

(0, 0)

Secondo vincolo

Primo vincolo

Terzo vincolo

Il nuovo problema aumentato e il seguente:

max Z = x1 + x2

20x1 +3x2 +x3 = 5010x1 +3x2 +x4 = 30

x2 +x5 = 5xi ≥ 0, i = 1, 2, 3, 4, 5.

Applichiamo ora il metodo del simplesso, evidenziando in blu le parti ditableau che sono cambiate rispetto al problema precedente.


Iterazione 0


Z

x3

x4

x5

(0)

(1)

(2)

(3)

1

0

0

0

−1

20

10

0

−1

3

3

1

0

1

0

0

0

0

1

0

0

0

0

1

0

50

30

5

Iterazione 1


Z

x3

x4

x2

(0)

(1)

(2)

(3)

1

0

0

0

−1

20

10

0

0

0

0

1

0

1

0

0

0

0

1

0

1

−3

−3

1

4

35

15

5

Iterazione 2


Z

x3

x1

x2

(0)

(1)

(2)

(3)

1

0

0

0

0

0

1

0

0

0

0

1

0

1

0

0

1

10

−2

1

10

0

7

10

3

− 3

10

1

13

2

5

3

2

5

Soluzione ottima, come atteso, in forma aumentata, e:(

3

2, 5, 5, 0, 0

)

mentre il valore della funzione obiettivo e Z1 = 13/2. Calcoliamo ora ladifferenza tra i valori delle funzioni obiettivo ottenute nei due problemi:

∆Z = Z1 − Z =13

2−

29

5=

7

10= y∗

3.


Il valore y∗

i definito in precedenza viene detto prezzo ombra per la risorsai e misura il valore marginale della risorsa, cioe il tasso di incremento diZ ottenuto aumentando la disponibilita della i−esima risorsa. Il metododel simplesso identifica il prezzo ombra come il valore del coefficiente dellai−esima variabile slack nell’equazione (0) del tableau finale.L’analisi dei prezzi ombra puo essere fatta anche graficamente quando ilproblema ha solo due variabili decisionali. Nell’esempio visto in precedenzaincrementando il valore di b3 aumenta il tasso di profitto solo se b3 ≤ 10.Aumentando oltre tale valore il valore massimo della funzione obiettivo noncambiera piu poiche la soluzione ottima non soddisfera il vincolo sotto formadi uguaglianza (infatti la frontiera del secondo vincolo interseca l’asse x2

nel punto (0, 10)). Dall’analisi del prezzo ombra y∗

1 = 0 si deduce che unincremento della prima risorsa non cambia la soluzione ottima (infatti questanon soddisfa il primo vincolo in forma di uguaglianza).

3.3 Il Metodo del Simplesso Rivisitato (Fa-

coltativo)

Un modo utile per comprendere meglio le operazioni effettuate dal metododel simplesso e quello di scrivere il metodo in forma matriciale, introducendoi vettori:

c =

c1

c2

...cn

, x =

x1

x2

...xn

, b =

b1

b2

...bm

e la matrice

A =

a11 a12 . . . a1n

a21 a22 . . . a2n

......

...am1 am2 . . . amn

in modo tale che il problema possa essere scritto come

max Z = cTxAx ≤ bx ≥ 0


Per ottenere la forma aumentata del problema si introduce il vettore xS dellevariabili slack,

xS =

xn+1

xn+2

...xn+m

cosicche i vincoli diventano

[

A , I]

[

xxS

]

= b

con[

xxS

]

≥ 0.

La BFS viene ottenuta ponendo le variabili non di base del vettore di n + melementi [x xS]T uguali a zero. Eliminando tali variabili rimane un sistemadi m equazioni in m incognite

BxB = b (3.1)

dove il vettore

xB =

xB1

xB2

...xBm

e ottenuto da [x xS] eliminando le variabili non di base mentre la matrice

B =

B11 B12 . . . B1m

B21 B22 . . . B2m

......

...Bm1 Bm2 . . . Bmm

e ottenuta da [A , I] eliminando le colonne corrispondenti alle variabili nondi base. Il metodo del simplesso introduce in base le variabili per cui Be non singolare, cioe tali che esiste B−1. Risolvere il sistema (3.1) significasostanzialmente invertire la matrice B e calcolare il vettore

xB = B−1b.


Indicando con cB il vettore i cui elementi sono i coefficienti della funzioneobiettivo corrispondenti agli elementi di xB allora il valore della funzioneobiettivo per la soluzione di base e:

Z = cTBxB = cT

BB−1b.

Considerando l’esempio introdotto all’inizio del capitolo possiamo eviden-ziare, nelle diverse iterazioni, i valori della matrice B e dei vettori xB.Inizialmente i vettori sono:

c =

11000

, b =

50304

, x =

[

x1

x2

]

, xS =

x3

x4

x5

la matrice delle equazioni:

[A, I] =

20 3 1 0 010 3 0 1 00 1 0 0 1

.

Iterazione 0:

xB =

x3

x4

x5

B =

1 0 00 1 00 0 1

= B−1

xB = B−1b =

1 0 00 1 00 0 1

50304

=

50304

,

Z = cTBxB =

[

0 0 0]

50304

= 0.

Iterazione 1:

xB =

x3

x4

x2


B =

1 0 30 1 30 0 1

, B−1 =

1 0 −30 1 −30 0 1

xB = B−1b =

1 0 −30 1 −30 0 1

50304

=

38184

,

Z = cTBxB =

[

0 0 1]

38184

= 4.

Iterazione 2:

xB =

x3

x1

x2

B =

1 20 30 10 30 0 1

, B−1 =

1 −2 30 1

10− 3

10

0 0 1

xB = B−1b =

1 −2 30 1

10− 3

10

0 0 1

50304

=

29

5

4

,

Z = cTBxB =

[

0 1 1]

29

5

4

=29

5.

3.3.1 Forma matriciale delle equazioni correnti

L’insieme delle equazioni correnti del metodo del simplesso (cioe il tableau)puo essere rappresentato in forma matriciale nel seguente modo:

[

1 −cT 0o A I

]

ZxxS

=

[

0b

]

.

Ad ogni passo vengono eseguite su questi dati una serie di operazioni alge-briche (in particolare il prodotto di un’equazione per una costante ed alcunecombinazioni lineari tra le equazioni) che possono essere espresse in forma


matriciale come il prodotto di una matrice per entrambi i membri dell’e-quazione appena scritta. Tale matrice e molto simile, come vedremo, allamatrice identita. In modo simbolico questa matrice puo essere rappresentatausando le informazioni relative ai termini noti del nuovo sistema di equazioni.Infatti ad ogni iterazione i termini noti sono Z = cT

BB−1b e xB = B−1b,quindi possiamo scrivere

[

ZxB

]

=

[

1 cTBB−1

o B−1

] [

0b

]

=

[

cTBB−1bB−1b

]

.

Eseguendo le stesse operazioni sui due membri dell’equazione la stessa ma-trice deve premoltiplicare anche le equazioni a sinistra, quindi poiche

[

1 cTBB−1

o B−1

] [

1 −cT 0o A I

]

=

[

1 cTBB−1A − cT cT

BB−1

o B−1A B−1

]

la forma matriciale delle insieme delle equazioni dopo ogni iterazione e

[

1 cTBB−1A − cT cT

BB−1

o B−1A B−1

]

ZxxS

=

[

cTBB−1bB−1b

]

.

Da tali relazioni appare evidente che, ad ogni passo, per determinare tuttigli elementi del tableau del metodo del simplesso, e necessario determinarela matrice B−1, mentre un’altra osservazione e che il calcolo delle quantitanecessarie richiede solo prodotti tra vettori. In quest’ultima parte del para-grafo riassumiamo i passi del metodo del simplesso rivisto e determiniamo leformule per calcolare in modo efficiente l’inversa della matrice B che, ad ognipasso non varia di molto. Il metodo del simplesso prevede i seguenti passi:1. Inizializzazione: Uguale al metodo del simplesso originario;2.1 Passo 1: Determinare la variabile entrante come nel metodo del simplessooriginario;2.2 Passo 2: Determinare la variabile di base uscente in modo analogo almetodo del simplesso originario ma calcolando solo i valori strettamente nec-essari, cioe i coefficienti strettamente positivi delle equazioni relativi allavariabile entrante per tutte le equazioni, tranne la (0), ed i relativi termininoti;2.3 Passo 3: Determinare la nuova BFS calcolando B−1 e ponendo xB =B−1b.3. Test di ottimalita: Analogo al metodo del simplesso originario solo che si


devono calcolare i coefficienti dell’equazione (0) relativi alle variabili non inbase.Il calcolo della matrice B−1 puo essere effettuato evitando la valutazionenumerica diretta della matrice inversa ma sfruttando il fatto che la matriceB cambia di poco rispetto all’iterazione precedente, percio la nuova B−1,che indichiamo con B−1

new, puo essere determinata cambiando di poco la ma-trice inversa precedente, che indichiamo con B−1

old. Per descrivere meglio tale

variazione supponiamo che xk sia la variabile entrante in base, aik e il coef-ficiente di xk nella i−esima equazione, per i = 1, . . . ,m, e sia r il numerodell’equazione che contiene la variabile di base uscente.Il nuovo insieme di equazioni, tranne l’equazione (0), puo essere ottenuto di-videndo la r−esima equazione per ark e sottraendo dalla i−esima equazionela r−esima moltiplicata per aik/ark. Gli elementi della matrice B−1

new sonopertanto

(

B−1new

)

ij=

(

B−1

old

)

ij−

aik

ark

(

B−1

old

)

rji 6= r

1

ark

(

B−1

old

)

iji = r.

Queste formule possono essere scritte anche in forma matriciale:

B−1new = MB−1

old

dove M e la matrice identita, eccetto la sua r−esima colonna, uguale alvettore

δ =

δ1

δ2

...δm

, δi =

aik

ark

i 6= r

1

ark

i = r.

Capitolo 4

Problemi di Trasporto eAssegnamento

4.1 Il Problema del Trasporto

Il problema del trasporto e legato, in generale, alla distribuzione di una mer-ce da un gruppo di centri di distribuzione (per esempio alcune fabbriche),chiamati nodi sorgente, ad un qualsiasi gruppo di centri di ricezione (peresempio alcuni magazzini), detti nodi destinazione, in modo tale da mini-mizzare il costo totale della distribuzione. Ogni nodo sorgente ha una certaofferta di unita da distribuire ai nodi destinazione e ogni nodo destinazioneha, a sua volta, una specifica domanda che deve essere soddisfatta dai no-di sorgente. Per il problema del trasporto si assume sempre che ogni nodosorgente ha un’offerta fissa, si, i = 1, . . . ,m (se m sono i nodi sorgente),che deve essere interamente inviata ai nodi destinazione. Ugualmente ogninodo destinazione ha una domanda fissa dj, j = 1, . . . , n (se n sono i nodidestinazione), che deve essere soddisfatta dai nodi sorgente. Dal punto divista teorico l’esistenza di soluzioni ammissibili e legata alla condizione

m∑

i=1

si =n

∑

j=1

dj.

Si assume sempre che il costo del trasporto da un nodo sorgente ad un nododestinazione sia direttamente proporzionale al numero di unita trasportate.Quindi il costo complessivo e pari al prodotto tra il costo unitario ed il numerodi unita trasportate. Si indica con cij il costo unitario per il trasporto dalla

69

CAPITOLO 4. PROBLEMI DI TRASPORTO E ASSEGNAMENTO 70

sorgente i alla destinazione j.Per descrivere il modello vengono introdotte le seguenti variabili decisionali:

xij = quantita della risorsa inviata dalla sorgente i alla destinazione j.

per i = 1, . . . ,m, e j = 1, . . . , n. Indicando con Z il costo totale, il problemadi trasporto puo essere formulato come problema di programmazione linearenel seguente modo:

min Z =m

∑

i=1

n∑

j=1

cijxij

soggetto ai vincoli

n∑

j=1

xij = si, i = 1, . . . ,m

m∑

i=1

xij = dj, j = 1, . . . , n

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

Una proprieta di cui gode il problema del trasporto e la cosiddetta interezzadelle soluzioni, cioe se i dati del problema (offerte e domande) sono interiallora anche la soluzione ottima (e tutte le BFS ammissibili) lo sono. L’al-goritmo che descriveremo nei successivi paragrafi consente di preservare taleproprieta trovando solo soluzioni intere. Il problema del trasporto puo essererappresentato attraverso una rete nel seguente modo:

S1 D1[s1] [d1]

S2 D2[s2] [d2]

......

Sm Dn[sm] [−dn]

c11

c12

c1n

c21c22

c2n

cm1

cm2 cmn


4.2 Il metodo del simplesso per il problema

del trasporto

Poiche il problema del trasporto e un particolare tipo di problema di program-mazione lineare allora puo essere risolto applicando il metodo del simplesso(e le sue varianti). Ovviamente avendo solo vincoli di uguaglianza devonoessere introdotte m + n variabili artificiali (una per ogni vincolo funzionale).Le colonne del tableau assumono una struttura particolare perche, facendoeccezione per l’equazione (0), i coefficienti sono uguali a 0 oppure a 1. Appli-cando per esempio il metodo del Big M, una volta che si procede ad azzerarei coefficienti delle variabili artificiali nella funzione obiettivo allora i coeffi-cienti della funzione obiettivo ad un certo passo del metodo sono del tipocij − ui − vj, oppure M − ui o M − vj, mentre il termine noto dell’equazione(0) e del tipo

−

m∑

i=1

siui −

n∑

j=1

djvj.

Le quantita ui e vj possono essere interpretate come:ui = multiplo della riga originale i che e stata sottratta dalla riga originale 0dal metodo del simplesso nelle varie iterazioni;vj = multiplo della riga originale m + j che e stata sottratta dalla riga origi-nale 0 dal metodo del simplesso nelle varie iterazioni.Nella prima fase del metodo del simplesso di deve ottenere una BFS inizialeintroducendo le variabili artificiali come variabili di base cui viene assegnatocome valore si oppure dj. Successivamente si devono identificare la variabileentrante in base e quella uscente e determinare infine la nuova BFS.Ricordiamo che l’introduzione delle variabili artificiali ha lo scopo primario dideterminare una BFS iniziale, tuttavia, nel problema in questione, esistonodiverse tecniche per poterla trovare quindi le variabili artificiali non sononecessarie. Inoltre i coefficienti dell’equazione (0) possono essere ottenuticalcolando direttamente i valori ui e vj senza coinvolgere le altre equazioni,sfruttando la proprieta che per le variabili in base i relativi coefficienti nellafunzione obiettivo devono essere nulli e quindi:

cij − ui − vj = 0

se xij e una variabile in base.La determinazione della variabile uscente e la conseguente variazione della


BFS possono essere trovate in modo semplice sfruttando il fatto che de-vono essere soddisfatti solo vincoli di uguaglianza. L’ultima, e piu impor-tante osservazione, sta nel fatto che il tableau del metodo del simplessopuo essere quasi del tutto eliminato. I dati che servono ad ogni iterazionesono i valori cij, si e dj ed i valori attuali di ui e vj. La tabella assumeapprossimativamente la seguente struttura:

Destinazione

1 2 n. . .

Domanda

vj

d1 d2 dn. . .

Sorgente

1

...

2

m

s1

...

s2

sm

Z =

Offerta ui

c11 c12 c1n

c21 c22 c2n

cm1 cm2 cmn

. . .

. . .

. . .

. . .

. . .. . . . . .

In ogni cella, prima di applicare il metodo del simplesso, viene inseritaun’informazione aggiuntiva:

Se xij e variabile

in base

Se xij non e variabile

in base

xij

cij cij

cij − ui − vj


Prima di vedere i metodi per ottenere una BFS iniziale e opportuno rifletteresul numero di variabili in base richiesto dal problema. Infatti il numero divincoli e uguale a m + n, quindi dovrebbero essere necessarie m + n varia-bili in base. Poiche il problema ammette solo vincoli di uguaglianza, unadelle equazioni e automaticamente soddisfatta una volta che lo sono le altre.Quindi il numero di variabili in base e pari a m + n − 1. Per comprenderetale proprieta supponiamo che siano soddisfatti tutti i vincoli tranne quellosulla domanda dell’ultima destinazione:

n∑

j=1

xij = si, i = 1, . . . ,m

m∑

i=1

xij = dj, j = 1, . . . , n − 1.

Sommando le prime equazioni sull’indice i ed applicando la proprieta diammissibilita si ottiene

m∑

i=1

n∑

j=1

xij =m

∑

i=1

si =n

∑

j=1

dj =n−1∑

j=1

dj + dn.

Per j = 1, . . . , n−1, a dj possiamo sostituire i valori delle variabili decisionali,ottenendo l’uguaglianza:

m∑

i=1

n−1∑

j=1

xij +m

∑

i=1

xin =m

∑

i=1

n−1∑

j=1

xij + dn,

da cui, semplificando i termini uguali, si ricava:

m∑

i=1

xin = dn,

il che dimostra che l’ultimo vincolo e automaticamente soddisfatto. Di con-seguenza ogni BFS ha esattamente m + n − 1 valori nonnegativi (che neltableau compaiono cerchiati) e la somma dei valori per ogni riga e per ognicolonna e uguale, rispettivamente, alla relativa offerta o domanda.


4.2.1 Il problema della BFS iniziale

La procedura per determinare una BFS iniziale segue una serie di passi chesi basano sull’analisi del tableau del simplesso per il problema specifico. In-nanzitutto dalle righe e dalle colonne da esaminare si sceglie una variabilesecondo un determinato criterio. A tale variabile si assegna un valore parial valore piu piccolo tra la domanda rimasta sulla colonna e l’offerta cherimane sulla riga. A questo punto si elimina la riga (o la colonna) che haesaurito l’offerta (o la domanda) e si procede nuovamente scegliendo un’altravariabile oppure tutte le variabili rimaste qualora il loro numero coincida conquello delle variabili in base ancora da scegliere. Chiaramente e necessarioaggiornare il valore dell’offerta (o della domanda) sottraendo il valore asseg-nato alla variabile in base. Se il valore residuo di domanda e offerta e ugualeallora si puo indifferentemente eliminare la riga o la colonna assegnando zeroall’offerta o alla domanda residua. Per la scelta della variabile da porre inbase esistono diversi algoritmi, i piu usati sono i seguenti:

1. Regola del Nord-Ovest;

2. Il Metodo di Approssimazione di Vogel;

3. Il Metodo di Approssimazione di Russell.

La Regola del Nord-Ovest consiste nel selezionare inizialmente x11 come va-riabile in base (variabile di nord-ovest). In generale, a partire dalla variabilein base xij si seleziona xi,j+1 se, per la sorgente i la quantita offerta non etutta utilizzata, altrimenti si seleziona xi+1,j.Il Metodo di Approssimazione di Vogel consiste nel calcolare per ogni rigao colonna ancora da considerare la differenza aritmetica tra il secondo piupiccolo ed il piu piccolo costo unitario cij ancora presente in quella riga ocolonna. Nella riga (o colonna) con la maggiore differenza si seleziona lavariabile con il piu piccolo costo unitario.Nel Metodo di Approssimazione di Russell per ogni riga sorgente i ancora daconsiderare si determina il valore ui che e il grande costo unitario cij ancorapresente in tale riga. Inoltre per ogni colonna j ancora da considerare sidetermina il valore vj che e il grande costo unitario cij ancora presente intale colonna. Per ogni variabile xij non selezionata, e appartenente a questerighe e colonne, si calcola il valore

∆ij = cij − ui − vj.


Si seleziona la variabile che ha il valore ∆ij negativo piu grande in valoreassoluto. A parita di ∆ij si puo scegliere una variabile a caso, oppure quellache ha un costo cij inferiore.I tre criteri per la scelta della BFS iniziale sono molto diversi tra loro. Sicu-ramente la regola del Nord-Ovest e quello piu semplice, non richiede alcunaoperazione particolare ma determina una BFS iniziale senza considerare icosti relativi alle variabili inizialmente in base. Il metodo di approssimazionedi Vogel sceglie come variabili in base quelle che hanno i costi piu bassi nellerighe (o nelle colonne) in cui maggiore e la differenza tra tale costo e quelloimmediatamente superiore. Il confronto avviene relativamente ai costi dellevariabili che sono nella stessa riga (o colonna), ma nulla assicura che la sceltasia la migliore in assoluto (la differenza potrebbe essere elevata ma anche ilcosto piu piccolo lo potrebbe essere). In letteratura si ritiene che il migliorecriterio sia proprio il metodo di approssimazione di Russell poiche scegliela variabile in base utilizzando un metodo molto simile a quello che vieneutilizzato dal metodo del simplesso per la scelta della variabile entrante inbase.

4.3 Riassunto del metodo del simplesso

Il metodo del simplesso per problemi di trasporto consiste in tre passi:1. Inizializzazione: si determina una BFS iniziale utilizzando uno dei criteridescritti.2. Test di ottimalita: si calcolano i valori ui e vj risolvendo il sistema diequazioni:

cij = ui + vj

per ogni (i, j) tale che xij e variabile di base. Poiche i valori incogniti dacalcolare sono m + n mentre le variabili in base sono m + n − 1 ad una ditali incognite puo essere assegnato un valore arbitrario, cioe zero. Per farcio conviene selezionare la riga con il maggior numero di variabili in base,ponendo il corrispondente ui = 0 (oppure fare lo stesso per una colonnaponendo il corrispondente vj = 0). A questo punto si calcolano i costi residui

cij − ui − vj

per ogni (i, j) tale che xij non e in base: se risulta che

cij − ui − vj ≥ 0


allora la soluzione trovata e quella ottima e non si procede oltre, altrimentisi esegue l’iterazione successiva.3. Iterazione: E composta da tre fasi:Fase 1: Si determina la variabile entrante selezionando la variabile non inbase xij tale che cij − ui − vj sia negativo e massimo in valore assoluto.Fase 2: Una volta indentificata la variabile entrante in base questo significache il suo valore aumenta (partendo ovviamente da zero). Poiche devonoessere soddisfatti i vincoli di uguaglianza sia sulle righe della tabella chesulle colonne questo significa che il valore di altre variabili in base (almenodue) deve diminuire altrimenti tali vincoli sarebbero violati e che ci sonoaltre variabili in base il cui valore aumenta. Questo significa identificare lacosiddetta reazione a catena, ovvero l’insieme di variabili in base il cui valoredeve aumentare (dette celle riceventi) e quelle il cui valore deve diminuire(dette celle donatrici) affinche i vincoli siano soddisfatti. La variabile in baseuscente e quella relativa alla cella donatrice con il valore piu piccolo.Fase 3: Si determina la nuova BFS aggiungendo il valore della variabile inbase uscente al valore corrente di ogni cella ricevente mentre da ogni celladonatrice si sottrae lo stesso valore (e bene osservare che una di tali celledonatrici non e piu una variabile in base).

4.4 Un esempio di problema del trasporto

Si consideri un problema del trasporto con 2 nodi sorgente, di offerta rispet-tivamente 30 e 50 e 3 nodi destinazione con domanda 35, 25 e 20. La matricedei costi e la seguente

C =

[

1 2 43 5 2

]

.

Si vuole determinare le quantita di merci da inviare dai nodi sorgente a quellidestinazione affinche il costo sia minimo.Innanzitutto scriviamo la tabella dei dati:


1 2 4

3 5 2

1 2 3 si

1

2

dj 35 25 20

30

50

Z =

Il primo passo del metodo del simplesso consiste nel determinare una BFSiniziale. Applicando la regola di Nord-Ovest, scegliamo x11 = 30 e poiapplichiamo l’algoritmo ottenendo la seguente tabella:

1 2 4

3 5 2

1 2 3 si

1

2

dj 35 25 20

30

50

30

5 25 20

Z = 210

e quindi la BFS iniziale (30, 0, 0, 5, 25, 20). Il valore della funzione obiettivoe

Z = 30 + 5 · 3 + 25 · 5 + 20 · 2 = 30 + 15 + 125 + 40 = 210.

Applicando il metodo di Vogel si ha la seguente situazione iniziale

Destinazioni1 2 3 si Differ. Righe

Sorgenti 1 1 2 4 30 12 3 5 2 50 1dj 35 25 20

Diff.col. 2 3 2

Si scegliex12 = 25

e si elimina la seconda colonna:


Destinazioni1 3 si Differ. Righe

Sorgenti 1 1 4 5 32 3 2 50 1dj 35 20

Diff.col. 2 2

A questo punto l’algoritmo prevede che si scelga

x11 = 5

in modo da eliminare la prima riga:


Sorgenti 2 3 2 50 1dj 30 20

A questo punto sono obbligate le scelte restanti per le variabili di base

x21 = 30, x23 = 20.

La BFS diventa quindi (5, 25, 0, 30, 0, 20). Graficamente si ha la seguentesituazione:

1 2 4

3 5 2

1 2 3 si

1

2

dj 35 25 20

30

50

5 25

30 20

Il valore della funzione obiettivo e

Z = 5 + 25 · 2 + 30 · 3 + 20 · 2 = 5 + 50 + 90 + 40 = 185.

Per il metodo di Russell si devono calcolare le quantita ui, vj e ∆ij che ri-portiamo nella tabella, rispettivamente, nell’ultima colonna, nell’ultima rigae all’interno di ogni cella.


1 2 4

3 5 2

1 2 3 si

1

2

dj

vj

35 25 20

3 5 4

30

50

ui

4

5

−6 −7 −4

−5 −5 −7

Si sceglie x23 come variabile in base, a cui viene assegnato il valore 20 edeliminiamo la terza colonna della tabella.

1 2 4

3 5 2

1 2 3 si

1

2

dj

vj

35 25

3 5

30

50

ui

2

5

−4 −5

−5 −5

Scegliamo x12 come variabile in base, assegnando il valore 25, in modo daeliminare la seconda colonna cosicche sono obbligate le scelte restanti per levariabili di base

x11 = 5, x21 = 30.

La BFS diventa quindi (5, 25, 0, 30, 0, 20). Osserviamo che abbiamo ottenutola stessa BFS calcolata dal metodo di Vogel, quindi il valore della funzioneobiettivo e lo stesso Z = 185. Applichiamo ora il metodo del simplesso allaBFS ottenuta con la regola di Nord-Ovest:


1 2 4

3 5 2

1 2 3

1

2

si

dj

ui

vj

30

50

35 25 20

30

5 25 20

Calcoliamo innanzitutto i valori vj e ui, poiche nella terza riga ci sono trevariabili in base poniamo u2 = 0 e ricaviamo gli altri valori ricordando che,per ogni variabile in base deve essere

cij = ui + vj.

Quindi deve esserev3 = c23 − u2 = c23 = 2

e, di conseguenza,

v2 = c22 − u2 = c22 = 5v1 = c21 − u2 = c21 = 3u1 = c11 − v1 = 1 − 3 = −2.

Riportiamo tali valori nella tabella del metodo

1 2 4

3 5 2

1 2 3

1

2

si

dj

ui

vj

30

50

35 25 20

30

5 25 20

3 5 2

−2

0

Per determinare la variabile entrante in base calcoliamo i valori

cij − ui − vj

e riportiamoli nelle celle della tabella.


1 2 4

3 5 2

1 2 3

1

2

si

dj

ui

vj

30

50

35 25 20

30

5 25 20

3 5 2

−2

0

−1 +4

La variabile entrante e sicuramente x12, cella ricevente, celle donatrici saran-no x11 e x22, mentre quest’ultima e candidata ad uscire dalla base perche in-crementando x12 e la prima variabile che raggiunge il valore 0 (infatti x22 = 25mentre x11 = 30). La reazione a catena e la seguente:

1 2 4

3 5 2

1 2 3

1

2

si

dj

ui

vj

30

50

35 25 20

30

5 25 20

3 5 2

−2

0

+

Le celle donatrici donano 25 unita alle celle riceventi (in modo tale da faruscire dalla base x22), cosicche la situazione diventa:

1 2 4

3 5 2

1 2 3

1

2

si

dj

ui

vj

30

50

35 25 20

5

30

25

20


Per verificare il test di ottimalita calcoliamo i nuovi valori di ui e vj. Poniamou1 = 0 perche nella prima riga ci sono due variabili in base (in alternativapotremmo porre anche u2 = 0 perche anche nella seconda riga ci sono duevariabili in base ma il risultato sarebbe lo stesso), e otteniamo gli altri valoria catena:

v1 = c11 − u1 = c11 = 1v2 = c12 − u1 = c12 = 2u2 = c21 − v1 = 3 − 1 = 2v3 = c23 − u2 = 2 − 2 = 0.

Riportiamo tali valori nella tabella e calcoliamo contemporaneamente i nuovivalori

cij − ui − vj

per le variabili non in base:

1 2 4

3 5 2

1 2 3

1

2

si

dj

ui

vj

30

50

35 25 20

5

30

25

20

1 2 0

0

2+1

+4

Poiche non ci sono variabili non in base aventi il valore cij − ui − vj negativoallora la soluzione trovata e quella ottima. Osserviamo che questa soluzionecoincide la BFS iniziale trovata con i metodi di Vogel e di Russell ed il valoreminimo della funzione obiettivo e

Z = 185.

4.4.1 Un esempio con destinazione fittizia

Si vuole risolvere il problema del trasporto con 3 sorgenti, con offerta rispet-tivamente 100 e 60 e 80 e 3 destinazioni con domanda 50, 70 e 90. La matricedei costi e la seguente

C =

1 − 22 3 43 1 2

.


Si vogliono determinare le quantita di merci da inviare dalle sorgenti alledestinazioni affinche il costo sia minimo.Innanzitutto osserviamo che

∑

i

si = 240,∑

j

dj = 210,

quindi e necessario introdurre una destinazione fittizia (dummy), che in-dicheremo con 4D, che serva ad assorbire l’offerta eccedente. I costi relativia tale destinazione saranno posti tutti uguali a zero. Inoltre si deve metterein evidenza che la sorgente 1 non deve inviare merce alla destinazione 2, per-tanto dobbiamo introdurre una penalizzazione per la variabile x12 ponendoc12 = M, dove M indica, al solito, un numero molto grande. La matrice deicosti diviene pertanto la seguente:

C =

1 M 2 02 3 4 03 1 2 0

.

Scriviamo la tabella dei dati ed applichiamo la Regola del Nord-Ovest pertrovare la BFS iniziale:

1 M 2 0

2 3 4 0

3 1 2 0

1 2 3 4D si ui

1

2

3

dj 50 70 90 30

vj

100

60

80

50 50

20 40

50 30

1 M M + 1 M − 1

0

3 − M

1 − M

M − 1

M + 1 0

1 − M 1 − M

−2

Z = 370 + 50M

Il valore della funzione obiettivo nella BFS iniziale e:

Z = 50 + 50M + 60 + 160 + 100 = 370 + 50M.

Osserviamo che, in base ai valori cij = ui − vj, possiamo scegliere x13 comevariabile entrante in base, x23 e la variabile uscente mentre celle donatricisono x12 e x23, mentre celle riceventi sono x13 e x22, le unita donate sono paria 40.


1 M 2 0

2 3 4 0

3 1 2 0

1 2 3 4D si ui

1

2

3

dj 50 70 90 30

vj

100

60

80

50 10

60

40

50 30

1 M 2 0

0

3 − M

0

M − 2

+2 1 − M

M − 1

0

M − 3

Z = 410 + 10M

Il valore della funzione obiettivo nella BFS corrente e:

Z = 50 + 10M + 80 + 180 + 100 = 410 + 10M.

Osserviamo che x32 e variabile entrante in base, x12 e la variabile uscentementre celle donatrici sono x12 e x33, mentre celle riceventi sono x13 e x32, leunita donate sono pari a 10.

1 M 2 0

2 3 4 0

3 1 2 0

1 2 3 4D si ui

1

2

3

dj 50 70 90 30

vj

100

60

80

50

10

60

50

40 30

1 1 2 0

0

2

0

−1

+2

M − 1

0

0

−2

Z = 420


Z = 50 + 100 + 180 + 10 + 80 = 420.

Osserviamo che x24 e variabile entrante in base, x34 e la variabile uscentementre celle donatrici sono x22 e x34, mentre celle riceventi sono x24 e x32, leunita donate sono pari a 30.


1 M 2 0

2 3 4 0

3 1 2 0

1 2 3 4D si ui

1

2

3

dj 50 70 90 30

vj

100

60

80

50

40

30

50

40

30

1 1 2 −2

0

2

0

−1

+2

M − 1

0

+2

+2

Z = 340


Z = 50 + 80 + 90 + 40 + 80 = 340.

Osserviamo che x21 e variabile entrante in base, x22 e la variabile uscentementre celle donatrici sono x22, x33 e x11, mentre celle riceventi sono x21, x32

e x13, le unita donate sono pari a 30.

1 M 2 0

2 3 4 0

3 1 2 0

1 2 3 4D si ui

1

2

3

dj 50 70 90 30

vj

100

60

80

20

70

30

80

10

30

1 1 2 −1

0

1

0

+1

+2

M − 1

+1

+1

+1

Z = 330


Z = 20 + 160 + 60 + 70 + 20 = 330.

Poiche e soddisfatto il test di ottimalita la BFS corrente

(20, 0, 80, 30, 0, 0, 0, 70, 10)


e quella ottima. Risolviamo lo stesso problema determinando la BFS inizialecon il metodo di approssimazione di Vogel:

Destinazioni1 2 3 4D si Differ. Righe

1 1 M 2 0 100 1Sorgenti 2 2 3 4 0 60 2

3 3 1 2 0 80 1dj 50 70 90 30

Diff.col. 1 2 0 0

Poniamo x24 = 30 e cancelliamo la quarta colonna:

Destinazioni1 2 3 si Differ. Righe

1 1 M 2 100 1Sorgenti 2 2 3 4 30 1

3 3 1 2 80 1dj 50 70 90

Diff.col. 1 2 0

Poniamo x32 = 70 e cancelliamo la seconda colonna:


1 1 2 100 1Sorgenti 2 2 4 30 2

3 3 2 10 1dj 50 90

Diff.col. 1 0

Poniamo x21 = 30 e cancelliamo la seconda riga:


Sorgenti 1 1 2 100 13 3 2 10 1dj 20 90

Diff.col. 2 0


Poniamo x11 = 20, cancelliamo la prima colonna, quindi le altre variabili inbase sono determinate:

x13 = 80, x33 = 10.

Scriviamo ora la tabella del metodo del simplesso:

1 M 2 0

2 3 4 0

3 1 2 0

1 2 3 4D si ui

1

2

3

dj 50 70 90 30

vj

100

60

80

20 80

30 30

70 10

−1 −1 0 −3

2

3

2

M − 1 +1

+1+1

+2 +1

Z = 330


Z = 20 + 160 + 60 + 70 + 20 = 330.

Poiche e soddisfatto il test di ottimalita la BFS corrente

(20, 0, 80, 30, 0, 0, 0, 70, 10)

e quella ottima.Ovviamente se la somma delle domande fosse stata superiore alla somma delleofferte allora sarebbe stato necessario aggiungere una sorgente fittizia concosti nulli ma il procedimento sarebbe stato esattamente lo stesso descrittonel paragrafo.

4.5 Il Problema di assegnamento

Il problema di assegnamento e un problema di programmazione lineare in cuideterminate risorse devono essere assegnate per eseguire determinate opera-zioni (dette task). Le risorse possono essere persone, ma anche macchinari,stabilimenti, intervalli di tempo e cosı via. Affinche un problema sia diassegnamento devono essere soddisfatti i seguenti requisiti:


1. Il numero delle risorse e quello dei task devono essere uguali (tale valoresara indicato con n).

2. Ogni risorsa deve essere assegnata ad un singolo task.

3. Ogni task e svolto da un’unica risorsa.

4. Il costo cij e associato all’esecuzione del task j da parte della risorsa i.

5. L’obiettivo e determinare le assegnazioni a costo globale minimo.

I primi tre requisiti sono piuttosto restrittivi ma e comunque possibile rifor-mulare determinati problemi in modo tale che siano soddisfatti.Supponiamo per esempio di dover collocare 3 nuove macchine nelle posizionioccupate precedentemente da quattro macchinari. In base alla distanza deimagazzini dalle posizioni abbiamo i seguenti costi orari:

Locazioni1 2 3 4

1 10 18 14 −Macchine 2 16 − 15 14

3 12 13 10 15

Per ricondurre questo esempio ad un problema di assegnamento e neces-sario innanzitutto introdurre una macchina fittizia (dummy), cui vengonoassegnati costi tutti uguali a 0. Inoltre osserviamo che ci sono due posizioniche non possono essere assegnate rispettivamente alle macchine 1 e 2 percioper evitare che tale assegnamento avvenga deve essere attribuito un costounitario molto alto, pari al valore M . La tabella dei costi diventa cosı:

Locazioni1 2 3 4

1 10 18 14 MMacchine 2 16 M 15 14

3 12 13 10 154(D) 0 0 0 0


4.5.1 Il modello matematico del problema di assegna-mento

Per descrivere il modello vengono introdotte le seguenti variabili decisionali:

xij =

1 se la risorsa i esegue il task j;

0 altrimenti

per i, j = 1, . . . , n. Ogni xij e una variabile binaria (puo assumere solo duevalori). Indicando con Z il costo totale, il problema di assegnamento puoessere formulato nel seguente modo:

min Z =n

∑

i=1

n∑

j=1

cijxij

soggetto ai vincoli

n∑

j=1

xij = 1, i = 1, . . . , n

n∑

i=1

xij = 1, j = 1, . . . , n

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

xij variabile binaria.

Cancellando il vincolo delle variabili binarie il problema puo essere considera-to come un normale problema di programmazione lineare e come tale puo es-sere risolto. Il modello puo essere assimilato anche al problema del trasportoin cui il numero di sorgenti m coincide con il numero di destinazioni n edinoltre ogni offerta

si = 1, i = 1, . . . , n

e ogni domandadj = 1, j = 1, . . . , n.

Applicando la proprieta di interezza del problema del trasporto ogni BFSha componenti intere e, in base ai vincoli, queste devono necessariamente


assumere valori 0 oppure a 1. Il problema puo essere descritto attraversouna rete:

A1 T1[1] [−1]

A2 T2[1] [−1]

......

An Tn[1] [−1]

c11

c12

c1n

c21c22

c2n

cn1

cn2 cnn

Ovviamente il metodo del simplesso adattato al problema del trasporto puoessere applicato anche al problema di assegnamento. In questo caso le soluzio-ni che si ottengono sono sempre degeneri in quanto il problema del trasportoprevede che le variabili di base siano m + n − 1, cioe in questo caso 2n − 1,ma di queste solo n sono uguali a 1 mentre le altre n − 1 devono esserenecessariamente nulle.Per risolvere il problema di assegnamento esiste un metodo piu semplice,descritto nel paragrafo seguente.

4.5.2 Il metodo ungherese

Il metodo ungherese deve il suo nome al fatto che fu descritto per la primavolta da due matematici ungheresi, Konig ed Egervary, intorno al 1930. Talealgoritmo consente di risolvere il problema di assegnamento evitando l’appli-cazione del metodo del simplesso.L’algoritmo viene applicato direttamente alla matrice dei costi, generandouna serie di tabelle equivalenti fino ad ottenerne una per la quale la soluzioneottima e banale. Nella tabella finale i costi sono tutti positivi o nulli e l’asseg-nazione ottima puo essere effettuata in corrispondenza dei valori nulli. L’ideachiave del metodo e quella di effettuare una serie di sottrazioni di opportunivalori dagli elementi delle righe (e delle colonna) senza alterare il problema.L’algoritmo e composto dai seguenti passi.


1. Sottrarre il piu piccolo valore in ogni riga da ogni elemento della stessariga (riduzione per righe) e scrivere i risultati in una nuova tabella.

2. Sottrarre il piu piccolo valore in ogni colonna da ogni elemento dellastessa colonna (riduzione per colonne) e scrivere i risultati in una nuovatabella.

3. Controllare se puo essere effettuato un assegnamento ottimo: per questobisogna determinare il minimo numero di linee necessarie a coprire tut-ti gli elementi della tabella uguali a zero. Se tale numero e uguale alnumero di righe allora e possibile determinare un insieme ottimo diassegnazioni e si esegue il passo 6 dell’algoritmo altrimenti si esegue ilpasso 4.

4. Se il numero minimo di linee e inferiore al numero di righe allora sideve modificare la tabella nel seguente modo:

a) si sottrae il piu piccolo valore non coperto da linee da ogni ele-mento non coperto della tabella;

b) si aggiunge tale valore agli elementi che si trovano all’intersezionetra due linee;

c) si lasciano invariati tutti gli altri elementi.

5. Ripetere i passi 3 e 4 finche non si ottiene un insieme ottimo di asseg-nazioni.

6. Effettuare le assegnazioni una alla volta in corrispondenza degli ele-menti nulli. Iniziare dalle righe o dalle colonne che presentano un solozero. Poiche ciascuna riga e ciascuna colonna deve ricevere esattamenteun’assegnazione, cancellare la riga e la colonna coinvolte dopo tale as-segnazione. Se non ci sono righe (o colonne) che hanno un unico ele-mento uguale a zero allora si considera quella che ne ha due. In questocaso l’assegnamento e arbitrario (questo vuol dire che l’assegnamentoottimo non e unico). Quindi bisogna considerare le righe e le colonnenon ancora cancellate e procedere con la successiva assegnazione.

Applichiamo il metodo ungherese all’esempio introdotto in precedenza edefinito dalla seguente tabella:


Locazioni1 2 3 4

1 10 18 14 MMacchine 2 16 M 15 14

3 12 13 10 154(D) 0 0 0 0

10

16

12

0

18

M

13

0

14

15

10

0

M

14

15

0

Tabella iniziale

0

16

12

0

8

M

13

0

4

15

10

0

M

14

15

0

Passo ISi sottrae il minimo 10 dalla 1a riga

0

2

12

0

8

M

13

0

4

1

10

0

M

0

15

0

Passo IISi sottrae il minimo 14 dalla 2a riga

0

2

2

0

8

M

3

0

4

1

0

0

M

0

5

0

Passo IIISi sottrae il minimo 10 dalla 3a riga

A questo punto si dovrebbe sottrarre il minimo da ciascuna colonna, mapoiche il valore minimo e zero ed in ogni riga (e/o colonna) c’e un elementouguale a zero (cioe il numero minimo di linee che coprono gli elementi ugualia zero coincide con la dimensione della matrice) allora e possibile procedereall’assegnazione ottima delle risorse ai task.


0

2

2

0

8

M

3

0

4

1

0

0

M

0

5

0

x11 = 1

0

2

2

0

8

M

3

0

4

1

0

0

M

0

5

0

x24 = 1

0

2

2

0

8

M

3

0

4

1

0

0

M

0

5

0

x33 = 1

0

2

2

0

8

M

3

0

4

1

0

0

M

0

5

0

x42 = 1

La soluzione ottima e la seguente

X =

1 0 0 00 0 0 10 0 1 00 1 0 0

mentre il costo minimo e

Z = 10 + 14 + 10 + 0 = 34.

Consideriamo il problema di assegnamento con 5 task e 5 risorse definitodalla seguente matrice dei costi:

C =

6 4 3 3 27 5 4 5 43 6 3 6 37 10 4 4 86 5 7 4 4

.

Applichiamo il metodo ungherese a tale problema:


6

7

3

7

6

4

5

6

10

5

3

4

3

4

7

3

5

6

4

4

2

4

3

8

4

Tabella iniziale

4

3

0

3

2

2

1

3

6

1

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

Matrice ottenuta sottraendo ilminimo da tutte le righe

4

3

0

3

2

1

0

2

5

0

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

Matrice ottenuta sottraendo ilminimo da tutte le colonne

Adesso e possibile effettuare l’assegnamento ottimo.

4

3

0

3

2

1

0

2

5

0

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

x15 = 1

4

3

0

3

2

1

0

2

5

0

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

x31 = 1


4

3

0

3

2

1

0

2

5

0

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

x23 = 1

4

3

0

3

2

1

0

2

5

0

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

x44 = 1

4

3

0

3

2

1

0

2

5

0

1

0

0

0

3

1

1

3

0

0

0

0

0

4

0

x52 = 1

La soluzione ottima e la seguente

X =

0 0 0 0 10 0 1 0 01 0 0 0 00 0 0 1 00 1 0 0 0

mentre il costo minimo e

Z = 2 + 4 + 3 + 4 + 5 = 18.

Osserviamo che l’assegnamento ottimo non e unico in quanto il problemaammette anche la seguente soluzione:

X =

0 0 0 0 10 1 0 0 01 0 0 0 00 0 1 0 00 0 0 1 0

.

Capitolo 5

Programmazione intera

5.1 Introduzione

In molti problemi pratici le variabili decisionali hanno senso solo se assumonovalori interi. In questo caso si parla di programmazione lineare intera (PLI).I modelli matematici sono gli stessi della programmazione lineare con il vin-colo aggiuntivo che le variabili devono assumere solo valori interi. Se solo al-cune variabili decisionali sono intere allora si parla di programmazione interamista. Un’altra area di applicazione e relativa a problemi di tipo decisionalein cui la risposta e si oppure no. Con due sole possibili scelte e naturale cheuna variabile decisionale xi possa essere uguale a

xi =

1 se la decisione e si;

0 se la decisione e no.

Tali variabili sono dette binarie e tali problemi fanno parte della cosiddettaprogrammazione binaria.

5.2 L’algoritmo di Branch-and-Bound

Ogni problema di Programmazione Lineare Intera con variabili limitate (peresempio binarie) ha un numero finito di soluzioni ammissibili che potrebberoessere enumerate per trovare quella ottima. Tale numero, seppur finito, esolitamente molto molto grande (esponenziale). Il metodo di Branch-and-

96

CAPITOLO 5. PROGRAMMAZIONE INTERA 97

Bound costituisce una validissima alternativa a tale procedura. Descriviamoora le diverse fasi dell’algoritmo.

5.2.1 Branching

Quando si opera con variabili binarie il modo piu semplice di procedere equello di suddividere l’insieme delle soluzioni ammissibili in sottoinsiemi, fis-sando ad ogni passo, per esempio, il valore di una delle variabili xj, dettavariabile di branching (i cui valori possibili sono chiaramente solo 0 e 1). Es-istono tecniche piuttosto sofisticate per la scelta della variabile di branching,in alternativa si puo seguire l’ordine naturale (cioe al primo passo si ponex1 = 0 e x1 = 1, per poi passare a x2, a x3 e cosı via). I due valori dellavariabile di branching definiscono due sottoproblemi che vengono risolti inmodo approssimato, come sara descritto nel paragrafo successivo. In questomodo si definisce un vero e proprio albero, detto albero delle soluzioni, chesi ramifica iterazione dopo iterazione, quando vengono definiti (e risolti) isottoproblemi definiti attribuendo i valori alle diverse variabili di branching.Nel corso dell’algoritmo alcuni di questi problemi potranno essere tagliati(fathomed) mentre altri saranno ulteriormente suddivisi in sottoproblemi.

5.2.2 Bounding

Per ogni sottoproblema si deve ottenere un limite (bound) sulla soluzioneammissibile. Un modo classico per ottenere questa informazione e quello dirisolvere il problema rilassato, che viene ottenuto cancellando un insieme divincoli che lo rendono difficile. Nel caso di un problema di programmazionebinaria si taglia proprio il vincolo xj ∈ {0, 1} che viene sostituito dai vincoli

xj ≤ 1, xj ≥ 0

per ogni j. Per risolvere il problema rilassato si puo applicare, per esempio,il metodo del simplesso (oppure anche il metodo grafico qualora il numero divariabili decisionali sia uguale a due).

5.2.3 Fathoming

Una volta risolto il problema rilassato un’eventualita e che esso non possa piudar luogo alla soluzione ottima, in questo caso puo essere tagliato, cioe non


si considerano piu i sottoproblemi che esso potrebbe generare in quanto si ecerti che essi non porteranno ad una soluzione migliore. Esistono tre criteriper tagliare un sottoproblema: un primo criterio e quello di avere ottenutouna soluzione binaria del rilassamento lineare. Infatti se la soluzione ottimadel rilassamento lineare e una soluzione binaria, questa deve essere soluzioneottima anche del problema di programmazione binaria. Questa soluzionedeve essere memorizzata come la cosiddetta soluzione incombente (cioe lamigliore soluzione ammissibile trovata finora). Si pone

Z∗ = valore di Z per la soluzione incombente.

Quindi il sottoproblema in questione non viene piu preso in considerazione.Poiche Z∗ e la migliore soluzione trovata finora questo suggerisce un altrocriterio per tagliare un sottoproblema. Infatti se il valore ottimo della fun-zione obiettivo del rilassamento lineare e inferiore a Z∗ allora non c’e bisognodi considerare ulteriormente tale sottoproblema.Il terzo modo per tagliare un sottoproblema e legato al fatto che se il proble-ma rilassato non ha soluzioni ammissibili allora a maggior ragione il problemanon rilassato non puo averne.Riepilogando, i Criteri di Fathoming sono i seguenti:Criterio n. 1: il limite e inferiore a Z∗;Criterio n. 2: il rilassamento lineare del sottoproblema non ha soluzioniammissibili;Criterio n. 3: la soluzione ottima del rilassamento lineare ha componentibinarie.

5.2.4 Sommario dell’algoritmo di Branch-and-Bound

Inizializzazione: Porre Z∗ = −∞. Applicare il passo di bounding, il passodi fathoming all’intero problema. Se non tagliato via allora classificarlo comeproblema completo ed eseguire la prima iterazione.Singola Iterazione:Fase 1. Branching: Tra i sottoproblemi rimanenti selezionare quello genera-to piu di recente (oppure quello che ha il bound piu grande). Generare daquesto due nuovi sottoproblemi fissando la variabile di branching a 0 e 1.Fase 2. Bounding: Per ogni sottoproblema ottenere un limite (bound) ri-solvendo il suo rilassamento lineare e approssimando per difetto il valore diZ della soluzione ottima risultante al piu grande numero intero inferiore ad


esso.Fase 3. Fathoming: Per ogni nuovo sottoproblema applicare i 3 criteri difathoming e scartare quelli che ne soddisfano uno.Se uno dei sottoproblemi viene scartato in base al terzo criterio di fathomingallora si deve eventualmente aggiornare il valore della soluzione incombenteZ∗.Test di ottimalita:Arrestare l’algoritmo quando non rimangono piu sottoproblemi, la soluzioneincombente e ottima, altrimenti eseguire un’altra iterazione.Il motivo della scelta del sottoproblema creato piu di recente e che durantela fase di bounding vengono risolti problemi di programmazione lineare soli-tamente usando il metodo del simplesso. Piuttosto che eseguire ogni voltail metodo dall’inizio conviene applicare una riottimizzazione che consiste nelmodificare il tableau finale del precedente problema tenendo conto delle pic-cole differenze nel modello ed applicando poche iterazioni del metodo delsimplesso.

5.3 Un’applicazione dell’algoritmo di Branch-

and-Bound

Definiamo quindi il seguente problema di Programmazione Binaria:

max Z = 9x1 + 5x2 + 6x3

6x1 +3x2 +5x3 ≤ 10−x1 −x2 +x3 ≤ 0

xj variabile binaria per j = 1, 2, 3.

Il primo passo dell’algoritmo e quello di risolvere il rilassamento lineare delproblema completo:

max Z = 9x1 + 5x2 + 6x3

(1) 6x1 +3x2 +5x3 ≤ 10(2) −x1 −x2 +x3 ≤ 0(3) x1 ≤ 1(4) x2 ≤ 1(5) x3 ≤ 1

x1, x2, x3 ≥ 0.

Applichiamo il metodo del simplesso introducendo 5 variabili slack.


Iterazione 0

Var.base Eq. Z x1 x2 x3 x4 x5 x6 x7 x8 bi

Z

x4

x5

x6

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

−9

6

−1

1

0

0

−5

3

−1

0

1

0

−6

5

1

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

10

0

1

1

1

Iterazione 1


Z

x4

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

−5

3

−1

0

1

0

−6

5

1

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

9

−6

1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

9

4

1

1

1

1


Iterazione 2


Z

x3

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

−7

5

3

5

−8

5

0

1

−3

5

0

1

0

0

0

0

6

5

1

5

−1

5

0

0

−1

5

0

0

1

0

0

0

9

5

−6

5

11

5

1

0

6

5

0

0

0

0

1

0

0

0

0

0

0

1

69

5

4

5

1

5

1

1

1

5

Iterazione 3


Z

x3

x5

x1

x2

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

1

0

0

0

0

6

5

1

5

−1

5

0

0

−1

5

0

0

1

0

0

0

9

5

−6

5

11

5

1

0

6

5

7

5

−3

5

8

5

0

1

3

5

0

0

0

0

0

1

76

5

1

5

9

5

1

1

4

5

Soluzione del problema rilassato e (1, 1, 1/5) mentre il valore della funzioneobiettivo e 76/5 = 15 + 1/5 che viene approssimato al valore intero

Z = 15.

Nessuno dei criteri di fathoming consente di tagliare il problema completoquindi scegliamo x1 come variabile di branching e definiamo due sottopro-


blemi, uno in cui fissiamo x1 = 0 e l’altro con x1 = 1 :

Sottoproblema 1

Fissato x1 = 0

max Z = 5x2 + 6x3

(1) 3x2 + 5x3 ≤ 10(2) − x2 + x3 ≤ 0(3) xj variabile binaria per j = 2, 3;

Sottoproblema 2

Fissato x1 = 1

max Z = 9 + 5x2 + 6x3

(1) 3x2 + 5x3 + 6 ≤ 10(2) − x2 + x3 − 1 ≤ 0(3) xj variabile binaria per j = 2, 3

ovveroSottoproblema 2

max Z = 9 + 5x2 + 6x3

(1) 3x2 + 5x3 ≤ 4(2) − x2 + x3 ≤ 1(3) xj variabile binaria per j = 2, 3.

Risolviamo ora il sottoproblema 1 rilassato:

max Z = 5x2 + 6x3

3x2 +5x3 ≤ 10−x2 +x3 ≤ 0x2 ≤ 1

x3 ≤ 1x2, x3 ≥ 0



Iterazione 0


Z

x4

x5

x6

x7

(0)

(1)

(2)

(3)

(4)

1

0

0

0

0

−5

3

−1

1

0

−6

5

1

0

1

0

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

0

10

0

1

1

Iterazione 1


Z

x4

x3

x6

x7

(0)

(1)

(2)

(3)

(4)

1

0

0

0

0

−11

8

−1

1

1

0

0

1

0

1

0

1

0

0

0

6

−5

1

0

−1

0

0

0

1

0

0

0

0

0

1

0

10

0

1

1

Iterazione 2


Z

x4

x3

x2

x7

(0)

(1)

(2)

(3)

(4)

1

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

1

0

0

0

6

−5

1

0

−1

11

−8

1

1

−1

0

0

0

0

1

11

2

1

1

0


Soluzione del sottoproblema 1 rilassato e (0, 1, 1) mentre il valore della fun-zione obiettivo e

Z = 11.

Poiche la soluzione e binaria allora il sottoproblema viene tagliato in baseal terzo criterio di fathoming. Inoltre poniamo Z∗ = 11 in quanto questae divenuta la soluzione incombente (cioe la migliore soluzione ammissibiletrovata finora).Risolviamo ora il sottoproblema 2 rilassato:

max Z = 5x2 + 6x3 + 93x2 +5x3 ≤ 4−x2 +x3 ≤ 1x2 ≤ 1

x3 ≤ 1x2, x3 ≥ 0

Anche in questo caso applicando il metodo del simplesso si devono introdurre4 variabili slack.

Iterazione 0


Z

x4

x5

x6

x7

(0)

(1)

(2)

(3)

(4)

1

0

0

0

0

−5

3

−1

1

0

−6

5

1

0

1

0

1

0

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

9

4

1

1

1


Iterazione 1


Z

x3

x5

x6

x7

(0)

(1)

(2)

(3)

(4)

1

0

0

0

0

−7

5

3

5

−8

5

1

−3

5

0

1

0

0

0

6

5

1

5

−1

5

0

−1

5

0

0

1

0

0

0

0

0

1

0

0

0

0

0

1

69

5

4

5

1

5

1

1

5

Iterazione 2


Z

x3

x5

x2

x7

(0)

(1)

(2)

(3)

(4)

1

0

0

0

0

0

0

0

1

0

0

1

0

0

0

6

5

1

5

−1

5

0

−1

5

0

0

1

0

0

7

5

−3

5

8

5

1

3

5

0

0

0

0

1

76

5

1

5

9

5

1

4

5

Soluzione del sottoproblema 1 rilassato e (1, 1, 1/5) mentre il valore dellafunzione obiettivo e 76/5 che viene approssimato al valore intero

Z = 15.

Visualizzare l’albero delle soluzioni ottenuto finora:


Completo Z = 15(1, 1, 1/5)

1 0 Z∗ = 11(0, 1, 1)

F(3)

x1 Z = 15(1, 1, 1/5)

Passiamo ora alla seconda iterazione e scriviamo i sottoproblemi ponendox2 = 1 e x2 = 0:

Sottoproblema 3

Fissato x2 = 0

max Z = 9 + 6x3

(1) 5x3 ≤ 4(2) x3 ≤ 1(3) x3 variabile binaria,

Sottoproblema 4

Fissato x2 = 1

max Z = 14 + 6x3

(1) 3 + 5x3 ≤ 4(2) − 1 + x3 ≤ 1(3) x3 variabile binaria,

ovveroSottoproblema 4

max Z = 14 + 6x3

(1) 5x3 ≤ 1(2) x3 ≤ 2(3) x3 variabile binaria.

In questo caso e superfluo risolvere il rilassamento lineare dei problemi binariperche le soluzioni sono molto semplici. Infatti x3 = 0 e soluzione del sotto-problema 3, e Z = 9 e il relativo valore della funzione obiettivo. Poiche tale


valore e inferiore rispetto alla soluzione incombente il sottoproblema vienetagliato applicando il primo criterio di fathoming. La soluzione del sotto-problema 4 e x3 = 0, in cui la funzione obiettivo ammette valore Z = 14, chediviene la nuova soluzione incombente

Z∗ = 14,

ed il sottoproblema viene tagliato applicando il terzo criterio di fathoming.Poiche non ci sono ulteriori sottoproblemi da risolvere la soluzione incombentee quella ottima e l’albero delle soluzioni finale e il seguente.

Completo Z = 15(1, 1, 1/5)

1 0 Z∗ = 11(0, 1, 1)

F(3)

1 0

x1

x2

F(3) F(1)

Z = 15(1, 1, 1/5)

Z∗ = 14(1, 1, 0)

Z = 9(1, 0, 0)


5.4 L’algoritmo di Branch-and-Bound per la

Programmazione Intera Mista

Supponiamo che in un problema di programmazione lineare con n variabili de-cisionali le prime k (≤ n) sono intere mentre le altre sono reali. Supponendodi dover risolvere il problema:

max Z =n

∑

j=1

cjxj

n∑

j=1

aijxj ≤ bi, i = 1, 2, . . . ,m,

xj ≥ 0, j = 1, 2, . . . , n,xj variabile intera, per j = 1, . . . , k, k ≤ n.

Appare chiaro che se k = n allora il problema e di programmazione lineareintera. L’algoritmo e molto simile al branch-and-bound per variabili bina-rie nel senso che si utilizza la tecnica del rilassamento lineare per i passi dibounding e fathoming. I cambiamenti sono i seguenti.Innanzitutto la scelta della variabile di branching non avviene secondo l’or-dine naturale poiche ora si considerano solo le variabili che devono assumerevalori interi e che invece hanno un valore non intero nella soluzione ottima nelrilassamento dell’attuale sottoproblema. Di solito tra queste variabili vienescelta la prima nell’ordinamento naturale ma potrebbero essere utilizzate an-che tecniche piu sofisticate.Il secondo cambiamento riguarda i valori assegnati alla variabile di branching.Poiche tale variabile puo assumere valori interi non e possibile definire i duesottoproblemi uguagliandola a 0 o 1, ne si puo generare un sottoproblema perogni possibile valore, allora si definiscono due sottoproblemi specificando duepossibili intervalli di valori. In dettaglio, se xi e la variabile di branching edx∗

i e il suo valore nella soluzione ottima del rilassamento lineare si definisconodue sottoproblemi aggiungendo il vincolo

xi ≤ ⌊x∗

i ⌋

nel primo exi ≥ ⌊x∗

i ⌋ + 1

in cui ⌊x∗

i ⌋ indica la parte intera del numero reale x∗

i :

⌊x∗

i ⌋ = max {n ∈ Z | n ≤ x∗

i } .


In questo caso puo succedere che la variabile di branching sia la stessa anchein qualche passo successivo.Il terzo cambiamento riguarda il passo di bounding. Nel caso di un pro-blema di programmazione lineare intera pura il valore ottimo della funzioneobiettivo del rilassamento lineare Z viene approssimato per difetto al fine diottenere un valore intero. Se alcune variabili possono assumere valori realitale arrotondamento non e necessario.La quarta modifica riguarda il terzo criterio di fathoming. Nel caso dellaprogrammazione intera mista il criterio deve richiedere che solo le variabilivincolate ad essere intere lo siano effettivamente nella soluzione ottima delrilassamento lineare.Vediamo quindi di riassumere l’algoritmo di Branch-and-Bound per problemidi programmazione lineare intera mista.Inizializzazione:Porre Z∗ = −∞. Applicare le operazioni di bounding, fathoming ed il test diottimalita descritto in seguito al problema di partenza. Se il problema nonviene tagliato allora eseguire la prima iterazione.Singola iterazione:

1. Branching: tra i sottoproblemi non tagliati sceglierne uno (per esempioquello generato piu recentemente). Scegliere la variabile di branching,cioe la prima variabile intera che nella soluzione ottima del rilassamentolineare non ha valore intero. Sia xj tale variabile ed x∗

j il suo valore nonintero. Generare due nuovi sottoproblemi aggiungendo rispettivamentei vincoli xj ≤ ⌊x∗

j⌋ e xj ≥ ⌊x∗

j⌋ + 1.

2. Bounding: per ogni nuovo sottoproblema ottenere il relativo bound ap-plicando il metodo del simplesso al suo rilassamento lineare ed usandoil valore di Z per la soluzione ottima risultante.

3. Fathoming: per ogni nuovo sottoproblema applicare i seguenti 3 criteridi fathoming e scartare quei sottoproblemi tagliati da uno di questi:Criterio 1: il bound risulta minore o uguale rispetto al valore dellasoluzione incombente Z∗;Criterio 2: il rilassamento lineare non ha soluzioni ammissibili;Criterio 3: la soluzione ottima per il rilassamento lineare ha valoriinteri per tutte le variabili vincolate ad assumere valori interi (se questasoluzione e migliore di quella incombente diventa la nuova soluzione


incombente e si riapplica il criterio 1 a tutti i sottoproblemi non ancoratagliati).

Test di ottimalita:Arrestare la procedura quando non ci sono altri sottoproblemi, la soluzioneincombente e quella ottima, se non c’e alcuna soluzione incombente allorail problema non ha soluzioni ammissibili, in caso contrario eseguire un’altraiterazione.

5.5 Un esempio di applicazione del metodo

Branch-and-Bound per la Programmazio-

ne Intera

Supponiamo di dover risolvere il seguente problema di programmazione li-neare intera:

max Z = 2x1 + 3x2 + 2x3

x1 +2x3 ≤ 32x1 +x2 ≤ 5

x1, x2, x3 ≥ 0x1, x2, x3 variabili intere.

Innanzitutto risolviamo, usando il metodo del simplesso, il rilassamento li-neare del problema di partenza che viene ottenuto eliminando il vincolo diinterezza delle tre variabili. Introduciamo due variabili slack, x4 e x5, chesono inizialmente le variabili in base.

Iterazione 0


Z

x4

x5

(0)

(1)

(2)

1

0

0

−2

1

2

−3

0

1

−2

2

0

0

1

0

0

0

1

0

3

5


Iterazione 1


Z

x4

x2

(0)

(1)

(2)

1

0

0

4

1

2

0

0

1

−2

2

0

0

1

0

3

0

1

15

3

5

Iterazione 2


Z

x3

x2

(0)

(1)

(2)

1

0

0

5

1

2

2

0

0

1

0

1

0

1

1

2

0

3

0

1

18

3

2

5

La soluzione ottenuta (0, 5, 3/2) non e intera, quindi non puo essere applicatoil terzo criterio di fathoming ed il problema non viene tagliato, inoltre

Z = 18

diviene il bound per i successivi sottoproblemi pur non essendo soluzioneincombente in quanto la soluzione non e intera. Consideriamo ora comevariabile di branching x3 poiche e la prima variabile che nella soluzione delproblema rilassato non ha un valore intero e definiamo due sottoproblemi incui aggiungiamo rispettivamente i seguenti vincoli:

x3 ≤ 1

ex3 ≥ 2.


Scriviamo ora esplicitamente i due sottoproblemi:

Sottoproblema 1

max Z = 2x1 + 3x2 + 2x3

x1 +2x3 ≤ 32x1 +x2 ≤ 5

x3 ≤ 1x1, x2, x3 ≥ 0

eSottoproblema 2

max Z = 2x1 + 3x2 + 2x3

x1 +2x3 ≤ 32x1 +x2 ≤ 5

x1, x2 ≥ 0, x3 ≥ 2.

Risolviamo il sottoproblema 1 con il metodo del simplesso introducendo 3variabili slack.

Iterazione 0


Z

x4

x5

x6

(0)

(1)

(2)

(3)

1

0

0

0

−2

1

2

0

−3

0

1

0

−2

2

0

1

0

1

0

0

0

0

1

0

0

0

0

1

0

3

5

1

Iterazione 1


Z

x4

x2

x6

(0)

(1)

(2)

(3)

1

0

0

0

4

1

2

0

0

0

1

0

−2

2

0

1

0

1

0

0

3

0

1

0

0

0

0

1

15

3

5

1


Iterazione 2


Z

x4

x2

x3

(0)

(1)

(2)

(3)

1

0

0

0

4

1

2

0

0

0

1

0

0

0

0

1

0

1

0

0

3

0

1

0

2

−2

0

1

17

1

5

1

La soluzione ottenuta (0, 5, 1) e intera, quindi applicando il terzo criterio difathoming il problema viene tagliato. Il valore della funzione obiettivo, cioeZ = 17, diviene la nuova soluzione incombente.

Z∗ = 17.

Per risolvere il sottoproblema 2 si deve effettuare il seguente cambio divariabile

x′

3 = x3 − 2 ⇒ x3 = x′

3 + 2, x′

3 ≥ 0,

cosicche il sottoproblema puo essere riscritto nel seguente modo:

max Z = 2x1 + 3x2 + 2(x′

3 + 2)x1 +2(x′

3 + 2) ≤ 32x1 +x2 ≤ 5

x1, x2, x′

3 ≥ 0,

ovveromax Z = 2x1 + 3x2 + 2x′

3 + 4x1 +2x′

3 ≤ −12x1 +x2 ≤ 5

x1, x2, x′

3 ≥ 0.

Appare evidente, osservando il primo vincolo, che il problema non ammettesoluzioni ammissibili, quindi il sottoproblema puo essere tagliato. Possiamoquindi scrivere l’albero dei sottoproblemi:


Completo Z = 18(0, 5, 3/2)

x3 ≤ 1 x3 ≥ 2Z∗ = 17(0, 5, 1)

F(3)

SoluzioneNon Ammissibile

F(2)

Un’ultima osservazione riguarda il fatto che, per come sono utilizzate le va-riabili di branching, potrebbe capitare che una stessa variabile decisionale siadi branching piu di una volta, in passi differenti dell’algoritmo.

5.6 L’algoritmo di Branch-and-Cut per la Pro-

grammazione Binaria

Si tratta di un metodo, descritto per la prima volta intorno alla meta deglianni Ottanta, per risolvere in modo efficiente problemi di programmazionebinaria di grandi dimensioni per i quali l’algoritmo di Branch-and-Boundmostrava una complessita computazionale di ordine esponenziale. Il metodosi puo applicare anche a problemi di programmazione binaria mista e interamista. Ambito ideale di applicazione sono i problemi in cui la matrice A deivincoli funzionali presenta una struttura sparsa, cioe il numero di elementidiversi da zero non supera il 5%. Consideriamo solo il caso di problemi diprogrammazione binaria pura. Il metodo utilizza una serie di tecniche com-binate insieme: il preprocessamento automatico del problema, la generazionedei piani di taglio e le tecniche di branch-and-bound.Le tecniche di preprocessamento del problema sono le seguenti:

1. Fissare il valore di alcune variabili: quando una variabile non puo as-sumere un determinato valore poiche questo non renderebbe possibile ilsoddisfacimento del vincolo indipendentemente dal valore assunto dallealtre variabili allora il valore di quella variabile deve essere posto uguale


all’altro valore. Per esempio il vincolo

5x1 + x2 − x3 ≤ 2

non puo essere soddisfatto se x1 = 1 e quindi deve essere necessaria-mente x1 = 0. Un criterio generale puo essere il seguente: una voltaidentificata la variabile con il piu grande coefficiente positivo si verificase la somma tra tale coefficiente e tutti i coefficienti negativi del vinco-lo eccede il termine noto, in caso affermativo tale variabile deve essereposta uguale a zero.

2. Eliminare i vincoli ridondanti: se un vincolo funzionale soddisfa persi-no la soluzione binaria piu difficile allora e ridondante e puo essereeliminato. Per un vincolo di tipo ≤ la soluzione binaria piu difficile havariabili uguali a 1 per quelle che hanno coefficienti nonnegativi e lealtre sono uguali a 0. Tali valori si invertono se il vincolo e di tipo ≥ .Per esempio i vincoli

3x1 + 3x2 ≤ 8, 3x1 − 2x2 ≥ −3

sono ridondanti perche

3(1) + 3(1) = 6 ≤ 8, 3(0) − 2(1) = −2 ≥ −3.

3. Rendere i vincoli piu stringenti: in questo caso si cerca di ridurrela regione ammissibile senza tuttavia eliminare soluzioni ammissibili.Consideriamo il seguente semplice problema:

max Z = 2x1 + 3x2

2x1 + 2x2 ≤ 3x1, x2 variabili binarie.

Le soluzioni ammissibili sono (0, 0), (1, 0) e (0, 1). Soluzione ottima delrilassamento lineare e (1/2, 1) mentre la soluzione ottima del problemabinario e (0, 1). Se al vincolo assegnato si sostituisce il seguente

x1 + x2 ≤ 1

si ottiene una regione ammissibile ridotta pur senza eliminare alcunasoluzione ammissibile ma con l’effetto che sia il rilassamento lineare cheil problema binario hanno la stessa soluzione ottima. Nella seguentefigura sono riportate le due regioni di ammissibilita.


• ••

La sostituzione di un vincolo con un altro che riduce la regione di ammissi-bilita e detta generazione di un piano di taglio. Un piano di taglio (o taglio)e appunto un nuovo vincolo funzionale che riduce la regione di ammissibilitasenza eliminare alcuna soluzione ammissibile.I piani di taglio possono essere generati in molti modi, la seguente e una dellepossibili procedure.

1. Considerare solo i vincoli funzionali nella forma ≤ che hanno coefficientinonnegativi.

2. Determinare un gruppo di variabili (detto copertura minima del vinco-lo) tali che:

(a) il vincolo e violato se ogni variabile del gruppo e uguale a 1 e tuttele altre sono uguali a 0.

(b) il vincolo e soddisfatto se il valore di ciascuna di queste variabiliviene cambiato da 1 a 0.

3. Se N denota il numero delle variabili del gruppo il piano di tagliorisultante ha la forma

somma delle variabili del gruppo ≤ N − 1.

Per esempio considerando il vincolo

5x1 + 4x2 + 7x3 + 5x4 ≤ 13


l’insieme {x1, x2, x3} e una copertura minima perche ponendo il loro valoreuguale a 1 (e x4 = 0) risulta

5 + 4 + 7 + 0 ≥ 13.

Tuttavia cambiando il valore di ogni variabile (a turno) da 0 a 1 il vincolo esoddisfatto:

5 + 4 + 0 + 0 ≤ 13, 5 + 0 + 7 + 0 ≤ 13, 0 + 4 + 7 + 0 ≤ 13.

Per comprendere meglio il significato di copertura minima consideriamo ilseguente vincolo:

8x1 + 3x2 + 2x3 ≤ 9. (5.1)

La situazione dei vertici e la seguente:

vertici ammissibili vertici non ammissibili(0, 0, 0) (1, 1, 1)(0, 0, 1) (1, 1, 0)(0, 1, 0) (1, 0, 1)(1, 0, 0)(0, 1, 1)

Osserviamo che l’insieme {x1, x2} rappresenta una copertura minima delvincolo, quindi

x1 + x2 ≤ 1 (5.2)

rappresenta un vincolo da affiancare a (5.1). Inoltre anche l’insieme {x1, x3}rappresenta una copertura minima del vincolo, quindi un altro vincolo e

x1 + x3 ≤ 1. (5.3)

I due vincoli (5.2) e (5.3) sono piu stringenti rispetto a (5.1) poiche i ver-tici ammissibili appartengono alla frontiera di almeno uno dei due, mentrenessuno appartiene alla frontiera del vincolo originario (fa eccezione l’origineche appartiene comunque alla frontiera di tutti i vincoli di nonnegativita),come si evince dalla presente tabella:

Vertici ammissibili Appartenenza ai Vincolix1 + x2 ≤ 1 x1 + x3 ≤ 1

(0, 0, 0) no no(0, 0, 1) no si(0, 1, 0) si no(1, 0, 0) si si(0, 1, 1) si si


Per illustrare meglio l’efficacia di tale tecnica consideriamo il seguente esem-pio di programmazione lineare binaria:

max Z = 6x1 + 5x2 + 4x3

2x1 +3x2 +4x3 ≤ 63x1 +x2 +6x3 ≤ 9


Risolviamo il rilassamento lineare del problema completo:

max Z = 6x1 + 5x2 + 4x3

(1) 2x1 +3x2 +4x3 ≤ 6(2) 3x1 +x2 +6x3 ≤ 9(3) x1 ≤ 1(4) x2 ≤ 1(5) x3 ≤ 1

x1, x2, x3 ≥ 0.


Iterazione 0


Z

x4

x5

x6

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

−6

2

3

1

0

0

−5

3

1

0

1

0

−4

4

6

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

6

9

1

1

1


Iterazione 1


Z

x4

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

−5

3

1

0

1

0

−4

4

6

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

6

−2

−3

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

6

4

6

1

1

1

Iterazione 2


Z

x4

x5

x1

x2

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

−4

4

6

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

6

−2

−3

1

0

0

5

−3

−1

0

1

0

0

0

0

0

0

1

11

1

5

1

1

1


Iterazione 3


Z

x3

x5

x1

x2

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

1

0

0

0

0

1

1

4

−3

2

0

0

0

0

0

1

0

0

0

4

−1

2

0

1

0

0

2

−3

4

7

2

0

1

0

0

0

0

0

0

1

12

1

4

7

2

1

1

3

4

Soluzione del problema rilassato e dunque il vettore (1, 1, 1/4), con valoredella funzione obiettivo Z = 12. E ovvio che non potendo tagliare il proble-ma completo poiche tale soluzione non soddisfa alcun criterio di fathoming,e necessario scegliere la variabile di branching (x1 seguendo l’ordine naturaleoppure x3 in modo piu oculato), definire due sottoproblemi e risolverli. Con-sideriamo invece la possibilita di risolvere il problema completo sostituendoai due vincoli quelli definiti dalle rispettive coperture minime. E facile os-servare che il primo vincolo ammette come unica copertura minima l’insieme{x2, x3}, che definisce il vincolo

x2 + x3 ≤ 1

mentre il secondo vincolo ammette come unica copertura minima l’insieme{x1, x2, x3}, che definisce il vincolo

x1 + x2 + x3 ≤ 2.

Consideriamo quindi il seguente problema

max Z = 6x1 + 5x2 + 4x3

3x2 +x3 ≤ 1x1 +x2 +x3 ≤ 2



Risolviamo il rilassamento lineare del problema completo:

max Z = 6x1 + 5x2 + 4x3

(1) x2 +x3 ≤ 1(2) x1 +x2 +x3 ≤ 2(3) x1 ≤ 1(4) x2 ≤ 1(5) x3 ≤ 1

x1, x2, x3 ≥ 0.


Iterazione 0


Z

x4

x5

x6

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

−6

0

1

1

0

0

−5

1

1

0

1

0

−4

1

1

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

1

2

1

1

1


Iterazione 1


Z

x4

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

−5

1

1

0

1

0

−4

1

1

0

0

1

0

1

0

0

0

0

0

0

1

0

0

0

6

0

−1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

6

1

1

1

1

1

Iterazione 1


Z

x2

x5

x1

x7

x8

(0)

(1)

(2)

(3)

(4)

(5)

1

0

0

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

1

1

0

0

−1

1

5

1

−1

0

−1

0

0

0

1

0

0

0

6

0

−1

1

0

0

0

0

0

0

1

0

0

0

0

0

0

1

11

1

0

1

0

1

Soluzione ottima del problema rilassato e dunque (1, 1, 0), con Z = 11, cherisulta essere soluzione ottima anche del problema binario iniziale. L’uso deivincoli definiti dalle coperture minime consente di ridurre la regione ammissi-bile eliminando quei vertici che sono ammissibili per il problema rilassato manon per quello binario. In tal modo aumenta la probabilita che la soluzionedel rilassamento lineare coincida con quella del problema binario.

Capitolo 6

Modelli di Ottimizzazione suReti

6.1 Terminologia delle reti

La rappresentazione attraverso reti e uno strumento ampiamente utilizzatoper descrivere problemi derivanti da differenti aree come la distribuzione diservizi, la pianificazione e la gestione delle risorse, l’allocazione di struttureper le telecomunicazioni. Essa consente di visualizzare graficamente le com-ponenti del sistema, le relative connessioni ed alcune informazioni costo (ilcosto, la lunghezza o altro) relative ad esse.Una rete consiste in un insieme di punti detti nodi (o vertici) ed in un insiemedi linee chiamate archi (o collegamenti) che collegano appunto i nodi. Se lun-go un arco e fissata una direzione allora e detto arco orientato. In questocaso l’arco viene etichettato citando prima l’origine (nodo di partenza) e poila destinazione (nodo di arrivo). Se l’arco non ha una direzione fissata, cioee possibile un flusso in entrambi i versi allora e detto arco non orientato.Una rete avente solo archi orientati e detta rete orientata, altrimenti e dettarete non orientata. Gli archi di una rete possono avere un flusso di qualchetipo (per esempio il numero massimo di veicoli che possono attraversare untratto stradale). In quest’ultimo caso ad ogni arco viene assegnato un valoreche indica appunto la sua capacita massima, cioe il valore massimo di taleflusso. Quando l’arco non e orientato si assume che il flusso possa avvenirein entrambe le direzioni, pertanto il valore del flusso associato a tale arcoviene considerato come il flusso netto (cioe la differenza dei flussi assegnati

123

CAPITOLO 6. MODELLI DI OTTIMIZZAZIONE SU RETI 124

nelle due direzioni). Per esempio, se un flusso 15 e stato assegnato in unadirezione e successivamente si assegna un flusso 8 in direzione opposta, alloral’effetto e quello di togliere 8 unita dal flusso originale, portandolo a 7. Taleprocedimento viene utilizzato anche per un arco orientato, ammettendo degliassegnamenti fittizi del flusso nella direzioni opposta a quella dell’arco, cau-sando una riduzione del valore complessivo del flusso nella direzione corretta.Quando due nodi non sono connessi direttamente da un arco allora ha sensochiedersi se esiste una sequenza di archi distinti che li connette. Tale sequen-za e detta cammino. Analogamente agli archi si parla di cammini orientatie cammini non orientati. Un cammino che inizia e finisce sullo stesso nodo edetto ciclo. Si dice che due nodi sono connessi se esiste almeno un camminonon orientato che li congiunge. Una rete e connessa se ogni coppia di nodi econnessa. Una rete connessa prende il nome di albero se non contiene alcunciclo. Un albero e detto albero ricoprente (spanning tree) se e una rete checonnette tutti i nodi e non contiene alcun ciclo. Se n e il numero dei nodiallora ogni albero ricoprente ha esattamente n − 1 archi poiche questo e ilnumero minimo di archi necessari per avere una rete connessa ed il numeromassimo possibile senza creare cicli. La quantita massima di flusso che puoessere trasportato su un arco diretto e detta capacita dell’arco. Un nodosorgente e quel nodo che ha la proprieta che il flusso uscente supera quelloentrante. Il caso contrario e quello del nodo destinazione in cui il flusso en-trante supera quello che esce. Un nodo di trasferimento soddisfa la proprietache i due flussi sono uguali.

6.2 Il Problema di Minimo Albero Ricoprente

Il Problema di Minimo Albero Ricoprente (Minimum Spanning Tree, o alberodi minima estensione) si definisce se la rete e connessa e non orientata, e,ad ogni arco, e associata una misura nonnegativa, la lunghezza, (che, peresempio, puo rappresentare una distanza, un tempo oppure un costo). Peril problema in questione si vuole trovare un albero ricoprente, cioe una retesenza cicli che colleghi tutti i nodi e tale che la sua lunghezza complessivasia minima. Il problema di minimo albero ricoprente puo essere sintetizzatonei seguenti punti:

1. E assegnato un insieme di nodi ed una lista di possibili collegamentitra i nodi insieme alle relative lunghezze;


2. si vuole costruire la rete con un numero di archi sufficiente a collegaretutti i nodi, in modo tale che esista un cammino tra ogni coppia dinodi;

3. obiettivo da raggiungere e determinare l’albero che ha la minima lunghez-za.

Se la rete ha n nodi, per quanto detto in precedenza, richiede n−1 collegamen-ti per assicurare l’esistenza di un cammino per ogni coppia di nodi. Possibiliapplicazioni di questo problema riguardano, per esempio, la progettazionedi reti di telecomunicazioni (per esempio reti in fibra ottica, reti di comput-er, linee dati telefoniche), oppure di reti di trasporto, di reti di trasmissioneelettrica o di collegamenti elettrici (per esempio minimizzare la lunghezza deicavi elettrici all’interno di un computer), e tutte quelle applicazioni in cui sivogliono minimizzare le connessioni tra punti diversi che devono comunicare(o essere collegati) tra loro.

6.2.1 Un algoritmo per il problema di minimo alberoricoprente

Un algoritmo per il problema di minimo albero ricoprente e composto daiseguenti passi:

1. Si seleziona un nodo in modo arbitrario che viene connesso al nodo piuvicino (cioe quello che ha la distanza inferiore dal nodo scelto) oppuresi seleziona l’arco che ha la lunghezza minima;

2. Si identifica il nodo non connesso piu vicino ad un nodo gia connesso,e quindi collegare questi due nodi. Si ripete l’operazione finche tutti inodi saranno connessi;

3. Nel caso in cui il numero di possibili nodi da scegliere al passo 1 oal passo 2 sia maggiore di 1, la scelta e del tutto arbitraria e portacomunque ad una soluzione ottima.

Per esempio si supponga di dover cablare in fibra ottica una zona dove sonogia presenti alcune stazioni per lo smistamento del segnale. Tali punti devonoessere collegati minimizzando la lunghezza complessiva dei cavi utilizzati. Lasituazione e schematizzata dalla seguente rete:


O

A

C

B

D

E

F

T

6

6

5

2

2

4

4

1

2

4

2

2

2

Nelle pagine seguenti vengono riportati i passi dell’algoritmo applicato a talerete, scegliendo O come nodo iniziale. Gli archi di colore rosso identificanoquelli appartenenti all’albero che si sta determinando.

O

A

C

B

D

E

F

T

6

6

5

2

2

4

4

1

2

4

2

2

2


O

A

C

B

D

E

F

T

6

6

5

2

2

4

4

1

2

4

2

2

2

O

A

C

B

D

E

F

T

6

6

5

2

2

4

4

1

2

4

2

2

2

O

A

C

B

D

E

F

T

6

6

5

2

2

4

4

1

2

4

2

2

2


Il minimo albero ricoprente e il seguente:

O

A

C

B

D

E

F

T

2

24

1

2

2

2

La lunghezza complessiva dei collegamenti e uguale a 15. E evidente che ilminimo albero ricoprente trovato non e l’unico in quanto in diversi passidell’algoritmo e stato necessario effettuare una scelta tra diversi archi.

6.3 Il Problema di Cammino Minimo

Il problema di cammino minimo viene definito su reti connesse, sia orientateche non orientate, in cui sono presenti due nodi speciali chiamati origine edestinazione, ed indicati di solito con O e T rispettivamente. Ad ogni arco einoltre associato un numero positivo (detto lunghezza dell’arco). L’obiettivoe determinare il cammino che unisce i nodi O e T con la lunghezza comp-lessiva minima. La lunghezza del cammino e la somma delle lunghezze degliarchi che lo compongono. L’algoritmo per risolvere il problema di camminominimo e di tipo iterativo, e consiste nello scegliere, ad ogni iterazione, ilnodo piu vicino all’origine tra quelli non ancora scelti. Nel dettaglio l’algo-ritmo procede nel seguente modo: nella k−esima iterazione si considerano inodi piu vicini al nodo origine (scelti ai passi precedenti), i loro cammini e ledistanze minime dall’origine, e che sono detti appunto nodi scelti. Tra questisi considerano quelli che sono direttamente connessi a nodi non ancora sceltie che sono detti nodi non scelti. Per ciascuno di questi, si considera il nodopiu vicino non ancora scelto (nodo non scelto con la distanza piu piccola).In questo modo si viene a formare un insieme di nodi, non ancora scelti, chesono candidati ad essere scelti. Tra questi viene scelto il piu vicino all’origine.


L’algoritmo termina quando viene scelto il nodo destinazione.Consideriamo ora la seguente rete non orientato della quale vogliamo calco-lare il cammino minimo dall’origine alla destinazione.

O

A

C

B D

E

T

3

4

4

1

55

7

1

2

4 7

2

6.3.1 Applicazione dell’algoritmo di cammino minimo

L’applicazione dell’algoritmo viene descritta utilizzando una tabella compo-sta da sette colonne e da un numero di righe uguale al numero di iterazionirichieste. Nella prima colonna della tabella e riportato l’indice dell’iterazionecorrente, nella seconda colonna sono riportati i nodi appartenenti all’insiemedi quelli gia scelti nelle precedenti iterazioni (all’inizio solo il nodo O) chesono direttamente collegati a nodi non ancora scelti. Per ciascuno di talinodi viene individuato un nodo candidato, cioe il nodo non scelto ad essopiu vicino, e che viene riportato nella terza colonna. Qualora ad un nodocorrispondono piu nodi candidati questi vengono riportati tutti nella terzacolonna. Per ciascuno dei nodi candidati viene riportata nella quarta colonnala sua distanza dall’origine (cioe la somma tra la distanza del nodo sceltodall’origine e la distanza del nodo scelto da quello candidato). A questopunto, confrontando tutti i valori riportati nella quarta colonna, viene scelto ilnodo candidato (o i nodi candidati) piu vicino all’origine, e che viene riportatonella quinta colonna. La distanza viene riportata nella sesta colonna, mentregli ultimi archi selezionati sono scritti nella settima colonna.


k

Nodi sceltidirettamente

connessi ai nodinon scelti

Nodicandidati

Distanzatotale

k−esimonodovicino

Distanzaminima

Ultimoarco

1 O A 2 A 2 OA

2 O C 4 C 4 OCA B 2 + 2 = 4 B 4 AB

3 A D 2 + 7 = 9 E 7 BEB E 4 + 3 = 7C E 4 + 4 = 8

4 A D 2 + 7 = 9 D 8 BDB D 4 + 4 = 8 EDE D 7 + 1 = 8

5 D T 8 + 5 = 13E T 7 + 7 = 14

T 13 DT

Osservando l’ultima colonna della tabella e, partendo dal nodo destinazioneT per poi procedere a ritroso, possiamo determinare il cammino minimo perandare da O a T . La lunghezza del cammino (o dei cammini) e il valoreriportato nell’ultima riga della sesta colonna. Abbiamo trovato due possibilicammini minimi entrambi di lunghezza 13:

O −→ A −→ B −→ E −→ D −→ TO −→ A −→ B −→ D −→ T.

6.4 Il Problema di Massimo Flusso

Si considera una rete orientata in cui su ogni arco viene fissato un valore mas-simo di veicoli (per esempio) che possono transitare da un nodo all’altro. Sivuole massimizzare il numero di veicoli che devono attraversare la rete dall’o-rigine O alla destinazione T in modo tale che in ogni nodo diverso da questidue il numero di veicoli che entra sia uguale a quello che esce. Il Problema diMassimo Flusso puo essere formulato come un problema di programmazionelineare e quindi puo essere risolto con il metodo del simplesso. Esistono tut-tavia algoritmi specifici come il metodo del cammino aumentante. Questoalgoritmo e basato sui concetti di rete residua e di cammino aumentante.Ad ogni iterazione l’algoritmo consiste nei seguenti tre passi:


1. Identificare un cammino aumentante selezionando un cammino orien-tato dalla sorgente alla destinazione nella rete residua, in modo taleche la capacita residua del cammino sia strettamente positiva (se talecammino non esiste allora il flusso trovato e ottimo).

2. Calcolare la capacita c∗ di questo cammino aumentante determinan-do la piu piccola delle capacita residue degli archi appartenenti a talecammino.

3. Diminuire di c∗ la capacita residua di ogni arco in questo camminoaumentante. Si incrementi di c∗ la capacita residua di ogni arco diquesto cammino aumentante nella direzione opposta. Ritornare quindial passo 1.

Vediamo ora un’applicazione dell’algoritmo per trovare il massimo flusso nelcaso della seguente rete:

O

A

B

C

D

T

9

7

7

6

2

4

6

9

3

Inizialmente su ogni arco e presente una capacita residua pari alla portatadel medesimo arco, evidenziamo tale situazione:


O

A

B

C

D

T

9

0

7

0

7 0

6 0

2

04

0 6

0

9

0

3

0

I iterazione: Cammino aumentante O − A − C − T : c∗ = min{9, 7, 6} = 6

O

A

B

C

D

T

3

6

7

0

1 6

6 0

2

04

0 0

6

9

0

3

0

6 6


II iterazione: Cammino aumentante O − B − D − T : c∗ = min{7, 6, 9} = 6

O

A

B

C

D

T

3

6

1

6

1 6

0 6

2

04

0 0

6

3

6

3

0

12 12

III iterazione: Cammino aumentante O − A − D − T : c∗ = min{3, 2, 3} = 2

O

A

B

C

D

T

1

8

1

6

1 6

0 6

0

24

0 0

6

1

8

3

0

14 14

IV iterazione: Cammino aumentante O − B − C − D − T : c∗ = min{1, 4, 3, 1} = 1

O

A

B

C

D

T

1

8

0

7

1 6

0 6

0

23

1 0

6

0

9

2

1

15 15


Se il problema ha grandi dimensioni puo essere piuttosto complicato ricer-care un cammino aumentante. Questo puo avvenire procedendo in modosistematico determinando tutti i nodi che possono essere raggiunti dalla sor-gente lungo un singolo arco avente capacita residua positiva. Da questi siidentificano tutti i nuovi nodi che possono essere raggiunti da questo nodocosicche si identifica un cammino avente capacita residua strettamente pos-itiva. Puo essere d’aiuto, per evitare di ricercare un cammino aumentanteche potrebbe non esistere, un importante risultato della teoria delle reti chee noto come Teorema di massimo flusso e minimo taglio. Un taglio e definitocome un insieme di archi orientati contenente almeno un arco appartenentead ogni possibile cammino orientato dalla sorgente alla destinazione. Il va-lore del taglio e la somma delle capacita degli archi del taglio. Il teorema dimassimo flusso e minimo taglio stabilisce che, per ogni rete avente una solasorgente ed una sola destinazione, il flusso massimo possibile dalla sorgentealla destinazione e uguale al valore del minimo taglio della rete. Quindi se Fe l’ammontare del flusso il valore di ogni taglio fornisce un limite superioreper F . Se F coincide con il valore di un taglio allora possiamo essere certiche il flusso corrente e ottimo. Questo implica che il relativo taglio nella reteresidua e zero. Nel caso dell’esempio visto prima il valore del flusso ottimotrovato e 15 che infatti corrisponde al minimo taglio riportato nella seguentefigura:

O

A

B

C

D

T

9

7

7

6

2

4

6

9

3

Minimo taglio

Un’altra situazione potrebbe verificarsi quando, pur non avendo raggiunto ilvalore massimo del flusso potrebbero non esserci (apparentemente) camminiaumentanti. Consideriamo la seguente rete:


O

A

B

C

D

T

7

8

6

5

3

2

6

9

Appare abbastanza immediato trovare il minimo taglio della rete, compostodagli archi OA, BC e BD, la cui capacita complessiva e uguale a 14 che risultaessere il valore del massimo flusso. Evidenziamo su ogni arco la capacitaresidua uguale alla portata del medesimo arco:

O

A

B

C

D

T

7

0

8

0

6 0

5 0

6

0

9

0

3

02

0


I iterazione: Cammino aumentante O − A − C − T : c∗ = min{7, 6, 6} = 6

O

A

B

C

D

T

1

6

8

0

0 6

5 0

0

6

9

0

3

02

0

6 6

II iterazione: Cammino aumentante O − A − D − T : c∗ = min{1, 3, 9} = 6

O

A

B

C

D

T

0

7

8

0

0 6

5 0

0

6

8

1

2

12

0

7 7


III iterazione: Cammino aumentante O − B − D − T : c∗ = min{8, 5, 8} = 5

O

A

B

C

D

T

0

7

3

5

0 6

0 5

0

6

3

6

2

12

0

12 12

A questo punto sembrerebbe che non ci siano ulteriori cammini aumentantinonostante il valore del flusso non sia quello massimo. In casi come questo ilcammino aumentante puo essere cercato anche invertendo il flusso in alcuniarchi, cioe percorrendo tali archi nella direzione inversa rispetto a quellaassegnata. Nel caso specifico osserviamo che considerando il cammino O −B − C − A − D − T (invertendo cioe la direzione dell’arco AC il cui flussonon e saturo andando da C ad A) si ottiene un aumento del flusso pari alledue unita necessarie per raggiungere il massimo flusso in base al teorema diminimo taglio e massimo flusso.

IV iterazione: Cammino aumentante O − B − C − A − D − T : c∗ = min{3, 2, 6, 2, 3} = 2

O

A

B

C

D

T

0

7

1

6

2 4

0 5

0

6

1

8

0

30

2

14 14

Alcune tipiche applicazioni del problema di massimo flusso riguardano peresempio la massimizzazione del flusso di petrolio (o di acqua) attraverso unsistema di condotte petrolifere (o idriche), oppure la massimizzazione del


flusso di veicoli attraverso una rete stradale. Per alcuni tipi di problemi ilflusso attraverso la rete potrebbe avere origine da piu di un nodo, o ancheterminare in piu nodi come nella seguente figura.

A

B

C

D

E

F

G

2

4

2

5

7

2

5

3

6

Per ovviare a questo problema si introduce sorgente fittizia (oppure una desti-nazione fittizia, o entrambe) e i relativi nuovi archi. La sorgente fittizia vienecollegata a tutti i nodi che originano il flusso assumendo come capacita ilflusso massimo originato dal nodo collegato. In modo analogo la destinazionefittizia viene collegata a tutti i nodi cui termina il flusso di partenza. La retedisegnata nella figura precedente questa viene modificata in questo modo.

O T

A

B

C

D

E

F

G

9

6

5

2

4

2

5

7

2

5

3

6

12

9


6.5 PERT/CPM

Le reti costituiscono uno strumento grafico molto potente e semplice per rap-presentare (e pianificare) alcune attivita da svolgere nell’ambito della realiz-zazione di un determinato progetto. Infatti la complessita nella realizzazionedi un progetto puo essere studiata in modo migliore scomponendolo in at-tivita elementari e valutando le relazioni tra queste ed i requisiti di cui ne-cessitano per essere portate a termine. Il PERT (Program Evaluation andReview Technique) ed il CPM (Critical Path Method) sono appunto duetecniche che consentono di fare cio. La differenza tra le due tecniche e cheil PERT si occupa solo della minimizzazione del tempo di esecuzione delprogetto: la tecnica risalte alla fine degli anni ’50, all’epoca in cui negli StatiUniti fu realizzato il progetto Polaris (un missile balistico a testata nuclearedestinato ad equipaggiare i sommergibili atomici). In quell’occasione lo scopodegli scienziati fu quello di portare a compimento il progetto nel piu brevetempo possibile trascurando completamente i costi (elevati) che esso richiede-va. Il CPM valuta anche i costi ed utilizza stime di tipo deterministico perla durata dell’attivita. Ci sono tuttavia alcuni passi che sono comuni alledue tecniche. Il primo e quello di scomporre il progetto in attivita piu pic-cole, cercando di mantenere un grado di dettaglio possibilmente omogeneo.Ad ogni attivita del progetto deve essere possibile attribuire parametri certicome il tempo di realizzazione e/o il costo. Il secondo passo e quello di deter-minare i vincoli tra le attivita elementari, cioe l’ordine con il quale le attivitadevono essere eseguite. Per esempio si deve stabilire che le attivita A,B e Cdevono precedere l’attivita D, che questa a sua volta deve precedere E e Fe cosı via. Il progetto puo essere descritto da due tipologie di rete:1) Rete AOA (Activity-On-Arc): un’attivita e rappresentata da un arco.Ogni nodo e usato per separare un’attivita (arco uscente) da ciascuna delleattivita predecessori (archi entranti). La sequenza degli archi mostra le re-lazioni di precedenza tra le attivita.2) Rete AON (Activity-On-Node): un’attivita e rappresentata da un nodo.Gli archi sono usati per rappresentare le relazioni di precedenza esistenti trale attivita.Supponiamo che un determinato progetto sia stato scomposto in 10 attivitaelementari e che le relazioni di precedenza e la durata di queste sono ripor-tate nella tabella 5.1. Visualizziamo ora il progetto in questione utilizzandola rappresentazione AON:


Attivita Predecessori diretti Durata previstaA −− 3 settimaneB A 4 settimaneC B 5 settimaneD B 4 settimaneE B 3 settimaneF C,D 4 settimaneG C 3 settimaneH D 6 settimaneI F,G,H 7 settimaneL D,E 7 settimane

Tabella 6.1:

INIZIO

A

B

DC E

F H L

I

G

FINE

3

4

45 3

4 6 7

7

3

Rappresentiamo ora lo stesso progetto utilizzando una rete AOA:


INIZIO

1

2

3 4

5 6 7 8

FINE

A

B

DC

E

HFG

I L

Nella precedente figura appare chiaro come la rappresentazione AOA sia benpiu complessa rispetto alla AON. Infatti e stato necessario introdurre unaserie di attivita fittizie (indicate dai collegamenti tratteggiati) per rappre-sentare correttamente i legami temporali tra queste. Si ritiene che le retiAON siano piu facili da costruire, piu semplici da rivedere e molto piu com-prensibili rispetto alle reti AOA.Ha senso chiedersi a questo punto qual e il tempo richiesto dal progetto peressere realizzato. Poiche ci sono alcune attivita che possono essere svolte inparallelo e chiaro che tale tempo non coincide con la somma delle durate delleattivita ma e legato alla lunghezza dei cammini lungo la rete. In una retedi progetto si devono considerare i cammini che partono dal nodo inizialee arrivano a quello finale. La lunghezza e la somma delle durate (teoriche)delle attivita che fanno parte del cammino. Nella tabella 5.2 sono riportati ivari cammini dell’esempio introdotto in precedenza con le relative lunghezze.La durata del progetto non puo essere inferiore alla lunghezza di un cam-mino ma potrebbe essere superiore. Consideriamo infatti l’attivita L che epreceduta da D e da E e che fa parte di due cammini. E chiaro che L potraessere eseguita non dopo 10 settimane (cioe dopo le attivita A-B-E) ma dopo


Cammino LunghezzaINIZIO-A-B-C-G-I-FINE 22 settimaneINIZIO-A-B-C-F-I-FINE 23 settimaneINIZIO-A-B-D-F-I-FINE 22 settimaneINIZIO-A-B-D-H-I-FINE 24 settimaneINIZIO-A-B-D-L-FINE 18 settimaneINIZIO-A-B-E-L-FINE 17 settimane

Tabella 6.2:

11 settimane (cioe dopo lo svolgimento delle attivita A-B-D che richiedonopiu tempo). La durata del progetto e uguale alla lunghezza del cammino piulungo, che prende il nome di cammino critico. Nell’esempio visto esiste uncammino critico che ha lunghezza pari a 24 settimane. Le attivita presentiin questo cammino devono essere eseguite senza ritardi pena l’allungamentodei tempi di realizzazione del progetto. Nell’ipotesi che si voglia accorciaretale tempo la tecnica CPM consente di farlo utlizzando la cosiddetta analisidel trade-off tempi-costi.

I Diagrammi di Gantt

Un modo grafico alternativo per rappresentare le attivita nella tecnica PERTsono, appunto, i diagrammi di Gantt, che mettono in evidenza le connessionie la collocazione temporali tra le attivita in relazione al periodo in cui ilprogetto viene realizzato. Nel diagramma viene riportato l’elenco delle at-tivita, ad ognuna delle quali viene associato graficamente il periodo in cuidovrebbe essere realizzata. In relazione all’esempio visto prima il Diagrammadi Gantt e il seguente.


Attivita

A

B

C

D

E

F

G

H

I

L

5 10 15 20

Il diagramma di Gantt consente inoltre di analizzare visivamente il camminocritico ma anche di verificare le conseguenze di possibili ritardi nella realiz-zazione di parti del progetto. Nell’esempio in questione si puo osservare cheun ritardo nella realizzazione dell’attivita L inferiore alle 5 settimane nonavrebbe alcuna conseguenza sulla realizzazione globale del progetto

6.5.1 Trade-off tempi-costi per le attivita

Concetto chiave di questo approccio e il cosiddetto crashing. Il crashing diun’attivita si riferisce alla possibilita di ridurre la sua durata utilizzando pro-cedure particolarmente costose. Il crashing di un progetto significa effettuareil crashing di alcune attivita al fine di ridurre la durata del progetto. Il meto-do CPM del trade-off tempi-costi consente di determinare di quanto ridurrela durata di ogni attivita per ridurre la durata del progetto. La tabella delleattivita del CPM e molto piu complessa di quella del PERT perche per ogniattivita si deve indicare il periodo di crash, cioe di quanto puo essere ridottala durata, il costo normale, il costo di crash (che e superiore al costo nor-male), la riduzione massima dei tempi ed il costo aggiuntivo per ogni periododi tempo (giorno o settimana) risparmiato. In un grafico tempi-costi il puntonormale mostra che la durata ed il costo quando l’attivita viene portata atermine normalmente. Il punto crash indica la durata ed il costo quandol’attivita viene accelerata senza badare a spese pur di ridurre la sua durata.La tecnica CPM assume che i tempi e i costi di crash possano essere noticon una buona approssimazione. Per determinare l’attivita (o le attivita) dasottoporre a crash si deve costruire una tabella in cui ad ognuna di queste


Attivita Tempi Costi Riduzione Costo perNormali Crash Normali Crash massima sett. risp.

A 3 2 100 160 1 60B 4 3 120 180 1 60C 5 4 150 200 1 50D 4 3 200 280 1 80E 3 2 120 160 1 40F 4 3 50 80 1 30G 3 2 60 80 1 20H 6 4 200 300 2 50I 7 5 200 300 2 50L 7 4 100 310 3 70

Tabella 6.3:

vengano associati il tempo normale e di crash, i costi normale e di crash,la riduzione massima dei tempi ed il costo risparmiato per unita di tempo.Spesso un crashing di tutte le attivita e un’operazione che, pur riducendonotevolmente i tempi di esecuzione del progetto, avrebbe, in generale, deicosti proibitivi, quindi e necessario determinare le attivita in base al tempodel quale si vuole ridurre la durata del progetto e del costo aggiuntivo chenon deve incidere in modo significativo sul costo complessivo. Per questatecnica la tabella che abbiamo introdotto in precedenza per descrivere le at-tivita deve essere modificata aggiungendo le informazioni legate ai costi e aitempi di crash (vedere tabella 5.3). Supponendo di dover eseguire il progettoutilizzando un budget non superiore a 1500 ed in un periodo di tempo nonsuperiore a 21 settimane osserviamo che, senza effettuare il crash di alcunaattivita, il costo del progetto e pari a 1300 mentre abbiamo visto che il cam-mino critico ha lunghezza pari a 24 settimane, quindi e necessario effettuareil crash di alcune attivita. La tecnica dell’analisi marginale dei costi prevededi effettuare il crash solo sulle attivita appartenenti al cammino critico epartendo da quelle che presentano un costo inferiore per settimana risparmi-ata. Nell’esempio introdotto in precedenza le attivita da considerare primasono I e H. Sottoponendo a crash l’attivita I per due settimane il costocomplessivo sale a 1400 mentre il numero di settimane scende a 22. Poichenon sono stati raggiunti gli obiettivi prefissati si continua sottoponendo acrash anche l’attivita H per una settimana in modo tale che il costo arriva a


1450 ed il numero di settimane necessarie scende a 21. Avendo raggiunto illimite temporale previsto per la realizzazione del progetto non e necessariosottoporre a crash nessun’altra attivita.Tale analisi presenta lo svantaggio di essere molto dispendiosa se la rete emolto complessa. In alternativa all’analisi marginale dei costi si puo utiliz-zare la programmazione lineare per risolvere il problema. Definiamo quindile seguenti variabili decisionali:

xj = riduzione della durata della j−esima attivita, j = A,B,C, . . . , I

e risolviamo il problema di minimizzare il costo aggiuntivo dovuto al crashdelle attivita:

min Z = 60xA + 60xB + 50xC + . . .

I vincoli per le variabili decisionali sono quelli di nonnegativita:

xA, xB, xC , . . . , xI ≥ 0

a cui dobbiamo aggiungere quelli relativi al massimo crash consentito edevidenziato nella tabella 5.3:

xA ≤ 1, xB ≤ 1, . . . , xI ≤ 3.

Indichiamo ora con yFINE il tempo di durata del progetto. Vogliamo che sia

yFINE ≤ 21.

e definiamo le ulteriori variabili

yj = tempo di inizio della j−esima attivita, j = B,C, . . . , I

con yA = 0. Ovviamente dobbiamo porre dei vincoli sui tempi di iniziodelle attivita. Un attivita generica deve iniziare nel momento che si ottienesommando al tempo di inizio del suo predecessore, la durata del predecessoree sottraendo il tempo di riduzione dovuto al crash, per esempio:

yB ≥ yA + tempo di A − xA

yB ≥ yA + 4 − xA

yC ≥ yB + 4 − xB

yD ≥ yB + 4 − xB

yE ≥ yB + 4 − xB

...


e cosı via. Se un’attivita ha piu predecessori si procede in modo analogo,aumentando pero il numero di vincoli:

yF ≥ yC + 5 − xC

yF ≥ yD + 4 − xD

...yFINE ≥ yI + 7 − xI

yFINE ≥ yL + 7 − xL.

Capitolo 1 Introduzionetiziano19661.interfree.it/pdf0910/ricerca0910.pdf · La nascita della...

Documents

Transcript of Capitolo 1 Introduzionetiziano19661.interfree.it/pdf0910/ricerca0910.pdf · La nascita della...