Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Concetti geometrici che ci serviranno per la programmazione lineare. Gli insiemi S sono

n

sottoinsiemi di R (e i punti sono vettori).

INSIEME CONVESSO = per ogni x, y in S e per ogni valore di λ in [0, 1] si ha che λx + (1

– λ)y appartiene a S (ovvero presi due punti nell’insieme, tutti i punti sul segmento che li

unisce appartengono ad esso, quella è detta COMBINAZIONE CONVESSA).

Geometricamente l’insieme di tutte le combinazioni convesse di due punti forma il

segmento che li congiunge. P = {x : A x ≤ b | i = 1...m}

i i

POLIEDRO CONVESSO = è una generalizzazione dell’insieme convesso, in cui l’insieme

è definito da un set di rette (quindi ottieni un insieme infinito oppure limitato, il politopo)

Un poliedro S si può chiamare:

CONO = se per ogni punto x del cono e per ogni valore λ positivo, allora anche λx

appartiene all’insieme. In pratica è una semiretta.

CONO CONVESSO = per ogni x, y in S e per ogni valore positivo di λ e μ, hai che λx + μy

appartiene anch’esso a S. Geometricamente è quello che chiameresti proprio cono: due

semirette che si incrociano all’origine e consideri il cono generato da essi.

CONO POLIEDRO = è un caso particolare di poliedro convesso dove b vale sempre 0

i

P = {x : A x ≤ 0 | i = 1...m}

i

CONO FINITAMENTE GENERATO = se esiste un insieme di punti (qualsiasi) x e un

insieme di λ tale per cui ogni punto di S è la sommatoria di λx

Consideriamo l’insieme P = {x : A x ≤ b | i = 1...m}

i i

Un punto x di P è un PUNTO ESTREMO se non esistono due punti y e z di P (diversi da

x) tali per cui x = λy + (1 – λ)z (quindi è un punto che non è combinazione di nessun altro

punto a parte se stesso, infatti se crei un segmento che parte da un vertice ti serve per

forza un secondo punto)

Una definizione alternativa dice che un punto x di P è un VERTICE se esiste un punto

qualsiasi c tale per cui cx > cy per qualsiasi punto y di P. In pratica esiste un iperpiano

passante per x che lo separa dal resto della regione di accettabilità.

Queste due definizioni non sono applicabili in un algoritmo. La terza definizione invece

dice che x* è una BASIC SOLUTION di P se tra tutti i vettori A con i che rappresenta i

i

vincoli in cui A x* = b (detti VINCOLI ATTIVI) ce ne sono n tra loro linearmente

i i

indipendenti. Il sistema formato da essi ha quindi un’unica soluzione che è il punto

cercato. Un vertice si ha perciò nell’intersezione tra n vettori linearmente indipendenti, in

quanto identificano un punto univocamente.

Se abbiamo un poliedro P, ogni punto in esso può essere espresso come somma di due

punti appartenenti ad un politopo Q e un cono poliedro C per cui P = Q + C

Gli elementi del politopo formano i PUNTI del poliedro, mentre gli elementi del cono

formano le DIREZIONI del poliedro. Ricorda che la somma di punti equivale alla somma di

vettori. Questo porta ad un teorema interessante: se un problema di massimo ha

soluzione finita, essa è uno dei punti del politopo.

Dato un insieme convesso S e un punto c fuori da esso, esiste un iperpiano che li divide o

meglio un punto x tale che cx > zx per ogni z in S, abbastanza intuitivo.

Per ogni problema di massimo, esiste un duale di minimo e viceversa. Come esempio

prendiamo il problema dei polli: abbiamo due tipi di mangime A e B che forniscono una

certa quantità di carboidrati, vitamine e proteine. I polli devono ricevere ogni giorno una

quantità minima di ogni sostanza e i mangimi hanno un costo. Dobbiamo decidere quanto

mangime prendere di un tipo e quanto dell’altro per minimizzare i costi. Modellare questo

problema è facile e non c’è nulla di strano.

Di questo problema esiste un duale che è quello del venditore delle pillole: ovvero quello

che ha i polli può comprare i mangimi, ma potrebbe anche comprare singolarmente delle

pillole di carboidrati, di vitamine e proteine. Il venditore di pillole deve quindi assegnare un

prezzo in modo da essere competitivo. Le variabili di decisione quindi sono i prezzi delle

tre pillole. Scrivendo questo modello in pratica usiamo esattamente gli stessi numeri ma li

mettiamo in posti diversi.

Chiamiamo allora A la matrice con le quantità di sostanze, b il vettore con la quantità

minima di carboidrati, vitamine, proteine, c il vettore con i costi, x le variabili del primo

problema e y le variabili del secondo problema. Il primo modello è

min cx

Ax ≥ b

x ≥ 0

Mentre il secondo è:

max yb

Ay ≤ c

y ≥ 0

Un altro problema simile è quello in cui abbiamo n fabbriche che producono qualcosa ed

m magazzini che richiedono parte della produzione. Trasportare il prodotto da una certa

fabbrica ad un altro magazzino ha un costo di trasporto b . La quantità prodotta dalle

ij

fabbriche e quella richiesta dai magazzini coincidono. È un problema di flusso a costo

minimo, perché fabbriche e magazzini producono e assorbono flusso, ma ogni arco ha un

costo. Dal punto di vista dei proprietari delle fabbriche e dei magazzini è un problema di

minimo (minimizzare il costo). La decisione x è quanto trasportare dalla fabbrica i al

ij

magazzino j, l’obiettivo è minimizzare il costo b x e i vincoli sono che la somma degli x

ij ij ij

deve coincidere con la domanda e con l’offerta.

Il duale è invece dal punto di vista delle compagnie di trasporto, che comprano dalle

fabbriche e vendono ai magazzini, quindi per loro è un problema di massimo

(massimizzare il profitto). Offrono un prezzo d’acquisto λ per ogni fabbrica e un prezzo di

i

vendita μ per ogni magazzino. Il loro scopo è massimizzare il guadagno ed essere più

j

competitivi del trasporto diretto.

Modello dal punto di vista dei proprietari delle fabbriche e dei magazzini

L’obiettivo è minimizzare la sommatoria su b x (dove b è il costo dell’arco)

ij ij ij

I vincoli sono che x deve essere positivo e la sommatoria degli x deve coincidere con

ij ij

l’offerta (e anche la domanda, che coincidono)

Modello dal punto di vista della società di trasporto:

Le variabili di decisione sono λ che indica la spesa per comprare il prodotto dalle

i

fabbriche e μ che indica il prezzo di vendita ai magazzini.

j

L’obiettivo è massimizzare il profitto, quindi la somma dei λ meno la somma dei μ

i j

Il vincolo è che μ - λ ≤ b altrimenti il guadagno se ne va nella spesa del trasporto.

j i ij

Chiamiamo b il vettore dei costi di trasporto, c il vettore con domanda e offerta, i due

problemi si presentano così:

min xb max cy

xA = c Ay ≤ b

x ≥ 0 y ≥ 0

A differenza di prima abbiamo che il problema di partenza contiene delle equazioni ma è

sempre un problema di minimo. Il duale come problema di massimo è in forma di minore o

uguale.

In pratica i due problemi (che chiamiamo PRIMAL e DUAL) possono essere SIMMETRICI

se entrambi fanno uso di disequazioni, oppure ASIMMETRICI se uno dei due fa uso di

equazioni. Per ottenere il duale di un problema, basta seguire una procedura automatica

riassumibile con questa tabella. Ricorda anche che il duale del duale è il primale.

max min

Variabili Vincoli

Vincoli Variabili

Vettore dei costi c Vettore dei termini noti b

Vettore dei termini noti b Vettore dei costi c

Ax ≥ b y ≤ 0

Ax ≤ b y ≥ 0

Ax = b y unbounded

x ≥ 0 yA ≥ c

x ≤ 0 yA ≤ c

x unbounded yA = c

Dati due problemi duali con soluzioni ammissibili x e y, vale che cx ≤ yb

Inoltre, se si verifica il caso che cx = yb allora x e y sono le soluzioni ottime. Questo è il

TEOREMA DI DUALITÀ DEBOLE.

Ne consegue che se il primale ha come valore ottimo una variabile infinita senza limite,

allora il duale non ha soluzione (perché fissando una soluzione per il duale fissi anche un

limite per il primale).

Il duale ha una sua interpretazione geometrica particolare, ovvero esprimiamo il vettore

dei costi c come combinazione lineare dei gradienti del primale (cioè le righe di A). è così

che si capisce che il duale ci dà informazioni sulla soluzione ottima del primale.

Cerchiamo di trovare un algoritmo per determinare la soluzione ottima partendo da una

soluzione possibile. Cerchiamo di risolvere un problema LP del tipo

max cx min yb

Ax ≤ b yA = c

y ≥ 0

Se x* è una soluzione possibile ma esiste una soluzione migliore x’, vuol dire che essa si

può ottenere da x* come x’ = x* + λξ dove λ è uno scalare positivo chiamato

n

DISPLACEMENT STEP mentre ξ è un vettore di R chiamato DISPLACEMENT

DIRECTION. Quindi se esiste questo vettore ξ tale per cui cx’ > cx* allora x* non è la

soluzione ottima, altrimenti lo è. In pratica è come se prendessimo un punto su un poliedro

e ci spostassimo in una certa direzione finché ci troviamo dentro i confini di questo

poliedro. Formalmente quindi una soluzione fattibile x* è migliorabile se e solo se esistono

questi valori λ > 0 e ξ tali che:

c(x* + λξ) > cx* = è migliore

A(x* + λξ) ≤ b = è ammissibile

Da queste disequazioni si ottengono queste condizioni sul valore del vettore ξ. Per la

seconda condizione si considerano i soli vincoli attivi dato che rappresentano delle

direzioni in cui non possiamo spostarci. Se non ci fosse nessun vincolo attivo allora

qualsiasi direzione sarebbe accettabile perché non usciremmo dalla regione di

ammissibilità. Si ottiene che una soluzione è ottimale se NON esiste una soluzione per

questo sistema:

cξ > 0

A ξ ≤ 0

I

Questo ha senso geometricamente: cξ rappresenta la direzione in cui il vettore c cresce,

mentre A ξ è un cono poliedro in cui qualsiasi vettore è accettabile. Comunque data una

I

soluzione possibile x, scegliamo una direzione ξ in base ai vincoli attivi presenti (quindi

una direzione che rispetti A ξ ≤ 0) mentre possiamo calcolare λ dalla disequazione A(x +

i

λξ) ≤ b e viene fuori che si deve avere

λ ≤ (b - A x*)/A ξ per ogni vincolo inattivo tale che A ξ > 0

i i i

In pratica diventa chiaro che trovare una soluzione ottima significa scegliere una direzione

(se esiste) insieme al fattore di scala. Cerchiamo quindi un algoritmo per trovare questi

valori (la direzione deve rispettare delle disequazioni ma la soluzione non è affatto univoca

in quel sistema!) e qui entra in scena il duale. Bisogna trovare la soluzione a questo

sistema chiamato RESTRICTED PRIMAL P’. È il problema associato alle due

disequazioni sopra, in cui l’aumento della funzione obiettivo è l’obiettivo stesso e i vincoli

sono i vincoli attivi del problema iniziale.

max cξ

A ξ ≤ 0

I

Di questo problema possiamo costruire il suo duale RESTRICTED DUAL D’ così

min η0

ηA = c

I

η ≥ 0

ovvero ha la particolarità che il vettore dei termini noti è sempre zero, per cui non ha senso

trovare la funzione obiettivo (si tratta quindi di un problema di fattibilità). Per quanto

riguarda il primale, è da notare che se abbiamo una soluzione ξ tale che cξ > 0, allora

esso ha ottimo non limitato, perché posso moltiplicare ξ per un qualsiasi scalare positivo.

Siccome poi il vettore dei termini noti è uguale a zero, la soluzione ξ = 0 è sempre

ammissibile. Come conseguenza del teorema di dualità debole, che conosci bene, si

possono avere due situazioni:

- Se D’ ha soluzione, allora P’ ha come soluzione ottima ξ = 0

- Se P’ ha ottimo non limitato, D’ non ha soluzione

Da questo abbiamo delle premesse per costruire un algoritmo che risolva i problemi di

programmazione lineare: partiamo da una soluzione fattibile, troviamo una direzione in cui

spostarci aumentando la funzione obiettivo e un fattore di scala per rimanere dentro i

vincoli. Un teorema che è conseguenza delle premesse date dice che se il restricted dual

ha soluzione, allora la nostra soluzione x è quella ottima per il problema di partenza. Ciò è

dimostrato dal FARKAS LEMMA che dice esattamente che o P’ ha soluzione illimitata

(quindi esiste una direzione di crescita) o D’ ammette soluzione (quindi abbiamo la

soluzione ottima), in modo esclusivo.

cξ > 0 ηA = c

I

A ξ ≤ 0 η ≥ 0

I

La dimostrazione è complicata ma spiega perché il risultato di un LP dipende

dall’esistenza della soluzione o meno nel primal.

Manca ancora il punto fondamentale: se D’ ha soluzione abbiamo finito, ma se non ha

soluzione dobbiamo scegliere uno dei tanti valori possibili per ξ Considerando il caso

semplice in cui la matrice A sia quadrata e di rango massimo, possiamo calcolarne

I I-1

l’inversa e nel D’ dal sistema dei vincoli ηA = c possiamo ricavare η = cA che avrà una

I

soluzione univoca. Chiamiamo questa soluzione η’: se essa è composta da soli valori non

negativi siamo nel caso in cui D’ ha soluzione ammissibile e quindi la soluzione x del

problema di partenza è ottima. Se invece contiene componenti negative, creiamo un

vettore u che vale 1 in corrispondenza DI UNA SOLA componente negativa di η’ e 0

h

altrove. La direzione che scegliamo sarà quella che risolve il sistema A ξ = -u o, con la

I h

I-1

matrice inversa, ξ = -A u . Con dei calcoli algebrici si può dimostrare facilmente che

h

questa soluzione è ammissibile per P’ e incrementa la funzione obiettivo. Dobbiamo però

vedere cosa succede nel caso, ben più frequente, in cui la matrice A non ammette

I

inversa. Se la matrice A ha meno righe che colonne, è in realtà ancora più semplice. Qui

I

ηA = c può non avere soluzioni perché ci sono più equazioni che variabili, come possiamo

I

costruire ξ? Siccome in P’ abbiamo delle disequazioni, il modo più semplice è trasformarle

in equazioni, per esempio così

cξ = 1

A ξ = 0

Ι

Risolvendo questo sistema troviamo sicuramente una direzione ammissibile. È più

complicato se la matrice A ha più righe che colonne...

I

Adesso abbiamo tutti gli strumenti per presentare un algoritmo funzionante nella

risoluzione di problemi di PL. Si chiama PRIMAL-DUAL SIMPLEX: i parametri sono i

vettori del problema A b c, la soluzione iniziale x, il flag unbounded, la soluzione iniziale

del duale y. La procedura modifica le variabili x, optimal, unbounded e y. La funzione

grow_along modifica x, I e unbounded.

optimal = false

unbounded = false

I = vincoli attivi in x

if I = Ø // se non siamo ai confini del poliedro

grow_along(c, x, I, unbounded) // usiamo c come direzione

while not optimal and not unbounded // finché non troviamo la soluzione

dual = {ηA = c}

I

if dual non ha una soluzione

ξ = soluzione di A ξ = 0 e cξ = 1 // calcolo ξ

I

grow_along(ξ, x, I, unbounded) // cresco verso quella direzione

else if dual ha soluzione con un h tale che η[h] < 0

ξ = soluzione di A ξ = -u[h] // u[i] vale 1 se i = h altrimenti 0

I

grow_along(ξ, x, I, unbounded)

else // il dual ha una soluzione ammissibile

optimal = true

y[i] = η[i] se i in I altrimenti 0

La funzione grow_along ha come parametri una direzione ξ, una posizione iniziale x, la

lista dei vincoli attivi I, un flag unbounded. Questi ultimi tre parametri vengono aggiornati

con la nuova posizione.

λ = min{(b - A x)/A ξ}

i i i

if λ = infinito

unbounded = true

else x = x + λξ

I = nuovi vincoli attivi in x

Aspetti da notare sono che:

- All’inizio se non ci sono vincoli attivi la miglior direzione è quella del gradiente c, dato che

indica dove la funzione obiettivo cresce

- Si distinguono i casi in cui il restricted dual non ha soluzione, ha soluzione con

componenti negative e ha soluzione con sole componenti positive

- Nel caso in cui la matrice A sia quadrata, il restricted dual avrà sicuramente una

soluzione analitica. Se questa contiene componenti negative non è ammissibile, per cui

possiamo trovare una direzione ξ. Se invece la soluzione ha sole componenti positive,

abbiamo trovato la soluzione ottima del problema di partenza. È interessante notare che il

restricted primal è un problema LP su coni: in questi casi si ha che la soluzione o è

illimitata oppure è nell’origine. È esattamente ciò che dice il Farkas Lemma ma si vede

anche geometricamente!

- Se la matrice A ha meno righe che colonne, si verifica o che il sistema non ha proprio

soluzione, oppure ne ha una che può avere o meno componenti negative. In questo caso

si usa il metodo presentato precedentemente.

- Se la matrice A ha più righe che colonne, mi sembra di aver capito che ci riconduciamo al

caso di matrice quadrata considerando solo le equazioni tra loro indipendenti.

Il TEOREMA DI DUALITÀ FORTE dice che, dati due problemi duali P e D nella forma

vista finora, x e y sono soluzioni ottimali SE E SOLO SE cx = yb

Un altro modo, più geometrico, per verificare se una soluzione è ottima, è controllare se il

gradiente del vettore dei costi si trova all’interno del cono generato dai gradienti dei vincoli

attivi. Se il vettore dei costi è dentro il cono allora quella soluzione è ottima, e viceversa.

Non abbiamo affrontato però il problema della soluzione iniziale. Non basta partire sempre

da zero? Eh no… Quella va bene se hai un problema nella forma ≤ b e tutti i valori di b

sono positivi. Costruiamo allora un PROBLEMA AUSILIARIO per trovare una generica

soluzione. Dividiamo i vincoli in due gruppi: quelli che hanno b ≥ 0 e quelli con b < 0, li

chiamiamo J e J

+ -

Per ogni vincolo con b < 0 creiamo una variabile v positiva: il problema ausiliario ha come

j

obiettivo max(-sum[j in J ](v )) (l’obiettivo è scoraggiarne l’uso visto che la funzione è

- j

limitata superiormente dal valore zero). I vincoli diventano A x ≤ b e A x - v ≤ b

J+ J+ J- J- J-

tenendo conto che -v ≤ 0

J-

Con questa formulazione, una soluzione di partenza sicuramente fattibile per il problema

ausiliario è mettere x = 0 e v = b I-

A questo punto, data la soluzione iniziale, cerchiamo la soluzione ottima con l’algoritmo

che abbiamo visto e otterremo le soluzioni ottime (x, v). Avrai due casi:

- Se v è diverso da zero, il problema originario NON HA SOLUZIONE

- Se invece v è uguale a zero, x è una soluzione possibile per il problema di partenza (e

questo si verifica banalmente perché se v è uguale a zero hai un’istanza del problema

iniziale)

Ne consegue che per risolvere un problema LP con il metodo dei simplessi bisogna far

girare quell’algoritmo due volte, quindi è un metodo A DUE FASI.

Ora l’ultima parte sulla programmazione lineare: COMPLEMENTARY SLACKNESS.

Continuiamo a considerare una coppia asimmetrica di problemi primal-dual dove il primal

è un massimo.

Date due soluzioni x e y per i problemi P e D, queste tre proprietà sono equivalenti:

x e y sono soluzioni ottime

cx = yb

y(b - Ax) = 0

Quest’ultima proprietà implica cose molto interessanti… Cioè c’è una relazione tra le

soluzioni del primal e quelle del dual:

- Se b = Ax allora y > 0

- Se b > Ax allora y = 0

In pratica quando la soluzione dei dual è positiva, nel primal abbiamo un’equazione (cioè

siamo su un vincolo attivo), mentre se nel primal abbiamo una disequazione stretta la

variabile associata nel dual è zero. Quindi usando il dual puoi verificare se una soluzione

proposta per il primal è ottima o meno. Guardi per ogni vincolo se soddisfa una equazione

o una disequazione stretta: da ciò determini nel dual quali variabili sono nulle e quali sono

positive. Considerando il sistema con le sole variabili strettamente positive, controlli che la

soluzione del dual sia effettivamente composta da soli valori positivi (ovvero ammissibile, o

che in generale la soluzione ottenuta rispetti i vincoli del problema).

Questa è la definizione con due problemi asimmetrici, cioè quelli visti finora. Vediamo

invece con un problema simmetrico cosa succede.

max cx min yb

Ax ≤ b yA ≥ c

x ≥ 0 y ≥ 0

Le condizioni del complementary slackness diventano

y(b - Ax) = 0

(c - yA)x = 0

Le implicazioni diventano simmetriche nei due problemi. Si aggiunge un’equazione in più

perché nel dual abbiamo delle disequazioni e non delle equazioni, per cui data una

soluzione esiste uno “scarto” che invece è nullo nel caso delle equazioni.

Questa proprietà ha interessanti implicazioni economiche. Ricordi alla prima lezione nel

problema dei telefoni che non potevamo rispondere alla domanda “compreresti un pezzo

in più di questo tipo?” Ora puoi rispondere. Se consideri il problema asimmetrico, il vettore

b indica le risorse a disposizione, mentre le variabili x indicano delle attività su cui

distribuire le risorse e l’obiettivo è massimizzare il profitto. In pratica si scopre una cosa

fantastica… Se modifichiamo le risorse, la soluzione del duale non cambia (perché non

modifichi i suoi vincoli) però cambi il valore della funzione obiettivo nel primale. La

soluzione del duale in realtà ti dice quali sono le risorse da aumentare affinché aumenti il

valore della funzione obiettivo! O meglio per ogni risorsa ti dice di quanto aumenta il valore

della funzione obiettivo incrementando di una unità quella risorsa. E qui ha senso perché

l’incremento esiste per le risorse dei vincoli attivi della soluzione ottima (che sono

equazioni), mentre per le altre risorse, che restano disuguaglianze strette, la variabile

associata nel duale è nulla.

La complementary slackness permette anche di sapere se la nostra soluzione rimane

ottima a fronte di variazioni sul vettore dei costi c. Assumiamo che quel vettore venga

sostituito con un nuovo vettore c’ in cui alcuni suoi componenti sono parametrici.

Risolvendo il duale otteniamo una soluzione y parametrica: siccome ogni elemento di y,

affinché la soluzione sia ottima, deve essere positivo, possiamo identificare un range per il

valore assunto dal parametro. Quel range indica i valori del vettore dei costi affinché la

soluzione x del primale rimanga quella ottima. Esiste anche un’interpretazione geometrica:

sai che una soluzione è ottima se il gradiente c è all’interno del cono generato dai gradienti

dei vincoli attivi. Disegnando un segmento che attraversa questi gradienti compreso il

vettore dei costi ottieni il range parametrico.

Data una coppia asimmetrica di problemi P e D, possiamo ricavare dalla matrice A una

sua sottomatrice quadrata e con equazioni linearmente indipendenti, quindi una matrice

invertibile. La chiamiamo A . Possiamo ricavare due soluzioni x e y tali che

B

B-1

x = A b

B B-1

y = (y , y ) dove y = cA e y = 0

B N B N

Queste sono dette SOLUZIONI DI BASE e possono essere:

AMMISSIBILE A x ≤ b y ≥ 0

N N B

NON AMMISSIBILE Esiste j in N tale che A x > b Esiste j in B tale che y < 0

j j j

DEGENERE Esiste j in N tale che A x = b Esiste j in B tale che y = 0

j j j

NON DEGENERE Per ogni j in N vale A x != b Per ogni j in B vale y != 0

j j j

Una matrice di base è detta -1B

MATRICE DI BASE PRIMALE AMMISSIBILE se b - A A b ≥ 0

N N B

-1B

MATRICE DI BASE DUALE AMMISSIBILE se cA ≥ 0

In qualche modo viene fuori che se x [y] è soluzione ottima e A è la matrice di base

B

-1B -1B

corrispondente, allora si verifica che cA ≥ 0 [b - A A b ≥ 0]

N N B

Peccato solo che non ho capito a che cavolo serve sto discorso delle basi. Ok usando

termini più comprensibili vuol dire che abbiamo un altro metodo per capire se una

soluzione x è ottima. Consideriamo una BASE B, cioè un insieme di colonne della matrice

A tali per cui la matrice è quadrata non singolare e la chiamiamo A . Calcoliamo due

B

B-1 B-1

soluzioni x e y dove x = A b e y = c A . Se la soluzione x è ammissibile allora B sarà

B B

una BASE PRIMALE AMMISSIBILE mentre se la y è ammissibile B sarà una BASE

DUALE AMMISSIBILE. Se entrambe le soluzioni sono ammissibili allora sono ottime.

Qui abbiamo a che fare con problemi di programmazione lineare in cui però le variabili

devono assumere valori INTERI (o anche binari, e ne abbiamo visti di problemi così –

questi sono i cosiddetti problemi di ottimizzazione combinatoria). La regione di

ammissibilità non è più un’area, ma un insieme di punti: solo quelli sono le possibili

soluzioni. Perdiamo delle proprietà, tra cui il fatto che la soluzione ottima sia sui vertici o

su una faccia, ma soprattutto perdiamo la CONVESSITÀ, che è il motore della LP.. Se

prendiamo due punti e li uniamo con un segmento, i punti in mezzo non sono più soluzioni

ammissibili. Tutta la LP si basava su questo: il nostro mondo crolla, e come se non

bastasse la maggior parte dei problemi reali sono di questi tipo e più difficili darisolvere

rispetto ai problemi continui.

Beh noi cosa facciamo? Ignoriamo l’integralità, cerchiamo la soluzione e la approssimiamo

ad un intero. Si chiama RILASSAMENTO LINEARE. Ma la effettiva soluzione ottima qual

è? Però con la ILP possiamo modellare problemi che non sono convessi. Prendi due

problemi LP che hanno come regione possibile due triangoli che si intersecano e da soli

sono convessi, ma uniti no. In LP hai due problemi distinti: se li metti insieme però non hai

l’unione dei due triangoli, ma la loro intersezione perché i vincoli sono in AND. Per

ottenere l’OR si usa un trucco… introduciamo una variabile binaria y e un valore M

abbastanza grande che permette di includere la regione di ammissibilità dell’altro

problema. Nell’LP risultante unisci le due equazioni ma aggiungi un termine che in una

equazione è My e nell’altra è M(1 – y). Così facendo se y è 1 un’equazione aggiunge M e

l’altra no, e il contrario se y vale 0 così puoi unire i due vincoli in uno solo in OR. Qui

abbiamo usato una sola variabile per due vincoli, ma un altro modo è usare n generiche

variabili binarie (e valori M) su n vincoli, e poi per evitare che più vincoli siano attivi

contemporaneamente basta aggiungere altre condizioni del tipo y + y < 2

1 2

Riprendiamo il famoso problema di scheduling di lavori su una pipeline. Abbiamo n task da

svolgere su m macchine in sequenza. Ogni task viene eseguito per intero e l’obiettivo è

minimizzare il tempo di completamento dell’ultima macchina. Dobbiamo assegnare l’ordine

con cui eseguire i task (quindi una sequenza). Il tempo d’esecuzione del task j sulla

macchina k è s mentre le variabili di decisione sono t cioè quando il task j inizia sulla

jk jk

macchina k. Ovviamente un task non può iniziare su una macchina se quella precedente

non ha ancora terminato, quindi il vincolo è t + s ≤ t

jk jk jk+1

Per indicare che dobbiamo minimizzare il tempo di fine introduciamo una variabile T e

inseriamo come vincolo t + s ≤ T e la funzione obiettivo è min(T). Il vincolo mancante è

jm jm

che una macchina non può lavorare su due task contemporaneamente: cioè per ogni

macchina k e coppia di task i e j, o prima fa i e poi j, oppure fa prima j e poi i cioè

t + s ≤ t

ik ik jk

t + s ≤ t

jk jk ik

Questi due vincoli devono essere esclusivi… allora introduci una variabile binaria y che

ijk

vale 1 se i viene prima di j sulla macchina k, 0 altrimenti. Aggiungi anche un valore M

molto grande e ottieni

t + s ≤ t + M(1 - y )

ik ik jk ijk

t + s ≤ t + M(y )

jk jk ik ijk

Un altro fenomeno ricorrente è quello di una funzione obiettivo non lineare, però lineare a

tratti, cioè in cui cambia il coefficiente angolare in vari intervalli. Facciamo il vecchio

esempio delle linee telefoniche: il prezzo dello scatto di una telefonata dipende da quanti

ne hai fatti. Per i primi 140 sono 50 lire, dal 141-esimo al 220 sono 207 lire e dal 221-

esimo in poi sono 127 lire. Se vogliamo minimizzare la spesa in base al numero di scatti,

creiamo tre variabili che indicano il numero di scatti consumati in ognuno dei tre intervalli

z z z ma serve anche garantire la sequenzialità. Per questo sono utili tre variabili logiche

0 1 2

y y y che valgono 1 se l’intervallo è partito o meno. La funzione obiettivo diventa

0 1 2

min(b y + 50z + 207z + 127z ) dove b è un costo fisso. Per i vincoli come facciamo?

0 0 0 1 2 0

Innanzitutto vincolare le singole variabili logiche è molto facile perché conosci la formula

dell’implicazione. Tuttavia bisogna fare in modo che se un intervallo non è consumato

allora la z vale 0, se un intervallo è consumato quelli precedenti devono avere z con il

valore massimo, mentre se un intervallo è consumato e non ce ne sono di consumati dopo

il valore di z deve essere compreso tra 0 e il massimo numero di scatti. Beh ti sei dato la

risposta da solo.

140y ≤ z ≤ 140y

1 0 0

80y ≤ z ≤ 80y

2 1 1

0 ≤ z ≤ My

2 2

Un problema di grande rilevanza è la scelta di sottoinsiemi. In pratica abbiamo un insieme

di elementi J e un insieme F di sottoinsiemi di J che hanno un costo. Lo scopo è scegliere

dei sottoinsiemi D di F tale che:

- Ogni elemento in J appartenga ad almeno un insieme di D (COPERTURA)

- Ogni elemento in J appartenga ad esattamente un insieme di D (PARTIZIONE)

- Ogni elemento in J appartenga ad al più un insieme di D (RIEMPIMENTO)

Molti problemi di reti logiche erano di questo tipo se ti ricordi. Ma per esempio anche un

problema di turnazione del personale è un problema di partizione. L’insieme I è dato dai

voli, i sottoinsiemi F sono i voli che ogni pilota è in grado di effettuare e il costo di ogni

sottoinsieme è la paga da dare al pilota. Questo è un problema di partizione dato che si

vuole dare un volo ad ogni pilota. Si può rappresentare l’insieme dei sottoinsiemi con una

matrice F tale che f indica se l’insieme i contiene l’elemento j. Le variabili di decisione

ij

sono delle d che valgono 1 se il sottoinsieme i appartiene alla soluzione. I prolemi si

i

formulano quindi come:

- Copertura: sum(i in F)[f *d ] ≥ 1 per ogni j in J

ij i

- Partizione: sum(i in F)[f *d ] = 1 per ogni j in J

ij i

- Riempimento: sum(i in F)[f *d ] ≤ 1 per ogni j in J

ij i

Altro problema frequente è quello delle frequenze: dobbiamo assegnare delle frequenze

alle antenne in modo che non interferiscano tra loro ma bisogna utilizzarne il meno

possibile. Serve una variabile logica y per ogni frequenza che dice se è usata o meno e

h

per ogni antenna un set di variabili x che dicono se la frequenza h è usata sull’antenna i.

ih

Lo scopo del problema è trovare il min(sum(y )), poi si indica che per ogni antenna i la

h

sum(x ) = 1 in modo che ogni antenna abbia una frequenza assegnata e per garantire

ih

l’assenza di interferenze si dice che per ogni coppia adiacente di nodi (i, j) deve valere che

x + x ≤ 1. Questo non è altro che il famoso problema della COLORAZIONE!

ih jh

Ora riguardo la risoluzione dei problemi ILP: la formulazione del problema è decisiva per

definire la complessità del problema risultante. In pratica risolvere il problema come se

fosse LP e approssimare la soluzione non per forza ti dà l’ottimo… Già approssimare la

soluzione a una che sia ammissibile non è facile, e per di più non è per forza ottima! Se

invece trovi una definizione del problema in cui tutti i vertici coincidono con delle

coordinate intere, risolvere il problema LP diventa esattamente uguale a risolvere il

problema ILP!

Ma non è tutto così semplice: per ottenere questa formulazione possono servire una

quantità esponenziale di vincoli…

Una matrice A è detta UNIMODULARE se ogni sua sottomatrice non singolare di rango

massimo ha determinante uguale a +1 o -1.

Una matrice A è detta TOTALMENTE UNIMODULARE se ogni sua sottomatrice non

singolare ha determinante uguale a +1 o -1. Di conseguenza la matrice contiene solo i

numeri 0, 1 e -1.

Queste matrici sono importanti perché appaiono spesso (tutti i problemi sui grafi hanno le

matrici fatte così) e hanno proprietà interessanti. Diciamo che una matrice è TU se:

- Ogni colonna ha al massimo due elementi non nulli

- Le righe si possono partizionare in due insiemi tali per cui se una colonna ha due numeri

dello stesso segno, le righe contenenti questi numeri appartengono a due insiemi diversi,

mentre se due colonne hanno numeri di segno opposto, le due righe che li contengono

appartengono allo stesso insieme.

Da questo si ottiene che se A e b hanno componenti intere e A è unimodulare, tutte le

soluzioni di base del problema

min cx

AX = b

x ≥ 0

hanno componenti intere.

Inoltre se A è totalmente unimodulare, i problemi

min cx min cx

Ax ≥ b Ax ≤ b

x ≥ 0 x ≤ 0

hanno tutti soluzioni di base a componenti intere.

Se vogliamo ottenere il problema PLI partendo da quello PL, dobbiamo affinare il modello

facendo in modo che la soluzione ottima intera si trovi su un vertice della regione di

ammissibilità. Dato il problema intero P, definiamo quello senza l’interezza della soluzione

P’ e la sua soluzione ottima come x’. Se hai che x’ è intero, è soluzione anche per P.

Una DISUGUAGLIANZA VALIDA è un vincolo del tipo gx ≤ γ tale per cui vale che gx ≤ γ

per ogni x intero che soddisfa i vincoli Ax ≤ b. Vuol dire che è un vincolo che al massimo

restringe la regione di ammissibilità nel problema continuo ma non di quello discreto. Un

PIANO DI TAGLIO è una disuguaglianza valida gx ≤ γ tale per cui gx’ > γ ovvero che

rende inammissibile la soluzione ottima del problema continuo.

Vuol dire che possiamo trovare la soluzione intera generando nuovi vincoli con i piani di

taglio finché la soluzione sarà intera. L’algoritmo quindi segue questi passi:

ottimo = false

while not ottimo:

solve(P’, x’)

if x’ è intero:

ottimo = true

else: generate_cut(g, γ)

add_cut(P’, g, γ)

Il punto quindi è come generare questo taglio. Uno di questi metodi è quello di CHVÁTAL

in cui dato un insieme di vincoli, per ognuno di essi scegliamo un coefficiente reale

positivo u e aggiungiamo un nuovo vincolo del tipo floor(sum(u *A ))x ≤ floor(sum(u *b ))

i i ij i i

Questa formula è valida perché la combinazione lineare non negativa di disuguaglianze

valide è ancora valida e possiamo usare il floor a sinistra e a destra per ottenere

coefficienti interi senza perdere la validità. Ciò che si ottiene è una disuguaglianza valida

che restringe il numero di soluzioni ammesse finché l’ottimo sarà una soluzione intera.

Questo metodo però non basta perché genera disuguaglianze valide ma non dei tagli (non

è un metodo costruttivo, perché di fatto non ti dice i valori di questo vettore u). Per trovare

i tagli si usa il metodo di GOMORY che però fa uso delle soluzioni di base e non di base…

Vabbè assumiamo di avere un problema in cui i vincoli sono delle equazioni del tipo Ax = b

(quindi può essere necessario aggiungere variabili di slack) e nel problema continuo

abbiamo una soluzione ottima x’ fatta dalle due componenti x’ e x’ . Se x’ ha tutte

B N B

componenti intere allora abbiamo la soluzione per il problema intero, altrimenti calcoliamo

B-1 B-1

la matrice A A (che indichiamo semplicemente con a) e un vettore x’ = A A b : per

N N B

ogni componente frazionaria di questo vettore, generiamo un’equazione del tipo x’ +

h

sum(j in N)[a *x ] ≤ b dove t è il vincolo corrispondente alla componente h del sistema. In

tj j t

pratica se x’ è la prima variabile quella sommatoria contiene i coefficienti della prima riga

h

di a moltiplicati per le variabili non basiche mentre la componente a destra è proprio il

valore di x’ nella soluzione. Poi da quella equazione consideri i floor di ogni coefficiente e

h

ottieni una disequazione valida che è anche un taglio. Se in queste disequazioni

compaiono variabili di slack, le si sostituiscono in funzione delle sole variabili effettive del

problema. Adesso ho finalmente capito qualcosa ed è molto interessante.

L’altra famiglia di metodi risolutivi è quella che fa uso di metodi enumerativi, ovvero scorro

tutte le soluzioni possibili e prendo quella con la miglior funzione obiettivo. Naturalmente

alla base c’è un albero di decisione che cresce esponenzialmente e per rendere la ricerca

più efficiente si usano stratagemmi simili a quelli usati nei problemi di ricerca

dell’intelligenza artificiale (tipo i CSP) per escludere varie scelte a priori. Per esempio:

- ENUMERAZIONE IMPLICITA: capire che hai violato un vincolo prima di aver assegnato

tutte le variabili, in modo da interrompere la visita di quel branch anzitempo

- SOVRASTIMARE: si fa una sovrastima della possibile soluzione che si può trovare nel

branch corrente. Se è peggiore della migliore soluzione trovata finora, è inutile proseguire.

Si parla di sovrastima se l’obiettivo è massimizzare, ma possiamo anche sottostimare nel

caso di problemi di minimo.

Questo non è altro che il BRANCH & BOUND e si può esprimere così: dati in input il

(sotto)problema di massimizzazione P ed una soluzione ammissibile v (quella trovata

finora). L’algoritmo è ricorsivo: ogni nodo dell’albero di ricerca è un sottoproblema.

Branch&Bound(P, v)

# calcola limite superiore e una possibile soluzione vera

b = upper_bound(P, x, infeasible)

if x è intero # la soluzione x è già l’ottimo

return b

else if infeasible # il problema non ha soluzione: è inutile proseguire

return -inf

else if b > v # la stima prevista migliora la soluzione nota

Per ogni sottoalbero P in Branch(P, x)

i

t = Branch&Bound(P v)

i

v = max(t, v)

Per un buon branch and bound bisogna quindi definire:

- Il calcolo dell’upper bound

- Il metodo di partizionamento

- L’ordine di visita dei sottoalberi

Per il bound esistono vari metodi di RILASSAMENTO, che consistono nel trasformare

vincoli “complicati” in vincoli più semplici da trattare che danno una stima per eccesso

della soluzione (sovrastimano i vincoli e la funzione obiettivo). Se questa stima per

eccesso rispetta i vincoli originali, allora è una soluzione ammissibile ed è pure ottima! Se

non li rispetta è comunque un limite superiore per la soluzione ottima del problema vero.

Ci sono vari tipi di rilassamento: quello semplice che abbiamo già visto è l’eliminazione del

vincolo di integralità delle variabili. È il RILASSAMENTO LINEARE, che è notoriamente

più facile da risolvere, e se la soluzione è intera allora vale anche per il problema intero.

Oppure possiamo rimuovere altri vincoli che danno più libertà alle variabili (l’eliminazione

di vincoli è una generalizzazione del rilassamento lineare). Altri rilassamenti curiosi sono

la COMBINAZIONE LINEARE DI VINCOLI già esistenti: anche questo permette di

espandere le soluzioni ammissibili e renderle più facili da trovare. Infine esiste il

RILASSAMENTO LAGRANGIANO che penalizza alcuni vincoli nella funzione obiettivo: è

una tecnica avanzata. Nel nostro corso useremo solo il rilassamento lineare.

Manca solo la scelta con cui visitare l’albero. Negli esempi più semplici ad ogni livello

dell’albero si assegna una certa variabile e il sottoproblema è assegnare quelle rimanenti,

come nei CSP. Ma non per forza un livello deve corrispondere sempre alla stessa

variabile, così come l’ordine degli assegnamenti non per forza deve essere statico. Se

abbiamo una soluzione per il problema continuo in cui una variabile è intera, essa va già

bene per noi e non ha molto senso sceglierla. Se invece la soluzione continua ha

componenti frazionarie, è meglio scegliere quella variabile come prossimo livello e

cerchiamo di renderla intera. Come si fa? Metti caso che la soluzione continua x ha un

valore frazionario f. Generi due sottoproblemi: uno in cui aggiungi il vincolo che x ≤ floor(f)

e l’altro in cui x ≥ ceil(f). Questo si chiama BRANCHING BIPARTITO ed è anche

semplificato nel caso di variabili binarie: in un problema x assume il valore fissato 0 e

nell’altro il valore fissato 1. Più in generale, se una variabile può assumere un range

limitato di valori (per esempio da 1 a k) anziché creare due sottoproblemi, crei k

sottoproblemi, ognuno nei quali x assume un valore fissato. Questo è BRANCHING K-

PARTITO ed è molto simile ai CSP.

Oggi parliamo della COMPLESSITÀ COMPUTAZIONALE: abbiamo risolto tanti problemi,

per alcuni abbiamo trovato algoritmi efficienti (shortest path, simplex algorithm, maximum

flow…) mentre per altri non abbiamo trovato algoritmi veloci (programmazione intera,

TSP…). Possiamo classificare i problemi in base all’efficienza degli algoritmi? Avoja…

Possiamo dividere i problemi “facili” da quelli “difficili” in base alla polinomialità. Un

problema è facile da risolvere se esiste un algoritmo polinomiale che lo risolve. Tuttavia

non possiamo dimostrare che un problema è difficile semplicemente perché non troviamo

un algoritmo polinomiale. Il fatto che troviamo un algoritmo efficiente è una prova, ma non

trovarlo non ci dice nulla sulla sua inesistenza.

Un problema è una domanda espressa in termini astratti la cui risposta dipende da un

insieme di parametri. Una istanza di un problema è un assegnamento dei parametri in

input. Un algoritmo è un insieme FINITO di istruzioni che, applicato a QUALSIASI istanza

di un problema, fornisce in un numero FINITO di passi una risposta al problema (o dà una

soluzione o dice che la soluzione non esiste).

Esistono vari modelli computazionali che, anche se diversi tra loro, possono simulare

qualsiasi computer reale (come la TURING MACHINE o la RANDOM ACCESS

MACHINE) e assumono di avere risorse infinite. Per misurare la complessità di un

algoritmo, ci serve sapere il numero di operazioni svolte per risolvere il problema. Per

coprire tutte le istanze del problema, si considera sempre il caso peggiore. Inoltre la

complessità si misura in funzione della dimensione dell’input. Alla fine però si usa la

notazione O grande, cioè si misura la complessità con l’input che tende all’infinito: quello

che conta è il ritmo di crescita della funzione, eliminando costanti moltiplicative e funzioni

additive di ordine inferiore. Sai già matematicamente la definizione di O grande.

Chiamiamo PROBLEMI DI DECISIONE quelli in cui la risposta è SÌ o NO. Esiste

qualcosa? Esiste un percorso nel grafo? Posso assegnare tutti i task alle macchine

soddisfacendo i vincoli temporali? Diciamo sì o no, non ottimizziamo niente. Oppure il

famoso SAT: esiste un assegnamento alle variabili booleane tale per cui il SAT è vero? Per

i problemi di ottimizzazione, aggiungiamo un parametro k e il problema diventa “esiste

un percorso con una lunghezza minore o uguale a k”? Esiste un insieme di beni per cui

porti a casa almeno k bitcoin? Se si riesce a risolvere efficientemente il problema

decisionale, si risolve anche quello di ottimizzazione.

La prima classe di problemi che vediamo è quella NP che sta per NONDETERMINISTIC

POLYNOMIAL. Un problema è NP se:

- È in forma decisionale

- Possiamo verificare la validità di una qualsiasi soluzione proposta in tempo polinomiale

Esiste un insieme di beni per cui porti a casa almeno k bitcoin? Ti do un insieme di beni e

in un attimo puoi dire se la soluzione proposta va bene o no.

Dentro NP c’è la classe P che sta per POLYNOMIAL. Sono i problemi che non solo

verifichi in tempo polinomiale, ma li risolvi anche in tempo polinomiale. Inoltre puoi

rispondere anche alla versione “negativa” del problema, cioè per esempio dire che non

esiste un percorso tra due punti in un grafo.

Il fatto che P sia contenuto strettamente in NP oppure è uguale ad NP non è dimostrato e

se lo dimostri vinci un milione di dollari e rivoluzionerai la storia dell’umanità. Quindi non

sappiamo se l’insieme NP \ P esiste, o meglio non sappiamo definire le caratteristiche di

un problema che sta in NP ma non in P.

All’inizio del corso il prof diceva che il SAT è la madre di tutti i problemi. Vediamo ora il

perché. Esiste un assegnamento che rende vero un insieme di clausole? Sicuramente sta

in NP perché verificarlo si fa subito, ma in P mi sa proprio di no: ha complessità

esponenziale se non usi delle euristiche.

Dato questo problema del SAT, proviamo (e possiamo) ridurre qualsiasi problema in NP a

questo problema. Significa che se io so risolvere efficientemente il SAT, allora so risolvere

efficientemente QUALSIASI problema in NP, anche quelli non ancora definiti. Dobbiamo

però definire cosa significa “ridurre” un problema in un altro. Un problema P è riducibile a

Q se posso risolvere in tempo polinomiale P utilizzando Q come sottoprogramma

ipotizzando che quest’ultimo abbia complessità costante. Quindi se abbiamo un algoritmo

efficiente per risolvere Q, possiamo dire che P appartiene a P. Se non esiste un algoritmo

efficiente per P (in teoria non si può dire) allora Q non appartiene a P. A quanto pare

questo problema Q è proprio il SAT. Ma infatti se ci pensi qualsiasi problema di

programmazione intera è un SAT, ma in realtà TUTTI i problemi sono riconducibili al SAT!

Da ingegnere informatico dovresti leggerti la dimostrazione perché è assai importante. Se i

problemi li esprimi come visita di un grafo di una Turing Machine ha più che senso (la

dimostrazione che SAT è NP-completo è il teorema di Cook-Levin ed è per temerari…

mostra come ogni problema si riconduca in tempo polinomiale ad una formula logica). Per

SAT comunque si intende qualsiasi formula logica, in genere la congiunzione di

disgiunzioni (seconda forma canonica): la prima forma canonica è facile da risolvere così

come il caso particolare del 2-SAT.

Da questo otteniamo la classe NP-COMPLETE, composto da problemi che:

- Sono in NP

- Qualsiasi problema in NP è riconducibile ad essi

Ciò vuol dire che se riesci a risolvere efficientemente un problema NP-completo, allora sai

risolvere efficientemente qualsiasi problema in NP e quindi dimostri che P = NP.

La riduzione è una proprietà transitiva, quindi partendo da un problema notoriamente NP-

completo come il SAT puoi ricavare altri problemi NP-completi.

Se un problema ha come caso particolare un problema NP-completo, allora esso è

almeno difficile quanto i problemi NP-completi e forma la classe dei problemi NP-HARD. I

problemi NP-hard nonostante il nome potrebbero non appartenere ad NP: ad essi quindi

appartengono i problemi di ottimo (non decisionali), infatti per questi verificare una

soluzione equivale a risolvere il problema.


ACQUISTATO

1 volte

PAGINE

37

PESO

787.40 KB

AUTORE

fiorixf2

PUBBLICATO

8 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica (COMO - CREMONA - MILANO)
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Ricerca operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Malucelli Federico.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica (como - cremona - milano)

Guida per la programmazione in C
Dispensa
Esercizi sulla programmazione in C
Esercitazione
Architettura dei calcolatori e sistemi operativi - Appunti
Appunto
Livello di linea
Appunto