ش معمول تاکنون به زمان نگهداری آنها نیز بستگی داشته باشد. در اینجا حالت اول را بکار برده و سرجمع مخارج نگهداری و تخلیه کالا از انبار و هر مقدار سودی که از فروش یا مصرف کالای مازاد حاصل میشود با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 تعیین تابع تناسب

دسته بندی : No category

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