بخشی از مقاله
چکیده
در این مقاله، شدنی بودن مساله ماکزیمم جریان معکوس - IMFG - مطالعه شده است. شدنی بودن میتواند در زمان خطی تست شده باشد، ولی در مورد - IMFG - این امکان وجود ندارد. مساله اصلاح کردن یک امکان کم جریان است، لذا با ارائه یک مثال نشان داده شده است که مساله این امکان را برای جریان اصلاح شده به وجود میآورد. در این تحقیق، بهینهسازی ترکیبی معکوس جدید معرفی و همینطور الگوریتم هایی برای بعضی از مسائل شدنی معکوس SDP ارائه شده است.
-1 مقدمه
در مسأله ماکزیمم جریان به دنبال جریان f می باشیم که در دو شرط تعادل و ظرفیت صدق کند و همچنین f ماکزیمم مقدار ممکن را دارا باشد. حال فرض کنیم یک جریان شدنی f داریم. در مساله ماکزیمم جریان معکوس باید کرانهای پایین و بالا را به نحوی تغییر دهیم که این جریان ماکزیمم شود. حال حالتی را در نظر میگیریم که مسأله ماکزیمم جریان مسئله نشدنی است.
در این حالت، باید جریان داده شده تغییر کند. در این مقاله، هدف این است که با کمترین تغییرات ممکن به این خواسته برسیم و برای آن، الگوریتمی ارایه می شود و درستی آن نیز اثبات خواهد شد که هدف تبدیل جریان داده شده در مساله ماکزیمم جریان معکوس نشدنی به حالت شدنی با کمترین تغییرات ممکن میباشد. یک مسئله بهینهسازی ترکیبی معکوس شامل اصلاح بعضی از پارامترهای یک شبکه میباشد از قبیل ظرفیتها و هزینهها برای اینکه یک راه حل شدنی داده شده از مسئله بهینهسازی مستقیم یک راهحل بهینه شود و فاصله بین بردار اولیه و بردار اصلاح شده پارامتر کمترین باشد.
در سالهای اخیر مقالات زیادی در زمینه بهینهسازی ترکیبی معکوس منتشر شدند - کیورا و همکاران . - 20081 الگوریتمهای زمانی چندجملهای قوی برای حل مسئله ماکزیمم جریان معکوس وقتی که نرم l1 مورد بررسی قرار گرفته، توسط Yang , Zhang و Ma ارائه شده بود - دیاکوون.، IMF . - 22006 به یک مسئله مینیمم برش در یک شبکه کمکی با ظرفیت کمان محدود و نامحدود کاهش مییابد.
الگوریتم برای IMF یک پیچیدگی زمانی / m - - ٍO - n.m.log - n دارد که در آن m تعداد کمانها و n تعداد گرهها میباشد. در حالت کلی - با GIMF مشخص شده - تحت نرم ٌl در - کوریا - 32000 مورد مطالعه قرار گرفته است، که کرانهای بالایی و پایینی برای جریان تغییر داده شدهاند. الگوریتمهای چندجملهای قوی و ضعیف برای حل GIMF پیشنهاد شدهاند. الگوریتمهای چندجملهای قوی برای GIMF همان پیچیدگی زمانی را مانند IMF دارند، اما مینیمم برش دریک شبکه با کرانهای کمتر جستجو شده است.
الگوریتمهای چندجملهای ضعیف برای GIMF یک پیچیدگی زمانی / m - .log - max{ n, R} - - ٍ}.m.log - n ٍ, m َ O - min{n دارند همچنین چهار مسئله ماکزیمم جریان معکوس توسط - لیو و ژانگ - - کیورا.، - 3 2007تحت فاصله نوع حاصلجمعی و نوع گرهای وزندار مورد مطالعه قرار گرفته است. الگوریتم های چندجملهای قوی برای حل این مسائل پیشنهاد شدهاند. در این مقاله یک مسئله بهینه سازی ترکیبی معکوس ارائه شده است. این مسئله بر مبنای اصلاح در حد امکان کم جریان به منظور تبدیل مسئله ماکزیمم معکوس به یک مسئله شدنی میباشد.[13]
-2 مسائل حملونقل و جریان شبکهای
تعدادی مسئله با ساختار خاص وجود دارند که از اجزای مهم موضوع برنامهریزی خطیاند. نماینده و نمونه بارز دسته وسیعی از این نوع مسائل خاص مسئله حملونقل و مسائل وابسته به آن است که در ادامه بحث به آن اشاره شده است. این مسائل مهماند زیرا اولاً حوزههای وسیعی از کاربردها را در بر میگیرند که بسیار با آنها رو به رو میشویم. در واقع، بسیاری از این مسائل پیش از توسعه کلی برنامهریزی خطی فرمولبندی شدهاند و همواره در بسیاری از کاربردها ظاهر میشوند. ثانیاً این مسائل از آن جهت مهم هستند که نظریه وابسته به آنها غنی است. این نظریه بصیرت ارزشمندی به ما میدهد و الهام بخش پیشرفتهای کلی جدیدی است.
این ببخشتقریباً به دوقسمت تقسیم میشود. در قسمت نخست مسئله حملونقل از دیدگاه روش سیمپلکس تجدید نظر شده بررسی میشود، که در مورد این مسئله شکل فوقالعاده سادهای به خود میگیرد. در قسمتهای دیگر این بخش، گرافها و جریانهای شبکهای معرفی میشوند. الگوریتم حملونقل تعمیم داده میشود و تعبیرهایی جدید ارائه میگردد. سپس یک الگوریتم خاص با کارایی بسیار زیاد، الگوریتم درختی، برای حل مسئله جریان ماکسیمال عرضه میشود. به دنبال آن در بخش پایانی، مسئله حمل و نقل مجدداً بررسی میشود.
- 2-1 مسئله حملونقل
تعداد m مبدأ وجود دارد، که باید از آنها مقادیر مختلفی از یک کالا را به n مقصد حمل کنیم تا تقاضای کالا در مقصدها برآورده شود. به طور مشخص، در مبدأ i یک مقدار ai از کالا موجود است و در مقصد j تقاضایی به اندازه b j برای کالا وجود دارد. فرض میکنیم که سیستم از موازنه برخوردار است، بدین معنا که کل عرضه برابر کل تقاضاست.
- 2-2 پیدا کردن یک جواب شدنی پایهای
عنوان روش سرراستی برای محاسبه یک جواب شدنی پایهای آغازی وابسته به یک مسئله حملونقل وجود دارد. مطالعه این روش در این مقطع ارزشمند است، زیرا معرف فرایندهایی محاسباتی است که اساس راه حل کلی مبتنی بر روش سیمپلکس را تشکیل میدهد. این روش هم چنین خاصیت اساسی ساختار مسئله حمل و نقل را، تا حدی نشان میدهد. روش قاعده گوشه شمال غرب را در 13]،5،3،2،[1 مشاهده نمایید.
- 2-3 روش سیمپلکس برای مسائل حملونقل
حال که ویژگیهای ساختاری مسئله حملونقل را معلوم کردهایم، مشخص کردن جزئیات روش سیمپلکس برای مسئله حملنقلو نسبتاً آسان است. هدف اصلی، بهرهگیری کامل از خاصیت مثلثی بودن پایهها به منظور دستیابی به کارآیی محاسباتی در روش و فشردگی در نمایش آن است. روشی که به کار میرود در واقع حاصل تعدیل نمونهای از روش سیمپلکس تجدید نظر شده است که وارون پایه هرگز محاسبه نمیشود، بلکه شکل مثلثی آن به طور مستقیم برای به دست آوردن تمامی متغیرهای مورد نیاز به کار میرود - دانت زینگ.6، . - 1951
- 2-4 الگوریتم حملونقل
حال میتوانیم مطالبی را که تا اینجا عرضه کردهایم کنار هم بگذاریم تا به شکل یک روش کامل سیمپلکس تجدید نظر شده برای مسئله حملونقل درآید. مراحل کار عبارتند از:
مرحله .1 یک جواب شدنی پایهای آغازی را با به کارگیری قاعده گوشه شمالغرب یا روش دیگری به دست آور.
مرحله .2 ضرایب سیمپلکس و ضرایب هزینه نسبی را محاسبه کن. اگر تمامی ضرایب هزینههای نسبی غیر منفی هستند، متوقف کن؛ جواب بهینه است. در غیر اینصورت، به مرحله 3 برو.
مرحله .3 یک متغیر غیر پایهای متناظر با ضریب هزینه منفی برای ورود به پایه انتخاب کن - معمولاً متغیری را انتخاب میکنند که متناظر با کوچکترین ضریب هزینه منفی باشد - . چرخه تغییر را محاسبه کن و را برابر کوچکترین متغیر پایهای که به آن علامت منفی داده شده است، قرار ده.
