بخشی از مقاله
چکیده :
کاربرد ریاضی در مدلسازیها در جهان امروز قابل چشمپوشی نیست. به علت نادقیق بودن دادهها در مسائل دنیای واقعی، مدلهای ریاضی بازهای خصوصاًبرنامهریزی غیرخطی بازهای INLP 4 1کاربردهای زیادی پیدا میکند . معروفترین مسائل INLP، مسائل برنامهریزی مرتبه دوم بازهای هستند که کاربرد وسیعی در علوم مختلف از جمله مدیریت موجودی، علم اقتصاد، انتخاب سهام، طراحی مهندسی و مطالعه مولکولی دارند. در این مقاله این نوع برنامهریزی در حالتی که متغیرها نامقید هستند، بررسی و روشی جهت تعیین کرانهای تابع هدف معرفی می گردد.
واژههای کلیدی: ماتریس بازه ای، برنامهریزی مرتبهدوم، متغیرهای نامقید، کرانهای تابع هدف
-1 مقدمه
مسائل برنامهریزی مرتبهدوم بازهای IQP 5 شامل تابع هدف مرتبهدوم و قیود خطی که دادهها به صورت نادقیق یا بازهای مشخص شدهاندمیباشد. به علت عدم قطعیت دادههای ورودی، مقدار تابع هدف هم به طور نادقیق با تعیین بهترین و بدترین مقدار بهینه تابع هدف، به صورت یک بازه مشخص میگردد.در صورت ثابت بودن ضرایب مسئله، برنامه ریزی مرتبه دوم معمولی است و با روش مضارب لاگرانژ قابل حل میباشد .[1] برای حل مسئله IQP روشهای مختلفی از جمله به کار بردن دوگانِ درن برای حل مسئله[3] و استفاده از تکنیک برنامهریزی ریاضی دوترازه جهت تعیین کرانهای هدف[8] پیشنهاد شدهاست. مسئله برنامهریزی خطی بازهای با متغیرهای نامقید قبلاً مورد بررسی قرار گرفته و روشهایی برای تعیین کرانهای بالا و پایین آن ارائه شده است .[5]
مسئله IQP با قیود مساوی در تعیین مقدار بدترین یک مسئله Np-hard است[6] در صورتی که IQP با متغیرهای نامقید برای تعیین هر دو مقدار بدترین و بهترین هدف به مسائلی Np-hard تبدیل میشود 4]،.[5 در این مقاله روشی برای تعیین مقادیر بهترین و بدترین بهینهی تابع هدف IQP با متغیرهای نامقید ارائه میگردد.این مقاله شامل 6 بخش است. در بخش 2 مفاهیم بازهای آمده است. بخش 3 مسئله برنامهریزی مرتبهدوم بازهای نامقید و بخش 4 روشحل این مسائل را معرفی میکند. بخش 5 نتایج عددی و بالاخره بخش 6 نتیجهگیری مقاله را در بردارد.
-2 مفاهیم بازهای
تعریف-1-2 عدد بازهای a بهصورت a , a تعریف میشود که در آن . a a اگر a a باشد، a را تباهیده گویند که در این صورت عدد بازهای a تبدیل به یک عدد حقیقی میشود.تعریفm, n ∈ ℝ -2-2 آنگاه ماتریس بازهای A به صورت زیر تعریف میگردد:اگر مجموعه تمام ماتریسهای بازهای m×n را با Iℝ × و مجموعه تمام بردارهای بازهای m تایی را با Iℝ نمایش دهیم آنگاه ∈ Iℝ ×
و ∈ Iℝ و ∈ Iℝ و ∈ Iℝ × میباشد.بازهای بودن ضرایب سبب میشود یک خانواده QP معمولی به نام مدلِ مشخصه به صورت زیر حاصل گردد.
-4 روش حل IQP نامقید
نادقیقبودن دادهها در مسئله برنامهریزی مرتبه دوم بازهای باعث میشود که مقدار تابع هدف به صورت بازه ] مقدار و f بدترین مقدار بهینه تابع هدف است. همچنین f در حالتی که متغیرها نامقیدند بصورت بازهای و به فرم به سبب نامقید بودن متغیرها محاسبهی f و f یک مسئلهی Np-hard است.[4] به همین دلیل با حل چند زیر مقادیر بهینهی این زیر مدل ها تعیین می گردند.
1-4 محاسبه بدترین مقدار بهینه تابع هدف
با توجه به اینکه 0 ممکن و مناسب برای تعیین f با حلn Ds x است این زیر مدل یک QP مقید معمولی است و به سادگی قابلحل می باشد. ناحیه شدنی - 2 - هم کوچکترین ناحیه یافتن بدترین مقدار بهینه تابع هدف است .[3] زیرمدل - 2 - بهصورت زیر انجام می شود.
2-4 محاسبه کران بالایی بهترین مقدار بهینه تابع هدف
در مسائل IQP نامقید علاوه بر اینکه محاسبهی صورت بازهی ] U , f L[f تعیین میشود.بایستی زیر مدل هایی را حل برای محاسبهی U fمقدار بهینه زیرمدل زیر باشد. f یک مسئله Np-hard است، نمیتوان این مقدار را به صورت دقیق بهدست آورد .[5] بلکه به کرد که کمترین مقدار بهین تابع هدف را در بزرگترین ناحیه شدنی نتیجه دهند. فرض کنید.همانند محاسبهی بدترین مقدار بهینه هدف، 2n زیر مدل - 4 - بایستی حل شود تا با مینیمم گرفتن از مقدار بهینه هدف آنها بتوانیم کران بالای f را تعیین کنیم. اگر ناحیه شدنی، ناحیهای همبند باشد محاسبهی U f با حل زیر مدلهای کمتری امکانپذیر است .[5] دراین حالت، ابتدا مدل مشخصه - 1 - را برای Ac A ، C Cc ، Qc Q و b = حل میکنیم. اگر x* جواب این مسئله با مقدار بهینه هدف f U باشد، قرار میدهیم s sgn x* و مقدار بهینه هدف را برای فضای جواب محدود شده به ناحیه s، با حل زیر مدل پایین محاسبه میکنیم.
