ডাইনামিক প্রোগ্রামিং

যদি উপ-সমস্যাগুলিকে পুনরাবৃত্তিয়ভাবে বৃহৎ সমস্যার মধ্যে আবদ্ধ করা যায় যাতে করে ডাইনামিক প্রোগ্রামিং এর পদ্ধতিগুলি এর ওপর প্রয়োগযোগ্য হয়, তাহলে বৃহত্তর সমস্যার মান ও ক্ষুদ্রতর সমস্যাগুলির মানের মাঝে একটি সম্পর্ক রয়েছে বলে ধরে নেয়া যেতে পারে। গাণিতিক অপ্টিমাইযেশন বিদ্যায় এই সম্পর্ককে বলা হয় বেলম্যান সমীকরণ।

গাণিতিক অপ্টিমাইজেশান

গাণিতিক অপ্টিমাইজেশানের পরিভাষায়, ডাইনামিক প্রোগ্রামিং এর সাহায্যে সাধারণত বোঝানো হয়, কোন একটি বৃহৎ বিষয়ে সিদ্ধান্ত গ্রহণকে সময়ের সাথে সাথে ভেঙে একাধিক ছোট ছোট সিদ্ধান্ত গ্রহণের পদক্ষেপে বিভক্ত করার প্রক্রিয়া। মনে করি, মূল্যমান ফাংশনের একটি অনুক্রম V₁, V₂, ..., V_n এবং সময় i=1 হতে n পর্যন্ত সিস্টেমের অবস্থা নির্দেশকারী y কে উক্ত অনুক্রম আর্গুমেন্ট হিসেবে গ্রহণ করে। n সময়ে y অবস্থার প্রাপ্ত মানের দ্বারা V_n(y) কে সংজ্ঞায়িত করা হয়।

নিয়ন্ত্রণ তত্ত্ব

নিয়ন্ত্রণ তত্ত্বে একটি চিরাচরিত সমস্যা হচ্ছে, কোন একটি সিস্টেম ${\displaystyle {\dot {\mathbf {x} }}(t)=\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)}$ কে অবিচ্ছিন্ন সময় অন্তর ${\displaystyle t_{0}\leq t\leq t_{1}}$ এর মাঝে গ্রহণযোগ্য আবক্র পথ ${\displaystyle \mathbf {x} ^{\ast }}$ অনুসরণ করে এবং একটি কস্ট ফাংশন মিনিমাইজে বাধ্য করতে গেলে যে গ্রহণযোগ্য নিয়ন্ত্রণ ${\displaystyle \mathbf {u} ^{\ast }}$ দরকার সেটি বের করা।

${\displaystyle J=b\left(\mathbf {x} (t_{1}),t_{1}\right)+\int _{t_{0}}^{t_{1}}f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)\mathrm {d} t}$ 

এই সমস্যার সমাধান হল, একটি সন্তোষজনক নিয়ন্ত্রণ বিধি অথবা বিধান ${\displaystyle \mathbf {u} ^{\ast }=h(\mathbf {x} (t),t)}$ এর ব্যবস্থা করা, যা একটি সন্তোষজনক আবক্রপথ ${\displaystyle \mathbf {x} ^{\ast }}$ এবং উন্নততর ক্ষতি-ফাংশন ${\displaystyle J^{\ast }}$ এর সৃষ্টি করে। শেষোক্ত ফাংশন ডাইনামিক প্রোগ্রামিং এর মৌলিক সমীকরণ মেনে চলে:

${\displaystyle -J_{t}^{\ast }=\min _{\mathbf {u} }\left\{f\left(\mathbf {x} (t),\mathbf {u} (t),t\right)+J_{x}^{\ast {\mathsf {T}}}\mathbf {g} \left(\mathbf {x} (t),\mathbf {u} (t),t\right)\right\}}$ 

একটি আংশিক ব্যবকলনীয় সমীকরণ যেটি হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণ হিসেবে পরিচিত যেখানে ${\displaystyle J_{x}^{\ast }={\frac {\partial J^{\ast }}{\partial \mathbf {x} }}=\left[{\frac {\partial J^{\ast }}{\partial x_{1}}}~~~~{\frac {\partial J^{\ast }}{\partial x_{2}}}~~~~\dots ~~~~{\frac {\partial J^{\ast }}{\partial x_{n}}}\right]^{\mathsf {T}}}$  এবং ${\displaystyle J_{t}^{\ast }={\frac {\partial J^{\ast }}{\partial t}}}$ . ${\displaystyle t}$ , ${\displaystyle \mathbf {x} }$ , এবং অজ্ঞাতনামা ফাংশন ${\displaystyle J_{x}^{\ast }}$ এর সাপেক্ষে ${\displaystyle \mathbf {u} }$ এর লঘুকরণ করে প্রাপ্ত ফলাফল হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রতিস্থাপন করে আংশিক ব্যবকলনীয় সমীকরণটির সমাধান সীমানা শর্ত ${\displaystyle J\left(t_{1}\right)=b\left(\mathbf {x} (t_{1}),t_{1}\right)}$  হতে পাওয়া যেতে পারে। কার্যক্ষেত্রে, এর জন্য সাধারণত সংখ্যাগত কৌশলের প্রয়োজন পড়ে যাতে করে নিখুঁত অপ্টিমাইজেশন সম্পর্কের বিযুক্ত (ডিসক্রিট) আসন্নায়ন (অপ্টিমাইজেশন) সম্ভবপর হয়। বিকল্পভাবে, এই চলমান প্রক্রিয়াটিকে একটি বিযুক্ত ব্যবস্থার মাধ্যমে অনুমান করা সম্ভব, যা হ্যামিল্টন – জ্যাকোবি – বেলম্যান সমীকরণে প্রাপ্ত অবস্থার সাথে সামঞ্জস্যপূর্ণ একটি পুনরাবৃত্তিয় সম্পর্কের সৃষ্টি করে:

${\displaystyle J_{k}^{\ast }\left(\mathbf {x} _{n-k}\right)=\min _{\mathbf {u} _{n-k}}\left\{{\hat {f}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)+J_{k-1}^{\ast }\left({\hat {g}}\left(\mathbf {x} _{n-k},\mathbf {u} _{n-k}\right)\right)\right\}}$ 

যেখানে ${\displaystyle k}$ -তম ধাপে ${\displaystyle n}$ টি সমভাবে বিস্তৃত বিযুক্ত সময় অন্তরে, ${\displaystyle {\hat {f}}}$ এবং ${\displaystyle {\hat {g}}}$ যথাক্রমে ${\displaystyle f}$  and ${\displaystyle \mathbf {g} }$ এর বিযুক্ত অনুুমানকে নির্দেশ করে। এই ফাংশনাল সমীকরণকে বেলম্যান সমীকরণ বলা হয়ে থাকে, যেটি সমাধান করে অনুকূলকরণ (অপ্টিমাইজেশান) সমীকরণের বিযুক্ত অনুমানের নিখুঁত একটি সমাধান পাওয়া সম্ভব।

 

অর্থনৈতিক উদাহরণ: রামজের সন্তোষজনক সঞ্চয়ের সমস্যা

অর্থনীতিতে, সাধারণভাবে লক্ষ্য হচ্ছে কোন ডাইনামিক সামাজিক কল্যান ফাংশনের সর্বাধিকরণ (লঘিষ্ঠকরণের পরিবর্তে)। রামজের সমস্যায়, এই ফাংশনটি ব্যয়ের সাথে উপযোগের একটি সম্পর্ক স্থাপন করে। ঢিলেঢালাভাবে বলতে গেলে, পরিকল্পনাকারীকে সমসাময়িক ব্যয় এবং ভবিষ্যত ব্যয়ের মাঝে একটি ভারসাম্য সৃষ্টি করতে হয় (বিনিয়োগের মূলধন যেটি উৎপাদনে ব্যবহৃত হয় তার মাধ্যমে) যেটি অন্তর্বর্তীকালীন বিকল্প নামে পরিচিত। ভবিষ্যত ব্যয় একটি নির্দিষ্ট ${\displaystyle \beta \in (0,1)}$ হারে ছাড়প্রাপ্ত হয়। মূলধনের রুপান্তরের একটি বিযুক্ত অনুমান নিচের সমীকরণের সাহায্যে দেয়া যায়:

${\displaystyle k_{t+1}={\hat {g}}\left(k_{t},c_{t}\right)=f(k_{t})-c_{t}}$ 

যেখানে ${\displaystyle c}$  ব্যয়, ${\displaystyle k}$  পুঁজি, এবং ${\displaystyle f}$  একটি উৎপাদন ফাংশন যেটি ইনাদার শর্তসমূহকে পূরণ করে। একটি মূলধন ${\displaystyle k_{0}>0}$  ধরে নেয়া হয়।

কম্পিউটার প্রোগ্রামিং

একটি সমস্যাকে ডায়নামিক প্রোগ্রামিং এর মাধ্যমে সমাধানের জন্য অবশ্যই দুটি মূল বৈশিষ্ট্য থাকতে হবে : অপটিমাল সাবস্ট্রাকচার এবং ওভারল্যাপিং সাব-প্রবলেম। যদি এমন হয় যে, ওভারল্যাপ করে না এমন সাব-প্রবলেমগুলোর সর্বোত্তম সমাধানগুলি একত্রিত করে কোনও সমস্যার সমাধান করা যায়, তবে কৌশলটিকে ডায়নামিক প্রোগ্রামিং এর পরিবর্তে "ডিভাইড অ্যান্ড কনকোয়ার" (বিভাজন এবং বিজয়ন) বলা হয়। একারণে মার্জ সর্ট এবং কুইক সর্ট কে ডাইনামিক প্রোগ্রামিং হিসাবে ধরা হয়না।