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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف[ویرایش]

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

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

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

که و به ازای . این مساله با عنوان برنامه ریزی کسری تعمیم یافته یا برنامه ریزی کسری حداکثر-حداقل نیز شناخته می شود[۲]. حال اگر , افاین باشند و یک چندوجهی محدب باشد آنگاه مساله مورد نظر یک برنامه ریزی کسری خطی خواهد بود و به فرم زیر نوشته می شود:

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

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

کاربردها[ویرایش]

کاربرد اقتصادی[ویرایش]

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

کاربرد غیر اقتصادی[ویرایش]

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

کاربردهای غیرمستقیم[ویرایش]

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

نتایج الگوریتمی و نظری[ویرایش]

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

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

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

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

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

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

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

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

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

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

و

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

که یک مساله برنامه ریزی مقعر است.[۸]

اگر یک جواب بهینه برای باشد آنگاه یک جواب بهینه برای مساله خواهد بود. این ایده اولین بار توسط Charnes و Cooper پیشنهاد گردید[۹].

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

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

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

یکی از معایب حل مستقیم مساله این است که مفاهیم دوگانی برنامه ریزی مقعر قابل استفاده نیستند. با این حال تبدیلی که در قسمت قبل تعریف شد اجازه استفاده از دوگانی برنامه ریزی مقعر را فراهم می سازد. بنابراین یک برنامه ریزی کسری دوگان را می توان برای برنامه ریزی مقعر معادل تعریف کرد[۱۰]. به طور مثال دوگان لاگرانژین به برنامه ریزی کسری دوگان زیر منتج می گردد:

که است.

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

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

که یک پارامتر حقیقی است. مساله گاهی اوقات راحتتر از مساله به صورت عددی قابل پیگیری است. طبق Dinkelbach [۱۱] یک جواب بهینه برای که ریشه یکتا است، حل مساله نیز خواهد بود.

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

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

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

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

منابع[ویرایش]

  1. https://en.wikipedia.org/wiki/Fractional_programming
  2. Schaible, Siegfried, and Toshidide Ibaraki. "Fractional programming." European Journal of Operational Research 12.4 (1983): 325-338.
  3. http://www.mmm.muroran-it.ac.jp/~shi/ss04.pdf
  4. ۴٫۰ ۴٫۱ Schaible, Siegfried. "Fractional programming." Handbook of global optimization. Springer US, 1995. 495-608.
  5. Schaible, Siegfried. "Fractional programming: applications and algorithms." European Journal of Operational Research 7.2 (1981): 111-120.
  6. Avriel, Mordecai, et al. Generalized concavity. Society for Industrial and Applied Mathematics, 2010.
  7. Martos, Béla. Nonlinear programming theory and methods. North-Holland, 1975.
  8. Schaible, Siegfried. "Parameter-free convex equivalent and dual programs of fractional programming problems." Zeitschrift für Operations Research 18 (1974): 187-196.
  9. Charnes, Abraham, and William W. Cooper. "Programming with linear fractional functionals." Naval Research logistics quarterly 9.3‐4 (1962): 181-186.
  10. Schaible, Siegfried. "Fractional programming. i, duality." Management Science 22.8 (1976): 858-867.
  11. Dinkelbach, Werner. "On nonlinear fractional programming." Management science 13.7 (1967): 492-498.
  12. Anstreicher, Kurt M. "A monotonic projective algorithm for fractional linear programming." Algorithmica 1.1-4 (1986): 483-498.
  13. Freund, Roland W., and Florian Jarre. "An interior-point method for fractional programs with convex constraints." Mathematical Programming 67.1-3 (1994): 407-440.