Appunti di Ricerca Operativa PDF

UNIVERSITÀ DEGLI STUDI DI NAPOLI FEDERICO II Scuola Politecnica e delle Scienze di Base Area Didattica Scienze Matematiche Fisiche e Naturali Appunti di Ricerca Operativa Paola Festa price(2)=2...

UNIVERSITÀ DEGLI STUDI DI NAPOLI FEDERICO II Scuola Politecnica e delle Scienze di Base Area Didattica Scienze Matematiche Fisiche e Naturali Appunti di Ricerca Operativa Paola Festa price(2)=2 2 2 2 1 price(1)=3 1 4 1 4 price(4)=0 2 2 3 3 price(3)=2 Appunti di Ricerca Operativa Paola Festa Dip. di Matematica e Applicazioni Studio 133 - Tel. 081 675605 E mail: [email protected] Indice 1 Introduzione 7 1.1 Classificazione dei problemi di ottimizzazione............. 8 1.2 Classificazione dei metodi risolutivi................... 9 2 Programmazione Lineare 11 2.1 Definizione di problema di Programmazione Matematica....... 12 2.2 Definizione di problema di Programmazione Lineare......... 13 2.3 Esempi di problemi di PL........................ 14 2.3.1 Un problema di trasporto.................... 14 2.3.2 Un problema di produzione................... 16 2.3.3 Il problema della dieta...................... 18 2.4 Forma standard di un problema di PL................. 19 2.4.1 Trasformazione della funzione obiettivo............ 20 2.4.2 Trasformazioni dei vincoli.................... 20 2.4.3 Nonnegatività dei termini noti................. 21 2.4.4 Trasformazioni delle variabili.................. 21 2.4.5 Formulazione standard di un generico problema di PL.... 22 2.5 Interpretazione e soluzione grafica di un problema di PL....... 25 2.6 Geometria della Programmazione Lineare............... 29 2.6.1 Poliedri ed insiemi convessi................... 30 2.6.2 Insiemi convessi.......................... 31 2.6.3 Punti estremi, vertici e soluzioni di base ammissibili..... 33 2.6.4 Poliedri in forma standard.................... 38 3 4 INDICE 2.6.5 Soluzioni di base degeneri.................... 42 2.6.6 Esistenza di punti estremi.................... 45 2.6.7 Ottimalità di punti estremi................... 47 2.7 Il Metodo del Simplesso......................... 48 2.7.1 Condizioni di ottimalità..................... 49 2.7.2 Il Metodo del Simplesso..................... 54 2.7.3 Il Metodo del Simplesso Revisionato.............. 61 2.7.4 Il Metodo del Simplesso Tabellare............... 63 2.7.5 Confronto fra il Simplesso Revisionato ed il Simplesso Tabellare 71 2.7.6 Come trovare una soluzione di base ammissibile iniziale... 71 3 Programmazione Lineare Intera 79 3.1 Introduzione................................ 79 3.2 Rilassamento continuo.......................... 82 3.2.1 Relazioni fra un problema di PLI ed il suo rilassamento continuo 84 3.2.2 Matrice dei vincoli unimodulare................. 85 3.3 Metodi dei Piani di Taglio........................ 98 3.3.1 Algoritmo di Gomory...................... 100 3.4 Branch & Bound (B&B)......................... 106 3.4.1 Criterio di Bounding....................... 112 3.4.2 Scelta della variabile di branching............... 113 3.4.3 Branch & Bound: esempio.................... 114 3.4.4 Generazione/Visita del Branching Tree............. 123 3.4.5 Zaino 0/1 e Zaino Frazionario.................. 126 3.5 Programmazione Dinamica (PD).................... 141 3.5.1 Due algoritmi di PD per il Problema dello Zaino 0/1..... 143 4 Ottimizzazione su grafi e reti 149 4.1 Cenni di teoria dei grafi......................... 149 4.1.1 Grafi non orientati........................ 149 4.1.2 Grafi orientati.......................... 154 4.1.3 Rappresentazione di grafi.................... 157 4.1.4 Rappresentazione di cammini.................. 162 INDICE 5 4.2 Il Problema del Vertex Cover Minimo................. 163 4.2.1 Il Problema del Vertex Cover Pesato.............. 164 4.2.2 Un algoritmo di approssimazione per il Vertex Cover..... 164 4.3 Minimum Spanning Tree (MST).................... 167 4.3.1 Minimum Spanning Tree: condizioni di ottimalità...... 169 4.3.2 Algoritmo di Kruskal....................... 174 4.3.3 Algoritmo di Prim........................ 180 4.4 Cammini................................. 186 4.4.1 Il problema della raggiungibilità: visita in ampiezza..... 187 4.4.2 Il problema della raggiungibilità: visita in profondità..... 189 4.5 Problemi di Cammino Minimo..................... 191 4.5.1 L’algoritmo di Dijkstra..................... 195 4.5.2 L’algoritmo di Floyd-Warshall................. 203 4.6 Pianificazione di un progetto...................... 208 4.6.1 Il Problema della Pianificazione di un Progetto........ 212 4.6.2 Critical Path Method (CPM).................. 213 4.7 Problemi di Flusso............................ 218 4.7.1 Il Problema del Massimo Flusso e il Problema di Flusso a Costo Minimo........................... 219 4.7.2 Proprietà e caratteristiche dei Problemi di Flusso....... 220 4.7.3 Proprietà fondamentali dei Flussi su Rete........... 223 4.7.4 Algoritmo di Ford-Fulkerson per il Problema del Massimo Flusso............................... 226 5 Esercizi 243 5.1 Programmazione Lineare......................... 243 5.2 Ottimizzazione su reti e grafi...................... 257 6 Appendice A 263 6 INDICE Capitolo 1 Introduzione La Ricerca Operativa è la disciplina che studia e mette a punto metodologie ed algoritmi per la risoluzione di problemi di ottimizzazione, ossia problemi in cui tipicamente occorre prendere decisioni circa l’uso di risorse disponibili solo in quantità limitate in modo tale da rispettare un assegnato insieme di vincoli e da massimizzare il beneficio ottenibile dall’uso delle risorse o minimizzare il costo totale che comporta l’utilizzo delle risorse stesse. Un processo decisionale alla base dell’analisi e risoluzione di un problema di ottimizzazione può essere scomposto nelle seguenti fasi: i. individuazione del problema e delle sue caratteristiche; ii. costruzione di un modello logico-matematico che lo rappresenti (formu- lazione degli obiettivi e scelta della variabili di interesse, dette variabili di decisione); iii. determinazione di una o più soluzioni; iv. analisi dei risultati ottenuti. 7 8 CAPITOLO 1. INTRODUZIONE 1.1 Classificazione dei problemi di ottimizzazione Tipicamente, un problema viene definito per mezzo di 1. una descrizione dei suoi parametri, lasciati in generale indeterminati; 2. una descrizione delle proprietà che deve esibire la soluzione desiderata. Un altro modo per definire un problema è fornire l’insieme P di tutte le sue possibili soluzioni. P è detto insieme ammissibile ed i suoi elementi soluzioni ammissibili. Un problema di ottimizzazione è un problema tale che sull’insieme delle sue soluzioni ammissibili è definita una funzione obiettivo c:P →R da massimizzare, se c esprime un profitto o beneficio associato ad ogni soluzione, oppure da minimizzare se c ne esprime un costo. Dunque, una soluzione ottima al problema è una soluzione x ∈ P che rende minima o mas- sima la funzione obiettivo. Tale tipo di problema può essere genericamente scritto come (P ) min{c(x) : x ∈ P }. Dato un problema (P ), indichiamo con z ∗ = min{c(x) : x ∈ P } il valore ottimo della funzione obiettivo ed una soluzione x∗ ∈ P tale che z ∗ = c(x∗ ) è detta soluzione ottima di (P ). In alcuni casi, invece di richiedere una soluzione ottima di un problema, può essere richiesto di individuarne una qualsiasi soluzione ammissibile, ossia di determinare se l’insieme delle soluzioni ammissibili sia vuoto o meno. In casi del genere, si parla di problema decisionale o problema di esistenza. Ad un problema decisionale è naturalmente associato il cosiddetto problema di certificato, che consiste nello stabilire se un dato x appartenga o meno 1.2. CLASSIFICAZIONE DEI METODI RISOLUTIVI 9 a P. Ovviamente, un problema di certificato è un particolare problema decisionale che prevede come soluzione “sı̀” oppure “no”. È banale osservare che un qualunque problema di ottimizzazione può essere interpretato come problema decisionale. Basta, infatti, interpretare l’insieme delle soluzioni ottime come insieme in cui ricercare una soluzione ammissibile. Analogamente, qualunque problema decisionale può essere in- terpretato come problema di ottimizzazione (per es. un problema di min- imo), dato che è sempre possibile definire per un problema decisionale una funzione obiettivo che associ 0 ad ogni elemento x ∈ P ed 1 altrimenti. Una volta formulato, un problema di ottimizzazione va chiaramente risolto tramite applicazione di un metodo che, data una qualunque istanza i del problema, fornisca una soluzione in un tempo finito. Dal punto di vista computazionale-algoritmico, i problemi di ottimizzazione si suddividono in problemi computazionalmente trattabili e problemi computazionalmente in- trattabili. Tali due classi coincidono in larga parte rispettivamente con la classe dei problemi polinomiali P (cioè che richiedono un tempo polinomiale per essere risolti all’ottimo) e la classe dei problemi N P-ardui. 1.2 Classificazione dei metodi risolutivi Gli algoritmi utilizzati per risolvere i problemi di ottimizzazione si suddivi- dono in tre categorie principali: Metodi esatti: essi risolvono il problema all’ottimo. In caso di prob- lemi computazionalmente intrattabili, essi richiedono complessità com- putazionale esponenziale o comunque superpolinomiale. Metodi di approssimazione: essi trovano una soluzione subottima, garantendo un indice della qualità della soluzione approssimata indi- viduata. La loro applicazione risulta utile in caso di problemi com- 10 CAPITOLO 1. INTRODUZIONE putazionalmente intrattabili. È chiaro che in tal caso sarebbe auspica- bile che il tempo di computazione da essi richiesto sia polinomiale (se avessero complessità superpolinomiale, non si avrebbe alcun vantaggio nell’applicarli!). Metodi euristici: essi trovano una soluzione subottima senza alcuna garanzia circa la qualità della soluzione individuata, per cui è ovvio che ha senso la messa a punto di euristiche solo polinomiali. L’applicazione di tali metodi è particolarmente indicata per risolvere problemi del mondo reale di grandi dimensioni e/o problemi talmente difficili dal punto di vista computazionale che per essi non esiste neanche un al- goritmo capace di trovare una soluzione approssimata in tempo poli- nomiale. Capitolo 2 Programmazione Lineare Nell’Introduzione un processo decisionale alla base dell’analisi e risoluzione di un problema di ottimizzazione è stato definito come un processo scom- ponibile nelle seguenti fasi: i. individuazione del problema e delle sue caratteristiche; ii. costruzione di un modello logico-matematico che lo rappresenti (formu- lazione degli obiettivi e scelta della variabili di interesse, dette variabili di decisione); iii. determinazione di una o più soluzioni; iv. analisi dei risultati ottenuti. In questo capitolo impareremo a costruire il modello logico-matematico a partire dalla descrizione verbale di un problema e delle sue caratteristiche, ossia definiremo formalmente un problema di Programmazione Matematica ed in particolare un problema di Programmazione Lineare (PL). Saranno, inoltre, descritti alcuni esempi di problemi di PL che chiariranno i concetti esposti. 11 12 CAPITOLO 2. PROGRAMMAZIONE LINEARE 2.1 Definizione di problema di Programmazione Matematica Sia (x1 , x2 ,... , xn ) = x ∈ Rn una variabile vettoriale ad n componenti, dette variabili di decisione. Siano {gi (x) : Rn → R, i = 1, 2,... , m} m funzioni scalari del vettore decisionale x e sia (b1 , b2 ,... , bm ) = b ∈ Rm un vettore a componenti scalari detto vettore dei termini noti. La variabile x è detta vincolata se per ogni i = 1, 2,... , m deve essere soddisfatta almeno una delle seguenti relazioni: (1) gi (x) ≤ bi ; (2) gi (x) = bi ; (3) gi (x) ≥ bi. Le relazioni (1) e (3) sono dette vincoli di disuguaglianza, mentre la relazione (2) è detta vincolo di uguaglianza. L’insieme S = {x ∈ Rn | gi (x) ≈ bi }, dove con il simbolo ≈ si intende che per ogni i vale uno dei tre simboli ≤, ≥, =, è detto insieme ammissibile. Esso è cioè l’insieme dei punti x ∈ Rn che soddisfano i vincoli sulle variabili. Si consideri ora un’ulteriore fun- zione scalare z(x) della variabile x detta funzione obiettivo e si consideri il problema di determinare il valore della variabile x che renda minima (risp. massima) la funzione obiettivo z(x) sull’insieme S, cioè nel rispetto dei vin- coli sulle variabili di decisione del tipo (1), (2) o (3). In termini formali, consideriamo il seguente problema: 2.2. DEFINIZIONE DI PROBLEMA DI PROGRAMMAZIONE LINEARE13 min z(x) (risp. max z(x)) s.a (soggetto a) g1 (x) ≈ b1 g2 (x) ≈ b2 ··· ≈ ··· gm (x) ≈ bm. Il problema appena descritto è un problema di Programmazione Matem- atica, la cui soluzione x∗ è chiaramente un punto appartenente ad S ed inoltre risulta che ∀ x ∈ S z(x∗ ) ≤ z(x) (risp. z(x∗ ) ≥ z(x)). x∗ è detto un punto di minimo vincolato (risp. massimo vincolato) per la funzione obiettivo z(x). 2.2 Definizione di problema di Programmazione Lineare Un problema di Programmazione Matematica è detto di Programmazione Lineare se ciascuna delle funzioni z(x) e {gi (x) : Rn → R, i = 1, 2,... , m} è lineare rispetto alla variabile x, cioè se z(x) = c1 x1 + c2 x2 + · · · + cn xn gi (x) = ai1 x1 + ai2 x2 + · · · + ain xn , i = 1, 2,... , m, dove cj , j = 1, 2,... , n e aij , i = 1, 2,... , m, j = 1, 2,... , n sono costanti scalari date. Riassumendo, un problema di PL è un problema del tipo 14 CAPITOLO 2. PROGRAMMAZIONE LINEARE min (risp. max) z(x) = c1 x1 + c2 x2 + · · · + cn xn s.a a11 x1 + a12 x2 + · · · + a1n xn ≈ b1 a21 x1 + a22 x2 + · · · + a2n xn ≈ b2 ··· ≈ ··· am1 x1 + am2 x2 + · · · + amn xn ≈ bm e vale la seguente definizione. Definizione 2.2.1 Per problema di programmazione lineare (PL) s’intende il problema di minimizzare o massimizzare una funzione obiettivo lineare in presenza di vincoli di disuguaglianza e/o uguaglianza lineari. 2.3 Esempi di problemi di PL In quanto segue verranno descritti alcuni semplici esempi di problemi di PL che faranno comprendere quanto sia vasta la gamma di situazioni reali in cui la programmazione lineare può essere usata. 2.3.1 Un problema di trasporto Si immagini un’industria che produce un bene di consumo in due diversi sta- bilimenti di produzione, situati rispettivamente a Pomezia e a Caserta. La distribuzione alla rete di vendita avviene da due depositi situati rispettiva- mente a Roma e a Napoli. Nella Tabella seguente per ogni unità di prodotto è riportato il costo legato al trasporto dal sito di produzione (Pomezia o Caserta) al deposito (Roma o Napoli). Lo stabilimento di Pomezia non può produrre settimanalmente più di 10000 unità di bene, mentre quello di Caserta non ne può produrre più di 8000. Inoltre, da statistiche fatte sulle vendite, risulta che ogni settimana 2.3. ESEMPI DI PROBLEMI DI PL 15 Tratta Costo (in euro) Pomezia–Roma 10 Pomezia–Napoli 30 Caserta–Napoli 5 Caserta–Roma 35 vengono vendute almeno 11000 unità di bene tramite il deposito situato a Roma e almeno 4600 unità tramite il deposito situato a Napoli. Obiettivo dell’industria è minimizzare il costo totale del trasporto della merce dagli stabilimenti ai depositi, assicurando al tempo stesso che ciascun deposito riceva settimanalmente le quantità su indicate. In questo caso, le variabili di decisione sono le quantità di bene trasportate settimanalmente dagli stabilimenti ai depositi: x1 = quantità di bene trasportata da Pomezia a Roma; x2 = quantità di bene trasportata da Pomezia a Napoli; x3 = quantità di bene trasportata da Caserta a Napoli; x4 = quantità di bene trasportata da Caserta a Roma. La funzione obiettivo è il costo totale sostenuto settimanalmente per il trasporto dagli stabilimenti ai depositi: z(x1 , x2 , x3 , x4 ) = 10x1 + 30x2 + 5x3 + 35x4. Come sottolineato, i due stabilimenti hanno capacità produttiva limi- tata. Tali limitazioni si traducono formalmente nell’imposizione dei seguenti vincoli: x1 + x2 ≤ 10000; x3 + x4 ≤ 8000. Il rifornimento medio settimanale ai depositi è garantito dall’imposizione dei seguenti vincoli: 16 CAPITOLO 2. PROGRAMMAZIONE LINEARE x1 + x4 ≥ 11000; x2 + x3 ≥ 4600. Infine, è più che evidente che ciascuna quantità xj , j = 1, 2, 3, 4 non può essere negativa. Dunque, la formulazione matematica completa del problema di trasporto descritto è la seguente: min z(x) = 10x1 + 30x2 + 5x3 + 35x4 s.a x1 + x2 ≤ 10000 x3 + x4 ≤ 8000 x1 + x4 ≥ 11000 x2 + x3 ≥ 4600 xi ≥ 0 ed intero, i = 1, 2, 3, 4. 2.3.2 Un problema di produzione Un pastificio produce pacchi da 500 gr. di 2 tipi di pasta: spaghetti e rigatoni. Per produrre tali beni sono necessarie 3 differenti materie prime: acqua, farina di grano duro e cartone per le scatole. Ciascun pacco da 500 gr. di spaghetti e rigatoni richiede le quantità di materie prime indicate nella Tabella 2.1. Pasta (500 gr.) Acqua (in l.) Farina (in Kg.) Cartone (in m2 ) Spaghetti 1 0.3 0.8 Rigatoni 1.5 0.28 0.6 Tabella 2.1: Quantità di materie prime richieste da ciascun pacco da 500 gr. di spaghetti e rigatoni. Per procurarsi le materie prime, il pastificio si serve di 3 fornitori che annualmente garantiscono per ciascuna materia prima le seguenti forniture: 2.3. ESEMPI DI PROBLEMI DI PL 17 Acqua (in l.) Farina (in Kg.) Cartone (in m2 ) 10000000 100000 50000 Per ciascun pacco da 500 gr. di spaghetti e rigatoni venduto il pastificio ricava i profitti riportati nella Tabella seguente. Pasta (500 gr.) Profitto (in euro) Spaghetti 0.50 Rigatoni 0.62 Obiettivo del pastificio è trovare la quantità di pacchi da 500 gr. di spaghetti e rigatoni da produrre annualmente tale da massimizzare il profitto totale ricavato dalla vendita. In questo caso, le variabili di decisione sono le quantità di pacchi da 500 gr. di spaghetti e rigatoni da produrre annualmente: xs = quantità di pacchi da 500 gr. di spaghetti da produrre all’anno; xr = quantità di pacchi da 500 gr. di rigatoni da produrre all’anno. La funzione obiettivo è il profitto totale ricavato annualmente dalla ven- dita dei pacchi da 500 gr. di spaghetti e rigatoni: z(xs , xr ) = 0.50xs + 0.62xr. Come sottolineato, le materie prime sono fornite annualmente in quan- tità limitate. Tali limitazioni si traducono formalmente nell’imposizione dei seguenti vincoli: xs + 1.5xr ≤ 10000000; 0.3xs + 0.28xr ≤ 100000; 0.8xs + 0.6xr ≤ 50000. 18 CAPITOLO 2. PROGRAMMAZIONE LINEARE Come nell’esempio precedente, anche in questo caso è più che evidente che le quantità xs ed xr non possono essere negative. Dunque, la formu- lazione matematica completa del problema descritto è la seguente: max z(x) = 0.50xs + 0.62xr s.a xs + 1.5xr ≤ 10000000 0.3xs + 0.28xr ≤ 100000 0.8xs + 0.6xr ≤ 50000 xi ≥ 0 ed intero, i = s, r. 2.3.3 Il problema della dieta Supponiamo di disporre di n alimenti caratterizzati da m fattori nutrizionali diversi e che per ogni alimento nella seguente Tabella sia riportato il valore nutrizionale unitario. alimento 1 alimento 2... alimento n fattore nutriz. 1 a11 a12... a1n fattore nutriz. 2 a21 a22... a2n............... fattore nutriz. m am1 am2... amn Si noti che il generico elemento aij contenuto in Tabella esprime il con- tenuto nutrizionale di tipo i di un’unità dell’ alimento di tipo j. Supponiamo che ad ogni unità di alimento di tipo j sia associato un costo cj (prezzo al supermercato). Indicato con b = (b1 , b2 ,... , bm ) il vettore con- tenente i valori nutrizionali di una dieta ideale per un adulto maschio di 30 anni, si vuole trovare la combinazione di alimenti x = (x1 , x2 ,... , xn ) che ab- bia il costo totale minimo e che al contempo soddisfi le esigenze nutrizionali contenute in b. 2.4. FORMA STANDARD DI UN PROBLEMA DI PL 19 Ebbene, tale problema è matematicamente formulabile come segue: n X (P ) min z(x) = cj xj j=1 s.a a11 x1 + a12 x2 +... + a1n xn = b1 (1.1) a21 x1 + a22 x2 +... + a2n xn = b2 (1.2)............... am1 x1 + am2 x2 +... + amn xn = bm (1.m) xj ≥ 0 j = 1, 2,... , n. In una variante del problema descritto, b potrebbe rappresentare il vet- tore dei fattori nutrizionali minimi richiesti affinchè una dieta si possa definire ”equilibrata” per un maschio adulto di 30 anni. In tal caso i vincoli del prob- lema diventano vincoli di ≥. 2.4 Forma standard di un problema di PL Il problema (P ) descritto nel paragrafo precedente si dice formulato in forma standard. In generale, vale la seguente definizione. Definizione 2.4.1 Un problema di PL si dice formulato in forma standard se si tratta di minimizzare una funzione obiettivo lineare soggetta a vincoli di uguaglianza, se le variabili di decisione sono vincolate ad essere nonnegative e il vettore dei termini noti è nonnegativo. Ogni problema di PL può essere formulato in forma standard applicando, qualora necessario, opportune trasformazioni alla funzione obiettivo, ai vin- coli ed alle variabili, per cui nel prosieguo della trattazione di problemi di PL, faremo sempre riferimento a problemi formulati in forma standard. 20 CAPITOLO 2. PROGRAMMAZIONE LINEARE 2.4.1 Trasformazione della funzione obiettivo È sempre possibile assumere che la funzione obiettivo lineare z(x) sia da minimizzare, in quanto il valore della variabile x∗ che rende massima z(x) rende minima la stessa funzione cambiata di segno: max z(x) = −min − z(x). 2.4.2 Trasformazioni dei vincoli Un qualsiasi vincolo può essere trasformato in vincolo di uguaglianza intro- ducendo opportune variabili aggiuntive nonnegative. Infatti, un vincolo del tipo n X aij xj ≤ bi j=1 può essere equivalentemente riscritto nella seguente forma: n X aij xj + xn+1 = bi , xn+1 ≥ 0, j=1 dove xn+1 rappresenta la differenza nonnegativa tra il secondo ed il primo membro della disuguaglianza e viene detta variabile di slack. Un vincolo del tipo n X aij xj ≥ bi j=1 può, invece, essere equivalentemente riscritto nella seguente forma: n X aij xj − xn+1 = bi , xn+1 ≥ 0, j=1 dove xn+1 rappresenta la differenza nonnegativa tra il primo ed il secondo membro della disuguaglianza e viene detta variabile di surplus. 2.4. FORMA STANDARD DI UN PROBLEMA DI PL 21 2.4.3 Nonnegatività dei termini noti È sempre possibile assumere che ogni componente del vettore dei termini noti b sia nonnegativa. Infatti, se cosı̀ non fosse, è sufficiente moltiplicare per (−1) entrambi i membri del vincolo ed eventualmente cambiare verso della disuguaglianza se il vincolo in questione non è un vincolo di uguaglianza. 2.4.4 Trasformazioni delle variabili È sempre possibile assumere che le variabili di decisione siano vincolate ad essere nonnegative. Infatti, se per qualche j = 1, 2,... , n risulta che xj ≤ 0, allora basta effettuare nella formulazione matematica la sosti- tuzione xj = −x′j , x′j ≥ 0; xj non è vincolata in segno, allora basta effettuare nella formulazione matematica la sostituzione xj = x+ − + − j − xj , xj ≥ 0, xj ≥ 0. Esempio 2.4.1 Consideriamo il problema di PL avente la seguente formu- lazione matematica: max z(x) = −3x1 − 2x2 + 5x3 + x4 s.a −x1 + x2 ≥1 x2 + 3x3 =4 x1 + 2x3 − x4 ≥ −2 x2 + x3 + 5x4 ≤3 xj ≥ 0 j = 1, 2, 3. e riscriviamolo in forma standard. A tale fine occorrerà: 1. trasformare la funzione obiettivo; 2. moltiplicare per (−1) entrambi i membri del terzo vincolo e cambiare verso della disuguaglianza; 22 CAPITOLO 2. PROGRAMMAZIONE LINEARE 3. introdurre la variabile di surplus x5 nel primo vincolo; 4. introdurre le variabili di slack x6 ed x7 nel terzo e nel quarto vincolo rispettivamente; 5. sostituire la variabile x4 non vincolata in segno con la differenza x4 −x8 , x4 ≥ 0, x8 ≥ 0. È semplice verificare che, applicando le trasformazioni 1 − 5, si ottiene la seguente formulazione matematica in forma standard e perfettamente equivalente alla precedente: min z(x) = 3x1 + 2x2 − 5x3 − x4 + x8 s.a −x1 + x2 − x5 =1 x2 + 3x3 =4 −x1 − 2x3 + x4 + x6 − x8 =2 x2 + x3 + 5x4 + x7 − 5x8 =3 xj ≥ 0, j = 1, 2,... , 8. 2.4.5 Formulazione standard di un generico problema di PL La formulazione standard di un generico problema di PL è, dunque, la seguente: min z(x) = c1 x1 + c2 x2 + · · · + cn xn s.a a11 x1 + a12 x2 +... + a1n xn = b1 (1.1) a21 x1 + a22 x2 +... + a2n xn = b2 (1.2)............... am1 x1 + am2 x2 +... + amn xn = bm (1.m) xj ≥ 0, j = 1, 2,... , n 2.4. FORMA STANDARD DI UN PROBLEMA DI PL 23 e con bi ≥ 0, i = 1, 2,... , m. Si indichino con A ∈ Rm×n , b ∈ Rm e c ∈ Rn rispettivamente la matrice dei coefficienti tecnologici aij , i = 1, 2,... , m, j = 1, 2,... , n, il vettore m- dimensionale dei termini noti e il vettore n-dimensionale dei coefficienti della funzione obiettivo che possono essere coefficienti di costo (prob. di minimo) oppure coefficienti di profitto (prob. di massimo). Dunque,   a a12... a1n  11   a  21 a22... a2n  A= ,  ............    am1 am2... amn   b1    b2  b= ,  ..  .   bm   c1    c2  c= .  ..  .   cn Allora la precedente formulazione può essere scritta nella seguente forma compatta: min z(x) = c′ x s.a Ax = b x ≥ 0. Si suppone, inoltre, che siano verificate le seguenti tre ipotesi: 24 CAPITOLO 2. PROGRAMMAZIONE LINEARE 1. rango[A]=rango[A|b]; 2. m < n; 3. la matrice A non ha colonne nulle. L’ipotesi 1 serve a garantire che il sistema Ax = b ammetta soluzione. L’esistenza dell’ipotesi 2 è legata alle seguente considerazione. Se m = n, il sistema Ax = b ammetterebbe un’unica soluzione e dunque non avrebbe senso minimizzare z(x), in quanto la regione ammissibile o conterrebbe un unico punto o sarebbe vuota, a seconda del segno delle variabili di decisione. L’ipotesi 3, invece, si giustifica in base alle seguente osservazione. La con- dizione per cui la j.ma colonna di A contiene tutti zeri implicherebbe che il valore della variabile di decisione xj sarebbe immediatamente determinabile. Infatti, se cj ≥ 0, allora xj = 0, mentre invece se cj < 0, allora il valore ottimo della funzione obiettivo z(x) sarebbe un valore infinitamente piccolo e cioè il problema sarebbe illimitato inferiormente. In alcuni casi sarà supposta verificata la seguente ulteriore quarta ipotesi 4. rango[A]= m, allo scopo di evitare che qualche vincolo sia combinazione lineare di altri vincoli e perciò ridondante. Si noti che se verificata l’ipotesi 4, non può accadere che m > n. Dunque, la veridicità delle ipotesi 1, 2 e 4 implica che il sistema di equazioni lin- eari Ax = b non abbia vincoli ridondanti e che abbia un numero infinito di soluzioni, condizione questa necessaria affinchè il problema di PL abbia senso. Si noti, infine, che la veridicità delle ipotesi 2 e 4 implica la veridicità anche dell’ipotesi 1. Infatti, se A ha rango pari al suo numero di righe, allora A|b avrà lo stesso rango, poichè essa ha lo stesso numero di righe di A. 2.5. INTERPRETAZIONE E SOLUZIONE GRAFICA DI UN PROBLEMA DI PL25 2.5 Interpretazione e soluzione grafica di un prob- lema di PL Quando il problema di PL da dover risolvere è caratterizzato da due sole variabili decisionali, è possibile risolverlo immediatamente per via grafica. In questo paragrafo verranno illustrati alcuni semplici esempi di rappre- sentazione e soluzione grafica di problemi di PL in due variabili. Essi ci aiuteranno a meglio comprendere gli aspetti geometrici della natura di questi problemi. x2 (b) (a) x*= (1,1) S x1 c Figura 2.1: Rappresentazione grafica del problema dell’Esempio 2.5.1. Esempio 2.5.1 Si consideri il seguente problema: 26 CAPITOLO 2. PROGRAMMAZIONE LINEARE min z(x) = −x1 − x2 s.a x1 + 2x2 ≤3 (a) 2x1 + x2 ≤3 (b) xj ≥ 0 j = 1, 2. L’insieme ammissibile S è la regione mostrata in grigio in Figura 2.1. Essa è individuata dall’insieme dei vincoli nel modo seguente. In generale, nel piano cartesiano con assi coordinati (x1 , x2 ) l’equazione ax1 + bx2 = d individua un fascio di rette al variare di d. In particolare, al variare di d tali rette si muovono parallelamente a se stesse nella direzione individuata dal vettore (a, b)′. La disuguaglianza ax1 + bx2 ≥ d individua il semipiano posto rispetto alla retta ax1 + bx2 = d dalla parte verso cui è orientato il vettore (a, b)′. Consideriamo, ad esempio, il vincolo (a) del nostro esempio. Innanzitutto, va rappresentata la retta x1 + 2x2 = 3 che in Figura 2.1 è la retta (a). Inoltre, x1 + 2x2 = d individua un fascio di rette al variare di d. Al crescere di d tali rette si muovono parallelamente a se stesse nel verso opposto rispetto al vettore (1, 2)′ , dato che il vincolo (a) esprime una relazione di ≤. Per rappresentare il vincolo (b) si procede allo stesso modo. Dunque, la regione ammissibile S risulta quella mostrata in Figura 2.1 tenendo conto degli ulteriori vincoli di nonnegatività delle variabili di decisione x1 ed x2. Anche per individuare la soluzione ottima rappresentata sul piano carte- siono dal punto x∗ = (x∗1 , x∗2 ) si procede con analoghi ragionamenti. Al 2.5. INTERPRETAZIONE E SOLUZIONE GRAFICA DI UN PROBLEMA DI PL27 crescere di z l’equazione −x1 − x2 = z individua un fascio di rette che si muovono parallelamente a se stesse nella direzione individuata dal vet- tore (c1 , c2 ) = (−1, −1). Dal momento che il nostro scopo è minimiz- zare z, noi siamo interessati a muovere il fascio di rette nel verso del vet- tore −(c1 , c2 ) = (1, 1) senza mai abbondonare la regione ammissibile S. Guardando la Figura 2.1, è facile rendersi conto che il minimo valore pos- sibile per z è −2 e che il vettore x∗ = (1, 1) è la soluzione ottima cercata. La regione ammissibile S del problema dell’esempio precedente è limi- tata e la soluzione ottima è unica. Attraverso il seguente esempio vengono descritti altri casi possibili. Esempio 2.5.2 Si consideri la regione ammissibile S descritta dai seguenti vincoli e rappresentata in Figura 2.2 −x1 + x2 ≤ 1 (a) xj ≥ 0, j = 1, 2. A seconda della funzione obiettivo da minimizzare, si possono presentare i seguenti vari casi. 1. Se il vettore dei costi è c = (1, 1), è evidente che x∗ = (0, 0) è l’unica soluzione ottima del problema. 2. Se il vettore dei costi è c = (1, 0), allora ogni vettore x∗ = (0, x2 ), 0 ≤ x2 ≤ 1 è soluzione ottima del problema. Si noti che l’insieme delle soluzioni ottime è limitato. 3. Se il vettore dei costi è c = (0, 1), allora ogni vettore x∗ = (x1 , 0), x1 ≥ 0 è soluzione ottima del problema. Si noti che l’insieme delle soluzioni ottime è illimitato. 28 CAPITOLO 2. PROGRAMMAZIONE LINEARE x2 2 c= (1,0) c= (−1,−1) 1 S (a) c= (1,1) c= (0,1) 1 x1 Figura 2.2: Rappresentazione grafica del problema dell’Esempio 2.5.2. 4. Se il vettore dei costi è c = (−1, −1), allora è possibile ottenere una sequenza di soluzioni ammissibili il cui costo converge a −∞, per cui si dice che in tal caso il costo ottimo è −∞. 5. Se viene imposto il seguente ulteriore vincolo x1 + x2 ≤ −2 (b), allora è evidente che il problema non ammette alcuna soluzione, es- sendo S vuota. 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 29 Riassumendo quanto visto nel precedente Esempio 2.5.2, nell’affrontare un problema di PL possono verificarsi i seguenti quattro casi. 1. Il problema ammette un’unica soluzione ottima. 2. Il problema ammette soluzioni multiple e l’insieme delle soluzioni ot- time può essere limitato o illimitato. 3. Il costo ottimo è −∞ e nessuna soluzione ammissibile è ottima. 4. La regione ammissibile S è vuota. Una importante osservazione che emerge dagli Esempi precedenti è che se il problema ammette almeno una soluzione ottima, allora una soluzione ottima è collocata in un vertice della regione ammissibile S. Nel prossimo paragrafo verificheremo che questa è una caratteristica generale tipica dei problemi di PL la cui regione ammissibile abbia almeno un vertice. 2.6 Geometria della Programmazione Lineare In questo paragrafo saranno definite alcune entità geometriche che sono alla base della PL e che consentono un’approfondita comprensione delle idee fondamentali alla base di un qualunque metodo per la risoluzione di un problema di PL. In particolare, definiremo come poliedro un insieme descritto da un numero finito di vincoli di uguaglianza e disuguaglianza. (Dunque, la regione ammissibile di un problema di PL è un poliedro). Studieremo, poi, le proprietà geometriche dei poliedri, con particolare enfasi a lori elementi speciali, detti spigoli e vertici. Il risultato geometrico principale è che un poliedro non vuoto P ha almeno un vertice se e solo se non contiene una retta e che, se questo è il caso, allora la ricerca di una soluzione ottima ad un problema di PL avente P come regione ammissibile può limitarsi ai soli vertici. 30 CAPITOLO 2. PROGRAMMAZIONE LINEARE 2.6.1 Poliedri ed insiemi convessi Definizione 2.6.1 L’insieme P = {x ∈ Rn | Ax ≥ b}, dove A ∈ Rm×n e b ∈ Rm , è detto poliedro. Dunque, la regione ammissibile S di ogni problema di PL è un poliedro, dato che può essere descritta da vincoli di disugualianza del tipo Ax ≥ b. In particolare, un insieme del tipo {x ∈ Rn | Ax = b, x ≥ 0} è un poliedro rappresentato in forma standard. Un poliedro può essere limitato o illimitato. Definizione 2.6.2 Un insieme S ⊂ Rn è limitato se esiste una costante k tale che il valore assoluto di ogni componente di ogni elemento di S è minore o uguale a k, cioè se |xi | ≤ k, ∀i = 1, 2,... , n, ∀ x ∈ S. Definiremo, ora, alcuni poliedri speciali, data la loro semplicitá. Definizione 2.6.3 Sia a ∈ Rn e sia b ∈ R uno scalare. L’insieme {x ∈ Rn | a′ x = b} è detto iperpiano. L’insieme {x ∈ Rn | a′ x ≥ b} è detto semispazio. Innanzitutto, si noti che un iperpiano delimita un semispazio. Inoltre, il vettore a è perpendicolare all’iperpiano stesso. Infatti, se x ed y ap- partengono allo stesso iperpiano, allora per definizione di iperpiano a′ x = b e a′ y = b e cioè a′ x = a′ y. Dunque, a′ (x − y) = 0 e ciò implica che a è ortogonale ad ogni vettore giacente sull’iperpiano stesso. Un’altra impor- tante osservazione da sottolineare è che un poliedro è dato dall’intersezione di un numero finito di semispazi (in caso di vincoli di disuguaglianza) ed un numero finito di iperpiani (in caso di vincoli di uguaglianza). Esempi di iperpiani e semispazi sono mostrati in Figura 2.3. 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 31 a2’x=b2 a’xb a1 a2 a1’x=b1 a a3 a3’x=b3 b x= a5 a’ a5’ x=b 5 a4’x=b4 a4 (a) (b) Figura 2.3: (a) Un iperpiano e due semispazi. (b) Il poliedro {x | a′i x ≥ bi , i = 1, 2,... , 5} risultante dall’intersezione di cinque semispazi. Si noti che il vettore ai è perpendicolare all’iperpiano {x | a′i x = bi }. 2.6.2 Insiemi convessi Definizione 2.6.4 Un insieme S ⊂ Rn è convesso se ∀ x, y ∈ S e ∀ λ ∈ [0, 1] risulta che λx + (1 − λ)y = v ∈ S. Si noti che v risulta dalla media pesata di x ed y e dunque appartiene al segmento che unisce x ad y. Infatti, si può in generale affermare che un insieme S è convesso se il segmento che unisce due punti qualunque di S è tutto contenuto in S stesso. Esempi di insiemi convessi e non convessi sono mostrati in Figura 2.4. La definizione di convessità si può estendere al caso di media pesata di un numero finito di vettori. Definizione 2.6.5 Siano x1 , x2 ,... , xk vettori di Rn e siano λ1 , λ2 ,... , λk 32 CAPITOLO 2. PROGRAMMAZIONE LINEARE Q S x x y y (a) (b) Figura 2.4: (a) S è un insieme convesso. (b) Q non è un insieme convesso. scalari non negativi la cui somma dà l’unità, cioè k X λi ≥ 0, i = 1, 2,... , k e λi = 1. i=1 k X Il vettore λi xi è detto combinazione convessa dei vettori x1 , x2 ,... , xk. i=1 Si dice inviluppo convesso dei vettori x1 , x2 ,... , xk l’insieme di tutti i vettori combinazione convessa di x1 , x2 ,... , xk e si indica con conv(x1 , x2 ,... , xk ). Teorema 2.6.1 Valgono le seguenti proprietà, di cui trascuriamo in questo contesto la verifica. (a) L’intersezione di insiemi convessi è un insieme convesso. (b) Ogni poliedro è un insieme convesso. (c) La combinazione convessa di un numero finito di elementi di un in- sieme convesso S appartiene essa stessa all’insieme convesso S. (d) L’inviluppo convesso di un numero finito di vettori è un insieme con- vesso. 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 33 Figura 2.5: Inviluppo convesso di sette punti in Rn. 2.6.3 Punti estremi, vertici e soluzioni di base ammissibili Come già osservato, una soluzione ottima di un problema di PL tende ad essere in corrispondenza di un vertice della regione ammissibile. In questo paragrafo daremo tre definizioni equivalenti di vertice. La prima definizione definisce un vertice di un poliedro P come suo punto estremo, ossia un punto che non può essere espresso come combinazione convessa di altri due punti di P. Definizione 2.6.6 Sia P un poliedro. Un vettore x ∈ P è detto punto estremo di P se non esistono due vettori y, z ∈ P (y, z 6= x) ed uno scalare λ ∈ [0, 1], tali che x = λy + (1 − λ)z. Una definizione di punto estremo alternativa lo definisce come vertice di P , ossia come unica soluzione ottima di qualche problema di PL avente P come regione ammissibile. Definizione 2.6.7 Sia P un poliedro. Un vettore x ∈ P è detto vertice di P se esiste un vettore c tale che c′ x < c′ y, per ogni y ∈ P , y 6= x. 34 CAPITOLO 2. PROGRAMMAZIONE LINEARE u w P v z x y Figura 2.6: Il vettore w non è punto estremo di P , in quanto combinazione convessa di u e v. x è, invece, punto estremo di P. La terza definizione equivalente di vertice è algebrica e perciò utile ai fini algoritmici. Per comprenderla, sono necessarie alcune ulteriori definizioni, riportate di seguito. Consideriamo il seguente generico problema di PL: min c′ x (P) s.a a′i x ≥ bi i ∈ M1 a′i x ≤ bi i ∈ M2 a′i x = bi i ∈ M3 xj ≥0 j ∈ N1 xj ≤0 j ∈ N2 xj non vincolata j ∈ N3 Definizione 2.6.8 Se un vettore x∗ soddisfa a′i x = bi per qualche i ∈ M1 , 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 35 M2 o M3 , allora il corrispondente vincolo si dice attivo in x∗. Se x∗ attiva n vincoli, allora x∗ soddisfa un certo sistema di n equazioni lineari in n incognite. Tale sistema ha un’unica soluzione se e solo se le n equazioni sono linearmente indipendenti. Il seguente teorema dà un preciso significato a questa affermazione. Teorema 2.6.2 Sia x∗ ∈ Rn e sia I = {i | a′i x∗ = bi } l’insieme degli indici dei vincoli che sono attivi in x∗. Allora, le seguenti affermazioni sono equivalenti fra loro: n vettori nell’insieme {ai | i ∈ I} sono linearmente indipendenti; {ai | i ∈ I} è una base di Rn , cioè ogni elemento di Rn può essere espresso come combinazione lineare dei vettori ai , i ∈ I; il sistema di equazioni a′i x = bi , i ∈ I, ha un’unica soluzione. Ora abbiamo tutti gli strumenti per definire un vertice di un poliedro come soluzione ammissibile che attiva n vincoli linearmente indipendenti: Definizione 2.6.9 Sia P un poliedro definito da vincoli di uguagliaglianza e/o disuguaglianza come in (P) e sia x∗ ∈ Rn. Il vettore x∗ è una soluzione di base se – tutti i vincoli di uguaglianza di (P) sono attivi in x∗ ; – x∗ attiva n vincoli linearmente indipendenti. Se x∗ è una soluzione di base che soddisfa tutti i vincoli, allora x∗ è detta soluzione di base ammissibile. Un esempio di soluzioni di base e soluzioni di base ammissibili è illustrato nelle Figure 2.7 e 2.8. 36 CAPITOLO 2. PROGRAMMAZIONE LINEARE x1 A x2 P C E D B x3 Figura 2.7: Sia P = {(x1 , x2 , x3 ) | x1 + x2 + x3 = 1, x1 , x2 , x3 ≥ 0} ⊂ R3. I punti A, B, C e D attivano tre vincoli, mentre E attiva solo due vincoli e cioè x1 + x2 + x3 = 1 e x2 = 0. Come già anticipato, le tre seguenti differenti definizioni sono perfetta- mente equivalenti fra loro: Teorema 2.6.3 Sia P un poliedro non vuoto e sia x∗ ∈ P. Le seguenti tre affermazioni sono equivalenti: x∗ è un vertice di P ; x∗ è un punto estremo di P ; 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 37 A E D P B C F Figura 2.8: I punti A, B, C, D, E ed F sono tutti soluzioni di base, dato che ciascuno di loro attiva due vincoli linearmente indipendenti. Tuttavia, solo i punti C, D, E ed F sono soluzioni di base ammissibili. x∗ è una soluzione di base ammissibile. Un importante risultato è sintetizzato nel seguente Corollario, in cui si sottolinea che se un poliedro P è descritto da un numero finito di dise- quazioni/equazioni lineari, allora P ammetterà un numero finito di soluzioni di base. Corollario 2.6.1 Dato un numero finito di vincoli lineari di disequazioni e/o equazioni, può esistere solo un numero finito di soluzioni di base e soluzioni di base ammissibili. Soluzioni di base adiacenti Due distinte soluzioni di base di un poliedro P ∈ Rn si dicono adiacenti se attivano gli stessi n − 1 vincoli. Ad esempio, in Figura 2.8 B ed E sono 38 CAPITOLO 2. PROGRAMMAZIONE LINEARE entrambi adiacenti a D, mentre A ed F sono adiacenti ad E. Se due soluzioni di base adiacenti sono anche ammissibili, come D e C, allora il segmento che li congiunge è detto lato del poliedro. 2.6.4 Poliedri in forma standard Nel precedente paragrafo è stata definita una soluzione di base in riferimento a poliedri generici. In questo paragrafo verrà specializzata la definizione in relazione a poliedri rappresentati in forma standard. I risultati e le definizioni di questo paragrafo sono fondamentali per la comprensione del metodo per la soluzione di problemi di PL, noto come Metodo del Simplesso. Sia P = {x ∈ Rn | Ax = b, x ≥ 0} un poliedro rappresentato in forma standard, dove A ∈ Rm×n. Abbiamo già osservato in precedenza che senza perdita di generalità è possibile assumere che m < n e che gli m vincoli siano linearmente indipendenti. Abbiamo definito una soluzione di base come un punto che rende attivi n vincoli linearmente indipendenti. Nel caso di poliedri in forma standard, oltre agli m vincoli di uguaglianza (linearmente indipendenti per ipotesi), al fine di ottenere un totale di n vincoli attivi linearmente indipendenti, devono essere individuate n − m variabili di decisione xj da porre uguali a 0, cosı̀ da rendere il corrispondente vincolo xj ≥ 0 attivo. La scelta di tali n − m variabili di decisione xj da porre uguali a 0 non è del tutto arbitraria, come mostrato dal seguente teorema. Teorema 2.6.4 Si considerino i vincoli Ax = b e x ≥ 0 e si assuma che A ∈ Rm×n sia una matrice a righe linearmente indipendenti. Un vettore x∗ ∈ Rn è soluzione di base se e solo se Ax∗ = b; è possibile individuare B(1), B(2),... , B(m) indici tali che 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 39 (i) le colonne AB(1) , AB(2) ,... , AB(m) sono linearmente indipendenti; (ii) se j 6= B(1), B(2),... , B(m), allora x∗j = 0. Si noti che le n − m variabili di decisione xj da porre uguali a 0 sono quelle della condizione (ii). Grazie alla validità del teorema appena enunciato, tutte le soluzioni di base di un poliedro descritto in forma standard possono essere ottenute ap- plicando la semplice procedura riportata di seguito. Passo 1. Scegliere m colonne di A linearmente indipendenti. Siano AB(1) , AB(2) ,... , AB(m) dette colonne. Passo 2. Porre xj = 0, per ogni j 6= B(1), B(2),... , B(m). Passo 3. Risolvere il sistema ad m equazioni Ax = b nelle m incognite xB(1) , xB(2) ,... , xB(m). Sia x̂ una soluzione di base ottenuta applicando la procedura appena descritta. Se x̂ ≥ 0 (in particolare, xB(1) , xB(2) ,... , xB(m) ≥ 0, essendo x∗j = 0, j 6= B(1), B(2),... , B(m)), allora x̂ è detta soluzione di base ammissibile. Viceversa, dal momento che ogni soluzione ammissibile di base x̂ è una soluzione di base, essa può essere ottenuta attraverso la semplice procedura descritta. Se x̂ è una soluzione di base, le variabili x̂B(1) , x̂B(2) ,... , x̂B(m) sono dette variabili di base, mentre le restanti n − m variabili di decisione xj , j 6= B(1), B(2),... , B(m) sono dette variabili non di base. Le colonne AB(1) , AB(2) ,... , AB(m) sono dette colonne di base e, dal momento che sono linearmente indipendenti, formano una base di Rm. È sempre possibile rior- dinare le colonne della matrice A, affinchè le colonne AB(1) , AB(2) ,... , AB(m) 40 CAPITOLO 2. PROGRAMMAZIONE LINEARE siano le prime m colonne, cosı̀ ottenendo una sottomatrice quadrata B ∈ Rm×m , detta matrice di base. Due matrici di base sono dette distinte se coin- volgono due insiemi di colonne linearmente indipendenti distinte. Si noti che la matrice di base B è invertibile essendo costituita da colonne linearmente indipendenti. Analogamente, possiamo definire un vettore xB di variabili di decisione di base xB(1) , xB(2) ,... , xB(m) ed un vettore xN di variabili di decisione non di base xj , j 6= B(1), B(2),... , B(m): h i B = AB(1) AB(2)... AB(m) ,   xB(1)    xB(2)  xB =  .  ..  .   xB(m) Le variabili di base xB sono determinate risolvendo il sistema di m equazioni in m incognite BxB = b, la cui unica soluzione è data da xB = B −1 b. Esempio 2.6.1 Sia P il poliedro in forma standard descritto dai seguenti vincoli di uguaglianza lineari: x1 + x2 + 2x3 + x4 =8 x2 + 6x3 + x5 = 12 x1 + x6 =4 x2 + x7 = 6 Dunque, la matrice A ed il vettore b sono i seguenti:   1 1 2 1 0 0 0    0 1 6 0 1 0 0  A= ,    1 0 0 0 0 1 0    0 1 0 0 0 0 1 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 41   8    12  b= .    4    6 Scegliamo le colonne A4 , A5 , A6 ed A7 come colonne di base. Si noti che esse sono sicuramente linearmente indipendenti, in quanto B = [A4 A5 A6 A7 ] è la matrice identità. Con tale scelta di matrice di base si ottiene la soluzione di base xB = [x4 x5 x6 x7 ] = [8 12 4 6] ed xN = [x1 x2 x3 ] = [0 0 0]. Dal momento che tale soluzione è non negativa, essa è una soluzione di base ammissibile. Un’altra possibile base è ottenibile scegliendo come colonne di base le colonne A3 , A5 , A6 ed A7 , anch’esse linearmente indipendenti. La soluzione di base corrispondente è xB = [x3 x5 x6 x7 ] = [4 − 12 4 6] ed xN = [x1 x2 x4 ] = [0 0 0]. In tal caso la soluzione di base ottenuta non è ammis- sibile, perchè x5 = −12 < 0. Corrispondenza fra basi e soluzioni di base Due soluzioni di base differenti devono necessariamente essere state generate da due basi differenti, ma non vale il viceversa. Ossia, due basi distinte possono generare la stessa soluzione di base. Ad esempio, si consideri il caso limite in cui b = 0. In questo caso, ogni base genera una soluzione di base nulla. Questo fenomeno ha importanti conseguenze algoritmiche ed è strettamente legato alla proprietà degenere di una soluzione di base, argomento di uno dei prossimi paragrafi. 42 CAPITOLO 2. PROGRAMMAZIONE LINEARE Soluzioni di base adiacenti e soluzioni adiacenti Abbiamo già detto che due distinte soluzioni di base sono adiacenti se atti- vano lo stesso insieme di n − 1 vincoli linearmente indipendenti. In caso di problemi in forma standard, si dice anche che due basi dis- tinte si dicono adiacenti se differiscono in una sola colonna di base. Non è complicato verificare che soluzioni di base adiacenti possono sempre essere generate da basi adiacenti. Viceversa, se due basi adiacenti generano due distinte soluzioni di base, allora tali due soluzioni sono adiacenti. Esempio 2.6.2 Nell’Esempio 2.6.1 le basi BI = [A4 A5 A6 A7 ] e BII = [A3 A5 A6 A7 ] sono adiacenti perchè differiscono per una sola colonna di base. Le soluzioni corrispondenti xI = [0 0 0 8 12 4 6] ed xII = [0 0 4 0 − 12 4 6] sono anch’esse adiacenti. Infatti, in questo caso n = 7 ed entrambe le soluzioni attivano gli stessi 6 vincoli: i 4 vincoli di uguaglianza, x1 ≥ 0 e x2 ≥ 0. 2.6.5 Soluzioni di base degeneri Abbiamo definito come soluzione di base un vettore che attiva n vincoli linearmente indipendenti. Cosa accade se più di n vincoli linearmente in- dipendenti sono attivati da uno stesso vettore x∗ ? In tal caso, si dice che x∗ è una soluzione degenere, in quanto attiva un numero di vincoli linearmente indipendenti superiore al minimo richiesto. Definizione 2.6.10 Una soluzione di base x∗ ∈ Rn è detta degenere se attiva più di n vincoli. In R2 l’intersezione di 3 o più rette dà luogo ad una soluzione di base de- genere; in R3 una soluzione degenere è in corrispondenza dell’intersezione di 4 o più piani. Esempi di soluzioni di base degeneri sono illustrati in Figura 2.9. 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 43 A 11 00 D 00 11 1 0 11 00 00 11 11 00 C P 11 00 00 11 11 00 B 00 11 1E 0 Figura 2.9: I punti A e C sono soluzioni di base ammissibili degeneri. I punti B ed E sono soluzioni di base ammissibili non degeneri. Il punto D è una soluzione di base non ammissibile degenere. Esempio 2.6.3 Sia P il poliedro descritto dai seguenti vincoli lineari: x1 + x2 + 2x3 ≤ 8 x2 + 6x3 ≤ 12 x1 + ≤4 x2 + ≤6 x ≥ 0. Il vettore xI = (x1 x2 x3 ) = (2 6 0) è una soluzione ammissibile di base non degenere, perchè attiva esattamente 3 vincoli linearmente indipendenti: x1 + x2 + 2x3 ≤ 8, x2 ≤ 6 e x3 ≥ 0. Il vettore xII = (x1 x2 x3 ) = (4 0 2) è una soluzione ammissibile di base degenere, perchè attiva 4 vincoli, 3 dei quali linearmente indipendenti: x1 + x2 + 2x3 ≤ 8, x2 + 6x3 ≤ 12, x1 ≤ 4 e x2 ≥ 0. 44 CAPITOLO 2. PROGRAMMAZIONE LINEARE Soluzioni di base degeneri per poliedri in forma standard Qualunque soluzione di base per poliedri in forma standard deve necessaria- mente attivare tutti gli m vincoli di uguaglianza. Dunque, l’unico modo per attivare più di n vincoli è che più di n − m variabili di decisione valgano 0. Definizione 2.6.11 Sia P = {x ∈ Rn | Ax = b, x ≥ 0} un poliedro de- scritto in forma standard e sia x∗ una soluzione di base. Sia m il numero di righe di A, allora x∗ è detta soluzione di base degenere se più di n − m componenti di x∗ sono nulle. Esempio 2.6.4 Consideriamo ancora una volta l’Esempio 2.6.3. Intro- ducendo nella descrizione del poliedro P le variabili di slack x4 , x5 ,... , x7 , è possibile trasformare la sua descrizione nella seguente forma standard: P = {x = (x1 x2... x7 ) | Ax = b, x ≥ 0}, dove   1 1 2 1 0 0 0    0 1 6 0 1 0 0  A= ,    1 0 0 0 0 1 0    0 1 0 0 0 0 1   8    12  b= .    4    6 Consideriamo la matrice di base costituita dalle colonne linearmente in- dipendenti A1 , A2 , A3 ed A7 , cioè B = [A1 A2 A3 A7 ]. Sappiamo che per calcolare la corrispondente soluzione di base dobbiamo innanzitutto porre a 0 le variabile non di base e poi risolvere il sistema di equazioni 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 45 Bx = b. Nel caso in esame, poniamo xN = (x4 x5 x6 ) = (0 0 0), men- tre xB = (x1 x2 x3 x7 ) = B −1 b = (4 0 2 6). Tale soluzione è una soluzione ammissibile di base degenere, poichè ha 4 componenti nulle lad- dove n − m = 7 − 4 = 3. Dunque, mentre inizialmente abbiamo posto a 0 le tre componenti di xN , la soluzione xB al sistema Bx = b ha un’ulteriore componente nulla o, in altre parole, essa attiva l’ulteriore vincolo x2 ≥ 0. Si noti, inoltre, che alla base B1 = [A1 A3 A4 A7 ] 6= B corrisponde la stessa soluzione di base ammissibile degenere xB1 = xB = (x1 x2 x3 x7 ) = (4 0 2 6) e xN1 = xN = (x4 x5 x6 ) = (0 0 0). 2.6.6 Esistenza di punti estremi In questo paragrafo verranno enunciate le condizioni necessarie e sufficienti affinchè un poliedro abbia almeno un punto estremo. È chiaro che non tutti i poliedri hanno sempre almeno un punto estremo. Un semispazio in Rn , n > 1, ad esempio, pur essendo un poliedro non ha punti estremi. L’esistenza di almeno un punto estremo per un poliedro P dipende dalla presenza o meno in P di una retta. Definizione 2.6.12 Un poliedro P ⊂ Rn contiene una retta se esiste un vettore x ∈ P ed un vettore non nullo d ∈ Rn tale che x + λd ∈ P, ∀ λ scalare. Un importante risultato è espresso nel seguente teorema, di cui tralasciamo la dimostrazione. Teorema 2.6.5 Sia P = {x ∈ Rn | a′i x ≥ bi , i = 1, 2,... , m} un poliedro non vuoto. Le seguenti affermazioni sono equivalenti fra loro: (a) P ha almeno un punto estremo. 46 CAPITOLO 2. PROGRAMMAZIONE LINEARE (b) P non contiene una retta. (c) Oltre ad a1 , a2 ,... , am , esistono altri n − m vettori tutti linearmente indipendenti fra loro. A B P Q D C Figura 2.10: Il poliedro P contiene una retta ed infatti non ha punti estremi; il poliedro Q non contiene una retta ed infatti ha 4 punti estremi: A, B, C e D. Esempi di poliedri con o senza linee sono illustrati in Figura 2.10. Si noti che un poliedro limitato non contiene una retta e cosı̀ anche il quadrante positivo {x | x ≥ 0}. Dal momento che un poliedro descritto in forma standard è contenuto nel quadrante positivo, ne consegue che neanch’esso contiene una retta. Infatti, è valido il seguente corollario. Corollario 2.6.2 Ogni poliedro limitato non vuoto ed ogni poliedro non vuoto descritto in forma standard ha almeno un punto estremo e, dunque, almeno una soluzione di base ammissibile. 2.6. GEOMETRIA DELLA PROGRAMMAZIONE LINEARE 47 2.6.7 Ottimalità di punti estremi In questo paragrafo verrano formalizzate le motivazioni per cui, come già accennato in precedenza, dato un poliedro P che abbia almeno un punto estremo e che sia la regione ammissibile di un problema di PL che ammette soluzione ottima, sia sempre possibile individuare in un vertice (o, equiva- lentemente, in un punto estremo o soluzione ammissibile di base) di P una soluzione ottima al problema stesso. Sono validi i seguenti risultati, di cui si trascura la verifica. Teorema 2.6.6 Si consideri il problema di PL consistente nel minimizzare c′ x su un poliedro P che abbia almeno un punto estremo e si supponga che il problema ammetta almeno una soluzione ottima. Allora, esiste una soluzione ottima al problema che è punto estremo di P. Il risultato precedente si applica sia a poliedri in forma standard che a poliedri limitati, dato che essi non contengono una retta. Il prossimo risultato esprime un concetto più forte di quello espresso nel Teorema 2.6.6. Teorema 2.6.7 Si consideri il problema di PL consistente nel minimizzare c′ x su un poliedro P che abbia almeno un punto estremo. Allora, o il valore della soluzione ottima è −∞ oppure esiste un punto estremo di P che è soluzione ottima finita del problema. Nel caso di problemi di PL generici, il Teorema 2.6.7 non si applica diret- tamente se la regione ammissibile non ha punti estremi. Tuttavia, sappiamo che un qualunque problema di PL può essere trasformato in un problema di PL equivalente formulato in forma standard, cui il Teorema 2.6.7 invece si applica. Vale, infatti, il seguente corollario. Corollario 2.6.3 Si consideri il problema di PL consistente nel minimiz- zare c′ x su un poliedro P non vuoto. Allora, o il valore della soluzione ottima 48 CAPITOLO 2. PROGRAMMAZIONE LINEARE è −∞ oppure esiste una soluzione ottima finita al problema. 2.7 Il Metodo del Simplesso Nel corso di questo paragrafo supporremo di dover risolvere il seguente gener- ico problema di PL formulato in forma standard: (Pr) min c′ x s.a Ax = b x ≥ 0, dove A ∈ Rm×n ha rango massimo m. Con Ai indicheremo l’i.ma colonna di A, mentre con a′i ne indicheremo l’i.ma riga. Suppurremo, inoltre, che P sia la regione ammissibile corrispondente al problema. Da quanto detto nei precedenti paragrafi è emerso che se un problema di PL formulato in forma standard ammette una soluzione ottima finita, allora esiste una soluzione ammissibile di base ottima. Il metodo del simplesso si basa su tale considerazione e cerca una soluzione ottima al problema muovendosi da una soluzione ammissibile di base ad una adiacente sempre nella direzione lungo la quale si verifica un decremento del valore corrente della funzione obiettivo. Nel momento in cui viene raggiunta una soluzione ammissibile di base a partire dalla quale non è possibile intraprendere più alcuna direzione migliorativa del valore corrente della funzione obiettivo, la soluzione ammissibile di base corrente è ottima e l’algoritmo termina. Obiettivo di questo paragrafo è analizzare il metodo del simplesso e la sua complessità computazionale, nonchè discutere di una sua particolare imple- mentazione, nota come simplesso revisionato. Verranno anche sottolineate alcune difficoltà in cui può incorrere tale metodo in presenza di soluzioni degeneri. 2.7. IL METODO DEL SIMPLESSO 49 2.7.1 Condizioni di ottimalità Per risolvere un generico problema di ottimizzazione, specialmente se il prob- lema da risolvere è NP-hard, molti algoritmi partono da una soluzione am- missibile x ed esplorano soluzioni ”vicine” ad x (nel nostro caso, adiacenti) conservando in memoria la soluzione migliore trovata durante l’esplorazione. Tali algoritmi sono noti in letteratura come algoritmi di ricerca locale e pro- ducono in output una soluzione ottima localmente alla soluzione ammissibile iniziale x. Sfortunatamente, in generale una soluzione ottima localmente non è necessariamente ottima globalmente. Il metodo del simplesso, passando da una soluzione ammissibile di base ad una soluzione ammissibile di base adiacente e terminando quando non esiste una soluzione ammissibile di base migliore, può essere interpretato come algoritmo di ricerca locale. Fortu- natamente, però, nel caso di problemi di PL, dal momento che si tratta di ottimizzare una funzione obiettivo convessa su una regione ammissibile convessa, si è certi che l’ottimo locale restituito in output dal metodo del sim- plesso è ottimo anche globalmente (vedi Appendice A, pag. 263). Ma come è possibile individuare una direzione lungo la quale si verifica un decremento del valore corrente della funzione obiettivo a partire dalla soluzione ammissi- bile di base corrente? In altri termini, data la soluzione ammissibile di base corrente x ∈ P a partire dalla quale vogliamo muoverci lungo la direzione di un certo vettore d ∈ Rn , come va scelto detto vettore d? La risposta a questa domanda è contenuta in quanto segue. Innanzitutto, dobbiamo limitare la scelta di d a quei vettori che non ci conducano fuori dalla regione ammissibile P. Tale osservazione porta immediatamente alla seguente definizione di direzione ammissibile. Definizione 2.7.1 Sia x ∈ P ⊂ Rn. Un vettore d ∈ Rn è detto direzione ammissibile a partire da x se esiste uno scalare θ > 0 tale che x + θd ∈ P. Sia x una soluzione ammissibile di base per il problema formulato in 50 CAPITOLO 2. PROGRAMMAZIONE LINEARE forma standard (Pr). In particolare, siano B(1), B(2),... , B(m) gli indici delle variabili di base e sia B = [AB(1) AB(2)... AB(m) ] la corrispondente matrice di base. Sappiamo che xB = (xB(1) xB(2)... xB(m) ) = B −1 b, mentre tutte le variabili non di base sono nulle, cioè xN = 0. Consideriamo, ora, la possibilità di muoverci dalla soluzione x e di ottenere la soluzione x + θd. Ciò può essere realizzato selezionando una variabile non di base xj , j 6= B(1), B(2),... , B(m) inizialmente a livello 0 ed incrementando il suo valore di una quantità positiva θ, mantenendo nulle le restanti n − m − 1 variabili non di base. Algebricamente ciò equivale a porre dj = 1 e di = 0 per ogni i 6= j, B(1), B(2),... , B(m). Al contempo, anche il vettore di base xB dovrà cambiare in xB + θdB , dove dB = (dB(1) dB(2)... dB(m) ) è il vettore le cui componenti sono le componenti di d corrispondenti alle variabili di base. Come determinare dB ? Innanzitutto, muovendoci da x a x + θd noi vogliamo comunque ri- manere all’interno della regione ammissibile P , cioè vogliamo preservare l’ammissibilità della nuova soluzione x + θd. Formalmente, ciò equivale a richiedere che A(x + θd) = b. (2.1) Intanto, Ax = b, dato che x è ammissibile, per cui la 2.1 è equivalente a richiedere che θ>0 Aθd = 0 =⇒ Ad = 0. (2.2) Dunque, m X X 0 = Ad = AB(i) dB(i) + Al dl. (2.3) i=1 l6=B(1),...,B(m) Ricordando che dj = 1 e di = 0 per ogni i 6= j, B(1), B(2),... , B(m), la 2.3 diventa m X 0 = Ad = AB(i) dB(i) + Aj = BdB + Aj. (2.4) i=1 2.7. IL METODO DEL SIMPLESSO 51 Dal momento che la matrice B è invertibile, è possibile concludere che dB = −B −1 Aj. (2.5) Il vettore d appena costruito è noto come j.ma direzione di base. Esso garantisce il rispetto dei vincoli di uguaglianza che descrivono la regione am- missibile P , ma cosa possiamo dire del rispetto dei vincoli di non negatività delle variabili di decisione x + θd ≥ 0? Con l’introduzione di d sicuramente il valore della variabile non di base xj è passato da 0 a θ > 0, mentre il valore delle restanti n−m−1 variabili non di base è rimasto nullo. Dunque, nel rispondere alla domanda precedente, dobbiamo preoccuparci solo del nuovo valore delle variabili di base e cioè di xB + θdB e distinguiamo due casi: (a) x è una soluzione ammissibile di base non degenere. Ciò implica che xB > 0, per cui vale che xB + θdB ≥ 0. Dunque, in tal caso, per θ sufficientemente piccolo, la non negatività delle variabili di base è preservata e d è una direzione ammissibile. (b) x è una soluzione ammissibile di base degenere. In questo caso, non sempre d è una direzione ammissibile. Infatti, può accadere che una variabile di base xB(i) sia nulla, mentre la corrispondente componente dB(i) di dB = −B −1 Aj sia negativa. In tale ipotesi, se seguissimo la direzione d abbandoneremmo la regione ammissibile P producendo una soluzione non ammissibile. Supponiamo di aver individuato una direzione ammissibile d e di essere pronti a spostarci da x al punto x + θd. È chiaro che effettueremo effet- tivamente lo spostamento solo qualora esso fosse conveniente in termini di decremento del valore della funzione obiettivo, che ora sarà c′ (x + θd) = c′ x + θc′ d. 52 CAPITOLO 2. PROGRAMMAZIONE LINEARE Valutiamo, dunque, c′ d. Ricordando che per ipotesi dj = 1 e di = 0 per ogni i 6= j, B(1), B(2),... , B(m), si ha che (2.5) c′ d = c′B dB + cj = cj − c′B B −1 Aj. (2.6) Proporzionata alla quantità cj − c′B B −1 Aj è, dunque, la variazione che il valore della funzione obiettivo subisce nel momento in cui passiamo da x ad x + θd e vorremmo chiaramente che tale quantità fosse strettamente negativa. Intanto, essa è cosı̀ importante da meritare la seguente definizione: Definizione 2.7.2 Sia x una soluzione di base, B la matrice di base ad essa corrispondente e sia cB il vettore dei costi associati alle variabili di base. Per ogni j, si definisce costo ridotto c̄j della variabile xj la seguente quantità: c̄j = cj − c′B B −1 Aj. Esempio 2.7.1 Si consideri il seguente problema di PL formulato in forma standard: min c1 x1 + c2 x2 + c3 x3 + c4 x4 s.a x1 + x2 + x3 + x4 =2 2x1 + 3x3 + 4x4 =2 x ≥ 0. Le prime due colonne della matrice A, A1 = [1 2] e A2 = [1 0], sono lin- earmente indipendenti, per cui possiamo scegliere x1 ed x2 come variabili di base. La matrice di base corrispondente è " # 1 1 B=. 2 0 Annulliamo le variabili non di base, x3 = x4 = 0 e risolviamo xB = B −1 b per conoscere il valore delle due incognite x1 ed x2 , ottenendo x1 = x2 = 1. 2.7. IL METODO DEL SIMPLESSO 53 Dunque, x = (x1 x2 x3 x4 ) = (1 1 0 0) è una soluzione ammissibile di base non degenere. Una direzione di base ammissibile d potrebbe essere trovata ponendo d3 = 1 e d4 = 0, mentre dB = (d1 d2 ) è individuato applicando la 2.5 come segue " #" # " # −1 0 1/2 1 −3/2 dB = (d1 d2 ) = −B A3 = − =. 1 −1/2 3 1/2 Dunque, il costo per muoversi lungo la direzione di base d è pari a c′ d = −3c1 /2 + c2 /2 + c3 = c̄3. Ricordando la Definizione 2.7.2 di costo ridotto, calcoliamo il costo ridotto delle variabili di base. Si noti innanzitutto che B = [AB(1) AB(2)... AB(m) ], per cui B −1 [AB(1) AB(2)... AB(m) ] = I, dove I è la matrice identità m × m. In particolare, B −1 AB(i) è la i.ma colonna della matrice identità ed è uguale ad ei (il vettore unità che ha per componenti tutti zeri fatta eccezione della i.ma componente). Dunque, per ogni variabile di base xB(i) , i = 1, 2,... , m si ha che c̄B(i) = cB(i) − c′B B −1 AB(i) = cB(i) − c′B ei = cB(i) − cB(i) = 0, cioè, il costo ridotto di ogni variabile di base è nullo. Il prossimo teorema esprime le condizioni per cui una soluzione ammissi- bile di base è ottima. Data l’interpretazione dei costi ridotti come variazione del valore della funzione obiettivo, la validità di quanto tale teorema afferma è alquanto intuitiva. Teorema 2.7.1 Sia x una soluzione ammissibile di base, B la matrice di base ad essa associata e sia c̄ il corrispondente vettore dei costi ridotti. (a) Se c̄ ≥ 0, allora x è ottima. (b) Se x è ottima e non degenere, allora c̄ ≥ 0. 54 CAPITOLO 2. PROGRAMMAZIONE LINEARE Grazie al Teorema 2.7.1, per essere sicuri che la corrente soluzione am- missibile di base non degenere sia ottima, è sufficiente controllare che tutti i costi ridotti delle variabili correntemente non in base siano non negativi. Tale controllo equivale ad esaminare tutte le n − m direzioni di base. Se, invece, la corrente soluzione è degenere, non è purtroppo disponibile un test altrettanto semplice. Fortunatamente, come vedremo di qui a poco, il metodo del simplesso consente di ovviare a tali difficoltà in maniera effi- ciente. 2.7.2 Il Metodo del Simplesso In quanto segue supporremo di trattare soluzioni ammissibili di base non degeneri. Supponiamo, inoltre, di disporre di una soluzione ammissibile di base x e dei costi ridotti c̄j associati alle variabili non di base. Se questi ul- timi sono non negativi, il Teorema 2.7.1 ci garantisce che abbiamo raggiunto la soluzione ottima cercata e l’algoritmo del simplesso termina. Altrimenti, se esiste un costo ridotto c̄j di una variabile non di base negativo, allora la j.ma direzione di base d (dj = 1, di = 0 per ogni i 6= j, B(1),... , B(m) e dB = −B −1 Aj ) è una direzione di base ammissibile che porta ad un decre- mento del valore della funzione obiettivo. Muovendosi lungo la direzione di d, il valore della variabile non di base xj passa da 0 ad un valore positivo θ, mentre il valore delle altre variabili non di base rimane nullo. Si fa rifer- imento a tale cambiamento dicendo che la variabile xj (o la colonna Aj ) entra in base. Muoversi lungo la direzione di d vuol dire muoversi toccando punti del tipo x + θd, θ > 0, ottendendo decrementi del valore della funzione obiettivo. È banale osservare che vorremmo raggiungere il punto cui cor- risponde il massimo di tali decrementi, sempre però rimandendo all’interno della regione ammissibile P , e cioè il punto x + θ ∗ d, dove θ ∗ = max{θ > 0 | x + θd ∈ P }. 2.7. IL METODO DEL SIMPLESSO 55 La risultante variazione del valore della funzione obiettivo sarà pari a θ ∗ c′ d = θ ∗ c̄j. Ma quanto vale θ ∗ ? Osserviamo che Ad = 0 =⇒ A(x + θd) = Ax = b ∀ θ, per cui i vincoli di uguaglianza che descrivono P non possono essere mai violati. Cosi’, x + θd può essere non ammissibile solo se una delle sue com- ponenti diventa negativa. A tal proposito distinguiamo due casi: (a) d ≥ 0. In questa caso, dato che per ogni θ > 0 il vettore x + θd ≥ 0 non può mai diventare non ammissibile, poniamo θ ∗ = ∞. (b) Esiste di < 0 per qualche i. Il vincolo xi + θdi ≥ 0 è equivalente a θ ≤ −xi /di e deve essere rispettato per ogni i tale che di < 0. Dunque, θ ∗ sarà dato proprio dal massimo valore possibile per θ nel rispetto del suddetto vincolo:   ∗ xi θ = min −. {i|di 0 per ogni i (ipotesi di soluzioni non degeneri). Supponiamo di aver calcolato θ ∗ < ∞. A questo punto, ci spostiamo da x a x̄ = x + θ ∗ d. Dal momento che xj = 0 e dj = 1, si avrà x̄j = θ ∗ > 0. Inoltre, sia l l’indice che minimizza la quantità espressa nell’Eq. 2.7, cioè xB(l) xB(i)   − = min − = θ∗, dB(l) {i=1,2,...,m|dB(i) 0} ui xB(l) 5. Sia l l’indice della variabile di base per cui θ∗ = ul. Si formi una nuova matrice di base rimpiazzando la colonna AB(l) con la colonna Aj e si calcoli la nuova soluzione ammissibile di base x̄ data da x̄l = 0, x̄j = θ∗ , x̄B(i) = xB(i) − θ∗ ui , i 6= l. Figura 2.11: Generica iterazione del metodo del simplesso. 58 CAPITOLO 2. PROGRAMMAZIONE LINEARE Il metodo del simplesso è inizializzato con una qualunque soluzione di base ammissibile, che è garantita esistere per problemi ammissibili in forma stan- dard. Il seguente teorema afferma che in caso di soluzioni non degeneri il metodo del simplesso funziona correttamente e termina dopo un numero finito di iterazioni. Teorema 2.7.3 Sia dato un problema di PL avente regione ammissibile P non vuota. Supponiamo che ogni soluzione ammissibile al problema sia non degenere, allora il metodo del simplesso termina dopo un numero finito di iterazioni. Al termine dell’esecuzione, possono verificarsi due possibilità: (a) è stata ottenuta una base ottima B ed una soluzione ottima ad essa associata; (b) è stato trovato un vettore d tale che Ad = 0, d ≥ 0 e c′ d < 0, per cui il valore ottimo della funzione obiettivo è −∞. Il Metodo del Simplesso per problemi degeneri: regole di pivoting Supponiamo di applicare il metodo del simplesso per risolvere un problema di PL che ammetta qualche soluzione ammissibile di base degenere. Allora, nel corso dell’algoritmo possono verificarsi i seguenti due casi. (a) La soluzione ammissibile di base corrente x è degenere. In questo caso, θ ∗ può risultare nullo e di fatto la nuova soluzione x̄ coinciderebbe con x stessa (due basi differenti cui corrisponde la stessa soluzione di base). (b) La soluzione ammissibile di base corrente x non è degenere. Supponi- amo di riuscire a calcolare un valore positivo per θ ∗ , ma ottenendo una nuova soluzione x̄ degenere. 2.7. IL METODO DEL SIMPLESSO 59 Dunque, ciò che può accadere è che si passi da una base ad un’altra ri- manendo fermi alla stessa soluzione di base ammissibile degenere. Se si è fortunati, si può individuare nel frattempo una direzione ammissibile di miglioramento del valore della funzione obiettivo, ma può anche accadere che l’algoritmo cicli indefinitamente. Tutto ciò può essere ovviato adot- tando delle semplici regole nello scegliere le variabili che escono dalla base e quelle che entrano in caso di ex equo, cioè nel caso in cui a più di una variabile di base corrisponda il minimo valore per θ ∗ e nel caso in cui più di una variabile non di base abbia un costo ridotto negativo. Per quanto riguarda il caso in cui più di una variabile non di base abbia un costo ridotto negativo, si può procedere adottando uno dei seguenti criteri: 1. scegliere l’indice j tale che |c̄j | sia massimo. Dal momento che il costo ridotto esprime il tasso di decremento del val- ore della funzione obiettivo, è del tutto logico pensare di scegliere come variabile entrante in base quella cui corrisponda il maggiore decre- mento. 2. scegliere l’indice j tale che θ ∗ |c̄j | sia massimo. Questa regola se adottata fa in modo che il metodo termini dopo un minor numero di iterazioni, però ad ogni iterazione richiede un mag- giore sforzo computazionale, dato che va calcolato θ ∗ per ogni c̄j < 0. 3. scegliere il più piccolo indice j tale che c̄j < 0. E’ questa la regola più semplice e computazionalmente economica, nota come regola di Bland. Per quanto riguarda il caso in cui a più di una variabile di base corrisponda il minimo valore per θ ∗ , si procede adottando la regola di Bland, cioè fra tutte le variabili di base candidate ad uscire dalla base, si sceglie quella avente indice minore. 60 CAPITOLO 2. PROGRAMMAZIONE LINEARE Riassumendo: Regola di Bland Se c̄j1 < 0, · · · , c̄jk < 0, j1 ,... , jk ∈ / {B(1),... , B(m)}, si decide di far entrare in base la variabile j = min {jh | c̄jh < 0}. xB(lh ) Se B(l1 ), · · · , B(lk ) ∈ {B(1),... , B(m)} t.c. dB(lh ) = θ ∗ , h = 1,... , k, si decide di far uscire dalla base la variabile xB(lh )   ∗ B(l) = min lh | − =θ. dB(lh ) Complessità del Metodo del Simplesso Riguardando attentamente la descrizione di una generica iterazione del metodo del simplesso riportata in Figura 2.11, ci si rende conto che il vettore B −1 Aj gioca un ruolo fondamentale, in quanto calcolato ripetutamente in passi dif- ferenti. Sarebbe consigliabile, infatti, calcolarlo una sola volta e memoriz- zarlo, in quanto, una volta che esso è disponibile, i costi ridotti, la direzione d e θ ∗ sono immediatamente calcolabili. Non è un caso, infatti, che le varie implementazioni del metodo del simplesso differescono proprio nella scelta del modo di calcolare e memorizzare B −1 Aj e, a seconda delle scelte operate, esse esibiscono complessità differenti. Prima di esaminarle, è opportuno os- servare che, data una matrice B ∈ Rm×m ed un vettore b ∈ Rm , sia il calcolo dell’inversa B −1 di B che risolvere il sistema Bx = b richiedono O(m3 ) oper- azioni aritmetiche. Il calcolo del prodotto matrice-vettore Bb richiede invece O(m2 ) operazioni aritmetiche, mentre il calcolo del prodotto interno p′ b di due vettori di dimensione m richiede O(m) operazioni aritmetiche. Fatte le suddette considerazioni, è facile calcolare la complessità computazionale 2.7. IL METODO DEL SIMPLESSO 61 di una singola iterazione del metodo del simplesso, cosı̀ come descritta in Figura 2.11. Infatti, all’inizio di ogni iterazione si hanno m indici di vari- abili correntemente in base B(1), B(2),... , B(m), si forma la base B e si calcola p′ = c′B B −1 risolvendo il sistema lineare p′ B = c′B nelle incognite p (il vettore p è chiamato vettore dei moltiplicatori del simplesso associati alla base B). Poi, per ogni variabile non di base xj deve essere calcolato il suo costo ridotto c̄j = cj − p′ Aj (a seconda della specifica regola di pivoting che si è deciso di adottare, possono essere calcolati TUTTI i costi ridotti, op- pure calcolarne uno alla volta e fermarsi non appena si è calcolato un costo ridotto negativo). Una volta trovata una variabile non di base xj che può entrare in base (cioè tale che cj < 0; se non esiste, l’algoritmo termina), risol- vendo il sistema Bu = Aj , si calcola il vettore u = B −1 Aj. A questo punto, è possibile individuare una direzione ammissibile da seguire per spostarci dalla soluzione di base corrente ottenendo un miglioramento della funzione obiettivo. Si calcola θ ∗ , si individua la variabile che deve lasciare la base e si calcolano le componenti della nuova soluzione di base. Per risolvere i sistemi p′ B = c′B e Bu = Aj occorrono O(m3 ) operazioni aritmetiche; mentre per calcolare i costi ridotti occorrono O(mn) operazioni aritmetiche, dato che per ottenerli bisogna effettuare il prodotto interno fra p ed ogni colonna non di base Aj. È chiaro, a questo punto, che la complessità computazionale di ogni singola iterazione del metodo del simplesso cosı̀ come descritta in Figura 2.11 è O(m3 + mn). 2.7.3 Il Metodo del Simplesso Revisionato Gran parte dello sforzo computazionale nell’implementazione del Metodo del Simplesso descritto in Figura 2.11 è legata alla necessità di dover risol- vere ad ogni iterazione due sistemi di equazioni lineari. Se fosse disponibile un metodo efficiente con il quale ottenere la matrice B −1 all’inizio di ogni 62 CAPITOLO 2. PROGRAMMAZIONE LINEARE iterazione, i vettori c′B B −1 e B −1 Aj sarebbero immediatamente ottenibili tramite semplice moltiplicazione vettoriale. L’implementazione alternativa descritta in questo paragrafo fornisce appunto tale metodo. Sia h i B= AB(1) AB(2)... AB(l−1) AB(l) AB(l+1)... AB(m) , la matrice di base all’inizio di un generica iterazione i e sia h i B̄ = AB(1) AB(2)... AB(l−1) Aj AB(l+1)... AB(m) , la matrice di base all’inizio dell’iterazione successiva i + 1. Per poter es- eguire tutti i passi previsti all’iterazione i + 1, dovremmo poter disporre della matrice inversa B̄ −1. Come si può facilmente osservare le matrici B e B̄ differiscono per la sola colonna l.ma (B contiene AB(l) , mentre B̄ contiene Aj corrispondente alla variabile entrante in base). Dunque, è logico pensare che anche le matrici B −1 e B̄ −1 siano simili. Infatti, come mostrato di se- guito, la matrice B̄ −1 è ottenibile da B −1 attraverso una serie di operazioni matriciali elementari applicata alle righe di B −1. Definizione 2.7.3 Data una matrice A ∈ Rm×n non necessariamente quadrata, si definisce operazione elementare di riga effettuata su A l’operazione di ag- giungere ad una riga ri , i = 1, 2,... , m una costante moltiplicata per la riga rj , j = 1, 2,... , m, con j possibilmente anche coincidente con i stesso. Ora, all’inizio della iterazione i + 1 si dispone della matrice B −1 , a par- tire dalla quale si può ottenere la matrice B̄ −1 effettuando una serie di operazioni elementari sulle righe della matrice B −1 |u. In particolare, sup-   ponendo che l sia l’indice della variabile candidata ad uscire dalla base, al- lora si deve applicare alla matrice [B −1 |u] una serie di operazioni elementari tese a trasformarne l’ultima colonna (quella contenente u) in una colonna contenente tutti 0 ed un solo 1 in corrispondenza della riga l.ma. 2.7. IL METODO DEL SIMPLESSO 63 Esempio 2.7.2 Supponiamo che     1 2 3 −4 −1     B =  −2  3 1 ;  u=  . 2  4 −3 −2 2 e supponiamo che l = 3. Una volta costruita la matrice   1 2 3 −4 [B −1 |u] =     −2 3 1 , 2  4 −3 −2 2 bisogna operare su [B −1 |u] in modo che la 4.rta colonna contenente u si trasformi nel vettore e3 = [0 0 1]. Ad esempio, si potrebbe moltiplicare la terza riga per 2 ed aggiungerla alla prima riga, per poi sottrarre la terza dalla seconda e finalmente dividere la terza per 2, cosı̀ ottenendo   9 −4 −1 0 −1   [B̄ |e3 ] =   −6 6 3 , 0  2 −3/2 −1 1 le cui prime tre colonne contengono la matrice inversa B̄ −1 desiderata. L’implementazione del Metodo del S