لعبة الإنتاج الخطي

📅 آخر تحديث: ٣١ يوليو ٢٠٢٦
✍️ نُشر في: ٣١ يوليو ٢٠٢٦
📷 يحتوي على 11 صور
الموسوعة الحرة

لعبة الإنتاج الخطي ( لعبة LP ) هي لعبة تضم N لاعبًا، حيث يمكن الحصول على قيمة التحالف من خلال حل مسألة برمجة خطية . تُستخدم هذه اللعبة على نطاق واسع في سياق تخصيص الموارد وتوزيع العوائد. رياضيًا، يوجد m نوعًا من الموارد، ويمكن إنتاج n منتجًا منها. يتطلب المنتج jأكج{\displaystyle a_{k}^{j}}كمية المورد رقم k . يمكن بيع المنتجات بسعر سوقي محدد.ج→{\displaystyle {\vec {c}}}بينما لا تستطيع الموارد نفسها ذلك. يُعطى كل لاعب من اللاعبين N متجهًابأنا→=(ب1أنا،...،بمأنا){\displaystyle {\vec {b^{i}}}=(b_{1}^{i},...,b_{m}^{i})}من الموارد. قيمة التحالف S هي أقصى ربح يمكن أن يحققه باستخدام جميع الموارد التي يمتلكها أعضاؤه. ويمكن الحصول عليها من خلال حل مسألة برمجة خطية مناسبة.P(S){\displaystyle P(S)}على النحو التالي.

v(S)=الأعلىx≥0(ج1x1+...+جنxن){\displaystyle v(S)=\max _{x\geq 0}(c_{1}x_{1}+...+c_{n}x_{n})}

s.ت.أج1x1+أج2x2+...+أجنxن≤∑أنا∈Sبجأنا∀ج=1،2،...،م{\displaystyle st\quad a_{j}^{1}x_{1}+a_{j}^{2}x_{2}+...+a_{j}^{n}x_{n}\leq \sum _{i\in S}b_{j}^{i}\quad \forall j=1,2,...,m}

جوهر

كل لعبة برمجة خطية v هي لعبة متوازنة تمامًا . لذا، فإن كل لعبة فرعية من v لها نواة غير فارغة . يمكن حساب إسناد واحد عن طريق حل المسألة الثنائية لـP(شمال){\displaystyle P(N)}. يتركα{\displaystyle \alpha }ليكن الحل الثنائي الأمثل لـP(شمال){\displaystyle P(N)}العائد الذي يحصل عليه اللاعب i هوxأنا=∑ك=1مαكبكأنا{\displaystyle x^{i}=\sum _{k=1}^{m}\alpha _{k}b_{k}^{i}}يمكن إثبات ذلك من خلال نظريات الازدواجية .x→{\displaystyle {\vec {x}}}يقع في صميم v .

تفسير مهم لعملية الإسنادx→{\displaystyle {\vec {x}}}يعني ذلك أنه في ظل السوق الحالية، تكون قيمة كل مورد j بالضبطαج{\displaystyle \alpha _{j}}على الرغم من أنها لا تُقيّم في حد ذاتها، فإن العائد الذي يجب أن يحصل عليه اللاعب هو القيمة الإجمالية للموارد التي يمتلكها.

مع ذلك، لا يمكن الحصول على جميع القيم المُسندة في جوهر المسألة من الحلول الثنائية المثلى. وقد دارت نقاشات كثيرة حول هذه المسألة. إحدى أكثر الطرق شيوعًا هي دراسة تكرار المسألة الأصلية بمقدار r مرة . ويمكن إثبات أنه إذا كانت القيمة المُسندة u موجودة في جوهر اللعبة المُكررة بمقدار r مرة لجميع قيم r، فإنه يمكن الحصول على u من الحل الثنائي المثلى.

مراجع