البرمجة الخطية لجداول التنفيذ

توزيع أمر على الزمن

يقلّل البرنامج الخطي هدفًا خطيًا $\mathbf c^{T}\mathbf x$ بقيود خطية $A\mathbf x\le\mathbf b$ و$\mathbf x\ge0$. والمجموعة الممكنة متعدد وجوه، أي شكل ذو أوجه مستوية وزوايا، ولأن الهدف خطي فأفضل نقطة تقع دائمًا عند زاوية (رأس) هذا الشكل. لا يوجد مشي نزولي: تقفز طريقة السمبلكس من رأس إلى رأس وتشق طرق النقطة الداخلية الوسط، وكلتاهما تبلغ الأمثل الدقيق لمسألة بآلاف المتغيرات في جزء من الثانية.

جدول التنفيذ برنامج خطي طبيعي. لبيع $Q$ سهمًا على $T$ فترة، ليكن $x_t$ الأسهم المباعة في الفترة $t$ و$c_t$ الكلفة المتوقعة للسهم فيها (الفارق السعري مع الأثر، بنقاط الأساس) و$u_t$ سعة كسقف مشاركة بنسبة 10% من الحجم المتوقع. ومع قيد ميزانية واحد يكون الحل جشعًا: املأ أرخص فترة حتى سقفها ثم التي تليها حتى يكتمل $Q$. ومضروب قيد الميزانية، الذي تعطيه البرمجة الخطية مجانًا، هو الكلفة الحدية لسهم إضافي أي كلفة أرخص فترة ما زال فيها متسع.

قد تأتي السعات من البيانات. ففي آخر 250 جلسة من مجموعة بيانات المقرر يبلغ الحجم اليومي الوسيط لسهم AAPL نحو 45.5 مليون سهم، فسقف مشاركة 10% يعني نحو 4.55 مليون سهم يوميًا، وبيع 20 مليون سهم يحتاج على الأقل $20/4.55=4.4$ أي خمس جلسات. والكلفة الثابتة للسهم تقريب أول. فالأثر الحقيقي يزداد مع حجم التداول في الفترة، فتصير الكلفة محدبة في $x_t$ ويتحول الجدول إلى برنامج تربيعي وهو نموذج المشروع الختامي.

• حل عند رأس: أمثل البرنامج الخطي عند زاوية متعدد الوجوه الممكن.
• جدول جشع: مع قيد ميزانية واحد املأ السعة الأرخص أولًا.
• السعر الظل: مضروب الميزانية هو الكلفة الحدية لسهم إضافي.

المختبر: ما الذي يُقيَّم

• الكلفة الكلية15 نقطة
• الكلفة المتوسطة10 نقطة
• الأسهم في أغلى فترة مستعملة15 نقطة
• الكلفة الحدية15 نقطة
• أمر أكبر من اللازم15 نقطة
• أين يقع أمثل البرنامج الخطي15 نقطة
• صياغة الجدول15 نقطة