برنامه‌ریزی هندسی

برنامه‌ریزی هندسی در سال ۱۹۶۷ توسط دافین، پترسون و زنر معرفی گردید. برنامه‌ریزی هندسی روشی کارآمد برای برخی از مسائل برنامه‌ریزی غیرخطی بوده و زیر مجموعه‌ای از مسائل سیگنومیال است. به کمک برنامه‌ریزی هندسی می‌توان مسائل کاربردی و در مقیاس بزرگ را به مدل بهینه‌سازی ریاضی تبدیل کرده و حل نمود. از کاربردهای GP می‌توان به طراحی مدارهای الکتریکی، مسائل مالی و آماری اشاره نمود.

نحوهٔ فرمول‌بندی

فرم استاندار

مسائل برنامه‌ریزی هندسی متشکل از تابع هدف پوزینومیال، قیود نامساوی پوزینومیال و قیود تساوی مونومیال هستند.

مونومیال به شکل زیر تعریف می‌شود:

$f(x)\,\!$ $=Cx_{1}^{a_{1}}x_{2}^{a_{2}}...x_{n}^{a_{n}}\qquad$ $C>0\qquad$$a_{i}\in \mathbb {R}$

پوزینومیال مجموع K جملهٔ مونومیال است:

$f(x)\,\!$$=\sum _{k=1}^{K}\ C_{k}x_{1}^{a_{1}k}x_{2}^{a_{2}k}...x_{n}^{a_{n}k}\qquad$

شکل استاندارد یک مسأله‌ی برنامه‌ریزی هندسی به صورت زیر است:

$minimize\qquad f_{0}(x)\,\!$

$subject\quad to\qquad f_{i}(x)\,\!$ $\leq 1,\qquad i=1,2,...,m$

$\qquad \qquad \quad \qquad h_{i}(x)\,\!$ $=1,\qquad i=1,2,...,p$

$x_{i}$ پارامتر بهینه‌سازی است. در بسیاری از موارد، برنامه‌ریزی هندسی می‌بایست به فرم استاندارد تبدیل شود. در صورتی که مسأله یک مسأله‌ی بیشینه‌سازی باشد می‌توان با معکوس کردن آن، مسأله را به یک مسأله‌ی کمینه‌سازی تبدیل نمود.

راهکارهای حل

برای حل یک مسأله‌ی برنامه‌ریزی هندسی باید عوامل مختلفی را در نظر گرفت. مسائل برنامه‌ریزی هندسی برای حل می‌بایست به شکل استاندارد باشد و همچنین شدنی بودن آن بررسی شود.

شدنی بودن

برای حل یک مسأله‌ی برنامه‌ریزی هندسی، مسأله می‌بایست شدنی باشد. در صورتی که مسأله شدنی نباشد، برای آن پاسخ بهینه وجود ندارد. در این موارد می‌توان حداقل یکی از قیود را ریلکس نمود. به منظور ریلکس سازی می‌توان یک متغیر اسکالر جدید s به منظور یافتن یک مقدار ${\hat {x}}$ که نزدیک به شدنی است، اضافه نمود. برنامه‌ریزی هندسی به صورت زیر خواهد بود:

$minimize\qquad s\,\!$

$subject\quad to\qquad f_{i}(x)\,\!$ $\leq s,\qquad i=1,2,...,m$

$\qquad \qquad \quad \qquad h_{i}(x)\,\!$ $=s,\qquad i=1,2,...,p$
$\qquad \qquad \qquad \quad s\geq 1$

با حل مسأله‌ی بالا مقادیر بهینهٔ ${\bar {x}}$ و ${\bar {s}}$ بدست می‌آید. ${\bar {s}}$ بیانگر این است که مسأله‌ی اصلی برنامه‌ریزی هندسی چگونه شدنی است. به طور مثال در صورتی که ${\bar {s}}=1$ باشد، ${\bar {x}}$ برای مسأله اصلی برنامه‌ریزی هندسی شدنی است. در صورتی که $s>1$ باشد، ${\bar {x}}={\hat {x}}$ قرار داده می‌شود.
روشی دیگر برای بررسی مسائل برنامه‌ریزی هندسی می‌توان با تغییر قیود، تأثیر آن‌ها را بر روی پاسخ بهینه بررسی نمود. این روش به شکل زیر مدل سازی می‌شود:

$minimize\qquad f_{0}(x)\,\!$

$subject\quad to\qquad f_{i}(x)\,\!$ $\leq u_{i},\qquad i=1,2,...,m$

$\qquad \qquad \quad \qquad h_{i}(x)\,\!$ $=v_{i},\qquad i=1,2,...,p$

در مدل بالا به جای قیود نامساوی و مساوی با یک، پارامترهای $u$ و $v$ قرار داده شده است. در صورتی که u بزرگ‌تر از یک باشد، قید نامساوی آزادتر، و در صورتی که کوچکتر از یک باشد، قید نامساوی محکم تر است. با قرار دادن مقادیر مختلف u و v می‌توان تأثیر این مقادیر را بر پاسخ بهینه بررسی کرد.

شکل محدب

مسائل برنامه‌ریزی هندسی به طور کلی جزو مسائل بهینه‌سازی محدب نیستند، اما می‌توان این مسائل را با تغییر متغیر $x_{i}=log(y_{i})$ و $b=log(C)$ به مسائل بهینه‌سازی محدب تبدیل نمود. در این صورت قیود مونومیال به شکل زیر خواهند بود:

${\begin{aligned}h_{i}(x)&=Cx_{1}^{a_{1}}x_{2}^{a_{2}}...x_{n}^{a_{n}}\\&=Ce^{a_{1}y_{1}}e^{a_{2}y_{2}}....e^{a_{n}y_{n}}\\&=e^{a^{T}y+b}\\\end{aligned}}$

به طور مشابه قیود پوزینومیال نیز به شکل زیر خواهند بود:

$f_{i}(x)\,\!$$=\sum _{k=1}^{K}\ e^{a_{k}^{T}y+b_{k}}$

با جایگذاری عبارات بدست آمده در مسأله‌ی برنامه‌ریزی هندسی، شکل مسأله به صورت زیر خواهد شد:

$minimize\qquad \sum _{k=1}^{K}\ e^{a_{0}k^{T}y+b_{0}k}\,\!$

$subject\quad to\qquad \sum _{k=1}^{K}\ e^{a_{i}k^{T}y+b_{i}k}\,\!$ $\leq 1,\qquad i=1,2,...,m$

$\qquad \qquad \quad \qquad e^{g_{i}^{T}y+b_{i}}\,\!$ $=1,\qquad i=1,2,...,p$

با توجه به این که لگاریتم یک تابع صعودی است، لگاریتم گرفتن از توابع هدف و قیود سبب تغییر نقطه‌ی بهینه مسأله نخواهد نشد؛ بنابراین با لگاریتم گرفتن از توابع هدف و قیود مسأله‌ی معادل زیر بدست خواهد آمد:

$minimize\qquad log(\sum _{k=1}^{K}\ e^{a_{0}k^{T}y+b_{0}k})\,\!$

$subject\quad to\qquad log(\sum _{k=1}^{K}\ e^{a_{i}k^{T}y+b_{i}k})\,\!$ $\leq 0,\qquad i=1,2,...,m$

$\qquad \qquad \quad \qquad log(e^{g_{i}^{T}y+b_{i}})\,\!$ $=0,\qquad i=1,2,...,p$

مسأله‌ی بدست آمده یک مسأله‌ی محدب است.

کاربردها

1. مهندسی
   • طراحی فرایند جداسازی پوسته
   • مسائل موازنه‌ی شیمی
   • بیشینه‌سازی آنتروپی
   • بهینه‌سازی سیستم‌های اتمی
2. سایر حوزه‌ها
   • مدل فهرست اموال در علم مدیریت
   • طراحی حمل و نقل
   • بیشینه‌سازی قابلیت اطمینان

پیوند به بیرون

https://optimization.mccormick.northwestern.edu/index.php/Geometric_programming

---