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

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

لذلك سوف نتطرق في هذا  البحث إلى :

·       مفهوم البرمجة الديناميكية .

·       أهم المفاهيم الرئيسية للبرمجة الديناميكية .

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

مفهوم البرمجة الديناميكية  .

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

 ويمكن توضيح مفهوم البرمجة الديناميكية في النقاط التالية:

 - هي أسلوب تحليلي لتقرير الخطة المثلى لتحقيق أهداف معينة تحت قيود معينة.

- هي مناسبة لتحليل السلوك الرشيد.

 - هي أسلوب لتحديد الخطة المناسبة من بين الخطط البديلة.

 - هي مختلفة عن غيرها من الأساليب كوناه تفترض تقسیم عملیات اتخاذ القرارات إلى خطوات متتالية.

 وعلى ذلك يمكن تعريف البرمجة الديناميكية بأنها :

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

 أهم المفاهيم الرئيسية للبرمجة الديناميكية .

1_  المرحلة: Stage تمثل إحدى الأساسيات التي يتم تقسيم المشكلة الرئيسة عليها ثم تستخرج قيم المتغيرات العائدة لهذه المرحلة .

 2. متغيرات الحالة State Variables: وهي المتغيرات التي تمثل الربط بين المراحل السابقة والمرحلة الحالية أو الربط بين مرحلة الحالية والمرحلة اللاحقة .

3 _ متغيرات القرار Decision variables وهي المتغيرات التي بموجبها يتم تحديد الحل الأمثل بالقياس إلى هدف المشكلة عند كل مرحلة من مراحل المشكلة

4_  السياسة المثلى ( Optimal Policy ): وهي عبارة عن مجموعة من متغيرات القرار التي ستعطي أفضل قيمة لدالة العائد .

 5 _ متغير العائد ( Return variable ): وهي متغيرات قياسية تقيس العائد الكلي المتكون في كل مرحلة.

إذ  تكون هذه المتغيرات دالة القرار  (di) ومتجهات الحالة )(xi ) ويمكن التعبير عن هذه الدالة كما يأتي:

 i=1,2,3.......n           ,  Ri = r(xi,di)     ......(1)           

6_ دالة التحويل ( Transformation Function ): وهي عبارة عن دالة رياضية تظهر العلاقة بين المراحل المختلفة وتساهم بنقل الحل الأمثل من المرحلة الحالية (كمخرجات) إلى مرحلة لاحقة (كمدخلات ) بهدف اتخاذ القرار الأمثل في هذه المرحلة .(هواش، 2016_2017)

7_ المعادلة التكرارية :  The Recursive Equation هي قاعدة لصياغة أي مشكلة أمثلية بواسطة البرمجة الديناميكية. إذ تكشف هذه المعادلة الطبيعة التعاقبية للبرمجة الديناميكية وتعكس بالوقت نفسه المبدأ الأساسي للامثلية الذي ينص على أن السياسة المثلى لها خاصية وهي مهما كانت الحالة الابتدائية والقرار الابتدائي فان القرارات المتبقية يجب أن تكون سياسة مثلي بالرجوع إلى الحالة الناتجة من القرار الأول (بخيث، 2008_2009) .

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

1_ تقسيم المشكلة الرئيسية الى عدد من المشاكل الثانوية الأصغر ويتم التعبير عن حل المشكلة الرئيسية من حيث الحل للمشاكل الفرعية الاصغر تبدأ الحلو الحكيمة من اصغر مشكلة ثانوية .

 2_ تجنب اعادة حساب المشكلة مرتين وغالبا مايتم بناء جدول للنتائج الفرعية للتخزين وتجنب التكرار وترتيب الحل .

3_ الجمع بين الحلول الصغيرة الثانوية للحصول على حلول للمشكلات الثانوية ذات حجم متزايد وتستمر العملية إلى أن نصل إلى حل المشكلة الأصلية .

مواصفات , الوصف الرياضي للبرمجة الديناميكية .

مواصفات البرمجة الديناميكية  متعددة المراحل  

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

 الوصف الرياضي للأداء بالبرمجة

ان حل المشاكل باستعمال البرمجة الديناميكية يتضمن طريقتين :

(1)                       الطريقة الأمامية: أو طريقة الحسابات الأمامية حيث يعتمد هذا الأسلوب على طريقة القيم المرتبطة تصاعديا كما يلي : f1 f2 ….fn

إن هذه الطريقة تعتمد على مبدأ التقدم في العمل إذ يتم حساب قيمة الدالة الأولى F1، ثم الانتقال إلى الدالة الثانية F2 وهكذا حتى نصل إلى الدالة الأخيرة Fn .

 طريقة الحسابات الخلفية: وهي معاكسة للطريقة الأولى إذ تستخدم العلاقة التكرارية في إيجاد الحل الأمثل عن طريق التحرك إلى الخلف مرحلة بمرحلة وفي كل مرحلة يتم ايجاد الخطة المثلى لكل حالة من حالات هذه المرحلة إلى أن نصل إلى المرحلة الأولى وبذلك يتم ترتيب الدوال ترتیبا تنازليا كالآتيFn/Fn-1....../F1 –

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

لتكنFn(ek1) القيمة التي تأخذها الدالة الاقتصادية بعد n مرحلة من التقدم والتحسين المعرفة الحالات المتعاقبة (ek1, ek2......,ekn) والسياسية (d1, d2,......, dn). و gi(eki, di) دالة الإيراد المتعلقة بالمرحلة 1. إذن الدالة الاقتصادية المراد تعظيمها هي كالتالي :

 Fn (ek1)=Max[g1(ek1 ,d1)+g2(ek2,d2)+.....+gn(ekn,dn)] و بالاستناد على معيار الأمثلية البيلمان، فللبحث عن أمثلية هذه الدالة ذات n مجهول نبحث عن أمثلية مجموع n دالة ذات مجهول واحد.( نلاحظ أن المجاهيل ليست مستقلة عن بعضها البعض وإنما حالة النظام في لحظة معينة تابعة لحالة النظام السابق والقرار المتخذ فيه.

ونكتب: Fn(ek1)=Max{g1(ek1,d1 )+Max[g2(ek2,d2)+.....+gn(ekn, dn)]} ويمكن كتابة أيضا: [(Fn(ek1)=Max[g1(ek1,d1)+Fn-1(ek2 Fn-1(ek2)=Max[g2(ek2,d2)+........+gn(ekn, dn)] ( مع بحیث: ek2 هي دالة ل ek1 و d1 ويمكننا كتابة (T1 ، ek2-T1(ek1,d1 و تسمى دالة التحويل. والمرحلتين الأخيرتين (Fn(ek1 و (Fn-1(ek2 تمثل النظام الدالي الأساسي للبرمجة الديناميكية

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

هو C، عدد الاختيارات للمحاور ، حيث أن (i=1,2,...,N) هو Mi وعائد الريح أو الريع Ri أما الكلفة الإضافية المتوقعة من البديل Mi للمحور اهي Ci,mi إن هدف المؤسسة هو اختيار الخطة المجدية المناسبة لكل محور بحيث أن العائد للمحاور جمیعا هو أعظم ما يمكن .