مفهوم نماذج اللعبة. مصفوفة الدفع

العمل العملي رقم 3

نماذج نظرية اللعبة

فهم نماذج اللعبة

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

1. خيارات لأفعال اللاعبين.

2. كمية المعلومات التي يمتلكها كل لاعب عن سلوك الشركاء ؛

3. المكسب الذي تؤدي إليه كل مجموعة من الإجراءات.

كقاعدة عامة ، يمكن تحديد المكاسب من الناحية الكمية (على سبيل المثال ، الخسارة - 0 ، الفوز - 1 ، التعادل - ½). اللعبة تسمى غرفة البخارإذا شارك فيه لاعبان ، و مضاعفإذا كان عدد اللاعبين أكثر من اثنين. اللعبة تسمى لعبة محصلتها صفرإذا كان ربح أحد اللاعبين يساوي خسارة الآخر. يسمى اختيار وتنفيذ أحد الإجراءات المنصوص عليها في القواعد نقللاعب. يمكن أن تكون الحركات شخصية أو عشوائية. حركة شخصية- اختيار واع من قبل اللاعب لأحد الإجراءات الممكنة (نقلة في لعبة شطرنج) ، حركة عشوائية- إجراء تم اختياره عشوائيًا (اختيار بطاقة من مجموعة متقطعة).

استراتيجية اللاعبتسمى مجموعة القواعد التي تحدد اختيار تصرفه لكل حركة شخصية ، اعتمادًا على الموقف الحالي. اللعبة تسمى النهائيإذا كان لدى اللاعب عدد محدود من الاستراتيجيات ، و بلا نهاية- غير ذلك.

لحل اللعبة ، أو لإيجاد حل اللعبة، يجب على المرء أن يختار إستراتيجية لكل لاعب تفي بشرط الأمثل ، أي يجب أن يتلقى أحد اللاعبين أقصى فوزعندما يتمسك الآخر باستراتيجيته. في نفس الوقت ، يجب أن يمتلك اللاعب الثاني الحد الأدنى من الخسارةإذا تمسك الأول باستراتيجيته. تسمى هذه الاستراتيجيات الأمثل. الغرض نظرية اللعبة هي تحديد الإستراتيجية المثلى لكل لاعب... عند اختيار الإستراتيجية المثلى ، من الطبيعي أن نفترض أن كلا اللاعبين يتصرفان بشكل معقول من وجهة نظر اهتماماتهم.

مصفوفة الدفع. أسعار اللعبة المنخفضة والعليا

ضع في اعتبارك لعبة نهاية ثنائية. دع اللاعب ألديه مالاستراتيجيات الشخصية التي سنحددها أ 1 ، أ 2 ، ... ، أ م.دع اللاعب بيوجد نالاستراتيجيات الشخصية ، دعنا نحددها ب 1 ، ب 2 ، ... ، ب ن.يقولون أن اللعبة لها بعد م ´ ن... نتيجة اختيار اللاعبين لأي زوج من الإستراتيجيات او ب ييتم تحديد نتيجة اللعبة بشكل فريد ، أي ربح ijلاعب أ(إيجابي أو سلبي) وخسارة (- ij) لاعب الخامس... مصفوفة Р = (a ij)، عناصرها هي المكافآت المقابلة للاستراتيجيات او ب ييسمى مصفوفة الدفعأو مصفوفة اللعبة.

مثال - لعبة "بحث"

لاعب أيمكن أن تختبئ في المخزن 1 - سنقوم بتعيين هذه الإستراتيجية على أنها أ 1أو في قبو 2 - استراتيجية أ 2... لاعب الخامسيمكن أن تبحث عن أول لاعب في القبو 1 - الإستراتيجية في 1، أو في قبو 2 - استراتيجية في 2... إذا كان اللاعب أموجود في الخزنة 1 واكتشفه اللاعب الخامس، بمعنى آخر. يتم تنفيذ بضع استراتيجيات (أ 1 ، ب 1)ثم اللاعب أيدفع غرامة ، أي أ 11= -1. وبالمثل نحصل عليه أ 22= -1. من الواضح أن الاستراتيجيات (أ 1 ، ب 2)و (أ 2 ، ب 1)اعطي اللاعب أالمردود هو 1 ، لذلك أ 12=أ 21= 1. وبالتالي ، نحصل على مصفوفة الدفع

تأمل اللعبة م ´ نمع المصفوفة Р = (a ij)وتحديد الأفضل بين استراتيجيات اللاعب أ... اختيار الاستراتيجية ا، لاعب أيجب أن يحسب أن اللاعب الخامسسوف يجيب على إحدى الاستراتيجيات في jالتي من أجلها مكسب للاعب أالحد الأدنى (لاعب الخامسيسعى إلى "إيذاء" اللاعب أ).

دعونا نشير بواسطة أ أناأصغر مكافأة للاعب أعند اختيار الإستراتيجية الجميع استراتيجيات اللاعب الممكنة الخامس(أصغر رقم في أناالصف الأول من مصفوفة الدفع) ، أي ...

من بين كل الأرقام أ أنااختر الأكبر :. دعنا نطلق على أدنى سعر للعبة ، أو أقصى فوز (ماكسيمين ). هذه مكافأة مضمونة للاعب "أ" لأي إستراتيجية للاعب "ب"... لذلك، .

يتم استدعاء الإستراتيجية المقابلة لقيمة الحد الأقصى استراتيجية maximin... لاعب الخامسمهتم بتقليل أرباح اللاعب أ؛ اختيار استراتيجية ب ي، فإنه يأخذ في الاعتبار أقصى ربح ممكن لـ A. Denote.

من بين جميع الأرقام ، نختار الأصغر ونتصل ب أعلى سعر للعبة ، أو فوز minimax (مينيماكس ). هذه خسارة مضمونة للاعب "ب" لأي إستراتيجية للاعب "أ"... لذلك، .

يتم استدعاء الاستراتيجية المقابلة ل minimax استراتيجية minimax... يسمى المبدأ الذي يملي على اللاعبين اختيار استراتيجيات minimax و maximin الأكثر دقة مبدأ minimax.

الألعاب الإحصائية

في العديد من المهام التي تؤدي إلى اللعب ، يكون سبب عدم اليقين هو نقص المعلومات حول الظروف التي يتم فيها تنفيذ الإجراء. لا تعتمد هذه الشروط على الأفعال الواعية للاعب آخر ، بل تعتمد على الواقع الموضوعي ، الذي يُطلق عليه عادة "الطبيعة". تسمى هذه الألعاب ألعاب الطبيعة (الألعاب الإحصائية).

مهمة

بعد عدة سنوات من التشغيل ، تبين أن المعدات الصناعية موجودة في إحدى الحالات التالية: ب 1 - يمكن استخدام المعدات في العام التالي بعد الصيانة الوقائية ؛ В 2 - لتشغيل الجهاز بدون مشاكل ، يجب استبدال أجزائه وتجميعاته الفردية في المستقبل ؛ ب 3 - المعدات تتطلب إصلاحات كبيرة أو استبدال.

اعتمادًا على الوضع الحالي ، ب 1 ، ب 2 ، ب 3 ، يمكن لإدارة المؤسسة اتخاذ القرارات التالية: أ 1 - لإصلاح المعدات بواسطة متخصصين في المصنع ، الأمر الذي يتطلب تكاليف مقابلة أ 1 = 6 ، أ 2 = 10 ، و 3 = 15 وحدة نقدية ؛ و 2 - استدعاء فريق خاص من المصلحين ، ستكون التكاليف في هذه الحالة ب 1 = 15 ، ب 2 = 9 ، ب 3 = 18 وحدة نقدية ؛ و 3 - استبدال المعدات بأخرى جديدة وبيع المعدات القديمة بقيمتها المتبقية. ستكون التكاليف الإجمالية لنتائج هذا النشاط متساوية ، على التوالي ، مع 1 = 13 ، مع 2 = 24 ، مع 3 = 12 وحدة نقدية.

ممارسه الرياضه

1. بعد أن أعطيت الموقف الموصوف مخطط لعبة ، حدد المشاركين فيه ، وحدد الاستراتيجيات الصرفة الممكنة للأطراف.

2. قم بعمل مصفوفة دفع ، وشرح معنى العناصر a ij من المصفوفة (لماذا هي سلبية؟).

3. لمعرفة القرار بشأن تشغيل المعدات في العام المقبل ، من المستحسن أن توصي إدارة المؤسسة لتقليل الخسائر وفقًا للافتراضات التالية: أ) تظهر الخبرة المكتسبة في المؤسسة في تشغيل معدات مماثلة أن احتمالات الحالات المشار إليها للمعدات هي ، على التوالي ، q 1 = 0.15 ؛ ف 2 = 0.55 ؛ ف 3 = 0.3 (تطبيق معيار بايز) ؛ ب) تُظهر التجربة أن جميع الحالات الثلاثة المحتملة للمعدات محتملة بالتساوي (تطبيق معيار لابلاس) ؛ ج) لا يمكن قول شيء محدد عن احتمالية المعدات (طبّق معايير Wald و Savage و Hurwitz). تم إعطاء قيمة المعلمة g = 0.8 في معيار Hurwitz.

المحلول

1) الموقف الموصوف هو لعبة إحصائية.

الإحصائي هو إدارة المؤسسة ، والتي يمكنها اتخاذ أحد القرارات التالية: إصلاح المعدات بمفردها (الإستراتيجية A1) ، استدعاء المصلحين (الإستراتيجية A2) ؛ استبدل المعدات بأخرى جديدة (الإستراتيجية أ 3).

جانب اللعب الثاني - الطبيعة ، سننظر في مجموعة من العوامل التي تؤثر على حالة المعدات: يمكن استخدام الجهاز بعد الإصلاح الوقائي (الحالة ب 1) ؛ من الضروري استبدال التجميعات الفردية وأجزاء المعدات (الحالة ب 2): مطلوب اصلاحأو استبدال المعدات (الدولة ب 3).

2) لنؤلف مصفوفة الدفع الخاصة باللعبة:

يوضح عنصر مصفوفة السداد a ij تكاليف إدارة المؤسسة إذا تبين ، مع الإستراتيجية المختارة A i ، أن المعدات في الحالة B j. تعتبر عناصر مصفوفة الدفع سلبية ، لأنه بالنسبة لأي استراتيجية يتم اختيارها ، سيتعين على إدارة المؤسسة تحمل التكاليف.

أ) تبين الخبرة المكتسبة في المؤسسة للعمل بشكل مشابه للمعدات أن احتمالات حالات المعدات تساوي q 1 = 0.15 ؛ ف 2 = 0.55 ؛ ف 3 = 0.3.

نمثل مصفوفة الدفع بالشكل:

حيث ، (أنا = 1،3)

وفقًا لمعيار بايز ، فإن الإستراتيجية المثلى هي الإستراتيجية البحتة - i ، والتي تزيد من متوسط ​​العائد للإحصائي ، أي المقدمة = ماكس.

استراتيجية بايز المثلى هي الإستراتيجية أ 1.

ب) تشير التجربة المتاحة إلى أن جميع الحالات الثلاثة المحتملة للمعدات هي متساوية الاحتمال ، أي = 1/3.

متوسط ​​الانتصارات متساوية:

1/3 * (- 6-10-15) = -31/3 "-10.33 ؛

1/3*(-15-9-18) = -42/3 = -14;

1/3 * (- 13-24-12) = -49/3 "-16.33.

استراتيجية لابلاس المثلى هي الإستراتيجية أ 1.

ج) لا يمكن قول شيء محدد عن احتمالات المعدات.

وفقًا لمعيار والد ، يتم اتخاذ الإستراتيجية المثلى لتكون إستراتيجية خالصة تضمن أقصى عائد في أسوأ الظروف ، أي

.

= ماكس (-15 ، -18 ، -24) = -15.

وبالتالي ، فإن الإستراتيجية المثلى هي А 1.

دعونا نبني مصفوفة مخاطر ، أين.

استراتيجية اللاعب هي خطة يقوم بموجبها بالاختيار في أي موقف ممكن ومع أي معلومات واقعية محتملة. بطبيعة الحال ، يتخذ اللاعب القرارات أثناء المباراة. ومع ذلك ، من الناحية النظرية ، يمكن افتراض أن كل هذه القرارات تم اتخاذها من قبل اللاعب مسبقًا. ثم تشكل مجمل هذه القرارات استراتيجيته. اعتمادًا على عدد الاستراتيجيات الممكنة ، يتم تقسيم الألعاب إلى محدودة وغير محدودة. تتمثل مهمة نظرية اللعبة في تطوير توصيات للاعبين ، أي تحديد الإستراتيجية المثلى لهم. الإستراتيجية المثلى هي الإستراتيجية التي ، مع التكرار المتعدد للعبة ، توفر للاعب معين الحد الأقصى لمتوسط ​​العائد الممكن.

أبسط نوع من الألعاب الإستراتيجية هي لعبة لاعبين بمجموع صفر (مجموع مكاسب الطرفين يساوي صفرًا). تتكون اللعبة من حركتين: يختار اللاعب A إحدى إستراتيجياته الممكنة Ai (i = 1 ، 2 ، m) ، ويختار اللاعب B الإستراتيجية Bj (j = 1 ، 2 ،. ، N) ، ويتم إجراء كل اختيار باستخدام الجهل التام باختيار لاعب آخر.

هدف اللاعب A هو تعظيم الوظيفة φ (Ai ، Bj) ، وبالتالي فإن هدف اللاعب B هو تقليل نفس الوظيفة. يمكن لكل لاعب اختيار أحد المتغيرات التي تعتمد عليها قيمة الوظيفة. إذا اختار اللاعب A بعض الاستراتيجيات Ai ، فإن هذا في حد ذاته لا يمكن أن يؤثر على قيمة الوظيفة φ (Ai ، Bj).

تأثير Ai على قيمة القيمة φ (Ai ، Bj) غير مؤكد ؛ لا يحدث اليقين إلا بعد الاختيار ، بناءً على مبدأ التصغير φ (Ai ، Bj) ، بواسطة لاعب آخر من المتغير Bj. في هذه الحالة ، يتم تحديد Bj بواسطة لاعب آخر. دع φ (Ai، Bj) = aij. لنؤلف مصفوفة أ:

صفوف المصفوفة تتوافق مع الاستراتيجيات عاي ، الأعمدة تتوافق مع الاستراتيجيات Bj. تسمى المصفوفة A الدفع أو مصفوفة اللعبة. العنصر aij في المصفوفة هو مكافأة اللاعب A إذا اختار الإستراتيجية Ai واللاعب B اختار الإستراتيجية Bj.

دع اللاعب "أ" يختار بعض الإستراتيجيات ذكاءً ؛ ثم في أسوأ الحالات (على سبيل المثال إذا أصبح الاختيار معروف للاعبج) سيحصل على مكافأة تساوي min aij. توقعًا لمثل هذا الاحتمال ، يجب على اللاعب "أ" اختيار مثل هذه الإستراتيجية من أجل زيادة الحد الأدنى للمكافأة إلى الحد الأقصى:

أ = ماكس دقيقة aij

تسمى القيمة أ - المكافأة المضمونة للاعب أ - بالسعر الأقل للعبة. استراتيجية Аi0 التي تضمن الحصول على a تسمى maximin.

ينطلق اللاعب B ، باختيار استراتيجية ، من المبدأ التالي: عند اختيار استراتيجية معينة Bj ، لن تتجاوز خسارته الحد الأقصى لقيم عناصر العمود j من المصفوفة ، أي أقل من أو يساوي الحد الأقصى aij

النظر في تعيين max aij لـ معان مختلفة j ، يختار اللاعب B بشكل طبيعي مثل هذه القيمة j حيث يتم تقليل خسارته القصوى:

β = min miax aij

تسمى القيمة β السعر الأعلى للعبة ، والإستراتيجية Bj0 المقابلة للمكافأة β تسمى minimax.

الربح الفعلي للاعب A مع الإجراءات المعقولة للشركاء محدود بأسعار اللعبة الأدنى والأعلى. إذا كانت هذه التعبيرات متساوية ، أي

نظرية اللعبة هي تخصص رياضي ، موضوعه طرق اتخاذ القرار في حالات الصراع.

يسمى الوضع نزاعإذا اصطدمت به مصالح عدة أشخاص (عادة شخصين) يسعون وراء أهداف معاكسة. يمكن لكل جانب القيام بعدد من الأنشطة لتحقيق أهدافه ، ونجاح أحد الجانبين يعني فشل الآخر.

حالات الصراع شائعة جدًا في الاقتصاد (العلاقة بين المورد والمستهلك ، والمشتري والبائع ، والمصرفي والعميل). تحدث حالات الصراع في العديد من المجالات الأخرى أيضًا.

تنشأ حالة الصراع من الاختلاف في مصالح الشركاء ورغبة كل منهم في اتخاذ القرارات المثلى التي تحقق الأهداف المحددة إلى أقصى حد. في هذه الحالة ، يجب على كل شخص أن يحسب ليس فقط أهدافه الخاصة ، ولكن أيضًا بأهداف الشريك ، ويأخذ في الاعتبار القرارات غير المعروفة مسبقًا التي سيتخذها الشركاء.

عادة ، يصعب تحليل حالات الصراع بشكل مباشر بسبب العديد من العوامل الثانوية التي تأتي. من أجل إتاحة التحليل الرياضي لحالة الصراع ، يجب تبسيطه ، مع مراعاة العوامل الرئيسية فقط. يسمى نموذج رسمي مبسط لحالة الصراع اللعبةأطراف النزاع - اللاعبين، ونتائج الصراع المكاسب.يمكن تحديد الكسب (أو الخسارة) بشكل نموذجي ؛ على سبيل المثال ، يمكنك تقدير الخسارة على أنها صفر ، والربح واحد ، والسحب على أنه 1/2.

اللعبة عبارة عن مجموعة قواعديصف سلوك اللاعبين. كل مرة تلعب فيها اللعبة بطريقة معينة من البداية إلى النهاية هي حفلة اللعبة.يسمى اختيار وتنفيذ أحد الإجراءات المنصوص عليها في القواعد نقللاعب. يمكن أن تكون الحركات شخصية أو عشوائية. حركة شخصيةهو اختيار واع من قبل اللاعب لأحد الإجراءات الممكنة (على سبيل المثال ، حركة في لعبة شطرنج). حركة عشوائية- يعد هذا أيضًا اختيارًا لأحد الخيارات العديدة ، ولكن هنا لا يتم اختيار الخيار من قبل اللاعب ، ولكن من خلال آلية معينة للاختيار العشوائي (رمي العملات المعدنية ، واختيار بطاقة من مجموعة مختلطة).

إستراتيجيةاللاعب عبارة عن مجموعة من القواعد التي تحدد اختيار أفعاله لكل نقلة شخصية ، اعتمادًا على الوضع الحالي.

إذا كانت اللعبة تتكون من حركات شخصية فقط ، فسيتم تحديد نتيجة اللعبة إذا اختار كل لاعب استراتيجيته الخاصة. ومع ذلك ، إذا كانت هناك حركات عشوائية في اللعبة ، فستكون اللعبة احتمالية ولن يحدد اختيار استراتيجيات اللاعبين بعد نتيجة اللعبة.

بغرض يقرراللعبة ، أو إيجاد حل للعبة ، يجب على المرء أن يختار استراتيجية لكل لاعب تفي بالشرط الأمثلأولئك. يجب أن يتلقى أحد اللاعبين أقصى فوز ،عندما يتمسك الآخر باستراتيجيته. في نفس الوقت ، يجب أن يمتلك اللاعب الثاني الحد الأدنى من الخسارةإذا تمسك الأول باستراتيجيته. تسمى هذه الاستراتيجيات الأمثل. يجب أن تفي الاستراتيجيات المثلى بشرط الاستقرار ، أي يجب أن يكون من غير المربح لأي لاعب أن يتخلى عن استراتيجيته في هذه اللعبة.

الهدف من نظرية اللعبة هو تحديد الإستراتيجية المثلى لكل لاعب.

ضع في اعتبارك لعبة نهاية ثنائية. دع اللاعب أ لديه م الاستراتيجيات الشخصية التي سنحددها أ 1 , أ 2 , ..., أكون ... دع اللاعب الخامس يوجد ن الاستراتيجيات الشخصية ، دعنا نحددها ب 1 , ب 2 , ..., بي ام ... يقولون أن اللعبة لها بعد م × ن ... نتيجة اختيار اللاعبين لأي زوج من الإستراتيجيات

أ i و B j (i = 1 ، 2 ، ... ، م ؛ ي = 1 ، 2 ، ... ، ن)

يتم تحديد نتيجة اللعبة بشكل فريد ، أي ربح ij لاعب أ (إيجابي أو سلبي) وخسارة ( - ل ij ) لاعب الخامس ... افترض القيم OU معروف بأي زوج من الاستراتيجيات (أ i ، ب ج ). مصفوفة ، عناصرها هي المكافآت المقابلة للاستراتيجيات ا و ب ي يسمى مصفوفة الدفعأو مصفوفة اللعبة. الشكل العاميتم عرض مثل هذه المصفوفة في الجدول 3.1.

الجدول 3.1

تتوافق صفوف هذا الجدول مع استراتيجيات اللاعب أ ، والأعمدة لاستراتيجيات اللاعب الخامس ... لنقم بإنشاء مصفوفة دفع للعبة التالية.

تأمل اللعبة م × ن مع المصفوفة P = (a ij) ، i = 1 ، 2 ، ... ، م ؛ ي = 1 ، 2 ، ... ، ن وتحديد أفضل الاستراتيجيات أ 1 , أ 2 , ..., أكون ... اختيار الاستراتيجية ا لاعب أ يجب أن يحسب أن اللاعب الخامس سوف يجيب على إحدى الاستراتيجيات ب ي التي من أجلها مكسب للاعب أ الحد الأدنى (لاعب الخامس يسعى إلى "إيذاء" اللاعب أ ). دعونا نشير بواسطة α أنا ، أصغر مكافأة للاعب أ عند اختيار الإستراتيجية ا لجميع استراتيجيات اللاعب الممكنة الخامس (أصغر رقم في أناالصف الأول من مصفوفة الدفع) ، أي

يتم استدعاء الإستراتيجية المقابلة لقيمة الحد الأقصى استراتيجية maximin... لاعب الخامس مهتم بتقليل أرباح اللاعب أ ؛ اختيار استراتيجية ب ي ، فإنه يأخذ في الاعتبار أقصى ربح ممكن لـ أ ... نشير

الإستراتيجية المقابلة للحد الأدنى تسمى إستراتيجية minimax. يسمى المبدأ الذي يملي على اللاعبين اختيار استراتيجيات minimax و maximin الأكثر "دقة" مبدأ minimax... ينبع هذا المبدأ من الافتراض المعقول بأن كل لاعب يسعى إلى تحقيق هدف مخالف لهدف العدو. دعونا نحدد الأسعار الدنيا والعليا للعبة والاستراتيجيات المقابلة في المشكلة.

إذا كانت أسعار اللعبة العلوية والسفلية هي نفسها ، إذن القيمة الإجماليةأعلى و سعر القاعألعاب α = β = v اتصل السعر الخالص للعبة ، أو على حساب اللعبة ... استراتيجيات minimax المقابلة لسعر اللعبة هي الاستراتيجيات المثلى، وكاملها حل مثالي ، أو قرار اللعبة... في هذه الحالة ، اللاعب أ يحصل على أقصى ضمان (بغض النظر عن سلوك اللاعب الخامس ) يفوز الخامس واللاعب الخامس يحقق الحد الأدنى المضمون (بغض النظر عن سلوك اللاعب أ ) خاسرة الخامس ... يقال أن الحل لهذه اللعبة الاستدامة ، بمعنى آخر. إذا التزم أحد اللاعبين بإستراتيجيته المثلى ، فلن يكون من المربح للآخر أن ينحرف عن استراتيجيته المثلى.

زوج استراتيجيات نظيفة ا و ب ي يعطي الحل الأمثل للعبة إذا وفقط إذا كان العنصر المقابل ij ، هو الأكبر في العمود والأصغر في صفه. مثل هذا الموقف ، إذا كان موجودًا ، يسمى نقطة سرج (على غرار سطح السرج الذي ينحني لأعلى في اتجاه واحد ولأسفل في الاتجاه الآخر).

المفاهيم الأساسية لنموذج إدارة المخزون.

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

دعونا ننظر في الخصائص الرئيسية لنماذج إدارة المخزون.

الطلب... يمكن أن يكون الطلب على المنتج المخزن حتمية(في أبسط الحالات ، ثابت في الوقت المناسب) أو عشوائي.يتم وصف عشوائية الطلب إما بلحظة عشوائية للطلب ، أو بحجم عشوائي للطلب في لحظات محددة أو عشوائية من الوقت.

تجديد المستودع.يمكن إجراء تجديد المستودعات إما بشكل دوري على فترات زمنية معينة ، أو عند استنفاد المخزونات ، أي تقليصها إلى مستوى معين.

حجم الطلب.مع التجديد الدوري والاستنفاد العرضي للمخزون ، قد يعتمد حجم الطلب على الحالة التي تمت ملاحظتها في وقت تقديم الطلب. عادة ما يتم تقديم الطلب بنفس المبلغ عندما يصل المخزون إلى مستوى معين - ما يسمى نقاط النظام.

وقت التوصيل.في نماذج إدارة المخزون المثالية ، من المفترض أن يتم تسليم التجديد المطلوب إلى المتجر على الفور. نماذج أخرى تأخذ في الاعتبار التأخير في التسليم لفترة زمنية ثابتة أو عشوائية.

تكلفة التوصيل.كقاعدة عامة ، من المفترض أن تكلفة كل تسليم تتكون من مكونين - تكاليف لمرة واحدة لا تعتمد على حجم الدُفعة المطلوبة ، والتكاليف التي تعتمد (غالبًا بشكل خطي) على حجم الدُفعة.

تكاليف التخزين.في معظم نماذج إدارة المخزون ، يعتبر حجم المستودع غير محدود عمليًا ، ويعمل حجم المخزون المخزن كقيمة تحكم. في هذه الحالة ، يُعتقد أن تخزين كل وحدة مخزون لكل وحدة زمنية يتم تحصيل رسوم معينة منه.

عقوبة النقص.يتم إنشاء أي مستودع من أجل منع النقص من نوع معينالمنتجات في نظام الخدمة. يؤدي نقص المخزون في الوقت المناسب إلى خسائر مرتبطة بتعطل المعدات ، وعدم انتظام الإنتاج ، وما إلى ذلك. تسمى هذه الخسائر عقوبة العجز.

تسمية الأسهم.في أبسط الحالات ، يُفترض أنه يتم تخزين مخزون من نفس نوع المنتج أو منتج متجانس في المستودع. في المزيد الحالات الصعبةيعتبر مخزون متنوع.

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

معيار فعالية استراتيجية إدارة المخزون المعتمدة هو دالة التكلفة (التكاليف) ،تمثل التكلفة الإجمالية لتوريد المنتج المخزن وتخزينه وتكلفة الغرامات.

تتمثل إدارة المخزون في إيجاد مثل هذه الإستراتيجية للتجديد والاستهلاك مع المخزون ، حيث تأخذ دالة التكلفة حدًا أدنى للقيمة.

دع الوظائف ، والتعبير عنها على التوالي:

تجديد المخزون,

استهلاك المخزون ،

الطلب على المنتج المخزن

لفترة من الزمن.

في نماذج إدارة المخزون ، عادةً ما تُستخدم المشتقات الزمنية لهذه الوظائف ، وتسمى ، على التوالي ،

اللعبة تسمى لعبة محصلتها صفر، أو عدائيإذا كان ربح أحد اللاعبين يساوي خسارة الآخر ، أي. لمهمة كاملة من اللعبة ، يكفي الإشارة إلى قيمة واحدة منهم. إذا أشرنا أ- مكاسب أحد اللاعبين ، ب- كسب الآخر ، ثم في لعبة محصلتها صفر ب = - ألذلك يكفي النظر ، على سبيل المثال ، أ.

يسمى اختيار وتنفيذ أحد الإجراءات المنصوص عليها في القواعد نقللاعب. يمكن أن تكون الحركات شخصية أو عشوائية.

حركة شخصيةهو اختيار واع من قبل اللاعب لأحد الإجراءات الممكنة (على سبيل المثال ، حركة في لعبة شطرنج).

حركة عشوائيةهو إجراء يتم اختياره عشوائيًا (على سبيل المثال ، اختيار بطاقة من مجموعة عشوائية). في عملي ، سأفكر فقط في الحركات الشخصية للاعبين.

إستراتيجيةاللاعب عبارة عن مجموعة من القواعد التي تحدد اختيار الإجراء الخاص به لكل نقلة شخصية ، اعتمادًا على الوضع الحالي. عادة ، أثناء اللعبة ، مع كل نقلة شخصية ، يقوم اللاعب بالاختيار بناءً على الموقف المحدد. ومع ذلك ، من حيث المبدأ ، من الممكن أن يتخذ اللاعب جميع القرارات مسبقًا (ردًا على أي موقف ينشأ). هذا يعني أن اللاعب قد اختار استراتيجية معينة ، والتي يمكن وضعها في شكل قائمة من القواعد أو البرنامج. (هذه هي الطريقة التي يمكنك بها لعب اللعبة بجهاز كمبيوتر). اللعبة تسمى النهائيإذا كان لكل لاعب عدد محدود من الاستراتيجيات ، و بلا نهاية- غير ذلك.

من أجل حل اللعبة أو إيجاد حل للعبة ، من الضروري أن يختار كل لاعب إستراتيجية تفي بالشرط الأمثل، بمعنى آخر. يجب أن يتلقى أحد اللاعبين أقصى فوزعندما يتمسك الآخر باستراتيجيته. في نفس الوقت ، يجب أن يمتلك اللاعب الثاني الحد الأدنى من الخسارةإذا تمسك الأول باستراتيجيته. مثل إستراتيجيةوتسمى أفضل... يجب أن ترضي الاستراتيجيات المثلى أيضًا حالة الاستقرار، بمعنى آخر. يجب أن يكون من غير المربح لأي لاعب أن يتخلى عن استراتيجيته في هذه اللعبة.

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

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

يمكن وصف نفس اللعبة العدائية النهائية بمصفوفات مختلفة تختلف عن بعضها البعض فقط في ترتيب الصفوف والأعمدة.

تأمل اللعبة م x ن مع المصفوفة Р = (a ij) ، أنا = 1،2 ، ... ، م ؛ ي = 1،2 ، ... ، ن وتحديد أفضل الاستراتيجيات أ 1 ، أ 2 ، ... ، أ م... اختيار الاستراتيجية الاعب أيجب أن يحسب أن اللاعب الخامسسوف يجيب على إحدى الاستراتيجيات ب يالتي من أجلها مكسب للاعب أالحد الأدنى (لاعب الخامسيسعى إلى "إيذاء" اللاعب أ). دعونا نشير بواسطة أأنا، أصغر مكافأة للاعب أعند اختيار الإستراتيجية الجميع استراتيجيات اللاعب الممكنة الخامس(أصغر رقم في ط صف مصفوفة الدفع) ، أي

أنا = ij , ي = 1 ، ... ، ن.

من بين كل الأرقام أأنا (أنا = 1،2 ، ... ، م ) اختر الأكبر. لنتصل أأدنى سعر للعبةأو الحد الأقصى للمكافأة (الحد الأقصى). هذا فوز مضمون للاعب. ألاستراتيجية أي لاعب الخامس... لذلك، ، أنا = 1 ، ... ، م; ي = 1 ، ... ، ن

يتم استدعاء الإستراتيجية المقابلة لقيمة الحد الأقصى أقصى استراتيجية... لاعب الخامسمهتم بتقليل أرباح اللاعب أ؛ اختيار استراتيجية ب ي، فإنه يأخذ في الاعتبار أقصى ربح ممكن لـ أ.

دعنا نشير: β أنا = ij , أنا = 1 ، ... ، م

من بين كل الأرقام ب ياختر الأصغر واتصل β أعلى سعر للعبةأو المكاسب minimax (minimax). هذه خسارة مضمونة للاعب الخامس.

لذلك، أنا = 1 ، ... ، م; ي = 1 ، ... ، ن.

يتم استدعاء الاستراتيجية المقابلة ل minimax استراتيجية minimax.

يسمى المبدأ الذي يملي على اللاعبين اختيار استراتيجيات minimax و maximin الأكثر "دقة" مبدأ minimax.ينبع هذا المبدأ من الافتراض المعقول بأن كل لاعب يسعى إلى تحقيق هدف مخالف لهدف العدو.

المحاضرة 9.مفهوم نماذج اللعبة. مصفوفة الدفع.

§ 6 عناصر نظرية اللعبة

6.1 مفهوم نماذج اللعبة.

يسمى النموذج الرياضي لحالة الصراع اللعبة , أطراف النزاع - لاعبين ونتائج الصراع المكاسب .

نقدم لكم كل لعبة رسمية أنظمة , أولئك. نظام شروط يحدد: 1) خيارات لأفعال اللاعبين. 2) مقدار المعلومات التي يمتلكها كل لاعب عن سلوك الشركاء ؛ 3) المكسب الذي تؤدي إليه كل مجموعة من الإجراءات. يمكن تحديد الكسب (أو الخسارة) بشكل نموذجي ؛ على سبيل المثال ، يمكنك تقدير الخسارة على أنها صفر ، والربح واحد ، والسحب على أنه 1/2. يسمى التقييم الكمي لنتائج اللعبة دفع .

اللعبة تسمى غرفة البخار , إذا شارك فيه لاعبان ، و مضاعف , إذا كان عدد اللاعبين أكثر من اثنين. سننظر فقط في الألعاب المزدوجة. أنها تنطوي على لاعبين أو الخامس،التي تتعارض مصالحها ، ونعني باللعبة سلسلة من الإجراءات من الجانب أو الخامس.

اللعبة تسمى لعبة محصلتها صفر ، أو عدائي سماء , إذا كان ربح أحد اللاعبين يساوي خسارة الآخر ، أي. مجموع المكاسب لكلا الطرفين يساوي الصفر. للحصول على مهمة كاملة للعبة ، يكفي الإشارة إلى قيمة واحدة منهم . إذا أشرنا أ- مكاسب أحد اللاعبين ، ب – مكافأة الآخر ، ثم لعبة محصلتها صفر ب = –أ، لذلك يكفي النظر ، على سبيل المثال أ.

يسمى اختيار وتنفيذ أحد الإجراءات المنصوص عليها في القواعد نقل لاعب. يمكن أن تكون التحركات الشخصية و عشوائي . حركة شخصية – إنه اختيار واع من قبل اللاعب لأحد الإجراءات الممكنة (على سبيل المثال ، نقلة في لعبة شطرنج). يتم تنظيم مجموعة الخيارات الممكنة لكل حركة شخصية من خلال قواعد اللعبة وتعتمد على المجموعة الكاملة من الحركات السابقة على كلا الجانبين.

حركة عشوائية – إنه إجراء تم اختياره عشوائيًا (على سبيل المثال ، اختيار بطاقة من مجموعة عشوائية). لكي يتم تحديد اللعبة رياضيًا ، يجب أن تشير قواعد اللعبة إلى كل حركة عشوائية توزيع الاحتمالات النتائج الممكنة.

بعض الألعاب يمكن أن تتكون فقط من حركات عشوائية (ما يسمى بالمقامرة البحتة) أو حركات شخصية فقط (الشطرنج ، لعبة الداما). معظم ألعاب الورق عبارة عن ألعاب مختلطة ، أي أنها تحتوي على حركات عشوائية وشخصية. في المستقبل ، سننظر فقط في الحركات الشخصية للاعبين.

تصنف الألعاب ليس فقط حسب طبيعة حركاتها (شخصية ، عشوائية) ، ولكن أيضًا حسب طبيعة وكمية المعلومات المتاحة لكل لاعب فيما يتعلق بأفعال الآخر. تتكون فئة خاصة من الألعاب مما يسمى بـ "الألعاب ذات معلومات كاملة». لعبة بمعلومات كاملة تسمى اللعبة التي يعرف فيها كل لاعب في كل نقلة شخصية نتائج جميع الحركات السابقة ، الشخصية والعشوائية. من أمثلة الألعاب التي تحتوي على معلومات كاملة الشطرنج ، لعبة الداما ، و لعبة مشهورة"الكفرات والصلبان". لا تنتمي معظم الألعاب ذات الأهمية العملية إلى فئة الألعاب التي تحتوي على معلومات كاملة ، نظرًا لأن عدم اليقين بشأن تصرفات العدو عادة ما يكون عنصرًا أساسيًا في مواقف الصراع.

أحد المفاهيم الأساسية لنظرية اللعبة هو المفهوم إستراتيجية .

إستراتيجية اللاعب عبارة عن مجموعة من القواعد التي تحدد اختيار الإجراء الخاص به لكل نقلة شخصية ، اعتمادًا على الوضع الحالي. عادة ، أثناء اللعبة ، مع كل نقلة شخصية ، يقوم اللاعب بالاختيار بناءً على الموقف المحدد. ومع ذلك ، من حيث المبدأ ، من الممكن أن يتخذ اللاعب جميع القرارات مسبقًا (ردًا على أي موقف ينشأ). هذا يعني أن اللاعب قد اختار استراتيجية معينة ، والتي يمكن وضعها في شكل قائمة من القواعد أو البرنامج. (هذه هي الطريقة التي يمكنك بها لعب اللعبة بجهاز كمبيوتر). اللعبة تسمى النهائي , إذا كان لكل لاعب عدد محدود من الاستراتيجيات ، و بلا نهاية .– غير ذلك.

بغرض يقرر اللعبة , أو تجد حل اللعبة , يجب على المرء أن يختار إستراتيجية لكل لاعب تفي بالشرط الأمثل , أولئك. يجب أن يتلقى أحد اللاعبين أقصى فوز ، عندما يلتزم اللاعب الثاني بإستراتيجيته ، في نفس الوقت ، يجب أن يمتلك اللاعب الثاني الحد الأدنى من الخسارة , إذا تمسك الأول باستراتيجيته. تسمى هذه الاستراتيجيات أفضل . يجب أن تفي الاستراتيجيات المثلى أيضًا بالشرط الاستدامة , أولئك. يجب أن يكون من غير المربح لأي لاعب أن يتخلى عن استراتيجيته في هذه اللعبة.

إذا تكررت اللعبة عدة مرات ، فقد لا يكون اللاعبون مهتمين بالفوز والخسارة في كل لعبة معينة ، أمتوسط ​​الربح (الخسارة) في جميع الأطراف.

الهدف من نظرية اللعبة هو تحديد الإستراتيجية المثلى لكل لاعب.

6.2 مصفوفة الدفع. أسعار اللعبة المنخفضة والعليا

اللعبة النهائية التي يلعب فيها اللاعب ألديها تيالاستراتيجيات واللاعب ب - صالاستراتيجيات تسمى لعبة.

تأمل اللعبة
لاعبان أو الخامس("نحن" و "العدو").

دع اللاعب ألديه تيالاستراتيجيات الشخصية التي سنحددها
... دع اللاعب الخامسيوجد نالاستراتيجيات الشخصية ، دعنا نحددها
.

دع كل جانب يختار استراتيجية محددة ؛ بالنسبة لنا سيكون للعدو ... نتيجة اختيار اللاعبين لأي زوج من الإستراتيجيات و (
) يتم تحديد نتيجة اللعبة بشكل فريد ، أي ربح لاعب أ(إيجابي أو سلبي) وخاسر
لاعب الخامس.

افترض القيم معروفون بأي زوج من الاستراتيجيات ( ,). مصفوفة
,
, عناصر منها المكاسب المقابلة للاستراتيجيات و , اتصل مصفوفة الدفع أو مصفوفة اللعبة. تتوافق صفوف هذه المصفوفة مع استراتيجيات اللاعب أ،والأعمدة لاستراتيجيات اللاعب ب... تسمى هذه الاستراتيجيات استراتيجيات نظيفة.

مصفوفة اللعبة
يشبه:

تأمل اللعبة
مع المصفوفة

وتحديد أفضل الاستراتيجيات
. اختيار الاستراتيجية , لاعب أيجب أن يحسب أن اللاعب الخامسسوف يجيب على إحدى الاستراتيجيات , التي من أجلها مكسب للاعب أالحد الأدنى (لاعب الخامسيسعى إلى "إيذاء" اللاعب أ).

دعونا نشير بواسطة أصغر مكافأة للاعب أعند اختيار الإستراتيجية لجميع استراتيجيات اللاعب الممكنة الخامس(أصغر رقم في أناالصف الأول من مصفوفة الدفع) ، أي

(1)

من بين كل الأرقام (
) اختر الأكبر:
.

لنتصل
السعر الأدنى للنجرا ، أو أقصى فوز (maxmin). هذا هو الفوز المضمون للاعب "أ" لأي إستراتيجية للاعب "ب". لذلك،

. (2)

يتم استدعاء الإستراتيجية المقابلة لقيمة الحد الأقصى استراتيجية maximin . لاعب الخامسمهتم بتقليل أرباح اللاعب أ،اختيار استراتيجية , يأخذ في الاعتبار أقصى ربح ممكن في هذه الحالة ل أ.نشير

. (3)

من بين كل الأرقام اختر الأصغر

و اتصل أعلى سعر للعبة أو فوز minimax (مينيماكس). يضمن Ego خسارة اللاعب "ب" . بناء على ذلك،

. (4)

يتم استدعاء الاستراتيجية المقابلة ل minimax استراتيجية minimax.

يسمى المبدأ الذي يملي على اللاعبين اختيار استراتيجيات minimax و maximin الأكثر "دقة" مبدأ minimax . ينبع هذا المبدأ من الافتراض المعقول بأن كل لاعب يسعى إلى تحقيق هدف مخالف لهدف العدو.

نظرية.لا يتجاوز السعر الأدنى للعبة دائمًا السعر الأعلى للعبة
.

إذا كان السعران العلوي والسفلي للعبة متماثلين ، فإن القيمة الإجمالية لأسعار اللعبة العلوية والسفلية
اتصل السعر الخالص للعبة ، أو على حساب اللعبة. استراتيجيات minimax المقابلة لسعر اللعبة هي الاستراتيجيات المثلى , وكاملها - حل مثالي أو بقرار اللعبة. في هذه الحالة ، اللاعب أيحصل على أقصى ضمان (بغض النظر عن سلوك اللاعب الخامس)ربح الخامسواللاعب الخامسيحقق الحد الأدنى المضمون (بغض النظر عن سلوك اللاعب أ)خاسرة الخامس... يقال أن الحل لهذه اللعبة الاستدامة , أولئك. إذا التزم أحد اللاعبين بإستراتيجيته المثلى ، فلن يكون من المربح للآخر أن ينحرف عن استراتيجيته المثلى.

إذا كان أحد اللاعبين (على سبيل المثال أ)يلتزم بإستراتيجيته المثلى واللاعب الآخر (الخامس)سوف تنحرف عن استراتيجيتها المثلى بأي شكل من الأشكال ، إذن لا يمكن أن تكون مربحة على الإطلاق للاعب الذي ينحرف ؛مثل هذا الانحراف لاعب الخامسقد يترك المكاسب في أحسن الأحوال دون تغيير. وفي أسوأ الأحوال ، زدها.

على العكس من ذلك ، إذا الخامستلتزم بإستراتيجيتها المثلى ، و أينحرف عن نفسه ، فلا يمكن بأي حال من الأحوال أن يكون مفيدًا له أ.

زوجان من الاستراتيجيات النظيفة و يعطي الحل الأمثل للعبة إذا وفقط إذا كان العنصر المقابل هو الأكبر في العمود والأصغر في صفه. مثل هذا الموقف ، إذا كان موجودًا ، يسمى نقطة سرج. في الهندسة ، تسمى نقطة على سطح لها خاصية الحد الأدنى المتزامن على طول إحداثي واحد والحد الأقصى على طول الآخر سرج النقطة ، عن طريق القياس يستخدم هذا المصطلح في نظرية اللعبة.

لعبة من أجلها
, اتصل لعبة نقطة السرج. جزء امتلاك هذه الخاصية ، نقطة السرج للمصفوفة.

لذلك ، لكل لعبة بنقطة سرج ، يوجد حل يحدد زوجًا من الإستراتيجيات المثلى لكلا الجانبين ، والتي لها الخصائص التالية.

1) إذا التزم كلا الجانبين بإستراتيجياتهما المثلى ، فإن متوسط ​​العائد يساوي صافي سعر اللعبة الخامس، وهي في نفس الوقت أسعارها الأدنى والأعلى.

2) إذا التزم أحد الطرفين باستراتيجيته المثلى ، وانحرف الآخر عن استراتيجيته ، فلا يمكن للجانب المنحرف إلا أن يخسر من هذا ولا يمكنه بأي حال من الأحوال زيادة مكاسبه.

فئة الألعاب ذات السرج ذات أهمية كبيرة من وجهة نظر نظرية وعملية.

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