اختيار مجموعة جزئية من N عنصر مرشّح، لكلٍّ منها قيمة ووزن، بحيث لا يتعدّى الوزن الإجمالي سعة (ميزانية، ساعات عمل، ساعات آلة) ويكون مجموع القيم أقصى. في الأدبيات Knapsack Problem — جدّ مسائل الاختيار المنفصل.
باختصار
هل يبدو مألوفاً؟
- لجنة استثمار سنوية أمامها 50-200 مشروع مرشّح وميزانية إجمالية ثابتة 50-500M TRY — الترتيب حدسي وسياسي؛ يُعَدّ جدول 'NPV/الاستثمار' لكن المثاليّة الرياضية ليست مضمونة.
- لكلّ مرشّح تقدير NPV، استثمار مطلوب، ساعات عمل مطلوبة، ساعات آلة مطلوبة (ثلاثة أبعاد قيود) — لكنّنا لم نبنِ نموذج اختيار يحترمها كلّها في الوقت نفسه.
- تخطيط الميزانية يستخدم 'رتّب واختر من الأعلى' — لكنّ المشاريع الصغيرة عالية النسبة NPV/وحدة التي تكفيها آخر 5-10% من الميزانية تخسر مكانها.
- اختيار حملات التسويق الرقمي: 30-80 مقترحًا، ميزانية شهرية أو ربعية ثابتة؛ أيّ مجموعة جزئية تُعظِّم الوصول/التحويل؟
- ثمّة تبعيّات بين المرشّحين (المشروع A يخفّض تكلفة B إن اختير؛ المشروعان C وD يستبعد أحدهما الآخر) — knapsack الكلاسيكي لا يلتقطها وتلزم قيود إضافية.
- في اللوجستيات: طائرة شحن أو حاوية ذات سعة محدودة — كلّ طرد له قيمة ووزن؛ تعظيم القيمة الإجمالية دون تجاوز السعة.
- مدير صندوق أسهم صغيرة: كون 200-500 سهم، حجم صندوق ثابت، لكلّ سهم عائد متوقّع وحدّ أدنى لحجم الصفقة؛ أيّ مجموعة جزئية يختار؟
- عقد توريد: 100+ مرشّح، ميزانية شراء سنوية ثابتة؛ لكلّ مورّد حدّ أدنى وأعلى للطلب؛ أيّ مجموعة جزئية تُعظِّم القيمة الإجمالية؟
لماذا تهم
كيف تُحل
عمق تقني
كيف تُحل
عمق تقنيفي جملة واحدة: رتّب المرشّحين بحسب القيمة لكلّ وحدة وزن كبداية جشعة؛ للإجابة الدقيقة شغّل البرمجة الديناميكية (السعة أقلّ من 10K) أو MIP (خاصّةً عند قيود متعدّدة الأبعاد أو تبعيّات) — تخرج أفضل مجموعة جزئية في دقائق.
في أدبيات بحوث العمليات (التخصّص الذي يستخدم الرياضيات والحاسوب لحلّ قرارات الأعمال) وعلوم الحاسوب تُدرَس المسألة باسم Knapsack Problem (مسألة حقيبة الظهر) — N عنصر مرشّح بقيمة (vᵢ) ووزن (wᵢ)؛ سعة W؛ أيّ مجموعة جزئية تُعظِّم Σvᵢ تحت Σwᵢ ≤ W؟ مسألة كلاسيكية تُدرَس منذ الخمسينيات، بحلول معيارية صناعيًّا عبر البرمجة الديناميكية وbranch-and-bound وحلّالات MIP الحديثة. الحلّ في ثلاث مراحل:
1. النمذجة — اختيار النسخة ومدخلات البيانات. عائلة المسألة واسعة؛ التطبيق يحدّد النسخة:
- 0/1 Knapsack (ثنائي): كلّ عنصر يُختار أو لا، بلا تكرار. اختيار مشاريع الاستثمار الكلاسيكي. xᵢ ∈ {0, 1}.
- Bounded Knapsack: عدد محدود من النُسخ لكلّ عنصر (xᵢ ∈ {0, 1, …, cᵢ}). دفعات الموردين.
- Unbounded Knapsack: نُسخ غير محدودة (xᵢ ≥ 0 صحيح). إنتاج محدود السعة، صفقات أسهم بأعداد صحيحة.
- Multi-Dimensional Knapsack (MKP): m قيد؛ لكلّ عنصر أوزان في m بُعدًا (ميزانية + ساعات عمل + ساعات آلة + …). Σⱼwᵢⱼxᵢ ≤ Wⱼ لكلّ j. أصعب بكثير.
- Quadratic Knapsack (QKP): هدف تربيعي مع تفاعلات بين العناصر (تآزر).
- Multiple-Choice Multi-Dimensional Knapsack: عناصر مُجمَّعة؛ يُختار من كلّ مجموعة عنصر واحد بالضبط.
- Subset-Sum: القيمة المستهدفة = الوزن؛ الإجمالي قريب من السعة بقدر المستطاع.
- Knapsack مع Set-Up: اختيار عنصر يستتبع تكلفة إعداد ثابتة (مجموعة). خطوط إنتاج، فتح مصنع.
المدخلات: قائمة المرشّحين N، تقديرات القيمة والوزن (NPV والاستثمار؛ في التسويق قيمة تحويل مُقدَّرة وتكلفة حملة)، السعة W (ميزانية سنوية أو شهرية، حمولة طائرة)، قيود متعدّدة الأبعاد (ساعات عمل، ساعات آلة، ميزانية فرعية بحسب الفئة)، بنية التبعيّات.
2. الحلّ — أدوات الخوارزميات.
- Greedy + تخفيف LP: الأبسط — رتّب بنسبة القيمة/الوزن واختر من الأعلى حتى تمتلئ السعة. لا يضمن المثاليّة (مثال مضادّ كلاسيكي: السعة 10، ثلاثة عناصر (v,w) = (6,5)، (5,4)، (4,3) — greedy 6+5=11، الأمثل 5+4+3=12)؛ تخفيف LP يوفّر الحدّ الأعلى لـbranch-and-bound. مفيد كفحص سريع.
- البرمجة الديناميكية (DP): الخوارزمية شبه متعدّدة الحدود الكلاسيكية (الزمن يعتمد على القيمة العدديّة لـW). الحالة dp[i][w] = أقصى قيمة بالعناصر i الأولى دون تجاوز الوزن w. الانتقال dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ). التعقيد O(N×W). N = 1000، W = 100.000 وحدة TRY = 10⁸ عمليّة، ثوانٍ على أجهزة حديثة. الواقع العملي: نُسخ متوسّطة (N ≤ 1000، W ≤ 10⁶) تُحلّ إلى الأمثل في دقائق؛ حدس ‘NP-hard فلا تُحلّ’ خاطئ.
- Branch-and-bound (بحث شجري مع تقليم الفروع غير الواعدة): مع تقليم بحدّ LP. تقنية متغيّرات النواة هي حالة الفنّ العملي لـ0/1 knapsack بملايين العناصر.
- MIP (Mixed-Integer Linear Programming — تحسين ببعض المتغيّرات 0/1 وأخرى مستمرّة): أداة طبيعيّة لـMKP والنُسخ ذات التبعيّات. حلّالات MIP مفتوحة المصدر أو تجاريّة تحلّ MKP بـ100-1000 عنصر إلى الأمثل (أو بفجوة صغيرة) في دقائق-ساعات.
- FPTAS (Fully Polynomial-Time Approximation Scheme — لأيّ ε > 0، تقريب (1-ε) في زمن متعدّد الحدود): مع ε = 0.01 يضمن 99% من الأمثل.
- الميتاهيوريستيك (جينية، tabu، simulated annealing): لـMKP الكبير جدًّا أو ذي التبعيّات الكثيفة؛ لا ضمان للأمثل، لكن جودة عمليّة.
اختيار مشاريع الاستثمار (50-200 عنصر، ميزانية واحدة أو 2-4 قيود): MIP أو DP 0/1 يعطي الأمثل في ثوانٍ. MKP كبير جدًّا (500+ عنصر، 5+ قيود): MIP قريبًا من الأمثل أو FPTAS. عمليًّا MIP كافٍ في معظم سيناريوهات المؤسّسات؛ خوارزمية knapsack متخصّصة نادرًا ما تكون ضروريّة.
3. التكامل الميداني وتحليل الحساسيّة. المُخرَج: المجموعة الجزئية المختارة، القيمة الإجماليّة، استخدام كلّ قيد، حساسيّة قائمة على تخفيف LP (أيّ مشروع دخل بشعرة، أيّ مشروع خرج بشعرة). تقرير لجنة الاستثمار: مقترح الاختيار، سيناريوهات بديلة (أيّ مشروع يختلف عند ميزانية ±10%، أيّ يدخل لو خُفِّف قيد ساعات العمل)، إبلاغ صريح للتبعيّات والقيود السياسيّة-الاستراتيجيّة. إعادة تخطيط ربعيّة: تُضاف مقترحات جديدة، يُقارَن NPV الفعلي بالتوقّع، يُحلّ النموذج مجدّدًا.
البدائل
يدوي + جداول
مجانيبلا ترخيص
لمن مناسبة: نطاق صغير، 10-30 مرشّحًا، ميزانية واحدة، تبعيّات بسيطة
- + بلا إعداد
- + سهل لتدخّل اللجنة السياسي-الاستراتيجي
- + كافٍ لمناقشة top-N سريعة
- − الترتيب-والاختيار لا يضمن أفضل مجموعة جزئية — خسارة قيمة 5-15% نموذجيّة
- − القيود متعدّدة الأبعاد لا تُحترَم يدويًّا
- − بنية التبعيّات خشنة (مشاريع ذات أولويّة، أزواج استبعاد متبادل)
- − بلا تحليل حساسيّة (ميزانية ±10%)
حلّال MIP مفتوح المصدر + نموذج داخلي
مفتوح المصدرترخيص مجّاني؛ تطوير داخلي 4-12 أسبوعًا أو 200K-600K TRY استشارات
لمن مناسبة: مؤسّسة بفريق OR/تحليلات، ميزانية سنوية 50M+ TRY
- + بلا رسوم ترخيص
- + نماذج اختيار المشاريع تنطبق جيّدًا على حلّالات مفتوحة المصدر
- + تحليل سيناريوهات سريع (ميزانية، ساعات عمل، سعة)
- + ملكيّة داخلية — النموذج شفّاف، الافتراضات قابلة للتدقيق
- − يلزم متخصّص في التحسين ومهندس بيانات
- − صيانة النموذج داخلية
- − ضوضاء تقدير العائد تظلّ — جودة المُدخَل حاسمة
حلّال MIP تجاري + نموذج داخلي
مؤسسيترخيص سنوي 200K-1.5M TRY (ملاحظة سوق TR)؛ مؤسّسات كبيرة 2-5M TRY
لمن مناسبة: مجموعة قابضة كبيرة، ميزانية سنوية 500M+ TRY، قيود متعدّدة الأبعاد
- + محرّك حلّ بالأمثل بمستوى صناعي
- + حلّ متوازٍ عالي الأداء
- + واجهة نمذجة ناضجة (scripting ودعم لغات النمذجة)
- + دعم صناعي
- − ترخيص مرتفع
- − التطوير الداخلي للنموذج يحتاج متخصّصًا في التحسين
- − خطر الاعتماد على المورّد — نقل النموذج لحلّال آخر 4-12 أسبوعًا
برنامج إدارة محفظة مشاريع مؤسّسي
مؤسسيترخيص سنوي 500K-3M TRY (ملاحظة سوق TR)، حسب الحجم
لمن مناسبة: متعدّد المحافظ، متعدّد الفئات، متعدّد الجغرافيا
- + تدفّق متكامل من المقترح إلى الاختيار
- + بنية التبعيّات (مشاريع ذات أولويّة، أزواج استبعاد، خصم تآزر) قابلة للنمذجة في الواجهة
- + إعادة تخطيط ربعيّة ومقارنة العائد الفعلي مدمجة
- + تقارير لجنة جاهزة
- − ترخيص مرتفع + 6-12 شهر تنفيذ
- − وحدة الحلّ المدمجة عادةً محدودة — قد لا تكفي للمحافظ الكبيرة
- − اعتماد على المورّد
- − التخصيص القطاعي يطيل المشروع
التوصية
اسأل في الاجتماع
- أيّ نُسخ تدعمها وحدة اختيار المشاريع — 0/1 ثنائي، عدد دفعات محدود، ميزانية واحدة، قيود متعدّدة الأبعاد، اختيار بمجموعات، تكلفة إعداد؟
- أيّ طريقة تشغّل الحلّال — حلّال بضمانة الأمثل، برنامج ديناميكي، تقريب، بحث متقدّم؟ كم يستغرق حلّ محفظة من 200-1000 مشروع بقيود متعدّدة؟
- هل بنية التبعيّات (مشاريع ذات أولويّة، أزواج استبعاد، خصم تآزر، تكاليف إعداد) قابلة للنمذجة في الواجهة، أم يجب كتابة القواعد يدويًّا؟
- تحليل حساسيّة — في سيناريوهات ميزانية ±10% أو ساعات عمل ±20%: أيّ مشاريع تتغيّر، وهل التقارير آليّة؟
- هل يمكن نمذجة عدم اليقين في مُدخلات العائد (اختيار تحت عدم اليقين)، أم تقدير نقطي فقط؟
- في الحلول متعدّدة القيود، هل تُذكر النسبة المئوية للانحراف بين القيمة المحقّقة والحدّ النظري الأعلى كي يعرف المستخدم 'أمثل أم قريب من الأمثل'؟
- هل المُخرَج يُنتج مباشرةً تقرير لجنة استثمار — المجموعة المختارة، نسبة الميزانية المستخدمة، القرارات بشعرة؟
- عند انتهاء العقد، بأيّ صيغة معياريّة يمكن تصدير بيانات المشاريع المرشّحة، مدخلات النموذج، تاريخ الحلول وتقارير الحساسيّة؟
تفاصيل تقنية
ملاحظة المحرّر
في الكلام العامّ تُسمَّى المسألة ‘اختيار المشاريع’ أو ‘توزيع الميزانية’ أو ‘تحديد أولويّة الاستثمار’. في الأدبيات اسمها Knapsack Problem (مسألة حقيبة الظهر) — من استعارة ملء حقيبة محدودة السعة بأنفس الحمولة (Dantzig 1957). هي جدّ مسائل الاختيار المنفصل. لا يجب الخلط بينها وبين مسألة تحسين المحفظة (#018 Markowitz متوسّط-تباين): Markowitz يعطي أوزانًا متّصلة (لكلّ أصل حصّة حقيقيّة بين 0% و100% من المحفظة) ويُنمذِج المخاطر عبر التباين والارتباط؛ أمّا knapsack فهو قرار منفصل: اختر أو لا تختر (xᵢ ∈ {0, 1}) ويُعظِّم القيمة تحت الميزانية وNPV. خلف معظم مسائل القرار الكلاسيكيّة يكمن knapsack — اختيار مشاريع الاستثمار، اختيار الحملات، الشحن، اختيار مجموعات الموردين الجزئيّة. مسائل cutting stock (#005، قطع هندسي متعدّد الأبعاد) و3D bin packing (#015، تعبئة حجميّة) أقارب قريبون لكنّها مسائل مختلفة: knapsack يُعظِّم القيمة، cutting stock يُقلِّل عدد البكرات، 3D bin packing يضع الطرود في صناديق. تخطيط التشكيلات (#017) نسخة متخصّصة من knapsack — مقرونة بنموذج طلب على مستوى المنتج.
أكثر نقطة مُهملة في القطاع: الفرق بين DP شبه متعدّدة الحدود وتسمية فئة التعقيد. Knapsack من فئة NP-hard — لا تُعرف خوارزمية متعدّدة الحدود في طول بتّات المُدخَل. يقرأ الممارس ذلك ‘لا يُحلّ’ — خاطئ. تعمل DP عند Bellman بزمن O(N×W) — W هي السعة. في ميزانية الاستثمار W = 50M TRY، لكن نُنمذِج بألف TRY (W = 50.000)؛ مع N = 200، الإجمالي 10⁷ عمليّة، ثوانٍ على عتاد حديث. شبه متعدّدة الحدود: الزمن متعدّد الحدود في قيمة W (وأُسّي في طول بتّاتها). النتيجة: حين تكون W معتدلة (آلاف، عشرات الآلاف) تحلّ DP نسخًا بملايين العناصر إلى الأمثل في دقائق. لا ينبغي القفز في اللجنة إلى ‘لا نستطيع معرفة الأمثل، فلنقرّر حدسًا’ — أدوات knapsack العمليّة (MIP، DP) في متناول الجميع.
النقطة الثانية المُهملة: عدم اليقين في مُدخلات NPV/القيمة. تفترض رياضيّات knapsack مُدخلات قطعيّة. في الواقع تستند تقديرات NPV إلى توقّعات خمس سنوات بانحراف ±20-40%؛ في مشاريع التكنولوجيا الجديدة والتحوّل الرقمي عدم اليقين أكبر. يبتلع حلّال knapsack الكلاسيكي ذلك الغموض ويُعيد مجموعة جزئية واحدة ‘مثلى’؛ وقد تتغيّر المجموعة كلّيًّا تحت NPV ±20%. العلاج: knapsack عشوائي (Bertsimas وSim 2003 تحسين متين، أمثل worst-case ضمن مجموعة عدم يقين للـNPV)، knapsack مع قيود احتماليّة (احتمال تجاوز الميزانية 5% كحدّ أقصى) أو ببساطة تحليل حساسيّة (مشاريع مستقرّة عبر سيناريوهات NPV ±20%). النقطة الثالثة: بنية التبعيّات. يفترض knapsack الكلاسيكي استقلال العناصر — تُجمع القيم. في الواقع ثمّة تآزر (A + B معًا قيمة إضافيّة)، استبعاد متبادل (A xor B)، أسبقيّة (A → B)، خصم سعة (A يجعل B أرخص). تُنمذَج كقيود MIP؛ يجب الخروج من واجهة knapsack القياسيّة إلى MIP أغنى.
خطوة بخطوة — للمتوسّط
المرحلة 1 — قِس أوّلًا، خطّط ثانيًا. آخر 3-5 سنوات من المشاريع المرشّحة (المقبولة + المرفوضة): تقدير NPV المقترح، NPV الفعلي (للمقبولة)، مبلغ الاستثمار، ساعات العمل، ساعات الآلة. إحصاء انحراف NPV بحسب الفئة (توسعة، تحديث، رقمي، تكنولوجيا معلومات) وبحسب الحجم، نسبة المتوقّع/الفعلي، نطاق ±%. وثّق متى في التخطيط السنوي تُثبَّت الميزانية والقيود الأخرى (ساعات العمل، ساعات الآلة، الميزانيات الفرعيّة بحسب الفئة).
المرحلة 2 — استخرج رأس المال المعرفي. بنية التبعيّات النموذجيّة بين المرشّحين (سلاسل الأسبقيّة، أزواج الاستبعاد المتبادل، تآزر خصم السعة). نطاقات موثوقيّة NPV: مشروع قياسي صغير ±10%، تحوّل رقمي ±30-40%، بحث وتطوير ±50%. متطلّبات سياسيّة لميزانيّات الفئات الفرعيّة (توازن إقليمي، تنويع قطاعي).
المرحلة 3 — تجربة. 6-10 أسابيع. في دورة لجنة استثمار سنويّة، شغِّل بالتوازي مع الاختيار الحدسي القائم MIP مفتوح المصدر. اعرض المُخرَجَين جنبًا إلى جنب للمجموعة نفسها من المرشّحين؛ اشرح الفروق (أيّ مشروع اختاره greedy، أيّ MIP، ولِمَ). يبقى القرار للجنة؛ MIP يُقدِّم توصية. معيار النجاح محدّد مسبقًا: محفظة MIP أعلى بـ5% على الأقلّ من NPV greedy.
المرحلة 4 — التوسّع. 6-12 شهرًا للوصول إلى دورة لجنة كاملة بـMIP. إعادة تخطيط ربعيّة (تُضاف مقترحات جديدة، تُزال مشاريع مُلغاة). تحليل حساسيّة سنوي (سيناريوهات ميزانية ±10%). knapsack عشوائي أو متين فقط بعد ترسيخ قاعدة عدم يقين NPV. لجنة استثمار ربعيّة: توصية MIP مقابل المحفظة المُعتمَدة، قائمة القرارات بشعرة، معايرة المتوقّع/الفعلي لـNPV.
المخاطر — ما الذي قد يسوء
- خطأ تقدير NPV/العائد. الحلّ أمثل رياضيًّا لقِيَم NPV المُعطاة؛ لو تغيّرت NPV بـ±20-40% فقد تتبدّل المجموعة المثلى. توسعة متينة أو عشوائيّة أو على الأقلّ تحليل حساسيّة (مشاريع مستقرّة عبر NPV ±20%) إلزاميّة. لمعايرة التوقّعات تتبّع NPV الفعلي / المتوقّع بحسب الفئة عبر الزمن.
- افتراض استقلاليّة المشاريع. يجمع knapsack الكلاسيكي قِيَم العناصر؛ في الواقع ثمّة تآزر (A + B معًا قيمة إضافيّة)، استبعاد متبادل (A xor B)، أسبقيّة (A → B)، خصم سعة (A يجعل B أرخص). تستلزم قيود MIP؛ يجب مغادرة واجهة knapsack القياسيّة.
- تجاهل توزيع المخاطر. يُعظِّم knapsack النقي القيمة الإجماليّة؛ لا يُنمذِج مخاطر المحفظة (تباين، تباين مشترك، مخاطر الذيل). اختيار خمسة مشاريع في القطاع نفسه قد يُعطي NPV عاليًا لكن يجعل المحفظة هشّة أمام صدمة قطاعيّة. تُضاف قيود ميزانيّة فرعيّة بحسب القطاع / الجغرافيا / الفئة، أو يُقرَن اختيار knapsack بمقياس مخاطر من نوع CVaR (#063).
- الإقفال على مورّد وحيد لبرنامج تخطيط الاستثمار. بلا بند تعاقدي لتصدير بيانات المرشّحين، مدخلات النموذج، تاريخ الحلول وتقارير الحساسيّة بصيغة معياريّة سنويًّا، استبدال المورّد يعني تصفير الذاكرة المؤسّسيّة للتخطيط. MIP مفتوح المصدر + نموذج داخلي يمنح استقلاليّة عن المورّد في النطاق المتوسّط.
نظرة فنّيّة إلى الحلّ
| النهج | النطاق النموذجي | زمن الحلّ | ضمان المثاليّة؟ |
|---|---|---|---|
| Greedy (ترتيب بـNPV/الاستثمار) | أيّ | فوري | لا (85-95% من الأمثل نموذجيًّا) |
| الحدّ الأعلى لـLP | أيّ | فوري | لا (حدّ أعلى) |
| البرمجة الديناميكية (Bellman 1957) | متوسّط (N≤1000، W≤10⁶) | ثوانٍ-دقائق | نعم |
| Branch-and-Bound (Martello-Toth 1990) | متوسّط-كبير 0/1 KP | دقائق-ساعات | نعم |
| Expanding Core لـPisinger (1997) | كبير جدًّا 0/1 KP | دقائق | نعم |
| MIP (حلّال عام) | عامّ (MKP، QKP، set-up) | ثوانٍ-ساعات | نعم (ضمن الفجوة) |
| FPTAS (Ibarra-Kim 1975) | كبير جدًّا، تقريب ε مقبول | دقائق | (1-ε) من الأمثل |
| ميتاهيوريستيك (جينية، tabu، SA) | MKP كبير جدًّا، كثيف التبعيّات | دقائق-ساعات | لا، جودة عمليّة جيّدة |
مقارنة نُسخ knapsack:
- 0/1 Knapsack: كلّ عنصر يُختار أو لا. ميزانيات رأس المال الكلاسيكيّة.
- Bounded Knapsack: نُسخ محدودة. دفعات الموردين.
- Unbounded Knapsack: نُسخ غير محدودة. إنتاج بسعة، صفقات أسهم بأعداد صحيحة.
- Multi-Dimensional Knapsack (MKP): m قيد — ميزانية + عمل + آلة + فئة.
- Quadratic Knapsack (QKP): تآزر أو تفاعل ثنائي.
- Multiple-Choice MKP: عناصر مجمّعة، واحد بالضبط لكلّ مجموعة.
- Subset-Sum: الهدف = الوزن؛ الإجمالي قريب من السعة بأكبر قدر.
- Knapsack مع Set-Up: تكلفة إعداد ثابتة لكلّ مجموعة.
اختيار دالّة الهدف:
- الهدف 1 — أقصى قيمة إجماليّة (NPV، قيمة تحويل): كلاسيكي.
- الهدف 2 — أقصى استخدام للميزانية (قريب من subset-sum): انضباط الاستهلاك الكامل.
- الهدف 3 — أقصى قيمة worst-case (عبر مجموعة عدم يقين NPV): تحسين متين Bertsimas-Sim.
- الهدف 4 — أقصى قيمة متوقّعة مع جزاء تباين (عشوائي): knapsack متوسّط-تباين.
نمذجة التبعيّات (في MIP):
- أسبقيّة (A → B): xB ≤ xA.
- استبعاد متبادل (A xor B): xA + xB ≤ 1.
- خصم تآزر: قرار إضافي yA·B.
- تكلفة set-up: قرار إضافي yk لكلّ مجموعة.
- ميزانية فرعيّة للفئة: Σᵢ∈Cwᵢxᵢ ≤ Wc لكلّ فئة C.
مصادر أكاديميّة
مدرجة في الواجهة الأماميّة تحت sources.
المصادر
- Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-288. مصدر مؤسِّس لصياغة LP/IP لـknapsack.
- Bellman, R. (1957). Dynamic Programming. Princeton University Press. الكتاب المؤسِّس للبرمجة الديناميكيّة؛ knapsack هو المثال الكلاسيكي.
- Martello, S. وToth, P. (1990). Knapsack Problems: Algorithms and Computer Implementations. Wiley. كتاب كلاسيكي؛ خوارزميات branch-and-bound، مقارنات تجريبيّة.
- Kellerer, H., Pferschy, U. وPisinger, D. (2004). Knapsack Problems. Springer. مرجع حديث شامل؛ كلّ النُسخ، FPTAS، MKP، QKP.
- Pisinger, D. (1997). A minimal algorithm for the 0-1 knapsack problem. Operations Research, 45(5), 758-767. خوارزمية expanding-core، حالة الفنّ العمليّة.
- Ibarra, O. H. وKim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463-468. المصدر المؤسِّس لـFPTAS لـknapsack.
- مركز رسائل YÖK — كلمات مفتاحيّة ‘sırt çantası’ أو ‘knapsack’ أو ‘proje seçimi’ — 25+ رسالة من الأكاديميا التركيّة. tez.yok.gov.tr
المسرد
- Knapsack Problem
- المسألة المؤسِّسة في التحسين المنفصل: اختيار مجموعة جزئية من N عنصر، لكلٍّ منها قيمة ووزن، لتعظيم القيمة الإجماليّة تحت قيد سعة على الوزن الإجمالي.
- Dynamic Programming
- تقنيّة OR / علوم الحاسوب لحلّ مسائل القرار متعدّدة المراحل عبر التحليل العَودي إلى مسائل فرعيّة متداخلة مع تخزين النتائج الوسيطة؛ قدّمها Bellman (1957).
- MIP
- نموذج تحسين تكون فيه بعض متغيرات القرار أعداداً صحيحة (مثل: عدد الشاحنات، عدد الورديات).
مشاكل ذات صلة
كم من النقد في أيّ صرّاف، وما تواتر إعادة التعبئة — التوازن بين شكاوى الصرّاف الفارغ وكلفة التجميد العالية
إن كنتَ بنكًا تجاريًا أو بنك مشاركة متوسط الحجم يشغّل 50-500 صرّاف آلي، فعليك كلّ صباح أن تجيب عن ثلاثة أسئلة: كم نقدًا يوضع في كلّ صرّاف، كم مرّة يُعاد تعبئة كلّ واحد، وأيّ مسار تسلكه المركبة المدرّعة. كلا الطرفَين مكلِف: نقد زائد داخل الصرّاف يضخّم كلفة الفرصة السنوية بفائدة 5-15% إضافةً إلى قسط التأمين؛ ونقد قليل يُفرِغ الجهاز، فيعجز العميل عن السحب وتأتي الشكاوى وضرر العلامة. ولأنّ مركز تسوّق، وموقف حافلات، وحرمًا جامعيًا، وحيّ مكاتب لها أنماط سحب مختلفة جدًّا، فإنّ قاعدة حدسية من نوع 'الكمّية ذاتها للجميع' تُؤذي الطرفَين معًا. هذه الصفحة موجَّهة إلى فرق عمليات البنوك التي تريد اتّخاذ القرارات الثلاثة معًا واستنادًا إلى البيانات.
ما النسبة من أموالي التي تذهب إلى أي استثمار؟
أحد الأسئلة الأساسية للمؤسسة الصغيرة أو المستثمر الفرد: هناك رأس مال وخيارات استثمار متعددة (أسهم، سندات، عملات، سلع، ودائع، عقارات، إعادة استثمار في العمل)، لكل منها عائد متوقع ومستوى مخاطرة مختلف، وبينها ارتباطات (يهبط أحدها بينما يصعد آخر). ما النسبة المئوية لكل خيار؟ الاسم الرياضي هو Portfolio Optimization Problem. عام 1952 صاغ Harry Markowitz إطار mean-variance — أساس النظرية الحديثة للمحفظة الحائز جائزة نوبل. تعظيم العائد المتوقع مع تقليل التباين (المخاطرة) مسألة برمجة تربيعية.
مدخلات متعدّدة + مخرجات متعدّدة — كيف أقيس الكفاءة النسبية لفروعي أو وحداتي؟
هذه الصفحة موجّهة إليكم إذا كنتم تديرون بنكًا بـ100-500 فرع، أو سلسلة مستشفيات متعدّدة المواقع بـ200-1500 سرير، أو إدارة تعليميّة بمئات المدارس، أو جهة حكوميّة تقارن أداء المحافظات. السؤال الجوهري: أيّ فرع/مستشفى/مدرسة كفؤ وأيّها ليس كذلك — والوحدات غير الكفؤة، أيّ وحدة 'أقران' ينبغي أن تتّخذها مرجعًا وبأيّ مقدار يجب أن تتحسّن؟ كلّ وحدة تستهلك في الوقت نفسه عدّة مدخلات (الموظفون، المساحة، الميزانيّة) وتُنتج عدّة مخرجات (إيرادات، زبائن/مرضى/طلاب، جودة)؛ مؤشّر مفرد مثل 'الإيرادات لكلّ موظّف' لا يلتقط هذه الحقيقة وقد يُظهر وحدة كفؤة على أنّها ضعيفة أو العكس. عند التطبيق السليم — لأنّ مرجعيّة الأقران تقدّم مرجعًا تحسينيًا ملموسًا — يرتفع قبول خطط تحسين الوحدات الضعيفة بنسبة 40-70%، وهو ما يعادل تقريبًا 10-50 مليون TRY هامشًا تشغيليًا سنويًا في شبكة فروع متوسّطة الحجم.