Group Relaxation
ساختار Group Relaxation
خلاصه (چکیده)
این مقاله تحقیقی است در مورد نتایج جدید در گروپ ریلکسیشن در برنامه ریزی خطی که از درس جبر از طریق و براساس تئوری برنامه ریزی خطی (صحیح) آمده است .
ما تمام گروههای ریلکسیشن را در تمام برنامه ریزی های خطی در برنامه های بی کران از ضریب ثابت ماتریس و بردار هزینه یاد می گیریم.
برنامه ها در خانواده با دسته بندی شاخص های غیر منفی محدودیت ها که می توانند ریلکس شوند در ماکزیمم گروپ ریلکسیشن که حل می کند هر مسأله ای را دسته بندی می شوند.
بخش مشخص این تئوری، تئوری زنجیره است که ثابت می کند این مجموعه ها در زنجیره های اشباع شده آمده اند.
ما برنامه های خطی غیر متغیر طبیعی را اختیار می کنیم که به آنarithmetic , degree
گفته میشود. ما همچنین مشخص می کنیم تمام خانواده های برنامه ریزی خطی که می تواند با Gomory relaxation ها حل شود.
این مقاله متکی به خود است و فرض می کند هیچ گونه آشنایی با تکنیک های جبری وجود ندارد.
مقدمه:
گروپ ریلکسیشن برنامه ریزی خطی توسط Ralph Gomory در 1960 معرفی شد. و برنامه ریزی خطی به فرم عمومی را به فرم زیر تعریف کرد:
(1)
گروپ ریلکسیشن آن توسط انداختن محدودیت های غیر منفی برروی متغیرهای پایه در حل بهینه خطی ریلکسیشن اختیار شد.
در این مقاله، ما نتایج اخیر برروی گروپ ریلکسیشن که برگرفته از آموزشهای جبری برنامه ریزی خطی که استفاده می کند Grobner bases of toric ideas را بررسی می کنیم.
فرض شد هیچ دانشی از این متدها وجود ندارد و شرح آن خود کفاست و قابل دسترسی برای شخصی که آشنا با متدهای سنتی برنامه ریزی خطی است.
برای خواننده ای که ممکن است در مورد مبدأ جبری، انگیزش ها و قسمتهای دیگر نتایج شرح داده شده علاقه مند باشد ما شرح مختصری در بخش آخر آورده ایم.
این توضیحات به صورت پاورقی های شماره دار و هم به صورت پاراگراف سازماندهی شده در بخش هشت آورده شده است.
در حالیکه آنها یک چشم انداز کاملی را از تئوری برای آنهایی که آشنایی با commutative جبر دارند اما دانستن آن لزومأ جهت پیوستگی مقاله لازم نیست.
به منظور اختصار از جزئیات تئوری کلاسیک گروپ ریلکسیشن صرفنظر می کنیم. شرح مختصری می تواند در Schrijver (1986 , 24.2) و خلاصه مجموعه یادداشتهای سخنرانی برروی این موضوع در Johnson یافت شود.
ما یک خلاصه از ملزومات براساس تحقیقات و بررسی های اخیرAardal , Weismantel , wolsey (2002) می دهیم.
خواننده را به هریک از منابع بالا برای جزئیات بیشتر در ارتباط با تئوری کلاسیک گروپ ریلکسیشن ارجاع می دهیم.
فرض می کنیم تمام داده ها در عبارت (1) صحیح بوده و AB پایه بهینه عبارت (1) هست.
گوموری در گروپ ریلکسیشن (1) عبارتست از:
(2)
اینجا N,B شاخص مجموعه برای پایه و غیر پایه ستونهای A برابر حل بهینه خطی ریلکسیشن (1) است.
بردار XNمشخص می کند متغیرهای غیر پایه و بردار هزینه كه جزء بندی شده بر طبق N , B است. علامت (mod1) نشان می دهد که بردار صحیح است. مسأله (2)تحت عنوان گروپ ریلکسیشن (1) نامیده می شود. از آنجایی که می تواند به فرم کانونی زیر نوشته شود:
(3)
که در آن G یک آبلین گروه هست و مسأله (3) می تواند به عنوان کوتاه ترین مسیر در یک گراف روی گره های |G| که بلافاصله تهیه می کند الگوریتم هایی را برای حل آن دیده شود. زمانی که حل بهینه از عبارت (2) پیدا شده می تواند بلند شود به بردار که در آن .Ax*=b
اگر سپس حل بهینه عبارت (1) است. در غیر این صورت کران پایین برای مقدار بهینه عبارت (1) است. چندین استراتژی ممکن در زمانی که گروپ ریلکسیشن نمی تواند برنامه خطی (صحیح) را حل کند وجود دارد. Gorry , No rthup , and Shapiro (1973) , Shapiro(1977) Wolsey (1973) , Nemhouser and Wolsey (1988) در مورد کارهای انجام شده در این جهت را ببینید.
یک ایده مشخص برطبق Wolsey (1971) که به این فصل خیلی مربوط است در نظر گرفتن توسعه یافته گروپ ریلکسیشن عبارت (1) است. اینها تمام گروپ ریلکسیشن های ممکن عبارت (1) هستند که با درنظر گرفتن محدودیت های غیر منفی روی همه متغیرهای پایه در ریلکسیشن خطی(1) است.
|
حالت خطی
