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

در ریاضیات بهینه‌سازی، برنامه‌ریزی کسری تعمیم یافته برنامه‌ریزی کسری-خطی است. تابع هدف در این مسئله به صورت نسبت دو تابع است که در حالت کلی خطی نیستند. بهینه‌سازی نسبت، معمولاً به بهینه‌سازی بازدهی یک سیستم مربوط می‌شود.

تعریف

فرض کنید $f,g,h_{j},j=1,\ldots ,m$ توابع با مقدار حقیقی روی مجموعه $\mathbf {S} _{0}\subset \mathbb {R} ^{n}$ باشند. همچنین فرض کنید $\mathbf {S} =\{{\boldsymbol {x}}\in \mathbf {S} _{0}:h_{j}({\boldsymbol {x}})\leq 0,j=1,\ldots ,m\}$. آنگاه مسئله غیرخطی

$(P)\;\;\;\;\;\;{\underset {{\boldsymbol {x}}\in \mathbf {S} }{\text{maximize}}}\quad {\frac {f({\boldsymbol {x}})}{g({\boldsymbol {x}})}},$

به ازای $g({\boldsymbol {x}})>0$ روی $\mathbf {S}$، یک برنامه‌ریزی کسری است.

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

$\max \left\{{\mathop {\min } \limits _{1\leqslant i\leqslant p}{q_{i}}\left(x\right):x\in S}\right\}$

که ${q_{i}}\left(x\right)={\frac {{f_{i}}\left(x\right)}{{g_{i}}\left(x\right)}}$ و ${g_{i}}\left(x\right)>0$ به ازای ${x\in S}$. این مساله با عنوان برنامه‌ریزی کسری تعمیم یافته یا برنامه‌ریزی کسری حداکثر-حداقل نیز شناخته می‌شود. حال اگر $g$ , $f$ افاین باشند و $S$ یک چندوجهی محدب باشد آنگاه مساله مورد نظر یک برنامه‌ریزی کسری خطی خواهد بود و به فرم زیر نوشته می‌شود:

$\max \left\{{{\frac {{c^{T}}x+\alpha }{{d^{T}}x+\beta }}:Ax\leqslant b,x\geqslant 0}\right\}$

که $c,d\in {\mathbb {R} ^{n}}$، $\alpha ,\beta \in \mathbb {R}$، بالانویس T نشاندهنده ترانهاده است، $A$ یک ماتریس $m\times n$ است و $b\in {\mathbb {R} ^{m}}$.

در تعمیم برنامه‌ریزی کسری خطی، مساله اخیر را برنامه‌ریزی کسری مقعر می نامند اگر که صورت کسر (تابع $f$) بر روی $S_{0}$ مقعر باشد و $g$ و $h_{j}$ روی مجموعه محدب $S_{0}$ محدب باشند. همچنین اگر $g$ افاین نباشد آنگاه $f$ را نامنفی در نظر می‌گیرند. توجه شود که تابع هدف مساله برنامه‌ریزی کسری مقعر معمولاً یک تابع مقعر نیست. به‌طور کلی تمرکز در برنامه‌ریزی کسری بر روی تابع هدف است و ساختار نسبت آن تابع. ناحیه شدنی هم فرض می‌شود یک مجموعه محدب باشد یا یک چندوجهی محدب در نظر گرفته می‌شود.

کاربردها

کاربرد اقتصادی

بازدهی یک سیستم گاهی اوقات به صورت نسبت ترم‌های اقتصادی و تکنیکی مشخصه سازی می‌گردد. که نتیجتاً حداکثرسازی بازدهی منجر به یک برنامه‌ریزی کسری می‌شود. معمولاً توابع هدف زیر در بحث اقتصاد مورد نظر هستند: 1- حداکثر سازی تولید 2- حداکثر سازی سوددهی نسبت به سرمایه‌گذاری 3- حداکثر درآمد نسبت به ریسک 4- حداقل سازی هزینه نسبت به زمان 5- حداکثرسازی خروجی نسبت به ورودی

کاربرد غیر اقتصادی

کاربردهای غیر اقتصادی از جمله تئوری اطلاعات، ریاضی و فیزیک کاربردی هستند.

کاربردهای غیرمستقیم

تعدادی از مسائل علم مدیریت وجود دارد که به‌طور غیرمستقیم به یک مساله برنامه‌ریزی کسری تبدیل می‌شوند.

نتایج الگوریتمی و نظری

به‌طور معمول مسائل کسری یا به صورت برنامه‌ریزی کسری مقعر هستند یا به صورت برنامه‌ریزی کسری خطی. معمولاً استراتژی‌های حل این مسائل به صورت زیر هستند:

1) حل مسائل برنامه‌ریزی شبه مقعر $(P)$:

برنامه‌ریزی‌های کسری مقعر (خطی) ویژگی‌های مشترکی با برنامه‌ریزی‌های مقعر (کسری) به شرح زیر دارند :

i) بیشینه محلی همان بیشینه عمومی است.

ii) مقدار بیشینه یکتا است اگر که یا صورت کسر اکیداً مقعر باشد یا مخرج کسر اکیداً محدب باشد.

iii) با فرض مشتق پذیر بودن <$g$، $h_{j}$ و $h_{j}$ بر روی مجموعه $S_{0}$ جواب شرایط بهینگی KKT مقدار بیشینه خواهد بود.

iv) در یک مساله برنامه‌ریزی کسری خطی، به شرط وجود مقدار بهینه، این مقدار در نقطه انتهایی چندوجهی محدب $S$ رخ خواهد داد.

با توجه به ویژگی‌هایی که بیان شد، امکان این وجود دارد که مسائل برنامه‌ریزی کسری مقعر را با استفاده از الگوریتم‌های استاندارد موجود برای برنامه‌ریزی مقعر حل نمود. اگر $(P)$ یک برنامه‌ریزی کسری خطی باشد، آنگاه ویژگی iv می‌تواند به منظور حل $(P)$ توسط روندی مانند سیمپلکس استفاده شود.

2) حل یک مساله برنامه‌ریزی مقعر معادل ( $(P')$):

برخی از الگوریتم‌های برنامه‌ریزی مقعر به منظور برنامه‌ریزی‌های مقعر تعمیم یافته مناسب نیستند. بنابراین در ظاهر انتخاب الگوریتم‌های برنامه‌ریزی مقعر به منظور حل مسائل برنامه‌ریزی کسری مقعر با مشکل مواجه می‌گردد. با این وجود نشان داده می‌شود که هر برنامه‌ریزی کسری مقعر را می‌توان به یک برنامه‌ریزی مقعر تبدیل کرد. برای این منظور از تغییر متغیرهای زیر استفاده می‌گردد:

$t={\frac {1}{g({\boldsymbol {x}})}}$ و ${\boldsymbol {y}}={\frac {\boldsymbol {x}}{g({\boldsymbol {x}})}}$

که مساله $(P)$ را به صورت $(P')$ تبدیل می نماید:

$\left({P'}\right)\;\;\;\;\;\max \left\{{tf\left({\frac {y}{t}}\right):{\begin{array}{*{20}{c}}{t{h_{k}}\left({\frac {y}{t}}\right)\leqslant 0,k=1,...,m}\\{tg\left({\frac {y}{t}}\right)\leqslant 1,{\frac {y}{t}}\in {S_{0}},t>0}\end{array}}}\right\}$

که یک مساله برنامه‌ریزی مقعر است.

اگر ${\frac {\bar {y}}{\bar {t}}}$ یک جواب بهینه برای $(P')$ باشد آنگاه ${{\bar {x}}={\frac {\bar {y}}{\bar {t}}}}$ یک جواب بهینه برای مساله $(P)$ خواهد بود. این ایده اولین بار توسط Charnes و Cooper پیشنهاد گردید.

به دلیل این چنین تبدیلی به برنامه‌ریزی مقعر، مسائل برنامه‌ریزی کسری مقعر می‌توانند توسط الگوریتم‌های موجود مربوط به برنامه‌ریزی مقعر حل شوند.

به‌طور خاص با اعمال تبدیل بر روی برنامه‌ریزی کسری خطی به مساله برنامه‌ریزی خطی زیر می‌رسیم:

$\max \left\{{{c^{T}}y+\alpha t:Ay-bt\leqslant 0,{d^{T}}y+\beta t=1,y\geqslant 0,t>0}\right\}$

3) حل برنامه‌ریزی دوگان $(D)$:

یکی از معایب حل مستقیم مساله $(P)$ این است که مفاهیم دوگانی برنامه‌ریزی مقعر قابل استفاده نیستند. با این حال تبدیلی که در قسمت قبل تعریف شد اجازه استفاده از دوگانی برنامه‌ریزی مقعر را فراهم می‌سازد. بنابراین یک برنامه‌ریزی کسری دوگان را می‌توان برای برنامه‌ریزی مقعر معادل $(P')$ تعریف کرد. به‌طور مثال دوگان لاگرانژین $(P')$ به برنامه‌ریزی کسری دوگان زیر منتج می‌گردد:

$\left(D\right)\,\,\,\,\,\,\min \left\{{\mathop {\sup } \limits _{x\in C}{\frac {f\left(x\right)-{u^{T}}H\left(x\right)}{g\left(x\right)}}:u\geqslant 0}\right\}$

که $H={\left\{{{h_{1}},...,{h_{m}}}\right\}^{T}}$ است.

4) حل یک مساله پارامتری $(P_{q})$:

کلاس‌های زیادی از الگوریتم‌ها بر اساس مساله پارامتری زیر که مرتبط با $(P)$ هستند وجود دارند:

$\left({P_{q}}\right)\;\;\;\;\pi \left(q\right)=\max \left\{{f\left(x\right)-qg\left(x\right):x\in S}\right\}$

که ${q\in \mathbb {R} }$ یک پارامتر حقیقی است. مساله $(P_{q})$ گاهی اوقات راحتتر از مساله $(P)$ به صورت عددی قابل پیگیری است. طبق Dinkelbach یک جواب بهینه برای $\left({P_{\bar {q}}}\right)$ که ${\bar {q}}$ ریشه یکتا $\pi \left(q\right)=0$ است، حل مساله $(P)$ نیز خواهد بود.

هر کدام از 4 روشی که تا به حال ذکر شدند ویژگی‌های خاص خود را دارند که برخی کاربردها و ویژگی‌های آن‌ها در مرجع با جزئیات مطرح شده‌اند.

5) روش‌های نقطه داخلی

علاوه بر روش‌های کلاسیک که در بالا ذکر شدند، تکنیک‌های جدیدی به وجود آمدند که از نوع نقطه داخلی هستند. اولین این روش‌ها توسط Anstreicher برای مسائل برنامه‌ریزی کسری خطی پیشنهاد شد. بعد از آن هم Ferund و Jarre یک روش نقطه داخلی برای برنامه‌ریزی‌های کسری مقعر پیشنهاد کردند.

جالب توجه است که برخی از این پنج استراتژی که مطرح شدند در ارتباط با مسائل مختلف برنامه‌ریزی کسری مقعر (خطی) که دارای ناحیه شدنی فشرده هستند می‌توانند عملکرد یکسانی داشته باشند. با این حال ممکن است یک استراتژی نسبت به استراتژی دیگر دارای بار محاسباتی بیشتری باشد.