Problema del trasporto - Ricerca operativa

DIMOSTRAZIONE

Condizione Necessaria→ ( è

è ),

Visto che la regione ammissibile è non vuota, è possibile sommare il primo set di vincoli (per

fare ciò si me e la sommatoria a sinistra e a destra):

=

∈ ∈ ∈

Si esegue lo stesso ragionamento per il secondo set di vincoli:

=

∈ ∈ ∈

Il membro sinistro delle due espressioni è uguale, e quindi:

=

∈ ∈

Condizione Sufficiente→ è ,

(è

è )

Si parte da una soluzione ammissibile della seguente forma:

= ∑

∈

Verifichiamo se è proprio ammissibile e quindi andiamo a sos tuire nei set di vincoli.

 Per il primo set di vincoli: = ∀ ∈

∈ ∑

∈

= → ∙ =

∑ ∑

∈ ∈

∈

Siccome si è ipo zzato che: =

∈ ∈

Segue: ∑ ∑

∈ ∈

∙ = → ∙ = → =

∑ ∑

∈ ∈

 Per il secondo set di vincoli: = ∀ ∈

∈ ∑

∈

= → ∙ =

∑ ∑

∈ ∈

∈

RICONDUZIONE MODELLO IN FORMA STANDARD

Il problema, per come è stato definito, è riportato in forma standard (vincoli di uguaglianza

e variabili non nega ve). Si cercherà di ricondursi sempre a questa forma perché, in tal

modo, vi si potrà sempre applicare il metodo del simplesso su re :

min () =

( , )∈

. . = ∀ ∈

∈ = ∀ ∈

∈

≥ 0 ∀(, ) ∈

Se il primo set di vincoli dovesse apparire in questa forma:

≤ ∀ ∈

∈

Nella formulazione standard viene espresso che tu o il flusso che il nodo ha a disposizione

lo offre.

In realtà l’offerta è un upper-bound su ciò che il nodo può offrire, quindi ci sta che il

vincolo possa anche essere di disuguaglianza (se la disponibilità complessiva è tale che

)

∑ ≥∑

∈ ∈

Per la riconduzione alla forma standard si u lizzerà una variabile di slack:

+ = ∀ ∈

,

∈

La variabile di slack è un nuovo nodo fi zio in e quindi un nuovo nodo di

,

domanda fi zio (il nodo che avrà domanda:

+ 1) = −

∈ ∈

Il nuovo nodo di domanda fi zio assorbe l’offerta in eccedenza.

Si intuisce che aggiungendo un nodo domanda fi zio si aggiungeranno anche archi di

costo 0.

La stessa cosa vale nel caso in cui si ha un eccesso di domanda: si inserisce un nodo offerta

fi zio tramite variabile di surplus.

RISOLUZIONE CON SIMPLESSO SU RETI

Il problema dei traspor può essere anche rappresentato a raverso una tabella ed è su

questa tabella (forma matriciale) che verranno effe uate le operazioni di pivot applicando il

metodo del simplesso:

1

2

1

2

E’ una tabella di dimensione ×

Le celle con rappresentano il costo sugli archi

Per ogni riga è associato il valore (offerta del nodo origine mentre per ogni

-esimo),

colonna è associato il valore (domanda del nodo des nazione

-esimo).

Nella tabella sono anche evidenzia i flussi sulla rete.

Vediamo un esempio considerando la seguente istanza:

10

15

10

5

10 8

15

7

2

10

3

1 2

10 5 10

1 8 7 10

2 2 3 10

3 15 15

Il problema si risolve con il Metodo del Simplesso su Re , la procedura è sempre la stessa:

avendo una soluzione di base inziale si determinano i coefficien di costo rido o. Per le

variabili fuori base, se esistono coefficien di costo rido o nega vi vuol dire che quella

non è o ma e quindi si fa entrare in base la variabile con coefficiente di costo rido o più

nega vo.

Per il problema del trasporto, il coefficiente di costo rido o ha la seguente forma:

̅ = − − ∈ , ∈

≔

≔

= ∀ ∈ →

∈ = ∀ ∈ →

∈

Il problema duale, infa , avrà la seguente forma:

max (, ) = +

∈ ∈

. . + ≤ ∀(, ) ∈

Data una ed il rela vo insieme di indici di base

:

̅ = − − = 0 ∀(, ) ∈ (∗)

Siccome i coefficien di costo rido o sono necessari per la valutazione dell’o malità o

meno della soluzione, per calcolare tali coefficien sono necessari i valori delle variabili

duali. Quindi, avendo una soluzione del primale, bisogna trovare la soluzione del duale

risolvendo un sistema di equazioni che consiste nell’imposizione dei coefficien di costo

rido o delle variabili in base uguali a zero.

Quante variabili in base ha il problema del trasporto? (Domanda orale)

Nel problema di flusso a costo minimo si hanno vincoli (si hanno nodi) e variabili

− 1

in base (perché la matrice non è a rango pieno, ha rango una riga è linearmente

− 1,

dipendente dalle altre). Una deve essere un albero ricoprente e quindi, avendo nodi,

affinchè sia un albero ricoprente (ovvero una stru ura aciclica e connessa), bisogna avere

almeno archi (almeno perché deve essere connessa) e al più archi (al più

− 1 − 1

perché deve essere aciclica). Siccome il problema del trasporto è un’stanza del problema di

flusso a costo minimo, ci si aspe a che tali ragionamen res no invaria .

Una anche per il problema del trasporto, è un albero e di conseguenza si avranno

, nodi: quindi il sistema avrà equazioni (perché si scrive la

+ − 1 (∗) + − 1

relazione di coefficiente di costo rido o per ogni arco associato alla base); il sistema inoltre

avrà variabili (tante quan sono i nodi della rete, si avranno variabili di ed

+

variabili di ). Dato che si tra a di un sistema con equazioni in

+ − 1 +

variabili, si avranno soluzioni.

∞

Vediamo come svolgere l’operazione di pivot nel problema di trasporto. Consideriamo

l’istanza dell’esempio precedente e si propone la soluzione che viene indicata:

1 2

10 5 10 in Vuota=0=Variabile Nota:

10 base

1 Casella

8 7 10

5 5

2 2 3 10

10

3 15 15

10 15

10

10 5

15

5

10 10

Si può verificare che si tra a di una soluzione ammissibile (si può intuire anche dalla

tabella).

Inoltre, la soluzione (grafo so ostante) è un albero (i nodi sono tu connessi tra di loro e

non ci sono cicli).

In questo caso: + =3+2=5

Il numero di variabili in base sarà: || = 5 − 1 = 4

Supponiamo di aver risolto il sistema per determinare le variabili duali, abbiamo calcolato i

coefficien di costo rido o per le variabili fuori base e risulta che:

̅ <0

Allora entra in base con valore

Si esegue l’operazione di pivot sul grafo; dato che entra in base si inserisce l’arco in blu;

essendo il grafo associato alla un albero, inserendo un arco si forma necessariamente

un ciclo, che avrà un orientamento dato dall’arco associato alla variabile che sta entrando in

base. Quindi:

{(1,2), (2,1)} {(2,2), (1,1)} }

= = = min { } = min{̅ , ̅ = 5

( , )∈

10 15

10

10 5

15

5

10 10

Si ha una nuova soluzione: =5=

= ̅ + = 10

= ̅ − =0

= ̅ − =5

Esce dalla base perché il suo valore coincide con il minimo degli archi appartenen a

Invece di valutare l’esistenza, o comunque la forma del ciclo nel grafo bipar to, lo si può

osservare anche nella tabella.

Par amo dalla cella rela va alla variabile che sta entrando in base, e cioè nella cella di e

si sa che bisogna sommare il flusso. Dopodichè bisogna spostarsi o in senso orizzontale

(sulla stessa riga sia a sinistra che a destra se c’è spazio per spostarsi, in questo caso ci sono

celle solo a sinistra) o in senso ver cale (sulla colonna 2 o sopra o so o se c’è spazio, in

questo caso ci sono celle solo di so o). Scegliamo in questo caso il senso ver cale (non

cambia nulla) e ci si ferma nella cella in cui si trova un valore di flusso diverso da 0: ci si

ferma nella cella e la variabile decrementerà il flusso (perché la cella precedente è

(2,2)

+; la successiva sarà -, poi + poi – e così via: ad ogni cella bisogna cambiare segno).

In maniera errata si andrebbe poi giù alla cella ma so o non avrebbe altre celle e a

(3,2)

sinistra non ci sarebbe flusso. Una regola è che ad ogni passaggio bisogna muoversi di

direzione diversa: se si procede ver cal