Programación lineal para calendarios de ejecución

Repartir una orden en el tiempo

Un programa lineal minimiza un objetivo lineal $\mathbf c^{T}\mathbf x$ sujeto a restricciones lineales $A\mathbf x\le\mathbf b$ y $\mathbf x\ge0$ . El conjunto factible es un politopo, una forma con caras planas y vértices, y como el objetivo es lineal el mejor punto está siempre en un vértice de esa forma. No hay marcha cuesta abajo: el método símplex salta de vértice en vértice y los métodos de punto interior atraviesan el interior; ambos alcanzan el óptimo exacto de un problema con miles de variables en una fracción de segundo.

\min_{\mathbf x}\ \sum_{t=1}^{T}c_t x_t\ ;\quad \sum_{t=1}^{T}x_t=Q,\qquad 0\le x_t\le u_t

(1)

Un calendario de ejecución es un programa lineal natural. Para vender $Q$ acciones en $T$ intervalos, sea $x_t$ las acciones vendidas en el intervalo $t$ , $c_t$ el coste esperado por acción allí (diferencial más impacto, en puntos básicos) y $u_t$ una capacidad, como un tope de participación del 10 % del volumen esperado. Con una sola restricción de presupuesto la solución es voraz: llenar el intervalo más barato hasta su tope, luego el siguiente más barato, hasta completar $Q$ . El multiplicador de la restricción de presupuesto, que la programación lineal da gratis, es el coste marginal de una acción más, es decir, el coste del intervalo más barato que aún tiene espacio.

Cuatro intervalosVendamos

Q=10{,}000

acciones. Los costes son

3,1,2,4

puntos básicos y los topes

4000,3000,5000,6000

acciones en los intervalos 1 a 4. Llenado voraz: el intervalo 2 (coste 1) toma su tope de

3000

, el intervalo 3 (coste 2) toma

5000

y el intervalo 1 (coste 3) toma las

2000

restantes. El total es

3000\cdot1+5000\cdot2+2000\cdot3=19{,}000

puntos básicos-acciones, un promedio de

1.9

pb. El coste marginal es el del intervalo 1,

3

pb, porque es el más barato que aún tiene espacio. La capacidad total es

18{,}000

, así que una orden de

20{,}000

acciones no tiene ningún calendario factible.

Las capacidades pueden venir de los datos. En las últimas 250 sesiones del conjunto de datos del curso, el volumen diario mediano de AAPL es de unos 45,5 millones de acciones; un tope de participación del 10 % son unos 4,55 millones de acciones al día, y vender 20 millones de acciones requiere al menos $20/4.55=4.4$ , es decir cinco, sesiones. Un coste constante por acción es una primera aproximación. El impacto real crece con el tamaño operado en un intervalo, lo que hace el coste convexo en $x_t$ y convierte el calendario en un programa cuadrático, el modelo del proyecto final.

Solución en un vértice: el óptimo de un PL está en una esquina del politopo factible.
Calendario voraz: con una sola restricción de presupuesto, llenar primero la capacidad más barata.
Precio sombra: el multiplicador del presupuesto es el coste marginal de una acción más.

Compruebe primero la factibilidadUn solucionador responde a una petición imposible con «infactible», no con un calendario aproximado. Compare el tamaño de la orden con la capacidad total antes de optimizar y decida qué cede si no cabe: un horizonte más largo, un tope de participación más alto o una orden menor. Costes y capacidades son previsiones, así que vuelva a ejecutar el programa a lo largo del día.

Lab: qué se califica

El coste total15 pts
El coste medio10 pts
Acciones en el intervalo más caro usado15 pts
El coste marginal15 pts
Una orden demasiado grande15 pts
Dónde está el óptimo de un PL15 pts
Formular el calendario15 pts

Repartir una orden en el tiempo

\min_{\mathbf x}\ \sum_{t=1}^{T}c_t x_t\ ;\quad \sum_{t=1}^{T}x_t=Q,\qquad 0\le x_t\le u_t

(1)

Cuatro intervalosVendamos

Q=10{,}000

acciones. Los costes son

3,1,2,4

puntos básicos y los topes

4000,3000,5000,6000

acciones en los intervalos 1 a 4. Llenado voraz: el intervalo 2 (coste 1) toma su tope de

3000

, el intervalo 3 (coste 2) toma

5000

y el intervalo 1 (coste 3) toma las

2000

restantes. El total es

3000\cdot1+5000\cdot2+2000\cdot3=19{,}000

puntos básicos-acciones, un promedio de

1.9

pb. El coste marginal es el del intervalo 1,

3

pb, porque es el más barato que aún tiene espacio. La capacidad total es

18{,}000

, así que una orden de

20{,}000

acciones no tiene ningún calendario factible.

Solución en un vértice: el óptimo de un PL está en una esquina del politopo factible.
Calendario voraz: con una sola restricción de presupuesto, llenar primero la capacidad más barata.
Precio sombra: el multiplicador del presupuesto es el coste marginal de una acción más.

Lab: qué se califica

El coste total15 pts
El coste medio10 pts
Acciones en el intervalo más caro usado15 pts
El coste marginal15 pts
Una orden demasiado grande15 pts
Dónde está el óptimo de un PL15 pts
Formular el calendario15 pts

Programación lineal para calendarios de ejecución

Repartir una orden en el tiempo

Lab: qué se califica

Inicia sesión para ejecutar tu código.

Programación lineal para calendarios de ejecución

Repartir una orden en el tiempo

Lab: qué se califica

Inicia sesión para ejecutar tu código.