مسئله بهینه‌سازی

شکل استاندارد مسئله بهینه‌سازی (پیوسته) به صورت زیر است:

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(x)=0,\quad i=1,\dots ,p\end{aligned}}}$

به طوری که:

• ${\displaystyle f(x):\mathbb {R} ^{n}\to \mathbb {R} }$ تابع مورد نظر ماست که می‌خواهیم بر روی ${\displaystyle x}$ کمینه شود.
• ${\displaystyle g_{i}(x)\leq 0}$ محدودیت نابرابری نامیده می‌شود و
• ${\displaystyle h_{i}(x)=0}$ محدودیت تساوی نامیده می‌شود.

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

به‌طور رسمی یک بهینه‌سازی ترکیبی A یک چهارتایی ${\displaystyle (I,f,m,g)}$ است به طوری که:

• ${\displaystyle I}$ مجموعه نمونه هاست.
• برای یک نمونه ${\displaystyle x\in I}$ داده شده، ${\displaystyle f(x)}$ مجموعه راه حل‌های امکان‌پذیر است.
• برای یک مورد داده شده ${\displaystyle x}$ و راه حل ممکن ${\displaystyle y}$ برای ${\displaystyle x}$، ${\displaystyle m(x,y)}$ اندازه ${\displaystyle y}$ را مشخص می‌کند که معمولاً یک عدد حقیقی مثبت است.
• g هدف تابع است که یا برابر کمینه یا بیشینه است.

هدف این است که برای یک نمونه ${\displaystyle x}$، یک راه حل بهینه پیدا کنیم که یک راه حل ممکن ${\displaystyle y}$ است با این شرط که

${\displaystyle m(x,y)=g\{m(x,y')\mid y'\in f(x)\}.}$

برای هر مسئله بهینه‌سازی ترکیبی، یک مسئله تصمیم متناظر وجود دارد که می‌پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص ${\displaystyle m_{0}}$ وجود دارد یا نه. به عنوان مثال یک گراف ${\displaystyle G}$ وجود دارد که شامل رئوس ${\displaystyle u}$ و ${\displaystyle v}$ یک مسئله بهینه‌سازی ممکن است «یافتن یک مسیر از ${\displaystyle G}$ به ${\displaystyle G}$ که از کمترین یال‌ها بگذرد» باشد. این مسئله ممکن است یک جواب مثلاً ۴ داشته باشد. یک مسئله تصمیم متناظر این خواهد بود که «آیا یک مسیر از ${\displaystyle G}$ به ${\displaystyle G}$ با استفاده از ۱۰ یال یا کمتر وجود دارد؟» این مسئله با یک «بله» یا «خیر» ساده جواب داده می‌شود. در زمینه الگوریتم‌های تخمین، الگوریتم‌ها برای مسائل سخت برای یافتن راه حل‌های نزدیک بهینه طراحی می‌شوند؛ بنابراین یک نسخه معمول تصمیم، یک توصیف ناکافی از مسئله است زیرا فقط راه حل‌های قابل قبول را مشخص می‌کند. اگرچه می‌توانیم مسائل تصمیم مناسبی مطرح کنیم، این مسائل دیگر بیشتر به‌طور طبیعی، یک مسئله بهینه‌سازی می‌شوند.

• بهینه‌سازی_خطی_عدد_صحیح

• نظریه پیچیدگی محاسباتی
• ان‌پی کامل

• Optimization_problem&oldid =468506162 ویکی‌پدیای انگلیسی مسئله بهینه‌سازی
• مهدی قطعی، بهینه‌سازی خطی و بهینه‌سازی تر کیبیاتی، انتشارات ناقوس، ۱۳۹۲، تهران، ایران.