فصل اول: مسایل مکان یابی میانه (تک وسیله ای)
1-1-مسایل جایابی با فاصله مجذور اقلیدوسی
1-2-مسایل جایابی با فاصله اقلیدوسی
1-1-مسایل جایابی با فاصله مجذور اقلیدوسی
مدل سازی و حل
خطوط تراز
مدل سازی و حل
اکنون مقیاس فاصله جدیدی به نام ”فاصله اقلیدوسی“ بیان می شود، اما به هر حال، بهتر است قبل از این که مساله با فاصله اقلیدوسی را مورد بررسی قرار دهیم، مساله جایابی تک تسهیلاتی را که در آن هزینه با مربع فاصله اقلیدوسی متناسب است بیان کنیم.
مطالعه مساله با فاصله مجذور (مرکز ثقل) بدین دلیل است که مسایل جایابی وجود دارند که در آن ها هزینه به جای این که به طور خطی افزایش یابد، بر حسب فاصله اقلیدوسی بین تسهیلات جدید و موجود به صورت درجه دوم افزایش می یابد.
مدل سازی و حل
مساله مرکز ثقل می تواند به صورت زیر فرمول بندی شود:
هر نقطه که رابطه 1-26 را می نیمم می کند باید شرایط زیر را برآورده کند:
مدل سازی و حل
با محاسبه مشتق جزیی رابطه 1-27 نسبت به x و y و مساوی صفر قرار دادن آن ها، حل یگانه زیر بدست می آید:
مدل سازی و حل
مختصه های وسیله جدید می تواند به صورت میانگین وزن دهی شده مختصه های x و y تسهیلات موجود تعبیر شوند و مختصه هایی هستند که رابطه 1-26 را می نیمم می کنند. شرایط رابطه 1-27 می تواند هم به صورت لازم و هم به صورت کافی برای یک می نیمم باشند.
مدل سازی و حل
مثال صفحه 27 کتاب
خطوط تراز
با دلایل بیان شده برای مساله متعامد، خطوط هم تراز برای مساله مرکز ثقل نیز مفید است.
خطوط هم تراز برای مساله مرکز ثقل به سادگی قابل دستیابی است.
خطوط هم تراز نشان داده شده در شکل 1-7 را برای دو مورد از مسایل مرکز ثقل در نظر بگیرید:
در مورد اول یک وسیله موجود است.
در مورد دوم، گردش مواد بین وسیله جدید و هر کدام از دو وسیله موجود برابر است.
خطوط تراز
در نتیجه، این نکته قابل توجه است که خطوط هم تراز دایره هایی هم مرکز با مرکز مکان بهینه خواهند بود.
شکل 1-7. خطوط هم تراز برای دو مساله مرکز ثقل ساده
(b)
(a)
خطوط تراز
حال وقتی که هر تعداد از تسهیلات موجود با گردش مواد نامساوی داریم، به نظر شما خطوط هم تراز شبیه چه چیزی خواهند بود؟
اگر گمان می کنید که خطوط هم تراز هنوز هم دایره هایی هم مرکز با مرکز مکان بهینه خواهد بود این مورد قابل ملاحظه است.
برای این که ببینید این امر درست است با در نظر گرفتن رابطه 1-27 می خواهیم مجموعه ای از همه نقاط (yوx) را تعیین کنیم، به طوری که:
خطوط تراز
جایی که k یک عدد ثابت است. در نتیجه با بسط مربع می بینیم:
و اکر w را به صورت زیر در نظر بگیریم:
خطوط تراز
رابطه 1-30 را بر W تقسیم کنید و رابطه های 1-29 و 1-30 را به کار بگیرید. می بینیم که:
با افزودن به طرفین رابطه 1-31 و ساده کردن، معادله یک دایره را بدست می آوریم:
خطوط تراز
با مرکز نقطه و شعاع:
بر مبنای این نتیجه، اگر نتوان وسیله جدید را در مکان بهینه قرار داد، باید با استفاده از خطوط هم تراز جاهای دیگر را ارزیابی کرد و باید همیشه آن نقطه ای استفاده شود که کم ترین فاصله مستقیم را با نقطه بهینه داشته باشد.
1-2-مسایل جایابی با فاصله اقلیدوسی
مدل سازی
روش حل کوهن
روش حل هندسی
رویه حل هذلولی (HAP)
ارتباط جواب بهینه متعامد و اقلیدوسی
خطوط تراز
روش اول رسم خطوط تراز
روش دوم رسم خطوط تراز
روش حل قیاسی
مدل سازی
در این بخش، مساله با فاصله اقلیدوسی به صورت زیر بیان می شود.
مساله با فاصله اقلیدوسی که به ”مساله اشتاینر-وبر“ شهرت دارد و ”مساله عمومی فرمات“ نیز نامیده می شود سابقه طولانی در تاریخ بهینه سازی دارد.
مدل سازی
در واقع، یک نسخه از مساله با m=3 و wi=1 و i=1,2,3 به طور محض به صورت یک مساله در هندسه ابتدا توسط فرمات در قرن هفدهم مطرح شد و به وسیله توریچلی قبل از 1940 حل گردید.
مساله به وسیله یک ریاضیدان سویسی به نام اشتاینر در قرن نوزدهم و به وسیله یک اقتصاددان آلمانی به نام وبر در اوایل قرن بیستم مورد مطالعه قرار گرفت.یک نتیجه دوگان مربوط به بحث دوگان مطرح شده در بخش قبل به وسیله ”فاسبندر“ در سال 1846 به دست آمد. تا این که ”کوهن“ در سال 1963 توانست مساله را بررسی کرده، به طور کامل آن را حل کند.
مدل سازی
مساله با فاصله اقلیدوسی در زمینه های مختلف روی می دهد.
رویکردی که فورا در حل مساله با فاصله اقلیدوسی به ذهن می آید این است که دوباره مشتق های جزیی رابطه 1-34 را محاسبه کرده، آن ها را برابر صفر قرار دهیم. با فرض (ai,bi) (x,y) و i=1,..,m مشتق های جزیی بدین گونه محاسبه هستند:
مدل سازی
مشتق ها:
مدل سازی
این نکته یادآوری می شود که اگر برای هر iی (ai,bi)=(x,y) آنگاه رابطه 1-35 و 1-36 تعریف نشده هستند. در نتیجه، می بینیم زمانی که مکان وسیله جدید –از لحاظ ریاضی- بر مکان یکی از تسهیلات موجود منطبق گردد مشکلات زیادی رخ می دهد.
اگر تضمینی وجود داشته باشد که هرگز مکان بهینه جدید با مکان یک وسیله موجود متشابه نیست آنگاه رابطه 1-35 و 1-36 هنوز شرط لازم و کافی برای یک مکان وسیله جدید با کم ترین هزینه دارا هستند.
متاسفانه چنین تضمینی وجود ندارد و در نتیجه، یک اصلاح برای رویکرد مشتق جزیی مورد نیاز است.
روش حل کوهن
اصلاحیه منسوب به کوهن بر مبنای R(x,y) دو سویه است و به صورت زیر تعریف می شود.
اگر
روش حل کوهن
و اگر (ak,bk)=(x,y) و k=1,…,m
جایی که
روش حل کوهن
R(x,y) برای همه نقاط در صفحه تعریف می شوند.
کوهن اثبات کرد که یک شرط لازم و کافی برای این که ( ) یک مکان با کمترین هزینه وسیله جدید باشد این است که .
در نتیجه، مکان برخی از تسهیلات موجود،( )، مکان بهینه وسیله جدید خواهد بود اگر و تنها اگر ( ) باشد.
(اگر این گمان برود که مکان بهینه وسیله جدید بر مکان یکی از تسهیلات موجود منطبق می گردد، باید محاسبه گردد.)
روش حل کوهن
اگر چه ما شرایط لازم و کافی را برای یک حل بهینه مساله فاصله اقلیدوسی داریم، ولی هنوز روشی برای تعیین محل ( ) رایه نکرده ایم. دو سویه که بعدا تحت عنوان مرکز ثقل اصلاح شده کوهن اشاره می شود می تواند دستکاری شده تا مبنایی را برای یک رویه محاسباتی جهت پیدا کردن مکان ( ) ایجاد کند. این نکته را در نظر بگیرید که با مساوی صفر قرار دادن رابطه (1-35)، عبارت زیر را بدست می آوریم:
روش حل کوهن
و اگر
آنگاه رابطه (1-37) می تواند به صورت زیر بیان شود
روش حل کوهن
به همین ترتیب با استفاده از رابطه (1-37) داریم
مادامی که تعریف شود، می توانیم رویه تکراری زیر را به کار بگیریم:
روش حل کوهن
اندیس k به شماره تکرار اشاره می کند. پس، یک مقدار شرع کننده ( ) برای تعیین ( ) مورد نیاز است. مقدار ( ) برای تعیین مقدار ( ) به کار می رود. و به همین ترتیب.
روش حل کوهن
رویه تکرار شونده ادامه پیدا خواهد کرد تا هیچ بهبود محسوسی در تخمین مکان بهینه برای وسیله جدید اتفاق نیافتد.
یا تا زمانی که مکانی پیدا شود که شرط مرکز ثقل اصلاح شده کوهن را ارضا کند.
رویه تکرار شونده تضمین می کند تا به مکان بهینه همگرا شود.
شرط همگرایی این مورد همانند نسخه های عمومی تر مساله Katz(1969)، Kuhn(1973) و Weiszfeld(1936) مورد بحث قرار گرفته است.
معمولا، حل مرکز ثقل به عنوان مقدار شروع کننده برای رویه تکرار شونده استفاده می شود.
روش حل کوهن
مثال صفحه 34 کتاب
روش حل هندسی
مثال قبلی می تواند به صورت هندسی نیز حل گردد. به ویژه، برای موردی که چهار وسیله موجود با وزن های برابر وجود دارند.
فرض کنید که چهار نقطه P1,P2,P3,P4 بتوانند در زوج های مرتب (A,B) و (C,D) قرار گیرند به طوری که خط های مستقیم AB و CD همان طور که در شکل (1-8) نشان داده شده، در نقطه x که بین A,B و بین C,D قرار دارد، همدیگر را قطع کنند.
نقطه x مکان بهینه وسیله جدید است.
روش حل هندسی
B
A
D
C
x
شکل 1-8. رویه حل گرافیکی برای مساله با فاصله اقلیدوسی
روش حل هندسی
برای موردی که سه وسیله موجود (A,B,C) با وزن های مساوی وجود دارند. اگر مثلث ABC تشکیل شده توسط تسهیلات موجود دارای زاویه های کمتر از 120 باشد، آنگاه مکان بهینه وسیله جدید نقطه ای است که خطوط مستقیم کشیده شده از آن به سمت هر کدام از تسهیلات موجود سه زاویه 120 تشکیل می دهد.
شکل (1-9) این وضعیت را نشان می دهد.
روش حل هندسی
شکل 1-9. جواب بهینه برای سه وسیله با وزن های برابر با زوایای کمتر از 120 درجه به روش هندسی
مکان بهینه
B
A
120
C
120
120
روش حل هندسی
اگر مثلث ABC شامل یک زاویه بزرگتر یا مساوی 120 درجه باشد، آنگاه مکان بهینه وسیله جدید در همان راس است که زاویه بزرگتر یا مساوی 120 درجه دارد است.
شکل (1-10) این حالت را نشان می دهد.
روش حل هندسی
B
A
C
شکل 1-10. جواب بهینه برای سه وسیله با وزن های برابر با یک زاویه بزرگتر از 120 درجه به روش هندسی
130
مکان بهینه
رویه تقریب هذلولی (AHP)
یک رویه حل تکرار شونده دیگر نیز برای حل مساله با فاصله اقلیدوسی بدون به کار بردن رویه مرکز ثقل اصلاح شده کوهن می تواند مورد استفاده قرار گیرد.
این رویه با آنچه که توسط رابطه (1-38) و (1-39) ارایه داده شده یکسان است به جز این که به صورت زیر تعریف می شود.
رویه تقریب هذلولی (AHP)
جایی که ε یک عدد ثابت اختیاری کوچک و مثبت است. این نکته را در نظر داشته باشید که رابطه (1-41) همیشه تعریف شده است. به علاوه وقتی که مقدار ε به صفر برسد، تابع جدید به تابع اصلی می رسد.
استفاده از رابطه (1-40) در رابطه های (1-38) و (1-39) یک رویه حل خیلی کارآمد ایجاد می کند.
این رویه HAP (رویه تقریب هذلولی) با جزییات بیش تر در فصل 2 بحث می شود.
رویه تقریب هذلولی (AHP)
نکته:
روش HAP می تواند برای حل مساله با فاصله متعامد نیز استفاده می شود.
رویه تقریب هذلولی (AHP)
مثال صفحه 37 کتاب
رویه تقریب هذلولی (AHP)
توجه:
البته، ما از HAP در حل مسایل جایابی با فاصله متعامد تک تسهیلاتی تا زمانی که حل بهینه بتواند به صورت مستقیم حل شود، استفاده نخواهیم کرد.
ارتباط جواب بهینه متعامد و اقلیدوسی
رویه تکرار شونده معمولا با استفاده از حل با فاصله متعامد یا حل مرکزی شروع می شود.
در برخی موارد، این حالت می تواند اتفاق بیافتد که حل با فاصله متعامد به طور موثری به حل بهینه با فاصله اقلیدوسی نزدیک است به طوری که جستوجوی بیش تر توجیه پذیر نیست.
با استفاده از نامساوی مثلث، حدهای بالا و پایین زیر برای حل با فاصله متعامد می تواند بدست آید.
ارتباط جواب بهینه متعامد و اقلیدوسی
که ، حل بهینه با فاصله اقلیدوسی
، حل بهینه با فاصله متعامد
، مقدار تابع هدف برای مساله با فاصله اقلیدوسی در نقطه
، برای مساله با فاصله متعامد
، برای مساله با فاصله متعامد
ارتباط جواب بهینه متعامد و اقلیدوسی
در واقع مفهوم نامساوی چپ رابطه فوق این است که مقدار تابع هدف اقلیدوسی بازای جواب بهینه خودش کمتر (بهتر) از مقدارش بازای جواب بهینه متعامد است که این نتیجه منطقی است.
توجه کنید که ، تابع هدف اقلیدوسی است.
ارتباط جواب بهینه متعامد و اقلیدوسی
مثال صفحه 38 کتاب
خطوط تراز
قبلا بر اهمیت خطوط هم تراز در بحث مساله با فاصله متعامد و مرکز ثقل تاکید شد.
متاسفانه روش های دقیقی برای ترسیم خطوط هم تراز برای مساله با فاصله اقلیدوسی به جز برای ساده ترین موارد با فقط یک یا دو وسیله همان طور که در شکل (1-11) نشان داده شده، در دسترس نیست.
خطوط تراز
خطوط هم تراز برای مورد (a) یک وسیله موجود
و برای مورد (b)، 2 وسیله موجود با گردش مواد مساوی با وسیله جدید، وجود دارند.
a
b
شکل1-11. خطوط هم تراز برای 2 نمونه از مسایل جایی با فاصله اقلیدوسی
روش اول رسم خطوط تراز
به دست آوردن تقریبی خطوط هم تراز با ارزیابی تابع هزینه با یک شبکه مستطیلی از نقاطی که محدوده مقادیر (x,y) مورد علاقه را پوشش می دهد، نسبتا ساده است.
خطوط هم تراز می توانند با درون یابی بین نقاط شبکه به دست آید یعنی کافی است برای نقاط تقاطع خطوط در شبکه مستطیلی، مقدار f(x,y) را حساب کنیم سپس آن هایی که مقدار یکسانی دارند را به هم وصل کنیم.
روش دوم رسم خطوط تراز
می توان با یک مقدار داده شده k به f(x,y) در رابطه (1-34) تخصیص داد و یک مقدار برای x انتخاب کرده و به دنبال دو مقدار yی باشیم که مقدار k را بدست می آورند.
این فرآیند برای مقادیر بعدی x ادامه پیدا می کنند تا خانواده ای از نقاط برای خط هم تراز با مقدار k بدست آید.
روش دوم رسم خطوط تراز
مثال صفحه 40 کتاب
روش حل قیاسی
علاوه بر حل تحلیلی مساله با فاصله اقلیدوسی، حل های قیاسی نیز بدست آمده است.
یک حل قیاس مکانیکی بسیار ساده در شکل (1-13) شرح داده شده است.
قیاس مکانیکی شامل یک تخته است که حاوی سوراخ هایی است که مکان تسهیلات موجود را به طور مناسب نشان می دهند.
m رشته وجود دارند که در یک گره مشترک به هم وصل هستند.
روش حل قیاسی
یک رشته از هر سوراخ عبور می کند یک وزنه به اندازه wi به انتهای هر یک از رشته ها متصل است.
نکته:
این کار انگیزه ای است برای استفاده از اصطلاح ”وزن“
به این سیستم اجازه داده می شود که به یک شرایط تعادل برسد.
بدون در نظر گرفتن اصطکاک، گره در محل بهینه وسیله جدید باقی می مانند.
یعنی محلی که گره در آن محل در حال تعادل قرار دارد مکان بهینه است.
روش حل قیاسی
قیاس مکانیکی برای ساختار دهی ساده بوده و تقریب های معقولانه ای برای مساله با فاصله اقلیدوسی فراهم می آورد.
حل به دست آمده می تواند به عنوان یک حل اولیه برای HAP یا رویه مرکز ثقل اصلاح شده کوهن استفاده شود.
روش حل قیاسی
تصویر صفحه 41 کتاب
روش حل قیاسی
قیاس مکانیکی می تواند برای تشریح یک نتیجه مهم که اصل اکثریت نامیده می شود استفاده شود.
طبق این اصل اگر حداقل نیمی (اکثریت) از وزن تجمعی به یک وسیله موجود مربوط باشد، مکان بهینه وسیله جدید بر مکان وسیله موجود منطبق است.
این قضیه هم برای برای مسایل جایابی با فاصله متعامد و فاصله اقلیدوسی که در آن یک وسیله جدید بررسی می شود، برقرار است.