Appunti Ricerca operativa

POTREBBE CHIEDERE DIMOSTRAZIONE

Questo risultato per variabili continue.

Si dimostra che se lÕalgoritmo del simplesso determina una soluzione ottima per il

Problema Primale, allora lÕalgoritmo fornisce anche una soluzione ottima del

corrispondente Problema Duale.

Teorema della Dualitˆ Forte (riformulato)

Si consideri un Problema Primale in forma standard ed una soluzione ammissibile di base

ottima x = (x = B b,x = 0), dove per la matrice dei vincoli si ha A = [B, D] e per il

vettore dei coefficienti di costo si ha c = c , c . In tal caso il Problema Duale ammette

una soluzione BD ammissibile ottima costituita dai moltiplicatori del simplesso nel vettore

con =c B.

λ, λ

Dimostrazione:

Si dimostra innanzitutto che = c B • una soluzione ammissibile per il Problema

λ

1) Duale.

Dato che la soluzione di base del Problema Primale • ottima, i relativi costi ridotti nel

vettore r = c D sono tutti 0. Ci˜ implica che:

− λ ≥

Si ha che implica che = c B • una

λ

soluzione ammissibile per il Problema Duale.

Si dimostra ora che = c B • anche una soluzione ottima considerando il

λ

2) precedente Corollario 1, in quanto sia x che sono soluzioni ammissibili per i rispettivi

λ

problemi e

Condizioni di complementarietˆ

Esistono delle precise condizioni che legano soluzioni ottime del Problema Primale e del

Problema Duale ( quando esistono).

Tali condizioni sono chiamate condizioni di complementarietˆ.

Si consideri un Problema Primale e il corrispondente Problema Duale (forma simmetrica).

Problema Primale Problema Duale

Le condizioni 1) e 2) si possono rappresentare insieme con i prodotti (λTai =0∀i.

−ci)xi

Le condizioni 3) e 4) si possono rappresentare insieme con i prodotti (aj x bj ) = 0 .

λj − ∀j

Nota: se il Problema Primale • in forma standard, si considerano solo le condizioni 1) e 2).

Esempio

PROGRAMMAZIONE LINEARE METODO DEL SIMPLESSO DUALE

LÕalgoritmo del simplesso duale permette di individuare una soluzione ottima o di stabilire

lÕassenza di soluzioni ammissibili di un problema di programmazione lineare.

LÕidea di fondo dellÕalgoritmo • di partire da una soluzione di base non ammissibile ma

ottima (con costi ridotti non negativi) di un Problema Primale e di esplorare lo spazio delle

soluzioni di base mantenendo lÕammissibilitˆ duale dei corrispondenti moltiplicatori del

simplesso.

In pratica lÕalgoritmo si muove tra soluzioni di base ottime ma non ammissibili del

Problema Primale Þno al possibile raggiungimento di una soluzione di base ammissibile

ed ottima.

Discuteremo lÕapplicazione dellÕalgoritmo del simplesso duale in forma tabellare

considerando i tableau delle soluzioni di base in forma canonica.

Metodo del simplesso in forma tabellare

Prima di trattare lÕalgoritmo del simplesso duale, analizziamo i passi del metodo del

simplesso in forma tabellare, al Þne di illustrare le differenze tra i due algoritmi.

Si consideri un problema di programmazione lineare in forma standard con m vincoli e n

variabili:

Sia data per il problema una

soluzione ammissibile di base

e la relativa forma canonica:

dove: x1,...,xm variabili di base, con x1 = =

β1,...,xm βm,

xm+1,...,xn variabili non di base, con xm+1 = 0,...,xn = 0.

Si aggiunge al corrispondente tableau

una riga relativa alla funzione obiettivo.

La presenza di tale riga si giustiÞca osservando che la funzione obiettivo pu˜ essere vista

come un ulteriore vincolo del problema:

+ c1x1 + c2x2 + . . . cmxm + cm+1xm+1 + á á á + cnxn = 0

−z

con come ulteriore variabile di base (esplicitamente non rappresentata nel tableau) con

−z

valore iniziale di 0.

Riformulando la funzione obiettivo in relazione alla soluzione di base ed ai costi ridotti

rj (j = m+1,...,n) delle variabili non di base, si ha

Per lÕultima riga si ottiene quindi:

In alternativa, lÕaggiornamento

dellÕultima riga del tableau pu˜

essere ottenuto modiÞcando la riga attraverso opportune operazioni con le altre righe in

modo da avere degli zeri (costi ridotti nulli) in corrispondenza delle variabili di basex1Éxm

A partire dal tableau precedente, si applicano i passi dellÕalgoritmo del simplesso

revisionato aggiornando il tableau quando si considera una nuova soluzione di base.

Esempio

Metodo del simplesso duale

Il metodo del simplesso duale si applica nei casi in cui si ha a disposizione una soluzione

di base ottima ma non ammissibile per un Problema Primale.

In tal caso tutti i costi ridotti sono 0 ma esiste almeno una variabile di base che assume

≥

valore negativo.

Questa situazione pu˜ derivare, ad esempio, a seguito di una variazione del vettore dei

termini noti.

Nel tableau della soluzione di base, si ha

la seguente situazione:

LÕidea dellÕalgoritmo • di muoversi tra le

soluzioni di base mantenendo lÕottimalitˆ

primale (data dai costi ridotti non negativi) cercando di ottenere lÕammissibilitˆ primale.

NellÕottica del problema duale, questo signiÞca muoversi verso lÕottimalitˆ duale

mantenendo lÕammissibilitˆ duale (si ricorda che i moltiplicatori del simplesso di una

soluzione di base con costi ridotti 0 costituiscono una soluzione ammissibile del

≥

problema duale).

Simplesso primale : la funzione obiettivo continua a scendere Þno a ottenere lÕottimo

Simplesso duale : la funzione obiettivo aumenta, quindi ÒpeggioraÓ ma diventa

ammissibile perchŽ prima abbiamo una soluzione ottima ma non ammissibile

(ammissibile = tutte variabili maggiori di zero)

Il metodo del simplesso duale ha due risultati possibili:

Determina una soluzione di base ammissibile ed ottima del problema.

1. Evidenzia che il problema non ammette soluzioni ammissibili (implicando, in questo

2. caso, anche lÕillimitatezza del Problema Duale).

Esempio: Per illustrare i passi dellÕalgoritmo del simplesso

duale, consideriamo il seguente problema:

A questo problema corrisponde il seguente tableau

(aggiungendo due variabili di surplus x4 e x5 e

moltiplicando per la parte sinistra e destra

−1

dei vincoli di uguaglianza)

dove si pu˜ facilmente identiÞcare la base [x4,x5] ottima ma non ammissibile.

LÕalgoritmo del simplesso duale sceglie prima la variabile da far uscire dalla base tra

quelle che hanno un valore negativo (nel primale si decide chi esce per trovare

ottimabilitˆ).

NellÕesempio si pu˜ scegliere x4 o x5 (entrambe con valore negativo). Si supponga di

scegliere x4.

Se tutti i coefficienti relativi alla variabile che esce dalla base sono 0, ovvero se

α ≥ αpj ≥

0 = 1,...,n per un certo indice di riga p, allora lÕalgoritmo termina e si pu˜ concludere

∀j

che il problema non ammette soluzioni ammissibili.

In questo caso infatti, visto che xj 0 si avrebbe 0 e lÕequazione

≥ ≥

∀j,

= < 0 non potrebbe mai essere soddisfatta.

βp

Non • il caso dellÕesempio considerato...

Se esiste invece almeno un coefficiente < 0, si effettua un cambio di base scegliendo

αpj

come variabile da far entrare in base la variabile con rapporto minimo (con < 0).

αpj

Ci˜ al Þne di garantire che i costi ridotti della nuova base siano tutti 0 (discutiamo in

≥

seguito, nelle slide 17-18, il motivo per cui tale criterio dÕentrata garantisce la non

negativitˆ dei costi ridotti).

NellÕesempio si determina lÕentrata in base della variabile x3 dal confronto dei rapporti

5/|-1| e 0/|-1| relativi alle variabili x1 e x3, rispettivamente. Si individua quindi il terzo

numero della riga R1 (-1) come elemento di pivot.

Il tableau risultante dal cambio di base (con le operazioni,

in sequenza, R1 = e R2 = R2 4R1) • il seguente:

−R1 −

LÕalgoritmo considera iterativamente una nuova soluzione di base Þno al possibile

raggiungimento di una soluzione ammissibile ed ottima.

NellÕesempio, allÕiterazione successiva esce dalla base la variabile x5 ed entra in base la

variabile x1 (in quanto 5/|-5|<2/|-1|).

Il corrispondente tableau (ottenuto con le operazioni

R2=−R2/5, R1=R1−R2 e R3=R3−5R2) • il seguente:

LÕalgoritmo termina in quanto ora la nuova base ([x3,x1]) risulta essere ammissibile ed

ottima.

Criterio dÕentrata di una variabile in base:

Al Þne di mantenere lÕottimalit‡ primale (ammissibilitˆ duale), • necessario far entrare in

base la variabile con rapporto rj/|α pj| minimo (con <0)

αpj

In particolare, si vuole che dopo lÕaggiornamento della riga del tableau relativa ai costi

ridotti, i nuovi valori dei costi ridotti siano 0.

≥

Si consideri lÕelemento di pivot che determina lÕingresso in base di una certa variabile

αpq

xq.

Dopo lÕaggiornamento della corrispondente riga, i costi ridotti valgono:

Si vuole quindi ottenere che

(dato che < 0),

α ∀j.

- Se 0, lÕultima disuguaglianza • sicuramente veriÞcata in quanto tutti i costi ridotti

αpj ≥

della soluzione di base corrente sono 0.

≥

- Se < 0, allora deve valere implicando

αpj

che la variabile che entra in base deve

avere il rapporto minimo rj/|α pj| per tutti gli < 0.

αpj

Il metodo del simplesso duale si pu˜ riassumere come segue:

Condizioni iniziali: una soluzione di base di un Problema Primale non ammissibile ed

•

ottima (ammissibile duale).

Approccio iterativo:

• Se tutte le variabili hanno un valore 0, STOP la soluzione di base corrente ottima •

≥

1. anche ammissibile;

Altrimenti scambiare (se possibile) una variabile di base con valore negativo con una

2. variabile non di base in modo da ottenere una nuova soluzione di base ottima.

Se lo scambio non • possibile, allora STOP il problema non ammette soluzioni

ammissibili (e il Problema Duale • illimitato);

Altrimenti tornare al passo 1.

3.

Analisi di sensitivitˆ

Due possibili campi di indagine

Analisi di sensibilitˆ rispetto a variazioni dei termini noti.

¥ Analisi di sensibilitˆ rispetto a variazioni dei coeff. di costo.

¥

Analisi di sensibilitˆ rispetto ai termini noti

Perturbando il vettore dei termini noti b del problema iniziale, cambiano, nel tableau

Þnale, solo i termini noti: abbiamo, quindi, una soluzione perturbata ed un nuovo valore

della funzione obiettivo.

Perturbazione dei termini noti -> ammissibilitˆ della soluzione pertu