پیوستها55
پیوست 156
پیوست 257
واژهنامه انگلیسی به فارسی58
فهرست مراجع62
فهرست شکلها
شکل 1-1: منحنی قیمت _ مقدار12
شکل 2-1: روند کلی الگوریتم ژنتیک18
شکل 2-2: نمونه ای از انتخاب در چرخ رولت25
شکل 3-1: نحوه فعال کردن GA ………………………………………………………………………………………………..49
شکل 3-2: پنجره GA ……………………………………………………………… …………………………………………..50
شکل 3-3: پنجره SA ……………………………………………………………………… …………………………………..51
فهرست جدولها
جدول صفحه
جدول 2-1: تشکیل کروموزم21
جدول2-2: مثالی از تبدیل کد گذاری22
جدول 2-3: محاسبه تابع بهینه23
جدول 2-4: محاسبه درصد برازندگی23
جدول2-5: تشکیل چرخ رولت25
جدول 2-6: عمل پیوند26
جدول 2-7: مقایسه بین یک مساله و الگوریتم بهینهسازی با یک سیستم فیزیکی………………………………………………………………………….29
جدول 3-1: مقادیرqij و tij در مثال 140
جدول 3-2: مقادیرxijmax وxijmin در مثال 141
جدول 3-3: aij و bij در مثال 141
جدول 3-4: aij و bij در مثال 242
جدول 3-5: مقادیرxijmax وxijmin در مثال 242

جدول 3-6: مقادیرqij در مثال 342
جدول 3-7: مقادیر tij در مثال 443
جدول3-8: جوابهای ایده ال از یک مجموعه 5 تایی مثال عددی46
جدول3-9: ادغام مقادیر اهداف تابع z برای هر مثال47
جدول3-10: بهینه (نزدیک بهینه) تابع هدف z4, z3,z2,z1 مطابق z در مثال 248
جدول 3-11:مقادیرxij بدست آمده از GA در مثال248
جدول3-12:مقادیرxij بدست آمده از SA درمثال 248
چکیده
مدلسازی مسالهی تخصیص سهم به تامینکننده با هزینهی سفارش وابسته
مهری علیپور
یکی از موضوعات جالب توجه در مدیریت زنجیره تامین، مدیریت عرضه است که بهطورکلی مربوط به فعالیتهای مربوط به تامینکنندگان ازقبیل توانمند سازی، ارزیابی مشارکت و … است. هدف اصلی از ارزیابی تامینکنندگان کالا، تعیین سهمیه مطلوب اختصاص داده شده بههر تامینکننده کالا در هنگام سفارش دادن خریداران میباشد.
در این پایاننامه یک مدل چندهدفه پیشنهاد میشود که در آن هزینههای خرید، واحدهای مرجوع شده و تاخیر در تحویل واحدها به حداقل و نمره کل بهدست آمده از فرایند ارزیابی تامینکننده کالا به حداکثر برسد. فرض میکنیم که خریدار، محصولات متعددی از تعدادی تامینکننده از پیش تعیین شده تهیه میکند. تقاضای خرید، تصادفی با توزیع احتمال پواسون برحسب قیمت هر نوع محصول میباشد. همچنین فرض اصلی ایناست که قیمتهای تامینکننده کالا بهصورت خطی وابسته به اندازه سفارش هر محصول است. از آنجا که تقاضا تصادفی است، خریدار ممکن است علاوه بر هزینهی خرید منظم، متحمل هزینههای نگهداری و کمبودکالا نیز بشود.
ما بهکمک روش معروف متریکL-1 برای حل مساله ارزیابی تامینکننده کالا از دو الگوریتم ابتکاری GA وSA استفاده میکنیم.
کلمات کلیدی : ارزیابی تامینکننده کالا ، اختصاص سهمیه ، تقاضای تصادفی ، قیمت وابسته به تقاضا.
A b s t r a c t
Modeling a supplier quota allocation problem with price-dependent ordering
Mehri Alipour
One of the interesting subjects in supply chain management is supply management, which generally relates to the activities regarding suppliers such as empowerment, evalution and so on. A major objective of supplier evaluation involves buyers determining the optimal quota allocated to each supplier when placing an order.
In this thesis, we propose a multi-objective model in which purchasing cost, rejected units, and late delivered units are minimized, while the obtained total score from the supplier evaluation process is maximized. We assume that the buyer obtains multiple products from a number of predetermined suppliers. The buyer faces a stochastic demand with a probability of Poisson distribution regarding each product type. A major assumption is that the supplier prices are linearly dependent on the order size of each product. Since demand is stochastic, the buyer may incur holding and stock out costs in addition to the regular purchasing cost. We use the well-known L-1 metric method to solve the supplier evaluation problem by utilizing two meta-heuristic algorithms (SA and GA) to solve the corresponding mathematical problems.
Keywords: Supplier selection, Quota allocation, Stochastic demand, Price-dependent demand.
مقدمه :
در دهه گذشته، مدیران به اهمیت نقش زنجیره تأمین1 SCM در ارزشآفرینی شرکتها پیبردهاند. اسمیچی لوی و همکاران (2004) SCM 2 را بهعنوان مجموعهای از روشهای مورد استفاده برای ادغام موثر تامینکنندگان، انبارها و فروشگاهها تعریف میکند بهطوریکه برای بهحداقل رساندن سیستم گستردهی هزینهها، کالا در مقادیر مناسب تولید شود و به مکان مناسب برده و در زمان مناسب توزیع شود، در حالیکه خدمات مورد نیاز در سطح رضایت بخش باشد [3]. فعالیت خرید بهعنوان یک قابلیت رقابتی یکی از مهمترین فعالیتهای زنجیره تامین است. با توجه به نقش تعیینکنندهی تامینکنندگان در کیفیت محصول نهایی و نهایتا رضایت مشتری، سازمانها عملکرد تامینکنندگان خود را بهصورت دورهای ارزیابی مینمایند. از آنجا که ادبیات در انتخاب تامینکننده کالا گسترده است ما مسئلهی اختصاص سهمیه تامینکننده را روی مواردی که در تکنیکهای مدلهای تصمیمگیری چندهدفه MODM 3 استفاده میشود مختص میکنیم. درحال حاضر تحقیقات در این زمینه به بخشهای زیر تقسیم میشود:
– مدلهای برنامهریزی ریاضی فقط با یک تابع هدف: با توجه به مدلهای با یک تابع هدف، قدسیپور و ا برایان(2001) 4یک مدل برنامهریزی غیرخطی عدد صحیح مختلط را بهمنظور حل مسئلهی چندهدفه منابع برای بهحداقل رساندن هزینه کل خرید سالانه فرموله کردند [4].
-مدلهای برنامهریزی ریاضی با دو تابع هدف، مینیمم کردن هزینه و ماکزیمم کردن سود: ونتورا و مندوزا (2008)5 یک روش دو مرحلهای برای مسئله انتخاب تامینکننده کالا و تخصیص مقدار سفارش بهطور همزمان ارائه کردند. چه و وانگ (2008)6 یک الگوریتم پایه ژنتیک و مفاخری و همکاران(2011)، برنامهریزی پویا چندهدفهیدو مرحلهای برای آن پیشنهاد کردند و جعفری و همکاران (2011) یک مدل عدد صحیح مختلط دو هدفه برای مینیمم کردن مجموع هزینهها و ماکزیمم کردن بازده کل ارائه کردند [5-8].
– مدلهای با حداقل سه تابع هدف، بهحداقل رساندن هزینه، اقلام تاخیری و واحدهای مرجوع شده: کارپاک و همکاران(2001)7 یک مدل برنامهریزی هدف برای مسئله ارزیابی و انتخاب تامینکنندگان با سه هدف شامل هزینه،کیفیت و توانایی تحویل پیشنهاد کردند. فضلالهپور و همکاران (2011)، رضایی و داوودی(2011)، سیفبرقی و اسفندیاری (2011) نیز از جمله کسانی هستند که در این مورد پژوهش کردند [9-12].
– مدلهای فازی که با ابهام و عدم دقت در داده های ورودی مانند تقاضا و ظرفیت مواجه میشوند: عمید و همکاران (2006)8 و کومار و همکاران (2006)9 مدلهای برنامهریزی چندهدفه فازی ارائه کردند [13و14].
– مدلهایی با انواع مختلف تخفیفهای تامینکنندگان، با توجه به پیچیدگی مسئله از الگوریتم ابتکاری برای حل آن استفاده شدهاست: معقول و رزمی(2009)، محمد ابراهیم (2009) و کمالی و همکاران (2011) در این زمینه تحقیق کردند [15-17].
– مدلهای با عدم قطعیت تقاضا، ظرفیت و غیره: لی و زابینسکی10(2011) و ژانگ و ژانگ11 (2011) یک مسئله انتخاب تامینکننده کالا، تکمحصول، تکهدفه و مسئله خرید تحت تقاضای تصادفی را بیان کردند. هدف به حداقل رساندن انتخاب، خرید، نگهداری و هزینههای کمبود برای انتخاب تامینکنندگان و تخصیص مقدار سفارش می باشد [18و19].
در این پایان نامه فرض میکنیم، خریداری که محصولات مختلف را از تعدادی تامینکنندهی از پیش تعیین شده فراهم میکند، با تقاضای تصادفی و توزیع احتمال پواسون مواجه است. از آنجا که تقاضا تصادفی است خریدار با هزینههای کمبود و نگهداری کالا، علاوه بر هزینه خرید بهطور معمول، مواجه میشود. همچنین فرض کردهایم که قصد خریدار جایگذاری مینیمم مقدار سفارش برای هر تامینکننده است. نیاز چنین فرضی ایناست که خریدار مایل به حفظ همکاری مستمر با تامینکنندگان انتخابشده باشد. لذا قیمت ارائه شده برای هر تامینکننده کالا بهصورت خطی وابسته به اندازه سفارش هر محصول است.کاستا و الیویرا 12(2001) استراتژیهای تکاملی مانند الگوریتم ژنتیک (GA) و شببیه سازی تبرید (SA) را بهعنوان بهترین الگوریتم برای حل مسائل برنامهریزی صحیح غیرخطی 13NIPمعرفی کردند[20]. در فصل اول با معیارهای تصمیمگیری و نمادها و فرمولبندی مسئله آشنا میشویم. در فصل دو به بررسی الگوریتمهای راهحل پرداخته و در فصل سه بهمنظور بررسی مدل و ارزیابی عملکرد روشهای پیشنهاد شده، مثالهایی ارائه و نتایج حاصل از حل آنها مقایسه میشود.

فصل اول
مفاهیم اولیه
معیارهای تصمیم گیری، نمادها و ارائهی مدل
مسئله تخصیص سهم به تامینکننده
برای آشنایی بیشتر با اهمیت مسئله تخصیص سهم به تامینکننده، ابتدا به ذکر چند تعریف میپردازیم.
زنجیره تامین: تمام فعالیت‌هاى مرتبط با جریان و تبدیل کالاها از مرحله ماده خام (استخراج) تا تحویل کالاى نهایى به مصرفکننده نهایى و نیز جریان‌هاى اطلاعاتى مرتبط با آنها را شامل مى‌شود.
مدیریت زنجیره تامین: یکپارچه سازى فعالیت‌هاى زنجیره تامین و نیز جریان‌هاى اطلاعاتى مرتبط با آن، از طریق بهبود و هماهنگ سازى فعالیت‌ها در زنجیره تامین از جمله موجودی و ترابری، تولید و عرضه محصول، براى دستیابى به مزیت رقابتى قابل اتکا و دائمی می باشد، تا بهترین ترکیب ممکن از پاسخدهی و کارایی برای بازاری که آن را تغذیه می کند بهدست آید.
تامینکننده: تامینکننده کسی است که بخشی از کالاها یا خدمات موردنیاز یک سازمان را درجهت تولید محصول یا ارائه خدمت به مشتری تامین میکند.
برای پیادهسازی مدیریت زنجیرهی تامین موانعی وجود دارد که عبارتند از:
تعدد مراکز تصمیمگیرى
عدم اطمینان زنجیره تامین از پیشبینی تقاضا
عدم اطمینان زنجیره تامین از زمانهای تحویل
عدم هماهنگی یک بخش شرکت با دیگر بخشها
تغییرات نامنظم در سفارشات
که اهمیت تعیین و تخصیص سهم به تامینکننده را بیشتر میکند.
تغییرات بسیار سریعی که در سرتاسر بازارهای جهانی اتفاق میافتد، به طور اساسی روشی را که مدیران به محیطشان مینگریستند، تغییر داده است. یکی از حوزههایی که مدیران توجه خود را بیشتر به آن معطوف کردهاند، مدیریت منبعیابی و خرید است.
سازمان باید اطمینان یابد که خرید انجام شده با الزامات و نیازمندیهای خرید انطباق دارد. نوع و گسترهی کنترل اعمال شده بر تامین کننده و اقلام/مواد و تجهیزات خریداری شده بر مراحل بعدی پدیدآوری محصول یا بر محصول نهایی بستگی دارد. سازمان باید تامینکنندگان را بر پایه توانایی آنان در تامین اقلام/مواد و تجهیزات/خدمات بر طبق الزامات سازمان ارزیابی و انتخاب کند. معیارهای انتخاب، ارزیابی و ارزیابی مجدد باید تعیین گردد.
در دهه اخیر، مدیریت خرید، در زنجیره تأمین چالشی برای عمدهی شرکتها بوده است و دستیابی به یک سطح رقابتی جهانی در زمینه تأمین، به یک نیاز اساسی تبدیل شده است. در بیشتر صنایع هزینه مواد خام (و قطعات(، هزینه اصلی محصول نهایی را تشکیل میدهند. بنابراین، دپارتمان خرید میتواند نقش کلیدی در کارایی و اثربخشی یک سازمان ایفا کند، زیرا میتواند اثر مستقیمی روی کاهش هزینه، سودآوری و انعطاف پذیری شرکت داشته باشد. بدون تردید، مهمترین و حساسترین مرحله در فرآیند خرید هر سازمان، ارزیابی و انتخاب تأمینکنندگان بهمنظور اختصاص سهم مناسب است. اهمیت انتخاب تأمینکننده از این حقیقت ناشی میشود که آنها تأمین منابع را تعهد میکنند، درحالیکه به طور همزمان بر فعالیتهایی، از قبیل مدیریت موجودی، برنامهریزی و کنترل تولید، الزامات جریان وجوه نقد و کیفیت محصول نیز اثر میگذارند.
در این بخش برای آشنایی با مسئله و مدل مربوط به آن، به مقدماتی در ارتباط با سیستمهای مختلف و معیارهای تصمیمگیری در آنها ، برگرفته از منبع [1] پرداخته میشود.
1-1 جریان مواد
موسسههای تولیدی، مواد اولیه و قطعاتی را تهیه و تا زمان نیاز انبار میکنند. تهیه و مدیریت انبار اقلام مربوطه را “تدارک” مینامیم. این عمل(تدارک)، مواد ورودی بخش تولید را تامین میکند. بخش “تولید” با پردازشهای لازم روی مواد اولیه و قطعات، تولیدات خود را تامین میکند. کالای تکمیل شده ممکن است در کنار مرکز تولید یا انبارهای محلی نگهداری شود. در هر حال کنترل کمیت آنها بخشی از وظایف”توزیع” است.
سه مشخصه جریان مواد مورد توجه مدیریت تولید قرار میگیرد:
کیفیت
کمیت زمانی
مخارج
منظور ازکیفیت، میزان انطباق خصوصیات تولید بر خصوصیات تعیین شده قبلی میباشد. منظور ازکمیت زمانی، حجم مواد پردازش شده در هر دوره زمانی و منظور از مخارج، بهای کلیه منابع و امکانات بهکار گرفته برای تولید کالا میباشد.
1-2 : انواع سیستمها
به طور کلی چهار نوع سیستم جریان مواد را میتوان برشمرد:
سیستم تولید پیوسته که انواع محدودی کالای مشابه در حجم زیاد و بطور دائم تولید میکند.
سیستم تولید منقطع که حجم زیادی از یک نوع کالا تولید و سپس تولید کالای دیگری شروع میشود.
سیستم پروژهای که یک یا چند نوع کالا اغلب فقط برای یک مرتبه تولید میکند.
سیستم انبار محض که پردازشی روی مواد صورت نمیگیرد و فقط کالایی تهیه و به متقاضیان تحویل میشود.
ازآنجا که مسئله اختصاص سهم به تامین کننده به سیستمهای انبار مربوط میباشد به تشریح معیارهای تصمیمگیری مربوط به سیستمهای انبار میپردازیم.
1-3 : مسائل تصمیمگیری
تصمیماتی که برای اداره سیستمهای تولیدی و انبار گرفته میشود، عموما دو نوع میباشند: نوع اول آنهایی که از روی قاعده و بهمنظور تنظیم جریان مواد صورت میگیرد، نوع دوم آنهایی که گهگاه به منظور اعمال سیاستها و ظرفیتها است.
در سیستمهای انبار محض تصمیمات اساسی عبارتند از:
چه اقلام یا کالایی را انبار نمود؟
چه موقع سفارش تهیه کالا داد؟
چقدر سفارش داد؟
به چه کسی سفارش داد؟
جهت بهعمل آوردن این تصمیمات بهطورمنطقی، سیستم مدیریت باید شامل یک روال پیش بینی تقاضا و یک سیاست سفارش باشد تا با توجه به سطح موجودی و حجم تقاضا مقدار سفارش را تعیین نماید.
1-4 : معیارهای تصمیمگیری
اهدافی که در کلیه تصمیمگیریهای مربوط به جریان مواد مورد توجه میباشند متنوع بوده و ممکن است در سیستمهای مشابه، متفاوت یا بالعکس در سیستمهای متفاوت، مشابه باشند. بههرحال بعضی از این اهداف عبارتند از:
کسب حداکثر درآمد
کاهش هزینه تدارک، تولید و توزیع
ارائهی سرویس خوب و جلب رضایت مشتری
کاهش میزان سرمایهگذاری در انبارها
پایین نگهداشتن حجم سرمایهگذاری روی وسایل تولید
در ساخت مدلها سعی میشود کارایی ها بر اساس یک واحد پولی اندازهگیری شوند. همچنین در این مدلها عوامل اقتصادی زیر بر حسب تناسب مورد توجه قرار می گیرند:
درآمدهای حاصل از فروش
مخارج تولید، تهیه و توزیع
زیانهای ناشی از کمبودات
مخارج سرمایهگذاری در انبارها
هزینههای تغییر نرخ تولید

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

هزینههای تغییر سطح نیروی کار
هزینههای تغییر امکانات.
1-5 : مخارج سیستمهای انبار
منظور از انبار، تجمع (یا ذخیره سازی) اشیایی است که بعدا برای ارضای نیازها و تقاضاهایی مصرف خواهند گردید. موجودی انبار عبارتست از حجم یا تعداد واحدهای کالایی که در انبار و در دسترس موجود است. وقتیکه موجودی انبار صفر است، گوییم حالت کمبود پیش آمده است. هر تقاضایی که در این مدت به انبار برسد قابل پرداخت نبوده و به عنوان کمبود در نظر گرفته میشود. چنانچه قرار باشد اینگونه تقاضاها بعدا وقتی مجددا کالایی به انبار رسید، اجابت شود، آنها را پستحویل یا تعویق تقاضا مینامند. در حالت دیگر اینگونه تقاضاها از دست میروند. بدین معنی که یا متقاضی نیازش را از جای دیگر برطرف میکند یا کالای دیگری بهجای کالای تقاضا شده انتخاب میکند. موقعیکه سفارش تهیه کالا برای ورود به انبار انجام شود ممکن است مدتی طول بکشد تا کالای سفارش داده شده عملا وارد انبار گردد این فاصله زمانی را مدت تاخیر یا تحویل گویند.
اداره یک سیستم انبار نیاز به داشتن یک روش تدارک کالا است. این روش باید مشخص کند که، چه موقع باید سفارش یا عمل تهیه کالا انجام شود و چه مقدار تهیه شود. بدیهی است که مقدار ورود کالا به انبار بر سطح موجودی و حجم کمبود اثر مستقیم دارد. لذا به منظور ارزیابی سیاستهای مختلف و بهکار بستن آنها لازم است مخارج اداره یک سیستم انبار را شناخت.
اقلام اصلی مخارج در سیستمهای انبار عبارتند از:
مخارج تدارک کالا
نگهداری کالا
کمبودها
مخارج اداره سیستم.
مخارج تدارک شامل دو بخش است: یک بخش مخارجی که مستقل از حجم کالای تدارک دیده شده میباشد، این مخارج ممکن است از قبیل پردازش و انجام مقدمات سفارش، ترخیص، حسابداری و غیره باشد. بخش دیگر شامل مخارج مربوط به حجم کالای تدارک دیده شده همانند بهای کالا، مخارج حملونقل و غیره میباشد. گاهی به بخش اول مخارج تدارک کالا (یا مخارج ثابت تدارک) و به بخش دوم مخارج متغیر سفارش گفته میشود. مخارج نگهداری کالا در انبار شامل مالیاتها، صدمات، فسادها و مخارج فضای انبار (مانند سیستمهای تهویه، نگهبان و غیره) و مخارج حاصل از رکود سرمایه در انبار میباشد. زمانی که سیستم موقتا فاقد موجودی بوده و تقاضایی برسد، زیان حاصل، متناسب با سرنوشت تقاضا، متفاوت خواهد بود. در حالتیکه تحویل کالا تا ورود محموله بعدی به تاخیر بیافتد، مخارج ممکن است شامل حمل یا جابجایی ویژه، متوقف شدن بسیاری فرایندهای تولیدی دیگر که به این کالا وابستهاند و حتی صدمات سنگین و حیاتی (مانند کمبود مهمات در سیستمهای نظامی یا کمبود دارو در سیستمهای پزشکی) باشد و در حالتیکه کالای دیگری جایگزین کالای مورد تقاضا شود، اگر کالای جایگزین از کیفیت پایینتری برخوردار باشد باعث عدمرضایت و کاهش اطمینان متقاضی خواهد شد و چنانچه از کیفیت بالاتر و در نتیجه بهای بیشتری برخوردار باشد مسلما برای سیستم زیان آور است و در حالتیکه متقاضی درخواست خود را لغو کند، زیان حاصل برابر سودی است که از دست میرود. لذا فرض میکنیم به ازای هر یک واحد کالای کمبود، زیان ثابتی برابر π ریال وارد میگردد.
1-6 مدلسازی سیستمهای تصادفی تکدورهای
در سیستمهای تکدورهای، کالا (کالاها) برای برآورد تقاضا در یک دوره تدارک دیده میشوند و کالایی که در انتهای دورهی برنامهریزی باقی میماند، در این دوره دیگر مصرف نداشته و لذا یا باید با هزینهای برای دوره بعد نگهداری شود یا بهدلیل هزینهی نگهداری یا فاسد شدن یا تکمیل نیاز متقاضیان و غیره ازبین برده شوند. بدین لحاظ در اینگونه سیستمها برنامهریزی فقط شامل یکدوره خواهد گردید. خصوصیت دیگری که در این سیستمها وجود دارد ایناست که بهدلیل کوتاهی دوره یا طولانی بودن زمان دریافت مواد یا قطعات اولیه یا زمان تولید، تدارک مواد یا قطعات اولیه در طول دوره میسر نبوده یا مفید نمیباشد. لذا هر اندازه که لازم است باید قبل از شروع دوره، دریافت یا سفارش شده باشد.
حجم تقاضا در طول دوره که با x نمایش داده میشود تصادفی و دارای تابع احتمالf(x) است.x_ij را سایز سفارش محصول j اختصاص یافته به تامینکننده i مینامیم. چنانچه سطح انبار در ابتدای دوره، بعد از تدارک کالا را با∑_j▒∑_i▒x_ij نشان دهیم، آنگاه مسئله بهصورت یافتن مقداری از x_ijکه هزینه کلی سیستم را بهحداقل برساند، در میآید.
با توجه به اینکه افق کار سیستم تنها شامل یک دوره بوده و در صورت کمبود، تقاضای وارده لغو میگردد، فرض میکنیم مخارج کمبود، π واحد برای هر واحد کالای کمبود باشد. کالاهایی که در انتهای دوره در انبار باقی میمانند، بسته به نوع آنها و خصوصیات سیستم، یا باید با صرف هزینهای از انبار خارج گردند یا با بهای کمتری به فروش رسانیده شوند.
در مورد مخارج نگهداری در این سیستمها دو حالت را میتوان در نظر گرفت. حالت اول ایناست که در صورت کوتاه بودن طول دوره، این مخارج تنها شامل کالاهایی که در انتهای دوره باقی ماندهاند، باشد. در حالت دوم مخارج نگهداری طبق روش معمول تاکنون به زمان نگهداری آنها نیز بستگی داشته باشد. در اینجا حالت اول را بکار برده و سرجمع مخارج نگهداری و تخلیه کالا از انبار و هر مقدار سودی که از فروش یا مصرف کالای مازاد حاصل میشود باh نشان میدهیم در واقع h مجموع هزینههای نگهداری و خارج ساختن کالا از انبار منهای بهای کسب شده از فروش آنها در صورت وجود است، لذا ممکن است h (هزینه نگهداری) صفر باشد.
1-7 مدل مسئله تخصیص سهم به تامینکننده
در این پایاننامه بهکمک نمادها و اهداف ذکر شده برگرفته از منبع [21] ، یک مدل چندهدفه فرض میکنیم که در آن هزینههای خرید، واحدهای مرجوع شده و تاخیر در تحویل واحدها مینیمم شود، درحالیکه نمره کل بهدست آمده از فرایند ارزیابی تامینکننده کالا به حداکثر برسد.
1-7-1 نشانهها و نمادها
i: فهرست تامین کنندگان
j: فهرست محصولات
P_ij: قیمت محصول jارائه شده توسط تامینکننده i که به مقدار سفارش بستگی دارد
W_i : نمره ارزیابی تامینکننده i که توسط کمپانی خریدار ارائه میشود
q_ij: درصد اقلام مرجوع شده که جنس j توسط تامینکننده i مرجوع شده
t_ij : درصد اقلام دیر تحویل شده از محصول j توسط تامینکننده i
Q_j: ماکزیمال درصد قابل قبول از اقلام مرجوع شده از محصول j
T_j: ماکزیمال درصد قابل قبول از اقلامی که دیر تحویل میشوند از محصول j
t: افق (دوره) برنامهریزی
D_j: متغیر تصادفی تقاضا از محصول j درافق برنامهریزی
f (D_j): تابع توزیع احتمال D_j
h_j : هزینه نگهداری به ازای هر واحد از محصول j که در انتهای افق برنامهریزی باقی میماند
π_j : هزینه جریمه به ازای هر واحد تقاضای از دست رفته از محصول j
λ_j : نرخ تقاضای محصول j
x_ijmin : مینیمال مقدار از محصول j که باید به تامینکننده i ارائه شود
x_ijmax : ماکزیمال مقدار از محصول j که باید به تامینکننده i ارائه شود
x_ij : تعداد سفارش محصول j اختصاص یافته به تامینکننده i
1-7-2 مدل پیشنهادی مسئله
با توجه به مطالبی که در ارتباط با سیستمهای مختلف و معیارهای تصمیم در آنها ارائه شد، مدل پیشنهادی ما چهار تابع هدف متفاوت دارد:
بهحداقل رساندن هزینه عملیاتی کل شامل هزینههای خرید، نگهداری در انبار و کمبودکالا.
بهحداقل رساندن کل واحدهای مرجوع شده.
بهحداقل رساندن کل واحدهایی که با تاخیر تحویل داده میشوند.
حداکثر کردن نمرات ارزیابی کل.
توابع هدف بیان شده میتواند بهجای روابط (1-1) تا (1-4) قرار گیرد.
MinZ_1=∑_i▒∑_j▒〖P_ij x_ij 〗+∑_j▒〖h_j ∑_(D_j=0)^∑_i▒x_ij ▒〖(∑_i▒x_ij 〗-D_j)f (D_j ) 〗+∑_j▒〖π_j ∑_(D_j=∑_i▒Xij)^∞▒( D_j-∑_i▒x_ij ) f(D_j)〗 (1-1)
Min Z_2 = ∑_i▒∑_j▒〖q_ij x_ij 〗 (2-1)
Min Z_3 =∑_j▒∑_i▒〖t_ij x_ij 〗 (3-1)
MaxZ_4=∑_j▒∑_i▒〖W_i x_ij 〗 (4-1)
subject to:
∑_i▒∑_j▒q_ij x_ij≤ Q_j ∑_i▒x_ij ∀j (5-1)
∑_i▒∑_j▒t_ij x_ij≤ T_j ∑_j▒x_ij ∀j (6-1)
x_ijmin≤x_ij≤x_ijmax ∀j,i (7-1)
تابع هدف (1-1)
معادله (1-1) شامل سه قسمت است. قسمت اول∑_i▒∑_j▒〖p_ij x_ij 〗 اشاره دارد به هزینه خرید کل، که مجموع قیمت هر محصول، ضربدر اندازه سفارش از هر محصول تخصیص داده شده به هر تامین کننده میباشد. قسمت دوم h_j ∑_(D_j=0)^∑_i▒x_ij ▒〖(∑_i▒x_ij 〗-D_j)f (D_j ) اشاره دارد به هزینهی کل نگهداری هر محصول j که در آن h_j هزینه نگهداری هر واحد کالا و∑_(D_j=0)^∑_i▒x_ij ▒〖(∑_i▒x_ij 〗-D_j)f (D_j ) باقیماندهی مورد انتظار در انتهای افق برنامهریزی است که تا زمانیکه ∑_i▒x_ij ≤ D_j ، غیرصفر است (D_j متغیر تصادفی تقاضای محصول j درافق برنامه ریزی است). قسمت سوم π_j ∑_(D_j=∑_i▒x_ij )^∞▒( D_j-∑_i▒x_ij ) f (D_j) به هزینه کل کمبود کالا اشاره دارد، که π_j هزینهی کمبود هر واحد کالا و∑_(D_j=∑_i▒Xij)^∞▒( D_j-∑_i▒x_ij ) مقدار کالایی است که با کمبود مواجه شده است.
متغیر تصادفی تقاضای محصول j دارای توزیع پواسون در نظر گرفته میشود. لذا فرض بر آن است که تقاضای محصولات مختلف مستقل است. با توجه به نمادهای فوق f (D_j) میتواند توسط رابطه (1-8) بهدست آید
f (D_j) = (e^(-λ_j t) 〖〖(λ〗_j t)〗^(D_j ))/(D_j !) . (8-1)
رابطه بین قیمت هر محصول پیشنهاد شده توسط هر تامینکننده، p_ij و مقدار سفارش مربوط به آن، x_ij را بهصورت رابطه (1-9)، خطی فرض میکنیم که پارامترهای a_ij و b_ij نشاندهنده عرض از مبدا و شیب منحنی قیمت- مقدار میباشد. (مانند شکل 1-1):
p_ij=a_ij-b_ij x_ij . (9-1)

شکل 1-1: منحنی قیمت-مقدار
تابع هدف (1-2)
شامل فرایندهایی است که درگیر بازگشت یا دریافت محصولات مرجوع شده به هر دلیل می باشند. فرایند مذکور میتواند قابل تعمیم به فرایندهای پشتیبانی از مشتریان پس از تحویل نیز باشد. بهصورت جزئیتر فرایند برگشت شامل موارد بازگرداندن مواد اولیه (به تامین کننده) و دریافت رسید محصول برگشتی (از مشتری) شامل کالای معیوب، مازاد و منقضی میباشد.
محدودیتها
محدودیت (1-5) تضمین میکند که تعداد کل واحدهای مرجوع شده از هر محصول کمتر از حداکثر سطح مجاز است. محدودیت (1-6 ) نشاندهنده آناست که تعداد کل اقلام دیرتحویلشده از هر محصول پایینتر از حداکثر سطح مجاز متناظر است. محدودیت (1-7) تضمین میکند که مقدار سفارش محصول j اختصاص یافته به تامینکننده i بین مقدار مینیمم و ماکزیمم متناظر قرار میگیرد.

1-7-3 روش حل مدل پیشنهادی
برای حل این مساله تصمیمگیری چند هدفه از روش متریک L_p، جواب ایدهآل مدل را بهدست آورده (جواب ایدهآل با توجه به هر تابع هدف از مدل اصلی با توجه به محدودیتهای (1-5) تا (1-7) بهدست میآید) و سپس با ترکیب آنها به یک تابع هدف که در (1-10) آمده است، سعی میشود نزدیکترین نقطه از فضای جواب به نقطهی ایدهآل یافت شود. توابع متفاوتی برای اندازهگیری فاصله در روش L_p تعریف میشود. ما از تعریف زیر استفاده میکنیم.
L_p={∑_(j=1)^k▒〖b_j [(f_j (x)-f_j (x_j^* ))/(f_j (x_j^* ) )]^p 〗}^(1/p)
که برای p=1 و k=4 رابطهی (1-10) بهدست میآید
z =b_1 [(z_1-z_1^*)/(z_1^* )] +b_2 [(z_2-z_2^*)/(z_2^* )] +b_3 [(z_3-z_3^*)/(z_3^* )] +b_4 [〖z_4^*-z〗_4/(z_4^* )].(10-1)
در معادله (1-10)، b_1 تا b_4 وزنهای مهمی هستند که با توجه به اهداف تصمیمگیرنده انتخاب میشوند. با توجه به غیرخطی بودن z_1 ، z نیز غیرخطی و شامل متغیرهای صحیح است. بنابراین یک مساله برنامهریزی صحیح غیرخطی NIP14 خواهیم داشت، که با روشهای متاهیوریستیک GA (الگوریتم ژنتیک) و SA (شبیه سازی گرم وسپس سرد کردن) آنرا حل میکنیم.

فصل دوم
استفاده از الگوریتم ژنتیک و الگوریتم شبیهسازی تبرید برای حل مدل پیشنهادی
متاهیوریستیک
محاسبه جواب بهینه برای اکثر مسائل بهینهسازی که در خیلی از زمینههای کاربردی و عملی مشاهده میگردند،کاری دشوار و سخت است. درعمل، معمولا به جوابهای “خوب” که از الگوریتمهای هیوریستیک یا متاهیوریستیک (فراابتکاری) بهدست میآید، اکتفا میگردد. روشهای فراابتکاری جوابهای “قابل قبول” در زمان معقول را برای مسائل پیچیده و سخت در زمینههای مهندسی و علوم ارائه مینمایند.
چه موقع از متاهیوریستیکها استفاده میشود؟
پیچیدگی یک مساله، زمان حل، ساختار دادههای ورودی و اندازه مساله شاخصهایی برای بررسی سختی یک مساله بهحساب میآید. استفاده از متاهیوریستیکها برای حل مسائل ساده، کاری بیهوده است. اگر یک مساله قابل تجزیه به مسائل کلاسیک یا مسالهای که حل شده است، باشد، میتوان با مراجعه به پیشینه تحقیق، الگوریتم مناسبی برای آن پیدا کرد. دسته ای از مسائلی که متا هیوریستیکها برای حل آن مناسب میباشند، بهصورت زیر طبقهبندی میشود:
یک مساله ساده (طبقه p) با ابعاد خیلی بزرگ. در این مورد، الگوریتمهای چندجمله ای دقیق برای حل مساله وجود دارند، ولی بهدلیل ابعاد بزرگ، خیلی پر هزینه می باشند.
برای حل برخی مسائل از ردهی انپی-سخت15 استفاده میشوند.
قادر به بهینه سازی مسائل با توابع هدف یا محدودیتهای زمانبر میباشند.
2-1 الگوریتم ژنتیک 16(GA)
استفاده از GA بهعنوان یک عضو از خانوادهی الگوریتمهای تکاملی یک راهحل مسائل NIP است که بیشتر اوقات با یک رشته اعداد دودویی یا حقیقی به نام کروموزم نشان داده میشود. هرکروموزم دارای یک مقدار تناسب17 است که معمولا به مقدار تابع هدف جواب مربوط است. در ابتدا در این الگوریتم یک جمعیت از جواب بهطور تصادفی تولید میشود، پس از آن برای تولید جوابهای جدید بهنام فرزندان تعدادی جواب با توجه به اعمال قانون تولید مثل انتخاب میشوند. جفتگیری از والدین با استفاده از اپراتورهایGA بهنام تقاطع18 و جهش19 انجام میشود تا زمانیکه قانون توقف صدق کند (برای مثال گذشت تعداد معینی از تکرارها).
2-1-1 مزایای الگوریتم ژنتیک
ذاتا موازی است، یعنی جمعیتی از نقاط بهجای یک نقطه مورد جستجو قرارمیگیرد.
با متغیرهای پیوسته و گسسته کار میکند.
نیاز به محاسبه مشتق تابع ندارد چون برای پیدا کردن جهت جستجو انتخاب تصادفی انجام میدهد.
قادر به بهینه سازی مسائل با متغیرهای زیاد است.
با متغیرهای کدشده کار میکند وکدبندی سرعت همگرایی الگوریتم را افزایش میدهد.
این الگوریتم از قوانین انتقال احتمالی بهجای قوانین انتقال قطعی استفاده میکند بدین معنا که حرکت آن در هر نقطه از الگوریتم کاملا احتمالی بوده و براساس قطعیت صورت نمیگیرد. این امر از مزایای مهم این روش بوده و از افتادن در کمینه محلی جلوگیری میکند. البته میزان احتمال بهگونهای است که احتمال حرکت به سوی هدف مساله بیشتر از احتمال حرکت به سمت مخالف جواب میباشد.
برای حل برخی مسائل از ردهی انپی-سخت نیز استفاده میشود.
قبل از دادن یک طرح کلی پیشنهاد اکتشافی مبتنی بر GA برخی از نمادهای اضافی را معرفی میکنیم.
ppsz: سایز جمعیت جواب که در طول اجرای الگوریتم ثابت است.
maxit: تعداد تکرار از پیش تعیین شده.
Pc: نرخ تقاطع (باکدام احتمال یک کروموزم ازهر نسل برای انجام تقاطع انتخاب شده است).
Pm: نرخ جهش (باکدام احتمال یک بیت از یک رشته جواب (یا یک ژن ازیک کروموزم) به منظور جهش انتخاب شده است).
ftfn: مقدار تابع تناسب که فرض شده است با مقدار تابع هدف برابر باشد.
2-1-2 طرح کلی از GA پیشنهادی
مرحله 1: مقداردهی اولیه ppszو maxit و Pc و Pmو ftfn
مرحله 2: تولید تصادفی جمعیت اولیه با توجه به ارزش ppsz
مرحله 3: تکرار تا زمانیکه maxit
مرحله 3-1: استفاده ازعملگر تولید مثل، انتخاب مجموعهای از جوابهای واجد شرایط با استفاده از قوانین چرخرولت20 و ساخت جمعیت جدید.
مرحله3-2 : انتخاب کروموزمهای والدین از جمعیت جدید بااحتمالPc
مرحله3-3: تقاطع (پیوند)
الف: شکل دادن جفتهای والدین، در میان کروموزمهای والدین
ب : بهکاربردن عملگر تقاطع تکنقطه ای برای تولید کروموزمهای فرزند از دو کروموزم والدین اولیه
پ: جایگزینی هر کروموزم والدین اولیه در جمعیت با کروموزمهای فرزند
مرحله 3-4 : بهکاربردن عملگر جهش در جمعیت با احتمال Pm
مرحله 3-5: محاسبه ftfn برای هر کروموزم و ذخیره بهترین مقدار در bv(best value) ، اگر از قبلی بهتر باشد.
مرحله 4: چاپ bv
در شکل (2-1) روند کلی الگوریتم ژنتیک نمایش دادهشده است.
شکل 2-1: روند کلی الگوریتم ژنتیک
در ادامه گامبهگام با این روند آشنا میشویم.
2-1-2-1 تعیین تابع تناسب
یکی از مزایای روش الگوریتم ژنتیک ایناست که فقط با مقدار تابع سرو کار دارد و نیازی به دانستن رابطه بین متغیرها و تابع نیست لذا برای انتخاب تابع نیازی به دانستن معادله دقیق آن نداریم و فقط اگر روشی بیابیم که بهوسیله وارد کردن متغیرهای مساله مقدار عددی تابع را بتوانیم پیدا کنیم کفایت میکند.
مثلا اگر بتوانیم بهوسیله روشی از روشهای ترسیمی در مورد مسالهای خاص به ازای متغیرهای مختلف مقدار تابع را پیدا کنیم یا اینکه اگر نرم افزاری برای تحلیل یک مساله مهندسی وجود دارد که متغیرها را از ما میگیرد و جواب را به ما میدهد میتوانیم بدون دانستن اتفاقاتی که در طی آن به جواب میرسیم، فقط با دانستن مقدار آن به ازای متغیرهای ورودی مقدار بهین تابع را بهوسیله الگوریتم ژنتیک بهدست آوریم.
اگر تابع هدف ما دارای قیود طراحی بود که معمولا هم چنین است میتوانیم به وسیله تابع جریمه، مجموعه قیود مساوی و نامساوی را به یک رابطه تبدیل کنیم و به بهینه کردن رابطه مورد نظر بپردازیم. برای مثال اگر برای مسالهای سه قید نامساوی و یک قید مساوی مانند زیر داشته باشیم:
1/6 x_1^2+1/6 x_1^2≤1
x_1≥0
x_2≥0
5x_1+3x_2=8
میتوان آنرا به صورت استاندارد زیر نوشت :
g_1 (x)=1/6 x_1^2+1/6 x_1^2-1≤0
g_2 (x)=-x_1≤0
g_3 (x)=-x_2≤0
g_4 (x)=5x_1+3x_2-8=0
بردار V را بهصورت زیر تعریف میکنیم:
V= max [0,g_1 (x), g_2 (x), g_3 (x), abs(g_4 (x))]
و تابع جریمه را بهصورت زیر تعریف میکنیم:
φ=f_0+RV
که در آن φ تابع هدف نامقید بوده و R ضریب جریمه است که انتخاب آن به عهده طراح میباشد و بردار V ماکزیمم نقض قید توسط متغیرها میباشد و از این پس تابع φکه تابع پنالتی ما میباشد به عنوان تابع هزینه بهینه میگردد.
2-1-2-2 تعیین طول کروموزوم
کروموزوم یک رشته از 0 و 1 است که مقدار n متغیر تابع هدف ما را دربردارد. مثلا اگر طول هر متغیر را α بیت در نظر بگیریم طول کل کروموزوم برابر است با: L=n*α (به هر بیت از کروموزوم یک ژن گویند).
میتوان برای تعیین α از رابطه زیر استفاده کرد: α=[(log⁡(b-a)*〖10〗^m )+1] که m دقت متغیرها بر حسب تعداد رقم اعشار و a حد پایین وb حد بالای متغیرها در مبنای 10 میباشد.
در جاهایی که لازم است برای اعداد منفی باید یک بیت به علامت آنها اختصاص داد و در مورد اعداد اعشاری باید ابتدا آنها را با ضرب در یک عدد به عدد صحیح تبدیل کرده و سپس به باینری تبدیل کرد.
2-1-2-3 تولید جمعیت اولیه
پس از تعین طول کروموزوم باید آنرا به طور اتفاقی از 0 و 1 پرکنیم. اینکار بهوسیله دستور زیر انجام میشود:
L= round (rand)
با توجه به اینکه تعداد ترکیبهای جایگیری 0 و 1 برای کروموزوم به طول L برابر است با لذا بهتر است تعداد کروموزومهای یک جمعیت را، از تعداد ترکیبهای نشستن صفر و یکها در یک کروموزوم بیشتر نگیریم، چرا که در بعضی از کروموزومها به ناچار تکرار میگردند.
مقدار بهینه تعداد کروموزومها در یک جمعیت بهطور تقریبی از رابطه n_pop=1.65*2^(0.21 L) بهدست میآید که در آن L، طول رشته است.
فرض کنید برای یک تابع دومتغیره5 کروموزوم با تعداد 10ژن در هرکدام انتخاب کردهایم. مانند جدول (2-1)

جدول 2-1: تشکیل کروموزم
x_2x_1کروموزم ش 10011100101ادامه جدول 2-1: تشکیل کروموزمx_2x_1کروموزم ش20111100 111کروموزم ش30010100110کروموزم ش41101011000کروموزم ش50101011010
در جدول (2-1)، 5 بیت اول هر کروموزوم، مربوط به مقدار باینری x_1 و 5 بیت دوم هر کروموزوم مربوط به مقدار باینریx_2 میباشد.
2-2-2-4 تبدیل کروموزمها به اعدادی در بازهی دامنهی همان متغیرها
اگر محدوده متغیرx_1 برابر است با: ≤ b x_1 ≥ a باید 0 و 1 های کروموزوم را به اعدادی در بازهی مورد نظر تبدیل کنیم. فرض کنید یک تکه ژنی از کروموزومی به طول L را که متعلق بهx_1 است میخواهیم به بازه 〖a≤x〗_1≤b تبدیل کنیم. اگر ∝=5. کوچکترین عددی که با 5 ژن در مبنای 2 میتوان ساخت بهصورت زیر است:
00000

کوچکترین عدد از بردن یک تکه کروموزوم ژنی به مبنای 10 برابر است با:
u=0*2^0+0*2^1+0*2^2+…+0*2^(∝-1)=0
11111بزرگترین عددی که در 5 ژن از یک کروموزوم میتوان داشت برابر است با:
و با بردن بزرگترین کروموزوم ∝ژنی به مبنای 10 داریم:
u=1*2^0+1*2^1+1*2^2+…+1*2^(∝-1)=2^∝-1
تمامی جایگشتهای 0 و 1 در یک بایت ∝ بیتی میتوانند اعدادی بین 0 تا 2^∝-1 در مبنای 10 تولید کند. در حالیکه مجموعه x_1 ما اعدادی در بازه a تا b میخواهد. تبدیل این دو مجموعه بهوسیله نگاشت انجام میشود. نگاشت خطی که بازهها را بههم تبدیل می کند. (u یک عدد در مبنای 10 است).
[0,2^∝-1] □(→┴(r=c_1+c_2 u) ) [a,b]
u=0 , r=a →c_1=a
u=2^l-1 , r=b →c_2=((b-a))/((2^∝-1) )
⇒r=a+((b-a)/(2^∝-1))*u
بههمین ترتیب میتوانیم برای x_2با دامنه مختص به خودش نگاشتی بنویسیم و اعداد باینری هر متغیر را به مقداری در مبنای 10 در بازه مجاز همان متغیر تبدیل کنیم.
جدول2-2: مثالی از تبدیل کد گذاری
متغیر x_1 متغیر x_2 کروموزم ش 10110011101مقداردرمبنای 10 623
2-1-2-5 بهدست آوردن مقدار تابع تناسب
مقدار متغیرها را در تابع هدف قرار داده و مقدار تابع را به ازای هر بردار x=[x_1, x_2,…, x_n] بهدست میآوریم بدین ترتیب برای مجموعه 5 کروموزومی و تابع هدف زیر داریم:
f(x)=x_1^2+x_2^2+3x_1 x_2
جدول2-3: محاسبه تابع بهینه
کروموزم هامتغیر x_1به صورت باینریمتغیر x_2 به صورت باینریx_1x_2f(x)کروموزمش1001110010128202864کروموزم ش2011110011130284204کروموزم ش 3101010011021121341کروموزم ش 41101011000113229کروموزم ش 5010101101110271639
2-1-2-6 محاسبه درصد برازندگی
درصد برازندگی هر کروموزوم را حساب میکنیم مثلا برای یک تابع دو متغیره درصد برازندگی برابر است با:
100* (جمع تمام برازندگیها / مقدار تابع به ازای )
که برای مجموعه 6 کروموزمی بالا و f(x)=x_1^2+x_2^2+3x_1 x_2 به صورت جدول (2-4) درمیآید:

در این سایت فقط تکه هایی از این مطلب(به صورت کاملا تصادفی و به صورت نمونه) با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود-این مطالب صرفا برای دمو می باشد

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

جدول2-4: محاسبه درصد برازندگی
کروموزم هامتغیر x_1 به صورت باینریمتغیر x_2به صورت باینریf(x)درصد برازندگیکروموزم ش 10011100101286428%کروموزم ش 2011110011142041/41%
ادامه جدول 2-4کروموزم هامتغیر x_1 به صورت باینریمتغیر x_2به صورت باینریf(x)درصد برازندگیکروموزم ش 3101010011013411/13%کروموزم ش 411010110002292/2%کروموزم ش 50101011011163916%جمع: 10227100%

دسته بندی : پایان نامه

دیدگاهتان را بنویسید