مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی –  ایران ترجمه – Irantarjomeh

مقالات ترجمه شده آماده گروه مهندسی صنایع

مقالات ترجمه شده آماده کل گروه های دانشگاهی

مقالات

چگونگی سفارش مقاله

الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

چکیده

این مقاله در ارتباط با مسئله جریان چند کالایی با توجه به تابع هدف کسری می باشد. شرایط بهینگی و مفاهیم دوگانگی این مسئله در مبحث جاری ارائه می شوند. به همین منظور، فرمولاسیون برنامه نویسی خطی کسری این مسئله مدنظر قرار گرفته و تئوری های دوگانگی ضعیف، دوگانگی مستقیم قوی و قضیه های کمک مکمل ضعیف اثبات می گردند که برای انجام آنها از تئوری دوگانگی متعارف مسایل برنامه نویسی خطی استفاده می شود که متفاوت از نتایج یکسان حاصل آمده در مبحث  Chadha و Chadha (2001) به شمار می آیند [۱]. بعلاوه، قضیه کمک مکمل قوی (اکید) حاصل می گردد که تا آنجایی که اطلاع داریم برای اولین بار ارائه می شوند. تغییر شکل این قضیه ها به منظور یافتن هزینه های کاهشی جدید برای مسئله جریان چند کالایی کسری اعمال می شود. این پارامترها را می توان جهت ایجاد برخی از الگوریتم ها به منظور بررسی مسئله جریان چند کالایی در یک حالت مستقیم مورد استفاده قرار داد. در این مقاله، ویژگی کران داری مجموعه موجه اصلی به یک فرض ضعیف تر در خصوص قابلیت حل مسئله اولیه تقلیل می یابد که از جمله دیگر موارد مورد بررسی در این مبحث است. در نهایت، یک کاربرد دنیای واقعی در ارتباط با مسئله جریان چند کالایی کسری ارائه می شود.

کلمات کلیدی: بهینه سازی ترکیبی، برنامه نویسی خطی، دوگانگی، قضیه کمک مکمل قوی، مسئله جریان چند کالایی    

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

۱- مقدمه

بسیاری از سیستم های کاربردی، همانند حمل و نقل کالاهای متعدد فیزیکی، وسایل نقلیه، یا برنامه های ارسال پیام، با قابلیت به اشتراک گذاری شبکه مشابه، تحت حاکمیت قیدها و محدودیت های جریان شبکه ای خود قرار دارند [۲، ۳]. مسئله جریان چند کالایی را می توان با توجه به تعداد زیادی از طرح های شبکه ای و مسایل حمل و نقل در نظر گرفت [۴]. در این مسئله، برخی از کالاها را می بایست از مبدأ خاص خود به مقاصد دیگری با توجه به حداقل مجموع هزینه جابجا نمود [۲]. حل این مشکل تحت محدودیت صحیح به صورت NP ـ سخت می باشد [۲]. به هنگامی که توابع متعدد هدف یا توابع نامشخص ارائه می شوند، فرایند راه حل مشکل چند کالایی سخت تر از روش های سنتی خواهد بود [۵]. به هنگامی که صرفاً دو تابع هدف در نظر گرفته شود، همانند به حداقل رسانی  هزینه  یا  به حداکثر رسانی پایایی، می توان نسبت به بهینه سازی ضریب این توابع هدف اقدام نمود. مشکل برنامه نویسی کسری فراهم آمده را می توان از طریق بکارگیری برخی از رویکردهای مدنظر حل نمود. به علاوه، برنامه های کسری در تعداد زیادی از مشکلات عملی رخ می دهند [۶، ۷] که می توان آنها را در تحلیل شبکه دیگر نیز دنبال نمود. برای آنکه مسایل چند کالایی کسری قابلیت ارضای تقاضا برای هر کالا در هر گره بدون نقض قیدهای تحمیلی برحسب مؤلفه های عرضه ـ تقاضا و ظرفیت را داشته باشند، می توان مدل جریان چند کالایی کسری حداکثری ذیل را در نظر گرفت که در آن G = (N, A) به عنوان شبکه ای با N و A به عنوان مجموعه های متشکل از n گره و m لینک مشخص شده اند:

بر مبنای این نتایج جدید و در ارتباط با برنامه نویسی خطی کسری، مسئله دوگان مرتبط با مسئله جریان چند کالایی کسری در بخش ۳ مشخص گردیده و هزینه کاهشی جدید جهت کنترل بهینگی راه حل ها ارائه می شود. در نهایت، شرایط کمک مکمل اثبات گردیده و کاربرد دنیای حقیقی برای مسئله جریان چند کالایی کسری عرضه خواهد شد. بخش ۴ برخی از نکات اصلی را به طور خلاصه ارائه می نماید.

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

۲- خواص دوگانگی برای مسئله برنامه نویسی خطی کسری

از طریق تبدیل متغیر چارنز ـ کوپر [۱۲]،

لم ۲ـ۱٫ (به مرجع [۱۳] رجوع شود). این مسئله (۱ـ۳) دارای راه حل بهینه ای خواهد بود، آن هم در صورتی که تنها مسئله (۲ـ۱) دارای یک راه حل باشد. در حقیقت، در صورتی که x به عنوان راه حل بهینه مسئله (۱ـ۳) محسوب شود،…

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

۳- شرایط بهینگی برای مسئله جریان چند کالایی کسری

در این بخش، ما مسئله  جریان چند کالایی کسری  (۱ـ۱)  که در مواجهه  با مسئله (۱ـ۲) می باشد را در نظر گرفته و سعی دریافتن برخی از شرایط بهینگی برای این مسئله می نماییم. با انجام این کار می توان اقدام به ارزیابی این موضوع نمود که آیا قابلیت یافتن یک راه حل بهینه برای این مسئله را خواهیم داشت یا خیر. علاوه بر این قابلیت تفسیر الگوریتم های مختلف به عنوان روش های خاص برای حل شرایط بهینگی حاصل گردیده و در وهله های مختلف حتی می توان رویکردهای الگوریتمی نوینی را برای حل این مسئله مورد بررسی قرار داد [۲]. از آنجایی که مسئله جریان چند کالایی کسری به عنوان یک برنامه خطی کسری به شمار می آید، که بر مبنای تئوری دوگانگی برنامه نویسی خطی می باشد، ما قابلیت ارائه ویژگی دوگان مسئله جریان چند کالایی کسری (۱ـ۱) و (۱ـ۲) را خواهیم داشت. به واسطه وجود محدودیت های مختلف برای هر لینک (i, j)، قیدهای موازنه جرم برای هر ترکیب گره ـ کالا و یک قید کمکی، این ویژگی دوگان مرتبط با چنین مسئله ای دارای سه نوع از متغیر به شرح ذیل می باشد: یک قیمت q_ij بر روی هر لینک (i, j)، پتانسیل گره  برای هر نوع ترکیب کالای k و گره i و همچنین یک متغیر کمکی z مرتبط با قید کمکی مربوطه. با بکارگیری این متغیرهای دوگان، قابلیت تعریف هزینه کاهشی  لینک (i, j) با توجه به کالای k به شرح ذیل وجود خواهد داشت:

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

۴- سیستم کاربردی شرکت جهانگردی

یک شرکت جهانگردی تمایل دارد تا نسبت به انتخاب مسیرهای مناسب و منطقی جهت انتقال مشتریان خود (توریست ها) از مبدأ به برخی از مقاصد مشخص شده در شهرهای شمالی ایران در نزدیک دریای خزر، بر حسب شکل ۱، اقدام نماید. در اینجا چندین نوع گره مختلف وجود دارد: A به عنوان مبدأ توریست ها، C هر دوی مبدأ و مقصد، E، F، I و K مقاصد آنها و موارد دیگر شهرهای میانی می باشند. شبکه شکل ۲ را در نظر بگیرید، که گره های آن به عنوان شهرهای اصلی و مقصد شکل ۱ به شمار آمده و لینک ها مترادف با مسیرهای حقیقی بین هر جفت  گره ها  به شمار می آیند. در این مثال،  اصطلاحات و  ویژگی های  ذیل بکار گرفته  می شوند.

• یک گروه توریست که در حال سیر بین یک مبدأ مشخص p و مقصد مشخص q می باشند به عنوان کالای در نظر گرفته می شود، و مجموعه چنین گروه هایی توریستی (کالاها) نیز به صورت  مشخص می شوند:

• برای هر گروه توریست های به عنوان تعداد مسافرین از p به q در نظر گرفته می شود. بنابراین برای هر  ما این مورد را خواهیم داشت:

مسئله جریان چند کالایی کسری: شرایط دوگانگی و بهینگی

۵- نتیجه گیری و رهنمودهای آتی

در این مقاله، یک مسئله جریان چند کالایی کسری مورد بررسی قرار گرفته است و بر مبنای شاخص های برنامه ریزی خطی، ویژگی دوگانه این مسئله تعریف گردیده و برخی از ویژگی های دوگانگی با توجه به رویکرد جدید حاصل آمده است. به علاوه قضیه کمک مکمل قوی برای یک مسئله کسری خطی اثبات می شود، که تا آنجایی که اطلاع داریم به عنوان اولین مورد انجام شده در این زمینه به شمار می آید. این ویژگی قابل توجه می باشد و حقیقتاً به عنوان یک مؤلفه مهم به شمار می آید، و جهت گسترش روش های نقطه داخلی به منظور حل این کلاس مسایل بهینه سازی کاملاً مفید می باشد (به مرجع [۱۵] رجوع شود).

مسئله دیگری نیز وجود دارد که می بایست آن را مدنظر قرار داد. این مورد تشریح شده است که به منظور کاربرد تئوری دوگانگی مسایل برنامه نویسی کسری خطی، الزامی جهت فرض کران داری مجموعه های محتمل اولیه وجود ندارد. بدینسان صرف فرض قابلیت حل مسئله اولیه کفایت خواهد داشت. بنابراین انجام تحقیقات آتی در ارتباط با موضوع یافتن برخی از شرایط مکفی ضعیف که تضمین کننده قابلیت حل مسایل کسری اولیه می باشد از جمله موارد مهم در این عرصه به شمار می آید.

به علاوه، شرایط بهینگی کمک مکمل برای مسئله جریان چند کالایی کسری ارائه شده است، که بر مبنای تعداد زیادی از الگوریتم های بهینه سازی می باشد. این مسئله را می توان در تحقیقات آتی نیز دنبال نمود. به علاوه قابلیت بررسی رویه های گسترشی برخی از الگوریتم ها بر مبنای فرایند آزاد سازی لاگرانژی در ارتباط با مسایل جریان چند کالایی کسری با توجه به استفاده از نتایج این تحقیق نیز وجود خواهد داشت.