\documentclass[oneside,a4paper,12pt]{book}
\usepackage{xepersian}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{fancyhdr}
\usepackage[onehalfspacing]{setspace}
\usepackage{pifont}
\renewcommand{\baselinestretch}{1.5}\normalsize
\begin{document}
\setcounter{chapter}{1}
\appendix
\chapter[روش‌های بهینه‌سازی دقیق]{روش‌های بهینه‌سازی دقیق}\label{}
\section{معرفی}
مسائل برنامه‌ریزی و زمان‌بندی به‌طور ذاتی ساده‌اند و به‌صورت برنامه‌ریزی خطی که به‌آسانی قابل حل در الگوریتم‌های موجود کارا هستند قابل فرمول‌بندی می‌باشند. این الگوریتم‌های کارا معمولا به‌عنوان الگوریتم‌های چندجمله‌ای زمان معرفی می‌شوند. این مسئله می‌تواند توسط یک الگوریتم کارا و زمان چندجمله‌ای حل شود، که مثال‌های خیلی بزرگ‌ از‌ آن مسئله با صدها یا هزاران فعالیت می‌توانند در یک مدت زمان نسبتا کوتاه در یک کامپیوتر حل شود.\\
از این رو، بسیاری از مسائل برنامه‌ریزی وجود دارند که ذاتا بسیار سخت می‌باشند. این مسائل به عنوان مسائل $NP-hard$ معرفی می‌شوند. این مسائل معمولا مسايل ترکیبی هستند که نمی‌توانند با مسائل خطی حل شوند و هیچ قانون یا الگوریتم ساده‌ای که جواب‌های بهینه در مدت زمان محدود کامپیوتر به‌دست آورد وجود ندارد. اغلب ممکن است که برنامه عددصحیح یا برنامه ریزی گسسته مناسبی برای چنین مسائلی وجود داشته باشد، اما حل اینگونه مسائل ممکن است به یک زمان بسیار زیاد کامپیوتری نیاز داشته باشد. \\
دسته‌های متنوع و مفیدی از روش‌ها برای به‌دست آورردن جواب‌های بهینه برای اینچنین مسائل $NP-hard‌$ وجود دارد. یکی از این دسته‌ها، روش‌های برنامه‌ریزی پویا را معرفی می‌کند. برنامه‌ریزی پویا یکی از گسترده‌ترین تکنیک‌های مورد استفاده برای پرداختن به مسائل بهینه‌سازی ترکیبی است. برنامه‌ریزی پویا روشی است که برپایه‌ی رویکرد تقسیم و موفقیت می‌باشد. برنامه‌ریزی پویا برای مسائلی که قابل حل در  زمان چندجمله ای هستند به‌خوبی مسائل $NP-hard$ می‌توانند به‌کار برده شوند.\\
اگر یک مسئله‌ برنامه‌ریزی بتواند توسط یک برنامه‌ریزی عددصحیح فرموله شود، آنگاه از تکنیک‌های مختلف دیگری نیز قابل اجرا است. شناخته شده‌ترین روش‌ها برای حل برنامه‌ریزی عدد صحیح، عبارت‌اند از:
\begin{enumerate}
\item روش‌های شاخه وکران 
\item  روش‌های چندسطحی برش
\item   روش‌های ترکیبی 
\end{enumerate}
اولین دسته از روش‌ها، شاخه و کران است که یکی از محبوب‌ترین دسته‌ها از تکنیک‌های مورد استفاده برای برنامه‌ریزی عدد صحیح است. شاخه‌کردن یک تقسیم‌بندی از فضای جواب ارائه می‌دهد و هر بخش از فضای جواب به‌طور مجزا درنظر گرفته می‌شود. محدود کردن (کرانی کردن) توسعه کران‌ها را برای بخش‌هایی از فضای جواب معرفی می‌کند( با فرض مینیمم کردن هدف). اگر کران پایینی یافت شود که در یک بخش از فضای جواب بزرگ‌تر از جواب صحیحی باشدکه قبلا در بخش دیگری از فضای جواب به‌دست آمده است، آنگاه بخش مربوط به کران بزرگتر می‌تواند نادیده گرفته شود. \\
دومین دسته از روش‌ها، روش‌های برنامه‌ریزی برش و تمرکز بر آزادسازی برنامه‌ریزی خطی در برنامه‌ریزی عدد صحیح است. این روش‌ها محدودیت‌های خطی اضافی را تولید می‌کنند، یعنی برنامه‌ریزی برش برای متغییرهایی که بایستی صحیح شوند اعمال می‌شود. تعداد نامعادلات محدودیت‌های اضافی مجموعه‌ی شدنی بیشتر از نامعادلات مجموعه‌های اصلی خطی بدون برش در جواب‌های صحیح است. حل کردن آزادسازی
$LP$
از
$IP$
با محدودیت‌های اضافی یک جواب جدید را به‌دست می‌دهد که ممکن است صحیح باشد. اگر جواب صحیح باشد، روش متوقف می‌شود و جواب به‌دست آمده به‌عنوان جواب نهایی برای مسئله اصلی
$IP$
است. اگر متغییرها عدد صحیح نباشند معادلات بیشتری ایجاد می‌شود.\\
روش‌های ترکیبی معمولا ترکیب ایده‌هایی از روش‌های متنوع و مختلف است. به‌عنوان مثال روش برنامه‌ریزی صفحه برش در سال‌های اخیر در میان استفاده کنندگان از این روش در ترکیب با شاخه و کران محبوب‌اند. وقتی روش شاخه و کران در تکنیک‌های برنامه‌ریزی برش استفاده می‌شود، آن‌را به‌عنوان شاخه و برش معرفی می‌کنند.
\section{برنامه‌ریزی پویا}
برنامه‌ریزی پویا اساساً یک برنامه شمارشی کامل است که از طریق یک روش تقسیم و موفقیت، برای به حداقل رساندن مقدار مورد محاسبه، تلاش می‌کند. روش حداقل‌‌کردن یک سری از زیرمسئله‌ها تا یافتن یک جواب برای مسئله اصلی است. جواب بهینه را برای هر زیرمسئله و سهم آن در تابع هدف را تعیین می‌کند. در هر تکرار جواب بهینه را برای یک زیرمسئله فعلی با استفاده از تمام اطلاعاتی که قبلاً در جواب‌های همه‌ی زیر مسئله‌های قبلی به‌دست‌ آمده است پیدا می‌کند.\\
 برنامه‌ریزی پویا با سه نوع معادله مشخص می‌شود. یعنی
\begin{enumerate}
\item شرایط اولیه
\item رابطه بازگشتی و
\item مقدار تابع بهینه 
\end{enumerate}
در برنامه‌ریزی پویا برای انتخاب یک گزینه، می‌توان از برنامه‌ریزی پویای پیشرو و برنامه‌ریزی پویای پسرو استفاده نمود. مثال زیر یک برنامه‌ریزی پویای پیشرو را نشان می‌دهد.\\
\textbf{مثال ب.2.1(فرمول برنامه‌ریزی پویای پیشرو)}.
یک ماشین و $n$ فعالیت را درنظر بگیرید. اگر فعالیت
$j$
در زمان
$C_j$
کامل شود و یک هزینه
$h_j(C_j)$
در برداشته باشد. مسئله مورد بررسی این است که کارها به‌گونه‌ای ترتیب داده شوند که هدف
\begin{equation*}
\sum_{j=1}^n h_j(C_j)
\end{equation*}
حداقل شود. این مسئله، یک مسئله بسیار مهم در نظریه برنامه‌ریزی است که شامل بسیاری از توابع هدف مهم در موارد خاص است، می‌باشد. به عنوان مثال، هدف یک تعمیمی از هدف  است، که از این رو یک مسئله
$NP-hard$
می‌باشد. فرض کنید
$j$
یک زیر مجموعه از 
$n$
فعالیت باشد و فرض کنید که همه‌ی فعالیت‌هایی که در 
$j$
هستند قبل از هر یک از فعالیت‌هایی که در مجموعه 
$j$
نیستند انجام شوند.
فرض کنید
\begin{equation*}
V(J)=\sum_{j\in J} h_j(C_j)
\end{equation*}
مجموعه‌ای از فعالیت‌های  $j$باشند که در ابتدا انجام شوند. فرمول برنامه‌ریزی پویا در مسئله به شرایط اولیه، مقدار تابع هدف و رابطه بازگشتی بستگی دارد.\\
\textit{شرایط اولیه:}
\begin{equation*}
V({j})=h_j(p_j) \hspace*{1.5cm}  j=1,2,...,n
\end{equation*}
\textit{رابطه بازگشتی:}
\begin{equation*}
V(J)=\min_{j\in J}\Big (V(J-\{j\})+h_j(\sum_{k\in J}p_k)\Big)
\end{equation*}
\textit{مقدار تابع بهینه:}
\begin{equation*}
V(\{1,...,n\})
\end{equation*}
ورای این روش برنامه‌ریزی پویا نسبتاً آسان است. در هر عمل از توالی بهینه برای یک زیرمجموعه از فعالیت‌ها (یک زیر مجموعه
$j$
که شامل
$L$
فعالیت است) تعیین می‌شود و فرض می‌شود این زیرمجموعه در ابتدا اعمال شود. این روند برای هرزیر مجموعه با اندازه
$L$
انجام می‌شود. که
$n!/ (l!(n-l)!)$
زیرمجموعه می‌باشد. برای هر زیرمجموعه، سهم
$L$
برنامه‌ریزی شده‌ی فعالیت‌ها برای تابع هدف محاسبه می‌شود. از طریق رابطه‌ بازگشتی به همه‌ی زیرمجموعه‌هایی که شامل
$L+1$
فعالیت است، گسترش داده می‌شود. هریک از
$L+1$
فعالیت به عنوان یک کاندیدا که در ابتدا باید انجام شود، در نظر گرفته می‌شود. وقتی که با استفاده از رابطه بازگشتی توالی واقعی
$L$
فعالیت از زیرمجموعه‌های کوچکتر مورد توجه قرار نمی‌گیرد، تنها بخشی از فعالیت‌های
$L$
در هدف شناخته می‌شود. پس از اینکه ارزش
$V(\{1,2,\ldots,n\})$
مشخص شد، توالی بهینه از طریق یک روش پسرو و ساده به‌دست می‌آید.\\
$V(J)$
باید برای همه‌ی زیرمجموعه‌هایی که شامل
$L$
فعالیت می‌باشد مشخص شود. که به تعداد
$n!/ (l!(n-l)!)$
زیرمجموعه است. همچنین مجموع اعداد تخمینی که بایستی انجام شود نیز
\begin{equation*}
\sum_{l=1}^n \dfrac{n!}{l!(n-l)!}=O(2^n)
\end{equation*}
می‌باشد.\\[0.7cm]
\textbf{مثال ب.2.2(کاربرد برنامه‌ریزی پویای پیشرو)}.
مسئله‌ی مثال قبل را با فعالیت‌های زیر درنظر بگیرید.
\begin{center}
\addtolength{\tabcolsep}{12pt}
\begin{tabular}{1111}
\hline فعالیت‌ها & 1 & 2 & 3\\ \hline $p_j$ & 4 & 3 & 6\\  $h_j(C_j)$ & $C_1 +C_^2$ & $3+C_2^3$ & $8C_3$ \\ \hline 
\end{tabular}
\end{center}
همچنین
$V(\{1\})=20$
و
$V(\{2\})=30$
و
$V(\{3\})=48$
هستند. دومین اثر متقابل روش همه مجموعه‌های شامل 2 فعالیت را درنظر بگیرید. به‌کار بردن رابطه بازگشتی حاصل می‌دهد:
\begin{equation*}
V(\{1,2\})=\min \Big(V(\{1\})+h_2(P_1+P_2), V(\{2\})+h_1(P_2+P_1)\Big)
\end{equation*}
\begin{equation*}
=\min(20+346, 30+56)=86 
\end{equation*}
\section{روش‌های بهینه‌سازی برای برنامه‌ریزی عدد صحیح}
\section{مثال‌هایی از کاربردهای شاخه و کران}
\end{document}