Programação linear para cronogramas de execução

Dividir uma ordem no tempo

Um programa linear minimiza um objetivo linear $\mathbf c^{T}\mathbf x$ sujeito a restrições lineares $A\mathbf x\le\mathbf b$ e $\mathbf x\ge0$. O conjunto viável é um poliedro, uma forma com faces planas e vértices, e como o objetivo é linear o melhor ponto está sempre em um vértice dessa forma. Não há caminhada morro abaixo: o método simplex salta de vértice em vértice e os métodos de pontos interiores cortam pelo meio; ambos chegam ao ótimo exato de um problema com milhares de variáveis numa fração de segundo.

Um cronograma de execução é um programa linear natural. Para vender $Q$ ações em $T$ intervalos, seja $x_t$ as ações vendidas no intervalo $t$, $c_t$ o custo esperado por ação ali (spread mais impacto, em pontos-base) e $u_t$ uma capacidade, como um teto de participação de 10 % do volume esperado. Com uma só restrição de orçamento a solução é gulosa: encher o intervalo mais barato até o teto, depois o seguinte mais barato, até completar $Q$. O multiplicador da restrição de orçamento, que a programação linear dá de graça, é o custo marginal de mais uma ação, isto é, o custo do intervalo mais barato que ainda tem espaço.

As capacidades podem vir dos dados. Nas últimas 250 sessões do conjunto de dados do curso, o volume diário mediano da AAPL é de cerca de 45,5 milhões de ações; um teto de participação de 10 % dá cerca de 4,55 milhões de ações por dia, e vender 20 milhões de ações exige pelo menos $20/4.55=4.4$, isto é, cinco, sessões. Um custo constante por ação é uma primeira aproximação. O impacto real cresce com o tamanho negociado num intervalo, o que torna o custo convexo em $x_t$ e transforma o cronograma num programa quadrático, o modelo do projeto final.

• Solução em vértice: o ótimo de um PL está num canto do poliedro viável.
• Cronograma guloso: com uma só restrição de orçamento, preencher primeiro a capacidade mais barata.
• Preço-sombra: o multiplicador do orçamento é o custo marginal de mais uma ação.

Lab: o que é avaliado

• O custo total15 pts
• O custo médio10 pts
• Ações no intervalo mais caro usado15 pts
• O custo marginal15 pts
• Uma ordem grande demais15 pts
• Onde fica o ótimo de um PL15 pts
• Formular o cronograma15 pts