بخشی از مقاله
چکیده
در این مقاله، هدف معرفی مسئله برنامه ر یزی خطی دوترازه ی کسری بازه ای و ارائه ی روشی برای حل آن می باشد. برای شروع، ابتدا مروری برمسئله برنامه}ر یزی خطی دوترازهKی کسری خواهیم داشت، سپس مسئله برنامه}ر یزی خطی دوترازهKی کسری بازه_ای را معرفی خواهیم کرد . برای حل مسئله، چون ضرایب توابع هدف به صورت کسرهایی بازه_ای هستند، حل مسئله به راحتی امکانپذیر نیست. از طرفی چون ضرایب صورت و مخرج در توابع هدف به صورت بازه_ای است. پس، هدف تعیین بهترین و بدترین مقدار بهینهKی تابع هدف تراز بالایی میباشد. دراین مقاله، ایده_اصلی استفاده از مدل صفحه برش و در نظر گرفتن تغییر متغیر چارنز و کوپر برای حل مسئله میباشد. و نهایتاً، مدل پیشنهادیمان را روی یک مثال تشریح خواهیم کرد. واژه^های کلیدی:برنامه}ر یزی خطی دوترازهKی کسری، ضرایب بازه_ای ، مدل صفحه برش ، برنامه ر یزی خطی دوترازهKی کسری بازه_ای
١ مقدمه
حالت خاصی از یک مسئله برنامه ر یزی خطی دوترازه زمانی است که، توابع هدف آن - تابع هدف تراز بالایی و تابع هدف تراز پائینی - به صورت کسری باشند. در این صورت یک مسئله برنامه ر یزی خطی دوترازهKی کسری - - BLF P خواهیم داشت ، که اولین بار توسط کالویت و گیل ١ در سال ١٩٩٩مطرح شد]٢.[ یک مسئله - - BLF P به صورت زیر قابل تعریف است : برنامه}ر یزی خطی دوترازهKی کسری، روش وزن¾دهی است که در سال ٢٠٠٧ توسط میشرا ٢ارائه شده است ]۵.[ در این روش، با تعیین وزن^هایی مناسب، می_توان مسئله برنامه}ر یزی خطی دوترازه را به یک مسئله بهینه سازی تک ترازه تبدیل کرد. در سال ٢٠١٠ ، دوران تکسریروش٣ سری تیلور پیشنهاد دادند . در این روش، جواب^های بهینهKی هر تابع هدف کسری بهدست می آید . به گونه_ای که برای هر تابع هدف کسری یک چند جمله_ای تیلور در نظر گرفته می_شود، سپس با وزن^های مناسب، مسئله دوترازهKی کسری به مسئله دوترازهKی خطی تبدیل می_شود. در سال ۴٢٠٠کالویت و گیل ۴، روی حل مسئله برنامه}ر یزی دوترازهKی کسری کار کردند و نشان دادند که جواب بهین مسئله BLF Pدر نقاط راسی مرزی از ناحیه شدنی اتفاق میhافتد. سپس ، با در نظر گرفتن الگوریتم بهترین - k ام ، به حل مسئله BLF P پرداختند .
و مسئله را همچنین از نظری هندسی مورد بررسی قرار دادند ]٣.[ درسال ٢٠١٢، پایان و کیخا ،۵باتوسعهKی تغییر متغیر چارنز و کوپر توانستند مسئله برنامه}ریزی خطی دوترازهKی کسری را به یک مسئله برنامه}ریزی دوترازهKی خطی تبدیل کنند و با بیان یک قضیه، توانستند صحت مدل پیشنهادی خود را ثابت کنند . در اینجا هدف ما ، معرفی مسئله برنامه ریزی دوترازه ی کسری بازه ای و حل آن به کمک مدل صفحه برش می_باشد . در واقع ، ایده اصلی ما در این مقاله ، استفاده از شرایط KKT و همچنین در نظر گرفتن برش - توی ۶ ، برای حل مسئله BLF P ICمی_باشد . برای حل مسئله برنامه}ریزی خطی دوترازهKی کسری بازهKای، چون ضرایب صورت و مخرج توابع هدف به صورت بازه_ای است ، ابتدا مسئله را به یک جفت مسئله BLF P بانام های مسئله بهترین و مسئله بدترین تبدیل می_کنیم ، سپس با کمک تغییر متغیر چارنز و کوپر دو مسئله برنامه}ریزی خطی دوترازهKی کسری را به یک جفت مسئله BLPتبدیل می_کنیم . نهایتاً ، بهترین و بدترین جواب های بهینهKی مقدار تابع هدف تراز بالایی را تحت شرایط KKTوبااستفاده از برش توی بهدست میÀآوریم . و مدل پیشنهادی خود را روی یک مثال تشریح می_کنیم تعریف ١.١.نقطهKی راسی x ; y - ، - جواب بهینهKی مسئله برنامه}ریزی خطی دوترازهKی کسری است هرگاه :
٢- برای هرنقطه راسی شدنی - x; y - 2 S داشته باشیم : ٢ ;١ fi - x ; y - fi - x; y - ; 8i =قضیه ١.٢. نقطهKی راسی x ; y - جواب - بهینهی مسئله برنامه} ر یزی خطی دوترازهKی کسری است ، ا گر و تنها ا گر t ای وجود داشته باشد که - ٢ ; y١yجواب - بهین مسئله برنامه}ر یزی دوترازهKی خطی باشد . اثباتاثبات. قضیهKی فوق با توجه به تعریف بهینگی و تغییر متغیر چارنز و کوپر بهsراحتی امکان_پذیر است .٢ روش پیشنهادی برای حل مسئله برنامه}ریزی خطی دوترازهKی بازه_ای در این قسمت، به معرفی مسئله برنامه}ریزی خطی دوترازهKی کسری با ضرایب بازه_ای در توابع هدف میyپردازیم . سپس روشی برای حل این مدل مسائل پیشنهاد ارائه میNدهیم. مسئله زیر را در نظر بگیرید :
در سال ٢٠١٢ برزا،رامبلی~وسراجبه حل٧ مسئله برنامه}ر یزی خطی دوترازهKی کسری با ضرایب بازه_ای در توابع هدف پرداختند. آنها به کمک الگور یتم بهترین - kام توانستند جواب بهینهKی مقدار تابع هدف تراز بالایی را تعیین کنند]١.[ چون در مسئله فوق ضرایب توابع هدف به صورت بازه_ای است. پس هدف تعیین بهترین و بدترین جواب^های بهینهKی مقدار تابع هدف تراز بالایی میباشد. بنابراین مسئلهKی فوق را به دو زیر مسئله برنامه}ر یزی خطی دوترازه Kی کسری، با در نظر گرفتن مطلوبترین و نامطلوبترین مقدار توابع هدف، تبدیل میNکنیم. سپس بااستفاده از تغیر متغییر توسعه یافته، به دو مسئله برنامه}ر یزی دوترازهKی خطی می_رسیم . که با حل این دو مسئله برنامه}ر یزی دوترازهKی خطی، بهترین و بدترین مقادیر بهینهKی مسئلهKی - ٢ - بهدست می_آید. روشی که در این مقاله پیشنهاد می _شود، الگور یتم صفحه برشی است که در ]۵[ ارائه شده است . این الگور یتم بر اساس برش - توی ٨ طراحی شده است . با توجه به توضیحات بیان شده و همچنین با در نظر گرفتن شرایط ایجاد برش در ]۵[ الگور یتم زیر را ارائه می_دهیم .
الگوریتم :
١- ١ = قرارi دهید. مسئله بهترین برنامه}ر یزی دوترازهK ی خطی را بدون در نظر گرفتن تابع هدف تراز پائینی برای بهدست آوردن جواب بهینهKی - xi; yi - حل کنید . برو به گام ٢. شرط٢- ]۵[ را برای نقطهKی راسی بهدست آمده اعمال می_کنیم . ا گر شرط برقرار باشد، نقطهKی راسی - xi; yi - بهترین جواب بهین خواهد بود . در غیر این صورت برش معرفی شده در ]۵[ را اعمال می_کنیم . به_نحوی که هیچ نقطهKی راسی دیگری ایجاد نشود. برو به گام ٣ . ٣- از مجموعه نقاط راسی مجاور به - xi; yi - ، نقطه_ای راسی که بهترین جواب بهین برای تابع هدف تراز بالایی داشته باشد، انتخاب کنید . برو به گام ١. روند فوق ، تا رسیدن به بهترین جواب بهینه برای تابع هدف تراز بالایی مسئلهKی - ٢ - ادامه می_یابد . ملاحظه ٢.١بدترین. جواب بهینهKی مسئلهKی - ٢، - با حل مسئله بدترین برنامه}ر یزی دوترازهKی خطی و باتوجه به روند فوق بهدست میMآید .
