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

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

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

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

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

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

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

محدودیت برش جدید به جدول سیمپلکس با محدودیت برش جدید اضافه شده و توضیح برش گومری و حل با سیمپلکس ثانویه اجرا می‌گردد. این کار منجر به بررسی جواب بهینه جدید می‌شود تا اطمینان حاصل شود که متغیرها اکنون مقادیر صحیح دارند.

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

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

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

برای درک بهتر، یک مثال روش بالاس (مسئله) با شروع حل و اشاره به گام‌های ۱ تا ۳ ، اولین شاخه‌زنی ، ادامه بررسی گره‌ها و ادامه شاخه‌زنی و بررسی ضوابط شاخه‌زنی ارائه می‌گردد. فرآیند با محاسبات و شاخه‌زنی دوم و محاسبه جواب گره و بررسی ژرفا پیش می‌رود و با ادامه فرآیند شاخه‌زنی ، انتخاب متغیر شاخه‌زنی X3 ، انشعاب بر روی X3 و محاسبه جواب‌ها و بررسی ژرفا به پاسخ نهایی روش بالاس منجر می‌شود.