Problema di ottimizzazione Sant'Anna

[Nickbru1]

 La Scuola Sant’Anna ha deciso di partecipare al
campionato di Formula Uno con una vettura, e si sta
preparando per il prossimo gran premio che si svolgerà sul
circuito di Montecarlo (comune della provincia di Lucca). I
suoi ingegneri hanno a disposizione i seguenti dati:

- la gara consiste in 120 giri di pista;

- la capacità del serbatoio della vettura permette, se necessario, di completare la gara senza alcun pit-stop.

- Per un pit-stop si impiegano 30 secondi in totale, compresi i tempi di rallentamento ed accelerazione, indipendentemente dalla quantità di carburante immessa;

- per ogni giro si consumano, indipendentemente da ogni altro parametro, 3 kg di carburante;

- il tempo di percorrenza di un giro aumenta di 3 centesimi di secondo per ogni kg di carburante in più
presente nel serbatoio all’inizio del giro stesso;

Determinare la strategia (cioè il numero dei pit-stop da
effettuare ed i giri nei quali effettuarli) per permettere di terminare la gara nel minor tempo possibile.

Qual è il miglior modo per risolvere questo tipo di problemi? Ce ne sono un sacco negli anni, però non so bene come comportarmi per una risoluzione elegante.

[axpgn]

Io proverei a fare così ...

Detto $p$ il numero di pit-stop effettuati, i secondi persi globalmente per tutte le fermate saranno $30p$
e il numero di giri di ogni "stint" sarà $120/(p+1)$.
Invece i secondi persi dovuti al peso sono $[120/(p+1)*(120/(p+1)+1)]*1/2*9/100*(p+1)$
Semplificando $[120(121+p)]/(p+1)*9/200=(653.4+5.4p)/(p+1)$
In totale i secondi in più saranno $(653.4+5.4p)/(p+1)+30p$

Deriviamo per minimizzare $(5.4(p+1)-653.4-5.4p)/(p+1)^2+30=-648/(p+1)^2+30=0$ ovvero $30p^2+60p-618=0$ che dà come soluzione $p=3.6476$ quindi $3$ o $4$ pit stop (forse $4$ ?)

Vedi tu ...

Cordialmente, Alex

[Nickbru1]

Come hai tirato fuori il tempo perso per il peso? Io avevo pensato a questo

$ 30p+(p+1)\cdot \frac{9}{100} \cdot \sum_{i=0}^{\frac{120}{p+1}}(\frac{120}{p+1}-i) $

e In questo modo verrebbe che il miglior tempo si ottiene per p=5

[axpgn]

Avrò sbagliato i conti ma mi pare la stessa cosa ...

La somma dei primi $n$ naturali è $sum_(k=1)^n k = (n(n+1))/2$, Gauss docet

Cordialmente, Alex

[axpgn]

Comunque ...

... con $5$ pit-stop a me viene un tempo più alto che con $4$ ovvero $263.4\text(s)$ contro $255\text(s)$

Cordialmente, Alex

[Nickbru1]

Si hai ragione, sono io non capace a fare i conti. Grazie mille

[axpgn]

Anche con $3$ pit-stop, il tempo in eccesso ($257.4\text(s)$) è minore di quello con $5$ ma maggiore di quello con $4$ e ciò rende la soluzione $3.6476$ plausibile ... però, toglimi una curiosità: i pit-stop sono un numero intero quindi la soluzione effettiva qual era?

Cordialmente, Alex

[jas1231]

Propongo la mia soluzione, ma non sono sicuro al 100%.

Innanzitutto dimostriamo che dividere il percorso in parti uguali è il modo migliore per ottimizzare le tempistiche.

Supponiamo che il percorso sia diviso in due parti da un pit stop: una parte consiste di \(i\) giri, l'altra invece di \(j\) giri, e supponiamo che \(i \ne j\).
Per ottimizzare i tempi, ovviamente, minimizziamo la benzina trasportata, quindi all'inizio del percorso il serbatoio dell'auto sarà riempito con \(3i \,\, \text{kg di carburante}\) mentre al pit stop sarà riempito con \(3j \,\, \text{kg di carburante}\).
Ora calcoliamo il tempo "perso" a causa del carburante trasportato (\(t_i\) è il tempo perso nel percorso \(i\) e \(t_j\) è il tempo perso nel percorso \(j\)).
\[
\begin{array}{l}
t_i= \dfrac{3}{100} \{3i+(3i-3)+(3i-6)+\ldots +3\}=\dfrac{9}{100}\dfrac{i(i+1)}{2} \\
\,\, \\
t_j=\dfrac{9}{100}\dfrac{j(j+1)}{2}
\end{array}
\]
Allora in totale per via del carburante si è perso
\[t=t_i+t_j=\dfrac{9}{100}\dfrac{(i+1)i+(j+1)j}{2}\]
Ora invece supponiamo che il percorso sia diviso in due parti uguali di lunghezza \(k\) allora \[k=\dfrac{i+j}{2} \,\, \text{e} \,\, t=2t_k=\dfrac{9}{100}\dfrac{(i+j+2)(i+j)}{4}\]

Riarrangiamo questo \(t\):

\[\dfrac{9}{100}\dfrac{(i+j+2)(i+j)}{4}=\dfrac{9}{100}\dfrac{((i+1)+(j+1))(i+j)}{4}=\dfrac{9}{100}\dfrac{(i+1)i+(j+1)j}{4}+\dfrac{9}{100}\dfrac{(i+1)j+(j+1)i}{4} \underbrace{\le \dfrac{9}{100}\dfrac{(i+1)i+(j+1)j}{2} }_{\text{Per il bunching theorem}}\]

Quindi, proprio come ci aspettavamo, dividendo in parti uguali ottimizziamo le tempistiche a parità di pit stop (questo ragionamento è valido per un percorso diviso in 2 parti ma lo si può generalizzare facilmente, ad esempio per induzione).

Ora non ci resta che trovare il numero ottimale di parti in cui dividere il percorso. Questo numero sarà tale che dividendo il percorso in meno o più parti il tempo perso (comprensivo di pit stop) sarà maggiore.

Supponiamo che il percorso sia diviso in \(x\) parti uguali e il carburante sia distribuito in maniera ottimale, allora
\[t_x=\dfrac{54}{10} \Large{(} \normalsize{\dfrac{120}{k}+1} \Large{)} +\normalsize{ 30(k-1)}\]

Se invece il percorso fosse diviso in \(x-1\) parti avremmo
\[t_{x-1}=\dfrac{54}{10} \Large{(} \normalsize{\dfrac{120}{k-1}+1} \Large{)} +\normalsize{ 30(k-2)} \]

Allora poniamo \[t_x
Da questo calcolo possiamo evincere che dividere il percorso in 5 parti uguali è la scelta ottimale, perché 5 se \(x>5\) allora \(t_x>t_5\) e se \(x<5\) allora \(t_5
Verifichiamo con i calcoli:
se dividiamo il percorso in 4
\[t_4=\dfrac{54}{10} \Large{(} \normalsize{\dfrac{120}{4}+1} \Large{)} +\normalsize{ 30(3)=257.4}\]
se dividiamo il percorso in 5
\[t_5=\dfrac{54}{10} \Large{(} \normalsize{\dfrac{120}{5}+1} \Large{)} +\normalsize{ 30(4)=255}\]
se dividiamo il percorso in 6
\[t_6=\dfrac{54}{10} \Large{(} \normalsize{\dfrac{120}{6}+1} \Large{)} +\normalsize{ 30(5)=263.4}\]

Quindi in conclusione la strategia migliore è piazzare 4 pitstop a distanze uguali tra loro

[Nickbru1]

"axpgn":

Anche con $3$ pit-stop, il tempo in eccesso ($257.4\text(s)$) è minore di quello con $5$ ma maggiore di quello con $4$ e ciò rende la soluzione $3.6476$ plausibile ... però, toglimi una curiosità: i pit-stop sono un numero intero quindi la soluzione effettiva qual era?

La soluzione purtroppo non c'è, ma è plausibile essere l'intero più vicino

[Nickbru1]

"jas123":Propongo la mia soluzione, ma non sono sicuro al 100%.

Siamo d'accordo allora. A me mancava una buona dimostrazione del perché fare soste uguali sia meglio

[axpgn]

In effetti, la sua (più che buona) dimostrazione era il tassello che mancava

[jas1231]

Secondo me in questo caso la difficoltà del problema stava proprio nel pensare di dividere il percorso in parti uguali.
Quindi per tornare alla domanda originale del post

"Nickbru":Qual è il miglior modo per risolvere questo tipo di problemi? Ce ne sono un sacco negli anni, però non so bene come comportarmi per una risoluzione elegante.

Onestamente non lo so, bisogna fare un po' di tentativi e ragionare sulle simmetrie, ma non credo che troverai da nessuna parte un metodo onnicomprensivo (e nel caso lo trovassi scrivilo subito che lo cerco anche io).