بخشی از مقاله
بهینه سازی پیوسته الگوریتم سیمپلکس برای مسائل برنامه ریزی کسری تکه ای – خطی
تعمیم های روش شناخته شده سیمپلکس برای برنامه ریزی خطی در دسترس می باشد . که این روش برای حل مسائل مربوط به برنامه ریزی تکه ای خطی و برنامه ریزی کسری خطی به کار می رود. در این مقاله از روش سیمپلکس برای برنامه های خطی ، برنامه های تکه ای – خطی و برنامه های کسری خطی استفاده می کنیم . نتایج محاسباتی ارائه شده بیشتر بر اساس دیدگاه هایی است که عملکرد الگاریتم در مسائل آزمون تصادفی به دست می آید.
واژه های کلیدی : برنامه ریزی کسری ، روش سیمپلکس ، توابع خطی تکه ای
1- مقدمه
برنامه کسری خطی – تکه ای (plfp) می تواند تعریف شود به صورت
= برای به حداقل رساندن
Ax=b مشروط به اینکه
در اینجا (xj) fi یک تابع محدب خطی – تکه ای پیوسته و ( ) یک تابع معقر خطی تکه ای پیوسته است بطوریکه برای هر راه حل موجه ( ) X= می باشد .
A یک ماتریس m×n از مرتبه سطری کامل ، b یک بردار m بطوریکه bi≥ و =U یک بردار- X می باشد . مسائل شناخته شده برنامه ریزی خطی و مسائل برنامه ریزی خطی – تکه ای (PFP) و مسائل برنامه ریزی کسری خطی (LFP) همگی موارد ویژه ای از PLFP می باشند . فوریور تعمیم توسعه یافته مدل سیمپلکس را در برنامه ریزی خطی برای حل PLP و اسوارپ و ماتریس سیمپلکس مطرح شده را برای گسترش در حل LFP ارائه می دهند . در این مقاله ما به بحث و
بررسی روش سیمپلکس برای حل PLFP و تعمیم و استفاده از روش سیمپلکس برای LP ، PLP ، LFP می پردازیم زمانیکه ، x و....و است plfp به plp تقلیل یافته و در این مورد الگاریتم ما به شکل الگاریتم فوریور کاهش می یابد . اگر x ... وj=1 و و به شکل خطی باشد (مثلا ً تکه ای – خطی با دقیقا ً یک تکه خطی ) سپس plfp به lfp و الگاریتم ما به الگاریتم اسوارپ و ماتریس کاهش یافته و تعدیل شده به صورت متغییرهایی گسترش می یابند . زمانی که خطی برای و وx و.... وj=1 باشد برای x و ...و j=1 ، plfp به lp با متغییرهای گوشه دار کاهش یافته و الگاریتم ما به روش سیپلکس معیار با متغییرهای گوشه دار تقلیل می یابد . این الگاریتم ما چارچوب واحدی برای حل مسائل بهینگی عمده فراهم نموده که در این مقاله به خوبی مورد مطالعه قرار گرفته است . مشهور اس
ت که plp می تواند به صورت lp با مقدمه ارائه شود . متغییرهای جدید در اینجا یک عدد با نقطه انفصال خطی باشد اگر می باشد . با استفاده از این انتقال ، plfp می تواند به عنوان یک lfp با متغییرهای X+ تنظیم گردد در اینجا یک عدد از نقطه انفصال خطی باشد اگر می باشد .
اما هر lfp می تواند به عنوان یک lp با یک محدودیت اضافی و یک متغییر مازاد تنظیم گردد . در مور
د lfp با متغییرهای گوشه دار ، این تغییرات انتقالی در ثابت های گوشه دار در متغییر بالاتر و گوشه های پایین تر به وجود می آیند . عملکرد واضح این متغییر بالاتر و گوشه های پایین تر محدودیت های اضافی x2 را ایجاد می نماید . بنابراین اگر چه یک plfp می تواند به عنوان lp تنظیم شود اما این روش برای عملا ً مناسب نیست چون سایز ناشی از lp می تواند به طور قابل ملاحظه ای بزرگ باشد بخصوص زمانی که ما دارای گوشه هایی در بالا یا پایین در متغییرها می باشیم . مشابه الگاریتم فوریور برای plp ، الگاریتم ما از یک روش مستقیم استفاده می کند که عملکرد آن بر اساس AX=b می باشد . بنابراین مزیت عمده الگاریتم ما ساختار ویژه آن است . در صورتی که A بتواند برای بدست آوردن ضریب انتفاع مورد بهره برداری قرار گیرد . اگر چه الگاریتم ما می تواند به عنوان یک روش درصد شیب ویژه مورد ارزیابی قرار گیرد اما اعداد متناهی غیر قابل تشخیص در تابع هدف به طور موثری توسط طراحی متغییرهای غیر پایه منطبق با نقاط تنظیم می گردند .
در این مقاله به صورت زیر سازمان دهی شده است . در بخش 2 ما به معرفی نمادسازی های مختلف و تعاریف و نتایج پایه می پردازیم ما همچنین به بحث و بررسی تبدیل صورت از PLFP به LFP و LFP به LP خواهیم پرداخت . بخش 3 با الگاریتم ها برای PLFP سروکار دارد . توضیح و تشریح الگاریتم در بخش 4 ارائه می شود . بخش 5 الگاریتم سیمپلکس را برای PLFP با استفاده از نمونه های عددی نشان می دهد . نتایج تجارب محاسباتی مقدماتی در بخش 6 گزارش شده و در
نهایت نتایج ملاحظات در بخش 7 ارائه می شود .
2- نشانه گذاری ها ، تعاریف و نتایج پایه
واژه ها و اصطلاحات و همین طور نمادگذاری ها در این بخش معرفی شده و در سراسر این مقاله مورد استفاده قرار می گیرد . اجازه دهید یک نقطه انفصال و نقطه انفصال باشد. اجازه دهید یک آرایش صعودی از عناصر مجزا در هر دوی و خطی باشد . بنابراین و می تواند به این صورت ارائه شود:
و
برای برخی از اعداد حقیقی
چون محدب است و مقعر است ، ما داریم :
تسلسل این توابع به این شکل نشان داده شده است :
از آنجایی که محدب و مقعر است ، انتقال استاندارد برنامه های خطی – تکه ای در برنامه های خطی مورد استفاده قرار می کیرد که به این شکل نشان داده شده است :
Plfp می تواند به عنوان برنامه کسری خطی فرمول بندی شود :
حداقل شده
مشروط براینکه
در اینجا
با استفاده انتقال شناخته شده کارنس و کوپر
این برنامه کسری می تواند به برنامه خطی تقلیل یابد :
تقلیل یافته
مشروط به
توجه کنید که تغییر شکل plfp به lfp یا lp به طور قابل ملاحظه ای مسأله سایز را افزایش می دهد اجازه دهید
مسأله زیر را مورد بررسی قرار دهید
AX=b , مشروط به اینکه
اجازه دهید ارزش بهینگی تابع هدف باشد قبلا ً :
در اینجا S مجموعه راه حل های ممکن است
قضیه زیر در نوشته های برنامه ریزی کسری شناخته شده است که به مورد plfp اختصاص یافته است .
قضیه 1- اجازه دهید یک راه حل بهینه برای plfp و باشد . سپس
بعلاوه یک راه حل بهینه با راه حلی بهینه برای plfp می باشد
قضیه 1 برای ایجاد شرایط بهینگی در روش سیمپلکس ما مورد استفاده قرار می گیرد .
3- الگاریتم سیمپلکس برای plfp
برای بحث و بررسی الگاریتم سیمپلکس برای plfp ما ابتدا نیازمند معرفی مفهوم جواب ممکن بنیادی (Bfs) برای plfp می باشیم . تعاریف ما دقیقا ً از تعریف bfs که توسط فوریور برای plpارائه شده است ، تبعیت می کند . اجازه دهید B یک ماتریس عادی m×m که شامل ستون های m از A می باشد . سپس B یک ماتریس پایه نامیده می شود . اجازه دهید شاخص i امین ستون B در ماتریس A و مجموعه شاخص ستون های B باشد . اجازه دهید به بردار M اختصاص داشته باشد که تطابق مختصات i برای متغییر است اجازه دهید
N={1,2, … , X}\B باشد . متغییرهای متغییرهای پایه نامیده می شود (تطابق با ماتریس پایه B) و N متغییرهای غیر پایه نامیده شده است . متغییرغیر پایه تطابق ارزش ها به نقطه انفصال یا می برد مثلا ً N برای برای متغییر غیر پایه ، اجازه دهید به شاخص اختصاص یابد . اجازه دهید باشد . ما سه وجه یک ساختار پایه می نامیم . ساختار پایه داده شده منطبق با Bfs اختصاصا ً تعریف شده به صورت :
در اینجا A,j ،j امین بردار ستون از ماتریس محدود A می باشد . ما این راه حل را به عنوان مطابقت Bfs با ساختار پایه قرار دادیم اجازه دهید باشد . اگر برای هر i باشد . سپس آن یک Bfs غیر تبهگن است .
اثبات : اجازه دهید یک راه حل بهینه برای plfp باشد . برای هر j=1,… x یک شاخص همچون انتخاب نمایید . اجازه دهید
اجازه دهید و باشد . سپس هر راه حل بهینه برای LFP به شکل زیر است :
تقلیل یافته
Ax=b , مشروط بر اینکه
یک راه حل بهینه برای plfp است
در Bfs داده شده منطبق با ساختار پایه برای PLFP می باشد ، هر متغییر پایه یک نقطه انتقال از یا است . اجازه دهید به شاخص مثل ، m ... و2و1=i اختصاص یابد . بردار از محور افقی iام به صورت است که بردار با شیب – f منطبق با ساختار پایه می باشد . همچنین بردار – m از محور افقی i که به صورت است بردار محور افقی – g منطبق با می باشد . ارزش متغییر غیر پایه مجاز است که از نقطه انفصال اخیر در جهت گوشه سمت چپ یا جهت گوشه سمت راست تغییر یابد . بنابراین ما دو کمیت که به و اختصاص دارد مورد محاسبه قرار می دهیم که تعریف شده به صورت :
در اینجا Z یک مقدار از تابع هدف در راه حل ممکن پایه می باشد و و منطبق با بردارهای محور افقی f و محور افقی هستند . اگر باشد سپس به عنوان 0 تعریف می شود . به صورت مشابه زمانی که است سپس به شکل 0 تعریف می گردد . صراحتا ً برای همه متغییرهای پایه است . ما را به عنوان گوشه سمت چپ در ارزش کاهش یافته و را به عنوان گوشه سمت راست در ارزش کم شده برای متغییر در نظر می گیریم
قضیه 3 – (معیار بهینگی ) یک راه حل ممکن بنیادی غیر تبهگن در صورتی برای plfp بهینه است اگر و تنها اگر باشد
اثبات . اگر x یک راه حل بهینه غیر تبهگن برای plfp باشد . ما باید نشان دهیم که
باشد . اجازه دهید N شاخص مجموعه متغییرهای غیر پایه و برای باشد ، حالا
در اینجا
فرض کنید برای تعدادی از متغییرهای غیر پایه باشد . راه حل جدید را اینگونه مورد بررسی قرار دهید که
در اینجا یک جزء قرار دادی است .
به طور آشکارا یک راه حل عملی است . چون x غیر تبهگنی که می تواند بدین گونه انتخاب گردد
حالا
ما می دانیم که و به وسیله فرضیات می باشد و به این صورت نشان داده می شود :
این امر بهینگی x را نقض می کند . به طور واضح ما می توانیم این مورد را زمانی که است برای برخی متغییر غیر بنیادی اثبات نماییم .
از طرف دیگر فرض کنید یک Bfs غیر تبهگن می باشد که به صورت وxو...وj=1 و می باشد . ما باید را به عنوان یک راه حل بهینه برای plfp نشان دهیم. ثابت کردن آن به وسیله قضیه 1 تنها کافی است را نشان دهد در اینجا
آشکارا بنابراین است . اگر ممکن است اجازه دهید plp را بررسی نمایید :
مشروط بر اینکه
در اینجا
بنابراین
حالا یک Bfs برای plp است . چون یک راه حل بهینه برای plpنمی باشد و باید قادر باشیم راه حل بهتری را برای plp بیابیم . سپس بر اساس فوریور] 12[ یک متغییر غیر پایه وجود دارد که در هر دو گوشه سمت چپ ، ارزش را در plp کاهش می یابد
یا گوشه سمت راست ارزش را در plp کاهش می دهد
در اینجا اما
و
=
بنابراین هر یک یا برای و این امر هر دوی و را نقص می کند . بنابراین امکان پذیر نمی باشد و بنابراین می باشد و این امر برهان را تکمیل می کند
برای توصیف الگاریتم سیمپلکس ، ما نیازمند یافتن یک Bfs اصلاحی از Bfs داده شده می باشد .
اگر Bfs اخیر از قضیه 1 بهینه نباشد ، در اینجا حداقل یک متغییر غیر پایه به صورت می باشد به
طوریکه یا است ( توجه کنید ما فرض می کنیم در اینجا Bfs غیر تبهگن است متغییر از به صورت در حالیکه دیگر متغییرهای پایه را در متغییر در نقطه انفصال حفظ می کند ما اکنون باید ارزش را تعیین نماییم به صورتی که Bfs اصلاحی جدید فراهم شود . این امر می تواند با استفاده از قانون انتخاب متغییر از دست رفته که در بخش زیر مورد بحث قرار گرفته است انجام گیرد . قانون انتخاب متغییر خارج شده مشابه الگاریتم سیمپلکس خطی – تکه ای فوریور می باشد . علاوه بر این گوشه
سمت چپ و گوشه سمت راست ارزش های وابسته به ارزش تابع هدف که به ارائه راه حل می پردازد کاهش می دهد . این مغایرت چشمگیر از محاسبات منطبق برای plp می باشد مورد 1. یک متغییر ورودی است و می باشد
چون به وسیله افزایش ارزش ارزش تابع هدف را کاهش خواهد داد . تغییر در آشکارا ارزش متغییر پایه را تغییر می دهد . اجازه دهید راه حل جدیدی باشد که به دست آمده است . سپس آن
می تواند به صورت زیر تغییر یابد که
1)
2)
3)
در اینجا
ما مایل به یافتن ارزش می باشیم همان طور که یک مطابقت Bfs در بسیاری از ساختارهای پایه می باشد . انتخاب آنی با محدود کردن به دست آمده است به طوریکه
4)
5)
اجازه دهید
6)
7)
و با انتخاب و ، Bfs با ساختار پایه ویژه مطابقت پیدا خواهد کرد
اجازه دهید
اگر همه Bfs ها به صورت غیر تبهگن باشند متمایز شده و1 یا 0 = ،
1 یا 0 = خواهد بود . در این زمان ما تنها خودمان را به مورد غیر تبهگن Bfs صفر خواهیم کرد . اگر باشد سپس متغییر پایه که گفته می شود به ارزش نقطه انفصال خواهد رسید . اگر باشد مقدار پایه که گفته می شود به ارزش نقطه انفصال می رسد . اگر باشد ، متغییر غیر پایه به ارزش نقطه انفصال بعدی که است می رسد . ارزش تابع هدف به این شکل داده شده :
در اینجا
این امکان وجود دارد که را به عنوان Bfs جدید انتخاب شود . علاوه بر این همان طور که در بخش ]12[ انجام شد بهتر است امکان افزایش مقدار را دورتر از جستجو کنیم . در این مورد ما می خواهیم مطمئن شویم که مقدار به طور پیوسته منفی است .
