UNIMORE-FIM INFORMATICA
Ottimizzazione Lineare Intera
Appunti delle lezioni
Lorenzo Balugani (@EvilBalu)
Quarto semestre
INTRODUZIONE
RICERCA OPERATIVA
La Ricerca Operativa è il ramo della matematica applicata in cui problemi decisionali vengono analizzati e risolti mediante modelli matematici, e l’obiettivo è quello di fornir supporto all’operazione decisionale. La Ricerca Operativa nasce in ambito militare, per poi spostarsi in ambito logistico, economico e simili. Il processo di approccio al problema segue due processi paralleli: la modellizzazione matematica e la raccolta dati, che unite portano ad un modello mediante il quale si può ottenere una soluzione che supporti una decisione. Un ramo della Ricerca Operativa è l’ottimizzazione combinatoria, che cerca un oggetto di valore ottimo (soluzione ottima) in una collezione finita di oggetti (rappresentata da ad esempio un grafo che contiene un grande numero di oggetti, che sono teoricamente enumerabili ma praticamente impossibile a prescindere dalla potenza di calcolo disponibile, e per questo è importante ottimizzare il modello).
PROGRAMMAZIONE LINEARE – INIZIO LEZIONI DEL PROFESSOR DELL’AMICO
Per scrivere un modello matematico è importante stabilire le variabili decisionali (variabili che rappresentano le scelte), costruire le equazioni che stabiliscono i limiti del problema e l’obiettivo. Nell’esempio dei tavoli e delle sedie, ad esempio, indichiamo con x il numero di tavoli e con y il numero di sedie, e indichiamo i vincoli che sono il legno (15 unità) e il tempo (15 ore). Tavoli e seggiole gestiscono diversamente le risorse: per il legno abbiamo 3𝑥 + 2𝑦 ≤ 15, per il tempo 2𝑥 + 3𝑦 ≤ 15. La richiesta è max(80𝑥 + 70𝑦). Rappresentando su un grafico a piano cartesiano le disequazioni precedentemente indicate, ovvero andando a trovare le rette impiegando le intersezioni degli assi, capire quali sono i semipiani giusti (verificando se un punto del semipiano rispetta la disequazione). La regione in comune è quella che rispetta entrambi i requisiti (ogni punto è ammissibile dal sistema di disequazioni). Definiamo 𝑍 = 80𝑥 + 70𝑦, la funzione che vogliamo massimizzare: se proviamo con 𝑍 = 0 possiamo identificare una retta, i cui tutti punti verificano lo 0 della funzione obiettivo. Provando altri valori, possiamo raggiungere l’obiettivo: tracciamo quindi linee parallele (linee di iso-profitto) e la soluzione ottimale è quella fornita dalla linea più alta che ha almeno un punto nella regione accettabile. La funzione obiettivo generale è scritta come 𝑧 = 𝑓(𝑥1, … , 𝑥𝑛).
Definizione: Gradiente
Data una funzione f si definisce gradiente il ∇𝑓 = 𝑑𝑓
𝑑𝑥1𝑒1+ ⋯ + 𝑑𝑓
𝑑𝑥𝑛𝑒𝑛 dove gli 𝑒𝑖 sono i versori del piano coordinato (vettori di valore unitario orientati come il piano). 𝑑𝑓
𝑑𝑥1 sono le varie derivate parziali. In parole comprensibili, avendo 𝑥𝑛 variabili il suo gradiente sarà un vettore (𝑥1′, … , 𝑥𝑛′) dove, dal momento che sono variabili di primo grado, avremo i loro coefficienti (nell’esempio precedente, ∇𝑓(80,70)). Il Gradiente calcolato in un punto indica la direzione di massima crescita della funzione in quel punto (il gradiente è perpendicolare a tutte le righe di isoprofitto).
I problemi di programmazione lineare vengono espressi in forma standard, dove i vincoli sono solo equazioni e le variabili sono solo positive. Per fare ciò, tornando al problema del falegname, introduciamo le variabili slack s1 e s2 e poniamo tutto = a 15, ottenendo quindi 3𝑥 + 2𝑦 + 𝑠1 = 15 e 2𝑥 + 3𝑦 + 𝑠2 = 15. Quando si rileva un consumo minore di 15, allora le variabili slack fanno da riempitivo, e non alterano la soluzione ottima in quanto non sono nella
funzione obiettivo. Tutto questo può essere visto come un sistema, che se risolto con gauss-jordan ci porta a trovare i valori delle variabili slack (in rosso sono indicati i pivot).
METODO DEL TABLEU (GAUSS-JORDAN SPIEGATO CAOTICAMENTE)
Siccome il problema è in forma standard, abbiamo già variabili non negative. Il problema viene messo all’interno di una tabella, che nella prima ha i coefficienti della funzione obiettivo (una variabile per colonna, incluse anche le slack), e nelle righe inferiori mettiamo i vincoli. Nella colonna più a destra ci sono i valori della funzione obiettivo/vincolo. Per leggere la prima soluzione data (dove abbiamo messo x e y a 0, ottenendo s1=s2=15), basta ignorare le colonne delle variabili non-slack. Così abbiamo tolto dalla soluzione sia x che y. Facciamo rientrare x, quindi devo andare a scegliere
x y s1 s2 80 70 0 0 3 2 1 0
2 3 0 1
x y s1 s2
0 0 -20 -10
1 0 3/5 -2/5
0 1 -2/5 3/5
quale variabile esce (facciamo uscire s1), ed è importante che quando x entra nella soluzione x abbia coefficiente 1 in un’equazione e nelle altre abbia 0. In altre parole, con le operazioni di Gauss Jordan andiamo a mettere i pivot come dovrebbero, e ci ritroviamo nella situazione indicata nella foto.
In certe situazioni, una variabile può far crescere infinitamente il valore della funzione obiettivo (quando tutti i coefficienti dei vincoli di una variabile slack sono negativi e questa ha coeff positivo nella funzione da ottimizzare (se si cerca un massimo, altrimenti deve essere negativo))e questo si verifica quando l’area su cui ragioniamo non è chiusa.
PROBLEMI CLASSICI
• Problema di trasporto. Vengono date n sorgenti di massima capacità 𝑎𝑖, 𝑖 = 1 … 𝑛, m destinazioni di richiesta 𝑏𝑗, 𝑗 = 1 … 𝑚 e i costi di trasporto da i a j sono indicati con 𝑐𝑖𝑗. La richiesta è trovare i trasporti in grado di soddisfare le richieste, senza superare le capacità massime e minimizzando il costo. Si può fare, dal punto di vista grafico, un grafo che a sinistra ha le sorgenti e a destra le destinazioni, e queste sono collegate da archi (su cui è indicato il costo). Le variabili 𝑥𝑖𝑗 rappresentano la quantità trasportata da i a j, e il modello
matematico può esser visto come min ∑𝑛𝑖=1∑𝑛𝑗=1𝑐𝑖𝑗𝑥𝑖𝑗, con i vincoli che sono il rispettare la capacità massima del nodo i, non sovrasaturare il nodo j (non dare più di quanto richiesto) (le variabili devono essere non negative e intere).
Questo problema è di assegnamento lineare. Data una matrice n*n 𝐶 = [𝑐𝑖𝑗] che definisce i costi del nostro problema, assegno una riga ad una colonna minimizzando il costo degli elementi e facendo in modo che ogni riga sia assegnata ad una colonna e viceversa e gli assegnamenti devono avere il costo minimo. Le variabili 𝑥𝑖𝑗 sono quindi 𝑥𝑖𝑗= {1 𝑠𝑒 𝑙𝑎 𝑟𝑖𝑔𝑎 𝑖 è 𝑎𝑠𝑠𝑜𝑐𝑖𝑎𝑡𝑎 𝑎𝑙𝑙𝑎 𝑐𝑜𝑙𝑜𝑛𝑛𝑎 𝑗
0 𝑑𝑖𝑣𝑒𝑟𝑠𝑎𝑚𝑒𝑛𝑡𝑒 , min ∑𝑛𝑖=1∑𝑛𝑗=1𝑐𝑖𝑗𝑥𝑖𝑗, ∑𝑛𝑖=1𝑥𝑖𝑗= 1 𝑗 = 1 … 𝑛, ∑𝑛𝑗=1𝑥𝑖𝑗 𝑖 = 1 … 𝑛, 𝑥𝑖𝑗∈ {0,1} 𝑖, 𝑗 = 1 … 𝑛.
• Knapsack. Vengono dati n oggetti, e ogni oggetto j ha un profitto (𝑝𝑗) e un peso (𝑤𝑗), e lo zainetto ha capacità massima c. Il problema è trovare l’insieme di oggetti che può esser messo nello zaino massimizzando il profitto. Ad ogni oggetto è associata la variabile di scelta 𝑥𝑗= {1 𝑠𝑒 𝑗 è 𝑠𝑐𝑒𝑙𝑡𝑜
0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 e il modello matematico risulta essere max ∑𝑛𝑗=1𝑝𝑗𝑥𝑗 con il vincolo ∑𝑛𝑗=1𝑤𝑗𝑥𝑗≤ 𝑐.
• Bin packing. Vengono dati n oggetti, ogni oggetto j ha una dimensione (𝑤𝑗), e infinite ceste di capacità c. La richiesta è far stare tutti gli n oggetti nel minor numero di ceste. Le variabili sono 𝑥𝑖𝑗=
{1 𝑠𝑒 𝑙′𝑜𝑔𝑔𝑒𝑡𝑡𝑜𝑗 è 𝑛𝑒𝑙 𝑐𝑒𝑠𝑡𝑜 𝑖
0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 e 𝑧𝑖= {1 𝑠𝑒 𝑖𝑙 𝑐𝑒𝑠𝑡𝑜 𝑖 è 𝑢𝑠𝑎𝑡𝑜
0 𝑑𝑖𝑣𝑒𝑟𝑠𝑎𝑚𝑒𝑛𝑡𝑒 . Costruendo il modello senza la seconda variabile, si ha ∑𝑛𝑗=1𝑤𝑗𝑥𝑖𝑗≤ 𝑐 (questo vincolo vale per ciascuno degli n contenitori). Se prendo tutti i contenitori da 1 a n ∑𝑛𝑖=1𝑥𝑖𝑗= 1, il che vuol dire che un dato elemento deve esserci solo in un contenitore.
Per scrivere la funzione di ottimizzazione abbiamo bisogno quindi di 𝑧𝑖 (definita come sopra), e le x e le z sono legate dalla vincolo 𝑥𝑖𝑗≤ 𝑧𝑖 o, scritto meglio, ∑𝑛𝑗=1𝑥𝑖𝑗≤ 𝑛𝑧𝑗. Versione alternativa del vincolo è ∑𝑛𝑗=1𝑤𝑗𝑥𝑖𝑗≤ 𝑐𝑧𝑖.
• Facility location. Sono date N zone potenziali, I zone dei clienti. Ogni sito j di N ha una capacità 𝑢𝑗 e un costo di attivazione 𝑐𝑗, ogni cliente ha una richiesta 𝑏𝑖 e il servire un cliente i da una località j ha un costo ℎ𝑖𝑗. Ogni cliente deve essere servito da una singola fabbrica. Il problema è soddisfare tutti i clienti minimizzando i costi.
Prendiamo le variabili 𝑥𝑗= {1 𝑠𝑒 𝑢𝑛𝑎 𝑓𝑎𝑏𝑏𝑟𝑖𝑐𝑎 è 𝑛𝑒𝑙 𝑠𝑖𝑡𝑜 𝑗
0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 , 𝑦𝑗𝑖 = {1 𝑠𝑒 𝑖𝑙 𝑐𝑙𝑖𝑒𝑛𝑡𝑒 𝑖 è 𝑠𝑒𝑟𝑣𝑖𝑡𝑜 𝑑𝑎𝑙 𝑠𝑖𝑡𝑜 𝑗
0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 . La
funzione obiettivo è min(∑𝑗∈𝑁𝑐𝑗𝑥𝑗+ ∑𝑖∈𝐼∑𝑗∈𝑁ℎ𝑖𝑗𝑦𝑖𝑗), che ha come vincoli ∑𝑗∈𝑁𝑦𝑖𝑗= 1 𝑖 ∈ 𝐼, ∑𝑖∈𝐼𝑏𝑖𝑦𝑖𝑗≤ 𝑢𝑗𝑥𝑗 𝑗 ∈ 𝑁, 𝑥𝑗∈ {0,1}𝑗 ∈ 𝑁, 𝑦𝑖𝑗∈ {0,1}𝑖 ∈ 𝐼, 𝑗 ∈ 𝑁.
• Fixed charge. Sono dati n prodotti, il cui costo iniziale per il j-esimo prodotto è 𝑘𝑗. Ogni prodotto di tipo j costa 𝑐𝑗 e comporta un guadagno 𝑔𝑗 per ogni unità del prodotto venduta. La quantità di risorse di tipo i è
indicata con 𝑏𝑖, e 𝑎𝑖𝑗 è l’uso di una risorsa i per unità di prodotto j. La richiesta è trovare la produzione ottimale. Utilizziamo la variabile 𝑥𝑗 per indicare il numero di prodotti di tipo j. La funzione obiettivo relativamente a j è max 𝑓(𝑥𝑗) = { 0 𝑠𝑒 𝑥𝑗= 0
𝑔𝑗𝑥𝑗− 𝑘𝑗− 𝑐𝑗𝑥𝑗 𝑠𝑒 𝑥𝑗> 0 dove 𝑔𝑗𝑥𝑗 sono i guadagni, a cui vengono sottratti i costi (la funzione è discontinua, quindi non lineare). Ad ogni prodotto j associo una variabile booleana 𝑦𝑗= { 1 𝑠𝑒 𝑥𝑗> 0
0 𝑎𝑙𝑡𝑟𝑖𝑚𝑒𝑛𝑡𝑖 e possiamo andare a definire la funzione obiettivo come max ∑𝑛𝑗=1(𝑔𝑗− 𝑐𝑗)𝑥𝑗− ∑𝑛𝑗=1𝑘𝑗𝑦𝑗, vincolato da ∑𝑛𝑗=1𝑎𝑖𝑗𝑥𝑗≤ 𝑏𝑖, 𝑥𝑗≤ 𝑀𝑦𝑗, 𝑦𝑗∈ {0,1}, 𝑥𝑗≥ 0.
NOTAZIONE MATRICIALE
Sia il modello da considerare il seguente: {
max 𝑧 = 80𝑥1+ 70𝑥2 3𝑥1+ 2𝑥2+ 𝑥3= 15 2𝑥1+ 3𝑥2+ 𝑥4= 15 𝑥1, 𝑥2, 𝑥3, 𝑥4 ≥ 4
. Consideriamo la funzione da massimizzare, e
vediamo che x1 e x2 hanno coefficienti 80 e 70, mentre x3 e x4 sono a 0, quindi 𝑐𝑇 = [80,70,0,0], 𝑥 = [ 𝑥1 𝑥2 𝑥3 𝑥4
] e il
prodotto scalare tra questi due vettori 𝑧 = ∑4𝑗=1𝑐𝑗𝑥𝑗= 80𝑥1+ 70𝑥2+ 0𝑥3+ 0𝑥4= 𝑐𝑇𝑥, che è la funzione obiettivo iniziale. Per rappresentare i vincoli, mettiamo i coefficienti delle variabili x delle equazioni in 𝐴 = [3 2 1 0
2 3 0 1] e i termini noti li mettiamo in 𝑏 = [15
15], e quindi avremo che la prima riga è il prodotto scalare di 𝑎1𝑗 per x (𝑏1) e la seconda è il prodotto scalare di 𝑎2𝑗 per x (𝑏2). In sintesi, 𝐴𝑥 = 𝑏.
Un problema generico quindi avrà una funzione da massimizzare max{𝑐𝑇𝑥 𝑐𝑜𝑛 𝐴𝑥 = 𝑏 𝑒 𝑥 ≥ 0} 𝑠𝑢𝑝𝑝𝑜𝑠𝑡𝑜 𝑚 = 𝑟𝑎𝑛𝑘(𝐴).
Definizione: Base
Una base di A è una sottomatrice quadrata B di A fatta da m colonne linearmente indipendenti (m=numero vincoli), quindi ha determinante diverso da 0.
Definizione: Variabile di base
Variabili associate alle colonne della matrice B, mentre sono non di base le variabili che sono associate alle rimanenti colonne.
Il sistema può venir riscritto per evidenziare la parte di base. A ha n colonne (𝐴 = [𝐴1… 𝐴𝑛]) e ne andiamo a selezionare m (𝐴 = [𝐵, 𝐹], B è base F è fuori base) e supponiamo che 𝐵 = [𝐴1… 𝐴𝑚]. Andiamo a dividere il vettore delle variabili in 𝑥 = [𝑥𝐵
𝑥𝐹] in variabili di base e fuori base. Possiamo riscrivere quindi 𝐴𝑥 = 𝑏 separando le componenti:
siccome la matrice A è partizionata in B e F, così come quello x, le variabili 𝑥𝐵 moltiplicano le colonne di B, idem per F (𝐵𝑥𝐵+ 𝐹𝑥𝐹= 𝑏) e le componenti in 𝑥𝐵 devono essere isolate (𝑥𝐵= 𝐵−1𝑏 − 𝐵−1𝐹𝑥𝐹) per risolvere il sistema matriciale e, imponendo che le 𝑥𝐹 siano uguali a zero, abbiamo risolto il sistema (soluzione di base). Tutto questo vale per i vincoli delle equazioni, ma non è detto che la soluzione trovata non abbia componenti negativi: se ci sono componenti negativi, allora la soluzione non è ammissibile: ci interessano solo quelle ammissibili (tutte le componenti sono non negative).
Tornando all’esempio, abbiamo 𝐴 = [3 2 1 0
2 3 0 1] , 𝐵 = [3 2
2 3] , 𝐹 = [1 0
0 1] 𝑥𝐵= [𝑥1
𝑥2] 𝑥𝐹= [𝑥3
𝑥4] 𝐵−1= [
3 5 −2
5
−2
5 3
5
].
𝐵−1∗ 𝐴 = [1 0
0 1
3
5 −2
5
−2
5 3 5
], 𝐵−1𝑏 = [
3
5 −2
5
−2
5 3 5
] [15 15] = [3
3]. 𝑥𝐵= [3 3] − [
3
5 −2
5
−2
5 3 5
] [𝑥3 𝑥4].
MODI DI SCRITTURA
Il problema di programmazione lineare può essere scritto in diversi modi, tra loro equivalenti:
• Standard, min {𝑐𝑇𝑥: 𝐴𝑥 = 𝑏, 𝑥𝑗≥ 0, 𝑗 = 1 … 𝑛}
• Canonica, min{𝑐𝑇𝑥: 𝐴𝑥 ≥ 𝑏, 𝑥𝑗≥ 0, 𝑗 = 1 … 𝑛}
• Generale, min {𝑐𝑇𝑥: 𝐴𝑥 = 𝑏. 𝐴′𝑥 ≥ 𝑏′, 𝑥𝑗≥ 0, 𝑗 ∈ 𝐽 ⊂ {1 … 𝑛}}
Dalla forma generale min {𝑐𝑇𝑥: 𝐴𝑥 = 𝑏. 𝐴′𝑥 ≥ 𝑏′, 𝑥𝑗≥ 0, 𝑗 ∈ 𝐽 ⊂ {1 … 𝑛}} è possibile passare alla forma standard min {𝑐𝑇𝑥: 𝐴𝑥 = 𝑏, 𝑥𝑗≥ 0, 𝑗 = 1 … 𝑛}. Le disequazioni vanno quindi trasformate in equazioni, e questo viene fatto con una variabile slack. E’ inoltre necessario sistemare le variabili senza vincoli, e questo viene fatto sostituendo ad ogni 𝑥𝑗 la differenza tra due variabili non negative 𝑥𝑗= 𝑥𝑗+− 𝑥𝑗−.
Per passare da standard a canonica (rappresentare un’equazione con disequazioni) basta usare due disequazioni, una
≥ e l’altra ≤ con il medesimo testo, e passare da canonica a generale è tutt’altro che problematico.
GEOMETRIA DELLA PROGRAMMAZIONE LI NEARE
Lo spazio che usiamo è uno spazio a n dimensioni (tante quante le variabili) e qui un’equazione del tipo 𝛼𝑇𝑥 = 𝛼0 rappresenta un iperpiano, mentre una disequazione è un semispazio/semipiano.
Gli iperpiani e i semispazi sono insiemi convessi, e l’intersezione di un numero finito di insiemi convessi è a sua volta un insieme convesso, quindi lo spazio delle soluzioni di un problema di PL è un insieme convesso.
Definizione: Poliedro
Intersezione di un numero finito di iperpiani e semispazi 𝑃 = {𝑥 ∈ ℛ𝑛: 𝐴𝑥 = 𝑏, 𝐴′𝑥 ≥ 𝑏′).
Definizione: Politopo
Un poliedro limitato, ∃𝑀 > 0: ‖𝑥‖ ≤ 𝑀∀𝑥 ∈ 𝑃, dove la norma indica la “lunghezza”.
Definizione: Vertice
Un punto x di un poliedro P tale che ∄𝑥1, 𝑥2∈ 𝑃 con 𝑥 =1
2𝑥1+1
2𝑥2 (non esistono due punti che sommati e moltiplicati per 0.5 dà come risultato il punto x). Un Poliedro ha un numero finito di vertici.
Teorema: Minkowsky-Weyl
Qualunque punto di un Politopo può essere ottenuto come combinazione convessa dei suoi vertici (combinazione lineare di punti che ha come coefficienti numeri compresi tra 0 e 1 e questa combinazione dà 1).
Teorema: Soluzione ottima
Dato un problema di Programmazione Continua min{𝑐𝑇𝑥: 𝑥 ∈ 𝑃} dove P è un Politopo finito, c’è almeno un vertice di P che fornisce la soluzione ottima.
Dimostrazione
Siano 𝑥1… 𝑥𝑘 vertici di P, 𝑦 ∈ 𝑃 un qualsiasi punto di P e 𝑧∗ il valore minimo su tutti i vertici. 𝑦 ∈ 𝑃 ⇒ ∃𝜆1… 𝜆𝑘≥ 0, ∑𝑘𝑖=1𝜆𝑖= 1: 𝑦 = ∑𝑘𝑖=1𝜆𝑖𝑥𝑖 per Minkowski-Weyl. Quindi abbiamo 𝑐𝑇𝑦 = 𝑐𝑇∑𝑘𝑖=1𝜆𝑖𝑥𝑖=
∑𝑘𝑖=1𝜆𝑖(𝑐𝑇𝑥𝑖) ≥∑𝑘𝑖=1𝜆𝑖𝑧∗= 𝑧∗. Quindi 𝑐𝑇𝑦 ≥ 𝑧∗, ovvero qualsiasi punto del politropo è maggiore uguale del valore minimo su tutti i vertici.
Teorema:
Dato un problema di Programmazione Continua in forma standard e una base B, allora la soluzione base 𝑥𝐵= 𝐵−1𝑏 , 𝑥𝐹= 0 definisce un vertice di 𝑃 ≔ {𝑥: 𝐴𝑥 = 𝑏, 𝑥 ≥ 0}.
Quindi se una soluzione base è ammissibile, allora definisce un vertice del poliedro.
L’ALGORITMO DEL SIMPLESSO
Bisogna trovare una base che fornisce una soluzione ammissibile x (per la quale servirà un metodo a parte). Avendo trovato la base, finché x non è ottima e illimitata, si trasforma prima la base attuale in una nuova base cambiando una sola colonna della base (si cambia una colonna della base con una colonna che non era in base) e si fa in modo che in questo cambiamento il valore della funzione obiettivo si avvicini ad essere ottima. L’algoritmo termina in un numero finito numero di iterazioni (𝑛
𝑚) = 𝑛!
𝑚!(𝑛−𝑚)!.
Consideriamo la condizione di ottimalità. In un problema di massimizzazione abbiamo max{𝑐𝑇𝑥: 𝐴𝑥 = 𝑏, 𝑥 ≥ 0}, 𝑥𝐵= 𝐵−1𝑏 − 𝐵−1𝐹𝑥𝐹, 𝐵−1𝑏 ≥ 0. Applicando la divisione delle componenti in base e fuori base fatta per le variabili ai coefficienti della funzione obiettivo si ha che 𝑧 = 𝑐𝑇𝑥 = [𝑐𝐵𝑇, 𝑐𝐹𝑇] ∗ [𝑥𝐵
𝑥𝐹] = 𝑐𝐵𝑇(𝐵−1𝑏 − 𝐵−1𝐹𝑥𝐹) + 𝑐𝐹𝑇𝑥𝐹= 𝑐𝐵𝑇𝐵−1𝑏 + (𝑐𝐹𝑇− 𝑐𝐵𝑇𝐵−1𝐹)𝑥𝐹= 𝑐𝐵𝑇𝐵−1𝑏 + 𝑐̅𝐹𝑇𝑥𝐹 dove i coefficienti 𝑐𝑇 = 𝑐𝑇− 𝑐𝐵𝑇𝐵−1𝐴 prendono il nome di costi ridotti.
Teorema:
Una soluzione di base ammissibile di un problema di PL in caso di massimo è ottima se tutti i costi ridotti sono tutti non positivi. Se il problema è di minimo, vale l’inverso.
Chiarito come scegliere la colonna che entra, dobbiamo decidere la colonna che esce dalla base. Indichiamo con 𝐴̅ = 𝐵−1𝐴 la matrice A trasformata rispetto alla base attuale, con 𝐹̅ = 𝐵−1𝐹 la parte della matrice F trasformata rispetto alla base attuale e con 𝑏̅ = 𝐵−1𝑏 i termini noti trasformati rispetto alla base attuale. La soluzione di base diventa quindi 𝑥𝐵= 𝐵−1𝑏 − 𝐵−1𝐹𝑥𝐹= 𝑏̅ − 𝐹̅𝑥𝐹. Sia ora 𝑥𝐵= [𝑥[1]… 𝑥[𝑚]]𝑇, ovvero identifichiamo le colonne di base, e se la colonna h, cioè 𝑥ℎ, entra nella base, succede che tutta la parte 𝐹̅ (a destra e a sinistra della colonna h) non ci
interessano, e l’equazione associata alla riga i è data dalla variabile che sta in base in riga i + il coefficiente in riga i e colonna h, e questa equazione è uguale all’iesimo elemento di 𝑏̅. In modo formale:
{
𝑥[1]= 𝑏̅ − 𝑎̅1 1ℎ𝑥ℎ≥ 0
…
𝑥[𝑖]= 𝑏̅ − 𝑎̅𝑖 𝑖ℎ𝑥ℎ≥ 0
…
𝑥[𝑚]= 𝑏̅̅̅̅ − 𝑎̅𝑚 𝑚ℎ𝑥ℎ≥ 0
⇒ {
𝑎̅1ℎ𝑥ℎ≤ 𝑏̅1
… 𝑎̅𝑖ℎ𝑥ℎ≤ 𝑏̅𝑖
… 𝑎̅𝑚ℎ𝑥ℎ≤ 𝑏̅̅̅̅𝑚
Per ogni disequazione bisogna esaminare due casi, ovvero 𝑎̅1ℎ≤ 0 (cambiando il valore di 𝑥ℎ la disuguaglianza rimane verificata) e 𝑎̅1ℎ> 0 ⇒ 𝑥ℎ≤ 𝑏̅𝑖
𝑎𝑖ℎ
̅̅̅̅̅. Da qui ne consegue che 𝑥ℎ≤ min {𝑏̅𝑖
𝑎𝑖ℎ
̅̅̅̅̅: 𝑎̅̅̅̅ > 0, 𝑖 =𝑖ℎ 1 … 𝑚}. Con questa conseguenza possiamo capire qual è la riga da buttare fuori, che chiamiamo t che dà la relazione
precedentemente indicata. Dato che 𝑥[𝑡]= 𝑏̅ − 𝑎𝑡 ̅̅̅̅𝑥𝑡ℎ ℎ, 𝑥ℎ= 𝑏̅̅̅𝑡
𝑎𝑡ℎ
̅̅̅̅̅⇒ 𝑥[𝑡]= 0, t lascia la base. Se, invece, 𝑎̅̅̅̅ ≤ 0, ∀𝑖 … 𝑚, 𝑥𝑖ℎ ℎ può crescere illimitatamente, con 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 che rimane soddisfatto: il problema è illimitato.
Lo pseudocodice dell’algoritmo del simplesso, quindi, risulta essere quello riportato a lato.
Rimane da risolvere l’ultimo problema, ovvero trovare una base ammissibile quando non direttamente disponibile (riga 1). In casi fortunati, una volta assemblato il tableau, si ha già disponibile una matrice identità da qualche parte, e
Locate a feasible basis 𝑩 = [𝑨[𝟏]… 𝑨[𝒎]] unlimited = false, optimal = false
while (optimal = false and unlimited = false) do compute 𝑩−𝟏 and set 𝒖𝑻= 𝒄𝑩𝑻𝑩−𝟏
compute reduced_costs 𝒄̅̅̅ = 𝒄𝒉 𝒉− 𝒖𝑻𝑨𝒉, ∀𝒙𝒉: 𝒉 ∈ 𝑨\𝑩 if (𝒄̅̅̅ < 𝟎∀𝒙𝒉 𝒉) then optimal = true
else
choose a non basic variable 𝒙𝒉: 𝒄̅̅̅ > 𝟎 𝒉
compute 𝒃̅ = 𝑩−𝟏𝒃 and 𝑨̅̅̅̅ = 𝑩𝒉 −𝟏𝑨𝒉
if (𝒂̅̅̅̅ ≤ 𝟎, 𝒊 = 𝟏 … 𝒎) then unlimited = true 𝒊𝒉
else
find t = argmin(𝒃̅ /𝒂𝒊 ̅̅̅̅, 𝒊 = 𝟏 … 𝒎: 𝒂𝒊𝒉 ̅̅̅̅ > 𝟎 ) 𝒊𝒉
update base setting [t]=h
endif endif
endwhile
qui non c’è problema. Nel caso in cui questo non si verifichi, è necessario procurarsi in qualche modo una base. Il modo per risolvere il problema è aggiungere delle variabili artificiali (indicate con a) che aggiungo per ogni riga ottenendo una matrice identità in fondo al tableau, e le metto nella base. Così facendo ho però modificato il modello, e questo non è bene, e devo assicurarmi che queste variabili siano uscite dalla base una volta trovata la soluzione ottima. Nella riga della funzione obiettivo, si mettono valori molto negativi (se il problema è di massimo), il che però causa problemi se usiamo il calcolatore. L’idea è quindi quella di lasciare le variabili artificiali, e di darvi peso 1 nella funzione obiettivo e 0 alle altre e trasformare il problema in un problema di minimo (problema artificiale di minimo).
METODO DELLE DUE FASI
La prima fase corrisponde a risolvere il problema nella forma artificiale di minimo. Cerco quindi una soluzione ottimale che non abbia le variabili artificiali al suo interno. Trovata una base ottimale, si passa alla seconda fase, in cui tengo buono il tableou, tolgo le variabili artificiali e risistemo la funzione obiettivo.
Parte 1: Con operazioni elementari, “libero” la riga sopra alla base (quella con i costi obiettivo), e la porto così in situazione iniziale per il metodo del tableau.
Parte 2: Ripristino il tutto, e ho così trovato una base da cui partire con il metodo del simplesso. Metto i costi delle colonne in base a 0, mettendomi in situazione di partenza, e proseguo.
Riassumendo: sia (x*,a*) la soluzione ottimale su un problema artificiale, e sia w* il suo valore. Se w*>0, non esiste una soluzione in cui le variabili artificiali siano fuori dalla base (non va bene), se w*=0, e nessuna variabile artificiale è nella base allora consideriamo le variabili x* come base, se invece ci sono variabili artificiali allora: se nella riga del tableau c’è il coeff 1 nella colonna h della variabile artificiale (e tutti gli altri valori sono 0) si può cancellare la riga e la colonna della v. artificiale, se invece c’è la stessa cosa ma con valori non nulli nella riga, allora si può fare del pivot sull’elemento selezionato.
DEGENERAZIONE
Definizione: Soluzione di base degenere
Chiamiamo soluzione di base degenere una soluzione che ha una o più componente uguale a 0.
Il problema è che quando si va a fare un pivot, anche se il costo ridotto della variabile ci farebbe cambiare la funzione obiettivo, in pratica facendo un pivot la variabile a valore 0 entra in base, la funzione obiettivo non cambia quando passo da un tableau all’altro, condizione esclusa dall’algoritmo del simplesso (il che manda il tutto in ciclo infinito).
Per evitare di avere cicli, si fa uso della regola di Bland.
Regola di Bland
Ogni volta che ci sono due colonne equivalenti che potrebbero entrare in base, va sempre scelta la colonna di indice minimo, e ogni volta che ci sono due righe equivalenti per il pivot, va scelta quella con l’indice minimo.
DUALITÀ
Dato un problema di minimo con due disequazioni (ad esempio), se si sposta la retta iso-profitto fuori dalla regione ammissibile P, troviamo la stessa soluzione minimizzando in P o massimizzando fuori da P. In termini matematici, ci sono due problemi: il problema primario (il problema di partenza, min 𝑐𝑇𝑥 , 𝐴𝑥 ≥ 𝑏, 𝑥 ≥ 0) e il suo duale
(max 𝑢𝑇𝑏 , 𝑢𝑇𝐴 ≤ 𝑐𝑇, 𝑢 ≥ 0), con ogni regola primaria associata ad una variabile duale e con ogni variabile primaria associata ad una regola duale. I termini noti e i coefficienti
della funzione obiettivo cambiano quindi posto passando dal primario e dal duale. La
soluzione del problema primale viene indicata con 𝑧𝑃, quella del duale con 𝑧𝐷. La prima parte della tabella spiega come associare i vincoli del primale alle variabili del duale, la seconda parte fa l’opposto.
Finora abbiamo considerato il problema duale espresso in forma canonica, e se ragioniamo in forma standard vi è una differenza: cambiano diffatti i vincoli del duale, questo perché le variabili del primale possono assumere qualunque tipo di valore.
La coppia primale-duale è equivalente, e il problema primale è solo il primo a venire considerato (non sempre il primale è un problema di minimo, ad esempio).
Lemma di Farkas
Una disuguaglianza lineare 𝑐0≤ 𝑐𝑇𝑥 è verificata da tutti i punti di un poliedro 𝑃 = {𝐴𝑥 = 𝑏, 𝑥 ≥ 0} non vuoto se e solo se esiste 𝑢 ∈ ℛ𝑚 (dove m è il numero di vincoli) tale che 𝑐𝑇≥ 𝑢𝑇𝐴 𝑒 𝑐0≤ 𝑢𝑇𝑏.
Dimostrazione
Per la parte sufficiente, si dimostra che se le due disequazioni sono rispettate, allora la disuguaglianza è verificata.
𝑐𝑇𝑥 ≥ 𝑢𝑇𝐴𝑥 = 𝑢𝑇𝑏 ≥ 𝑐0⇒ 𝑐𝑇𝑥 ≥ 𝑐0.
Per quella necessaria, si dimostra che se la disuguaglianza è verificata allora sono rispettate anche le due disequazioni.
Considerando il problema min{𝑐𝑇𝑥: 𝑥 ∈ 𝑃}, e ha una soluzione ottima finita dato che 𝑐0≤ 𝑐𝑇𝑥∀𝑥 ∈ 𝑃 implica 𝑐0≤ min{𝑐𝑇𝑥: 𝑥 ∈ 𝑃}. Indicando con 𝑥∗ la soluzione ottimale e B la base corrispondente, si ha che 𝑢𝑇 = 𝑐𝐵𝑇𝐵−1 soddisfa le disequazioni (𝑐𝑇= 𝑐𝑇− 𝑐𝐵𝑇𝐵−1𝐴 ≥ 0 ⇒ 𝑐𝑇≥ 𝑢𝑇𝐴, 𝑐0≤ 𝑐𝑇𝑥∗= 𝑐𝐵𝑇𝑥𝐵∗ = 𝑐𝐵𝑇𝐵−1𝑏 = 𝑢𝑇𝑏).
Per dimostrare l’equivalenza dei problemi primale/duale, definiamo il poliedro 𝑃 = {𝐴𝑥 = 𝑏, 𝑥 ≥ 0} e prendiamo un problema di ottimizzazione min{𝑐𝑇𝑥: 𝐴𝑥 = 𝑏, 𝑥 ≥ 0} = max{𝑐0: 𝑐0≤ 𝑐𝑇𝑥, 𝑥 ∈ 𝑃} = max{𝑐0: 𝑐0≤ 𝑢𝑇𝑏, 𝑐𝑇 ≥ 𝑢𝑇𝐴} (Lemma di Farkas) = max{𝑢𝑇𝑏: 𝑐𝑇 ≥ 𝑢𝑇𝐴}.
Teorema: Dualità forte
Se dato un problema in forma standard con una soluzione finita, allora il valore della soluzione in forma standard è uguale a quella del problema duale.
Teorema: Dualità debole
Se dato un problema primale in forma canonica, per qualunque coppia 𝑥̃ ∈ 𝑃, 𝑢 ̃ ∈ 𝐷 ammissibile per il problema duale è minore uguale del valore della funzione obiettivo
calcolato per il problema primale (𝑢̃𝑇𝑏 ≤ 𝑐𝑇𝑥̃).
Dimostrazione
𝐴𝑥̃ ≥ 𝑏 ⇒ 𝑢̃𝑇𝐴𝑥̃ ≥ 𝑢̃𝑇𝑏 ma 𝑐𝑇≥ 𝑢̃𝑇𝐴 ⇒ 𝑐𝑇𝑥̃ ≥ 𝑢̃𝑇𝑏.
In base alle caratteristiche del problema primale, il duale
può avere degli aspetti particolari (come indicato dalla tabella a fianco).
CONDIZIONI DI OTTIMALITÀ
Si consideri il problema min{𝑐𝑇𝑥: 𝐴𝑥 ≥ 𝑏, 𝑥 ≥ 0} che ha come duale max{ 𝑢𝑇𝑏: 𝑢𝑇𝐴 ≤ 𝑐𝑇, 𝑢𝑇 ≥ 0} e poniamo 3 condizioni:
A. Ammissibilità del primale: 𝐴𝑥 ≥ 𝑏, 𝑥 ≥ 0 B. Ammissibilità del duale: 𝑢𝑇𝐴 ≤ 𝑐𝑇, 𝑢𝑇≥ 0 C. Dualità forte: 𝑐𝑇𝑥 = 𝑢𝑇𝑏
Usando A e B, 𝑐𝑇𝑥 > 𝑢𝑇𝐴𝑥 ≥ 𝑢𝑇𝑏, e C, 𝑐𝑇𝑥 = 𝑢𝑇𝐴𝑥, 𝑢𝑇𝐴𝑥 = 𝑢𝑇𝑏, si ha (𝑐𝑇− 𝑢𝑇𝐴)𝑥 = 0, 𝑢𝑇(𝐴𝑥 − 𝑏) = 0, che prendono il nome di condizioni di ottimalità: se una soluzione x e u sono entrambe ottime, devono verificare quelle due condizioni. Le condizioni, dato che 𝑐𝑇− 𝑢𝑇𝐴 ≥ 0 e 𝑥 ≥ 0, possono venire scritte come
{
(𝑐1− 𝑢𝑇𝐴1)𝑥1= 0
…
(𝑐𝑛− 𝑢𝑇𝐴𝑛)𝑥𝑛= 0 {
𝑢1(𝑎1𝑥 − 𝑏1) = 0
…
𝑢𝑚(𝑎𝑚𝑥 − 𝑏𝑚) = 0
Riassumendo, dato un problema primale e il suo duale e prendiamo una soluzione ammissibile per il primale e una per il duale e queste rispettano le condizioni di ottimalità, allora la coppia è ottima.
ALGORITMO DEL SIMPLESSO DUALE
L’algoritmo del simplesso opera sul problema Primale e soddisfa le richieste A e C, e termina quando 𝑐𝑇= 𝑐𝑇− 𝑐𝐵𝑇𝐵−1𝐴 = 𝑐𝑇− 𝑢𝑇𝐴 ≥ 0 ⇒ B.
L’algoritmo del simplesso sul duale soddisfa le richieste B e C, e termina quando viene rispettata la condizione A. Dato un poliedro 𝑃: min{𝑐𝑇𝑥: 𝐴𝑥 = 𝑏, 𝑥 ≥ 0}, una base B e una condizione 𝑢𝑇= 𝑐𝐵𝑇𝐵−1 abbiamo (𝑐𝑇− 𝑢𝑇𝐴)𝑥 =
(𝑐𝐵𝑇− 𝑢𝑇𝐵)𝑥𝐵+ (𝑐𝐹𝑇− 𝑢𝑇𝐹)𝑥𝐹= 0 (C), se 𝑐𝑇 = 𝑐𝑇− 𝑐𝐵𝑇𝐵−1𝐴 ≥ 0 (B) e se 𝑥𝐵 = 𝐵−1𝑏 ≥ 0 la coppia x, u è ottimale (A), diversamente ∃𝑥𝑗< 0. Si esegue puoi un pivot con il termine noto negativo per procedere nella direzione di A.
Se 𝑎𝑡𝑗 ≥ 0, ∀𝑗, l’equazione t non può venir soddisfatta da valori ≥ 0, se ∃ℎ: 𝑎𝑡ℎ< 0 si esegue il pivot su 𝑎𝑡ℎ e 𝑥ℎ entra nella base con un valore positivo (𝑎𝑏𝑡
𝑡ℎ). Il pivot pone a 0 𝑐ℎ e gli altri costi diventano 𝑐̃𝑗= 𝑐𝑗−(𝑐ℎ)
𝑎𝑡ℎ𝑎𝑡𝑗, 𝑎𝑡𝑗≥ 0 ⇒ 𝑐̃𝑗≥ 0, 𝑎𝑡𝑗 < 0, 𝑐̃𝑗≥ 0 se 𝑐𝑗≥ 𝑐ℎ
𝑎𝑡ℎ𝑎𝑡𝑗⇒ ℎ = 𝑎𝑟𝑔𝑚𝑖𝑛 { 𝑐𝑗
|𝑎𝑡𝑗|: 𝑎𝑡𝑗 < 0}, che è la colonna che viene scelta per il pivot.
ANALISI DI SENSITIVITÀ (PARTE 17)
Dato un modello che rappresenta un problema, i numeri inseriti possono essere soggetti a fluttuazioni. Ci si domanda se, con la variazione dei parametri, la soluzione ottimale rimanga sempre la stessa (quanto è robusta la soluzione ottima). All’aumentare dei termini noti, la regione ammissibile cresce, ma senza alterare la base… ma se i termini noti crescono troppo, la base cambia (altrimenti risulta non ammissibile, ovvero una soluzione in base è negativa). Si ha quindi 𝑏 → 𝑏 + Δ𝑏 ⇒ 𝑥𝐵= 𝐵−1(𝑏 + Δ𝑏) ≥ 0, 𝑥𝐵= 𝐵−1Δ𝑏 ≥ 0.
Se sono i coefficienti a cambiare, invece, la soluzione va a spostarsi (in quanto determina una variazione della pendenza della retta iso-profitto), ma rimane immutata la regione ammissibile. L’ottimalità della base è garantita da 𝑐𝑇 = 𝑐𝑇− 𝑐𝐵𝑇𝐵−1𝐴 ≥ 0 → 𝑐𝐹− 𝑐𝐵𝐵−1𝐹 ≥ 0, se j non è in base allora 𝑐𝑗+ Δ𝑐𝑗− 𝑐𝐵𝐵−1𝐴𝑗≥ 0 → Δ𝑐𝑗≤ 𝑐𝑗− 𝑐𝐵𝐵−1𝐴𝑗= 𝑐𝑗, mentre se è in base 𝑐𝐹− 𝑐𝐵𝐵−1𝐹 ≥ 0
INTEGER LINEAR PROGRAMMING
METODO DEL SIMPLESSO MIGLIORATO (PARTE 18)
Consideriamo un tableau con molte colonne e poche righe: solo una piccola parte del tableau che viene aggiornata viene effettivamente impiegata, e il resto non viene affatto utilizzato. Per fare il pivoting, è necessario calcolare tutti i costi ridotti per selezionare la colonna h (che ha costo negativo), e ci serve solo la colonna
𝐵−1𝐴ℎ per selezionare la riga. Una possibile strategia è di non elaborare l’intero tableau, ma di calcolare solo le colonne che entrano in base. Per fare ciò, oltre ad utilizzare il tableau, useremo anche una matrice che prende il nome di carry, che al posto della funzione obiettivo ha zeri e al posto del corpo del tableau ha una matrice identità.
Eseguiamo ora le operazioni su Carry e Tableau, considerandoli come un entità unita, e si ottiene il seguente risultato:
nel carry è quindi presente 𝐵−1, e possiamo considerare solo lei e i termini noti.
L’algoritmo procede in questo modo:
1. Calcola i costi ridotti 𝑐𝑗= 𝑐𝑗− 𝑢𝑇𝐴 ∀𝑗 ∈ 𝐹
2. Sceglie la variabile entrante 𝑥ℎ
3. Genera la colonna 𝐴ℎ= 𝐵−1𝐴ℎ e orla il carry 4. Seleziona la riga t per il pivot
5. Esegue il pivot sul carry orlato e sul termine noto METODO DELLA COLUMN GENERATION
L’algoritmo visto può essere sintetizzato in 4 passi:
1. Trova una base accettabile B 2. Calcola 𝑥𝐵= 𝐵−1𝑏, 𝑢𝑇= 𝑐𝐵𝑇𝐵−1
3. Trova la colonna 𝑗∗ con i costi ridotti minimi, 𝑐𝑗∗= 𝑐𝑗∗− 𝑢𝑇𝐴𝑗∗ che sarà il valore minimo tra tutte le colonne j 4. Se 𝑐∗≥ 0, il processo si interrompe, diversamente si va a definire una nuova base B includendo 𝐴𝑗∗ e si torna
al passo 2.
PROBLEMA DEL CUTTING STOCK
Sia I un insieme di n oggetti di lunghezza 𝑙𝑖, 𝑖 = 1 … 𝑛, sia 𝑛𝑖 il numero di pezzi che possono essere tagliati da ogni oggetto i e sia L la lunghezza dei fogli da cui gli oggetti vengono tagliati. Viene definito come pattern una configurazione di oggetti che possono venir tagliati da un foglio.
Indichiamo con J l’insieme di tutti i pattern, e vado a inserirli in una tabella, indicando per ogni pattern quanti oggetti posso ottenere.
Indichiamo con 𝑎𝑖𝑗 il numero di pezzi dell’oggetto i tagliati nel pattern j (A è la tabella che abbiamo costruito), e all’interno della variabile 𝑦𝑗 il numero di volte che il pattern j verrà usato.
L’obiettivo è quello di minimizzare il numero di pattern utilizzati, ovvero min ∑𝑗∈𝐽𝑦𝑗, con vincolo che per ogni oggetto i io produca il numero richiesto (∑𝑗∈𝐽𝑎𝑖𝑗𝑦𝑗≥ 𝑛𝑖, 𝑖 ∈ 𝐼). Questo problema non sarebbe normalmente impiegabile, a causa dell’altro numero dei pattern (tante, troppe variabili), ma con il metodo del simplesso migliorato non è un problema. Al posto dell’insieme J andiamo a usare un insieme ridotto J’ (numero ridotto di colonne), ottenendo quindi un problema ridotto (da L(P) a RL(P)). Data la soluzione ottimale di RL(P) e le sue variabili duali u, se 𝑐𝑇− 𝑢𝑇𝐴 ≥ 0 sappiamo che la soluzione è ottimale anche per L(P), ma non ho a disposizione A: è necessario trovare un modo per superare il calcolo diretto dei costi. Vogliamo sapere se 𝑐𝑇= 𝑐𝑇− 𝑢𝑇𝐴 ≥ 0, 𝑐𝑗= 𝑐𝑗− 𝑢𝑇𝐴𝑗= 1 − ∑𝑖∈𝐼𝑎𝑖𝑗𝑢𝑖≥ 0, 𝜃 = min
𝑗∈𝐽(1 − ∑𝑖∈𝐼𝑎𝑖𝑗𝑢𝑖), se 𝜃 ≥ 0 siamo a posto. Vogliamo ora trovare il pattern 𝑗∗ che dia i costi ridotti minimi, e assegnamo alla variabile 𝑧𝑖 il numero di volte che l’oggetto i viene usato nel pattern ottimale. Il modello sarà:
min 1 − ∑ 𝑢𝑖𝑧𝑖
𝑖∈𝐼
, ∑ 𝑙𝑖𝑧𝑖
𝑖∈𝐼
≤ 𝐿, 𝑧𝑖≥ 0 𝑖 ∈ 𝐼 equivalente a max 𝜃′= ∑ 𝑢𝑖𝑧𝑖
𝑖∈𝐼
, ∑ 𝑙𝑖𝑧𝑖
𝑖∈𝐼
≤ 𝐿, 𝑧𝑖≥ 0
Perché minimizzando il negativo di una funzione vuol dire massimizzare quella funzione, e tutto è stato ricondotto ad un problema di tipo knapsack con profitti 𝑢𝑖, pesi 𝑙𝑖.
PROGRAMMAZIONE INTERA CONTRO PROGRAMMAZIONE CONTINUA
A livello di vincoli, viene aggiunto il vincolo di interezza, ma questo piccolo cambiamento va a trasformare un problema semplice in un problema complesso, np completo. Possiamo tuttavia provare a costruire una soluzione intera partendo da una più facile da ottenere soluzione continua. Arrotondando la soluzione ottimale PLC, si ottiene una soluzione ammissibile, ma non ottimale per il problema PLI, che si troverà comunque nei pressi della PLC arrotondata: in altre parole, ci si accontenta della soluzione sub ottimale, anche se a volte vengono ricavate soluzioni inutili. Questa distinzione viene fatta in base alla dimensione dei valori delle variabili: se sono grandi valori, un piccolo
errore è accettabile (soluzione utile), risultano essere inutili se i valori sono piccoli (ad esempio, produrre 2,5 navi) e sono inutili quando la soluzione arrotondata non è ammissibile.
Consideriamo il problema intero 𝑧𝑃𝐿𝐼= min{𝑐𝑇𝑥: 𝑥 ∈ 𝑃 ∩ 𝑍𝑛}, dove P è un politopo e 𝑍𝑛 è l’insieme di tutti i punti a coordinate intere. Il rilassamento continuo rimuove quest’ultima parte, e si limita a lavorare sul politopo. 𝑧𝑃𝐿𝐶 diventa quindi una stima, dato che abbiamo un problema intero definito su insieme ristretto e togliendo questo vincolo estendiamo l’insieme delle soluzioni, e quando vado a ottimizzare e cerco il minimo su una regione ammissibile più grande troverò un minimo minore uguale di quello che troverei il PLI: nei problemi di minimo prende il nome di lower bound, in quelli di massimo upper bound (non potranno mai essere superati dal problema intero).
Definizione: Convex Hull
Dato qualsiasi insieme 𝑆 ∈ ℛ𝑛 chiamiamo convex hull il più piccolo insieme convesso (continuo) 𝑐𝑜𝑛𝑣(𝑆) contenente S.
Se S è l’insieme delle soluzioni, allora si ha che in PLI min{𝑐𝑇𝑥: 𝑥 ∈ 𝑃 ∩ 𝑍𝑛} = min{𝑐𝑇𝑥: 𝑥 ∈ 𝑐𝑜𝑛𝑣(𝑃 ∩ 𝑍𝑛)} in PLC.
PIANI DI TAGLIO
Un’idea perseguibile è quella di ottenere l’approssimazione del convex hull per passi successivi, ovvero aggiungere un vincolo al problema che prende il nome di piano di taglio. Applicando questo vincolo va a rendere non ammissibile alcune soluzioni del problema PLC, senza intaccare le soluzioni intere. Data la soluzione ottima del rilassamento continuo 𝑥∗ di P, la
disuguaglianza 𝛼𝑇𝑥 ≥ 𝛼0 è un piano di taglio se 𝛼𝑇𝑥 ≥ 𝛼0∀𝑥 𝑖𝑛𝑡𝑒𝑟𝑖 ∶ 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 e 𝛼𝑇𝑥∗≤ 𝛼0 (ovvero, la soluzione intera è salva mentre quella continua non è accettabile). Un possibile algoritmo è presentato a lato.
Per avere un’implementazione efficiente, ci
concentriamo sulla soluzione del problema dopo aver aggiunto il piano di taglio, e andiamo ad aggiungere una riga e una colonna al tableau. Al posto di risolvere da zero il problema, usiamo la nuova colonna come colonna m+1 della matrice di base. La base risulta essere non adatta al problema primale, ma adatta al problema duale, e possiamo usare il simplesso duale partendo dalla riga aggiunta.
TAGLI DI GOMORY
Il metodo per il calcolo dei piani di taglio che viene presentato di seguito prende il nome di metodo di Gomory, che è un metodo generale valido per qualsiasi problema. L’idea di base è quella di sfruttare le informazioni del tableau per ricavare il piano, considerando di aver risolto il rilassamento continuo e aver trovato la base ottimale B, 𝑥𝐵= 𝐵−1𝑏, 𝑥𝐹= 0, 𝐴 = 𝐵−1𝐴, 𝑏 = 𝐵−1𝑏. Si ha che 𝑏𝑡= 𝑥𝑡+ ∑𝑗∈𝐹𝑎𝑡𝑗𝑥𝑗 è l’equazione del tableau, e su questa vengono fatte le seguenti trasformazioni: 𝑥𝑡+ ∑𝑗∈𝐹⌊𝑎𝑡𝑗⌋𝑥𝑗≤ 𝑏𝑡, dato che la soluzione deve essere intera si ha 𝑥𝑡+
∑𝑗∈𝐹⌊𝑎𝑡𝑗⌋𝑥𝑗≤ ⌊𝑏𝑡⌋ e si va a sottrarre questo all’equazione del tableau, ottenendo ∑𝑗∈𝐹(𝑎𝑡𝑗− ⌊𝑎𝑡𝑗⌋)𝑥𝑗≥ 𝑏𝑡− ⌊𝑏𝑡⌋. Il taglio è valido per costruzione (non è stata eliminata alcuna soluzione intera).
Input: problema PLI su P
Output: se esiste, la soluzione ottimale xS
Risoluzione del rilassamento continuo con xS if (problema illimitato o vuoto)
return endif
while(xS non intero) do
trova un piano di taglio valido a_t*x>=a0 aggiungi vincolo a_t*x-x[n+1]=a0
risolvi il problema PLC if (problema vuoto)
return endif
endwhile
BRANCH AND BOUND
Il Branch and Bound è una tecnica generale per trovare la soluzione ottimale a un problema np completo di ottimizzazione, come ad esempio min{𝑧(𝑥): 𝑥 ∈ 𝑆(𝑃0)}. Il metodo è composto da due passaggi:
1. Si va a dividere 𝑃0 nei sottoproblemi 𝑃1, … , 𝑃𝑞 la cui unione fornisce il problema iniziale, con tutti i problemi che hanno la funzione obiettivo 𝑧(𝑃0) e con 𝑆(𝑃0) =∪𝑘=1𝑞 𝑆(𝑃𝑘) (anche se è meglio lavorare con delle partizioni, in modo da evitare di trovare le stesse soluzioni in più insiemi), quindi 𝑧(𝑃0) =
min{𝑧(𝑃1), … , 𝑧(𝑃𝑞)}.
2. Si applica una tecnica di bounding, che ci permettono di risolvere sottoproblemi senza risolverli esplicitamente
La soluzione del problema 𝑃𝐾 può essere ottenuta in 4 modi:
1. Trovo la soluzione ottimale (Esplicita) 2. Mostro che 𝑆(𝑃𝐾) = 0 (Esplicita)
3. Data una soluzione accettabile di valore 𝑧 provo che 𝑧(𝑃𝐾) ≥ 𝑧 (Implicita) 4. Applico a 𝑃𝐾 la fase di braniching (Esplicita)
La regola di branching va a determinare un albero delle decisioni, e ogni figlio rappresenta un problema.
Prendiamo 𝑧, valore di una soluzione accettabile. Questa può essere o un lower bound, che permette di risolvere un problema di minimizzazione 𝑃𝐾 se esiste un lower bound tale che 𝐿𝐵(𝑃𝐾) ≤ 𝑧(𝑃𝐾) ovvero 𝐿𝐵(𝑃𝐾) ≥ 𝑧, oppure un upper bound, che permette di risolvere un problema di massimizzazione 𝑃𝐾 se esiste un upper bound tale che 𝑈𝐵(𝑃𝐾) ≥ 𝑧(𝑃𝐾) ovvero 𝑈𝐵(𝑃𝐾) ≤ 𝑧. Un bound viene trovato mediante rilassamento del problema originale, ovvero dato un problema max{𝑧(𝑥): 𝑥 ∈ 𝑆(𝑃)} un rilassamento è 𝑅(𝑃) = (𝑧𝑅(𝑥), 𝑆𝑅(𝑃)) con 𝑆𝑅(𝑃) ⊇ 𝑆(𝑃) e con 𝑧𝑅(𝑥) ≤ 𝑧(𝑥)∀𝑥 ∈ 𝑆(𝑃) (Per la minimizzazione), 𝑧𝑅(𝑥) ≥ 𝑧(𝑥)∀𝑥 ∈ 𝑆(𝑃) (Per la massimizzazione).
Il rilassamento può essere di tipo continuo, ottenuto da un problema di PLI rimuovendo il vincolo di interezza, oppure viene fatto mediante rimozione di vincoli.
STRATEGIE ESPLORATIVE
Una volta decisa la struttura dell’albero (come dividiamo il problema in sottoproblemi) dobbiamo decidere la strategia di esplorazione. Le possibilità sono la Deep first (genera e esplora il primo sottoproblema disponibile, cercando sempre di, ad esempio nel caso di max, procedere nella direzione in cui l’upper bound aumenta), la Lowest/Highest first, che genera e valuta tutti i sottoproblemi del problema corrente, e li ordina in base al bound, per poi esplorare il minimo o il massimo (a seconda che sia lowest o highest), oppure si procede con la tecnica mista, che genera tutti i sottproblemi del problema attuale, e si va ad esplorare il problema con valore massimo/minimo (niente coda).
In base al problema, alcune tecniche vanno meglio delle altre (la deep first è adatta per problemi di schedulazione, la high/low first è adatta per problemi come quello del
commesso viaggiatore).
IMPLEMENTAZIONE DELLA DEEP FIRST Le variabili e funzioni considerate saranno level (livello dell’albero attuale, impostato a 1), k (contatore problemi, impostato a 0), active(l) (restituisce il problema attivo al livello l, inizialmente 0), lastChild(l) (restituisce l’ultimo figlio al livello l),
While true do
forward = true while forward do
j = lastChild(l)+1 k++
genera il jesimo sottoproblema PK di active(l) l++
lastChild(l)=0 active(l)=k
if PK è vuoto o UB(PK)<=zS forward=false
if PK ha una soluzione ottimale xC valore zC xS=xC
zS=xC
forward=false endif
endwhile
getNumCh(P) restiuisce il numero di figli generati dal problema P, xS e zS sono le soluzioni ottimali (inizialmente 0 e – infinito) e UB è la funzione che ritorna l’upperbound.
A lato è riportato lo pseudocodice.
Il deep first è quindi veloce da
implementare, trova soluzioni accettabili in un tempo breve, ma le prime soluzioni sono generalmente pessime. L’highest first, invece, sebbene sia più lento (ma non in modo drammatico) e più difficile da implementare, trova fin da subito buone soluzioni.
BRANCH AND BOUND STANDARD PER PLI
Nella forma standard, viene utilizzato il rilassamento continuo, con una regola di branching che seleziona 𝑥𝑗= 𝛼, dove 𝛼 è frazionaria e genera due sottoproblemi aggiungendo i vincoli 𝑥𝑗≤ ⌊𝛼⌋, 𝑥𝑗≥ ⌈𝛼⌉. La strategia usata è la l/h first.
KNAPSACK
Il problema è esprimibile come 𝑧 = max{∑𝑛𝑗=1𝑝𝑗𝑥𝑗: ∑𝑛𝑗=1𝑤𝑗𝑥𝑗≤ 𝑐, 𝑥𝑗∈ {0,1}, 𝑗 = 1 … 𝑛 }. Viene usato il rilassamento continuo, la strategia deep first e viene usata una branching rule associa un oggetto (gli oggetti sono ordinati in base al rapporto valore/peso non crescente) ad ogni livello e in quel livello si decide se prenderlo o meno, e al livello j 𝑥𝑗 valrà 1 per generare il problema di sinistra, 0 per generare il problema di destra.
Il rilassamento continuo prende il nome di bound di Dantzig, e inizia ordinando gli elementi per rapporto non
crescente 𝑝𝑗/𝑤𝑗, e si va a cercare l’elemento critico (indice s) tale che ∑𝑠−1𝑗=1𝑤𝑗≤ 𝑐, ∑𝑠𝑗=1𝑤𝑗> 𝑐, per poi selezionare gli elementi interi 1…s-1 e la frazione di elementi s che va a saturare la capacità, ovvero 𝑥𝑗= 1, 𝑗 = 1 … 𝑠 − 1, 𝑥𝑠= (𝑐 − ∑𝑠−1𝑗=1𝑤𝑗)/𝑤𝑠. Si ha che l’upper bound è 𝑈𝐵 = ∑𝑠−1𝑗=1𝑝𝑗+ 𝑝𝑠𝑥𝑠, se 𝑝𝑗 sono interi allora 𝑈𝐵 = ∑𝑠−1𝑗=1𝑝𝑗+ ⌊𝑝𝑠𝑥𝑠⌋, valore che non potrà mai essere superato dalla soluzione. Si procede ad applicare l’upper bound con la regola di branching scelta (il calcolo dell’UB va fatto solo se potrebbe essere diverso dall’UB del problema padre), e si indica per ogni sottoproblema esplorato la capacità residua 𝑐. Se la capacità residua è insufficiente per gli elementi successivi, l’esplorazione viene interrotta.
VANTAGGI E LIMITI DEI METODI DEI PIANI DI TAGLIO E B&B
• Piani di taglio
o Dopo poche iterazioni, generalmente, viene prodotto un buon bound o Dopo una fase iniziale la convergenza potrebbe risultare lenta o Finché non si ha finito, non è disponibile una soluzione
• B&B
o Produce soluzioni accettabili dalle prime iterazioni
o Anche se ha già trovato la soluzione ottimale, potrebbe volerci tempo per esplorare tutti i branch per provarne l’ottimalità della soluzione
Una strategia alternativa è la Branch and Cut, che cerca di combinare i vantaggi dei piani di taglio con quelli della B&B, che usa un metodo dei piani di taglio troncato per calcolare dei buoni bounds (aggiunge un numero limitato di piani di taglio senza aver bisogno di calcolare una soluzione intera e usa diversi tagli nel nodo radice e altri ancora nei
problemi intermedi) e impiega anche una strategia di branching per separare il problema corrente quando l’elaborazione del bound è terminata.
back=true while back do
level-- if level == 0
break i=active(l);
if UB(Pi)>zS e lastChild(l)<getNumCh(Pi) back=false
endif endwhile endwhile
