موضوع مقاله: الگوریتم غیرمرکب | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم غیرمرکب | مقدمه: در روش بهینه‌سازی جورج دانتزیگ الگوریتم غیر مرکب یکی از بهترین الگوریتم‌ها برای برنامه‌ریزی خطی است.Richard W. | ## بخش 1: الگوریتم غیرمرکب | 1, 2000 نام این الگوریتم از مفهوم یک غیر مرکب برگرفته شده و توسط ت.س.موتزگین پیشتهاد شده‌است. سیمپلیس‌ها در واقع در این الگوریتم مورد استفاده قرار نگرفته‌اند، ولی یک تفسیر از آن این است بر روی مخروط‌های سیمپلیسی، و اینها سیمپلیس‌هایی منتاسب با محدویت‌های اضافی می‌شوند. مخروط‌های سیمپلیسی مورد سؤال، گوشه‌های (یعنی در همسایگی راس‌ها) یک شی هندسی که یک پولی توپ نامیده می‌شوند. یک شیوهٔ مستقیم برای تبدیل هر برنامه خطی به حالت استاندارد وجود دارد که این در از بین رفتن عمومیت تأثیری ندارد. یک توصیف صفاتی ساده از نقاط کرانی رأس‌های این پولی توپ وجود دارد ، یک نقطه کرانی است اگر و فقط اگر ستون بردارهای، جایی که به صورت خطی غیر مستقل باشند. در این مبحث، چنین نقطه‌ای به عنوان یک راه حل پایه‌ای امکان‌پذیر(BFS) شناخته می شود. می‌توان نشان داد که برای یک برنامه خطی در فرم استاندارد، اگر تابع مقصود یک مقدار کمینه در منطقه محتمل داشته باشد، در نتیجه این مقدار را روی (حداقل) یکی از نقاط کرانی خواهد داشت. این در عنوان خودش مسئله را به یک پردازش با حالت محدود تبدیل می‌کند، زیرا تعداد محدودی از نقاط کرانی وجود دارند، در هر حال تعداد نقاط کرانی به‌طور غیرقابل کنترلی برای کوچکترین برنامه‌های خطی نیز بزرگ است. همچنین می‌توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه‌ای وجود دارد که نقطه را در بر می‌گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه‌ای که از نقطه دور می‌شود. اگر گوشه کراندار باشد، گوشه به نقطه‌ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می‌شود، در غیر این صورت تابع مقصود زیر گوشه بی‌کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه‌های پولی توپ به نقطه‌های کرانی با مقادیر کمر تابعی، به وجود می‌آورد. این ادامه پیدا می‌کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی‌کران، مشاهده شود، این کار ادامه پیدا می‌کند، و این نتیجه‌گیری می‌شود که مسئله جوابی ندارد. الگوریتم همیشه به مام می‌رسد به این دلیل که تعداد رأس‌های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می‌کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد. | ## بخش 2: الگوریتم غیرمرکب | وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز ۱، یا یک راه حل پایه‌ای عملی که پیدا می‌شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز ۲، الگوریتم غیرمرکب به این گونه اعمال می‌شود که راه حل پایه‌ای عملی در فاز ۱ به عنوان نقطه شروع به آن داده می‌شود. نتایج محتمل در فاز ۲ یا یک راه حل پایه‌ای و عملی بهینه است یا یک گوشه بی‌کران که تابع مقصود در زیر آن بی‌کران است.Robert J. فرم استاندارد تبدیل یک برنامه خطی به یکی به حالت استاندارد، می‌تواند به صورت مقابل اعمال شود. ابتدا برای هر متغیر با یک کران پایین‌تر به غیر از صفر، یک متغیر جدید معرفی می‌شود که نشانگر تفاوت بین متغیر و حد می‌باشد. برای مثال، داده شده با این محدودیت با متغیر جدید، y۱، که برابر است با تساوی دوم برای حذف x_۱ از برنامه خطی استفاده می‌شود. دوم، برای هر قید باقی‌مانده، یک متغیر جدید به نام متغیر اسلَک، معرفی می‌شود که هر قید را به یک قید تساوی تبدیل می‌کند. برای مثال این نامساوی‌ها با این جایگزین می‌شود راه آسانتر این است که دستکاری جبری بر روی نامساوی‌ها در این فرم انجام شود. در نامساوی‌هایی که ≥ وجود دارد مانند نامساوی دوم، بعضی نویسندگان ارجاع می‌دهند به متغیری که به متغیر surplus معروف است. این می‌تواند به دو راه انجام شود، یکی با حل کردن مسئله برای متغیری در یکی از تساوی‌ها یی که وجود دارد و سپس حذف متغیر با جایگزینی. برای مثال اگر z_۱ بدون قید است کس می‌نویسیم این تساوی برای حذف z_۱ از برنامه خطی استفاده می‌شود. زمانی که پروسه به اتمام می‌رسد، منطقه محتمل به فرم زیر خواهد بود Ax=b,x_i≥۰ همچنین بهتر است که درچه A را تعداد ردیف‌ها در نظر بگیریم. | ## بخش 3: الگوریتم غیرمرکب | این به هیچ وجه باعث از بین رفتن عمومیت نمی‌شود، زیرا در هر حال یا: دارای تساوی‌های اضافی است که می‌توان آن‌ها را حذف کرد، یا سیستم متناقض است و دستگاه خطی هیچ راه حلی ندارد. جدول مخروطی یک دستگاه خطی به فرم استاندارد می‌تواند به صورت ماتریسزیر نمایش داده شود ردیف اول نمایانگر تابع مقصود و باقی ردیف‌ها نشانگر قیدها هستند. (در نظر داشته باشید، نویسنده‌های مختلف، روش‌های مختلفی برای برای نوشتن این دستگاه استفاده می‌کنند)اگر ستون‌های A بتوانندبه گونه‌ای چیده شوند که دربر گیرنده ماتریس هویت باشند که از درجه Pاست (تعداد سطرها در A)در نتیجه جدول یا ماتریس در حالت مخروطی قرار دارد. متغیرهای نظیر ستون‌های ماتریس هویت، متغیرهای پایه‌ای نامیده می‌شوند، در حالی که باقی متغیرها غیرپایه ای یا متغیرهای آزاد هستند. اگر متغیرهای غیر پایه‌ای صفر در نظر گرفته شوند، مقادیر متغیرهای پایه‌ای به راحتی قابل بدست آمدن هستند، به این گونه که با گرفتن ورودی‌هایی در b ، راه حل یک راه حل پایه‌ای محتمل است. برعکس، با داشتن یک راه حل امکان‌پذیر، ستون‌های نظیر متغیرهای غیر صفر می‌توانند به یک ماتریس غیر منفرد ارتقا داد. تغییر شکل اضافی جمع سطرها می‌تواند برای حذف ثابت‌های c TB از تابع مقصود به کار می‌رود. ضریب‌های به روز شده، که با نام ضریب‌های متناسب هزینه اینیز شناخته می‌شوند، نرخ تغییرات تابع مقصود با توجه به متغیرهای غیر پایه‌ای، هستند.Evar D. (elementary) عملیات محوری عملیات هندسی جابجایی از یک راه حل محتمل به یک راه حل پایه‌ای محتمل همجوار، با عملیات محوری پیاده‌سازی می‌شود. ردیفی که این عنصر را دربردارد ضربدر معکوس آن می‌شود تا این عنصر به ۱ تبدیل شود، و سپس ضرب شده‌های ردیف با ردیف‌های دیگر برای تغییر ورودی‌های ستون به صفر، جمع می‌شوند. نتیجه این می‌شود که، اگر عنصر محوری در ردیف r قرار دارد، در نتیجه ستون، r امین ستون ماتریس هویت خواهد بود. متغیر این ستون الان یک متغیر پایه‌ای است که با متغیری که متناظر با ستون r ام ماتریس هویت، جابجا می‌شود، البته قبل از عملیات. در حقیقت، متغیر متناظر با ستون محوری وارد دستهٔ متغیرهای پایه‌ای شده و نام آن می‌شود متغیر رونده. | ## جمع‌بندی | جدول همچنان به فرم مخروطی است ولی با مجموعه‌ای از متغیرهای پایه‌ای که با یک عنصر تغییر پیدا کرده‌اند.