بهینه سازی اقتصاد.
فهرست مندرجات[نهفتن] |
[ویرایش] تاریخچه
اولین تکنیک بهینهسازی را کارل فردریش گاوس ابداع کرد. اما عمده اصطلاحات مورد استفاده در این حوزه به دوره معاصر برمیگردد. اصطلاح برنامه ریزی خطی را نخستین بار جرج دانتزیگ در 1940 میلادی بهکاربرد. اصطلاح برنامهریزی در حوزه بهینهسازی به معنای برنامهنویسی برای کامپیوتر نیست، با این همه، رایانهها، امروزه به شکل گستردهای در حل مسائل ریاضی مورد استفاده قرار میگیرند. ریشه این اصطلاح به کاربرد واژه «برنامه» در ارتش ایالات متحده برمیگردد که در اشاره به طرحهای لجستیک و آموزشی به کار میرفت که دانتزیگ آن را مورد مطالعه قرار میداد. دیگر ریاضیدانان مهم در زمینه بهینهسازی عبارتند از:
[ویرایش] شاخههای اصلی
- برنامهریزی محدب به بررسی حالتی میپردازد که تابع هدف محدب است و قیودی اگر وجود داشته باشند یک مجموعه محدب را شکل میدهند. میتوان آن را حالت خاصی از برنامهریزی غیرخطی یا تعمیمی از برنامهریزی درجه دوم محدب دانست.
- برنامهریزی خطی نوعی از برنامه ریزی محدب است که به بررسی مواردی میپردازد که در آن تابع هدف خطی است و مجموعه قیود با استفاده از معادلات و نامعادلات خطی مشخص میشود. چنین مجموعهای اگر کراندار باشد چندوجهی یا کثیرالوجوه خوانده میشود.
- برنامهریزی مخروط مرتبه دوم نوعی از برنامه ریزی محدب است که شامل انواع خاصی از برنامههای درجه دوم است.
- برنامه ریزی شبهمعین نوعی از برنامه ریزی محدب و تعمیمی است از برنامهریزی خطی و درجه دوم که متغیرهای تحت بررسی آن، ماتریسهای شبهمعین است.
- برنامهریزی مخروطی شکل عمومی برنامهریزی محدب است. برنامهریزی خطی، برنامهریزی مخروط مرتبه دوم و برنامه ریزی شبهمعین را میتوان بهعنوان حالت خاصی از این نوع برنامه ریزی دانست.
- برنامهریزی عدد صحیح به بررسی آن دسته از برنامهریزیهای خطی میپردازد که در آن همه و یا برخی از متغیرها، تنها مقادیر صحیح اتخاذ میکنند.
- برنامه ریزی درجه دوم در تابع هدف آن جملات از مرتبه دو ظاهر میشوند، درحالیکه مجموعه مقادیر ممکن بهوسیله معادلات و نامعادلات خطی مشخصنمایی میشود. حالات خاصی از تابع هدف را میتوان تحت برنامه ریزی محدب بررسی کرد.
- برنامهریزی غیرخطی به بررسی مواردی میپردازد که در آن تابع هدف یا قیود و یا هردوی آنها حاوی بخشی غیرخطی هستند.
- برنامهریزی تصادفی به بررسی مواردی میپردازد که در آن برخی قیود یا پارامترها به متغیرهای تصادفی بستگی دارند.
- برنامهریزی ترکیبیاتی مسائلی را مدنظر دارد که مجموعه جوابهای ممکن گسسته اند و یا میتوانند به شکل گسسته تبدیل شوند.
- برنامهریزی با بعد نامتناهی مواردی را بررسی میکند که مجموعه جوابهای ممکن یک زیر مجموعه از فضای با بعد نامتناهی است. یک نمونه آن فضای توابع است.
- برنامهریزی فصلی که در آن حداقل یک قید باید ارضا شود ولی لزومی برای برقراری همه قیود نیست.
- برنامهریزی مسیری اختصاص به بهینهیابی مسیر وسایل نقلیه هوایی فضایی دارد.
در برخی زیرشاخهها، تکنیکها اصولا برای بهینهسازی پویا، یعنی بهینهسازی در طول زمان به کار میرود:
- حساب تغییرات با درنظرگرفتن اینکه چنانچه تغییر کوچکی در مسیر انتخابی بدهیم، تابع هدف چه تغییری میکند، در بهینهیابی تابع هدف در نقاط زمانی بسیار به کار گرفته میشود.
- کنترل بهینه تعمیمی است از حساب تغییرات.
- برنامهریزی پویا مواردی را بررسی میکند که استراتژی بهینه یابی برمبنای تقسیم مسئله به مسائل کوچکتر استوار است. معادلهای که روابط بین این مسائل کوچکتر را بررسی میکند معادله بلمن خوانده میشود.
- برنامهریزی ریاضی با قیود تساوی که در آن قیود شامل نامعادلات تغییر یابنده و یا comlementarity است.
[ویرایش] انواع مسائل بهینه سازی و تقسیم بندی آنها
در ریاضیات، مسئله بهینهسازی، مسئله یافتن بهترین جواب از تمام جوابهای ممکن است. مسئله بهینهسازی A چهارتایی (I,f,m,g) است که در آن
- I نشاندهنده یک مجموعه است
- f تابعی است که به هر عضو معلوم مجموعهای از جوابهای ممکن نظیر میکند
- عبارت (m(x,y برای هر ، و هر جواب ممکن y برای x نشاندهنده اندازه y است، که معمولا یک عدد حقیقی مثبت است
- g تابع هدف است که حاوی مینیممسازی یا ماکزیممسازی است.
هدف یافتن جواب بهینه برای x است، یعنی یک جواب ممکن چون y که
برای هر مسئله بهینهسازی، یک مسئله تصمیم متناظر وجود دارد که در پی یافتن جوابی ممکن برای یک اندازه خاص m0 است. در الگوریتمهای تخمین، الگوریتمها برای یافتن جوابهای نزدیک-بهینه برای مسائل پیچیده طراحی میشود. گرچه در این مسائل هم میتوان مسائل تصمیم متناظر تعریف کرد، ولی عموما آن را با مسائل بهینه سازی مشخص میکنند که طبیعیتر هم هست.
[ویرایش] بهینهسازی تک بعدی و بهینهسازی چند بعدی
اگر تنها یک متغیر در مسئله بهینهسازی وجود داشته باشد، مسئله بهینهسازی تک بعدی و در غیر این صورت چند بعدی خوانده میشود.
[ویرایش] بهینهسازی پویا و بهینهسازی ایستا
اگر تابع هزینه مسئله بهینهسازی تابعی از زمان نباشد، با یک مسئله بهینهسازی ایستا سر و کار داریم. ولی اگر زمان نیز وارد تابع هزینه شود مسئله بهینهسازی پویا میشود.
[ویرایش] بهینهسازی مقید و نا مقید
اگر متغیرهای مسئله بهینهسازی به مجموعه و یا قید خاصی محدود شده باشند، با یک مسئله بهینهسازی مقید Constrained Optimization سروکار داریم و در غیر این صورد مسئله بهینهسازی نامقید است.
[ویرایش] بهینهسازی پیوسته و بهینهسازی گسسته
یک مسئله بهینهسازی گسسته مسئله ای است که در آن مقادیر متغیرهای مسئله از یک مجموعه معین گسسته هستند. در حالی که، در یک مسئله پیوسته، مقادیر متغیرها از یک مجموعه پیوسته هستند.
[ویرایش] بهینهسازی تک معیاره و چند معیاره
یک مسئله بهینهسازی تک معیاره (Single Objective)، دارای تنها یک تابع هدف می باشد. اما در یک مسئله چند معیاره (Multi Objective)، تعداد تابع هدف هایی که بطور همزمان بهینه می شوند بیش از یکی است. معمولاً در یک مسئله بهینهسازی چند معیاره، با دادن اهمیتی (وزنی) به هر یک از توابع هدف و جمع بستن آنها، مسئله را تبدیل به یک مسئله تک معیاره می کنند. حل مسائل بهینهسازی چند هدفه، به تنهایی مبحث مستقل و مهمی از حوزه بهینهسازی است.
[ویرایش] مسئله بهینهسازی
مدخل اصلی: مسئله بهینهسازی
مسئله بهینهسازی به شکل زیر میتواند ارائه میشود:
با مفروض گرفتن تابع f : A R، که در آن R مجموعه اعداد حقیقی است. به دنبال یافتن عنصری از xopt در A هستیم به شکلی که برای هر x متعلق به A داشته باشیم (f(xopt) ≤ f(x و یا آنکه برای هر x متعلق به A داشته باشیم (f(xopt) ≥ f(x.
چنین فرمولبندی مسئله بهینهسازی یا مسئله برنامهریزی ریاضی خوانده میشود. بسیاری از مسائل جهان واقع میتواند در این چهارچوب عمومی مدل شود. نوعاً، A زیرمجموعهای از فضای اقلیدسی Rn است که اغلب با مجموعهای از قیود، یعنی معادلات و نامعادلاتی که اعضای A باید آنها را ارضا کند، مشخص میشود. دامنه f مجموعه انتخاب یا فضای جستجو خوانده میشود، درحالیکه عناصر A، جوابهای ممکن یا قابل دستیابی خوانده میشوند.
تابع f، عموما تابع هدف خوانده میشود. جواب ممکنی که تابع هدف را ماکزیمم کند و یا اگر هدف مینیممسازی باشد، آنرا مینیمم کند، جواب بهینه خوانده میشود.
[ویرایش] ماکزیمم و مینیمم نسبی
عموماً، وقتی ناحیه جوابهای ممکن مسئله محدب نباشد، چندین مینیمم و ماکزیمم نسبی وجود خواهد داشت. ماکزیمم نسبی *x نقطهای است که برای آن یک δ > 0 وجود داشته باشد بهطوریکه برای هر x که در رابطه زیر صدق کند
داشته باشیم
یعنی در ناحیه جواب، مقدار تابعی همه نقاط حول (لااقل) یک همسایگی از *x، کوچکتر یا مساوی مقدار تابع در آن نقطه باشد. مینیمم نسبی نیز به شکل مشابهی تعریف می شود.
الگوریتمهای زیادی برای حل مسائل غیرمحدب ارائه شده است. شاخهای از ریاضیات کاربردی و آنالیز عددی که با ایجاد الگوریتمهای قطعی -با تضمین همگرایی در زمان متناهی- به جواب بهینه واقعی یک مسئله غیرمحدب بیانجامد، بهینهیابی سرتاسری خوانده میشود.
[ویرایش] نمادگذاری
مسائل بهینهسازی غالباً با نمادهای ویژهای نمایش داده میشوند. در اینجا چند مثال آورده میشود.
که به معنی یافتن مقدار مینیمم تابع هدف x2 + 1 است، که x متعلق به مجموعه اعداد حقیقی است. به وضوح، حداقل مقدار این تابع، 1 است که در x = 0اتفاق میافتد.
که به معنی یافتن مقدار ماکزیمم تابع هدف 2x است، که x متعلق به مجموعه اعداد حقیقی است. در این حالت حداکثری وجود ندارد؛ چرا که مجموعه مقادیر تابع هدف بیکران است. پس پاسخ بینهایت یا تعریف نشده است.
که به دنبال مقدار یا مقادیری از x در بازه است که تابع هدف x2 + 1 را مینیمم میکند (مقدار مینیمم تابع اهمیتی ندارد). در این حالت جواب x = − 1 است.
که به دنبال زوج مرتب(هایی) همچون (x,y) است که مقدار تابع هدف را ماکزیمم میکند با این قید که x در بازه [5,5-] باشد (مقدار ماکزیمم تابع اهمیتی ندارد). در این حالت، جوابها، زوج مرتبهایی به شکل (5,2kπ) و (2kπ+πو5-) است، بهطوریکه k تمام اعداد صحیح را در برمیگیرد.
[ویرایش] قضایا
قضایای اصلی مسئله بهینهسازی را «قضایایی برای اثبات وجود نقاط بهینه»، «قضایایی برای یافتن این نقاط» و «قضایایی برای تحلیل حساسیت این نقاط نسبت به تغییر پارامترهای مسئله» تشکیل می دهند. در زیر به برخی از مهم ترین آنها اشاره میشود.
[ویرایش] وجود نقطه بهینه
قضیه مقدار بحرانی منتسب به کارل وایرشتراس شرایط وجود نقطه بهینه را بیان میکند.
اگر فضای جواب های ممکن، فشرده (ویا به طور هم ارز، در فضای اقلیدسی، بسته و کراندار باشد) و ناتهی باشد و از طرفی تابع هدف، پیوسته باشد، آنگاه برای تابع هدف، مقادیر ماکزیمم و مینیمم (بهینه)، در این مجموعه یافت خواهد شد.
[ویرایش] طریقه یافتن نقطه بهینه
قضیه نقطه مانای فرما بیان میدارد که جواب بهینه مسائل غیرمقید، در نقاطی یافت میشود که مشتق اول یا گرادیان تابع هدف صفر باشد. پس گام اولیه در یافتن این جوابها استفاده از آزمون مشتق اول است. یعنی عموماً باید به دنبال نقاط بحرانی بود، یعنی نقاطی که در آن مشتق یا گرادیان تابع هدف صفر باشد یا تعریف نشده باشد و یا در مرز ناحیه جواب باشد. معادلهای که در آن مشتق اول، در نقاط درون ناحیه جواب، برابر صفر قرار داده شده است، اغلب "شرط مرتبه اول" خوانده میشود.
نقاط بهینه مسائل «بهینه سازی با وجود قیود نامساوی»، با استفاده از ضرایب لاگرانژ به دست میآید. این روش نیازمند محاسبه یک سیستم از نامعادلات است که شرایط کاروش-کان-تاکر خوانده میشود.
آزمون مشتق اول، نقاطی را که ممکن است بهینه باشد مشخص میکند، اما نمیتواند تمایزی بین نقاط ماکزیمم، مینیمم و دیگر نقاط بحرانی ایجاد کند. زمانیکه تابع هدف دوبار مشتقپذیر است، این تمایز در مسائل غیرمقید، با توجه به مشتق دوم یا ماتریس مشتقهای دوم (ماتریس هشین) حاصل میشود و در مسائل مقید، این تمایز، با ماتریس مشتقهای مرتبه دوم تابع هدف و قیود ( ماتریس هشین مرزدار) یه دست میآید. شرایطی که تمایز بین این نقاط ماکزیمم و مینیمم را نشان میدهد، اغلب "شرایط مرتبه دوم" خوانده میشود.
[ویرایش] اگر مسئله تغییر کند، نقطه بهینه چه تغییری میکند؟
قضیه پوش چگونگی تغییر مقادیر جواب بهینه را در اثر تغییر پارامترها تشریح میکند.
کلاود برگ (1963) در قضیهای موسوم به قضیه ماکزیمم به تشریح پیوستگی جواب بهینه به عنوان تابعی از پارامترها میپردازد.
[ویرایش] کاربرد بهینهسازی در اقتصاد
اقتصاد، در بسیاری مسائل، برنامه ریزی ریاضی را به کار میگیرد. در اقتصاد خرد، مسئله حداکثرسازی مطلوبیت و مسئله دوگان آن یعنی مسئله حداقلسازی مخارج، مسائل بهینهسازی هستند. فرض بر آن است که مصرفکنندهها مطلوبیت خود را و بنگاهها سود خود را حداکثر میکنند. قیمت دارایی نیز، بر پایه تئوری قیمت گذاری دارایی، با بهینهسازی توضیح داده میشود. برای توضیح تجارت بین کشورها نیز بهینهسازی به کار میرود.
مسئله اقتصاد به یک تعبیر عبارت است از تخصیص بهینه منابع محدود (کمیاب) به نیازهای نامحدود. از نظر ریاضی این یک مسئله بهینهسازی است. چنانکه در اقتصاد خرد معمول است، اگر این مسئله ایستا در نظر گرفته شود، می تواند به عنوان یک مسئله بهینهسازی مقید در نظر گرفته شود که تابع هدف آن مطلوبیت (نیازهای نامحدود) و قیود هم منابع محدود هستند. دوآل این مسئله نیز مینیمم سازی هزینه های مصرف کننده است که در اقتصاد خرد به آن پرداخته میشود. معمول ترین روش برای حل چنین مسائلی استفاده از شرایط کان-تاکر است. اما چنانچه، این مسئله پویا در نظر گرفته شود، به مسئله ریاضی تعیین مسیرهای زمانی برای تخصیص عوامل می رسیم که در ذات خود یک مسئله کنترل است و با استفاده از تکنیکهای کنترل بهینه از جمله هامیلتونین میتوان آنرا حل کرد. اقتصاد کلان بیشتر با چنین مسائلی سر و کار دارد.
[ویرایش] روش ضرایب لاگرانژ
هنگامیکه با قیود به شکل معادله (تساوی) سر و کار داریم، این روش بهینهسازی بسیار کارا خواهد بود. بهعلاوه، هنگامیکه مقادیر ثابت قیود تغییر میکند، اطلاعات با ارزشی از مقدار بهینه تابع هدف در اختیار میگذارد.
ابتدا، تابع هدف F را در نظر بگیرید که بر زیرمجموعهای چون X از فضای اقلیدسی تعریف شده است (پس عناصر X می توانند بردار باشند)؛ که این زیرمجموعه، توسط قیود به شکل g(x)=b تعریف میشود. تابع لاگرانژ در این حالت عبارت خواهد بود از ((L(x,y)=F(x)+y.(b-g(x
شرایط لازم را میتوان، از طریق یافتن نقاط بحرانی تابع لاگرانژ (ماکزیممسازی بدون قید)، به دست آورد. به علاوه ضرایب y که به ضرایب لاگرانژ موسومند، تفسیر مهمی دارند که در زیر، همراه با مثالی توضیح داده خواهد شد.
[ویرایش] قیمت سایه
تغییر در مقدار تابع هدف جواب بهینه در مسئله بهینهسازی با استفاده از یک واحد بیشتر از منبع (قید) است که خود مطلوبیت نهایی قید یا هزینه نهایی افزودن به قید است. قیمت سایه، مقدار ضریب لاگرانژ در جواب بهینه است. مصرفکنندهای را درنظربگیرید که دارای ثروت W است و با قیمتهای ثابت p1,p2 روبروست. مسئله مصرفکننده در این حالت عبارت خواهد بود از
لاگرانژین این مسئله به شکل زیر خواهد بود:
با استفاده از شرایط مرتبه اول، مقادیر بهینهساز به دست خواهد آمد که تساوی زیر را برقرار خواهد کرد:
اگر به مصرف کننده یک واحد اضافه تر از ثروت داده شود، در جاییکه مطلوبیت نهایی برحسب هر واحد پولی برابر *λ است، تغییر مطلوبیت نهایی بر حسب واحد پولی یک واحد اضافه تر از ثروت برابر خواهد بود با *λ که به قیمت سایه مشهور است.
[ویرایش] شرایط کاروش-کان-تاکر
در ریاضیات، شرایط کاروش-کان-تاکر، (Karush-Kuhn-Tucker) و یا کان-تاکر (Kuhn-Tucker)، شرایط لازم برای جواب بهینه در برنامهریزی غیرخطی میباشد، مشروط بر آنکه برخی شرایط Regularity ارضا شود. کان-تاکر در واقع تعمیمی است بر روش ضرایب لاگرانژ که در آن قیود نامساوی هم در نظر گرفته شده است. مسئله بهینهسازی غیرخطی زیر را در نظر بگیرید:
تابع هدف تابعی است که قصد حداقل سازی آن را داریم؛ توابعی هستند که قیود نامساوی را تشکیل میدهند و توابعیاند که قیود تساوی را شکل میدهند، m و l به ترتیب تعداد قیود نامساوی و تساوی هستند. شرایط کان-تاکر، به افتخار هارولد و. کان (Harold W. Kuhn) و نیز آلبرت و. تاکر (Albert W. Tucker) نامگذاری شده است که اول بار، این شرایط را منتشر کردهاند. پژوهشگران بعدی، شرایط لازم این مسئله را یافتند. ویلیام کاروش (William Karush) در پایاننامه کارشناسیارشد خود، این شرایط را تشریح کرده است.
[ویرایش] شرایط لازم
فرض که تابع هدف باشد و توابع قیود نامساوی به شکل و توابع قیود نامساوی به شکل باشند. اگر *x، مینیمم موضعی باشد که برخی شرایط Regularity را ارضا کند، آنگاه ثابتی چون و وجود خواهد داشت بطوریکه
[ویرایش] شرایط کافی
اگر مجموعه جوابهای ممکن ، مجموعهای ناتهی و فشرده و ضمناً محدب باشد، و تابع هدف بر این مجموعه، پیوسته و مقعر باشد؛ در این صورت، ماکزیمم موضعی، ماکزیمم مطلق است. بعلاوه، اگر تابع هدف اکیدا مقعر باشد، در این صورت جواب یکتاست، یعنی یک ماکزیمم مطلق یکتا وجود دارد. پس یک راه اطمینان حاصل کردن از اینکه، جوابهای حاصل از شرایط مرتبه اول کان-تاکر، ماکزیمم هستند، بررسی شرایط فوقالذکر است.
هرگاه تابع هدف f و قیود نامساوی gi بطور پیوسته مشتقپذیر و محدب باشند و قیود تساوی hj توابع آفین باشند؛ شرایط لازم، کافی نیز خواهند بود.
مارتین 1985 (Martin 1985)، دستهای از توابع را مشخص کرد که در آنها شرایط کان-تاکر، وجود بهینه سرتاسری را تضمین میکند، که توابع invex خوانده میشوند. اگر قیود تساوی، توابع آفین باشند، قیود نامساوی و تابع هدف بطور پیوسته مشتقپذیر و invex باشند، شرایط کان-تاکر برای بهینه سرتاسری، کافی نیز خواهد بود.
[ویرایش] توابع مقداری
تابع مقداری (value function) برای مسئله ماکزیمم سازی زیر
به شکل زیر تعریف خواهد شد
(دامنه v، عبارت خواهد بود از ) با این تعریف، ضرایب λi نشاندهنده نرخ افزایش تابع مقداری، درصورت افزایش ai خواهد بود.
چنانچه هر ai بهعنوان قید منابع تفسیر شود، ضرایب نشان خواهد داد که افزایش در منبع، مقدار بهینه تابع f را تا چه اندازه افزایش خواهد داد. این تعبیر، بهویژه در اقتصاد مهم است و در مسائلی همچون حداکثرسازی مطلوبیت مورد استفاده نیز میباشد.
[ویرایش] مسئله حداکثرسازی مطلوبیت
مسئله حداکثرسازی مطلوبیت، مسئلهای است که مصرفکننده در اقتصاد خرد، با آن روبروست. این سوال که "چگونه میبایستی ثروت خود را برای به دست اوردن حداکثر مطلوبیت خرج کنم؟" خود یک نوع از مسئله تصمیمگیری بهینه است.
فرض کنید مجموعه مصرفی، (یا به عبارت ساده تر مجموعه همه سبدهای مصرفی که اگر قید بودجهای نبود، ممکن بود انتخاب شوند)، حاوی L کالا است و فرض کنید که به مقادیر مثبت محدود شده است.
و همچنین فرض کنید که قیمت کالاها مثبت باشند.
و فرض کنید که ثروت مصرف کننده برابر w باشد، آنگاه مجموعه سبدهای قابل خرید، مجموعه بودجه، برابر خواهد بود با
که ضرب داخلی بردار قیمت و مقادیر مصرفی است، و یا هزینه مصرفی کالای x با قیمتهای p است. مصرفکننده میخواهد که بهترین سبد مصرفی را که میتواند ابتیاع کند. تابع مطلوبیتی به صورت یک تابع حقیقی مقدار با دامنه سبدهای کالایی در نظر بگیرید مثل
انتخابهای مصرفی بهینه مصرفکننده (x(p, w، سبدهای حداکثر کننده مطلوبیت مصرفکننده در مجموعه بودجه است یعنی
یافتن (x(p, w به مسئله حداکثرسازی مطلوبیت مشهور است. اگر u پیوسته باشد و هیچ کالایی مجانی نباشد، (x(p, w وجود خواهد داشت. اگر حداکثرساز همواره منحصر به فرد باشد، آنگاه آن را تابع تقاضای مارشالی گویند. رابطه بین تابع مطلوبیت و تقاضای مارشالی در مسئله حداکثرسازی مطلوبیت رابطه بین تابع مخارج و تقاضای هیکسی را در مسئله حداقلسازی مخارج را بازمیتاباند.
لزوما جواب (x(p, w منحصر به فرد نیست. اگر مصرفکنندهای همواره یک سبد بهینه را آنچنانکه در بالا تعریف شد انتخاب کند، آنگاه (x(p, w تناظر تقاضای مارشالی خوانده میشود.
اما باید توجه داشت که بهینه سازی صرفا یک ابزار ریاضی است و ممکن است رفتار افراد در عمل به گونه ای دیگر هم باشد. تئوری عقلانیت محدود، بیانگر آنست که در عمل، مصرفکننده ممکن است همواره سبد بهینه را انتخاب نکند. برای مثال، یک مشکل، نیاز به تفکر زیاد است.
[ویرایش] مثال
تابع کاب-داگلاس U را برای مطلوبیت مصرف کننده که از مصرف دو کالای x و y حاصل میکند، در نظر بگیرید. مصرف کننده در پی حداکثرسازی مطلوبیت خود است که با حداکثرسازی عبارت زیر هم ارز است:
ln U = a ln x + (1-a) ln y
که در آن a<1 ثابت معین میباشد. اما مصرف کننده با قید محدودیت منابع خود هم روبروست. یعنی چنانچه ثروت وی برابر w و قیمت کالاها در بازار به تر تیب برابر p و q، همگی داده شده و معین باشند؛ قیدی را که مصرف کننده با آن مواجه است میتوان به شکل زیر نوشت:
px+qy≤w
با تشکیل تابع (L = a ln x + (1-a) ln y + M(w-px-qy و نوشتن شرایط کان-تاکر داریم:
a=pMx , (1-a)=qMy , M>0 , px+qy≤w , M(w-px-qy)=0
پس اولاً از ترکیب شرط میانی و شرط آخر داریم: w-px-qy=0
(البته چون تابع هدف در هرد متغیر افزایشی است، قید همواره به صورت تساوی برقرار میشود)
و ثانیاً از ترکیب سه شرط اول داریم: aqy = (1-a)px
از حل دستگاه دو معادله و دو مجهولی که توسط این دو معادله آخر ساخته میشود، مقادیر حداکثرساز x و y برحسب پارامترهای a,p,q,w به دست خواهد آمد که همان تقاضای مصرف کننده از این دو کالا را نشان میدهد.
[ویرایش] مسئله حداقلسازی هزینه
در اقتصاد خرد، مسئله حداقلسازی هزینه، صورت دیگری برای مسئله حداکثرسازی مطلوبیت است. سوال "چه ثروتی برای دستیابی به سطح خاصی از خوشی (مطلوبیت) لازم است ؟" به دو بخش تقسیم میشود. با تابع مطلوبیت معین برای مصرفکننده، قیمتهای معین، و مطلوبیت هدفگذاری شده،
- چه ثروتی برای مصرفکننده لازم است؟ پاسخ این پرسش با تابع مخارج به دست میآید.
- مصرفکننده برای رسیدن به این مطلوبیت هدفگذاری شده چه چیزی بخرد تا مخارج خود را حداقل کند؟ پاسخ این پرسش با تابع تقاضای هیکسیداده میشود.
[ویرایش] تابع مخارج
به صورت ریاضی، تابع مخارج به شکل زیر تعریف میشود.
تابع مطلوبیت u را که بر سبدهای کالایی مشتمل بر L کالا تعریف شده برای مصرفکننده در نظر بگیرید. در این صورت، تابع مخارج مصرفکننده، مقدار ثروتی را نشان میدهد که در قیمتهای داده شده p، برای خرید آن سبدی از کالاها لازم است که مطلوبیتی لااقل به اندازه *u میدهد
که
مجموعهای از سبدهای کالایی است که مطلوبیتی حداقل به اندازه *u میدهد.
[ویرایش] تناظر تقاضای هیکسی
تناظر تقاضای هیکسی (*h(p,u، به وسیله ارزانترین سبد کالایی که مطلوبیت هدفگذاریشده را بدهد، تعریف میشود و میتواند برحسب تابع مخارج با تابع تقاضای مارشالی تعریف شود.
ممکن است که تقاضای هیکسی و مارشالی منحصر به فرد نباشند، یعنی بیش از یک سبد کالا وجود داشته باشد که مسئله حداقلسازی هزینه را حل کند. در این صورت میتوان تقاضا را به جای تابع، بهعنوان یک تناظر تعریف کرد. چنانچه فرض کنیم اشباعناپذیری محلی برقرار باشد، جواب یکتا است و تقاضا را میتوان بهعنوان تابع تعریف کرد.
[ویرایش] کنترل بهینه
نظریه کنترل بهینه، یک روش بهینهسازی ریاضی است برای به دست آوردن سیاستگذاریهای کنترلی و تعمیمی است بر حساب تغییرات. این روش به وسیلهٔ لو پنتریاگین و همقطارانش در شوروی و نیز ریچارد بلمن در آمریکا ابداع شد.
[ویرایش] روش عمومی
نظریه کنترل بهینه در پی یافتن قانون کنترل برای یک سیستم معین است به شکلی که ضابطه بهینگی خاصی به دست آید. مسئله کنترل، تابعی از متغیرهای کنترل و متغیرهای وضعیت است . کنترل بهینه،در واقع مجموعهای از معادلات دیفرانسیل است که "مسیری" از متغیرهای کنترل که تابع هزینه را مینیمم میکند، نشان میدهند. کنترل بهینه میتواند با استفاده از اصل حداکثرسازی پنتریاگین (شرط لازم)، یا حل معادله همیلتن-ژاکوبی-بلمن (شرط کافی) به دست آید.
[ویرایش] مفاهیم کنترل بهینه به همراه مثالی ساده
اتومبیلی را در نظر بگیرید که بر خط مستقیمی روی تپه ماهور به پیش میرود. مسئله آن است که راننده چطور پدال گاز را بفشارد که کل زمان مسافرت وی حداقل شود؟ قانون کنترل، در این مثال، به طریقی که راننده گاز را میفشارد و دنده عوض میکند برمیگردد. سیستم، در این مثال، شامل جاده و اتومبیل است، ضابطه بهینگی، در این مثال، حداقلسازی زمان مسافرت است. مسائل کنترل معمولاً شامل قیود فرعی است. قیود فرعی در این مثال، میتواند شامل حداکثر سوخت قابل دسترس، حداکثر سرعت و... باشد. «تابع هزینه»، در این مثال عبارتی ریاضی است که زمان را به عنوان تابعی از سرعت، ملاحظات جغرافیایی و شرایط اولیه سیستم میدهد.
[ویرایش] چهارچوب مجرد
چهارچوبی مجردتر از مثال بالا را به شکل زیر میتوان بیان کرد. تابع هزینه (نسبت به متغیر زمان پیوسته) زیر حداقل شود
با توجه به قیود دینامیک مرتبه اول
و قیود مسیر
و شرایط مرزی
که (x(t وضعیت و (u(t کنترل خوانده میشود. t متغیر مستقلی است که عموماً زمان است. t0 زمان اولیه و tf زمان انتهایی است. لاگرانژین خوانده میشود. چنین مسائل کنترل بهینه ممکن است چندین جواب داشته باشند. اغلب هر جواب مسئله کنترل بهینه به شکل یک حداقل ساز نسبی است.
[ویرایش] روشهای عددی برای کنترل بهینه
مسائل کنترل بهینه اغلب غیرخطی هستند و بنابراین عموما جواب تحلیلی ندارند. نتیجتاً بهکارگیری روشهای عددی برای حل مسائل کنترل بهینه، به نظر ضروری میرسد. در روش غیرمستقیم، که رهیافتی برای حل مسائل کنترل بهینه است، با استفاده از حساب تغییرات برای به دست آوردن شرایط مرتبه اول، به یک مسئله مقدار مرزی میرسیم که خود، شکل مشتقات همیلتونین را دارد. بنابراین سیستم همیلتونین زیر را خواهیم داشت:
که
با استفاده از شرایط مرزی مناسب مسئله حل خواهد شد.
در روش مستقیم، متغیر کنترل و/یا متغیر وضعیت با استفاده از تخمین چندجملهای، تخمین زده میشود.
[ویرایش] هامیلتونین
هامیلتونین در تئوری کنترل بهینه به وسیلهٔ پنتریاگین ابداع شد. وی اثبات کرد که یک شرط لازم برای حل مساله کنترل بهینه این است که کنترل باید به گونهای انتخاب شود که همیلتونین را کمینه کند. همیلتونین را میتوان به شکل زیر تعریف کرد:
که در آن (λ(t برداری از متغیرهای costate است با بعدی برابر با بعد متغیر وضعیت (x(t. نمادها و تعریف مساله متغیر کنترل (u(t باید به گونهای انتخاب شود که تابع زیر را کمینه کند:
متغیر حالت سیستم (x(t به صورت زیر تغییر مییابد:
متغیر کنترل باید شرایط زیر را داشته باشد:
همیلتونین پنتریاگین را میتوان با یک تابع 4 متغیره نظر گرفت:
دراین حالت، شرایط ماکزیمم را میتوان به شکل زیر نوشت:
[ویرایش] مثالی از حل یک مسئله کنترل بهینه
استراتژی حل مسائل کنترل بهینه عموماً یافتن costate یا قیمت سایه (λ(t است که در برخی موارد و به ویژه در مسائل زمان پیوسته، میتواند بهصورت صریح به دست آورده شود.
مسئله کشیدن چاه از نفت را، برای حداکثر T دوره زمانی، در نظر بگیرید. فرض کنید که در زمان 0، موجودی نفت در چاه به میزان x0 است و هزینه بیرون کشیدن نفت (u(t)2 / x(t است که (u(t نرخ کشیدن نفت از چاه است. قیمت نفت در بازار ثابت و برابر P است. مسئله یافتن نرخ (u(t برای حداکثرسازی سود (بدون تنزیل زمانی) است با این فرض که در زمان T، نفت برای صاحب چاه ارزشی ندارد.
پاسخ: صاحب چاه نفت سود خود را، Π، حداکثر میکند که به شکل زیر نوشته میشود
و برای این کار با قید زیر مواجه است
با استفاده از همیلتونین داریم:
از طرفی در زمان T، نفت چاه ارزشی ندارد یعنی
- λ(T) = 0
با استفاده از معادلات بالا به دست آوردن معادلات دیفرانسیل (u(t و (λ(t ساده خواهد شد:
با استفاده از شرایط اولیه و شرایط زمان T، میتوان این توابع را به صورت عددی بهدستآورد.
[ویرایش] نرمافزارها
- فهرست جامعی از نرمافزارهای بهینهسازی را میتوانید در اینجا بینید.
- LINDO - Linear Interactive and Discrete Optimizer برای حل مدلهای ساده خطی به روش سیمپلکس و تحلیل حساسیت، حل مسائل مقدارصحیح و برنامه ریزی درجه دوم. محدودیت نسخه رایگان فوق، در پذیرش تعداد متغیرها (حداکثر 300 متغیر) و قیدها (حداکثر 150 قید) است.
- IMSL Numerical Libraries مجموعهای از الگوریتمهای ریاضی و آماری در C/C++، Fortran، Java و C#/.NET است. زیرروالهای موجود در آن شامل الگوریتمهای مینیمم سازی مقید غیرخطی و خطی، مینیمم سازی غیرمقید و برنامهریزی غیرخطی است.
- KNITRO برای حل مسائل غیرخطی بهکار میرود.
- Mathematica محیطی برای مسائل ریاضی که میتواند برای حل بهینهسازی غیرخطی مقید، برنامهریزی خطی و برنامهریزی عدد صحیح به کار رود.
- Opt++ یک بسته شیگرا برای برنامهریزی غیرخطی [۱]
- Merlin بسته نرمافزاری Fortran-77 برای بهینهسازی غیرخطی که open source است. [۲]
- OpenOpt برای بهینهسازی در زبان NumPy
- FortSP حل مسائل برنامهریزی تصادفی
- Comet زبان برنامهنویسی پرکاربرد در بهینهسازی
- NAG Libraries زیرروالهایی برای بهینهسازی برای زبانهای برنامهنویسی C، C++، Fortran، Python، Java و .NET و نیز بستههای MATLAB، Maple و Excel
- Moocho برای حل برنامههای غیرخطی؛ به صورت open-source در دسترس است.
- OOL - Open Optimization library یک مجموعه از روالهای بهینهسازی در C.
- IOptLib - Investigative Optimization Library یک کتابخانه برای الگوریتمهای بهینهسازی (ANSI C).
- ALGLIB روالهایی برای بهینهسازی در C++، C#، Delphi و Visual Basic
- OAT - Optimization Algorithm Toolkit یک مجموعه از الگوریتمهای بهینهسازی در Java
- JPOP - Java Parallel Optimization Package یک بسته open-source برای Java که برای محاسبه توابع، گرادیان و هشینها به کار میرود.
- Free Optimization Software by Systems Optimization Laboratory, Stanford University
- BNDSCO نرمافزاری مناسب حل مسائل کنترل بهینه به روش غیرمستقیم
- MATLAB برای حل مسائل کنترل بهینه با ابزارهایی نظیر RIOTS ،DIDO ،GPOPS و PROPT و البته محیط بهینهسازی TOMLAB
- ACADO Toolkit - Open Source Toolkit for Automatic Control and Dynamic Optimization C++, MATLAB interface available
- Flood: An open source neural networks C++ library
- GPOPS - Open Source Pseudospectral Optimal Control Solver in MATLAB
- PSOPT - Open Source Pseudospectral Optimal Control Solver in C++
[ویرایش] برای مطالعه بیشتر
- فهرست مهمترین آثار در زمینه بهینهسازی
- لوئنبرگر دیوید، برنامهریزی خطی و غیر خطی، ترجمه مهدوی امیری نظام الدین و پورکاظمی محمدحسین، انتشارات دانشکاه صنعتی شریف ، 1379، تهران.
- دانلود رایگان کتاب بهینه سازی چند هدفه
- فایلهای آموزشی هوش مصنوعی متلبسایت
- Convex Optimization – Boyd and Vandenberghe Book on Convex Optimization
- Convex Optimization I EE364a: Course from Stanford University
- Panos Y. Papalambros and Douglass J. Wilde (2000). Principles of Optimal Design : Modeling and Computation, Cambridge University Press. ISBN 0-521-62727-3
- Stephen Boyd and Lieven Vandenberghe (2004). Convex Optimization, Cambridge University Press. ISBN 0-521-83378-7
- Becerra, V.M., 2008, Optimal control. Scholarpedia, 3(1):5354
- Evans, L.C., An Introduction to Optimal Control Theory available free online
- Stengel, R. F., 1994. Optimal Control and Estimation. Dover.
- Sethi, S. P., and Thompson, G. L., 2000. Optimal Control Theory: Applications to Management Science and Economics, 2nd edition, Springer (ISBN 0387280928 and ISBN 0792386086). Slides are available at http://www.utdallas.edu/~sethi/OPRE7320presentation.html
- P. Varaiya: Lecture Notes on Optimization, 2d. ed. ,1998
- Sussmann, Willems: 300 Year of Optimal Control, IEEE Control Systems, June 1997
- Sontag, Eduardo D. Mathematical Control Theory: Deterministic Finite Dimensional Systems. Second Edition. Springer. (ISBN 0-387-984895) available free online
[ویرایش] مجلات
- Optimal Control Applications and Methods. John Wiley & Sons, Inc.
- SIAM Journal of Control and Optimization
[ویرایش] پیوندهای بیرونی
- بهینه سازی چیست؟ (تئوری بهینه سازی)
- کتاب الگوریتم بهینهسازی کلونی مورچهها
- شبکه عصبی چیست؟
- برنامهريزی ژنتيک چیست؟
- Optimization Related Links
- Mathematical Programming Glossary
- Global optimization
- COIN-OR — Computational Infrastructure for Operations Research
- Decision Tree for Optimization Software Links to optimization source codes
- NEOS Wiki
- Optimization Online
- Simplemax Online Optimization Services Web applications to access nonlinear optimization services
- Mathematical Programming Society
- Dr. Benoît CHACHUAT: Automatic Control Laboratory - Nonlinear Programming, Calculus of Variations and Optimal Control
- Elmer G. Wiens: Optimal Control - Applications of Optimal Control Theory Using the Pontryagin Maximum Principle with interactive models
- GESOP - Graphical Environment for Simulation and OPtimization
- Anatomy of Cobb-Douglas Type Utility Functions in 3D
[ویرایش] منابع
- Mas-Colell, Andreu; Whinston, Michael; & Green, Jerry (1995), Microeconomic Theory, Oxford: Oxford University Press. ISBN 0-19-507340
- اینتریلیگیتور میشل، بهینهسازی ریاضی، ترجمه پورکاظمی حسین علی، مرکز چاپ و انتشارات دانشگاه شهید بهشتی، 1368، تهران.
- برادلی، هکس و مگننی، برنامه ریاضی کاربردی، ترجمه ذکایی آشتیانی ، موسسه عالی پژوهش در برنامهریزی و توسعه، 1372، تهران.
- لوئنبرگر دیوید، برنامهریزی خطی و غیر خطی، ترجمه مهدوی امیری نظام الدین و پورکاظمی محمدحسین، انتشارات دانشکاه صنعتی شریف ، 1379، تهران.
مالی و اقتصادی(۴)
