دانلود پایان نامه

از نوع#/D/ cap/ // / میباشد.

3-2- تعریف مساله
فرض کنید I نشان دهنده مجموعه مکانهای بالقوه تسهیلات و J معرف مجموعه مشتریان می‌باشند که تقاضا هر مشتری j∈J یک متغیر تصادفی باینری (صفر ویک) است که ما آن را با 〖 λ〗_jنشان می‌دهیم. همچنین فرض می شود که 〖 λ〗_jاز یک توزیع احتمال برنولی با پارامتر〖 p〗_jتبعیت میکند. حال می‌توان 〖 λ〗_j را بصورت زیر نمایش داد:
(3-1)
(jϵJ).
〖 λ〗_j={█(1 p_(j )@■(0& 1-p_j ))┤
پس،توزیع احتمال برنولی را می توان نشان داد:
(3-2)
(jϵJ).
P_x (x=λ_j)=p_j^(〖 λ〗_j )⁡〖(1-p_j )^(〖 1-λ〗_j ) 〗

3-2-1- فرضیات مساله
فرضیات مساله ارائه شده در این تحقیق عبارتند از:
فضای جواب گسسته است و یک مجموعه محدودی از مکانهای بالقوه برای تسهیلات وجود دارد.
یک حداقل ظرفیتی برای تسهیلات وجود دارد.
اگر یک تسهیلی مستقر شد، باید به اندازه حداقل ظرفیت خود به مشتریان سرویس دهد.
هر تسهیل دارای حداکثر ظرفیتی میباشد و می‌تواند به اندازه ظرفیتاش به مشتریان سرویس دهد.
ظرفیت محدود تاثیری بر تعداد مشتریانی که به یک تسهیل تخصیص می‌یابند، ندارد. این به آن معناست که به هر تسهیل بیشتر از ظرفیتاش، مشتری تخصیص یابد.
دو نوع استراتژی مختلف برای تسهیلاتی که بیشتر از ظرفیتشان مشتری دارند، رخ میدهد.
ممکن است تمامی تقاضای مشتریان را برآورد نشود.
ما در این تحقیق برای تصمیم گیری در مورد تقاضای مشتریان دو استراتژی متفاوتی را در نظر می‌گیریم. ما فرض میکنیم که یکی از این دو استراتژی برای تامین تقاضای مشتریان اتفاق میافتد. این دو استراتژی زمانی مطرح میشود که تعداد مشتریان تخصیص داده شده به هر تسهیل بیشتر از حداکثر ظرفیت‌اش باشد. هدف از ارائه استراتژیها این است که اگر تعداد تقاضای مازاد برای هر تسهیل زیاد باشد به نفع سازمان است که در هر صورتی تمامی تقاضای مشتریان را تامین کند که این تقاضای اضافی از طریق منابع بیرون از سازمان تامین میشود و اما اگر تعداد تقاضای مازاد کم باشد از نظر هزینهی باصرفه است که برآورده نشود. حال در اولین استراتژی، تعداد تقاضای مازاد برای هر تسهیل به منابع بیرونی تحویل داده می‌شود. در این استراتژی تمامی تقاضاهای مشتری تامین می‌شود. در استراتژی دوم میزان تقاضای مازاد برای هر تسهیل تامین نمی‌شود یعنی هر تسهیل حداکثر به اندازه ظرفیت‌اش می‌تواند جوابگوی تقاضا باشد.
در این تحقیق، ما یک مسئله مکانیابی- تخصیص در فضای گسسته و تسهیلات با ظرفیت محدود در نظر میگیریمکه تقاضای مشتریان دارای توزیع احتمال برنولی است. هدف از ارائه مدل پیشنهادی تعیین بهترین مکان برای استقرار تسهیلات و تخصیص تقاضای مشتریان به تسهیلاتی که مستقر شده‌اند می‌باشد. تابع هدف این مساله شامل مینیمم کردن1) هزینه ثابت برای استقرار تسهیلات 2) هزینه کل انتظاری تخصیص مشتریان به تسهیلات 3) هزینه کل انتظاری برآورد کردن تقاضا 4) هزینه کل انتظاری تقاضا‌های تامین نشده مشتریان میباشد.

3-2-2- پارامترهای مساله
پارامترهای مورد استفاده در مدل پیشنهادی در ذیل معرفی شده است:
f_i هزینه ثابت برای استقرار تسهیل i
〖 l〗_iحداقل تعداد مشتریان که به تسهیل مستقر شده iباید تخصیص یابند
k_i حداکثر تعداد مشتریان که به تسهیل مستقر شده iمی‌توانند تخصیص یابند
c_ij هزینه سرویس تسهیل i به مشتری j
g_i هزینه هر واحد منابع بیرون سپار برای هر تسهیل i
h_i هزینه هر واحد تقاضای برآورد نشده برای هر تسهیل i
v_i هزینه راه اندازی برای منابع بیرون سپار تسهیل i
M^∞ یک عدد مثبت بزرگ
در این تحقیق، ما یک مسئله مکانیابی- تخصیص که تقاضای مشتریان احتمالی بوده و از توزیع احتمال برنولی تبعیت می‌کند را معرفی می‌کنیم. هر تسهیل دارای ظرفیت بوده و در صورت استقرار تسهیل حداقل به اندازه 〖 l〗_i مشتری به آن تخصیص می‌یابد. در این جا همه مشتریان تخصیص یافته به تسهیلات دارای تقاضا نمی‌باشند، یعنی یک تعداد از مشتریان دارای تقاضا نمی‌باشند.〖 J〗_jمجموعه مشتریان تخصیص داده شده به تسهیلiمی‌باشد که〖 η〗_iمعرف تعداد مشتریانی که تقاضا داشته و به تسهیل i تخصیص می یابند، می‌باشد که میتوان بصورت〖 η〗_i=∑_jϵJ▒〖λ_j 〗نشان داد.

3-2-3- متغیر های تصمیم مساله
مسئله مکانبایی- تخصیص با تقاضای احتمالی برنولی که شامل استقرا مجموعهای از تسهیلات و تخصیص مشتریان به تسهلات مستقر شده میباشد. هدف از مدل، کمینه کردن جمع هزینه ثابت برای استقرار تسهیلات، هزینه سرویسدهی و دیگر هزینه پیشنهادی میباشد. برای فرمولبندی ریاضی مدل ما متغیر های تصمیم مورد نیاز را معرفی میکنیم، که مجموعه‌ی از این متغیرها شامل:

مطلب مرتبط :   پایان نامه رشته حقوق درباره : حقوق بشر

〖=x〗_ij

=〖 y〗_i

بنابراین، مدل اولیه میتوان بصورت زیر نشان داد:
Minf_i y_i+E_ξ(Service cost+ Outsourcing cost+ Unmet Demand cost)
(3-3)
s.t. ∑_(i∈I)▒〖x_ij=1,〗
∀ j∈J,
(3-4)
x_ij≤y_i,
∀ i∈I, j∈J,
(3-5)
〖 l〗_i y_i≤∑_(j∈J)▒〖λ_j x〗_ij ,
∀ i∈I,
(3-6)
y_i∈{0,1},
∀ i∈I,
(3-7)
x_ij∈{0,1},
∀ i∈I, j∈J.
(3-8)

در تابع هدف (3-3) جمع هزینه مستقر سازی هر تسهیل، هزینه سرویس‌دهی هر تسهیل به مشتریانی که تقاضا دارندو هزینه مربوط به استراتژی ها را کمینه میکند. محدودیت (3-4) نشان می‌دهد که هر مشتری تنها به یکی از تسهیلات تخصیص می‌یابد. محدودیت (3-5)تضمین می‌کند که تخصیص مشتریان به تسهیلاتی صورت می‌گیرد که که مستقر شده‌اند
. محدودیت (3-6) نشان می‌دهد که اگر تسهیلی مستقر شد باید به اندازه حداقل ظرفیت‌اش، مشتری به آن تخصیص داده شود. محدودیت های (3-7)و (3-8)نشان دهنده‌ای متغیرهای باینری (صفر ویک) است.

3-2-4- استراتژیهای موجود مساله
در قسمت ما به توضیح استراتژی های موجود میپردازیم. از آنجایی که تقاضای مشتریان احتمالی در نظر گرفته شده است، برای محاسبه ارزش انتظاری استراتژی های موجود ما نیاز به معرفی چند متغیر تصمیم دیگری داریم. z_i نشان دهنده تعداد مشتریان تخصیص داده شده به تسهیل i می باشد. حال متغیرهایz_iو 〖 η〗_i را می توان نشان داد:
(3-9)
(iϵI).
z_i=∑_jϵJ▒x_(ij ) ,
(3-10)
(iϵI).
〖 η〗_i=∑_jϵJ▒〖λ_jx_ij 〗 ,
واضح است توزیع احتمال 〖 η〗_i وابسته به مقدار واقعی از بردار x_ij برای j∈J و یا مجموعه از می‌باشد. این وابستگی را می توان بصورت زیر نشان داد:
(3-11)
(iϵI).
P_x [〖 η〗_i=s]=P_x [∑_jϵJ▒〖λ_j x_ij 〗]
با توجه به مطالب گفته شده می توانیم این توزیع احتمال را بصورت زیر دوباره نویسی کنیم.
(3-12)
(iϵI).
P_x [η_i=s]=∑_(s⊂J_j:|S|=s)▒∏_(j∈S)▒〖p_j ∏_(j∈J_jS)▒(1-p_j ) 〗

حال، به معرفی دو استراتژی موجود در این تحقیق میپردازیم. این استراتژی‌ها زمانی برای هر تسهیل اتفاق می‌افتد که تعداد مشتریانی تخصیص داده شده به آن بیشتر از k_i باشد.این دو استراتژی در مقابل هم هستند، یعنی یکی از این استراتژی برای هر تسهیل که دارای مشتریان بیشتر از ظرفیتشان دارند، اتفاق میافتد.
در استراتژی اول اگر تعداد تقاضا برای هر تسهیل از k_i بیشتر باشد، تعداد مشتری باقیمانده η_i-k_i توسط منابع بیرون تامین می‌شود. بنابراین کل تقاضا برای تمامی مشتریان تامین میشود. برای تامین این تقاضاهای مازاد متحمل هزینه های برای واگذاری به منابع بیرون از سیستم میشود که وابسته به تسهیلی است که بیشتر از ظرفیت‌اش مشتری داشته باشد(Outsourcing).

دراستراتژی دوم تقاضای مازاد برآورد نمی‌شود و هر تسهیل دقیقاً به اندازه ظرفیت خودش میزان تقاضا مشتریان را تامین می‌کند. بنابراین همه تقاضای تخصیص داده شده به تسهیلات در این استراتژی برآورده نمی‌شود در حالی که بخشی از آن تامین میشود. در این صورت ما متقبل هزینه فروش از دست رفته می شویم که وابسته به تسهیلی است که دارای تقاضای مازاد میباشد(Unmet Demand).
با توجه به مطالب گفته شده برای محاسبه هزینه استراتژیهای موجود به محاسبه ارزش انتظاری این استراتژیها میپردازیم.
E_ξ(Service cost+ Outsourcing cost+ unmet demand cost)
= E_ξ(Service cost) + E_ξ(Outsourcing cost) + E_ξ(Unmet demand cost).
از آنجای که گفته شده، به آن دسته از مشتریان تخصیص داده شده به تسهیلات مستقر شده سرویس داده میشود، که دارای تقاضا باشند. به عبارتی، هزینه انتظاری سرویسدهی بصورت زیر میباشد.
E_ξ(Service cost) =c_ij p_j x_ij
(3-13)

بعلاوه، ارزش انتظاری برای هزینه منابع بیرون سپار و هزینه تقاضای برآورد نشده را نشان می دهیم. با در نظر گیری مقادیر شدنی قابل شمارش از 〖 η〗_i:
〖 E〗_ξ (Outsourcing cost)
=∑_iϵI▒[∑_(s=0)^(z_i)▒〖P_x [η_i=s]×E_ξ [Outsourcing cost|η_i=s]+ v_i 〗]
=∑_iϵI▒[g_i ∑_(s=k_i+1)^(z_i)▒〖P_x [η_i=s](s-k_i )+v_i 〗] ,
(3-14)

E_ξ (Unmet demand cost)
=∑_iϵI▒∑_(s=0)^(z_i)▒〖P_x [η_i=s]×〗 E_ξ [Unmet demand cost|η_i=s]
=∑_iϵI▒〖h_i ∑_(s=k_i+1)^(z_i)▒〖P_x [η_i=s](s-k_i ) 〗〗.
(3-15)

3-2-5- همگن سازی
از آنجای که، به کار بردن احتمالهای متفاوت برای مشتریان در حال کلی مشکل میباشد، در اینجا فرض شده که تمامی مشتریان دارای احتمال مشابه ای باشند (p_j=p ∀ j∈J). بنابراین، η_i دارای توزیع احتمال دوجملهای با پارامترهای t و p میباشد، که در اینجا t=z_i است، توزیع η_i وابسته به تعداد مشتریان تخصیص داده شده به تسهیل مستقر شده i که این مشتریان دارای تقاضا میباشند. با توجه به موارد گفته شده توزیع احتمال را میتوان بصورت زیر نشان داد.
b_ts=P_x [η_i=s]=(t¦s) p^s (1-p)^(t-s),
s=0,1,…t.
(3-16)

مطلب مرتبط :   مصادره اموال

با توجه به فرضات موجود در قسمت همگن سازی و فرمول بندی قبلی (15)-(13) ، حال هزینه انتظاری برای استراتژیهای پیشنهادی را بصورت زیر باز نویسی کرد.
∑_(i∈I)▒∑_(j∈J)▒〖pc_ij x_ij 〗+∑_(i∈I)▒[g_i ∑_(s=k_i+1)^(z_i)▒〖b_(z_i s) (s-k_i )+v_i 〗] +∑_(i∈I)▒h_i ∑_(s=k_i+1)^(z_i)▒〖b_(z_i s) (s-k_i ) 〗.
(3-17)

از آنجای که، حد بالا برای متغیر تصمیم z_i که از جمع شدنی مقادیر s میباشد، مشخص نیست. این امر سبب مشکلاتی در حل مسئله میشود، این مشکل را با تعریف متغیرهای جدید حل نمود. متغیرهای جدید بصورت زیر تعریف شده است.

=y_it

=q_i

حال، با تعریف متغیرهای جدید می توان محدودیت جدید برای مسئله که∑_(t=l_i)^(|J|)▒y_it ≤1 و y_it=1 اگر و فقط اگر 〖 z〗_i=t را تعریف کرد. از اینرو، تابع هدف (13) بصورت زیر باز نویسی کرد
∑_(i∈I)▒∑_(j∈J)▒〖pc_ij x_ij 〗+∑_(i∈I)▒∑_(t=l_i)^(|J|)▒y_it [g_i ∑_(s=k_i+1)^t▒〖b_ts (s-k_i )+v_i 〗]+∑_(i∈I)▒〖∑_(t=l_i)^(|J|)▒y_it h_i 〗 [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]
(3-18)

بنابراین، مدل پیشنهادی برای مسئله در حالت همگن میتوان بصورت زیر فرمولبندی کرد.
min┬⁡〖∑_(i∈I)▒∑_(t=l_i)^|J|▒〖f_i y_it 〗+∑_(i∈I)▒∑_(j∈J)▒〖pc_ij x_ij 〗+∑_(i∈I)▒〖q_i [∑_(t=l_i)^|J|▒y_it [g_i ∑_(s=k_i+1)^t▒〖b_ts (s-k_i )+v_i 〗]] 〗+∑_(i∈I)▒(1-q_i )[∑_(t=l_i)^(|J|)▒y_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]] 〗
(3-19)
s.t.

∑_(i∈I)▒〖x_ij=1〗,
∀ j∈J,
(3-20)
∑_(j∈J)▒〖λ_j x〗_ij =∑_(t=l_i)^(|J|)▒〖ty_it 〗,
∀ i∈I,
(3-21)
∑_(t=l_i)^(|J|)▒y_it ≤1 ,
∀ i∈I,
(3-22)
∑_(t=l_i)^(|J|)▒y_it [g_i ∑_(s=k_i+1)^t▒〖b_ts (s-k_i )+v_i 〗]-∑_(t=l_i)^(|J|)▒y_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]≥M^∞×(1-q_i ),
∀ i∈I,
(3-23)
∑_(t=l_i)^(|J|)▒y_it [g_i ∑_(s=
k_i+1)^t▒〖b_ts (s-k_i )+v_i 〗]-∑_(t=l_i)^(|J|)▒y_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]≤M^∞×q_i,
∀ i∈I,
(3-24)
y_it∈{0,1},
∀ i∈I,
l_i≤t≤|J|,
(3-25)
x_ij∈{0,1},
∀ i∈I,
j∈J,
(3-26)
〖 q〗_i∈{0,1},
∀ i∈I.
(3-27)

تابع هدف (3-19) شامل سه قسمت عمده است. قسمت اول هزینه مستقر سازی هر تسهیل بعلاوه هزینه سرویس‌دهی هر تسهیل به مشتریانی که تقاضا دارند را کمینه میکند. در قسمت دوم، هزینه تقاضای مشتریانی که توسط منابع بیرون سپار تامین میشود، را کمینه میکند و قسمت سوم در تابع هدف(3-19)، هزینه تقاضاهای مشتریان که برآورد نمی شود را کمینه می‌کند. محدودیت (3-20) نشان می‌دهد که هر مشتری تنها به یکی از تسهیلات تخصیص می‌یابد. محدودیت (3-21) تضمین میکند که هر تسهیلی که مستقر شده است به یک تعداد مشخصی از مشتریان سرویس میدهد. در محدودیت(3-22) نشان داده شده که به حداقل تعداد مشتریانی مشخصی که توسط تسهیلی که مستقر شده سرویس داده میشود. محدودیت (3-21) و (3-22) به طور همزمان تضمین میکنند که اگر تسهیلی مستقر شد باید به اندازه حداقل ظرفیتاش به آن مشتری تخصیص یابد. محدودیت (3-23) و (3-24) سبک و سنگینی بین استراتژیهای موجود رخ داده شده برای تسهیلی که مستقر شده و تعداد مشتریان تخصیص داده شده به آن بیشتر از ظرفیتاش باشد، را تضمین میکند. محدودیت های(3-25) – (3-27) نشان دهنده‌ای متغیرهای باینری (صفر ویک) هستند.

3-2-6- خطی سازی مدل ریاضی
از آنجای که تابع هدف (3-19) غیر خطی میباشد، این امر سبب بالا رفتن زمان حل مسئله میشود. برای بهتر کردن زمان حل ما تصمیم به خطی سازی این مدل پیشنهادی میگیریم. در واقع برای خطی کردن مدل ما نیاز به تعریف متغیرهای تصمیم جدید داریم و از آنجای که مسئله، یک مدل برنامهریزی عدد صحیح صفر و یک است ما متغیرهای جدید صفر و یک را بصورت زیر تعریف میکنیم.
w_it=y_it.q_i
∀ i,t
(3-28)
با توجه به معادله بالا، برای خطی سازی مدل ریاضی پبشنهادی دو محددیت خطی باید به طور همزمان به مسئله اضافه شود. این دو محدویت را میتوان بصورت زیر نشان داد.
w_it-y_it-q_i+1.5≥0
∀ i,t
(3-29)
〖1.5w〗_it-y_it-q_i≤0
∀ i,t
(3-30)
w_it∈{0,1}
∀ i,t
(3-31)
مطابق با تعریف متغیرهای جدید و محدودیت بالا، مدل خطی برای مسئله پیشنهادی را می توان بصورت زیر توسعه داد:
min┬⁡〖∑_(i∈I)▒∑_(t=l_i)^|J|▒〖f_i y_it 〗+∑_(i∈I)▒∑_(j∈J)▒〖pc_ij x_ij 〗+∑_(i∈I)▒[∑_(t=l_i)^|J|▒w_it [g_i ∑_(s=k_i+1)^t▒〖b_ts (s-k_i )+v_i 〗]] +∑_(i∈I)▒[∑_(t=l_i)^(|J|)▒y_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]-∑_(t=l_i)^(|J|)▒w_it h_i [∑_(s=k_i+1)^t▒〖b_ts (s-k_i ) 〗]] 〗
(3-32)
بطوریکه محدودیت های (3-20)- (3-27) و محدودیت های جدید (3-29)- (3-31).
با خطی سازی مدل

دسته بندی : علمی

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