Domande orale Ricerca operativa

II

Fase simplesso?

I =

La Fase dell’algoritmo del simplesso determina se il problema in forma standard

I

}

{ : = , ≥ , ∈ ℝ

è compatibile. In tal caso individua una base ammissibile e

, … ,

pone il problema in forma canonica. A tale scopo si introducono m variabili artificiali (una

1

per ogni vincolo) e si definisce il problema ausiliario (sempre in forma di minimo):

(, )

= + ⋯ +

1

+ =

≥ 0 , ≥ 0

≥

è una base e quindi il problema non è vuoto e si pone facilmente in forma canonica

sostituendo le variabili nella f.o. Il problema non è illimitato: è un problema di minimo con tutti

coefficienti della f.o. positivi e variabili vincolate in segno.

Il problema ausiliario può essere risolto applicando la Fase II del metodo del simplesso.

}

= { : = 0 , ≥ 0, ∈ ℝ

[Teorema] Il problema è compatibile se e solo se il valore

∗ ∗ ∗

( )

, = 0.

della soluzione ottima del problema ausiliario è

[Dim] ∗

= 0 ⇒

1. è compatibile (ha una soluzione ammissibile): ≥ 0,

Dato che la f.o. del problema ausiliario è la somma delle variabili artificiali e che

∗ ∗ ∗ ∗ ∗ ∗

= 0 = 0. + = = .

allora se e solo se Segue che Quindi è una

.

soluzione ammissibile per

∗

⇒ = 0:

2. è compatibile ∗

> 0.

Supponiamo per assurdo che esista una soluzione ammissibile di e che Se è

(, 0) = 0.

ammissibile per allora è una soluzione del problema ausiliario con valore Ma

∗

> 0

allora non è il valore ottimo.

∗ ∗ ∗

= 0 ,

Se allora è una soluzione ammissibile per non è detto tuttavia che sia una SBA.

Fase II simplesso?

.

Sia una base ammissibile e il problema posto in forma canonica rispetto a

[Algoritmo del simplesso] (massimo/minimo)

−1

= − . ≤ 0 ≥ 0),

1. [Ottimalità] Esamina il vettore dei costi ridotti Se ( la

−1

[

= , 0]

soluzione è ottima. Fine

> 0 < 0)

2. [Variabile entrante] Scegli un tale che (

−1

≤ 0,

3. [Illimitatezza] Se allora il problema è illimitato. Fine

−1 −1

( ) ( )

∕ > 0. ℎ

4. [Variabile uscente] Calcola per ogni riga con Sia l’indice di

ⅈ ℎ-esima

riga che realizza il minimo rapporto. è la colonna entrante in base e la colonna di

è quella uscente −1

( ) ℎ-esima

5. [Aggiornamento] Esegui il pivot su : aggiungi ad ogni riga un multiplo della

ℎ

riga in modo da trasformare nel versore .

ℎ

6. Torna al punto 1

Criterio di ottimalità?

−1 −1

[

= , 0] − ≤ 0

[Teorema] Sia una base ammissibile e la corrispondente SBA. Se

= 1, … , ,

per ogni allora è ottima

[Dim]

−1 −1

( )

= + −

La funzione obiettivo del problema ridotto è:

−1

− ≤ 0, =

Se la soluzione ottima del problema ridotto si ottiene banalmente ponendo

−1

0. =

Il valore ottimo è che coincide con il valore assunto dalla funzione obiettivo in

.

corrispondenza di Segue che è una soluzione ottima.

[Osservazione] Il teorema fornisce un criterio sufficiente ma non necessario: può esistere una SBA

ottima degenere, (Ad una soluzione di base ammissibile possono corrispondere più matrici di base.

In questo caso si parla di soluzione di base ammissibile degenere. Una SBA degenere associata ad

-esima).

una base ha almeno una componente nulla (per esempio la La stessa SBA, quindi,

-esima

può essere contenuta da una qualsiasi nuova base B’ diversa nella colonna. Infatti, il pivot su

−1 −1

( )

, = 0.

un elemento lascia invariato il ettore soluzione essendo Una SBA degenere

= , −

soddisfa all’uguaglianza più di vincoli: le m equazioni del sistema le restrizioni sulle

variabili non in base e le restrizioni sulle variabili in base con valore nullo. Si parla di SBA degeneri

perché alcuni cambi di base non comportano un effettivo cambio di vertice) in corrispondenza della

quale uno o più costi ridotti delle variabili fuori base sono positivi.

• −1

− ≤ 0

Se allora è ottima

• −1

− ≤ 0

Se è ottima e non degenere allora

Criterio Illimitatezza? −1

[

= , 0] −

[Teorema] Sia una base ammissibile e la corrispondente SBA. Se esiste un con

−1 −1

( )

> 0 ≤ 0

e (cioè se esiste una colonna fuori base con costo ridotto positivo e

coefficienti tutti non positivi), allora il problema è illimitato superiormente.

[Dim]

Si applica direttamente il teorema fondamentale della PL. Facciamo cioè vedere che se esiste un

−1 −1

( )

− > 0 ≤ 0 > 0

con e allora esiste una direzione di recessione d con e

quindi, per il teorema citato, il problema è illimitato

Consideriamo il problema ridotto senza le variabili di slack :

−1

( )

: −

−1 1

=

≥ 0

− −1

( )

{

∈ ℝ , ∈ ∈ ℝ | ≤

E facciamo vedere che il versore è una direzione di cioè

−1 −1

( ) ( )

0} = ≤ 0. > 0,

Infatti, che per ipotesi è Inoltre, infatti:

−1 −1

( )

= − = − > 0

che per ipotesi è

Diseguaglianza valida?

(, ) {

ℎ ≤ = ∈ ℝ : ≤ } ⊆ ℝ

è una disuguaglianza valida per un poliedro se

(, ) (, )

{

⊆ ∈ ℝ : ℎ ≤ }. ℎ ≤

Una disuguaglianza valida per è soddisfatta da ogni

(, )

ℎ ≤ <

punto di , quindi aggiungendo al sistema di (dis)equazioni che definisce

(, )

, l’insieme delle soluzioni del sistema non cambia.

ℎ ≤

[Teorema] Ogni disuguaglianza ottenuta come combinazione conica dei vettori riga della

(, )

[|]

matrice estesa è una disuguaglianza valida per .

[Dim]

ℎ = ∑ = ∑ ≥ 0, ℎ = ∑ ≤ ∑ = ∈

e con per ogni

Sostituendo una parte o tutti i vincoli di un problema di PL con una o più disuguaglianze valide si

ottiene un rilassamento del problema.

Dal problema primale al problema duale?

= { | ≤ }

Ad ogni problema di programmazione lineare detto problema primale,

può sempre essere associato un altro problema di PL, detto problema duale, che gode di alcune

proprietà e che in generale è utile per:

• Stimare l’errore commesso quando si considera una qualsiasi soluzione ammissibile in luogo

di una ottima

• Analizzare la stabilità/sensitività delle soluzioni

• Stabilire condizioni di ottimalità e quindi progettare algoritmi esatti

Il miglior bound duale:

• Variabili: coefficienti della combinazione conica dei vincoli del problema

• Vincoli: la combinazione conica deve dominare la funzione obiettivo termine a termine

• Funzione obiettivo: minimizzare il termine noto della combinazione conica

Il problema duale di un problema di PL (detto problema primale) consiste nel determinare i

coefficienti che, tra tutte le disuguaglianze valide (cioè le combinazioni coniche di vincoli) che

,

dominano la funzione obiettivo di corrispondono a quella che produce il miglior bound duale.

Il problema duale non è un rilassamento di P. Il problema duale può essere interpretato come

()

problema di scelta ottimale di parametri di una classe di rilassamenti di che si ottengono

con la tecnica dei moltiplicatori di Lagrange. Il metodo dei moltiplicatori di Lagrange è alla base della

soluzione dei problemi di ottimizzazione non lineare vincolati.

[Metodo dei moltiplicatori di Lagrange] Il vincolo può essere violato ma ad un certo prezzo.

PRIMALE min DUALE (D) max PRIMALE max DUALE min

(P) (P) (D)

Coeff. di Termini Coeff. di Termini

costo noti costo noti

Termini Coeff. di Termini Coeff. di

noti costo noti costo

≥ ≥0 ≥ ≤0

Vincoli Variabili Vincoli Variabili

≤ ≤0 ≤ ≥0

= =

Libera Libera

≤ ≥

≥0 ≥0

Variabili Vincoli Variabili Vincoli

≥ ≤

≤0 ≤0

= =

Libera Libera

Coeff. Coeff. Coeff. Coeff.

( ) ( )

( ) ( )

× ×

× ×

Dualità debole? &isi