برنامه ریزی عدد صحیحدرس های رایگان

حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

تهیه شده توسط گروه آموزشی بهینه یاب

حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

برای دانلود بسته طلایی آموزش کامل حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه شامل : جزوه کامل آموزش این درس، فایل ویدیوی آموزش این درس، فایل صوتی آموزش این درس، فایل ارایه حین درس مدرس بر روی دکمه زیر کلیک کنید.

دانلود بسته طلایی آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

برای دانلود جزوه آموزش کامل حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه بر روی دکمه زیر کلیک کنید.

دانلود جزوه آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

برای دانلود ویدیو آموزش کامل حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه بر روی دکمه زیر کلیک کنید.

دانلود ویدیو آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

درس 12: حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

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

 

 

تفاوت اصلی یک مسئله برنامه‌ریزی عدد صحیح و برنامه‌ریزی خطی در فرض صحیح بودن متغیرهای مسئله است. شاید در نگاه اول صحیح بودن متغیرها باعث می‌شود که تعداد جواب‌های امکان پذیر شمارا باشد که با کنترل تمامی آن‌ها می‌توان جواب بهینه را یافت. فرض کنید یک مدل دارای n متغیر دودویی (مقدار صفر یا یک می‌تواند اخذ نماید) باشد. اگر n=10 باشد، تعداد جواب‌های بیش از 1000 تا و اگر n=20 باشد، تعداد جواب‌ها، بیش از یک میلیون و اگر n=30 باشد، تعداد جواب‌ها بیشتر از یک میلیارد خواهد بود که حتی سریعترین کامپیوترها قادر به شمارش تمامی جواب‌ها نخواهند بود. حال اگر تعداد متغیرها از مقیاس میلیون باشند، دشوار به سرعت است بیشتر می‌شود.

پیچیدگی محاسبات یک مسئله برنامه ریزی عدد صحیح به دو عامل بستگی دارد:

1 – تعداد متغیرهای عدد صحیح

2 – ساختار مسئله

همان طور که ملاحظه می‌شود تعداد محدودیت‌ها اثری در دشوار حل مسئله ندارد که این برخلاف مسئله برنامه‌ریزی خطی است. از آنجایی که حل مسائل برنامه ریزی عدد صحیح عملا بسیار دشوار تر از حل مسائل برنامه‌ریزی خطی است، لذا گاهی منطقی به نظر می‌رسد که با حذف محدودیت‌های عدد صحیح، مسئله را به مسئله برنامه ریزی خطی آزاد شده تبدیل ساخت و سپس آن را با روش سیمپلکس حل جواب‌ها را گرد کرد. این روش ممکن است برای حل برخی از مسائل کاربردی که مقدار بسیار بزرگی دارند مناسب باشد. ولی این روش دارای دو اشکال زیر است:

1- شاید جواب گرد شده دیگر موجه نباشد.

2- شاید جواب گره شده دیگر بهینه نباشد.

برای تشریح دو اشکال فوق، مثال زیر را در نظر بگیرید.

حل برنامه ریزی عدد صحیح

جواب بهینه مسئله فوق به صورت زیر می شود.حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

حل برنامه ریزی عدد صحیح

متغیری که غیر صحیح دارد یعنی x2 را به عدد صحیح x2=1 گرد می‌کنیم، جواب حاصل x2=1 , x1=1 و z=7 می‌شود که این جواب با جواب بهینه مدل اصلی، یعنی z=10، x2=2,x1=0 اختلاف زیادی دارد.

متداول ترین الگوریتم برای حل مسائل برنامه ریزی عدد صحیح، روش انشعاب و تحدید یا شاخه و کرانه (Branch and Bound) است که نکته اصلی در آن، شمارش ضمنی جواب‌های موجه است. در ادامه این روش مورد بررسی قرار می‌گیرد.

روش شاخه و کرانه Branch and Bound

چون تعداد جواب‌های موجه یک مسئله برنامه ریزی عدد صحیح محدود، متناهی است، لذا طبیعی است که برای پیدا کردن جواب بهینه آن از روش شمارش (Enumeration procedure) استفاده شود. همان طور که گفته شد، چون تعداد جواب‌ها بسیار زیاد است، هر روش شمارش باید به صورت آگاهانه طوری طراحی شود که درصد کمی ‌از جواب‌ها را مورد بررسی قرار دهد. در این بخش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه بررسی می شود.

مبنای روش شاخه و کرانه برای حل مسائل برنامه ریزی عدد صحیح به شرح زیر است:

فرض کنید تابع هدف مسئله مورد نظر باید حداقل شود و مقدار تابع هدف نیز از مقدار مشخصی که آن را حد بالا (Upper Bound) (با zU نشان داده می‌شود) تجاوز نمی‌کند. این حد بالا معمولا مقدار تابع هدف به ازای بهترین جواب موجهی است که تاکنون پیدا شده است. منطقه جواب به چند زیر مجموعه منشعب می‌شود. آنگاه حد پایین (Lower Bound) هر زیر مجموعه ( zL ) بدست می‌آید. این حد پایین به این معنا است که zL از zU بیشتر باشد از بررسی خارج می‌شود. هر زیر مجموعه که جواب موجه ندارد و یا این که بهترین جواب موجه آن یافته شده است، از بررسی خارج می‌شود. هر زیر مجموعه‌ای که به هر کدام از دلایل فوق حذف شوند به ته رسیده یا fathomed گفته می‌شود.

وقتی یک مجموعه به ته می‌رسد، یکی دیگر از مجموعه‌های باقی مانده که مثلا بهترین حد را دارند انتخاب می‌شود. در عمل شاخه شدن بر روی آن انجام می‌شود. این کار تا زمانی ادامه می‌یابد که جواب موجهی بدست آید که مقدار تابع هدف آن از حد پایینی هیچکدام از زیر مجموعه‌های باقی مانده بیشتر نباشد و چنین جوابی، جواب بهینه است.

الگوریتم روش شاخه و کرانه

در ادامه خلاصه روش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه به صورت الگوریتمی ‌بیان می‌شود:

قدم ابتدایی (Initial step) : در نظر بگیرید zU=∞ . کل جواب‌های مورد بحث را به عنوان زیر مجموعه موجود در نظر بگیرید.

قدم انشعاب (Branch step): یکی از زیر مجموعه‌های باقی مانده (یک زیر مجموعه که نه به ته رسیده و نه منشعب شده است) را برای انشعاب انتخاب کنید. آن گاه زیر مجموعه انتخاب شده را به دو تا چند زیر مجموعه تقسیم کنید.

قدم تحدید (Bound step): حد پایینی مقدار تابع هدف ( zL ) را برای این زیر مجموعه تعیین کنید.

قدم به ته رسیدن (fathoming step): هر زیر مجموعه جدید که دارای یکی از شرایط زیر باشد، از بررسی بیشتر کنار گذاشته می‌شود.

آزمون 1: zL≥zU

آزمون 2: زیر مجموعه مورد نظر شامل هیچ جواب موجهی نیست.

آزمون 3: بهترین جواب موجه این زیر مجموعه مشخص شده است. اگر zL<zU باشد، این جواب جایگزین بهترین جواب موجود می‌شود و zU=zL و سپس آزمون 1 برای باقی گره‌ها انجام می‌شود.

قدم بهینگی: هنگامی‌ که زیر مجموعه دیگری برای انشعاب باقی نمانده است، توقف کنید. بهترین جواب موجه همان جواب بهینه است. در غیر این صورت، به قدم انشعاب بروید.

مثال: مسئله تخصیص کار به نفر زیر را در نظر بگیرید. هدف این است که هر کدام از کارها منحصرا به یکی از چهار نفر طوری تخصیص داده شود که مجموع هزینه‌های انجام شده حداقل شود.

حل برنامه ریزی عدد صحیح

 

حل:

تکرار صفر:

این مسئله دارای !4=24 ترکیب مختلف از جواب‌ها است. حد پایین این 24 جواب را با zL نشان می‌دهیم. برای چنین حد پایینی، جمع کردن حداقل‌ های ممکن هزینه‌های تخصیص ( یعنی مجموع اعداد حداقل ستون‌های جدول هزینه) در نظر گرفته می‌شود که در این مثال برابر با 2+1+2+2=7 می‌شود. این جواب مربوط به تخصیص DCDC است که واضحا یک جواب غیرموجه است.

تکرار 1:

با تخصیص کار 1 به هر کدام از افراد آغاز می‌کنیم و کل جواب‌ها را به 4 زیر مجموعه تخصیص می‌دهیم. برای مثال، حد پایین zL برای تخصیص کار 1 به نفر A برابر با 14=9+(1+2+2) می‌شود. به این صورت که 9 هزینه تخصیص کار 1 به نفر A است و حداقل هزینه‌ها برای مابقی کارها به شرط این که به فرد A دیگر کاری تخصیص داده نشود. حد پایین برای کار 1 به نفر B، برابر با 9=4+(1+2+2) می‌شود. برای تخصیص کار 1 به فرد C، حد پایین برابر 13=3+(3+2+5) می‌شود. برای تخصیص کار 1 به فرد D، حد پایین zL برابر با 8=2+(1+3+2) می‌شود.

چون zL برای زیر مجموعه C، منجر به جواب موجه CBDA می‌شود، لذا حد بالایی جواب بهینه نیز به صورت zU=13 به هنگام می‌شود و CBDA جواب بهینه فعلی می‌شود. طبق آزمون 3، زیر مجموعه C به ته می‌رسد. با توجه به آزمون 1، زیر مجموعه A به ته می‌رسد و لذا تنها دو مجموعه B و D برای انشعاب باقی می‌ماند. خلاصه نتایج در شکل زیر آمده است.

حل برنامه ریزی عدد صحیح

تکرار 2:

از بین دو زیر مجموعه باقی مانده، زیر مجموعه D به دلیل این که کمترین حد پایین را دارد انتخاب می‌شود. به این اصل، اصل بهترین حد گفته می‌شود. در این زیر مجموعه که کار 1 به فرد D تخصیص داده می‌شود و در این زیر مجموعه، می‌توان 3 زیر مجموعه DA، DB، و DC منشعب کرد که حد پایین به ترتیب برابر با 12، 10، و 12 می‌شود. برای این سه زیر مجموعه، هیچ یک از آزمون‌های توقف برقرار نیست. لذا زیر مجموعه‌های باقی مانده عبارتند از B، DA،DB و DC. نتایج این تکرار در شکل زیر آمده است.

حل برنامه ریزی عدد صحیح
تکرار 3:

از بین چهار زیر مجموعه باقی مانده، زیر مجموعه B به دلیل کمترین حد پایین انتخاب می‌شود و انتخاب به سه زیر مجموعه BA،BC، BD منشعب می‌شود. حد پایین آن‌ها به ترتیب برابر با 4+5+(2+2)=13 ، 4+1+(2+5)=12 و 13=4+4+( 3+2) خواهد بود. چون زیر مجموعه‌های BA و BC جواب‌های موجه هستند و حد پایین زیر مجموعه‌های BA و BD برابر حد بالای هستند، لذا هر سه زیر مجموعه به ته می‌رسند.

همچنین چون زیر مجموعه BC یک جواب موجه است مقدار تابع هدف در آن از zU فعلی کمتر است، لذا جواب BCDA بهترین جواب موجه جدید محسوب می‌شود. از آن جاییکه zU=12 برابر با zL زیر مجموعه‌های DA و DC است، لذا این دو مجموعه نیز به ته می‌رسد. بنابراین، تنها زیر مجموعه‌ای که تا این لحظه به جا مانده است، DB است. نتایج این تکرار در شکل زیر آمده است

حل برنامه ریزی عدد صحیح

تکرار 4:

تنها زیر مجموعه باقی مانده، DB است که به زیر مجموعه‌های DBA و DBC تقسیم می‌شود. حد پایین آن‌ها به ترتیب 2+3+4+(2)=11 و 2+3+3+(5)=13 است. چون این دو حد مربوط به جواب‌های موجه می‌شوند، لذا هر دو زیر مجموعه به ته می‌رسند. علاوه بر این‌ها، جواب موجه DBAC مربوط به زیر مجموعه DBA از بهترین جواب موجود بهتر است ( 11<12 )، لذا این جواب (DBAC) به عنوان جواب جدید انتخاب می‌شود. چون زیر مجموعه‌ای دیگر که هنوز به ته نرسیده باشد، باقی نمانده است، لذا بهترین جواب موجه (یعنی DBAC)، جواب بهینه است و الگوریتم به پایان می‌رسد. خلاصه محاسبات این تکرار در شکل زیر آمده است.

حل برنامه ریزی عدد صحیح

در مثال فوق، از قاعده بهترین حد برای انتخاب شاخه‌ها استفاده شد. قاعده دیگر در انتخاب شاخه روش جدیدترین حد است که از جدیدترین حد بدست آمده برای شاخه کردن استفاده می‌شود.

الگوریتم شاخه و کرانه برای برنامه‌ریزی صفر و یک

همان طور که در بخش قبلی گفته شده، بسیاری از مسائل برنامه ریزی عدد صحیح به صورت متغیرهای صفر و یک هستند. اما در برخی از مسائل، متغیرها می‌توانند بیش از دو مقدار به خود بگیرند. ولی می‌توان این مدل‌ها را به متغیرهای دودویی تبدیل کرد. فرض کنید که x یک عدد صحیح باشد. در این صورت می‌توان گفت

حل برنامه ریزی عدد صحیح
که
حل برنامه ریزی عدد صحیح

در این حالت، yi متغیرهای کمکی از نوع صفر و یک هستند.

برای ارایه دستور حل شاخه و کرانه برای مسئله برنامه ریزی عدد صحیح دودویی، مسئله‌ای عمومی ‌به صورت زیر را در نظر بگیرید.

حل برنامه ریزی عدد صحیح

که در مدل فوق داریم.
حل برنامه ریزی عدد صحیح

این فرض در واقع محدودیتی ایجاد نمی‌کند. زیرا اگر cj<0 باشد، می‌توان xj را با (1-x’j)- جایگزین کرد که در این صورت ضریب متغیر x’j در تابع هدف مثبت خواهد شد. با توجه به موارد فوق، الگوریتم شاخه و کرانه به صورت زیر ارایه می‌گردد.

گام شاخه کردن: در این گام با تخصیص 0 یا یک به برخی از متغیرها یک زیر مجموعه تعریف می‌شود که آن را جواب جزیی (x1,x2,…,xN) می‌نامند. تکمیل جواب جزیی، جوابی است که N متغیر اول آن برابر متغیرهای جزیی است. اگر (x1,x2,…,xN) آخرین جواب باشد، این جواب به دو زیر مجموعه تقسیم می‌شود که در یکی از آن xN+1=1 و در دیگری xN+1=0 است.

گام کرانه: حد پایین zL مربوط به جواب جزیی (x1,x2,…,xN) که موجه باشد به صورت زیر تعریف می‌شود.

حل برنامه ریزی عدد صحیح

چنانچه جواب جزیی، موجه نباشد و xN=0، می‌توان حد پایینی را به شرح زیر تعریف کرد:

حل برنامه ریزی عدد صحیح

در صورتیکه جواب جزیی موجه نباشد و xN=1 باشد، حد پایین از رابطه زیر محاسبه می‌شود.

حل برنامه ریزی عدد صحیح

گام توقف یا به ته رسیدن: در صورتی که جواب جزیی فعلی در یکی از آزمون‌های سه گانه زیر صدق کرد، دیگر نیازی به شاخه کردن نیست. این آزمون‌ها عبارتند از:

آزمون 1: zL≥zU

که zU مقدار تابع هدف بهترین جواب موجهی است که تا این مرحله بدست آمده است. در صورتیکه تاکنون جواب موجهی بدست نیامده است، zU=∞ منظور می‌شود.

آزمون 2:

در این آزمون نبودن جواب موجه در زیر مجموعه مورد نظر بررسی می‌شود که با تکمیل جواب جزیی فعلی آیا ممکن است که حداقل یکی از محدودیت‌ها هرگز برقرار نشود؟ طبق این آزمون، در صورتیکه به ازای یکی از مقادیر i=1,…,m ، رابطه زیر صدق نماید، آنگاه شاخه کردن جواب جزیی فعلی متوقف می‌شود.

حل برنامه ریزی عدد صحیح

آزمون 3:

در این آزمون رسیدن به بهترین جواب موجه در زیر مجموعه بررسی می‌شود که آیا جواب جزیی فعلی موجه است یا نه. چنانچه جواب جزیی فعلی به XN=0 ختم شود، به جای بررسی موجه بودن جواب جزیی فعلی، موجه بودن جواب جزیی که در آن XN+1=1 بررسی می‌شود. بیان ریاضی این آزمون به صورت زیر است.

حل برنامه ریزی عدد صحیح

چنانچه این شرط برقرار شود و همچنین داشته باشیم zL<zU ، لذا zL=zU می‌شود و این جواب به عنوان بهترین جواب موجود در نظر می‌گیریم.

برای روشن شدن موضوع مثال زیر را حل می‌کنیم.

تمرین: مسئله برنامه ریزی عدد صحیح زیر را حل نمایید.

حل برنامه ریزی عدد صحیح

حل:

تکرار صفر:

zU=∞ و چون ضریب متغیرها در تابع هدف نامنفی هستند، لذا مقدار بهینه تابع هدف قطعا از صفر بزرگتر است و لذا zL=0. چون جواب (0,0,0,0,0,0) در محدودیت‌های 1 و 3 امکان پذیر نیست، لذا شرایط توقف برقرار نیست و باید این گره، شاخه کرد و این گره به دو شاخه x1=1 و x1=0 تقسیم می‌شود.

تکرار 1: جواب جزیی (1) بررسی می‌شود:

آزمون 1:

حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح
این گره در این آزمون به ته نمی‌رسد.

آزمون 3: جواب (1,0,0,0,0,0) بررسی می‌شود که محدودیت‌ها برقرار یا نه؟

حل برنامه ریزی عدد صحیح

این گره در آزمون 3 بسته نمی‌شود.

تکرار 2: گره با جواب جزیی (1,0) بررسی شود:

آزمون 1:

حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح

آزمون 3: جواب (1,0,1,0,0,0) را از نظر برقراری در محدودیت‌ها بررسی شود.
حل برنامه ریزی عدد صحیح

این گره در آزمون 3 بسته نمی‌شود.

تکرار 3: جواب جزیی (1,0,0) بررسی شود.

آزمون 1:
حل برنامه ریزی عدد صحیح
آزمون 2:
حل برنامه ریزی عدد صحیح

آزمون 3: با توجه به این که جواب جزیی (1,0,0) است، باید جواب (1,0,0,1,0,0) کنترل شود که در محدودیت‌ها برقرار است یا نه؟

حل برنامه ریزی عدد صحیح

جواب (1,0,0,1,0,0) امکان‌پذیر است و لذا zU=12.

تکرار 4: جواب جزیی (1,0,1) در نظر بگیرید

آزمون 1:

حل برنامه ریزی عدد صحیح

آزمون 2:

حل برنامه ریزی عدد صحیح

چون محدودیت 1 برقرار نیست لذا این گره با توجه به آزمون 2 به ته می‌رسد.

تکرار 5: جواب جزیی (1,1) را در نظر بگیرید.

آزمون 1:
حل برنامه ریزی عدد صحیح

 

آزمون 2:
حل برنامه ریزی عدد صحیح

این گره به ته می‌رسد.

تکرار 6: جواب جزیی (0) را در نظر بگیرید.

آزمون1:

حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح

با این آزمون به ته نمی‌رسد.

آزمون 3: چون x1=0 است، باید کنترل شود که (0,1,0,0,0,0) امکان پذیر است یا نه؟
حل برنامه ریزی عدد صحیح

در این آزمون، گره به ته نمی‌رسد.

تکرار 7: جواب جزیی (0,1) را در نظر بگیرید.

آزمون 1:
حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح
آزمون 3: جواب (0,1,0,0,0,0) بررسی شود.
حل برنامه ریزی عدد صحیح
تکرار 8: جواب جزیی (0,1,1) را در نظر بگیرید.

آزمون 1:
حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح

آزمون 3: جواب (0,1,1,0,0,0) کنترل شود.
حل برنامه ریزی عدد صحیح

این گره با آزمون 3 به ته می‌رسد و zU=11 بهترین جواب موجه فعلی است.

تکرار 9: جواب جزیی (0,1,0) را در نظر بگیرید.

آزمون 1: چون رابطه زیر برقرار است و لذا این گره بسته می‌شود.
حل برنامه ریزی عدد صحیح

تکرار 10: جواب جزیی (0,0) را در نظر بگیرید.

آزمون 1:

حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح

آزمون 3: جواب (0,0,1,0,0,0) را بررسی کنید.
حل برنامه ریزی عدد صحیح

این گره به ته نمی‌رسد.

تکرار 11: جواب جزیی (0,0,1) را در نظر بگیرید.

آزمون 1:

حل برنامه ریزی عدد صحیح آزمون 2:

حل برنامه ریزی عدد صحیح

آزمون 3: جواب (0,0,1,0,0,0) کنترل شود.
حل برنامه ریزی عدد صحیح

تکرار 12: جواب جزیی (0,0,1,1) را در نظر بگیرید.

آزمون 1: چون رابطه زیر برقرار است

حل برنامه ریزی عدد صحیح

و لذا این گره بسته می‌شود.

تکرار 13: جواب (0,0,1,0) را در نظر بگیرید.

آزمون 1: چون رابطه زیر برقرار است

حل برنامه ریزی عدد صحیح

لذا این گره بسته می‌شود.

تکرار 14: جواب (0,0,0) را در نظر بگیرید.

آزمون 1:
حل برنامه ریزی عدد صحیح

آزمون 2:
حل برنامه ریزی عدد صحیح

این گره با آزمون 2 به ته می‌رسد.

کلیه گره‌ها بسته شده است و جواب بهینه z=11 و (0,1,1,0,0,0) می‌شود. خلاصه محاسبات در شکل زیر آمده است.

حل برنامه ریزی عدد صحیح

الگوریتم شاخه و کرانه برای برنامه‌ریزی مختلط

مدل برنامه‌ریزی عدد صحیح زیر را در نظر بگیرید:

حل برنامه ریزی عدد صحیح

در مدل فوق، اگر I=n باشد مدل برنامه‌ریزی عدد صحیح خالص (Pure integer programming) خواهیم داشت. برای حل مدل فوق الگوریتم زیر ارایه می‌شود.

با حذف محدودیت عدد صحیح و حل مسئله برنامه‌ریزی خطی آزاد شده انجام می‌شود. اگر جواب حاصل به ازإی تمامی متغیرهای عدد صحیح، مقدار صحیح به خود بگیرد، در این صورت جواب بهینه بدست آمده است. در غیر این صورت، در هر تکرار متغیری مانند xj را بر می‌گزیند که مقدار آن عدد صحیح نباشد به طوری که اگر k عدد صحیح باشد،

حل برنامه ریزی عدد صحیح

سپس زیر مجموعه موجود را دو زیر مجموعه جدید تقسیم می‌کند.

  • جواب‌هایی که در آن xj≤k
  • جواب‌هایی که در آن xj≥1+k

با حذف شرط صحیح بودن و حل مسئله برنامه‌ریزی خطی آزاد شده (با اضافه کردن محدودیت‌های xj≤k یا xj≥1+k ) یک حد بالا ( zU ) برای زیر مجموعه بدست می‌آید. جواب مسئله آزاد شده توسط روش سیمپلکس ثانویه بدست می‌آید. آزمون‌های به ته رسیدگی به صورت سه آزمون زیر است:

آزمون 1: zL≥zU

آزمون 2: با روش سیمپلکس ثانویه در می‌یابیم که جواب موجهی وجود ندارد.

آزمون 3: در جواب بهینه، تمام متغیرهای (xj (j=1,…,I عدد صحیح باشند.

اگر زیر مجموعه‌ای با آزمون 3 به ته رسید و zL < zU باشد، آنگاه zL = zU قرار داده شده و این جواب را به عنوان بهترین جواب موجود ذخیره می‌شود. پس از آن که تمامی ‌زیر مجموعه‌های باقی مانده به ته رسیدند، آنگاه حد پایین همان جواب بهینه است.

مثال: مدل برنامه‌ریزی عدد صحیح زیر را از روش شاخه و کرانه حل نمایید.

حل مدل برنامه ریزی عدد صحیح

حل: فرم استاندارد مدل فوق به صورت زیر است:

حل مدل برنامه ریزی عدد صحیح

حل مدل برنامه ریزی عدد صحیح

متغیر x1 و x2 دارای مقدار غیر صحیح در جواب بهینه است. لذا یکی از متغیرها را باید برای شاخه کردن انتخاب کرد که در این مرحله x2 انتخاب می‌شود.

 

حل مدل برنامه ریزی عدد صحیححل مدل برنامه ریزی عدد صحیححل مدل برنامه ریزی عدد صحیححل مدل برنامه ریزی عدد صحیح

 

با توجه به این که ضرایب متغیرها در معادله شماره 4 مثبت است و سمت راست منفی است، لذا این جواب امکان ناپذیر است.

حل مدل برنامه ریزی عدد صحیح

حل مدل برنامه ریزی عدد صحیح
حل مدل برنامه ریزی عدد صحیح
حل مدل برنامه ریزی عدد صحیح
حل مدل برنامه ریزی عدد صحیح
حل مدل برنامه ریزی عدد صحیح
حل مدل برنامه ریزی عدد صحیح
حل مدل برنامه ریزی عدد صحیح

کلیه مراحل حل را می‌توان در درخت زیر نشان داد.

حل مدل برنامه ریزی عدد صحیح

حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

توجه: برای مطالعه ادامه این درس و دانلود سایر محصولات مربوط به این درس می توانید به موارد زیر مراجعه کنید.

حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

برای دانلود بسته طلایی آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه شامل : جزوه کامل آموزش این درس، فایل ویدیوی آموزش این درس، فایل صوتی آموزش این درس، فایل ارایه حین درس مدرس بر روی دکمه زیر کلیک کنید.

دانلود بسته طلایی آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

برای دانلود جزوه کامل آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه بر روی دکمه زیر کلیک کنید.

دانلود جزوه آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

برای دانلود ویدیو آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه بر روی دکمه زیر کلیک کنید.

دانلود ویدیو آموزش حل مسائل برنامه ریزی عدد صحیح به روش شاخه و کرانه

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

دکمه بازگشت به بالا