Appunti completi corso Ricerca operativa

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