Appunti Fondamenti di ricerca operativa

SCELTA DELLA VARIABILE USCENTE E DELLA VARIABILE ENTRANTE

̂ < 0,

Se in una SBA ci sono più coe0icienti di costo ridotto negativi bisogna decidere quale indice j scegliere

*

per entrare in base. Tra le possibili regole segnaliamo:

̂ < 0

1. Si sceglie il più piccolo indice j per cui * ̂

2. Si sceglie l’indice j corrispondente al valore più piccolo (discesa più rapida)

* ∗

̂

3. Si sceglie l’indice j corrispondente al valore più piccolo (massima diminuzione della f.o.)

*

4. Si sceglie l’indice j a caso (4̅

(4̅ !∗

∗ $

= min µ : < 0, ℎ ∈ ℬ¶ =

Se ci sono più indici i* per cui si può scegliere l’indice i* che deve uscire

B

@ @ !∗

$

dalla base ad esempio prendendo:

1. Il più piccolo indice i* che realizza il minimo

2. Un indice i* a caso tra quelli che realizzano il minimo

Robert Bland ha proposto di usare sempre la regola (1.) (detta regola di Bland) ed ha dimostrato che in questo

modo non ci potranno mai essere dei cicli nell’algoritmo del simplesso e quindi si avrà sempre la terminazione

dell’algoritmo in un numero finito di iterazioni in una SBA con tutti i coe0icienti di costo ridotto non negativi.

Teorema: la Fase II del metodo del simplesso, equipaggiata con la regola di Bland, termina in un numero finito di

iterazioni

Teorema: e il problema di PL ammette soluzione ottima allora esiste una SBA a cui corrisponde un vettore di

coe0icienti di costo ridotto con componenti ≥ 0 ⇒

Dimostrazione: per ipotesi, esiste soluzione ottima Teorema fondamentale della PL implica che esistono una

⇒

SBA e una SBA soluzione ottima. Esistenza di una SBA può partire Fase II del metodo del simplesso. Finitezza

⇒

del metodo trova una SBA in cui uno dei due criteri è soddisfatto. Il problema ammette soluzione ottima per

ipotesi, quindi non è illimitato inferiormente, quindi il metodo si ferma perché ha trovato una SBA che soddisfa il

criterio di ottimalità.

Teorema: dato un problema di PL, una ed una sola delle seguenti evenienze può verificarsi:

(i) il problema ha insieme ammissibile vuoto;

(ii) il problema ammette soluzione ottima;

(iii) il problema è illimitato inferiormente ⇒

Dimostrazione: una asserzione esclude le altre due. Se il problema non ha insieme ammissibile vuoto

⇒

Teorema fondamentale della PL implica che esiste una SBA. Esistenza di una SBA può partire Fase II del

⇒

metodo del simplesso. Finitezza del metodo trova una SBA in cui uno dei due criteri è soddisfatto, i.e.,

• quello dell’ottimalità, e quindi il problema ammette soluzione ottima

• quello dell’illimitatezza, e quindi il problema è illimitato inferiormente

Osservazione – Teorema: dato un problema di PL, una ed una sola delle seguenti evenienze può verificarsi:

(i) il problema ha insieme ammissibile vuoto;

(ii) il problema ammette soluzione ottima;

(iii) il problema è illimitato inferiormente

È una peculiarità della Programmazione Lineare. Si pensi al problema non lineare in una variabile min e , x≥0.

-x

Insieme ammissibile non vuoto, funzione obiettivo limitata inferiormente su R e quindi, a maggior ragione

sull’insieme ammissibile, ma il problema non ammette soluzione.

ALGORITMO DEL SIMPLESSO: Fase I

Stabilisce se l’insieme ammissibile è vuoto oppure no; nel caso in cui non sia vuoto, fornisce una SBA

• viene costruito un problema di PL ausiliario aggiungendo m variabili artificiali e definendo una

opportuna funzione obiettivo

• il problema ausiliario ammette soluzione ottima e la sua struttura `e tale che `e immediatamente

disponibile una SBA per esso (vettore in n + m variabili)

• si applica la Fase II al problema ausiliario e, in un numero finito di iterazioni, si arriva ad una soluzione

ottima dello stesso problema, con cui si può stabilire che il problema originario ha insieme

ammissibile vuoto oppure no;

• nel caso in cui la conclusione sia che il problema originario ha insieme ammissibile non vuoto, dalla

soluzione ottima del problema artificiale `e possibile ricavare una SBA per il problema originario

Scriviamo il problema ausiliario in forma esplicita La funzione obbiettivo è data dalla somma delle

variabili artificiali che sono vincolate ad essere

≥ 0, allora il valore della funzione obbiettivo,

calcolata in qualsiasi punto ammissibile, è

maggiore o uguale a zero.

Esempio:

Abbiamo detto che in corrispondenza di un qualsiasi punto ammissibile il valore della funzione obiettivo è

maggiore o uguale a zero. Esiste almeno un punto ammissibile del problema ausiliario? Sì, ricordando che b ≥ 0

̅ 0

= ̅ + · = 0 + =

Punto ammissibile (in n + m variabili) del problema ausiliario Infatti risulta

• • • •.

·

̅ ≥ 0, · = ≥ 0.

con

• Insieme ammissibile non vuoto

• Il problema non è illimitato inferiormente ∗

⇒ essendo problema di PL ammette soluzione ottima a cui corrisponde il valore della funzione obbiettivo

• •

∗

∗ $ ∗

= 1 ≥ 0. ∗ $ ∗ ∗

= 1 = 0,

Teorema: il problema originario ha insieme ammissibile non vuoto se e solo se dove è il valore

ottimo della funzione obbiettivo del problema ausiliario. ∗

⇒

Dimostrazione: z* = 0 problema originario con insieme ammissibile non vuoto. Sia (x* ) soluzione ottima del

T

∗ $ ∗ ∗

= 1 = 0 ⇒

problema ausiliario = 0 perché ha tutte le componenti non negative.

⇒ Ax* + I0 = b, x* ≥ 0 ⇒ x*

(x* 0) ammissibile per il problema ausiliario ammissibile per il problema originario.

T ∗

= 0,

Teorema: il problema originario ha insieme ammissibile non vuoto se e solo se z* = 1 dove z* è il valore

T

ottimo della funzione obiettivo del problema ausiliario. $

(̅ )

⇒

Dimostrazione: problema originario con insieme ammissibile non vuoto z* = 0. Sia una soluzione

$ $

(̅ (̅

̅ = , ̅ ≥ 0. ·) = 0)

ammissibile del problema originario, i.e., Il punto è ammissibile per il problema

$

̅ + 0 = , ̅ ≥ 0, · = 0 ̅1 · = 0.

ausiliario, infatti e risulta $ $

(̅ (̅

·) = 0)

Ricordando che z ≥ 0, possiamo concludere che il punto è soluzione ottima del problema

ausiliario a cui corrisponde il valore ottimo.

Vogliamo risolvere il problema per calcolare z* e stabilire se l’insieme ammissibile del problema originario è

vuoto oppure no. Possiamo applicare la Fase II del metodo del simplesso al problema ausiliario?

Per poterla applicare abbiamo bisogno di una SBA del problema ausiliario la cui matrice dei coe0icienti del

sistema lineare è (A I). Sappiamo individuare una matrice di base A ?

B

Prendiamo come matrice di base A la matrice I associata alle variabili artificiali α allora:

B

- variabili artificiali α in base;

- variabili originarie x fuori base 0 0 0

̅ % % %

= ” • = ” • =

Soluzione di Base del problema ausiliario è anche una SBA per il problema

• • • •

(!

· (!

5

ausiliario perché, senza perdita di generalità, stiamo supponendo b ≥ 0.

0

̅ %

=

A partire dalla SBA possiamo applicare la fase II del metodo del simplesso ottenendo una SBA

• • • •

·

∗ ∗ $ ∗

= 1 ≥ 0.

ottima (x* ) per il problema ausiliario a cui corrisponde un valore della funzione obbiettivo

T ∗

∗ $ ∗

= 1 ≥ 0.

SBA ottima per il problema ausiliario a cui corrisponde il valore della funzione obbiettivo

• •

∗

-Se z* > 0 possiamo concludere che il problema originario ha insieme ammissibile vuoto, stop.

-Se z* = 0 l’insieme del problema originario è non vuoto e dobbiamo individuare una SBA per lo stesso problema

5

̅ = • •

0

%(&

∗

∗

= 0.

SBA ottima per il problema ausiliario con z* = 0 allora

• •

∗

∗

= 0

1) e tutte le variabili artificiali sono uscite dalla base

∗

= 0

2) ma alcune variabili artificiali sono rimaste in base

(!

5∗

5

∗

∗

= =

Nel caso 1) e quindi è immediatamente disponibile per il problema originario la SBA

• • < = >

0 ?

%(&

∗ 6

0

∗

&

(!

5 5

̅ = •= ” •.

•

0 0

%(& %(&

Nel caso 2), i.e., α* = 0 ma alcune variabili artificiali sono rimaste in base, siamo in presenza di una SBA

⇒

degenere per il problema ausiliario operazione di pivot virtuale per provare a far uscire le variabili artificiali

rimaste in base e a far entrare le variabili originarie.

In e0etti, nel caso 2) individuiamo una soluzione di base ammissibile del problema originario, ma il numero di

componenti di x* maggiori di zero è minore di m. L'operazione di pivot virtuale permette di individuare un insieme

di indici i di colonne corrispondenti a x *= 0 che permette di completare una base insieme agli indici con x *> 0.

i i

CONVESSITA’ DELLE SOLUZIONI OTTIME E PROBLEMI CON INFINITE SOLUZIONI

Supponiamo di aver trovato una SBA che verifica la condizione su0iciente di ottimalità e vogliamo sapere se

esistono altre soluzioni ottime. Anzitutto dimostriamo che se ci sono due soluzioni ottime distinte, allora tutto il

segmento che le collega è composto da soluzioni ottime. ∗ $ %

{

= min , = ∈ : = , ≥ 0}

Teorema: se x e x sono punti di minimo globale del problema allora

1 2 ! " % ! "

[ ] { (1 [0,1]}

, = ∈ : = + − ) , ∈

tutti i pinti del segmento sono punti di minimo globale del

*

problema. Questo significa che l’insieme delle soluzioni ottime è convesso.

! " $ $ ! $ " ∗

(1

= + − ) ∈ = = =

Dimostrazione: dato bisogna dimostrare che (i) e che (ii) .

! &quo