با استفاده از حل کننده در اکسل می توان حداکثر جریان از گره S به گره T در یک شبکه جریان را پیدا نمود. امتیاز در یک شبکه گره (S، A، B، C، D، E و T) نامیده می شود. خطوط در یک شبکه به نام SA، SB، SC، AC، و غیره هستند.
دانلود فایل اکسل این آموزش maximum-flow-problem
فرمول بندی مدل
مدل اکسل ما به صورت زیر در نظر گرفته شده است.
1. برای حل مسئله حداکثر جریان، به سه سوال زیر پاسخ دهید.
a. چه تصمیماتی اتخاذ می شود؟ برای این مشکل، ما نیاز به اکسل برای پیدا کردن جریان در هر قوس داریم. به عنوان مثال، اگر جریان در SB به مقدار 2 باشد، در سلول D5 برابر 2 است.
b. محدودیت های این تصمیمات چیست؟ جریان خالص (جریان – جریان In) گره A، B، C، D و E باید برابر با 0 باشد. به عبارت دیگر، Flow Out = Flow In. همچنین، هر قوس ظرفیت ثابت دارد. جریان هر قوس باید کمتر از این ظرفیت باشد.
c. اندازه گیری کلی عملکرد برای این تصمیمات چیست؟ اندازه گیری کلی عملکرد حداکثر جریان است، بنابراین هدف این است که این مقدار را به حداکثر برسانیم. حداکثر جریان برابر با جریان از گره S است.
2. برای ایجاد مدل ساده تر، می توانید محدوده های زیر را نام ببرید.
نام محدوده | سلول ها |
---|---|
From | B4:B15 |
To | C4:C15 |
Flow | D4:D15 |
Capacity | F4:F15 |
SupplyDemand | K5:K9 |
MaximumFlow | D17 |
3. توابع زیر را وارد کنید.
توضیح: توابع SUMIF جریان جریان خالص هر گره را محاسبه می کنند. برای گره A، اولین تابع SUMIF مقادیر ستون Flow را با “A” در ستون From (Flow Out) مقداری می دهد. دومین تابع SUMIF مقادیر در ستون Flow با “A” در ستون (Flow In) مقداری را می دهد. حداکثر جریان برابر با مقدار در سلول I4 است که جریان از خارج از گره S. به دلیل گره A، B، C، D و E یک جریان خالص از 0، جریان از گره S خواهد جریان In از گره T برابر است.
آزمون و خطا
با استفاده از این فرمولاسیون، هر راه حل آزمایشی آسان می شود.
1. به عنوان مثال، SADT مسیر با جریان 2. مسیر SCT با جریان 4. مسیر SBET با جریان 2. این مسیر ها به مجموع جریان 8 است.
استفاده از آزمون و خطا لازم نیست. در قسمت بعد توضیح خواهیم داد که چگونه می توان از حل کننده اکسل برای یافتن راه حل بهینه استفاده کرد.
مدل را حل کنید
برای پیدا کردن راه حل بهینه، مراحل زیر را اجرا کنید.
1. در بخش داده، در گروه آنالیز، روی Solver کلیک کنید.
توجه: دکمه حل کننده را نمی توان پیدا کرد؟ برای بارگیری افزونه Solver اینجا را کلیک کنید .
پارامترهای حل کننده را وارد کنید (به عنوان خوانده شده). نتیجه باید با تصویر زیر سازگار باشد.
شما انتخاب تایپ کردن نام دامنه یا کلیک روی سلولهای صفحه گسترده را دارید.
2. MaximumFlow را برای هدف وارد کنید.
3. حداکثر را کلیک کنید.
4. جریان را برای تغییر سلول های متغیر وارد کنید.
5. برای وارد کردن محدودیت زیر، روی افزودن کلیک کنید.
6. برای وارد کردن محدودیت زیر، روی افزودن کلیک کنید.
7. بررسی کنید “متغیرهای بدون محدودیت غیر منفی” را انتخاب کنید و Simplex LP را انتخاب کنید.
8. در نهایت، روی حل کلیک کلیک کنید.
نتیجه:
راه حل بهینه:
نتیجه گیری: مسیر SADT با جریان 2. مسیر SCT با جریان 4. مسیر SBET با جریان 2. مسیر SCET با جریان 2. مسیر SACET با جریان 1. مسیر SACDT با جریان 1. این مسیر ها حداکثر جریان 12 را فراهم می کند.