بخشی از مقاله
اثبات برنامه ریزی خطی از شرایط مرتبه دوم برنامه ریزی غیر خطی
خلاصه مطالب
در این نوشته ما به ارائه یادداشت جدیدی از شرایط استاندارد مرتبه اول و دوم در موقعیت های ضروری تحت شرایط محدودماندگاسرین – فرومویز (MFCQ) برای مسائل برنامه ریزی غیر خطی می پردازیم .
ما تحت شرایط محدودیت به کار منحنی توسط MFCQ خواهیم پرداخت . این امر باعث کاهش امکانات در اثبات آسان تحت محدودیت های نابرابر MFCQ میگردد. و همچنین استفاده آرام از نابرابریها و محدودیت ها را با استفاده از تابع مجازات کاهش می دهد. اثبات جدید بر اساس قضیه دو گانگی در برنامه ریزی می باشد که این مدارکدر نوشته ها بر اساس نتایج حاصل از آنالیز های ریاضی به دست می آید . این مقاله اثری را که در سالهای اخیر توسط بیربیل و همکاران انجام گرفته بود را تکمیل می کند . در اینجا اثبا برنامه ریزی خطی در شرایط ضروری مرتبه اول با استفاده از تخفیف شرایط محدودیت انجام گرفته است .
واژه های کلیدی :
شرایط محدودیت ، شرایط بهینگی
مقدمه
در یادداشت اخیر[1] بیربیل و فرنک به ارائه یک برهان مقدماتی از شرایط مرتبه اول مسائل برنامه ریزی غیر خطی با محدودیت های برابری و نابرابری مبتنی بر قضیه دوگانگی برای برنامه ریزی خطی پرداخته اند .
در ابتدا به نظر می رسد مانعی همچون اثبات شرایط مرتبه دوم وجود دارد با این حال ما در اینجا نشان می دهیم که اثبات مرتبه دوم شرایط به همین دلیل در قضیه دوگانگی برای برنامه ریزی خطی قرار گرفته است.
نسخه های گوناگونی از این نتایج وجود دارد : در اینجا ما شرایط مرتبه دوم تحت شرایط محدودیت ماندگاسرین-فرومویز(MFCQ) بررسی می کنیم . د واقع ما تحت شرایط محدودیت ضعیف یا محدودیت ملایم (MCQ) کار می کنیم : که آن به ما این اجازه را می دهد که به کاهش محدودیت های نابرابرتنها با روش ساده و بی تکلف و بازنویسی هر گونه محدودیت برابری به عنوان دو محدودیت نابرابر بپردازیم . این نکته فنی بسیار جالب است به طوریکه در ابتدا شیوه ای ساده به نظر می رسید که در شرایط ضروری بی فایده و غیر کاربردی است . در مقایسه با آن روش اثبات ساده شده دارای ویژگیهای زیر است : در یادداشت موجود محدودیت نابرابر نسبت به محدودیت برابر کم ترشده است . همان طور که این ساده سازی هاجالب است اثبات اول شرایط سفارش شده در آن گنجانده شده است . محدودیت بربر ماندگاسرین- فرومویز در بخش5 معرفی شده و شرایط مرتبه دوم تحت MFCQ نمونه ای است که در بخش[3] ارائه شده .
در نوشته های گسترده وجود شرایط مرتبه دوم انواع مختلف شرایط مرتبه دوم و محدودیت نابرابر ارائه شده است . در اینجا معامله ای میان قدرت مرتبه دوم شرایط و شرایط محدودیت وجود دارد . برهان های ناشی از نتیج آنالیز های ریاضی بر اساس قضیه تابع ضمنی یا خاصیت تنظم متریک می باشد . محاسبات اخیر در مرتبه دوم شرایط بهینگی در منابع [4-6] ارائه شده است . خط مشی برهان های ارائه شده در مقاله حاضر به شرح زیر است. نقطه حداقل مطلق است . همان طور که ممکن است ما بئون محدودیت در کلییت چنین استدلال کنیم : "با وجود محدودیت حتی یک توپ به اندازه کافی کوچک است " بنابراین با جایگزین کردن محدودیت برابری با دو محدودیت نا برابری ما مساله را به عنوان مساله NLP(P) تنها با نابرابریها باز نویسی می کنیم . MCQ هنوز پس از این فرمول بندی نگهداری می شود. بنابراین تقلیل برهان تنها درمورد نابرابری ها ایجاد شده است . همچنین دنباله نامتناهی از مسائل NLP کمکی تنها با نابرابریها ساخته شده است . انتخاب یک نقطه از حداقل مطلق برای هر یک از این مسائل ایجاد شده ایست . این دنباله از مسائل و نقاط دارای خصوصیات ذیل می باشد . MFCQ در نقاط حداقل نگه داشته می شود و نقاط حداقل به سوی گرایش دارند.
مسائل کمکی به شکل زیر تعرف شده اند : همه محدودیت های (نابرابر)(P) کم شده و تابع مجازات افزوده شده است . همان طور که ذکر شده مسائل NLP تنها دارای نابرابریهایی هستند علاوه بر این MFCQ قابل تغییر به صورت صریح به استدلال می پردازد. مرتبه دوم شرایط ضروری برای این مسائل دارای شکل بسیار قدیمی است و اینها مسائلی است که در مرحله بعد فرمول بندی در شرایط برنامه ریزی وجود دارد . بنابراین از قضیه دوگانگی برای LP اعمال شده است . این امر شرایط ضروری در مرتبه دوم در فرمدوگانه را ارائه می دهد . به کاربران این شرایط ضروری محدود به شرایط لازم مرتبه دوم برای نقطه حداقل مطلق در مساله منتهی می شود.
در نهایت ما قضیه دوگانه را برای LP بازگومی نماییم : برای یک جفت مساله دوگانه LP که هردو دارای ارزشی بهینه یکسان می باشد ، هردوی آنها را غیر عملی نمی سازذ و همچنین اگر این ارزش محدود باشد هر دوی این راه حل ها مطلوب خواهند بود. در شکل استاندارد یک جفت از مسائل دوگانه LP به صورت زیر است:
→C,x > >
و
در اینجاA یک ماتریس است در اینجا C یک بردار ستونی n بعدی و b یک بردار ستونی m بعدی و x یک متغییر بردار ستونی n بعدی می باشد <0,0> به استاندارد درونی در ℝ اختصاص دارد که k برابر با m یا n می باشدکه به این صورت مفروض است :
2- نتایج بیانیه
1-2 مسأله NLP با محدودیت های نابرابر
ما مسأله برنامه ربزی غیر خطی (NLP) را با محدودیت نا برابر مورد بررسی قرار دادیم
(p)
در اینجا یک تابع -2C می باشد . این امر منحصر به کلیت عملکرد شرایط بهینگی همچون نتایج اصلی که به اندازه کافی برای مسائل NLP قابل اجراست نمی باشد . به این معنا که جایگزینی هر محدودیت برابر توسط دو محدودیت نابرابر بصورت می باشد .
2-2 شرایط محدودیت علایم
اجازه دهید یک نقطۀ موجه برای (p) باشد . ما می نوسیم
سپس یک زیر مجموعه یک مجموعۀ مجاز - نامیده می شود اگر یا دنبالۀ نا متناهی در برای باشد . با این شرایط محدودیت ملایم (MCQ) را برای (P) و نقطه موجه را اینگونه معرفی می کنیم : برای هر یک از مجموعه های موجه یک بردار برای وجود دارد .نماد به درصد تغییر (شیب ) اختصاص دارد .
مثال 1. مسأله برنامه ریزی غیرخطی , h را بررسی نمایید . در اینجا یک تابع -2C است . اجازه دهید یک نقطه موجه برای باشد . این مساله را دوباره به صورت باز نویسی کنید در اینجا و می باشد . سپس شرایط محدودیت ملایم برای مساله نگه داشته شده و در نهایت در نقطه بازنویسی می شو د . در حقیقت برای دارای
و برای دارای می باشد . مجموعه موجه نمی باشد به طوریکه و است و همچنین توابع هر دو یک ارزش مثبت در یک نقطه می باشد و به طور ویژه ، موجه - نمی باشد .
مثال 2. مساله برنامه ریزی غیر خطی p را بررسی کنید در اینجا توابع -2C می باشد . اجازه دهید یک نقطه موجه باشد فرض کنید در اینجا یک بردار برای برای همۀ وجود داشته باشد سپس شرایط محدودیت ملایم به طور آشکارا مورد رضایت قرار می گیرد . توجه کنید MFCQ بر اشاره دارد که یک مجاز می باشد .
3-2 قضیه اصلی
اکنون ما می توانیم نتیجه اصلی را به صورت یک قاعده فرمول بندی کنیم
قضیه (1) . مساله NLP با محدودیت های نابرابر بررسی کنید
(p)
در اینجا توابع 2C می باشد . اجازه دهید یک نقطۀ حداقل موضع (P) باشد . فرض کنید MCQ برای حفظ شود . سپس در اینجا یک مجموعه مجاز برای هر بردار می باشد به این صورت که
(i)
در اینجا برای برابرها
(ii)
و نابرابرها
(iii)
حفظ حقیقت
4-2 شرایط محدودیت ماندگاسرین – فرومویز
اکنون ما مساله NLP را با شرایط برابر یا نا برابر مورد بررسی قرار می دهیم
(p)
در اینجا m,j=1,…,p یک تابع -2C است . اجازه دهید یک نقطۀ موجه (P) باشد . ما می نوسیم . شرایط محدودیت ماندگاسرین فرومویز گفته می شود که حفظ می شود اگر MCQ برای نقطه حفظ شود و مساله NLP با نا برابرها که توسط حاصل می شود با نوشتن هر محدودیت برابر به عنوان دو محدودیت نا برابر به صورت :
(Q)
خواهد بود .
ما فرمول بندی مشهور MFCQ را بازگو می کنیم علاوه بر این که ما MFCQ را به MCQ ربط می دهیم . پیشنهاد (1) . یک مسالۀ از فرم ، نقطۀ موجه و شرایط زیر را بررسی قرار دهید :
1- گیره های MFCQ در
2- شیب های به طور خطی و مستقل بوده و هیچ ارتباط خطی جزئی میان مجموعه بردارهای زیر وجود ندارد .
برای هر یک از ضرایب بردارهای غیر خنثی نمی باشد
3- MCQ برای نقطه و مساله حفظ می شود
سپس شرایط (1) و(2) با یکدیگر برابرند و این دو شرط در شرط (3) نشان داده می شود
این قضیه کوتاه بوده و ما آن را بدون واسطه به دست می آوریم . مجموعه ای از بردارها مخروطی نامیده می شوند و اگر ارتباط خطی بدیهی با ضرایب خنثی نداشته باشند مستقل هستند .
قضیه : ما می خواهیم به ارائه یک قضیه برای مساله های فرم ارائه دهیم که تنها برای مسائلی با محدودیت های نا برابر به کار می رود . برای اثبات برابری (1) و(2) کافی است که عنصر مجموعه محدود را در فضای بردار که به صورت مخروطی است کنترل نماییم اگر یک بردار وجود داشت در این صورت آن دارای یک محصول درونی خنثی با هر بردار در مجموعه می باشد . استقلال مخروطی مجموعه بردارهای در می تواند دوباره به عنوان یک خصوصیت از مساله Lp با متغییر فرمول بندی شود .
داشتن ارزش صفر . این مساوی با ویژگی مساله دوگانه Lp با متغییر Z می باشد .
Max 0
که دارای ارزش صفر است . که در این بخش عملی است . این خصوصیات به معنی مطابقت با وجود بردار برای هر کدام بطوری که ضرورت دارد می باشد اکنون ما این استنباط را مورد بررسی قرار می دهیم (3) (2) . شرایط (2) را در نظر بگیرد سپس برای هر انتخاب علائم ، بردارهای به طور مخروطی مستقل هستند . علاوه بر این بردار d به صورت و می باشد . این امر نشان می دهد که برای هر و هر بردار x اعداد نمی تواند به طور همزمان مثبت باشد و همین امر باعث می شود MCQ صحت نقطۀ و مساله را حفظ نماید .
اکنون ما شرایط بهینه مشهور را با استفاده از مضارب غیر ثابت برای مسائل NLP تحت MFQ به صورت قاعده مطرح می کنیم .
قضیه (2) . شرایط بهینگی برایNLP تحت MFCQ . مسئله NLP را با محدودیت های برابر و نا برابر مورد بررسی قرار دهید . توابع پیوسته دو برابر m, j=1,…,p . اجازه دهید یک نقطۀ محلی حداقل باشد که MFCQ را تکمیل می کند . سپس ، برای هر به صورت زیر خواهد بود :
(i)
در اینجا مضارب برای هر یک از برابریها وجود دارد
(ii)
و برای نا مساوی ها
(iii)
قضیه (2) یک نتیجه منطقی از قضیه (1) و پیشنهاد (1) است . در واقع قضیه (1) را با مسائل NLP و محدودیت برابر یا نا برابر پس از جایگزینی با محدودیت برابر توسط دو محدودیت نا برابر اجرا کرد: پیشنهاد 1 نشان می دهد مفروضات پیشنهاد 1 قانع کننده بوده و نتیجه پیشنهاد 1 به آسانی به نظر می رسد که نتایج حاصل از پیشنهاد 2ارائه شده است . به این معنی که مجموعه مضارب Mj با برابر با صفر است
3- اثبات قضیه 1 در موارد ویژه دارای MFCQ
در این بخش ما به اثبات قضیه 1 تحت MFCQ می پردازیم
1-3 واریانس های ممکن در نقطۀ محتمل مساله یک منحنی کوچک در مجموعه محتمل با نقطۀ پایان می باشد که دقیق تر است . این نقطه از خانوادۀ نقاط محتمل از می باشد که در آن پارامتر همۀ اعداد غیر خنثی کوچک را کنار می گذارد . در اینجا به طور مداوم وابسته به می باشد و در اینجا است . اگر یک نقطۀ محلی حداقل باشد بنابراین خصوصیات زیر صحیح است :
(R)
ما این خصوصیات با تغییرات محتمل به دو صورت زیر نشان خواهیم داد : واریانس های خطی
برای واریانس های خطی ، این امر به شرایط مرتبۀ اول (p) و برای واریانس های درجه دوم برای شرایط مرتبه دوم برای (p) منتهی می شود .
قضیه . تنظیم قضیه (1) را در مورد بررسی قرار داده و فرض کنید MFCQ برای حفظ می شود . بطوریکه یک مجموعه مجاز - باشد کافی است آن را برای هر بردار نشان دهیم
(i)
در اینجا مضارب برای تساوی وجود دارد
(ii)
و عدم تساوی
(iii)
حفظ صحت
1- ابتدا شرایط را مرتب کنید
(a) امکان . ما داریم
سپس شرایط می باشد
برای بردارهای محتمل کافی است . و برای همه به اندازه کافی کوچک است
(b) خاصیت (R) برای . برای یک واریانس محتمل ما توسط خاصیت (R) داریم :
برای به اندازه کافی کوچک است بنابراین
(c) اولین ترتیب شرایط در شکل اولی یا متممی . ترکیب خاصیت (R) برای واریانس محتمل در نتیجه مراحل (a) و(b) مفهوم زیر را ارائه می دهد :
(d) اولین ترتیب شرایط در شکل دوتایی یا مضربی .مفهوم ایجاد شده در مرحلۀ (c) می تواند بار دیگر به عنوان خصوصیت مساله Lp با متغییرd تنظیم شود
