|
در [[ریاضیات]] و [[علوم رایانه]] یک مسئله بهینه سازی،بهینه‌سازی، مسئله یافتن بهترین راه حل از میان همه راه حل هایحل‌های عملی می باشدمی‌باشد. مسئله های بهینه سازیمسئله‌های میبهینه‌سازی تواندمی‌تواند به دو دسته تقسیم شود که متغیرها پیوسته یا گسسته باشند. یک مسئله بهینه سازیبهینه‌سازی با [[متغیر|متغیرهای]]های گسسته به عنوان یک مسئله بهینه سازیبهینه‌سازی ترکیبی یا ترکیبیاتی شناخته می شوندمی‌شوند. در یک مسئله بهینه سازیبهینه‌سازی ترکیبی، ما به دنبال مجموعه ایمجموعه‌ای از اشیاء از قبیل عدد صحیح، [[جایگشت]] و یا [[گراف|گرافی]] می گردیممی‌گردیم که تعداد اعضایش محدود (و یا به طور قابل شمارش نامحدود) باشند.
==مسئله بهینه سازی پیوسته==
شکل استاندارد== مسئله بهینهبهینه‌سازی سازی (پیوسته) به صورت زیر است:==
شکل استاندارد مسئله بهینه‌سازی (پیوسته) به صورت زیر است:
: <math>\begin{align}
&\underset{x}{\operatorname{minimize}}& & f(x) \\
\end{align}</math>
به طوری که:
* <math>f(x): \mathbb{R}^n \to \mathbb{R}</math> [[تابع]] مورد نظر ماست که می خواهیممی‌خواهیم بر روی <math>x</math> کمینه شود.
* <math>g_i(x) \leq 0</math> محدودیت نابرابری نامیده می شودمی‌شود و
* <math>h_i(x) = 0</math> محدودیت تساوی نامیده می شودمی‌شود.
طبق قرارداد، شکل استاندارد، یک مسئله به حداقل رساندن را توصیف می کندمی‌کند. یک مسئله به حداکثر رساندن می تواندمی‌تواند با منفی کردن تابع هدف به دست آید.
==مسئله بهینه سازی ترکیبی==
== مسئله بهینه‌سازی ترکیبی ==
به طور رسمی یک بهینه سازیبهینه‌سازی ترکیبی A یک چهارتایی <math>(I, f, m, g)</math> است به طوری که:
* <math>I</math> مجموعه نمونه هاست.
* برای یک نمونه <math>x \in I</math> داده شده، <math>f(x)</math> [[مجموعه]] راه حلحل‌های های امکان پذیرامکان‌پذیر است.
* برای یک مورد داده شده <math>x</math> و راه حل ممکن <math>y</math> برای <math>x</math>، <math>m(x, y)</math> اندازه <math>y</math> را مشخص می کندمی‌کند که معمولاً یک عدد حقیقی مثبت است.
* g هدف تابع است که یا برابر کمینه و یا بیشینه است.
هدف این است که برای یک نمونه <math>x</math>، یک راه حل بهینه پیدا کنیم که یک راه حل ممکن <math>y</math> است با این شرط که
: <math>
m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .
</math>
برای هر مسئله بهینه سازیبهینه‌سازی ترکیبی، یک [[مسئله تصمیم]] متناظر وجود دارد که می پرسدمی‌پرسد ببیند آیا یک راه حل ممکن برای مقدار خاص <math>m_0</math> وجود دارد یا نه. به عنوان مثال یک گراف <math>G</math> وجود دارد که شامل رئوس <math>u</math> و <math>v</math> یک مسئله بهینه سازیبهینه‌سازی ممکن است «یافتن یک مسیر از <math>G</math> به <math>G</math> که از کمترین یال هایال‌ها بگذرد» باشد. این مسئله ممکن است یک جواب مثلاً ۴ داشته باشد. یک مسئله تصمیم متناظر این خواهد بود که «آیا یک مسیر از <math>G</math> به <math>G</math> با استفاده از ۱۰ یال یا کمتر وجود دارد؟» این مسئله با یک «بله» یا «خیر» ساده جواب داده می شودمی‌شود.
در زمینه الگوریتم هایالگوریتم‌های تخمین، الگوریتم هاالگوریتم‌ها برای مسائل سخت برای یافتن راه حل هایحل‌های نزدیک بهینه طراحی می شوند.می‌شوند؛ بنابراین یک نسخه معمول تصمیم، یک توصیف ناکافی از مسئله است زیرا فقط راه حل هایحل‌های قابل قبول را مشخص می کندمی‌کند. اگرچه می توانیممی‌توانیم مسائل تصمیم مناسبی مطرح کنیم، این مسائل دیگر بیشتر به طور طبیعی، یک مسئله بهینه سازی میبهینه‌سازی شوندمی‌شوند.
=== مسئله بهینه سازیبهینه‌سازی NP ===
یک مسئله بهینه سازیبهینه‌سازی NP یا به طور مخفف NPO یک مسئله بهینه سازیبهینه‌سازی ترکیبی است با شرایط اضافی زیر. توجه داشته باشید که چندجمله‌ای هایچندجمله‌ای‌های اشاره شده در زیر، توابعی با سایز متناسب با ورودی هایورودی‌های تابع هستند، نه مجموعه ایمجموعه‌ای مطلق از نمونه ورودی هاورودی‌ها.
* سایز هر راه حل ممکن <math>\scriptstyle y\in f(x)</math> به طور چندجمله‌ای محدود به سایز نمونه <math>x</math> داده شده است.
* زبان هایزبان‌های <math>\scriptstyle \{\,x\,\mid\, x \in I \,\}</math> و <math>\scriptstyle \{\,(x,y)\, \mid\, y \in f(x) \,\}</math> می توانندمی‌توانند در زمان چندجمله‌ای مشخص شوند و
* m در زمان چندجمله ایچندجمله‌ای قابل محاسبه است.
این دلالت بر این دارد که مسئله تصمیم متناظر، یک NP است. در علوم کامپیوتر، معمولاً مسائل بهینه سازیبهینه‌سازی جالب توجه، ویژگی هایویژگی‌های بالا را دارند و بنابراین مسائل NPO هستند. یک مسئله به علاوه یک مسئله بهینه سازیبهینه‌سازی نوع P یا PO خوانده می شودمی‌شود اگر [[الگوریتم|الگوریتمی]] وجود داشته باشد که در زمان چندجمله ایچندجمله‌ای راه حل بهینه را پیدا کند. معمولاً هنگام کار کردن با دسته NPO، مسائل بهینه سازیبهینه‌سازی جالبی وجود دارد که نسخه هاینسخه‌های تصمیم، NP-سخت هستند. توجه داشته باشید که روابط سختی، همواره در تناسب با ساده سازیساده‌سازی هستند. به علت ارتباط بین الگوریتم هایالگوریتم‌های تخمین و مسائل محاسباتی بهینه سازی،بهینه‌سازی، مسائل بهینه سازیبهینه‌سازی با نسخه هاینسخه‌های تصمیم [[ان‌پی کامل|NP-تکمیل]] لزوماً NPO-تکمیل نامیده نمی شوندنمی‌شوند.
NPOPB یک دسته دیگر است؛ NPO با تابع هزینه محدود به چندجمله ایچندجمله‌ای. مسائلی با این شرایط، ویژگی هایویژگی‌های مطلوب زیادی دارند.
== جستارهای وابسته ==
* [[نظریه پیچیدگی محاسباتی]]
* [[ان‌پی کامل]]
== منابع ==
* [http://en.wikipedia.org/w/index.php?title=Optimization_problem&oldid=468506162 ویکی پدیایویکی‌پدیای انگلیسی مسئله بهینه سازیبهینه‌سازی]
* مهدی قطعی، بهینه سازی بهینه‌سازی خطی و بهینه سازی بهینه‌سازی تر کیبیاتی، انتشارات ناقوس، 1392،۱۳۹۲، تهران، ایران.
[[رده:بهینه‌سازی ریاضی]]
| 