برنامه‌سازی غیرخطی

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

در ریاضیات برنامه سازی غیر خطی ((Nonlinear programming (NLP) فرایند حل یک سیستم از برابری‌ها و نابرابری‌ها بر روی مجموعه‌ای از متغیرهای ناشناخته حقیقی، در یک تابع هدف که باید کمینه یا بیشینه شود و بخشی از محدودیت‌های آن غیر خطی است، می‌باشد.

روش های برنامه سازی غیر خطی[ویرایش]

روش لاگرانژ[ویرایش]

در این روش تابع هدف به صورت تابع F در نظر گرفته میشود.

این تابع بر زیرمجموعه‌ای چون X از فضای اقلیدسی تعریف شده است (پس عناصر X می توانند بردار باشند). این زیرمجموعه، توسط قیود به شکل g(x)=b تعریف می‌شود. تابع لاگرانژ در این حالت عبارت خواهد بود از: ((L(x،y)=F(x)+y.(b-g(x

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

روش برنامه ریزی مرتبه دوم[ویرایش]

برنامه ریزی مرتبه دوم ( QP ) روشی برای مینیمم سازی توابع مرتبه دوم n متغیره با m محدودیت خطی نامساوی یا مساوی و یا هر دو است.

مسائل برنامه ریزی مرتبه دوم ساده ترین فرم مسائل برنامه ریزی غیر خطی با محدودیت نا مساوی می باشد.

روش گرادیان کاهش یافته عمومی[ویرایش]

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

  • به دست آوردن مدل با نقاط عملیاتی و خطی کردن تمام محدودیت های تابع هدف حول نقاط عملیاتی . بطوریکه مساله به فرم برنامه ریزی خطی تبدیل شود . سپس استفاده از برنامه ریزی خطی برای حل مساله خطی .
  • تکرار روش برنامه ریزی خطی برای رسیدن به جواب مناسب با خطی کردن توابع محدودیت ها و تابع هدف و چنانچه به جواب مناسب نرسید با خطی کردن دوباره محدودیت ها و توابع هدف حول نقطه جدید optimum مساله پیدا می شود .

در روشهای ذکر شده ممکن است روش به همگرایی نرسد و این خود یکی از معایب روشهای فوق است به واقع بهترین الگوریتم عمومی حاضر استفاده از الگوریتم گرادیان کاهش یافته عمومی است.

کاربرد برنامه سازی غیر خطی[ویرایش]

یکی از مسائل پرکاربرد و معمول برای توابع غیر خطی و برنامه سازی غیر خطی مسائل مربوط به بهینه سازی است. مثلاً بهینه سازی هزینه حمل و نقل با انتخاب روش یا روش هایی از میان چندین روش نقل و انتقال است که هرکدام ظرفیت ها و محدودیت های متفاوتی دارند. به عنوان مثال نقل و انتقال نفت خام با انتخاب روش های ترکیبی از خط لوله، تانکر، راه آهن، حمل کننده های دریایی که هرکدام توابع هزینه ای متفاوتی دارند میتواند در نهایت به ما یک تابع غیر خطی از هزینه بدهد.

نمایش فرمولی مساله های بهینه سازی[ویرایش]

مساله بهینه سازی می‌تواند به صورت های مختلفی بیان شود مثلاً یکی از ساده ترین حالت ها این است که به صورت زیر بیان شود:

\max_{x \in X}f(x)

برای بیشینه کردن بعضی از متغیرها مانند توان عملیاتی محصول یا

\min_{x \in X}f(x)

برای کمینه کردن تابع هزینه در جایی که داریم:

f: R^n \to R
X \subseteq R^n.

روش‌های حل مساله[ویرایش]

اگر تابع هدف مساله به صورت f یک تابع خطی باشد و فضای محدوده یک Polytope باشد این مساله یک مساله برنامه نویسی خطی است که با روش های خطی شناخته شده به راحتی حل می شود.

اگر تابع هدف یک تابع Concave ( مساله به حداکثر رسانی ) یا یک تابع Convex ( مساله به حداقل رسانی )باشد و محدودیت ها از نوع محدب (convex) باشد، آنگاه مساله یک مساله محدب (convex) نامیده می شود و روش ها و متدهای عمومی برای بینه سازی محدب (Convex Optimization)میتوانند در اغلب این مساله ها مورد استفاده قرار گیرند. اگر تابع هدف نسبت تابعی مقعر (Concave) و محدب (Convex) باشد و محدودیت ها به صورت محدب باشد، این مساله میتواند به یک مساله بهینه سازی محدب تبدیل شود که در آن از تکنیک های برنامه نویسی کسری استفاده میشود.

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

مثال‌ها[ویرایش]

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

تقاطع خط با فضای محدوده، راه حل را نشان می‌دهد.

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

x۱ ≥ ۰
x۲ ≥ ۰
x۱۲ + x۲۲ ≥ ۱
x۱۲ + x۲۲ ≤ ۲

با تابع هدفی به صورت زیر که باید بیشینه شود:

f(x) = x۱ + x۲

درحالی که: (x = (x۱، x۲.

حل دو بعدی مساله.

نمونه سه بعدی[ویرایش]

اشتراک سطح بالایی با فضای محدوده در وسط، راه حل را نمایش می‌دهد.

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

x۱۲x۲۲ + x۳۲ ≤ ۲
x۱۲ + x۲۲ + x۳۲ ≤ ۱۰

با تابع هدفی به صورت زیر که باید بیشینه شود:

f(x) = x۱x۲ + x۲x۳

درحالی که: (x = (x۱، x۲، x۳.

حل سه بعدی مساله.

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

Bertsekas, Dimitri P. (1999). Nonlinear Programming (Second ed.). Cambridge, MA.: Athena Scientific. ISBN 1-886529-00-0. 

منابع برای مطالعه بیشتر[ویرایش]

پیوند به بیرون[ویرایش]