فایل ورد کامل روشی نیمه مدولار برای برنامه نویسی پویای گسسته

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

این مقاله، ترجمه شده یک مقاله مرجع و معتبر انگلیسی می باشد که به صورت بسیار عالی توسط متخصصین این رشته ترجمه شده است و به صورت فایل ورد (microsoft word) ارائه می گردد

متن داخلی مقاله بسیار عالی، پر محتوا و قابل درک می باشد و شما از استفاده ی آن بسیار لذت خواهید برد. ما عالی بودن این مقاله را تضمین می کنیم

فایل ورد این مقاله بسیار خوب تایپ شده و قابل کپی و ویرایش می باشد و تنظیمات آن نیز به صورت عالی انجام شده است؛ به همراه فایل ورد این مقاله یک فایل پاور پوینت نیز به شما ارئه خواهد شد که دارای یک قالب بسیار زیبا و تنظیمات نمایشی متعدد می باشد

توجه : در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل می باشد و در فایل اصلی فایل ورد کامل روشی نیمه مدولار برای برنامه نویسی پویای گسسته،به هیچ وجه بهم ریختگی وجود ندارد

تعداد صفحات این فایل: ۲۰ صفحه

بخشی از مقاله انگلیسیعنوان انگلیسی:A submodular approach to discrete dynamic programming~~en~~

Abstract

Submodular functions are playing an increasing role in analyzing many discrete optimization problems. The purpose of this paper is to continue the trend by using submodular functions and their properties to develop a duality for discrete dynamic programming.

۱ Introduction

Duality is one of the most elegant concepts and one of the important computational tools in mathematics. Duality’s contributions to analysis and optimization are many. However, as a result of the recursive nature of dynamic programming (DP), duality results for DP are quite limited.

Bellman [1,2] was the first to introduce a duality concept in dynamic programming. Bellman [1] used Lagrange multipliers to reduce the state space. This in itself does not result in a general duality theory for DP. However, this concept, which was later generalized by Everett [4], has played an increasingly important role in discrete optimization vis-a-vis Lagrangian relaxation.

Dinkle and Peterson [3] developed a duality theory for the class of dynamic programming problems that have convex return functions and linear transition functions through the use of generalized geometric programming duality. In their approach, Dinkle and Peterson viewed the primal and dual problems in terms of orthogonal spaces. This approach is not without possible drawbacks. As Rockafellar [9,10] noted, it may not be a very effective scheme since it doesn’t always lead to unambiguous Lagrangians. It also does not provide the most natural setting for the study of the optimal value functions and it could create a conceptual stumbling block in application if there is not an obvious subspace at hand. Klein and Morin [6,7] overcame this problem with a more general approach using conjugate functions. Aside from the previously mentioned results and the fact that numerous other authors have provided tantalizing hints, a general duality theory for dynamic programming does not appear to have been developed to date.

We will look at the shortest route problem on a directed acyclic network which is the prototype problem for Dynamic Programming (DP). In this paper we will show how a duality can be achieved for the DP formulation of the shortest route problem.

$$en!!