Relazione PST 2° ESERCITAZIONE SUI MODELLI

6. MODELLO DI ASSEGNAZIONE DI EQUILIBRIO DETERMINISTICO RISOLTO CON UN

MSA ( 0,5%)

ALGORITMO TEST DI ARRESTO

L’ algoritmo MSA è il seguente ,

1 ∙

e sono nulli, ed effettuo il seguente

Si procede partendo da un flusso iniziale, nel nostro caso

ragionamento →→→→

Riprendo l’ lo metto in c e faccio una serie di giri e mi fermo quando tra due iterazioni

coincidono. Nella realtà un’ algoritmo di questo tipo non converge,

successive i valori dell’

quindi quando faccio questo procedimento non devo mettere gli un valore pari alla medi degli

di ogni iterazione e mediante il teorema di Browell dimostro che l’ algoritmo converge.

Partendo dai tempi iniziali ottengo le probabilità e che risultano essere pari o ad 1 o a 0

ricavando cosi ∙ ∙

Per le successive iterazioni prendo gli e calcolando i nuovi e mediante la relazione

1 1

Mentre i costi li ricaviamo sempre dalla BPR e procediamo a calcolare le nuove e ed i

relativi e .

Importante è il test di arresto che si basa sul concetto che mi posso fermare quando ho raggiunto il

messo in (0) mi genera un uguale a quello

punto fisso. Il punto fisso si ha quando l’

generato. Il test di arresto ossia la sequenza si arresta quando la differenza adimensionalizzata tra i

flussi di assegnazione stocastica e la soluzione corrente sono inferiori a una soglia di errore

lim → ℎ

→ 11

C1 C2 Pr 1 Pr 2 F 1 F 2 k test 1 test 2 testmax

DNL DNL

f f

1 2

0 0 10 12 1 0 1076.9 0 0 0

1076.92 0 18.403 12 0 1 0.0 1076.9 1 -1 #DIV/0! #DIV/0!

538.462 538.462 19.370 12.630 0 1 0.0 1076.9 2 -1 1 1

358.974 717.949 19.571 14.727 0 1 0.0 1076.9 3 -1 0.5 0.5

269.231 807.692 19.635 18.642 0 1 0.0 1076.9 4 -1 0.33 0.33

215.385 861.538 19.661 25.059 1 0 1076.9 0 5 4 -1 4

358.974 717.949 19.865 29.218 1 0 1076.9 0 6 2 -1 2

461.538 615.385 20.428 31.836 1 0 1076.9 0 7 1.33 -1 1.33

538.462 538.462 21.501 33.508 1 0 1076.9 0 8 1 -1 1

598.291 478.632 23.222 34.606 1 0 1076.9 0 9 0.8 -1 0.8

646.154 430.769 25.751 35.351 1 0 1076.9 0 10 0.67 -1 0.67

685.315 391.608 29.300 35.870 1 0 1076.9 0 11 0.57 -1 0.57

717.949 358.974 34.163 36.242 1 0 1076.9 0 12 0.5 -1 0.5

7. (DUE)

MODELLO DI ASSEGNAZIONE DI EQUILIBRIO DETERMINISTICO RISOLTO CON UN

F &W ( 0,01%)

RANK OLFE TEST DI ARRESTO

In questo algoritmo vogliamo ricercare un vettore pari a

̅

̅

Dove è la linearizzazione della funzione z nel punto di equilibrio. La linearizzazione di una

funzione la si può fare con la funzione di Taylor fermandoci al primo ordine. Il valore della

̅

funzione in un suo intorno la possiamo approssimare a

̅ ̅

̅ ̅ ∇

Ed è pari al valore della funzione in quel punto più la derivata prima per il prolungamento . Per

trovare il minimo della funzione z lineare quando essa è somma di costanti e di variabili equivale a

considerare il minimo solo della parte variabile perché nella derivata in generale le costanti si

annullano. Quindi la relazione precedente si specializza

̅ ̅

̅ ∇

Dalla quale otteniamo il minimo.

Se la soluzione è nella parte non linearizzata prolunghiamo per continuità con Doerty In questo

modo otteniamo che 12

dove è il carico di rete

A questo punto possiamo sviluppare il nostro algoritmo e lo risolviamo con una sequenza di carichi

stocastici.

Partiamo da un e calcoliamo ricavando un e ricavati i costi d’ arco

0,1

calcoliamo l’ algoritmo di minimo percorso. Devo trovare un con

,

∙

Parto da un vettore iniziale dei flussi e calcolo le funzioni di costo. Mi calcolo il carico di rete

rispetto a quei costi e da quel punto mi sposto con la linearizzazione ottenendo il punto che mi da il

minimo della funzione z e da questo punto riparto. Sto prendendo la mia superficie di 2 e parto da

un punto individuando la direzione e mi sposto su di essa. Quando calcolo l’ è come se stessi

calcolando il gradiente mi trovo cioè sulla direzione di massima discesa e tagliando la superficie in

ottengo la mia funzione piana. Devo trovare un algoritmo che all’ interno dell’ intervallo mi

faccia trovare il minimo che risulta essere il minimo della sezione fatta. Riparto ora dal punto

e individuo un'altra direzione di discesa per ritrovare il minimo in un altro lato. Per trovare il

minimo di questa funzione utilizzo la seguente formula

, ,

: ∙ ∙ 0

Il vantaggio dell’ approccio sta nell’ aver trasformato il calcolo delle derivate nel calcolo delle

funzioni di costo.

Quello che manca è il test di arresto ossia quando è inutile proseguire perché la funzione risulta

essere quasi orizzontale. Il ragionamento che facciamo è sul valore della derivata e mi fermo

quando questo valore è prossimo allo zero perché noi stiamo cercando il bivio.

8. (SUE)

MODELLO DI ASSEGNAZIONE DI EQUILIBRIO STOCASTICO RISOLTO CON UN

10

ALGORITMO INCREMENTALE DIVIDENDO LA DOMANDA IN INTERVALLI

Ripartisco la domanda in 10 intervalli tutti uguali k = 1……10 e considero i flussi iniziali tutti nulli

∆ 0

10

13

Dai costi iniziali dei due percorsi moltiplicati per il otteniamo le due utilità e . Per ricavare la

probabilità di scelta dei due percorsi calcoliamo l’ esponenziale delle due funzioni di utilità e dalla

relazione

d f

Da questa relazione moltiplicando la probabilità per la domanda otteniamo

Le successive funzioni di costo le calcoliamo mediante la BPR ovvero:

∙ 1 ∙ → 1 ∙

Il nostro algoritmo si arresta quando k = n lim

→

Più interazioni facciamo più il valore finale dei flussi ottenuti si avvicina a .

D C1 C2 βt V1 V2 esp V1 esp V2 Pr 1 Pr 2 f1 f2

107.69 10 12 -0.91 -9.100 -10.920 0.0001117 0.0000181 0.8606 0.1394 92.676 15.016

107.69 10.00046 12.000000 -0.91 -9.100 -10.920 0.0001116 0.0000181 0.8605 0.1395 185.347 30.037

107.69 10.00737 12.000006 -0.91 -9.107 -10.920 0.0001109 0.0000181 0.8598 0.1402 277.937 45.140

107.69 10.03728 12.000031 -0.91 -9.134 -10.920 0.0001079 0.0000181 0.8564 0.1436 370.170 60.599

107.69 10.11730 12.000101 -0.91 -9.207 -10.920 0.0001004 0.0000181 0.8473 0.1527 461.414 77.047

107.69 10.28318 12.000264 -0.91 -9.358 -10.920 0.0000863 0.0000181 0.8267 0.1733 550.445 95.708

107.69 10.57353 12.000629 -0.91 -9.622 -10.921 0.0000663 0.0000181 0.7856 0.2144 635.050 118.797

107.69 11.01608 12.001493 -0.91 -10.025 -10.921 0.0000443 0.0000181 0.7103 0.2897 711.541 149.998

107.69 11.60139 12.003795 -0.91 -10.557 -10.923 0.0000260 0.0000180 0.5905 0.4095 775.137 194.094

107.69 12.25534 12.010640 -0.91 -11.152 -10.930 0.0000143 0.0000179 0.4446 0.5554 823.013 253.911

14

La generica iterazione è pari al calcolo delle funzioni di costo secondo i flussi dell’ iterazione k.

Dalle funzioni ottenute che sono i costi d’arco calcolo i costi di percorso e quindi la probabilità di

scelta del percorso.

∗

∆ ∙ →

9. (SUE)

MODELLO DI ASSEGNAZIONE DI EQUILIBRIO STOCASTICO RISOLTO CON UN

100

ALGORITMO INCREMENTALE DIVIDENDO LA DOMANDA IN INTERVALLI

∆ 100

In questo caso il procedimento da seguire è uguale al caso precedente con l’ unica differenza di

dover fare 100 iterazioni ottenendo dei valori di seguito riportati

d C1 C2 βt V1 V2 esp V1 esp V2 Pr 1 Pr 2 f1 f2

10.769 10 12 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86057 0.13943 9.26764 1.5016

10.769 10.000000046 12.000000000 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86057 0.13943 18.5353 3.0032

10.769 10.00000074 12.000000001 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86057 0.13943 27.8029 4.5048

10.769 10.00000373 12.000000003 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86057 0.13943 37.0705 6.0064

10.769 10.0000118 12.000000010 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86056 0.13944 46.3382 7.508

10.769 10.0000288 12.00000002 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86056 0.13944 55.6058 9.0096

10.769 10.00005973 12.00000005 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86056 0.13944 64.8733 10.511

10.769 10.00011065 12.00000009 -0.91 -9.1 -10.92 0.0001117 0.0000181 0.86055 0.13945 74.1408 12.013

10.769 10.00018877 12.00000016 -0.91 -9.1 -10.92 0.0001116 0.0000181 0.86055 0.13945 83.4082 13.515

10.769 10.00030237 12.00000025 -0.91 -9.1 -10.92 0.0001116 0.0000181 0.86053 0.13947 92.6755 15.017

10.769 10.00046085 12.00000038 -0.91 -9.1 -10.92 0.0001116 0.0000181 0.86052 0.13948 101.943 16.519

10.769 10.00067472 12.00000056 -0.91 -9.101 -10.92 0.0001116 0.0000181 0.86049 0.13951 111.209 18.021

10.769 10.00095558 12.00000079 -0.91 -9.101 -10.92 0.0001116 0.0000181 0.86046 0.13954 120.476 19.524

10.769 10.00131614 12.00000109 -0.91 -9.101 -10.92 0.0001115 0.0000181 0.86042 0.13958 129.742 21.027

10.769 10.0017702 12.00000147 -0.91 -9.102 -10.92 0.0001115 0.0000181 0.86037 0.13963 139.008 22.531

10.769 10.00233267 12.00000193 -0.91 -9.102 -10.92 0.0001114 0.0000181 0.86031 0.13969 148.273 24.035

10.769 10.00301955 12.0000025 -0.91 -9.103 -10.92 0.0001114 0.0000181 0.86024 0.13976 157.537 25.54

10.769 10.00384791 12.00000319 -0.91 -9.104 -10.92 0.0001113 0.0000181 0.86015 0.13985 166.8 27.046

10.769 10.00483593 12.00000401 -0.91 -9.104 -10.92 0.0001112 0.0000181 0.86004 0.13996 176.062 28.554

10.769 10.00600286 12.00000498 -0.91 -9.105 -10.92 0.0001111 0.0000181 0.85991 0.14009 185.322 30.062

10.769 10.00736901 12.00000612 -0.91 -9.107 -10.92 0.0001109 0.0000181 0.85976 0.14024 194.581 31.573

10.769 10.00895576 12.00000745 -0.91 -9.108 -10.92 0.0001108 0.0000181 0.85959 0.14041 203.838 33.085

15

10.769 10.01078554 12.00000898 -0.91 -9.11 -10.92 0.0001106 0.0000181 0.85939 0.14061 213.093 34.599

10.769 10.01288182 12.00001074 -0.91 -9.112 -10.92 0.0001104 0.0000181 0