سایت مقالات فارسی – تخصیص سفارش به تأمین کنندگان به کمک الگوریتم های متاهیوریستیک در شرکت …

(۵۵)
(۵۶)
(۵۷)
با جایگذاری در تابع هدف خواهیم داشت:
(۵۸)
با توجه به اینکه ها عدد صحیح هستند تابع هدف ما گسسته خواهد بود. از طرفی میتوان اثبات کرد که تابعی محدب است، بنابراین تابع هدف مسأله با فرض مشخص نمودن مقادیر محدب خواهد بود.
بنابراین برای حل حالتهای مختلف متغیر را در مسأله در نظر گرفته و پس از حذف ترکیب هایی که تقاضا را ارضا نمیکنند در نهایت حالتی که کمترین هزینه را داشته باشد به عنوان جواب مسأله انتخاب میکنیم.
بستههای نرمافزاری متداول معمولاً یک جواب بهینه محلی ارائه میدهند که در صورت محدب بودن تابع هدف همان جواب بهینه کلی خواهد بود. بنابراین ما از نرم افزار Lingo برای حل مثال استفاده خواهیم نمود. در ابعاد بزرگ نرم افزار Lingo قادر به حل سریع نیست و ما مجبوریم از الگوریتم ژنتیک و کد نویسی آن در نرم افزار مطلب برای حل مسأله استفاده کنیم.
خلاصه
در این فصل ابتدا ما به مدلسازی مسأله پرداختیم. در این مدل علاوه بر مدلسازی همزمان منافع خریدار در مورد اقلام معیوب تصمیم گیری می کنیم و سیاست برخورد با این اقلام مشخص می شود. نوع آوری ما در این تحقیق، نحوه برخورد با اقلام معیوب بود که با لحاظ کردن سیاست های تصمیم گیری در خصوص اقلام معیوب و لحاظ کردن تغییرات در مدل، مدل را بازنویسی کردیم. اگر q درصد از اقلام از نظر کیفیتی مناسب باشند با بقیه این اقلام به روشهای مختلفی میتوان برخورد کرد، بهترین راه که به نفع طرفین خواهد بود جداسازی این اقلام بر اساس حجم معیوب بودن آنهاست.
بهطور کلی با توجه به حجم معیوب بودن، یکی از تصمیمهای زیر را میتوان اتخاذ نمود:
برگرداندن کالای معیوب به تأمین کننده.
خرید محصول به عنوان محصول درجه ۲ توسط خریدار انجام شود و تعمیر آن بر عهده خریدار باشد.
خرید به صورت محصول درجه ۱ و تعمیر توسط تأمین کننده.
در فصل بعد در مورد متدولوژی حل مسأله بحث و صحبت خواهیم کرد.
فصل ۴:
متدولوژی حل مسأله
مقدمه
این فصل به حل مساله با استفاده از الگوریتم ژنتیک می پردازد. در ابتدا الگوریتم ژنتیک معرفی می شود و سپس ویژگیهای این الگوریتم مورد بررسی قرار می گیرد و در ادامه نحوه استفاده و به کارگیری این الگوریتم در حل مسأله بیان شده و در پایان مدل به کمک برنامه کامپیوتری مطلب کد نویسی شده است.
معرفی الگوریتم ژنتیک
پیشینهی الگوریتم ژنتیک به سال های حدود ۱۹۶۰ برمی گردد. در دهه های ۵۰ و ۶۰، تحقیقات متعددی برای استفاده از نظریه‌ی تکامل تدریجی و ایده‌های بنیادین داروین در بهینه سازی مسائل مهندسی به طور مستقل صورت گرفت. ایده‌ی اصلی در همه‌ی این سیستمها، رشد یک جمعیت از پاسخهای اولیه‌ی یک مسأله به سمت پاسخ بهینه با الهامگیری از عملگرهای انتخاب و تغییر ژنتیک طبیعی بود. الگوریتم ژنتیک نخستین بار در سال ۱۹۷۵ مطرح شد. بعدها این روش با تحقیقات گسترده‌ی افراد مختلف در سال ۱۹۸۹ جایگاه خویش را یافت و امروزه بهواسطه‌ی تواناییهای خویش جای مناسبی در میان دیگر روشها دارد.
همه‌ی موجودات زنده از واحدهای کوچکی به نام سلول تشکیل شدهاند. هر سلول نیز به نوبه خود از مجموعهای از یک یا چند کروموزوم[۲۵] تشکیل شده است. کروموزومها رشتههایی از مولکول DNA هستند که در حقیقت برنامه‌ی کاری موجود زنده را در خود ذخیره میکنند. هر کروموزوم شامل چندین ژن است. در طول تولید مثل[۲۶]، ژنها از کروموزومهای والدین با یکدیگر ترکیب[۲۷] شده تا کروموزوم جدیدی را تشکیل دهند. در طی این تغییرات، ممکن است تغییرات کوچکی در برخی از بخش های DNAی ژنهای فرزند، بوجود آید و فرزند دچار جهش[۲۸] شود. در نهایت تناسب[۲۹]یک موجود زنده با توجه به احتمال زیستن آن تعیین میشود.
روال بهینهیابی در الگوریتم ژنتیک براساس یک روند تصادفی هدایت شده استوار است. در این روش به بیان ساده، برای بهینه سازی تابع هدف مسأله، در هر مرحله، از یک جمعیت[۳۰] اولیه کروموزومها (افراد) که در حقیقت پاسخهای اولیه‌ی مسأله هستند، به یک جمعیت جدید از کروموزومها و یا یک نسل[۳۱] جدید که در حقیقت پاسخهای ثانویه مسأله‌ی مفروض هستند میرسیم. بنابراین با تکرار این عملیات و تولید جمعیت جدید از جمعیت قبلی در هر مرحله و در نتیجه رسیدن به نسلهای موفق، جمعیت به سمت یک پاسخ بهینه رشد خواهد کرد.
در الگوریتم ژنتیک هر کروموزوم نشان دهنده‌ی پاسخی از مسأله‌ی مورد نظر است. این پاسخ بسته به نوع کدسازی مسأله که با توجه به خصوصیات مسأله تعیین میشود، می تواند به صورت ماتریسی از اعداد حقیقی (کدسازی حقیقی)، یک رشته از بیتهای صفر و یکی (کدسازی باینری) و غیره مطرح شود. بنابراین هر کدام از ژنها که اجزای کروموزومها هستند، میتوانند نشانگر یک عدد حقیقی، یک بیت و غیره باشند[۹۸].
امروزه محققان بسیاری برای حل مدلهای خود در حوزهی علوم مختلف به الگوریتم ژنتیک روی آوردهاند و در شاخهی انتخاب تأمینکننده هم محققان بسیاری از این رویکرد استفاده کردهاند.
[۹۹] یک درخت پوشا براساس الگوریتم ژنتیک برای بهینهسازی مدل خود ارایه کردهاند. [۱۰۰] یک مدل زنجیرهی تأمین فازی با ترکیب الگوریتم ژنتیک و تئوری امکان ارایه کردهاند. [۱۰۱] مدلی برای تخصیص سفارش براساس اندازهگیری ریسک و هزینهی سفارشدهی ارایه داده و برای حل آن از الگوریتم ژنتیک استفاده کردهاند. بهعنوان نمونهای دیگر از تحقیقات این حوزه میتوان به [۱۰۳-۱۰۲] اشاره کرد.
وقتی مسأله از نوع برنامهریزی مختلط است برای اینکه بتوان از بستههای نرمافزاری برای حل آن استفاده کرد باید آنرا به مسألهی برنامهریزی خالص تبدیل کرد برای این منظور باید کلیهی مقادیری را که متغیر گسسته میتواند بپذیرد در نظر گرفت. سادهترین حالت، حالتی است که متغیر گسسته فقط میتواند مقادیر صفر و یک داشته باشد، پس از در نظر گرفتن کلیهی حالتهای صفر و یک حالتهایی که قادر به ارضای محدودیتها نیستند، حذف میشوند و برای حالتهای قابل قبول، بهکمک بستههای نرمافزاری جواب بهینه محاسبه شده و بهترین جواب از بین آنها، جواب نهایی مسأله خواهد بود.
با توجه به پیچیده بودن مدل این مسأله حل آن به کمک بسته های نرمافزاری زمانبر خواهد بود. بنابراین برای حل دقیق و سریع از الگوریتم ژنتیک استفاده شده است.
ویژگیهای الگوریتم ژنتیک
الگوریتم ژنتیک دارای ویژگیهای مهمی است که هنگام انتخاب روش حل مد نظر قرار گرفته است:
الگوریتم ژنتیک در هر تکرار، جمعیتی از جوابها را در فضای امکانپذیر مسأله ایجاد میکند نه فقط یک نقطه را. بنابراین پردازش موازی یکی از مهمترین برتریهای الگوریتم ژنتیک است. به این معنی که در این روش به جای یک متغیر، در یک زمان، یک جمعیت به سوی نقطه بهینه رشد مییابد و سرعت همگرایی روش بسیار بالا میرود.
الگوریتم ژنتیک هر جمعیت را با استفاده از قوانینی که بر پایه‌ی احتمالات و انتخاب تصادفی از جمعیت قبلی قرار دارد، شکل میدهد.
معیار الگوریتم ژنتیک جهت حرکت به سمت جوابهای بهتر تنها مقادیر تابع هدف هر جواب است و نه مشتق توابع یا اطلاعات کمکی دیگر. بنابراین اجباری بر مشتقپذیر بودن تابع نیست. در بسیاری از روشهای دیگر، بهینهسازی بر اساس مشتقات مراتب مختلف تابع صورت میگیرد.
با استفاده از این روش میتوان مسائلی را که نسبت به تغییر پارامترهای خود خوش رفتار نیستند (مثلاً دارای تناوب های زیاد و در نتیجه مینیممهای نسبی زیاد هستند و یا توابعی که به شدت غیر خطی عمل میکنند) با مقیاس خوبی بهینه کرد.
این روش برای بهینه سازی مسائلی که با کمیت های گسسته سر و کار دارند بسیار مناسب است.
ساز و کار الگوریتم ژنتیک
الگوریتم ژنتیک در هر مرحله برای رسیدن از یک جمعیت به نسل بعد از سه فرایند اصلی کمک میگیرد:

دانلود کامل پایان نامه در سایت pifo.ir موجود است.