حل مساله کوتاهترین مسیر در اکسل

 

از حل کننده در اکسل برای پیدا کردن کوتاهترین مسیر از گره S به گره T در یک شبکه ناخواسته استفاده کنید. امتیاز در یک شبکه گره (S، A، B، C، D، E و T) نامیده می شود. خطوط در یک شبکه به نام SA، SB، SC، AC، و غیره هستند.

 

دانلود فایل اکسل این آموزش shortest-path-problem

 

فرمول بندی مدل

مدل اکسل ما به صورت زیر در نظر گرفته شده است.

1. برای حل مسأله کوتاهترین مسیر، به سه سوال زیر پاسخ دهید.

a. چه تصمیماتی اتخاذ می شود؟ برای این مشکل، ما نیاز به اکسل برای پیدا کردن قوس در کوتاهترین مسیر است یا نه (بله = 1، بدون = 0). برای مثال، اگر SB بخشی از کوتاهترین مسیر باشد، سلول F5 برابر است با 1. اگر نه، سلول F5 برابر 0 است.

b. محدودیت های این تصمیمات چیست؟ جریان خالص (جریان – جریان در) هر گره باید برابر با عرضه / تقاضا باشد. گره S تنها باید یک قوس خروجی داشته باشد (جریان خالص = 1). گره T فقط باید یک قوس ورودی داشته باشد (جریان خالص = -1). تمام گره های دیگر باید یک قوس خروجی و یک قوس ورودی داشته باشند، اگر گره در کوتاهترین مسیر باشد (جریان خالص = 0) یا هیچ جریان (جریان خالص = 0).

c. اندازه گیری کلی عملکرد برای این تصمیمات چیست؟ اندازه گیری کلی عملکرد کل فاصله کوتاه ترین مسیر است، بنابراین هدف این است که این مقدار را به حداقل برسانیم.

2. برای ایجاد مدل ساده تر، می توانید محدوده های زیر را نام ببرید.

نام محدوده سلول ها
From B4:B21
To C4:C21
Distance D4:D21
Go F4:F21
NetFlow I4:I10
SupplyDemand K4:K10
TotalDistance F23

 

3. توابع زیر را وارد کنید.

توضیح: توابع SUMIF جریان جریان خالص هر گره را محاسبه می کنند. برای گره S، تابع SUMIF مقادیر ستون Go را با “S” در ستون From میفرستد. در نتیجه تنها سلول F4، F5 یا F6 می تواند 1 (یک قوس خروجی) باشد. برای گره T، تابع SUMIF مقادیر در ستون Go را با “T” در ستون To میفرستد. در نتیجه تنها سلول F15، F18 یا F21 می تواند 1 (یک قوس ورودی) باشد. اکسل برای همه گره های دیگر به ستون From و To نگاه می کند. فاصله کل برابر با مقادیر Distance و Go است.

ازمون و خطا

با استفاده از این فرمولاسیون، هر راه حل محاکمه ای آسان می شود.

1. به عنوان مثال، SBET مسیر دارای فاصله کل 16 است.

استفاده از آزمایش و خطا لازم نیست. ما بعدا توضیح خواهیم داد که چگونه می توان از حلال اکسل برای یافتن راه حل بهینه استفاده کرد.

مدل را حل کنید

برای پیدا کردن راه حل بهینه، مراحل زیر را اجرا کنید.

1. در بخش داده، در گروه آنالیز، روی Solver کلیک کنید.

توجه: دکمه حل کننده را نمی توان پیدا کرد؟ برای بارگیری افزونه Solver اینجا را کلیک کنید .

پارامترهای حل کننده را وارد کنید (به عنوان خوانده شده). نتیجه باید با تصویر زیر سازگار باشد.

شما انتخاب تایپ کردن نام دامنه یا کلیک روی سلولهای صفحه گسترده را دارید.

2. TotalDistance را برای هدف وارد کنید.

3. روی Min کلیک کنید.

4. برو برای تغییر سلول های متغیر وارد شوید.

5. برای وارد کردن محدودیت زیر، روی افزودن کلیک کنید.

6. چک کنید «متغیرهای بدون محدودیت غیر منفی را انتخاب کنید» و Simplex LP را انتخاب کنید.

7. در نهایت، روی حل کلیک کلیک کنید.

نتیجه:

راه حل بهینه:

نتیجه گیری: SADCT کوتاه ترین مسیر با فاصله کل 11 است.

 

 

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

*

code