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

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

استفاده های اصلی از مشکلات با متغیر، یک عدد صحیح، بهینه سازی است. یک روش که با استفاده از یک عدد صحیح برنامه ریزی خطی، همچنین از روش برش نامیده می شود.

روش Gomory پس از ریاضیدان به نام بود، برای اولین بار در 1957-1958 الگوریتم توسعه یافته است که هنوز هم به طور گسترده ای مورد استفاده برای حل مسائل برنامهریزی خطی عدد صحیح است. فرم استاندارد از مشکل برنامه ریزی عدد صحیح اجازه می دهد تا در دسترس و به طور کامل فاش مزایای استفاده از این روش است.

روش Gomori اعمال شده به یک برنامه ریزی خطی تا حد زیادی وظیفه پیدا کردن ارزش های مطلوب پیچیده. پس از integrality یک نیاز اساسی، بیشتر تمام پارامترهای مشکل است. موارد وجود دارد که مشکل با داشتن معتبر (عدد صحیح) برنامه، حضور در تابع هدف محدودیت در مجموعه ای قابل قبول، تصمیم می آید به دستیابی به حداکثر. این به خاطر فقدان آن راه حل جدایی ناپذیر است. بدون شرایط مشابه، به عنوان یک قاعده، در قالب یک تصمیم بردار مناسب است.

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

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

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

روش Gomory اساسا شامل محدودیت ساختمان، که راه حل هایی که می nonintegral نیست را کاهش دهد. در این صورت، هیچ قطع هیچ راه حل های صحیح طرح وجود دارد.

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

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

هنگامی که محدودیت های ساخت و ساز باید انتخاب شود جزئی از یک طرح مطلوب با بالاترین بخش. این است که این محدودیت خواهد شد به جدول سیمپلکس موجود اضافه شده است.

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

پس از یک تعداد متناهی از تکرار انجام شود، دستیابی به یک برنامه بهینه از مشکل مطرح شده در مقابل برنامه ریزی عدد صحیح، و یا اثبات غیر محلولی از مشکل است.