Lineare Programmierung für Ausführungspläne

Einen Auftrag über die Zeit verteilen

Ein lineares Programm minimiert ein lineares Ziel $\mathbf c^{T}\mathbf x$ unter linearen Nebenbedingungen $A\mathbf x\le\mathbf b$ und $\mathbf x\ge0$. Die zulässige Menge ist ein Polytop, eine Form mit ebenen Flächen und Ecken, und weil das Ziel linear ist, liegt der beste Punkt stets an einer Ecke dieser Form. Es gibt kein Bergabgehen: Das Simplexverfahren springt von Ecke zu Ecke, Innere-Punkte-Verfahren schneiden durch die Mitte, und beide erreichen das exakte Optimum eines Problems mit Tausenden Variablen in Sekundenbruchteilen.

Ein Ausführungsplan ist ein natürliches lineares Programm. Um $Q$ Aktien in $T$ Intervallen zu verkaufen, sei $x_t$ die im Intervall $t$ verkaufte Menge, $c_t$ die erwarteten Kosten je Aktie dort (Spread plus Impact, in Basispunkten) und $u_t$ eine Kapazität, etwa eine Beteiligungsgrenze von 10 % des erwarteten Volumens. Mit einer einzigen Budgetnebenbedingung ist die Lösung gierig: das billigste Intervall bis zur Grenze füllen, dann das nächstbilligste, bis $Q$ erledigt ist. Der Multiplikator der Budgetnebenbedingung, den die lineare Programmierung gratis liefert, sind die Grenzkosten einer weiteren Aktie, nämlich die Kosten des billigsten Intervalls, das noch Platz hat.

Die Kapazitäten können aus Daten stammen. In den letzten 250 Handelstagen des Kursdatensatzes liegt das mediane Tagesvolumen von AAPL bei etwa 45,5 Millionen Aktien; eine Beteiligungsgrenze von 10 % sind also etwa 4,55 Millionen Aktien pro Tag, und der Verkauf von 20 Millionen Aktien braucht mindestens $20/4.55=4.4$, also fünf, Handelstage. Konstante Kosten je Aktie sind eine erste Näherung. Der reale Impact wächst mit der in einem Intervall gehandelten Menge, was die Kosten in $x_t$ konvex macht und den Plan zu einem quadratischen Programm, dem Modell des Abschlussprojekts.

• Ecklösung: Das Optimum eines LP liegt an einer Ecke des zulässigen Polytops.
• Gieriger Plan: Mit einer Budgetnebenbedingung zuerst die billigste Kapazität füllen.
• Schattenpreis: Der Budgetmultiplikator sind die Grenzkosten einer weiteren Aktie.

Lab: Was bewertet wird

• Die Gesamtkosten15 Pkt.
• Die Durchschnittskosten10 Pkt.
• Aktien im teuersten genutzten Intervall15 Pkt.
• Die Grenzkosten15 Pkt.
• Ein zu großer Auftrag15 Pkt.
• Wo das Optimum eines LP liegt15 Pkt.
• Den Plan formulieren15 Pkt.