موقعیت انبار کالا و موتورهای چند آغازه GRG و موتورهای تکاملی ابزار Solver

آخرین به‌روزرسانی: 27 دی 1401

در سری مقاله های آموزش اکسل، در فصل گذشته به استفاده از ابزار Solver برای امتیازدهی به تیم‌های ورزشی پرداختیم، در این مقاله موقعیت انبار کالا و موتورهای چند آغازه GRG و موتورهای تکاملی ابزار Solver را مورد بررسی قرار می‌دهیم.

درک موتور چند آغازه GRG و موتورهای تکاملی ابزار Solver

همان‌طور که در فصل 29 به نام” مقدمه‌ای بر بهینه‌سازی با ابزار Solver اکسل” بیان کردیم، نرم‌افزار اکسل 2019 دارای سه موتور قابل‌دسترس برای حل مسائل بهینه‌سازی است: موتور Simplex LP، موتور GRG Nonlinear و موتور Solver Evolotionary. در بخش‌های بعدی جزئیات بیشتری درباره اینکه چگونه دومین و سومین این موتورها برای حل مسائل بهینه‌سازی به ما کمک می‌کنند در اختیار شما قرار خواهیم داد.

ابزار Solver چگونه مسائلی با مدل خطی را حل می‌کند؟

مدل Solver چنانچه تمامی ارجاعات به سلول‌های متغیر در سلول هدف و محدودیت‌ها با اضافه‌کردن شرایط شکل (سلول‌های هدف)* محدودیت‌ها ایجاد شده باشد، مدلی خطی محسوب می‌شود. برای مدل‌های خطی همواره می‌بایست موتورهای Simplex را که برای یافتن کارآمد راه‌حل‌های مدل‌های Solver خطی طراحی شده‌اند استفاده کنید. نرم‌افزار اکسل 2019 می‌تواند به مسائل مدل‌های خطی تا 200 سلول متغیر و 100 محدودیت رسیدگی کند. نسخه‌های ابزار Solver که می‌توانند مسئله‌های بزرگ‌تری را مورد رسیدگی قرار دهند در سایت Solver.com موجود هستند.

موتور GRG Nonlinear چگونه مسائل مربوط به مدل‌های بهینه‌سازی غیرخطی را حل می‌کند؟

چنانچه سلول هدف و یا هریک از محدودیت‌ها حاوی ارجاعاتی به سلول‌های متغیری که در شکل (سلول متغیر)*(محدودیت) نباشد، دارای یک مدل غیرخطی خواهیم بود. اگر x و y سلول‌های متغیر باشند، ارجاعاتی چون موارد زیر در سلول هدف و یا هریک از محدودیت‌ها مدل را غیرخطی می‌کنند.

• x2
• x*y
• sin x
• ex
• x*e2y

چنانچه فرمول‌های غیرخطی دارای عملگرهای ریاضی معمولی‌ای همانند مثال‌های قبلی باشند، استفاده مناسب از موتور GRG Nonlinear می‌تواند به‌سرعت راه‌حل بهینه را برای مدل Solver ما پیدا کند. جهت نمایش نحوه کارکرد موتور GRG Nonlinear، فرض کنید می‌خواهید تابع –x2 را به حداکثر برسانید. این تابع در تصویر 1-36 نمایش‌داده‌شده است. (فایلی به نام Optimizationexamples.xlsx را مشاهده کنید)

می‌توان دید که این تابع برای x=0 به حداکثر می‌رسد. همچنین، توجه کنید که در حالت x=0 تابع دارای شیب صفر است. موتور GRG Nonlinear این مسئله را با تلاش برای پیداکردن نقطه که شیب تابع را برابر صفر می‌کند حل می‌نماید. به شکل مشابهی اگر بخواهید تابع y=x2 را به حداقل برسانید. موتور GRG Nonlinear این مسئله را با تعیین اینکه شیب این تابع برای حالت X=0 برابر با صفر است حل می‌کند. (تصویر 2-36 را ببینید)

بدبختانه توابع زیادی وجود دارند که نمی‌توان آنها را به‌سادگی با مشخص‌کردن نقطه‌ای که باعث صفر شدن شیب تابع می‌شود به حداکثر رساند. مثلاً فرض کنید که می‌خواهید تابع نشان‌داده‌شده در تصویر 3-36 را وقتی که محدوده x بین صفر و دوازده باشد به حداکثر برسانید.

می‌بینید که این تابع دارای چند قله است. اگر با مقدار x نزدیک 8 شروع کنیم، راه‌حل درست برای مسئله (x کمی کوچک‌تر از 8) را به دست می‌آوریم. اگر نزدیک قله دیگری مثلاً x=2 آغاز کنیم راه‌حل x کمی کوچک‌تر از عدد 2 را پیدا می‌کنیم که راه‌حل نادرستی است. ازآنجایی‌که در بیشتر مسئله‌ها (مخصوصاً آنها که بیش از یک سلول متغیر دارند) نقطه شروع مناسب را نمی‌دانید، به نظر می‌رسد بامانع بزرگی برای رفع کردن روبرو هستید. خوشبختانه اکسل 2019 گزینه Multistart (چند آغازه) را برای شما تدارک دیده است.

برای استفاده از این گزینه، ابتدا کادر محاوره‌ای Solver Parameters را با کلیک روی تب Data و بعد کلیک بر گزینه solver در گروه گزینه‌های Analyze باز می‌کنیم. (اگر ابزار Solver را نصب نکرده‌اید به فصل 29 مراجعه کنید) می‌توانید گزینه Multistart را با کلیک روی Options در سمت راست Select A Solving Method انتخاب کرده و سپس در کادر محاوره‌ای Options تب GRG Nonlinear را انتخاب کنید. حالا روی Use Multistart در بخش Multistart کادر محاوره‌ای کلیک کنید. اکسل هنگامی که گزینه Multistart انتخاب شود بسیاری از راه‌حل‌های آغازکننده را انتخاب کرده و پس شروع کار با این نقاط آغازین، بهترین جواب را پیدا می‌کند. این روش معمولاً مسئله‌های مربوط به منحنی‌های چند قله‌ای و چند دره‌ای را حل می‌نماید.

راستی بهتر است بدانید فشاردادن کلید Esc ابزار Solver را متوقف می‌کند. همچنین، به‌خاطر داشته باشید که گزینه GRG Multistart وقتی که در سلول‌های متغیرتان حدهای بالا و پایین معقولی گذاشته باشید بهتر کار می‌کند. (مثلاً شما سلول متغیر را به این شکل: Cell< 100million تعریف نمی‌کنید.)

موتور GRG همچنین، چنانچه سلول هدف و یا محدودیت‌ها از توابع ناهمواری مثل Max, Min, ABS, IF,SOMEIF,COUNTIF,SUMIFS,CONTIFS و سایر توابع ناهموار درگیر با سلول‌های متغیر استفاده کند با مشکل روبرو خواهد شد. این توابع نقطه‌هایی ایجاد می‌کنند که به دلیل آنکه شیب‌ها ناگهانی تغییر می‌کنند در آن هیچ شیب منحصربه‌فرد تعریف شده‌ای وجود ندارد. مثلاً تصور کنید یک مسئله بهینه‌سازی نیاز دارد که مدل ارزش یک اختیار خرید اروپایی با قیمت توافقی 40 دلار را ایجاد کنید. این اختیار خرید به شما اجازه می‌دهد سهام را به مبلغ 40 دلار خریداری کنید. اگر قیمت سهام در انقضای اختیار خرید را s در نظر بگیریم، آنگاه ارزش اختیار خرید برابر است با Max(0,s-40). این رابطه را در تصویر 4-36 نمایش داده‌ایم. مشخص است که وقتی s-40 باشد ارزش اختیار خرید شیبی ندارد بنابراین موتور GRG از کار خواهد افتاد.

همان‌طور که تصویر 5-36 نشان می‌دهد، مدل Solver که دارای تابعی با قدرمطلق باشد (به‌خاطر داشته باشید که قدر مطلق یک عدد فاصله آن عدد تا صفر است) شیبی برای x=0 نخواهد داشت. در اکسل تابع ABS(x) قدر مطلق عدد x را برمی‌گرداند.

تصویر 4-36 ارزش اختیار خرید برای قیمت سهام 40 دلاری هیچ شیبی ندارد

مسئله‌های بهینه‌سازی که سلول هدف و یا هریک از محدودیت‌های آن فاقد شیب در مقادیر سلول‌های متغیر هستند مسئله‌های بهینه‌سازی ناهموار نامیده می‌شوند. حتی گزینه GRG Multistart هم با این مسائل دچار مشکل می‌شود. در این موقعیت‌ها می‌بایست موتور Evolutionary Solver را به مدل اعمال کنید. این Solver برای مدل‌های Solver غیرخطی محدود به 100 سلول متغیر و 100 محدودیت است.

موتور Evolutionary Solver چگونه مسئله‌های بهینه‌سازی ناهموار را حل می‌کند؟

موتور Evolutionary Solver در اکسل 2019 بر اساس الگوریتم ژنتیک یعنی مفهومی که توسط جان هالند پروفسور دانشگاه میشیگان کشف شد است. برای استفاده از موتور Evolutionary Solver کار را با درنظرگرفتن 50 تا 100 نقطه در محدوده عملی مسئله (که مجموعه نقاطی است که با محدودیت ما هماهنگی دارند) شروع می‌کنیم. این مجموعه نقطه‌ها جمعیت (Population) نامیده می‌شود. سپس برای هر نقطه سلول هدف را ارزشیابی می‌کنیم. ما با استفاده از ایده بقای متناسب‌ترین شکل از نظریه تکامل، نقطه‌های جمعیت را به طریقی که احتمال اینکه اعضای جمعیت آینده در نزدیک اعضای جمعیت قبلی‌ای که ارزش سلول هدف خوبی دارند قرار گیرند تغییر می‌دهیم.

ازآنجاکه این روش بر اساس مقدار سلول‌های هدف بنا شده و نه بر اساس شیب، قله‌ها و دره‌های چندگانه مشکلی ایجاد نخواهند کرد. همچنین، توابعی که دارای شیب نیستند (اصطلاحاً توابع ناهموار) در اینجا مشکل مهمی حساب نخواهند شد. موتور Evolutionary Solver (مثل موتور Multistart GRG) همچنین، وقتی که حدهای بالا و پایین مناسبی برای سلول‌های متغیر قرارداده شده باشد بهتر کار می‌کند. پس از آنکه Evolutionary Solver Engine را انتخاب کردید (از بخش Select A Solving Method در کادر محاوره‌ای Solver Parameters) بهتر است گزینه Options را انتخاب کنید، تب Evolutionary را نمایان کنید (از کادر محاوره‌ای Options) و بعد میزان جهش را به 0.5 تغییر دهید.

همچنین، در قیمت گزینه‌های انتخابی Variables گزینه Required Bounds را انتخاب کنید و بیشترین زمان بدون پیشرفت را به 3.600 ثانیه تغییر دهید، افزایش میزان جهش باعث کاهش احتمال اینکه Solver با برخورد به یک راه‌حل ضعیف دچار درجازدن شود را کاهش می‌دهد. افزایش حداکثر زمان بدون پیشرفت به 36.00 ثانیه به Solver اجازه می‌دهد تا زمانی که نتواند تا 3600 ثانیه سلول هدف را مورد پیشرفت قرار دهد مرتباً عمل نماید. به این صورت ابزار Solver حتی اگر کامپیوتر خود را رها کنید همچنان به کار خود ادامه می‌دهد.

اکنون بیاید از ابزار Solver اکسل 2019 برای حل دو مسئله جالب مرتبط به موقعیت تأسیسات استفاده کنیم.

پاسخ به سؤالات این فصل:

یک شرکت توزیع اینترنتی می‌بایست در چه مکان‌هایی از ایالات متحده یک انبار ذخیره کالا قرار دهد تا مسافت کل ارسال بسته‌ها را به حداقل برساند؟

تعداد موارد ارسالی (به هزار) که هرسال به شهرهای مختلف فرستاده می‌شوند در تصویر 6-36 نشان‌داده‌شده (کاربرگ One Warehouse را در فایلی به نام Warehouseloc.xlsx مشاهده کنید.)

کلید اصلی این مدل فرمول زیر است که فاصله تقریبی بین دو شهر ایالات متحده که دارای طول و عرض جغرافیایی داده شده (Long1 و Lat1) و (Long2 و Lat2) هستند را به ما می‌دهد:

برای شروع در سلول‌های F4:G4 مقادیر آزمایشی طول و عرض جغرافیایی انبار را وارد می‌کنیم. سپس با کپی‌کردن فرمول: =69*SQRT((C7-$F$4)^2+(D7-
$G$4)^2) از سلول F7 در محدوده F8:F27 فاصله تقریبی هر شهر از انبار را محاسبه می‌کنیم. پس از آن با کپی‌کردن فرمول =E7*F7 از سلول G7 در محدوده G8:G27 فاصله طی شده برای ارسال کالا به هر شهر را محاسبه می‌کنیم. در سلول H5 فرمول =SUM(G7:G27) فاصله کل طی شده برای تمامی ارسال کالاها را محاسبه می‌کند. سلول هدف ما با تغییر محدوده F4:G4 سلول H5 را به حداقل می‌رساند. پس از آنکه موتور GRG Nonlinear را انتخاب کردید، کادر محاوره‌ای Solver Parameters چون تصویر 7-36 ظاهر می‌شود.

پس از آنکه روی دکمه Solver کلیک کردید درمی‌یابید که انبار می‌بایست در 36.81 درجه طول جغرافیایی و 92.48 درجه عرض جغرافیایی قرار گیرد که نزدیک به شهر اسپرینگفیلد از ایالت میسوری است. (مختصات در سلول F4:G4 در تصویر 6-36 نشان‌داده‌شده.)

یک شرکت توزیع اینترنتی می‌بایست در چه مکان‌هایی از ایالات متحده دو انبار ذخیره کالا قرار دهد تا مسافت کل ارسال بسته‌ها را به حداقل برساند؟

اقدامات انجام شده برای این مسئله در کاربرگ Two Warehouses در فایلی به نام warehouseloc.xlsx قرار گرفته و در تصویر 8-36 نشان‌داده‌شده است.

برای شروع طول و عرض جغرافیایی برای انبارها را در محدوده F4:G5 وارد می‌کنیم. سپس فرمول =69*SQRT((C7-$F$4)^2+(D7-$G$4)^2) را از سلول F7 به محدوده F8:F27 وارد می‌کنیم تا فاصله هر شهر از انبارها شماره 1 محاسبه کنیم. با کپی‌کردن فرمول =69*SQRT((C7-$F$5)^2+(D7-$G$5)^2) از سلول G7 به محدوده G8:G27 فاصله هر شهر را با انبار شماره 2 محاسبه می‌کنیم. ازآنجاکه کالاهای ارسالی به هر شهر از نزدیک‌ترین انبارها ارسال می‌شوند، می‌بایست فاصله هر شهر با نزدیک‌ترین انبار را با کپی‌کردن فرمول =MIN(F7,G7) از سلول H7 به محدوده H8:H27 محاسبه نماییم. در سلول‌های I7:I27 فاصله پیموده شده توسط هریک از کالاهای ارسالی شهر را با کپی‌کردن فرمول =H7*E7 از سلول I7 به سلول‌های I8:I27 محاسبه می‌کنیم و بالاخره در سلول I5 کل فاصله پیموده شده توسط کالاهای ارسالی را با فرمول =SUM(I7:I27) محاسبه می‌نماییم.

اکنون آماده هستیم تا از ابزار Solver برای مشخص‌کردن بهترین مکان برای انبارها استفاده کنیم. تنظیم کادر محاوره‌ای Solver Parameters در تصویر 9-36 نشان‌داده‌شده است.

کار را با انتخاب موتور GRG Nonlinear از لیست Select a Solving Method انتخاب می‌کنیم. سپس از راه حلی” ضعیف” استفاده می‌کنیم که در آن هر انبار را در طول و عرض جغرافیایی صفر قرار می‌دهد. این راه‌حل ضعیف است آن هم به دو دلیل: این راه‌حل انبار را در آفریقا قرار می‌دهد و از سوی دیگر دو انبار را در یک جا قرار می‌دهد. مشکل دووجهی است: تابع MIN موقعیتی بدون هیچ شیب ایجاد می‌کند و احتمالاً سلول هدف ما در نتیجه عملکرد چهار سلول متغیر دارای چندین قله و دره می‌شود. اگر سلول هدف ما دارای چند قله و دره باشد (در چهار بعد) راه‌حل ضعیف اولیه ما ممکن است نزدیک پایین دره نباشد که راه‌حل بهینه حقیقی است. در موقعیت‌هایی که مشکوک هستیم که آیا چندین قله و هدف وجود دارد یا نه فکر خوبی است که از گزینه GRG Multistart استفاده کنیم که چندین نقطه شروع را بکار می‌گیرد و از هر نقطه شروع بهترین پاسخ را پیدا می‌کند. در بیشتر اوقات بهترینِ بهترین راه‌حل‌هایی که توسط موتور Multistart پیدا می‌شود بهینه‌ترین راه‌حل برای مسئله به شمار می‌رود.

برای بکار بردن موتور Multistart حدودی برای سلول‌های متغیر ایجاد کرده و بعد ابزار Solver را با استفاده از گزینه GRG Multistart اجرا می‌کنیم. برای حد سلول‌های متغیر طول جغرافیایی از عددهای 0 و 90 درجه استفاده می‌کنیم. این به ما اطمینان می‌دهد که انبار در شمال استوا قرار گرفته. برای حد سلول‌های متغیر عرض جغرافیایی عددهای 0 و 150 را انتخاب می‌کنیم که با این کار اطمینان حاصل می‌کنیم که موقعیت در غرب گرینویچ، انگلستان و شرق آنکوراژ در آلاسکا باشد.

در نتایج می‌بینیم که میانگین مسافت پیموده شده توسط هر بار کالا 502 مایل است. موقعیت انبارها در سلول‌های F4:G5 تصویر 8-36 نمایش‌داده‌شده. انبار 1 نزدیک شهر لگزینگتون در کنتاکی است درحالی‌که انبار 2 در شهر لنکستر در ایالت کالیفرنیا قرار گرفته.

برای تأیید این مورد که ابزار Solver راه‌حل بهینه را پیدا کرده، موتور Evolutionary Solver را به راه می‌اندازیم و می‌بینیم که راه‌حل بهینه هیچ راه پیشرفت دیگری ندارد. (از این بهتر نمی‌شود)

فرض کنید برای عرض جغرافیایی حد بالای 100 درجه را انتخاب کرده باشیم. پس از اجرای ابزار Solver درمی‌یابیم که Solver عرض جغرافیایی‌ای نزدیک به 110 درجه پیشنهاد می‌دهد. اگر بر سلول متغیر حدی قرار دهید و ابزار Solver سلول متغیر را مجبور کند تا مقداری نزدیک به آن حد را در نظر بگیرد، می‌بایست آن حد موردنظر را کمی تقلیل دهید.

مسئله‌های این فصل

با فرض اینکه اجازه به ساخت سه انبار داده شود، بهترین راه‌حل را برای مسئله انبار پیدا کنید.

فرض کنید می‌خواهید یک دستشویی را در جایی بسازید که کارمندان شرکتی روزانه برای رفتن به دستشویی کمترین فاصله ممکن را بپیمایند. این کارمندان در کارخانه در چهار موقعیت مختلف کار می‌کنند که در جدول زیر نشان‌داده‌شده است.

فرض کنید که کارمندان وقتی به دستشویی می‌روند و برمی‌گردند همواره در مسیرهای شمال – جنوب و شرق – غرب راه می‌روند. این دستشویی در کجا می‌بایست قرار گیرد؟

مسئله دوم را درصورتی‌که شرکت بخواهد دو دستشویی احداث کند حل کنید.

جعبه‌ای می‌بایست چهار فوت مکعب حجم داشته باشد. شما می‌بایست ارتفاع، طول و عرض این جعبه را مشخص کنید. ساخت سطوح بالا و کف این جعبه در هر فوت مکعب 30 سنت هزینه برمی‌دارد و چهار سطح دیگر جعبه بر هر فوت مکعب 20 سنت هزینه برمی‌دارد. چطور می‌توانید ارزان‌ترین جعبه را بسازید؟

فرض کنید وزنه‌ای را از ارتفاع H با شتاب V و زاویه θ پرتاب می‌کنید. اگر H=5 فوت و V=100 فوت بر ثانیه باشد، چه زاویه‌ای باعث می‌شود وزنه به بیشترین مسافت پرتاب شود؟ فرض کنید که پس از زمانی معین، مختصات y از این پرتاب وزنه برابر با h+v*SIN(theta)*time-0.5*g*(time^2) و مختصات x برابر v*time*cos(theta) باشد.