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

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

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

فرم استاندار

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

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

الگو:چپ‌چین

$f(x)$ $=C{x}_1^{a_1}{x}_2^{a_2}...x_n^{a_n}$ $C>0$$a_i\in ℝ$

الگو:پایان چپ‌چین الگو:سخ پوزینومیال مجموع K جملهٔ مونومیال است:الگو:سخ الگو:چپ‌چین الگو:درشت الگو:پایان چپ‌چین الگو:سخ شکل استاندارد یک مسأله‌ی برنامه‌ریزی هندسی به صورت زیر است:

الگو:چپ‌چین $minimize{f}_0(x)$

$subjectto{f}_i(x)$ $\le 1,i=1,2,...,m$

$h_i(x)$ $=1,i=1,2,...,p$ الگو:پایان چپ‌چین $x_i$ پارامتر بهینه‌سازی است. در بسیاری از موارد، برنامه‌ریزی هندسی می‌بایست به فرم استاندارد تبدیل شود. در صورتی که مسأله یک مسأله‌ی بیشینه‌سازی باشد می‌توان با معکوس کردن آن، مسأله را به یک مسأله‌ی کمینه‌سازی تبدیل نمود.

راهکارهای حل

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

شدنی بودن

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

$subjectto{f}_i(x)$ $\le s,i=1,2,...,m$

$h_i(x)$ $=s,i=1,2,...,p$الگو:سخ $s\ge 1$ الگو:پایان چپ‌چینالگو:سخ با حل مسأله‌ی بالا مقادیر بهینهٔ $\overline{x}$ و $\overline{s}$ بدست می‌آید. $\overline{s}$ بیانگر این است که مسأله‌ی اصلی برنامه‌ریزی هندسی چگونه شدنی است. به طور مثال در صورتی که $\overline{s}=1$ باشد، $\overline{x}$ برای مسأله اصلی برنامه‌ریزی هندسی شدنی است. در صورتی که $s>1$ باشد، $\overline{x}=\hat{x}$ قرار داده می‌شود.الگو:سخ روشی دیگر برای بررسی مسائل برنامه‌ریزی هندسی می‌توان با تغییر قیود، تأثیر آن‌ها را بر روی پاسخ بهینه بررسی نمود. این روش به شکل زیر مدل سازی می‌شود:الگو:سخ الگو:چپ‌چین $minimize{f}_0(x)$

$subjectto{f}_i(x)$ $\le u_i,i=1,2,...,m$

$h_i(x)$ $=v_i,i=1,2,...,p$ الگو:پایان چپ‌چینالگو:سخ در مدل بالا به جای قیود نامساوی و مساوی با یک، پارامترهای $u$ و $v$ قرار داده شده است. در صورتی که u بزرگ‌تر از یک باشد، قید نامساوی آزادتر، و در صورتی که کوچکتر از یک باشد، قید نامساوی محکم تر است. با قرار دادن مقادیر مختلف u و v می‌توان تأثیر این مقادیر را بر پاسخ بهینه بررسی کرد.

شکل محدب

مسائل برنامه‌ریزی هندسی به طور کلی جزو مسائل بهینه‌سازی محدب نیستند، اما می‌توان این مسائل را با تغییر متغیر $x_i=log(y_i)$ و $b=log(C)$ به مسائل بهینه‌سازی محدب تبدیل نمود. در این صورت قیود مونومیال به شکل زیر خواهند بود:الگو:سخ الگو:چپ‌چین $\begin{array}{cc}{h}_i(x)& =C{x}_1^{a_1}{x}_2^{a_2}...x_n^{a_n}\\ & =C{e}^{a_1{y}_1}{e}^{a_2{y}_2}....e^{a_n{y}_n}\\ & =e^{a^{T}y+b}\\ \end{array}$ الگو:پایان چپ‌چین به طور مشابه قیود پوزینومیال نیز به شکل زیر خواهند بود:الگو:سخ الگو:چپ‌چین $f_i(x)$$=\sum _{k=1}^K{e}^{a_k^{T}y+b_k}$ الگو:پایان چپ‌چینالگو:سخ با جایگذاری عبارات بدست آمده در مسأله‌ی برنامه‌ریزی هندسی، شکل مسأله به صورت زیر خواهد شد:

الگو:چپ‌چین $minimize\sum _{k=1}^K{e}^{a_0{k}^{T}y+b_{0}k}$

$subjectto\sum _{k=1}^K{e}^{a_i{k}^{T}y+b_{i}k}$ $\le 1,i=1,2,...,m$

$e^{g_i^{T}y+b_i}$ $=1,i=1,2,...,p$ الگو:پایان چپ‌چین با توجه به این که لگاریتم یک تابع صعودی است، لگاریتم گرفتن از توابع هدف و قیود سبب تغییر نقطه‌ی بهینه مسأله نخواهد نشد؛ بنابراین با لگاریتم گرفتن از توابع هدف و قیود مسأله‌ی معادل زیر بدست خواهد آمد:الگو:سخ الگو:چپ‌چین $minimizelog(\sum _{k=1}^K{e}^{a_0{k}^{T}y+b_{0}k})$

$subjecttolog(\sum _{k=1}^K{e}^{a_i{k}^{T}y+b_{i}k})$ $\le 0,i=1,2,...,m$

$log(e^{g_i^{T}y+b_i})$ $=0,i=1,2,...,p$ الگو:پایان چپ‌چینالگو:سخ مسأله‌ی بدست آمده یک مسأله‌ی محدب است.

کاربردها

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

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

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

---