بهینه سازی خطی عدد صحیح ( به انگلیسی: Integer Linear Optimization ) زیر شاخه ای از بهینه سازی ریاضی است که مسایل آن مشابه مسایل بهینه سازی خطی است، با این تفاوت که همه یا برخی از متغیر ( مجهول ) های مسئله عدد صحیح هستند. همانند بهینه سازی خطی، هدف برنامه ریزی عدد صحیح پیدا کردن مقدار کمینه یا بیشینه از یک تابع خطی بر روی فضایی با محدودیت هایی خطی است، اما به دلیل وجود متغیرهای گسسته این فضا پیوسته و محدب نیست بلکه فضایی گسسته ( در نتیجه نامحدب ) است. چنانچه تعدادی از متغیرها به صورت اعداد صحیح و بقیه متغیرها به صورت اعداد غیر صحیح بیان شوند، مسئله از نوع بهینه سازی خطی ترکیبی ( به انگلیسی: mixed - integer linear programming ) ، که به اختصار MILP هم گفته می شود، خواهد بود.
فرم متعارف مسئلهٔ بهینه سازی عدد صحیح به این صورت بیان می شود:
با بکار بردن متغیرهای کمکی می توان فرم متعارف را به به فرم استاندارد تبدیل کرد:
با این کار نامساوی ها به تساوی تبدیل می شوند. در این مدل b بردار منابع، c بردار هزینه و A ماتریس ضرایب می باشد.
مثال زیر را در نظر بگیرید:
نقاط صحیحی که می توانند جواب مسئله باشند در شکل با رنگ قرمز نشان داده شده اند و خطوط بریده بریده قرمز نشانگر ناحیه امکان پذیر برای جواب مسئله است. خطوط آبی، ناحیه ای را نشان می دهد که پاسخ مسئله بدون در نظر گرفتن شرط صحیح بودن در آن قرار می گیرد.
ایده اصلی در این روش تقسیم ناحیه امکان پذیر به چند زیر منطقه و بررسی امکان وجود جواب های صحیح در این نواحی است. بدین منظور گام های زیر پیموده می شوند:
• مسئله خطی اصلی را بدون در نظر گرفتن شرط صحیح بودن متغیرها حل کنید ( الف ) . اگر همه متغیرها مقدار صحیح گرفتند، جواب مسئله بدست آمده است. در غیر اینصورت به گام دوم بروید.
• اگر تابع هدف از نوع Max بود قرار دهید ∞ - =ZL در غیر اینصورت قرار دهید ∞+=ZL.
• شاخه بندی:
یکی از متغیرهای تصمیم گیری که عدد صحیح نیست را انتخاب کنید ( XJ=X*J ) و دو مسئله فرعی P1 و P2 را به صورت زیر ایجاد کنید:
مسئله P1 همان مسئله ( الف ) می باشد با این تفاوت که قید [XJ ≤ [X*j به آن اضافه شده است.
مسئله P2 همان مسئله ( الف ) می باشد با این تفاوت که قید [1 +XJ ≤ [X*j به آن اضافه شده است.
۴. کران :
مسئله بدست آمده P1 P2 را حل کرده و بهترین مقداری که برای تابع هدف به ازای یک جواب موجه عدد صحیح برای ۲ مسئله مذکور بدست آمده را جایگزین ZL کنید.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلففرم متعارف مسئلهٔ بهینه سازی عدد صحیح به این صورت بیان می شود:
با بکار بردن متغیرهای کمکی می توان فرم متعارف را به به فرم استاندارد تبدیل کرد:
با این کار نامساوی ها به تساوی تبدیل می شوند. در این مدل b بردار منابع، c بردار هزینه و A ماتریس ضرایب می باشد.
مثال زیر را در نظر بگیرید:
نقاط صحیحی که می توانند جواب مسئله باشند در شکل با رنگ قرمز نشان داده شده اند و خطوط بریده بریده قرمز نشانگر ناحیه امکان پذیر برای جواب مسئله است. خطوط آبی، ناحیه ای را نشان می دهد که پاسخ مسئله بدون در نظر گرفتن شرط صحیح بودن در آن قرار می گیرد.
ایده اصلی در این روش تقسیم ناحیه امکان پذیر به چند زیر منطقه و بررسی امکان وجود جواب های صحیح در این نواحی است. بدین منظور گام های زیر پیموده می شوند:
• مسئله خطی اصلی را بدون در نظر گرفتن شرط صحیح بودن متغیرها حل کنید ( الف ) . اگر همه متغیرها مقدار صحیح گرفتند، جواب مسئله بدست آمده است. در غیر اینصورت به گام دوم بروید.
• اگر تابع هدف از نوع Max بود قرار دهید ∞ - =ZL در غیر اینصورت قرار دهید ∞+=ZL.
• شاخه بندی:
یکی از متغیرهای تصمیم گیری که عدد صحیح نیست را انتخاب کنید ( XJ=X*J ) و دو مسئله فرعی P1 و P2 را به صورت زیر ایجاد کنید:
مسئله P1 همان مسئله ( الف ) می باشد با این تفاوت که قید [XJ ≤ [X*j به آن اضافه شده است.
مسئله P2 همان مسئله ( الف ) می باشد با این تفاوت که قید [1 +XJ ≤ [X*j به آن اضافه شده است.
۴. کران :
مسئله بدست آمده P1 P2 را حل کرده و بهترین مقداری که برای تابع هدف به ازای یک جواب موجه عدد صحیح برای ۲ مسئله مذکور بدست آمده را جایگزین ZL کنید.
wiki: بهینه سازی خطی عدد صحیح