آشنایی با برنامه ریزی هندسی

معرفی و شمای کلی

نظریه برنامه‌ریزی هندسی (Geometric Programming) یا به اختصار GP در سال‌های ۱۹۶۱ الی ۱۹۶۷ توسط فیزیکدان نظری آقای زنر (Clarence Zener) مطرح گردید. هدف از این کار ارائه راهکار مطمئن برای حل مسایل غیرخطی با ساختارهای مشخص بود. متعاقبا در سال‌های بعدی آقای دافین (Richard Duffin) نظریه دوگان را برای حل مسایل غیرخطی در قالب برنامه‌ریزی هندسی ارائه کرد. از طرفی مشخصه‌های ساختاری مسایل برنامه‌ریزی هندسی، محققان و متخصصین حوزه بهینه‌سازی را به سمت طراحی الگوریتم‌های کارا مانند روش نقطه داخلی برای حل این دسته مسایل سوق داده است. به طور کلی مسایل GP دسته‌ی متمایزی از مسایل بهینه‌سازی در مجموعه‌ی برنامه‌ریزی محدب (Convex Programming) هستند.

جهت بررسی ساختار یک مساله GP ابتدا دو عبارت مهم بایستی مطرح شوند.

در تابع مونومیال (monomial) متغیرهای \( x \) همیشه مثبت، پارامتر \( c>0 \) و پارامتر \( a_i \) مقدار حقیقی دلخواه می‌باشد.

$$f(x) = cx_1^{a_1} x_2^{a_2}… x_n^{a_n}$$

تابع پورینومیال (posynomial) شامل مجموع چند تابع مونومیال می‌باشد.

$$f(x) = \sum_{k=1}^K c_k x_1^{a_{1k}} x_2^{a_{2k}}… x_n^{a_{nk}}$$

بنابراین شمای کلی مساله GP به فرم زیر است.

$$\textbf{minimize} \quad f_0(x) \\ \text{subject to} \quad f_i(x) \leq 1, \quad i=1,…,m \\ h_i(x) = 1, \quad i=1,…,p$$

که \( f_i \) پوزینامیال و \( h_i \) مونومیال است.

نظریه دوگان

آقای دافین (Richard Duffin) در سال ۱۹۶۷ با انتشار کتاب Geometric Programming نظریه دوگان را برای مسایل GP مطرح کردند. ایشان در طی مطالعات خود نشان دادند که دوگان یک مساله GP به صورت زیر می‌باشد.

$$\textbf{maximize} \quad g_0(\lambda,\delta)=\prod_{k=0}^p \{\lambda_k^{\lambda_k} \prod_{i \in [k]} (c_i/\delta_i)^{\delta_i} \} \\ \text{subject to} \quad \sum_{i \in [k]} \delta_i = \lambda_k, \quad k=0,1,…,p \\ \sum_{i =1}^n a_{ij} \delta_i = 0, \quad j=1,…,m \\ \lambda_0 =1 \\\delta_i \geq 0, \quad \lambda_k \geq 0, \quad \forall i,k$$

محدودیت دوم این مدل به محدودیت‌های Orthogonality و محدودیت‌های اول و سوم به محدودیت‌های Normality مشهورند.

مثال کاربردی

فرض کنید شرکتی قصد دارد مخزن‌های نفتی با کمترین هزینه ساخت رویه طراحی کند. حداقل ظرفیت هر مخزن بایستی به میزان \( ۱۰۰۰\pi \) باشد. بنابراین متغیرهای تصمیم مساله ارتفاع \( x_1 \) (به متر) و شعاع \( x_2 \) (به متر) می‌باشند. محدودیت حداقل ظرفیت را می‌توان به صورت زیر در نظر گرفت:

$$ x_1(\pi x_2^2) \geq 1000 \pi$$

که قابل تبدیل به محدودیت استاندارد دارای عبارات پوزینامیال می‌باشد:

$$ (۱۰۰۰) x_1^{-1}x_2^{-2} \leq 1$$

بنابراین مساله اولیه GP به فرم زیر خواهد بود:

$$\textbf{minimize} \quad 2\pi x_2^2 + 2\pi x_1 x_2 \\ \text{subject to} \quad 1000x_1^{-1}x_2^{-2} \leq 1 \\ x_1,x_2 >0 $$

عبارت اول تابع هدف مساحت کف و در مخزن بوده و عبارت دوم مساحت جانبی آن می‌باشد. در مدل ارائه شده سه عبارت مونومیال وجود دارد که دو تای آنها در تابع هدف و یکی از آنها در محدودیت می‌باشد. از طرفی در مساله دوگان متناظر به ازای هر عبارت مونومیال یک متغیر دوگان و به ازای هر متغیر مساله اصلی یک محدودیت دوگان نوشته می‌شود. بنابراین فرم دوگان این مثال شامل سه متغیر و دو محدودیت اصلی (Orthogonality)، یک محدودیت نرمالیزه شده (Normality) و یک محدودیت تناظر لاگرانژ است.

بنابراین طبق تعریف، دوگان این مساله به فرم زیر خواهد بود:

$$\textbf{maximize} \quad (2\pi/\delta_1)^{\delta_1} (2\pi/\delta_2)^{\delta_2} (1000/\delta_3)^{\delta_3} \lambda_1^{\lambda_1} \\ \text{subject to} \quad \delta_1 + \delta_2 = 1 \\ \delta_2 – \delta_3 = 0 \\ 2\delta_1 + \delta_2 – 2\delta_3 = 0 \\ \delta_3 = \lambda_1 \\ \delta_1, \delta_2, \delta_3,\lambda_1 \geq 0 $$

واضح است که فضای شدنی مساله دوگان یک نقطه است چرا که محدودیت‌ها تشکیل یک سیستم با چهار معادله و چهار مجهول را می‌دهند (در این حالت گفته می‌شود که درجه سختی مساله GP صفر می‌باشد).

$$ \delta_1 + \delta_2 = 1 \\ \delta_2 – \delta_3 = 0 \\ 2\delta_1 + \delta_2 – 2\delta_3 = 0 \\ \delta_3 = \lambda_1$$

پس از حل داریم:

$$ \delta_1^* = 1/3, \delta_2^*= 2/3, \delta_3^*= 2/3, \lambda_1^*=2/3 \\ g_0(x^*) = 1187.45 $$

این جواب بهینه و منحصربفرد دوگان می‌باشد که جواب بهینه‌ی اولیه نیز است. از طرفی مقادیر \( \delta_1^* \) و \( \delta_2^* \) نشان دهنده سهم هریک از عبارات مونومیال در تابع هدف اصلی می‌باشند.

بنابراین:

$$ x_2^* = 7.93 \text{meters} \\ x_1^* = 15.87 \text{meters} $$

نرم‌افزار CVX

روش مبتنی بر نظریه دوگان، زمانی که مساله از درجه‌ی سختی بزرگتر از صفر برخوردار هست کارا نمی‌باشد. حال قصد حل این مثال به کمک پکیج CVX را داریم. پکیج CVX یک سیستم مدل‌سازی مبنی بر نرم‌افزار MATLAB برای مسایل برنامه‌ریزی محدب است که توسط پروفسور بوید (Stephen Boyd) و همکارانش توسعه داده شده است. این پکیج از مسایل دسته GP نیز پشتیبانی می‌کند و از لینک CVX: Matlab Software for Disciplined Convex Programming قابل دریافت می‌باشد.

کد متلب مرتبط با مثال در قسمت زیر آورده شده است:

 n=2;
 C = 2*pi;
 cvx_begin gp
 variables x(n)
 obj= C*x(2)^2 + C*x(1)*x(2);
 minimize( obj )
 subject to
 (x(1)^-1)*(x(2)^-2)*1000 <= 1;
 cvx_end

در صورت علاقه‌مندی جهت کسب اطلاعات بیشتر به منابع و مقالات زیر رجوع فرمایید:

  • Rajgopal, J. Geometric Programming. Wiley Encyclopedia of Operations Research and Management Science.
  • T. R. Jefferson and C. H. Scott, Geometric Programming, in Decision Technologies and Applications, INFORMS, 2009, pp. 4–۸۱٫
0 Comments
Inline Feedbacks
View all comments