- 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) – على المرحلة الأولى، ...، من خلال z N (x N -1 , u N) -on المرحلة ن. من الواضح أن

نحن بحاجة إلى العثور على التحكم الأمثل 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 السابقة، وما إلى ذلك. لذلك، غالبًا ما تسمى المعادلات الوظيفية متكررة (متكررة). علاقات بيلمان.

1. ميزات المهام البرمجة الديناميكية

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

• نحن نعتبر نظامًا يتم تحديد حالته في كل خطوة بواسطة المتجه x t. مزيد من التغييرات في حالتها تعتمد فقط على هذه الدولة xt ولا يعتمد على كيفية وصول النظام إلى هذه الحالة. وتسمى مثل هذه العمليات بالعمليات التي ليس لها تأثير لاحق.
• في كل خطوة، يتم تحديد حل واحد، تحت تأثير النظام الذي ينتقل منه الحالة السابقة 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 حيث تصل وظيفة الهدف إلى قيمة متطرفة. إذا كانت الحالات الأولية والنهائية لمشكلة البرمجة الديناميكية معروفة، فإننا نتحدث عن مشكلة ذات نهايات ثابتة. إذا كانت المناطق الأولية والنهائية معروفة، فإننا نتحدث عن مشكلة ذات نهايات حرة.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

الشكل 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

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

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

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

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

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

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

int** effMatrix;

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

int StringToInt(CString);

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

BOOL fillMatrix();

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

Virtual BOOL DestroyWindow();

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

Virtual BOOL OnInitDialog();

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

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

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

إنت ماكس إندكس؛// الحد الأقصى للمؤشرفي ناقلات الموارد

مرفق int;//enterprise

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

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

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

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

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

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

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

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

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

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

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

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

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

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

نتيجة العرض

1. إدخال بيانات

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

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

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

طلب.

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

كثافة العمليات 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
مخطط كتلة البرنامج
هيكل خوارزمية البرنامج
نتيجة البرنامج
خاتمة
فهرس

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

عمل جيدإلى الموقع">

سيكون الطلاب وطلاب الدراسات العليا والعلماء الشباب الذين يستخدمون قاعدة المعرفة في دراساتهم وعملهم ممتنين جدًا لك.

نشر على http://www.allbest.ru/

مشكلة تخصيص الموارد باستخدام طريقة البرمجة الديناميكية

لتوسيع الطاقة الإنتاجية لثلاث مؤسسات A وB وC، يتم تخصيص عدد معين من وحدات الكهرباء الإضافية بمبلغ x 0 = 8 وحدات. يمكن إطلاق الكهرباء على شكل 1، 2، 3، 4، 5، 6، 7 و 8 وحدات. من خلال استثمار وحدات x i من الكهرباء في تطوير المؤسسة i، يمكنك الحصول على دخل من وحدات i في المؤسسة. يخرج متغيرات مختلفةخ ط (ك) تخصيص الكهرباء الإضافية. أنها تجلب الدخل إلى i (k)، k = 1، n. الخيارات الممكنةوترد تنمية المشاريع في الجدول 1. يجب أن يكون إجمالي الدخل لجميع المؤسسات الحد الأقصى، أي y=؟ ذ أنا (ك)> ماكس

طاولة 1. خيارات تطوير المؤسسة

الخيار ك	المؤسسة أ	المؤسسة ب	المؤسسة ج

رياضي التدريج مهام:

ص=؟ في أنا (ك)> الأعلى

؟X أنا (ك)؟x 0

حل:

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

g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4

طاولة 2. الحلول المثلى المشروطة (الخطوة 3)

ولاية		يتحكم

هناك أربعة احتمالات لاستثمار الأموال - ضوابط من أربع خطوات x C (1) = 0 وحدة، x C (2) = 1 وحدة، x C (3) = وحدتان، x C (4) = 3 وحدات. وتسع حالات ممكنة نظريًا للنظام S 2 قبل تخصيص الأموال للمؤسسة C - حجم الاستثمارات غير الموزعة على المرحلة الثالثة: 0،1،2،3،4،5،6،7،8.

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

الجدول 3: توزيع استثمار البرمجة الديناميكية

يتم ملء جميع الحالات المحتملة التي تسبق المرحلة الثالثة بالمثل. يتم تسليط الضوء على القيم المثلى للمؤشرات بالخط العريض في الجداول.

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

g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4

وبالتالي، بالنسبة للحالة S 1 =3 مع التحكم في الخطوة x A (2) = 1 نحصل على:

g A (S 1)=max k f A +g c ]

الحد الأقصى k 4+g c =4+5=9، حيث نجد من الجدول 1، و g c من الجدول 3. يتم ملء جميع الحالات بالمثل.

طاولة 4. الحلول المثلى المشروطة (الخطوة 2)

ولاية	و أ +ز ج	يتحكم

هنا تنشأ المواقف التي لن يكون فيها الحل الأمثل هو الحل الوحيد، وبالتالي، في الحالة S 1 = 3، ستكون عناصر التحكم في الخطوة x A (2) = 1 و x A (3) = 2 هي الأمثل بشكل مشروط، مما يعطي نفس الشيء. كسب ز ا (س 1)=9

طاولة 5. الحلول الأمثل دون قيد أو شرط (الخطوة 1)

في المرحلة الأولى (الجدول 5) - تخصيص الاستثمارات للمؤسسة ب - توجد حالة سابقة واحدة فقط للنظام، تتوافق مع الحالة الأولية S 0 =8. يتم تحديد الكسب الأمثل غير المشروط بالتعبير:

y * = g B (S 0)= الحد الأقصى k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5

يمكن أن تكون الضوابط المثالية غير المشروطة التي تضمن الحد الأقصى للدخل مختلفة.

مخطط للعثور على الجميع الخيارات المثلىويرد توزيع الاستثمارات بين المؤسسات (الجدول 6) في الشكل 1.

طاولة 6. التوزيع الأمثل للاستثمارات.

الشكل 1. مخطط التوزيع الأمثل للاستثمارات بين المؤسسات

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

تم النشر على موقع Allbest.ru

...

وثائق مماثلة

الخصائص العامةومؤشرات الأداء الاقتصادي للمؤسسات الثلاث محل الدراسة. حل مشكلة تخطيط الإنتاج وتوزيع الاستثمار باستخدام البرمجة الخطية والديناميكية. التحليل المقارن للنتائج.

تمت إضافة الدورة التدريبية في 25/04/2015


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

تمت إضافة الدورة التدريبية في 30/12/2010


طريقة البرمجة الديناميكية ومراحلها الرئيسية. استراتيجية استبدال المعدات الأمثل. تقليل تكاليف بناء وتشغيل المؤسسات. التوزيع الأمثل للموارد في شركة STROYKROVLYA LLC والاستثمارات في PKT Khimvolokno.

تمت إضافة الدورة التدريبية في 01/08/2015


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

أطروحة، أضيفت في 08/07/2013


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

تمت إضافة الدورة التدريبية في 14/01/2011


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

تمت إضافة الاختبار في 15/10/2010


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

تمت إضافة الدورة التدريبية في 12/16/2013


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

تمت إضافة العرض في 12/02/2014


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

أطروحة، أضيفت في 02/11/2017


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

خطة الدرس

الانضباط الأكاديمي الطرق والنماذج الرياضية في الاقتصاد

موضوع الدرس حل مختلف مشاكل عملية DP باستخدام الأساليب الرياضية.

أهداف الدرس

تطوير المهارات في حل مشاكل البرمجة الديناميكية.

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

-غرس الانضباط والعزيمة لدى الطلاب.

معدات الدرسملاحظات محاضرة ف.ب. أجالتسوف "الأساليب الرياضية في البرمجة".

خلال الفصول الدراسية:

وقت التنظيم:

التحقق من الغائبين وملء السجل.

تحديث المعرفة المرجعية: إجابات على الأسئلة الأمنية

ما هي المهام التي تسمى متعددة الخطوات؟

ما الجهاز الرياضي المستخدم لحل المسائل متعددة الخطوات؟

ما هو التحكم الأمثل ش*؟

ما هي خوارزمية الطريقة تقريبيات متتاليةفي دائرتين؟

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

تعلم مواد جديدة:

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

• أطول مشكلة فرعية مشتركة: بالنظر إلى تسلسلين، تحتاج إلى العثور على أطول متتالية فرعية مشتركة.

• مشكلة العثور على أطول متتالية فرعية متزايدة: في ضوء التسلسل، تحتاج إلى العثور على أطول متتالية فرعية متزايدة.

• مشكلة المسافة التحريرية (مسافة Levenshtein): بالنظر إلى سلسلتين، تحتاج إلى العثور على الحد الأدنى لعدد عمليات المسح والاستبدال والإضافات للأحرف التي تحول سلسلة إلى أخرى.

• مشكلة حساب أرقام فيبوناتشي

• مشكلة ترتيب ضرب المصفوفات: بالنظر إلى المصفوفات، ...، من الضروري تقليل عدد العمليات العددية لضربها.

• مشكلة اختيار المسار

• مشكلة اتخاذ القرار المتسلسل

• مشكلة استغلال العمالة

• مشكلة إدارة المخزون

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

• خوارزمية فلويد-وارشال: ابحث عن أقصر المسافات بين جميع رؤوس الرسم البياني الموجه الموزون.

• خوارزمية بيلمان-فورد: ابحث عن أقصر مسار في الرسم البياني الموزون بين رأسين محددين.

• الحد الأقصى لمجموعة القمم المستقلة في شجرة: في حالة وجود شجرة، أوجد الحد الأقصى لمجموعة القمم بحيث لا يكون اثنان منها متصلين بحافة.

مثال: التخصيص الأمثل للموارد

رأس المال 40 مليون روبل. يجب على المستثمر الاستثمار في أربعة مشاريع استثمارية حتى يحصل على الحد الأقصى من الدخل. يوضح الجدول ربحية المشاريع (الاستثمارات مضاعفات 8 ملايين روبل)

ش

الربح من التنفيذ

f4(ش)

f3(ش)

f2(ش)

f1(ش)

55

39

120

115

10 0

120

135

134

14 0

145

158

147

حل:

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

المرحلة 1.

نقوم بتوزيع رأس المال بين أربعة مشاريع وحساب الربح المستلم ل (أنا ), أنا = 8,16,24,32,40.

خطوة واحدة: نقدييستثمرون في المشروع الرابع.

ل(8)= 55

ل(16)=58

ل(24)=90

ل(32)=100

ل(40)=140

الخطوة 2: يتم استثمار الأموال في المشروعين الرابع والثالث.

ش

الربح من التنفيذ

خطوة واحدة

f3(ش)

55

39

10 0

120

14 0

145

الخطوه 3: يتم استثمار الأموال في المشروع الرابع والثالث (الخطوة 2) والثاني.

ش

الربح من التنفيذ

الخطوة 2

و 2(ش)

94

108

120

135

135

175

158

175

134

214

147

المرحلة 2:

في الخطوة الرابعة نختار الحد الأقصى لقيم الربح المتحصل عليها L (40) = 214.

والعودة الى ترتيب عكسيمن جدول إلى جدول (من 4 خطوات إلى 1) نختار قيم الدخل التي يتم عندها الحصول على القيمة 214.

الحد الأقصى للدخل 214 مليون روبل. يمكن الحصول على الأموال المستثمرة من خلال توزيع الأموال على النحو التالي:

مشروع واحد – 0 مليون روبل.

2 مشروع – 24 مليون روبل.

المشروع الثالث – 8 مليون روبل.

4 مشروع – 8 مليون روبل.

توحيد المواد الجديدة:

5. تلخيص الدرس: الاستنتاجات والتقييمات العمل في المنزل:

(2) البند 5.1

Ср12: تكوين واستيعاب محتوى المادة النظرية

توقيع المعلم

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

دعونا نتخيل عملية توزيع الموارد بين الكيانات الاقتصادية كعملية إدارة مكونة من ن خطوة (رقم الخطوة يتزامن مع رقم مشروطالكيان الاقتصادي). دع 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 وحدة تقليدية. عرين. وحدات

خاتمة

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

1. المفاهيم الأساسية

1.1. نموذج البرمجة الديناميكية

1.2. مبدأ المثالية. معادلة بيلمان

2. التخصيص الأمثل للموارد

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

2.2 نموذج تخصيص الموارد ثنائي الأبعاد

2.3 منفصلة نموذج ديناميكيالتخصيص الأمثل للموارد

2.4 مراعاة الآثار اللاحقة لمشاكل التخصيص الأمثل للموارد

خاتمة

قائمة المصادر المستخدمة

الملحق 1. قائمة البرامج لحل مشكلة التخصيص الأمثل للموارد مع المعلمات المحددة. نتائج البرنامج

مقدمة

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

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

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

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

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

1. المفاهيم الأساسية

1.1 نموذج البرمجة الديناميكية

هيا نعطي وصف عامنماذج البرمجة الديناميكية.

يعتبر نظام تسيطر عليهوالتي، تحت تأثير السيطرة، تنتقل من الحالة الأولية

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

الصورة 1

ولاية

الأنظمة بعد كثخطوة ( ك = 1,2 …,ن) يتميز بالمعلمات ، ، ...، والتي تسمى إحداثيات المرحلة.يمكن تمثيل الحالة بنقطة في الفضاء ثلاثي الأبعاد تسمى مساحة المرحلة.يتم تحقيق التحول المستمر للنظام (خطوة بخطوة) بمساعدة بعض الأنشطة،،…، التي تشكل إدارة النظام ، أين يتم التحكم ك-خطوة نقل النظام من حالة إلى أخرى (الشكل 1). الإدارة على كالخطوة الرابعة هي تحديد قيم متغيرات تحكم معينة.

ونحن نفترض من الآن فصاعدا أن حالة النظام في النهاية كثالخطوة تعتمد فقط على الحالة السابقة للنظام

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

تسمى المساواة (1.1). معادلات الدول.المهام

نحن نفترض نظرا.

تحكم متفاوت ش , سوف نحصل على "كفاءات" مختلفة للعملية، والتي سنقوم بتقييمها كميًا من خلال الوظيفة الموضوعية ز , اعتمادا على الحالة الأولية للنظام

ومن التحكم المحدد ش : . (1.2)

مؤشر الأداء كثخطوة من عملية المراقبة التي تعتمد على الدولة

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

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

، فيمكننا أن نفكر في دالة مضافة.

عادة، يتم التحكم في ظروف العملية في كل خطوة

تنطبق بعض القيود. ضوابط تلبية هذه القيود تسمى مقبولة .

يمكن صياغة مشكلة التحسين خطوة بخطوة على النحو التالي: تحديد مجموعة الضوابط الممكنة