حل مساله حداکثر جریان در اکسل

 

با استفاده از حل کننده در اکسل می توان حداکثر جریان از گره 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 را فراهم می کند.

 

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

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