الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 48000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
شماره
۶۷
کد مقاله
IND67
مترجم
گروه مترجمین ایران ترجمه – irantarjomeh
نام فارسی
یک الگوریتم ایجاد ستون دو هدفه برای مسئله جریان با کمترین هزینه چند کالایی
نام انگلیسی
A Bi-objective Column Generation Algorithm for the Multi-Commodity Minimum Cost Flow Problem
تعداد صفحه به فارسی
۴۲
تعداد صفحه به انگلیسی
۲۷
کلمات کلیدی به فارسی
جریان های شبکه, مسئله جریان با حداقل هزینه چند کالایی دو هدفه, تجزیه دانتزیگ – ولف, ایجاد ستون, روش سیمپلکس دو هدفه
Department of Engineering Science, University of Auckla; Department of Management Science, Lancaster University, United Kingdom
کشور
انگلستان – نیوزیلند
یک الگوریتم ایجاد ستون دو هدفه برای مسئله جریان با کمترین هزینه چند کالایی
چکیده
در این مقاله ما یک الگوریتم ایجاد ستون برای حل مسئله دو هدفه چند کالایی جریان با حداقل هزینه را ارائه می نمائیم. این روش بر مبنای روش سیمپلکس و تجزیه دانتزیگ – ولف می باشد. فرآیند آغازین این روش بر مبنای بهینه سازی مسئله مرتبط با اولین هدف می باشد، یعنی یک مسئله جریان چند کالایی تک هدفه، که با استفاده از فرایند تجزیه دانتزیگ – ولف حل می گردد. متعاقباً، مشابه با روش سیمپلکس دو هدفه، الگوریتم ما در یک پروسه تکراری از یک نقطه حدی نامغلوب به سمت نقطه بعدی، از طریق یافتن متغیرهای ورودی با ضریب حداکثری ارتقای هدف دوم و با تخریب اولین هدف، حرکت می نماید. روش ما قابلیت فرمول بندی مجدد این مسئله در قالب یک مسئله اصلی دو هدفه با توجه به مجموعه ای از محدودیت های ظرفیت و چندین مورد از مشکلات فرعی کسر خطی تک هدفه را خواهد داشت، که هر کدام از آن ها با توجه به مجموعه ای از محدودیت های بقای جریان شبکه مدنظر می باشند. مسئله اصلی بصورت تکراری اقدام به بروز رسانی ضرایب هزینه برای مسئله های – فرعی کسری می نماید. بر مبنای این ضرایب هزینه یک راه حل بهینه برای هر مسئله فرعی حاصل می شود. راه حلی که از بهترین نسبت مقدار هدف در بین کلیه مسایل فرعی برخوردار می باشد، معرف متغیر ورودی برای مستربیس به شمار می آید. این الگوریتم به هنگامی به انتها می رسد که هیچگونه متغیر ورودی دیگری وجود نداشته باشد که قابلیت ارتقای هدف ثانویه از طریق تخریب اولین هدف را داشته باشد. این مورد موکد آن است که کلیه نقاط حدی نامغلوب مشکل اصلی حاصل شده اند. بر این مبنا، ما عملکرد این الگوریتم را بر روی چندین نمونه از شبکه دو هدفه مستقیم با ویژگی های مختلف و تعداد مختلف کالاها مورد بررسی قرار می دهیم.
کلمات کلیدی:جریان های شبکه، مسئله جریان با حداقل هزینه چند کالایی دو هدفه، تجزیه دانتزیگ – ولف، ایجاد ستون، روش سیمپلکس دو هدفه
ستون دو هدفه مسئله جریان کمترین هزینه چند کالایی
۱- مقدمه
مسئله جریان با حداقل هزینه چند کالایی (MCMCF) به عنوان یک مسئله بهینه سازی شبکه ای به شمار می آید که در آن می بایست قابلیت ارسال چندین کالا از گره های چشمه / سورس به گره های چاهک / سینک وجود داشته باشد. بر این مبنا هر یک از این کالاها توانایی به اشتراک گذاری قوس ها و رقابت در خصوص ظرفیت آنها را خواهند داشت. با توجه به این موضوع، مشکل MCMCF را می توان به عنوان یک مسئله بهینه سازی خطی با دو مجموعه از قیدها مدل سازی نمود: قیدهای بقای جریان و قیدهای ظرفیت که ارتباط دهنده کالاها با یکدیگر می باشند. این قیدها از یک شکل قطری بلوکی خاص برخوردار می باشند. با توجه به مزیت این ساختار خاص، چندین رویکرد تجزیه برای حل این مشکل ارائه شده است (به مرجع [۱] و مراجع مرتبط رجوع شود). در بسیاری از مضامین کاربردی مدل های شبکه، نظیر حمل و نقل، مبحث تخصیص، ارسال و جابجایی مرکب کالا و مسایل مربوط به موقعیت، بیش از یک هدف وجود دارد که می بایست آنها را در نظر گرفت. این اهداف شامل زمان، هزینه، ریسک، نگرانی های محیطی و غیره می باشند. بنابراین مدل های جریان چند هدفه برای مدل سازی موقعیت های مرتبط با تصمیم گیری دنیای حقیقی، در مقایسه با مدل های تک هدفه، مناسبتر می باشند [۲، ۳، ۴، ۵، ۶، ۷، ۸]. در این مقاله ما مسئله جریان با حداقل هزینه چند کالایی دو هدفه (BMCMCF) را در نظر می گیریم. بر این مبنا، ما یک الگوریتم تجزیه را مشخص می سازیم که بر مبنای الگوریتم سیمپلکس دو هدفه می باشد و براساس آن نوعی ویژگی جدید تجزیه دانتزیگ ـ ولف جهت برنامه های خطی دو هدفه را ارائه می نماییم.
این مقاله به شرح ذیل سازماندهی شده است: مقاله جاری به طور مختصر در بخش دو مورد بحث قرار می گیرد. ویژگی های و سوابق ضروری ریاضیاتی همراه با روش سیمپلکس دو هدفه و روش تجزیه دانتزیگ ـ ولف استاندارد در بخش ۳ ارائه می شوند. در بخش ۴، روش BOSD پیشنهادی خود را عرضه می داریم. در نهایت نتایج عددی در بخش ۵ ارائه خواهند شد.
ستون دو هدفه مسئله جریان کمترین هزینه چند کالایی
۲- مباحث مرتبط
تحقیقات زیادی در خصوص مسایل MCMCF چند هدفه انجام نشده اند، بنابراین ما نسبت به بررسی تحقیقات انجام شده در خصوص مسایل جریان با حداقل هزینه چند هدفه با کاربرد صرف ویژگی های تک کالایی اقدام می نماییم. اخیرترین تحقیق انجام شده در این زمینه به وسیله Hamacher و همکاران [۱۲] ارائه شده است. از اینرو ما صرفاً تحقیقات جدید انتشار یافته در این زمینه را ارائه خواهیم نمود که یکی از آنها در ارتباط با ویژگی های چند کالایی می باشد.
Sedeno-Noda و همکاران [۱۳] فرآیند تغییر روش متغیرها را جهت حل مسئله جریان با حداقل هزینه دو کالایی غیر جهت دار دو هدفه عرضه داشتند. آنها این مسئله را به شرح ذیل ارائه داده اند:
با استفاده از مقادیر مطلق برای مقدار جریان در آخرین مجموعه قیدهای (۲)، مقادیر جریان برای هر یال ممکن است به صورت منفی مشخص شوند. روش ارائه شده به وسیله Sedeno-Noda و همکاران اقدام به جداسازی این مسئله به دو مسئله جریان با حداقل هزینه دو هدفه همراه با یک کالا نموده و از روش سیمپلکس شبکه پارامتری جهت حل این مسایل استفاده نمودند. این روش را نمی توان برای بیش از دو کالا تعمیم داد و بنابراین صرفاً برای مسایل دو کالایی غیرجهت دار مناسب خواهد بود.
Eusebio و همکاران [۱۴] نوعی الگوریتم سیمپلکس دو هدفه اولیه ـ دوگان را برای مسئله جریان شبکه تک کالایی دو هدفه ارائه نمودند که بر مبنای الگوریتم سیمپلکس اولیه ـ دوگان دو هدفه Ehrgott و همکاران [۱۵] می باشد، اما در عین حال از اطلاعات هزینه کاهشی جهت اجتناب از تکرار یا حشو استفاده نمودند. آنها اینگونه گزارش نمودند که روش آنها از عملکرد کارا و مناسبی در زمینه نمونه های بزرگ برخوردار نمی باشد.
Raith و Ehrgott [16] یک الگوریتم خاص را جهت محاسبه مجموعه کاملی از راه حل های کارآمد برای مسئله جریان با حداقل هزینه صحیح (تک کالایی) دو هدفی (BIMCF) بر مبنای روش دو فازه عرضه نمودند، برای کسب اطلاعات بیشتر به مرجع [۱۷] در زمینه روش دو فازی رجوع شود. در فاز ۱ آنها از یک الگوریتم سیمپلکس شبکه ای پارامتری [۱۸] جهت محاسبه کلیه راه حل های صحیح استفاده نمودند که تصاویر آن به صورت نقاط حدی کرانه conu(Z) مدنظر است، که در آن conu(×) به عنوان غلاف گوژ آرگومان آن و Z تصویر در فضای عینی مرتبط با مجموعه محتمل می باشد. از آنجایی که آنها اقدام به حل یک مسئله بهینه سازی دو هدفه صحیح نموده اند، تصاویر برخی از راه حل های کارآمد در بخش داخلی conu(Z) قرار می گیرند. در فاز ۲، این راه حل های کارآمد باقیمانده با استفاده از یک k بهترین الگوریتم جریان [۱۹] بر روی مسئله مجموع وزن دار عینی واحد محاسبه می شود. از آنجایی که مسایل صحیح چند هدفه مشکل تر از مسایل پیوسته می باشند، نمونه های BIMCF که در این مبحث حل شده اند همگی دارای اندازه کوچک بوده و کلیه الگوریتم های ذکر شده در این مبحث صرفاً برای نمونه های کوچک و متوسط کارآمد خواهند بود.
ستون دو هدفه مسئله جریان کمترین هزینه چند کالایی
۳- سابقه
در این بخش، سابقه ریاضیاتی ضروری ارائه می شود. ما همچنین اقدام به خلاصه سازی روش سیمپلکس دو هدفه و کاربرد تجزیه دانتزیگ ـ ولف استاندارد در خصوص مسئله MCMCF تک هدفه نمودیم. بر این مبنا یک مسئله بهینه سازی خطی دو هدفه (BLP) را به شرح ذیل در نظر گیرید:
۳ـ۱٫ روش سیمپلکس دو هدفه
مدل سازی مشکل BMCMCF (1) به عنوان یک برنامه خطی اجازه کاربرد روش سیمپلکس دو هدفه استاندارد را ارائه می نماید. Ehrgott [10] یک توصیف جامع در ارتباط با این روش را عرضه داشته و بر این مبنا ما نیز از همین ایده در این مبحث استفاده می نماییم. روش سیمپلکس دو هدفه در ابتدا کار خود را از طریق بهینه سازی این مشکل با توجه به اولین هدف آغاز می نماید. این روش متعاقباً به صورت تکراری از یک نقطه حدی ناغالب به سمت نقطه حدی دیگر حرکت نموده و سعی در یافتن متغیرهای ورودی با ضریب حداکثری ارتقا در ارتباط با هدف دوم با توجه به تخریب اولین هدف می نماید، با توجه به این موضوع لازم است تا انتخاب t در مرحله ۵ الگوریتم ۱ را در نظر گیرید. این روش به هنگامی متوقف خواهد شد که کلیه نقاط حدی ناغالب حاصل شده باشند. راه حل اولیه ممکن است از کارایی اندکی برخوردار باشد و چنین الگوریتمی احتمالاً قابلیت یافتن برخی از راه حل های کارآمدی را خواهد داشت که در آن اقدام به تعریف نقاط حدی ناغالب نشده است. این راه حل ها را می توان به آسانی در انتهای الگوریتم کنار گذاشت. توجه داشته باشید که مجموعه حاصله ممکن است همچنان حاوی راه حل هایی باشد که مشخص کننده نقطه مشابه در فضای هدف است. بر این مبنا لازم است تا کلیه این نقاط به عنوان ترکیبات کوژی نقاط ناغالب حدی حاصل آمده در نظر گرفته شوند. این پروسه در قالب الگوریتم ۱ ارائه شده است.
۳ـ۲٫ روش تجزیه دانتزیگ ـ ولف برای مسئله MCMCF
Dantzig [25] الگوریتمی را برای حل مسئله MCMCF بر مبنای روش تجزیه دانتزیگ ـ ولف ارائه نمود. در روش تجزیه دانتزیگ ـ ولف مسئله اصلی، یک نگارش تک هدفی (۱) در باب مسئله اصلی (MP) با توجه به مجموعه ای از قیدهای (پیچیده) ظرفیت، و مشکلات فرعی q، فرمول بندی می شود، که هر کدام با توجه به مجموعه ای از قیدهای بقای جریان، ، مدنظر خواهند بود. بر این مبنا MCMCF را می توان به شرح ذیل نوشت:
ستون دو هدفه مسئله جریان کمترین هزینه چند کالایی
۴- روش تجزیه سیمپلکس دو هدفه
در این بخش ما روش BOSD پیشنهادی را برای حل مسئله BMCMCF ارائه می نماییم. روش BOSD قابلیت فرمول بندی مجدد مسئله BMCMCF در یک مسئله اصلی دو هدفه (BMP) با توجه به مجموعه ای از قیدهای ظرفیت و مسایل فرعی q را خواهد داشت که هر کدام از آنها با توجه به مجموعه ای از قیدهای بقای جریان شبکه در نظر گرفته می شوند، یعنی EXk = bk برای K := 1, 2, …, q. BMCMCF را می توان به عنوان یک مسئله خطی دو هدفه به شرح ذیل نوشت (۸):
ستون دو هدفه مسئله جریان کمترین هزینه چند کالایی
۵- نتایج محاسباتی
در این بخش، ما نسبت به آزمایشات محاسباتی با استفاده از روش BOSD بر روی چندین نمونه شبکه ای دو هدفه جهت دار با ویژگی های مختلف و تعداد متفاوتی از کالا اقدام خواهیم نمود. کلیه آزمایشات عددی با استفاده از سیستم عامل ویندوز ۷ با سرویس پک ۱ و با بهره گیری از پردازنده (Intel (R) Xeon(R) (CPU، ۶۷/۲ گیگاهرتز، و رم ۶ گیگابایت، و با استفاده از سیستم عامل ۶۴ بیتی انجام شدند. این روش در برنامه متلب MATLAB R2013b Pro پیاده شد. کلیه مسایل فرعی خطی تک هدفه با استفاده از GUROBI 5.6 حل شدند [۲۸]. ما نتایج محاسباتی حاصله از چندین نوع از نمونه های شبکه دو هدفه جهت دار، با یک، دو، سه و پنج کالا، را حاصل آوردیم.
ستون دو هدفه مسئله جریان کمترین هزینه چند کالایی
۶- نتیجه گیری و تحقیقات آتی
در این مقاله، با یکپارچه سازی تجزیه دانتزیگ ـ ولف با روش سیمپلکس دو هدفه، ما اقدام به ارائه نوعی روش جدید برای حل مسئله BMCMCF نمودیم. این روش به عنوان اولین سیستم کاربردی (تجزیه دانتزیگ ـ ولف) در ارتباط با بهینه سازی دو هدفه به شمار می آید. این روش اقدام به فرمول بندی مجدد این مولفه در یک مسئله اصلی دو هدفه با توجه به مجموعه ای از قیدهای ظرفیت و چندین مسئله فرعی کسری خطی تک هدفه می نماید، که هر کدام در ارتباط با مجموعه ای از قیدهای شبکه ای مدنظر قرار می گیرند. پس از یافتن یک راه حل بهینه مرتبط با این مشکل با توجه به اولین هدف، مسایل فرعی کسری خطی اقدام به ایجاد ستون های ورودی برای هر مبنای مسئله اصلی به منظور حرکت از یک نقطه حدی ناغالب به نقطه دیگر می نمایند. ما عملکرد روش خود بر روی مجموعه های مختلف نمونه های شبکه دو هدفه با چندین کالا را مورد بررسی قرار دادیم. برحسب نتایج محاسباتی ما، تعداد کالاها دارای همبستگی مثبتی با تعداد میانگین نقاط حدی ناغالب می باشند و از یک همبستگی مثبت قوی با ضریب تعداد تکرارها در ارتباط با تعداد نقاط حدی ناغالب برخوردار می باشند. این بدان معنا می باشد که افزایش تعداد کالاها الزاماً منجر به افزایش میانگین زمان پردازنده نخواهد شد.
در این مبحث در ارتباط با تجزیه دانتزیگ ـ ولف برای مسایل جریان چند کالایی تک هدفه، این نقطه غالباً فرض می شود که چنین مواردی با توجه به یک چشمه و یک چاهک واحد برای هر کالا ساختاربندی شده اند [۲۵]. مسایل فرعی متعاقباً به عنوان مسئله کوتاهترین مسیر مدنظر قرار می گیرند. برای مسئله BMCMCF، ما می توانیم مشخص سازیم که از یک چشمه و یک چاهک واحد برای هر کالا برخوردار می باشیم. در مورد ویژگی دو هدفه، مسئله فرعی (۱۱) شامل یافتن یک جریان هزینه حداقلی در شبکه و عدم وجود ظرفیت بر روی قوس ها با توجه به تابع هدف کسری ذیل می باشد:
بعلت آنکه تابع هدف کسری، و بواسطه این حقیقت که ویژگی ایجادی ستون مسئله فرعی می بایست قابلیت یافتن متغیرها با هزینه کاهشی را داشته باشد، که به صورت منفی برای یک هدف و مثبت برای هدف دیگر است، مسایل فرعی مطرح شده در این باره بیش از این قابلیت حل به صورت ساده به عنوان مسایل کوتاهترین مسیر را نخواهند داشت. در آینده، ما کاربرد این روش ها را مورد خطاب قرار خواهیم داد، که بر مبنای آن قابلیت نشان دادن ساختار شبکه مسایل فرعی حاصل خواهد شد.
از آنجایی که این روش پیشنهادی بر مبنای روش سیمپلکس دو هدفه می باشد، کاربرد نوعی افزونه مرتبط با این رویکرد برای سه یا چند هدف ممکن است از طریق بررسی روش سیمپلکس چند هدفه کفایت داشته باشد. با این وجود، یافتن متغیرهای ورودی به بیس در روش سیمپلکس چند هدفه نیازمند راه حل برنامه های خطی تک هدفه دارد که الزاماً از یک ساختار شبکه ای برخوردار نمی باشند، رجوع به مرجع [۱۰]. این نوع از ویژگی تعمیم یافته بالقوه برای بیش از دو هدف، به عنوان یکی دیگر از اهداف تحقیقاتی آتی ما به شمار می آید.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
