البرمجة الديناميكية. مشكلة التخصيص الأمثل للموارد

01.05.2019

نظرية مختصرة

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

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

السمات النموذجية للمشاكل متعددة الخطوات.

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

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

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

4. يمكن فرض قيود على الدولة والسيطرة على النواقل التي يشكل اتحادها منطقة الحلول الممكنة.

5. يجب إيجاد مثل هذا التحكم المقبول لكل خطوة من أجل الحصول على القيمة القصوى لدالة الهدف لجميع الخطوات.

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

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

يمكننا صياغة المبادئ التالية التي تقوم عليها البرمجة الديناميكية: مبدأ المثالية ومبدأ الانغماس.

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

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

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

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

من الضروري إيجاد التحكم الأمثل بحيث يوفر الحد الأقصى للوظيفة الموضوعية في ظل القيود.

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

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

لنبدأ من المرحلة الأخيرة. لتكن الحالات المحتملة للنظام في بداية المرحلة الرابعة. نجد:

بالنسبة للمرحلتين الأخيرتين نحصل على:

على نفس المنوال:

…………………….

التعبير (5) هو تمثيل رياضي لمبدأ المثالية. التعبير (4) هو الشكل العام لكتابة القيمة المثلى المشروطة لدالة الهدف للمراحل المتبقية. تسمى التعبيرات (1) - (5) بمعادلات بيلمان الوظيفية. طبيعتها المتكررة (العودة) واضحة للعيان، أي. للعثور على التحكم الأمثل في الخطوات، عليك معرفة التحكم الأمثل المشروط في المراحل السابقة، الخ. ولذلك، تسمى المعادلات الوظيفية في كثير من الأحيان علاقات بيلمان المتكررة.

مثال على حل المشكلة

المهمة

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

مطلوب إيجاد الحل الأمثل لتوزيع الائتمان بين المؤسسات بحيث تصل الزيادة الإجمالية في الإنتاج في جمعية الإنتاج إلى الحد الأقصى.

الأموال المخصصة، مليون وحدة نقدية

شركة

№1

№2

№3

№4

زيادة إنتاج الإنتاج في المنشآت مليون وحدة نقدية.

100

حل المشكلة

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

البرمجة الديناميكية هي بحث متعدد المراحل للحل الأمثل. يعتمد تحسين عملية متعددة الخطوات على مبدأ R. Bellman الخاص بالمثالية.

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

الأموال المخصصة

100

الخطوة 1

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

الخطوة 2

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

الخطوه 3

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

الخطوة 4

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

0 0 0 0 0 20 10 12 12 16 40 31 31 36 37 60 42 43 48 52 80 62 62 67 73 100 76 76 79 85

إجابة

خطة التوزيع الأمثل لـ 100 وحدة من الموارد بين 4 مؤسسات:

وفي هذه الحالة، سيصل إجمالي الزيادة في الإنتاج إلى قيمة قصوى تبلغ 85.

متوسطتكلفة حل الاختبار هي 700 - 1200 روبل (ولكن ليس أقل من 300 روبل للطلب بأكمله). يتأثر السعر بشكل كبير بمدى إلحاح القرار (من يوم إلى عدة ساعات). تكلفة المساعدة عبر الإنترنت للامتحان/الاختبار تبدأ من 1000 روبل. لحل التذكرة.

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

أمثلة على المشاكل ذات الصلة

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

مشكلة البرمجة التربيعية
يوجد مثال على حل مسألة برمجة محدبة من الدرجة الثانية باستخدام طريقة رسومية.

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

هناك قدر معين من الموارد s 0 التي يجب توزيعها بين كيانات الأعمال للأنشطة الحالية خلال الفترة قيد المراجعة (الشهر، الربع، نصف العام، السنة، وما إلى ذلك) من أجل الحصول على إجمالي الحد الأقصى للربح. حجم استثمارات الموارد x i (؛) في أنشطة كل كيان اقتصادي هو مضاعف لقيمة معينة ح. من المعروف أن كل كيان اقتصادي، اعتمادًا على حجم الأموال المستخدمة xi للفترة قيد المراجعة، يحقق ربحًا بمبلغ fi(xi) (لا يعتمد على استثمار الموارد في الكيانات الاقتصادية الأخرى).

دعونا نتخيل عملية توزيع الموارد بين كيانات الأعمال كعملية إدارة مكونة من n خطوة (يتزامن رقم الخطوة مع الرقم الشرطي لكيان الأعمال). دع s k () يكون معلمة حالة، أي. مقدار الأموال المتاحة بعد الخطوة k للتوزيع على كيانات الأعمال المتبقية (n - k). ومن ثم يمكن كتابة معادلات الحالة بالشكل التالي:

دعونا نقدم في الاعتبار الوظيفة - إجمالي الربح الأمثل المشروط المستلم من k-th، (k+1) - th، ...، n-th الكيانات الاقتصادية، إذا كانت الموارد بمبلغ s k-1 () وتم توزيعها على النحو الأمثل بينهما. يمكن عرض مجموعة القرارات الإدارية المحتملة فيما يتعلق بحجم الموارد المخصصة في الخطوة k على النحو التالي: .

ثم المعادلات المتكررة لـ R.E. سيبدو بيلمان (المخطط العكسي) كما يلي:

مثال.هناك قدر معين من الموارد s 0 = 100، والتي يجب توزيعها بين n = 4 كيانات تجارية للأنشطة الحالية خلال الفترة قيد المراجعة (الشهر) من أجل الحصول على إجمالي الحد الأقصى للربح. حجم استثمار الموارد xi (;) في أنشطة كل كيان اقتصادي هو مضاعف للقيمة h=20 ويتم تحديده بواسطة المتجه Q. ومن المعروف أن كل كيان اقتصادي يعتمد على حجم الأموال المستخدمة xi للفترة قيد المراجعة، يحقق ربحًا بمبلغ f i (xi) () (لا يعتمد على استثمار الموارد في كيانات اقتصادية أخرى):

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

حل.لنقم بإنشاء معادلات بيلمان المتكررة (المخطط العكسي):

دعونا نحدد الحدود القصوى المشروطة وفقا لـ (13)؛ وترد نتائج الحساب في الجدول 1.

الجدول 1. حساب الأمثل المشروط







22+20=42


22+33=55	17+42=59



22+46=68	17+55=72	14+59=73







67+20=87

بناءً على نتائج التحسين الشرطي، سنحدد التخصيص الأمثل للموارد:

وبالتالي فإن التخصيص الأمثل للموارد هو:

والتي ستوفر أكبر ربح بمبلغ 87 وحدة تقليدية. عرين. وحدات

إجابة:التخصيص الأمثل للموارد: والذي يوفر أكبر ربح من 87 وحدة تقليدية. عرين. وحدات

خاتمة

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

البرمجة الديناميكية (DP) هي طريقة لإيجاد الحلول المثلى للمشكلات ذات البنية متعددة الخطوات (متعددة المراحل).

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

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

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

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

في التدوين المقبول، يمكن كتابة مبدأ بيلمان الأمثل في شكل رياضي على النحو التالي

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

ينقسم الإجراء الحسابي لطريقة DP إلى مرحلتين: التحسين المشروط وغير المشروط.

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

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

3.1. مشكلة التخصيص الأمثل للموارد

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

يجب اعتبار المهمة المطروحة على أنها متعددة الخطوات.

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

دعونا نستخدم علاقة بيلمان التكرارية (3.1)، والتي تؤدي في هذه المشكلة إلى المعادلات الوظيفية التالية لـ
:

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

في مرحلة التحسين غير المشروط، يتم تحديد الخطة المثلى لتوزيع الموارد بين المؤسسات.

مثال 3.1.

ولزيادة حجم إنتاج المنتجات التي يرتفع الطلب عليها، تم تخصيص أموال قدرها 50 مليون روبل لأربع شركات تابعة لاتحاد الإنتاج. يمكن تخصيص كل مؤسسة: 0، 10، 20، 30، 40 أو 50 مليون روبل. وفي الوقت نفسه، الزيادة السنوية في إنتاج كل من الشركات
والاعتماد على الاستثمار معروف ومبين في الجدول. 3.1.

الجدول 3.1

حجم الأموال المخصصة س(مليون روبل)	الزيادة السنوية في إنتاج المنتج (مليون روبل)، حسب حجم الأموال المخصصة
حجم الأموال المخصصة س(مليون روبل)

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

العمل المختبري

علوم الكمبيوتر وعلم التحكم الآلي والبرمجة

الأموال المخصصة X للمؤسسة التي تحقق الربح في نهاية العام. الوظائف موضحة في جدول: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 حدد مقدار الأموال التي يجب تخصيصها لكل مؤسسة لذلك أن إجمالي الربح يساوي مجموع الأرباح المحصلة من كل مشروع كان الأكبر. السماح بمبلغ الأموال المخصصة لهذه المؤسسة. المعادلات في الخطوة m تحقق الشرط: إما ألا نخصص أي شيء لأي مؤسسة: أو لا أكثر من ذلك...

العمل المخبري 4_2. حل مشكلة تخصيص الموارد باستخدام طريقة البرمجة الديناميكية.

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

معلومات نظرية مختصرة

يتلخص بناء نموذج البرمجة الديناميكية (DP) وتطبيق طريقة DP لحل المشكلة في ما يلي:

اختيار طريقة لتقسيم عملية الإدارة إلى خطوات؛
تحديد معلمات الحالة ومتغيرات التحكم X ك في كل خطوة؛
اكتب معادلات الحالة.
تقديم وظائف موضوعيةك الخطوة الرابعة والدالة الهدف الكلي؛
إدخال الحد الأقصى المشروط (الحد الأدنى) والتحكم الأمثل المشروط في الاعتبارالخطوة الخامسة: .
اكتب DP الرئيسي للدائرة الحسابيةمعادلات بيلمانل و وفقا للقاعدة:

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

أ) و

ب) على طول سلسلة التحكم الأمثل (الحل).

بيان مشكلة البرمجة الديناميكية بشكل عام.

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

و 1 (X)	f2(X)	و 3 (X)	و 4 (X)

تحديد مقدار الأموال التي يجب تخصيصها لكل مؤسسة بحيث يكون إجمالي الربح (المساوي لمجموع الأرباح المتلقاة من كل مؤسسة) هو الأكبر.

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

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

يمكن تمثيل معادلات الحالة ومخطط التوزيع على النحو التالي:

هنا - معلمة الحالة مقدار الأموال المتبقية بعدك -الخطوة، أي. الأموال المتبقية ليتم توزيعها على الباقي (4-ك) الشركات.

دعونا نقدم في الاعتبار وظيفة - الربح الأمثل المشروط الذي تم الحصول عليه من i، (ك +1 )الرابعة،...،المنشآت إذا تم توزيع الأموال فيما بينها على النحو الأمثل). المعادلات في الخطوة الرابعة تحقق الشرط: (أوك نحن لا نخصص أي شيء للمؤسسة: إما ليس أكثر مما لديناالخطوة ك :).

معادلات بيلمان لها الشكل:

يتم حل المعادلات عن طريق التحسين المتسلسل لكل خطوة.

الخطوة 4 يجب استثمار جميع الأموال المتبقية في الخطوة الرابعة في المؤسسة الرابعة، حيث أن الأرباح، وفقا للجدول، تزيد بشكل رتيب. في هذه الحالة، بالنسبة للقيم المحتملة نحصل على:

الخطوه 3 . نحن نضع افتراضات بشأن رصيد الأموال من خلال الخطوة الثالثة: يمكن أن تأخذ القيم 0،1،2،3،4،5 (= 0، إذا تم منح جميع الأموال للمؤسسات الأولى والثانية، وما إلى ذلك). بناءً على ذلك، نقوم باختيار ومقارنة مجموع القيم لقيم مختلفة عند قيم ثابتة. لكل منها الحد الأقصى لهذه القيم هو الربح الأمثل المشروط الذي يتم الحصول عليه من خلال التوزيع الأمثل للأموال بين المؤسسات الثالثة والرابعة. القيم التي تم الحصول عليها مذكورة في الجدول في العمودين 5 و 6 على التوالي.

س ك-1	ك =3	ك =2	ك =1
	و 3 (× 3 )+	و 2 (× 2 )+	و 1 (× 1 )+


	0+4=4 3+0=3	0+4=4 6+0=6	0+6=6 8+0=8
	0+6=6 3+4=7 4+0=4	0+7=7 6+4=10 9+0=9	0+10=10 8+6=14 10+0=10
	0+8=8 3+6=9 4+4=8 7+0=7	0+9=9 6+7=13 9+4=13 11+0=11	0+13=13 8+10=18 10+6=16 11+0=11
	0+13=13 3+8=11 4+6=10 7+4=11 11+0=11	0+13=13 6+9=15 9+7=16 11+4=15 13+0=13	0+16=16 8+13=21 10+10=20 11+6=17 12+0=12
	0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18	0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15	0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18

2 خطوة ك =2. بالنسبة لجميع القيم الممكنة، تكون القيم في العمودين 8 و9 على التوالي؛ المصطلحات الأولى في قيم العمود 7 مأخوذة من الشرط، المصطلحات الثانية مأخوذة من العمود 5 متى.

خطوة واحدة . يتم تنفيذ التحسين الشرطي في الجدول فيك = 1 ل.

إذا، إذن = 5؛ الربح المستلم من أربع مؤسسات، بشرط توزيع = 5 أموال بين المؤسسات الثلاث المتبقية على النحو الأمثل، يساوي.

إذا، إذن = 4؛ إجمالي الربح، بشرط أن يتم توزيع = 4 أموال بين المؤسسات الثلاث المتبقية على النحو الأمثل، يساوي.

وبالمثل، متى، و؛

متى و؛

وبمقارنة القيم التي تم الحصول عليها، نحصل على.

بالحساب نحصل عليه ومن الجدول في العمود 9 نجد. التالي نجد، وفي العمود 6. وأخيرا، و. حل مثالي.

إجابة. الحد الأقصى لإجمالي الربح هو 24 دولارًا أمريكيًا. بشرط أن يتم تخصيص 1 دولار أمريكي لمؤسسة واحدة؛ تم تخصيص مبلغ 2 دولار أمريكي للشركة الثانية؛ المؤسسة الثالثة - 1 دولار أمريكي؛ المؤسسة الرابعة - 1 دولار أمريكي

تنفيذ المهمة فيمايكروسوفت اكسل

يظهر إدخال البيانات الأولية في الجدول في الشكل 1.

رسم بياني 1. إدخال البيانات المصدر في خلايا ورقة العملمايكروسوفت اكسل

2. ترتيب ملء خلايا الجدول:

1). إلى الخلية E 15 أدخل الصيغة INDEX($B$3:$F$8,MATCH($C15,$B$3:$B$8),G$12+1) وانسخ الصيغة في نطاق الخلايا معه 15 إلى ه 35.

2). في الخلية F 15 أدخل الصيغة

INDEX($B$3:$F$8,MATCH($D15,$B$3:$B$8),5) وانسخ الصيغة إلى نطاق الخلايا باستخدامإف 15 إلى إف 35.

3). في الخلية G 15، أدخل الصيغة E 15+ F 15 وانسخ الصيغة إلى النطاق:ز 15 - ز 35.

4). ونجد القيمة القصوى لكل حالة من 0 إلى 5 لهذا الغرض في الخليةح 15 أدخل الصيغة MAX(G15); بعد إدخال الصيغة في الخليةح 16 بحاجة إلى تغيير النطاق منز 16 إلى ز 16: ز 17، الخ. في جميع أنحاء العمود إلى الخليةح 30 (الشكل 2 أ).

3. ابحث عن قيمة التحكم التي تتوافق مع الحد الأقصى لقيمة الدالة لهذا الغرض في الخليةأنا 15 دعنا ندخل الصيغة INDEX($ج 15: ز 15؛مباراة(ح 15؛ز 15;0);1)، انسخ الصيغة في الخليةأنا 16 وزيادة النطاق، مما أدى إلى الخليةأنا 16 نحصل على: INDEX($ج 16: ز 17؛مباراة(ح 16؛ ز 16: ز 17;0);1). بعد ذلك، انسخ الصيغة إلى الخلاياأنا 18، أنا 21، أنا 25، أنا 30 ، زيادة النطاق تدريجيًا (الشكل 2 ب)

الشكل 2 أ. نوع ورقة العمل مع الصيغ،ك =3.

الشكل 2 ب (الجانب الأيمن من ورقة العمل مع الصيغ،ك =3

ونتيجة لذلك نحصل على:

أرز. 3 . نتيجة الخطوة الأولى (ك = 3).

4. حدد النطاقه 15: أنا 35، نفذ الأمرانسخ جي 15 وتنفيذ الأمرإدراج .

5. دعونا نغير صيغة الوظيفة. إلى الخلاياك 15، ك 16، ك 18، ك 21، ك 25، ك 30 ندخل على التوالي القيم القصوى للخطوة السابقة الموجودة في الخلاياح 15، ح 16، ح 18، ح 21، ح 25، ح 30. في الخلايا المتبقية نضع القيم في نفس العمود والمناظرة للخلايا السابقةس ك . :

إلى الخلية K 17 انسخ قيم الخلية K15؛

في الخلايا K19 وK20 قيم K16 وK17؛

في قيم K22:K24 K18:K20؛

في قيم K26:K29 K21:K24؛

في قيم K31:K35 K25:K29؛

ونتيجة لذلك نحصل على:

الشكل 4. نتيجة الخطوة الثانية (ك = 2).

6. حدد نطاقًا من الخلايا J15: ن 35، نفذ الأمرينسخ ، ضع المؤشر في الخليةيا 15، تنفيذ الأمرإدراج . ونتيجة لذلك، نحصل على جدول كامل مع حل لك =1 (الشكل 5)

7. دعونا نشرح النتائج التي تم الحصول عليها: في. بالحساب نحصل عليه ومن الجدول في العمود 12 نجد. التالي نحدد، ومن العمود 6. وأخيرا، و. وبالتالي، فإن القيمة المثلى وقيمة الدالة هي 24 متر مكعب، وهو ما يتوافق مع البيانات التي تم الحصول عليها يدويًا.

الشكل 6. نتيجة الخطوة الثالثة (ك = 1).

تمارين التحكم. خيارات.

1. ومن المقرر أن يتم تنفيذ أنشطة أربع مؤسسات صناعية في العام المقبل. الأموال الأولية بالدولار الأمريكي حجم الاستثمار في كل مؤسسة هو مضاعف 1 دولار أمريكي. مرافق X، المخصصة ك -المؤسسة () تحقق الربح في نهاية العام. الوظائف محددة في جدول:

و 1 (X)	f2(X)	و 3 (X)	و 4 (X)

تحديد مقدار الأموال التي يجب تخصيصها لكل مؤسسة بحيث يكون إجمالي الربح هو الأكبر.

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

و 1 (X)	f2(X)	و 3 (X)

تحديد مقدار الأموال التي يجب تخصيصها لكل مؤسسة بحيث يكون إجمالي الربح هو الأكبر.

بالإضافة إلى أعمال أخرى قد تهمك
58796.		التوقعات الجغرافية	977.5 كيلو بايت
	بحلول نهاية الدرس، ينبغي أن تكون قادرًا على التعرف على الكلمات الجديدة ومجموعات الكلمات في النص وفهمها، وقراءة وفهم الجوهر والتفاصيل على الرغم من الصعوبات الطبيعية.
58797.		المعلومات وعمليات المعلومات. نظام الحساب	128 كيلو بايت
	توصيف زغالني لهؤلاء. قواعد السلامة في حساب PEOM. علوم الكمبيوتر. مفاهيم المعلومات. المعلومات والضوضاء. عمليات المعلومات. المعلومات والإخطار.
58798.		أنظمة التشغيل	126 كيلو بايت
	طاولة العمل. كائنات ويندوز الأساسية. رؤية الكائن. العمليات والسلطات والأوامر الأساسية للعمل مع الكائنات. قائمة سياق الكائن التسميات هي لغرضهم.
58799.		أساسيات الروبوتات مع الأقراص	144.5 كيلو بايت
	توصيف زغالني لهؤلاء. تنسيق القرص. تشخيص وإلغاء تجزئة الأقراص. تحديث المعلومات على القرص. قواعد كتابة وقراءة المعلومات من الأقراص المرنة.
58800.		محرر النص	190 كيلو بايت
	أنظمة معالجة النصوص ووظائفها الرئيسية. إلهام لمحرر النص. واجهة المحرر. صف المعلومات. أوضاع الشاشة، vikoristannia vikon.
58801.		محرر الرسوم البيانية	708 كيلو بايت
	توصيف زغالني لهؤلاء. رسومات الآلة. شاشة رسومية. نظام معالجة المعلومات الرسومية. الإدخالات عبارة عن رسومات للأوليات الرسومية عند العمل مع المحرر. أنواع الملفات الرسومية.
58802.		الجداول الإلكترونية	280.5 كيلو بايت
	نافشالنا. وصف موضوع جديد وإبراز دوره في مقرر علوم الكمبيوتر. أدخل مفهوم الجدول الإلكتروني. تعريف الطلاب ببرامج معالجة ET، وقواعد إدخال المعلومات وتحريرها في ET، وطرق تنسيق ET.
58803.		أنظمة إدارة قواعد البيانات (DBMS)	156.5 كيلو بايت
	تحية أساسية. قاعدة بيانات وثائقية واقعية. Iєrarchical، merezheva، النموذج العلائقي لقاعدة البيانات. العناصر الرئيسية لقاعدة البيانات: الحقل، السجل، الملف. نظام إدارة قواعد البيانات.

- 1.03 ميجابايت

دعونا نعطي صيغة رياضية لمبدأ المثالية. من أجل التبسيط، سنفترض أن الحالة الأولية x 0 والحالة النهائية x T للنظام معطاة. دعونا نشير بواسطة z 1 (x 0 , u 1) إلى قيمة وظيفة الهدف في المرحلة الأولى مع الحالة الأولية للنظام x 0 ومع التحكم u 1 , بواسطة z 2 (x 1 , u 2) المقابلة قيمة وظيفة الهدف فقط في المرحلة الثانية، ..، من خلال
z i (x i -1 ,u i) - في المرحلة i، ...، حتى z N (x N -1 , u N) - في المرحلة N. من الواضح أن

من الضروري العثور على التحكم الأمثل u*= (; ;...;) بحيث يوفر الحد الأقصى للوظيفة الموضوعية (1) تحت القيود.

لحل هذه المشكلة، نغمرها في عائلة متشابهة. دعونا نقدم بعض الرموز. اسمحوا، على التوالي، المناطق

تعريفات لمشاكل مماثلة في المرحلة الأخيرة، والمرحلتين الأخيرتين، وما إلى ذلك؛
- مجال تعريف المشكلة الأصلية. دعونا نشير بـ F 1 (x N -1)، F 2 (x N -2)، ...، F k (x N -k)، ...، F N (x 0)، على التوالي، الأمثل المشروط قيم دالة الهدف في المرحلة الأخيرة، وقيمتين أخيرتين، وما إلى ذلك، عند k أخيرًا، وما إلى ذلك، في جميع مراحل N.

لنبدأ من المرحلة الأخيرة. دع x N-1 هي الحالات المحتملة للنظام في بداية المرحلة N. نجد:

F 1 (x N -1) = z N (x N -1، u N). (2)

بالنسبة للمرحلتين الأخيرتين نحصل عليها

F 2 (x N -2) = (Z N -1 (x N -2، u N -1) + F 1 (x N -1)). (3)

على نفس المنوال:

F 3 (x N -3) = (Z N -2 (x N -3، u N -2) + F 2 (x N -2)). (4)

………………………………………………….

F ك (x N -k) = (z N-k +1 (x N -k , u N-k +1) + F k- 1 (x N-k +1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0، u 1) + F N -1 (x 1)). (6)

التعبير (6) هو تمثيل رياضي لمبدأ المثالية. التعبير (5) هو الشكل العام لكتابة القيمة المثلى المشروطة لدالة الهدف للمراحل المتبقية k. تسمى التعبيرات (2) – (6) بمعادلات بيلمان الوظيفية. طبيعتها المتكررة (المتكررة) مرئية بوضوح، أي للعثور على التحكم الأمثل في خطوات N، تحتاج إلى معرفة التحكم الأمثل المشروط في المراحل N - 1 السابقة، وما إلى ذلك. لذلك، غالبًا ما تسمى المعادلات الوظيفية متكررة (متكررة). علاقات بيلمان.

مميزات مشاكل البرمجة الديناميكية

وبناءً على ما سبق، يمكننا تسليط الضوء على الميزات التالية لمشكلات البرمجة الديناميكية.

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

أي تسلسل صالح للإجراءات لكل خطوة ينقل النظام من الحالة الأولية إلى الحالة النهائية يسمى استراتيجية التحكم. تسمى استراتيجية التحكم التي تؤدي إلى قيمة متطرفة للوظيفة الموضوعية الأمثل.

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

الصورة 1

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

مشكلة توزيع الموارد

2.1 بيان عام للمشكلة

دعونا نفكر في تطبيق طريقة البرمجة الديناميكية باستخدام مثال توزيع الأموال بين ستة كائنات لإعادة الإعمار تابعة لشركة مرافق مياه المدينة:

1. محطة الضخ والترشيح المركزية.

2. محطة الضخ والترشيح الشرقية .

3. محطة ضخ المياه.

4. محطة التهوية المركزية.

5. محطة التهوية الشرقية.

6. محطة تهوية البلد.

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

الجدول 1.1 بيانات الإدخال لإنتاجية كائنات إعادة الإعمار

الرقم التسلسلي للكائن

حجم الموارد المخصصة لتطوير المرافق (بالآلاف غريفنا)

إنتاجية الأشياء نتيجة التطوير (ألف م3)

مخطط كتلة البرنامج

الشكل 1. البرنامج الرئيسي

QtObj – عدد الكائنات

QtRes - عدد الموارد

effMatrix - مصفوفة أداء الكائن،

distVector – ناقل الموارد المخصصة

الخطوة 1: التحسين المشروط

الخطوة 2. التحسين غير المشروط

I = QtObj-1.0 يشكل نتيجة المتجه

الشكل 2. إدخال البيانات

distVector - ناقل المسافة، effMatrix = مصفوفة الأداء

إذا تم إدخال كافة عناصر المصفوفة

إذا لم يكن ناقل الأداء

سلبي

الشكل 3. التحسين المشروط،

نشكل مصفوفة الإخراج (الحد الأقصى لوظيفة الهدف)

outMatrix - الحد الأقصى لمصفوفة الهدف

QtObj – عدد الكائنات

QtRes - عدد الموارد

مصفوفة – مصفوفة الأداء

distVect – ناقل المسافة (ناقل الموارد)

لا نعم إذا كانت المؤسسة الأولى

العثور على الحد الأقصى

نعم maxItem = temp; outMatrix[i][j] = maxItem

هيكل خوارزمية البرنامج

إدخال البيانات – فئة DataDlg.

أفراد الفئة المتغيرة.

// ناقل لتخزين كمية الموارد

الأمراض المنقولة جنسيا::ناقل distVector;

// مصفوفة أداء الكائن

int** effMatrix;

// دالة لتحويل سلسلة إلى رقم

int StringToInt(CString);

// وظيفة للتحقق من صحة البيانات المدخلة

BOOL fillMatrix();

// وظيفة تنظيف الموارد بعد إغلاق النافذة

Virtual BOOL DestroyWindow();

// وظيفة تهيئة الحوار

Virtual BOOL OnInitDialog();

حساب النتائج - الفصل الرئيسي لدورة البرنامجWorkDlg

أفراد الفئة المتغيرة

intValue; // قيمة الأداء

int MaxIndex;// الحد الأقصى للمؤشر في ناقل الموارد

مرفق int;//enterprise

int Resource;//مورد مخصص

العنصر ** outMatrix؛ // الحد الأقصى للمصفوفة المستهدفة

الأمراض المنقولة جنسيا::ناقل resVector; // ناقل النتائج

void BuildOutMatrix(int **,std::vector );//وظيفة إنشاء مصفوفة الأهداف (التحسين المشروط)

afx_msg void OnBnClickedButton1(); // معالج للنقر على الزر "احسب"، الذي يبدأ عملية الحساب.

Virtual BOOL DestroyWindow();// مسح موارد البرنامج

إخراج تقرير فئة النتائج

الغرض من هذه الفئة هو إخراج متجه النتيجة في شكل جدول.

2.4 نتائج البرنامج

إدخال البيانات الأولية

إدخال البيانات الخاصة بإنتاجية كائنات إعادة الإعمار

إذا لم يتم ملء كافة الحقول

إذا تم إدخال حرف غير صحيح

إدخال البيانات بشكل صحيح

نتيجة العرض

إدخال بيانات

نتيجة البرنامج

إدخال البيانات الأولية

إدخال إنتاجية الكائن

طلب.

قائمة البرنامج

كثافة العمليات DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// هل تم ملء جميع الحقول؟

منطقية DataDlg::FillMatrix()

علامة منطقية = صحيح؛

ل (int i = 0؛ i< Cells.GetSize(); i ++){

من أجل (int j = 0؛ j< Cells.GetAt(i)->Edits.GetSize(); ي++)(

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

إذا (درجة الحرارة->m_hWnd != NULL)(

temp->GetWindowText(str);

إذا (str.IsEmpty())(

messageBox(L"تحتاج إلى ملء جميع الحقول"، L"خطأ"، MB_ICONERROR | MB_OK);

وصف العمل

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

محتوى

مقدمة ……………………………………………… 2
البرمجة الديناميكية
المفاهيم الأساسية ............... 4
مبادئ البرمجة الديناميكية. معادلات بيلمان الوظيفية ............... 5
مميزات مشاكل البرمجة الديناميكية………….10
مشكلة تخصيص الموارد .......................... 12
بيان عام للمشكلة ............................ 13
مخطط كتلة البرنامج
هيكل خوارزمية البرنامج
نتيجة البرنامج
خاتمة
فهرس