برنامهریزی هندسی
برنامهریزی هندسی در سال ۱۹۶۷ توسط دافین، پترسون و زنر معرفی گردید. برنامهریزی هندسی روشی کارآمد برای برخی از مسائل برنامهریزی غیرخطی بوده و زیر مجموعهای از مسائل سیگنومیال است. به کمک برنامهریزی هندسی میتوان مسائل کاربردی و در مقیاس بزرگ را به مدل بهینهسازی ریاضی تبدیل کرده و حل نمود. از کاربردهای GP میتوان به طراحی مدارهای الکتریکی، مسائل مالی و آماری اشاره نمود.
نحوهٔ فرمولبندی[ویرایش]
فرم استاندار[ویرایش]
مسائل برنامهریزی هندسی متشکل از تابع هدف پوزینومیال، قیود نامساوی پوزینومیال و قیود تساوی مونومیال هستند.
مونومیال به شکل زیر تعریف میشود:
پوزینومیال مجموع K جملهٔ مونومیال است:
شکل استاندارد یک مسألهی برنامهریزی هندسی به صورت زیر است:
پارامتر بهینهسازی است. در بسیاری از موارد، برنامهریزی هندسی میبایست به فرم استاندارد تبدیل شود. در صورتی که مسأله یک مسألهی بیشینهسازی باشد میتوان با معکوس کردن آن، مسأله را به یک مسألهی کمینهسازی تبدیل نمود.
راهکارهای حل[ویرایش]
برای حل یک مسألهی برنامهریزی هندسی باید عوامل مختلفی را در نظر گرفت. مسائل برنامهریزی هندسی برای حل میبایست به شکل استاندارد باشد و همچنین شدنی بودن آن بررسی شود.
شدنی بودن[ویرایش]
برای حل یک مسألهی برنامهریزی هندسی، مسأله میبایست شدنی باشد. در صورتی که مسأله شدنی نباشد، برای آن پاسخ بهینه وجود ندارد. در این موارد میتوان حداقل یکی از قیود را ریلکس نمود. به منظور ریلکس سازی میتوان یک متغیر اسکالر جدید s به منظور یافتن یک مقدار که نزدیک به شدنی است، اضافه نمود. برنامهریزی هندسی به صورت زیر خواهد بود:
با حل مسألهی بالا مقادیر بهینهٔ و بدست میآید. بیانگر این است که مسألهی اصلی برنامهریزی هندسی چگونه شدنی است. به طور مثال در صورتی که باشد، برای مسأله اصلی برنامهریزی هندسی شدنی است. در صورتی که باشد، قرار داده میشود.
روشی دیگر برای بررسی مسائل برنامهریزی هندسی میتوان با تغییر قیود، تأثیر آنها را بر روی پاسخ بهینه بررسی نمود. این روش به شکل زیر مدل سازی میشود:
در مدل بالا به جای قیود نامساوی و مساوی با یک، پارامترهای و قرار داده شده است. در صورتی که u بزرگتر از یک باشد، قید نامساوی آزادتر، و در صورتی که کوچکتر از یک باشد، قید نامساوی محکم تر است. با قرار دادن مقادیر مختلف u و v میتوان تأثیر این مقادیر را بر پاسخ بهینه بررسی کرد.
شکل محدب[ویرایش]
مسائل برنامهریزی هندسی به طور کلی جزو مسائل بهینهسازی محدب نیستند، اما میتوان این مسائل را با تغییر متغیر و به مسائل بهینهسازی محدب تبدیل نمود. در این صورت قیود مونومیال به شکل زیر خواهند بود:
به طور مشابه قیود پوزینومیال نیز به شکل زیر خواهند بود:
با جایگذاری عبارات بدست آمده در مسألهی برنامهریزی هندسی، شکل مسأله به صورت زیر خواهد شد:
با توجه به این که لگاریتم یک تابع صعودی است، لگاریتم گرفتن از توابع هدف و قیود سبب تغییر نقطهی بهینه مسأله نخواهد نشد؛ بنابراین با لگاریتم گرفتن از توابع هدف و قیود مسألهی معادل زیر بدست خواهد آمد:
مسألهی بدست آمده یک مسألهی محدب است.
کاربردها[ویرایش]
- مهندسی
- طراحی فرایند جداسازی پوسته
- مسائل موازنهی شیمی
- بیشینهسازی آنتروپی
- بهینهسازی سیستمهای اتمی
- سایر حوزهها
- مدل فهرست اموال در علم مدیریت
- طراحی حمل و نقل
- بیشینهسازی قابلیت اطمینان
پیوند به بیرون[ویرایش]
https://optimization.mccormick.northwestern.edu/index.php/Geometric_programming
منابع[ویرایش]
- ↑ Boyd,Stephen & Vanderberghe, Lieven. Convex Optimization