Algoritmo para negociações ótimas ao longo de uma rota fixa

5

Imagine que você é responsável por um navio de carga:

  • viajando ao longo de uma rota fixa ou loop (A, B, C, D, A ...)
  • tem capacidade máxima de carga

Em cada parada, você pode:

  • comprar commodities, até sua capacidade de carga, ou vender cargas que você já comprou
  • cada parada tem preços diferentes para cada mercadoria
  • para simplificar, você não pode ficar sem dinheiro para comprar
  • também para simplificar, os valores de carga são infinitamente divisíveis, portanto não há problemas semelhantes a problemas de mochila

Qual algoritmo posso usar para determinar as melhores mercadorias e quantidade para comprar / vender em cada parada, para obter o maior lucro?

A solução não é apenas comprar baixa e vender alta porque você tem espaço de carga limitado, e há uma compensação entre o transporte de carga rentável entre muitas paradas e a realização de mais negócios em cada parada. Por exemplo: dada uma rota A - > B - > C, duas mercadorias (maçãs, laranjas) e os seguintes preços:

Stop | Apples | Oranges
-----+--------+--------
   A |     $1 |     $1
   B |     $2 |     $1
   C |     $4 |     $3
A melhor ação seria comprar maçãs em A e vendê-las em C, com lucro de US $ 3 *. Mas se as laranjas se valorizassem para $ 3 em B, então seria melhor comprar laranjas em A, vendê-las em B e comprar maçãs, e vender as maçãs em C, para um lucro total de ($ 2 + $ 2) * capacidade.

    
por congusbongus 23.12.2016 / 03:32
fonte

5 respostas

1

Desenhe um gráfico com nós para cada porta. De cada porto a todos os outros portos, desenhe uma vantagem para cada commodity, aumente a margem com o lucro obtido com o transporte da commodity ao longo desse hop port-port. Então agora você tem um multigrafo ponderado. Para completar, você vai querer adicionar bordas de C de volta a A com peso 0 - não há lucro transportando maçãs ou laranjas de C para A.

Esta é uma rede de fluxo, existem muitos algoritmos. Uma instância simples como essa pode render-se bem à programação linear.

A menos que haja limites para a oferta e demanda de maçãs e laranjas em qualquer um ou em cada um dos portos, não há nada a ganhar transportando parte das cargas, nem transportando cargas misturadas.

Meu rápido esboço sugere que você ganha tanto dinheiro pegando uma carga de maçãs de A a B e depois outro carregamento de maçãs de B para C como transporta um carregamento de maçãs direto de A para C. Então, isso é outra resultado estranho da simplicidade do problema como colocado.

OP escreve há uma compensação entre o transporte de carga lucrativa entre muitas paradas e fazer mais negócios em cada parada , mas não há expressão de tal troca na questão; se houver uma troca, não sai dos números.

Espero que, como o OP adiciona complexidade ao modelo, ele continue sendo um problema de rede de fluxo, mas a escolha do algoritmo se torna mais interessante.

    
por 23.12.2016 / 09:56
fonte
1

Eu provavelmente programaria assim:

Primeiro, determine todas as rotas comerciais possíveis

A-B
B-C
C-A

A-C
B-A
C-B

Em seguida, calcule o comércio mais rentável entre cada rota

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

= > zerar lucros negativos e item não definido (carga vazia)

Determine possíveis combinações e lucro total:

A-B,B-C,C-A
A-C, C-A
A-B, B-A
B-C, C-B
    
por 23.12.2016 / 10:59
fonte
1

você também poderia apenas força bruta
Para cada porto e cada produto, insira -1 0 1 para vender, manter, comprar
Você vai acabar com (porta * produto) ^ 3 opções para avaliar
Percorrer todos eles e ver qual é o lucro máximo
Você poderia eliminar vender se o porto é o baixo preço do produto
E você pode eliminar a compra se a porta é o alto preço do produto

Eu consegui trabalhar

Para um loop infinito, apenas corro como 3 vezes | Eu testei várias entradas e sempre resolvi pela segunda passagem

Na primeira passagem, você não pode vender algo que ainda não tenha

Na última passada, não compre nada que não vai vender

Eu fiz capacidade 2 * 3 * 5 * 7 * 11 para divisibilidade ainda
Se você quiser mais de 11 produtos, adicione mais primes

Além disso, você nunca precisa comprar mais de um produto por porta. Se houver empate, a divisão não alterará nada. Você pode entrar em um problema de visão desigual com divisões.

Este é uma resposta para um passo.

    
por 24.12.2016 / 16:17
fonte
1

As restrições de capacidade são uma dor de cabeça para modelar, mas podem ser resolvidas com programação linear.

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

onde

  • i, j são locais
  • P é o lucro de comprar em i e vender em j
  • X é a quantidade comprada em i e vendida em j
por 04.01.2017 / 00:41
fonte
0

Ou eu estou perdendo alguma coisa ou a resposta é muito simples:

  • Suponha que os preços de compra e os preços de venda sejam os mesmos em cada porto e que não haja cobrança por carga / descarga.
  • Em cada parada, você pode descarregar / vender tudo e comprar / carregar nova carga. Isso tem o mesmo efeito de vender / descarregar apenas parte da carga, porque você sempre pode comprar o mesmo tipo novamente.

Com esse raciocínio, o mix de carga em cada perna pode ser calculado independentemente do mix de carga em qualquer outra perna. Como a sequência de portas é dada, você carrega a carga com a maior diferença de preço para a próxima porta em cada perna.

    
por 26.12.2016 / 20:49
fonte

Tags