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

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

به طوری که:

• ${\displaystyle f(x):{\mathbb{R}}^n\to \mathbb{R}}$
  تابع مورد نظر ماست که می‌خواهیم بر روی ${\displaystyle x}$
  کمینه شود.
• ${\displaystyle g_i(x)\le 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 m(x,y)=g\{m(x,y^{\prime })\mid y^{\prime }\in f(x)\}.}$

برای هر مسئله بهینه‌سازی ترکیبی، یک مسئله تصمیم متناظر وجود دارد که می‌پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص ${\displaystyle m_0}$

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

یک مسئله بهینه‌سازی NP یا به‌طور مخفف NPO یک مسئله بهینه‌سازی ترکیبی است با شرایط اضافی زیر. توجه داشته باشید که چندجمله‌ای‌های اشاره شده در زیر، توابعی با سایز متناسب با ورودی‌های تابع هستند، نه مجموعه‌ای مطلق از نمونه ورودی‌ها.

• سایز هر راه حل ممکن ${\displaystyle y\in f(x)}$
  به‌طور چندجمله‌ای محدود به سایز نمونه ${\displaystyle x}$
  داده شده‌است.
• زبان‌های ${\displaystyle \{x\mid x\in I\}}$
  و ${\displaystyle \{(x,y)\mid y\in f(x)\}}$
  می‌توانند در زمان چندجمله‌ای مشخص شوند و
• m در زمان چندجمله‌ای قابل محاسبه است.

این دلالت بر این دارد که مسئله تصمیم متناظر، یک NP است. در علوم کامپیوتر، معمولاً مسائل بهینه‌سازی جالب توجه، ویژگی‌های بالا را دارند و بنابراین مسائل NPO هستند. یک مسئله به علاوه یک مسئله بهینه‌سازی نوع P یا PO خوانده می‌شود اگر الگوریتمی وجود داشته باشد که در زمان چندجمله‌ای راه حل بهینه را پیدا کند. معمولاً هنگام کار کردن با دسته NPO، مسائل بهینه‌سازی جالبی وجود دارد که نسخه‌های تصمیم، NP-سخت هستند. توجه داشته باشید که روابط سختی، همواره در تناسب با ساده‌سازی هستند. به علت ارتباط بین الگوریتم‌های تخمین و مسائل محاسباتی بهینه‌سازی، مسائل بهینه‌سازی با نسخه‌های تصمیم NP-تکمیل لزوماً NPO-تکمیل نامیده نمی‌شوند. NPOPB یک دسته دیگر است؛ NPO با تابع هزینه محدود به چندجمله‌ای. مسائلی با این شرایط، ویژگی‌های مطلوب زیادی دارند.

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

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

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