ⓘ مسئله بهینه‌سازی. در ریاضیات و علوم رایانه یک مسئله بهینه‌سازی، مسئله یافتن بهترین راه حل از میان همه راه حل‌های عملی می‌باشد. مسئله‌های بهینه‌سازی می‌تواند به ..

                                     

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

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

                                     

1. مسئله بهینه‌سازی پیوسته

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

minimize x f x s u b j e c t o g i x ≤ 0, i = 1, …, m h i x = 0, i = 1, …, p {\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&fx\\&\operatorname {subject\;to} &&g_{i}x\leq 0,\quad i=1,\dots,m\\&&&h_{i}x=0,\quad i=1,\dots,p\end{aligned}}}

به طوری که:

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

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

                                     

2. مسئله بهینه‌سازی ترکیبی

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

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

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

m x, y = g { m x, y ′ ∣ y ′ ∈ f x }. {\displaystyle mx,y=g\{mx,y\mid y\in fx\}.}

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

                                     

2.1. مسئله بهینه‌سازی ترکیبی مسئله بهینه‌سازی NP

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

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

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

                                     

3. منابع

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