Algoritmo per scambi ottimali lungo una rotta fissa

Question

Algoritmo per scambi ottimali lungo una rotta fissa

Naviga le tue risposte

#1 da (1 voti)
#2 da (1 voti)
#3 da (1 voti)
#4 da (1 voti)
#5 da (0 voti)

5

Immagina di essere a capo di una nave da carico:

viaggiare lungo una rotta o un anello (A, B, C, D, A ...)
ha una capacità massima di carico

Ad ogni fermata puoi:

acquista merci, fino alla tua capacità di carico o vendi merci che hai già acquistato
ogni fermata ha prezzi diversi per ciascuna merce
per semplicità, non puoi restare senza soldi per comprare
anche per semplicità, gli importi delle merci sono divisibili all'infinito, quindi non ci sono problemi con lo stack-problem

Quale algoritmo posso utilizzare per determinare le migliori materie prime e ammontare a comprare / vendere ad ogni fermata, per ottenere il massimo profitto?

La soluzione è non solo per comprare basso e vendere alto perché hai uno spazio di carico limitato, e c'è un compromesso tra trasportare carichi redditizi tra molte fermate e fare più scambi ad ogni fermata. Ad esempio: data una rotta A - > B - > C, due prodotti (mele, arance) e i seguenti prezzi:

Stop | Apples | Oranges
-----+--------+--------
   A |     $1 |     $1
   B |     $2 |     $1
   C |     $4 |     $3

L'azione migliore sarebbe comprare mele in A e venderle a C, con un profitto di $ 3 * capacità. Ma se le arance dovessero apprezzare $ 3 in B, allora sarebbe meglio acquistare arance in A, venderle in B e comprare mele e vendere le mele in C, per un profitto totale di ($ 2 + $ 2) * capacità.

algorithms

posta congusbongus 23.12.2016 - 03:32

fonte

5 risposte

Leggi altre domande sui tag algorithms

Etimologia delle funzioni "statiche" Come faccio a sapere quando effettuare il refactoring delle chiamate globali alle query del database e quando lasciarle da sole?

score 1 · Answer 1

Disegna un grafico con i nodi per ogni porta. Da ogni porto a ogni altra porta traccia un vantaggio per ogni merce, appesantisci il margine con il profitto guadagnato dal trasporto della merce lungo quel porto-porto. Quindi ora hai una multigrafo ponderata. Per completezza ti consigliamo di aggiungere bordi da C a A con peso 0 - non ci sono profitti che trasportano mele o arance da C a A.

Questa è una rete di flusso, ci sono molti algoritmi. Un'istanza semplice come questa potrebbe produrre piacevolmente una programmazione lineare.

A meno che non vi siano limiti alla fornitura e alla domanda di mele e arance in uno o in ciascuno dei porti, non si guadagna nulla trasportando parti di carico, né trasportando carichi misti.

Il mio schizzo rapido suggerisce che si fanno tanti soldi per trasportare un carico di mele da A a B e poi un altro carico di mele da B a C come si fa trasportando un carico di mele diretto da A a C. Quindi questo è un altro strano risultato della semplicità del problema posto.

L'OP scrive c'è un compromesso tra il portare merci redditizie tra molte fermate e fare più scambi ad ogni fermata ma non c'è espressione di tale compromesso nella domanda; se c'è un compromesso non emerge dai numeri.

Mi aspetto che, poiché OP aggiunge complessità al modello, rimane un problema di rete del flusso ma la scelta dell'algoritmo diventa più interessante.

score 1 · Answer 2

Probabilmente lo programmerei in questo modo:

Prima di tutto determina tutte le possibili rotte commerciali

A-B
B-C
C-A

A-C
B-A
C-B

Quindi calcola lo scambio più redditizio tra ogni percorso

foreach (item in items)
  profit = (item.a.ask - item.b.bid) * (cargosize/item.size)
  if (profit> highestprofit)
    selecteditem = item
    highestprofit = profit

= > azzera i profitti negativi e disinserisci l'articolo (carico vuoto)

Determina le possibili combinazioni e il profitto totale:

A-B,B-C,C-A
A-C, C-A
A-B, B-A
B-C, C-B

score 1 · Answer 3

Potresti anche solo forzarlo a forza Per ogni porto e ogni prodotto inserisci -1 0 1 per vendere, tenere, comprare
Finirai con (porta * prodotto) ^ 3 opzioni per valutare
Corri attraverso tutti loro e vedi qual è il massimo profitto Puoi eliminare vendere se la porta è il prezzo basso del prodotto
E puoi eliminare buy se la porta è il prezzo elevato del prodotto

Ho funzionato

Per e ciclo infinito lo eseguo appena 3 volte
Sottopongo a test diversi ingressi e questo si è sempre risolto con il 2 ° passaggio

Al primo passaggio non puoi vendere qualcosa che non hai ancora

Nell'ultimo passaggio non compra nulla che non venderai

Ho reso capacità 2 * 3 * 5 * 7 * 11 per divisibilità pari
Se vuoi più di 11 prodotti, aggiungi altri numeri primi

Inoltre non è mai necessario acquistare più di 1 prodotto per porta. Se c'è un pareggio allora la divisione non cambia nulla. Puoi entrare in un problema di deviazione irregolare con le divisioni.

Questo è una risposta per un passaggio.

score 1 · Answer 4

I limiti di capacità sono un mal di testa da modellare, ma possono essere risolti con la programmazione lineare.

Max Z = Sum_i,j (P_i,j * X_i,j)
subject to:
    Carried_at_i = Sum_j (X_j<=i,j>i)            for all i
        //Kind of a rough sketch, not sure about this one.
        //e.g. Since it's a round trip, j<i could mean something different, etc.
    Carried_at_i <= Capacity                     for all i
    X_ij >= 0                                    for all i, j

dove

i, j sono posizioni
P è il profitto di acquistare a i e di vendere a j
X è la quantità acquistata a i e venduta a j

score 0 · Answer 5

O mi manca qualcosa o la risposta è davvero semplice:

Supponiamo che i prezzi di acquisto e i prezzi di vendita siano gli stessi in ogni porto e che non vi sia alcun addebito per il carico / scarico.
Ad ogni fermata, puoi scaricare / vendere tutto e acquistare / caricare nuovo carico. Ciò ha lo stesso effetto di vendere / scaricare solo parte del carico, perché puoi sempre comprare lo stesso tipo .

Con questo ragionamento, il mix di carico in ciascuna gamba può essere calcolato indipendentemente dal mix di carico in qualsiasi altra tappa. Poiché viene fornita la sequenza di porte, carichi il carico con la differenza di prezzo più alta per la porta successiva in ciascuna tratta.