الگوریتم غیرمرکب

دانشنامه عمومی

در روش بهینه سازی جورج دانتزیگ الگوریتم غیر مرکب یکی از بهترین الگوریتم ها برای برنامه ریزی خطی است. [ ۱] [ ۲] [ ۳] [ ۴] [ ۵]
در بهینه سازی ریاضیاتی، الگوریتم غیر مرکب دانتزیگ، ( یا روش غیر مرکب ) یک الگوریتم محبوب برای برنامه نویسی خطی است. مجله پردازش در علوم و مهندسی این الگوریتم را به عنوان یکی از ۱۰ الگوریتم برتر در قرن بیستم معرفی کرده است. [ ۶] نام این الگوریتم از مفهوم یک غیر مرکب برگرفته شده و توسط ت. س. موتزگین[ ۷] پیشتهاد شده است. سیمپلیس ها در واقع در این الگوریتم مورد استفاده قرار نگرفته اند، ولی یک تفسیر از آن این است بر روی مخروط های سیمپلیسی، و اینها سیمپلیس هایی منتاسب با محدویت های اضافی می شوند. مخروط های سیمپلیسی مورد سؤال، گوشه های ( یعنی در همسایگی راس ها ) یک شی هندسی که یک پولی توپ نامیده می شوند. [ ۸] [ ۹] [ ۱۰] [ ۱۱] شکل این پولی توپ توسط قیدهای ایجاد شده در تابع هدف، مشخص می شود.
الگوریتم غیر مرکب بر روی برنامه هایی در فرم استاندارد عمل می کند؛ مسئله های خطی به این فرم، کمینه شده
c ⋅ x
مشروط بر این که:
A x = b , x i ≥ 0
x = ( x 1 , … , x n ) با وجود متغیرهای مسئله، c = ( c 1 , … , c n ) ضریب های تابع گفته شده می باشند، ماتریس A، یک ماتریس p*n می باشد و ثابت های b = ( b 1 , … , b p ) که b j ≥ 0 . یک شیوهٔ مستقیم برای تبدیل هر برنامه خطی به حالت استاندارد وجود دارد که این در از بین رفتن عمومیت تأثیری ندارد. در اصطلاحات هندسی، منطقه محتمل
یک ( به احتمالی بیکران ) پولی توپ محدب است. یک توصیف صفاتی ساده از نقاط کرانی رأس های این پولی توپ وجود دارد ، x = ( x 1 , … , x n ) یک نقطه کرانی است اگر و فقط اگر ستون بردارهای A i ، جایی که به صورت خطی غیر مستقل باشند. در این مبحث، چنین نقطه ای به عنوان یک راه حل پایه ای امکان پذیر ( BFS ) شناخته می[ ۱۲] شود.
می توان نشان داد که برای یک برنامه خطی در فرم استاندارد، اگر تابع مقصود یک مقدار کمینه در منطقه محتمل داشته باشد، در نتیجه این مقدار را روی ( حداقل ) یکی از نقاط کرانی خواهد داشت. [ ۱۳] این در عنوان خودش مسئله را به یک پردازش با حالت محدود تبدیل می کند، زیرا تعداد محدودی از نقاط کرانی وجود دارند، در هر حال تعداد نقاط کرانی به طور غیرقابل کنترلی برای کوچکترین برنامه های خطی نیز بزرگ است. [ ۱۴]
عکس الگوریتم غیرمرکبعکس الگوریتم غیرمرکب
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس