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

در ریاضیات بهینه‌سازی، برنامه‌ریزی کسری تعمیم یافته برنامه‌ریزی کسری-خطی است. تابع هدف در این مسئله به صورت نسبت دو تابع است که در حالت کلی خطی نیستند. بهینه‌سازی نسبت، معمولاً به بهینه‌سازی بازدهی یک سیستم مربوط می‌شود.https://en.wikipedia.org/wiki/Fractional_programming

 تعریف 
فرض کنید  توابع با مقدار حقیقی روی مجموعه  باشند. همچنین فرض کنید . آنگاه مسئله غیرخطی

به ازای  روی ، یک برنامه‌ریزی کسری است.

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

که  و  به ازای . این مساله با عنوان برنامه‌ریزی کسری تعمیم یافته یا برنامه‌ریزی کسری حداکثر-حداقل نیز شناخته می‌شودSchaible, Siegfried, and Toshidide Ibaraki. "Fractional programming." European Journal of Operational Research 12.4 (1983): 325-338..
حال اگر  ,  افاین باشند و  یک چندوجهی محدب باشد آنگاه مساله مورد نظر یک برنامه‌ریزی کسری خطی خواهد بود و به فرم زیر نوشته می‌شود:

که ، ، بالانویس T نشاندهنده ترانهاده است،  یک ماتریس  است و .

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

 کاربردها 
 کاربرد اقتصادی 
بازدهی یک سیستم گاهی اوقات به صورت نسبت ترم‌های اقتصادی و تکنیکی مشخصه سازی می‌گردد. که نتیجتاً حداکثرسازی بازدهی منجر به یک برنامه‌ریزی کسری می‌شود. معمولاً توابع هدف زیر در بحث اقتصاد مورد نظر هستند:
1- حداکثر سازی تولید
2- حداکثر سازی سوددهی نسبت به سرمایه‌گذاری
3- حداکثر درآمد نسبت به ریسک
4- حداقل سازی هزینه نسبت به زمان
5- حداکثرسازی خروجی نسبت به ورودی
 کاربرد غیر اقتصادی 
کاربردهای غیر اقتصادی از جمله تئوری اطلاعات، ریاضی و فیزیک کاربردی هستندSchaible, Siegfried. "Fractional programming." Handbook of global optimization. Springer US, 1995. 495-608..
 کاربردهای غیرمستقیم 
تعدادی از مسائل علم مدیریت وجود دارد که به‌طور غیرمستقیم به یک مساله برنامه‌ریزی کسری تبدیل می‌شوندSchaible, Siegfried. "Fractional programming: applications and algorithms." European Journal of Operational Research 7.2 (1981): 111-120..

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

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

برنامه‌ریزی‌های کسری مقعر (خطی) ویژگی‌های مشترکی با برنامه‌ریزی‌های مقعر (کسری) به شرح زیر دارندAvriel, Mordecai, et al. Generalized concavity. Society for Industrial and Applied Mathematics, 2010. :

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

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

iii) با فرض مشتق پذیر بودن <،  و  بر روی مجموعه  جواب شرایط بهینگی KKT مقدار بیشینه خواهد بود.

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

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

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

برخی از الگوریتم‌های برنامه‌ریزی مقعر به منظور برنامه‌ریزی‌های مقعر تعمیم یافته مناسب نیستندMartos, Béla. Nonlinear programming theory and methods. North-Holland, 1975.. بنابراین در ظاهر انتخاب الگوریتم‌های برنامه‌ریزی مقعر به منظور حل مسائل برنامه‌ریزی کسری مقعر با مشکل مواجه می‌گردد. با این وجود نشان داده می‌شود که هر برنامه‌ریزی کسری مقعر را می‌توان به یک برنامه‌ریزی مقعر تبدیل کرد. برای این منظور از تغییر متغیرهای زیر استفاده می‌گردد:

و

که مساله  را به صورت  تبدیل می نماید:

که یک مساله برنامه‌ریزی مقعر است.Schaible, Siegfried. "Parameter-free convex equivalent and dual programs of fractional programming problems." Zeitschrift für Operations Research 18 (1974): 187-196.

اگر  یک جواب بهینه برای  باشد آنگاه  یک جواب بهینه برای مساله  خواهد بود. این ایده اولین بار توسط Charnes و Cooper پیشنهاد گردیدCharnes, Abraham, and William W. Cooper. "Programming with linear fractional functionals." Naval Research logistics quarterly 9.3‐4 (1962): 181-186..

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

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

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

یکی از معایب حل مستقیم مساله  این است که مفاهیم دوگانی برنامه‌ریزی مقعر قابل استفاده نیستند. با این حال تبدیلی که در قسمت قبل تعریف شد اجازه استفاده از دوگانی برنامه‌ریزی مقعر را فراهم می‌سازد. بنابراین یک برنامه‌ریزی کسری دوگان را می‌توان برای برنامه‌ریزی مقعر معادل  تعریف کردSchaible, Siegfried. "Fractional programming. i, duality." Management Science 22.8 (1976): 858-867.. به‌طور مثال دوگان لاگرانژین  به برنامه‌ریزی کسری دوگان زیر منتج می‌گردد:

که  است.

4) حل یک مساله پارامتری :

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

که  یک پارامتر حقیقی است. مساله  گاهی اوقات راحتتر از مساله  به صورت عددی قابل پیگیری است. طبق Dinkelbach Dinkelbach, Werner. "On nonlinear fractional programming." Management science 13.7 (1967): 492-498. یک جواب بهینه برای  که  ریشه یکتا  است، حل مساله  نیز خواهد بود.

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

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

علاوه بر روش‌های کلاسیک که در بالا ذکر شدند، تکنیک‌های جدیدی به وجود آمدند که از نوع نقطه داخلی هستند. اولین این روش‌ها توسط Anstreicher برای مسائل برنامه‌ریزی کسری خطی پیشنهاد شدAnstreicher, Kurt M. "A monotonic projective algorithm for fractional linear programming." Algorithmica 1.1-4 (1986): 483-498.. بعد از آن هم Ferund و Jarre یک روش نقطه داخلی برای برنامه‌ریزی‌های کسری مقعر پیشنهاد کردندFreund, Roland W., and Florian Jarre. "An interior-point method for fractional programs with convex constraints." Mathematical Programming 67.1-3 (1994): 407-440..

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

 منابع 

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