注文を時間に分ける
線形計画は、線形制約 と の下で線形の目的関数 を最小化します。実行可能集合は平らな面と頂点を持つ多面体で、目的が線形なので最良点は常にその形の角（頂点）にあります。坂を下る歩みはありません。シンプレックス法は頂点から頂点へ跳び、内点法は内部を突っ切ります。どちらも数千変数の問題の厳密な最適解を一瞬で求めます。
(1)
執行スケジュールは自然な線形計画です。 株を 区間で売るとき、区間 の売却数を 、そこでの1株あたり期待コスト（スプレッドとインパクト、ベーシスポイント）を 、容量（たとえば予想出来高の10%という参加率上限）を とします。予算制約が1つなら解は貪欲で、最も安い区間を上限まで埋め、次に安い区間へと が済むまで進みます。線形計画が無料で教えてくれる予算制約の乗数は、もう1株売る限界コスト、つまりまだ余裕のある最も安い区間のコストです。
4つの区間 株を売ります。区間1〜4のコストは bp、上限は 株です。貪欲に埋めると、区間2（コスト1）が上限の 、区間3（コスト2）が 、区間1（コスト3）が残りの を引き受けます。合計は bp·株で、平均 bp です。限界コストは区間1の bp で、余裕のある最も安い区間だからです。総容量は なので、 株の注文には実行可能なスケジュールがそもそもありません。
容量はデータから得られます。このコースのデータセットの直近250営業日で、AAPLの出来高の中央値は約4550万株なので、参加率10%の上限は1日約455万株で、2000万株を売るには少なくとも 、つまり5営業日が必要です。1株あたりのコストを一定とするのは第一近似です。実際のインパクトは区間内の取引量とともに増えるため、コストは について凸になり、スケジュールは2次計画になります。これが総仕上げのモデルです。
- 頂点解：線形計画の最適解は実行可能な多面体の角にあります。
- 貪欲なスケジュール：予算制約が1つなら、最も安い容量から埋めます。
- シャドウプライス：予算制約の乗数は、もう1株の限界コストです。
まず実行可能性を確認するソルバーは不可能な要求に対して、近似的なスケジュールではなく「実行不可能」と答えます。最適化の前に注文サイズを総容量と比べ、収まらないときは何を譲るかを決めてください。期間を延ばすか、参加率の上限を上げるか、注文を小さくするかです。コストと容量は予測値なので、一日の進行に合わせてプログラムを再実行します。
ラボ：採点される内容
- 総コスト15点
- 平均コスト10点
- 使われる最も高い区間の株数15点
- 限界コスト15点
- 大きすぎる注文15点
- LPの最適解の位置15点
- スケジュールの定式化15点