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

در روش بهینه‌سازی جورج دانتزیگ الگوریتم غیر مرکب یکی از بهترین الگوریتم‌ها برای برنامه‌ریزی خطی است.
در بهینه‌سازی ریاضیاتی، الگوریتم غیر مرکب دانتزیگ، (یا روش غیر مرکب) یک الگوریتم محبوب برای برنامه‌نویسی خطی است. مجله پردازش در علوم و مهندسی این الگوریتم را به عنوان یکی از ۱۰ الگوریتم برتر در قرن بیستم معرفی کرده‌است.
نام این الگوریتم از مفهوم یک غیر مرکب برگرفته شده و توسط ت.س.موتزگین پیشتهاد شده‌است. سیمپلیس‌ها در واقع در این الگوریتم مورد استفاده قرار نگرفته‌اند، ولی یک تفسیر از آن این است بر روی مخروط‌های سیمپلیسی، و اینها سیمپلیس‌هایی منتاسب با محدویت‌های اضافی می‌شوند. مخروط‌های سیمپلیسی مورد سؤال، گوشه‌های (یعنی در همسایگی راس‌ها) یک شی هندسی که یک پولی توپ نامیده می‌شوند. شکل این پولی توپ توسط قیدهای ایجاد شده در تابع هدف، مشخص می‌شود.

مرور

الگوریتم غیر مرکب بر روی برنامه‌هایی در فرم استاندارد عمل می‌کند؛ مسئله‌های خطی به این فرم،
کمینه شده
مشروط بر این که:
 با وجود متغیرهای مسئله،  ضریب‌های تابع گفته شده می‌باشند، ماتریس A، یک ماتریس p*n می‌باشد و ثابت‌های  که . یک شیوهٔ مستقیم برای تبدیل هر برنامه خطی به حالت استاندارد وجود دارد که این در از بین رفتن عمومیت تأثیری ندارد.
در اصطلاحات هندسی، منطقه محتمل
یک (به احتمالی بیکران) پولی توپ محدب است. یک توصیف صفاتی ساده از نقاط کرانی رأس‌های این پولی توپ وجود دارد ،
 یک نقطه کرانی است اگر و فقط اگر ستون بردارهای، جایی که به صورت خطی غیر مستقل باشند. در این مبحث، چنین نقطه‌ای به عنوان یک راه حل پایه‌ای امکان‌پذیر(BFS) شناخته می شود.
می‌توان نشان داد که برای یک برنامه خطی در فرم استاندارد، اگر تابع مقصود یک مقدار کمینه در منطقه محتمل داشته باشد، در نتیجه این مقدار را روی (حداقل) یکی از نقاط کرانی خواهد داشت. این در عنوان خودش مسئله را به یک پردازش با حالت محدود تبدیل می‌کند، زیرا تعداد محدودی از نقاط کرانی وجود دارند، در هر حال تعداد نقاط کرانی به‌طور غیرقابل کنترلی برای کوچکترین برنامه‌های خطی نیز بزرگ است.
همچنین می‌توان نشان داد که اگر یک نقطه کرانی، نقطه کمینه تابع مقصود نیست، در نتیجه یک گوشه‌ای وجود دارد که نقطه را در بر می‌گیرد به شکلی که تابع مقصود اکیداً نزولی است بر روی گوشه‌ای که از نقطه دور می‌شود. اگر گوشه کراندار باشد، گوشه به نقطه‌ای دیگر در جایی که تابع مقصود مقدار کمتری دارد، متصل می‌شود، در غیر این صورت تابع مقصود زیر گوشه بی‌کران است و برنامه خطی هیچ راه حلی ندارد. الگوریتم غیر مرکب، این بینش را با گذشتن از تمامی گوشه‌های پولی توپ به نقطه‌های کرانی با مقادیر کمر تابعی، به وجود می‌آورد. این ادامه پیدا می‌کند تا وقتی که به مقدار کمینه دست پیدا کند، یا یک راس بی‌کران، مشاهده شود، این کار ادامه پیدا می‌کند، و این نتیجه‌گیری می‌شود که مسئله جوابی ندارد. الگوریتم همیشه به مام می‌رسد به این دلیل که تعداد رأس‌های پولی توپ، متناهی است؛ همچنین به خاطر این که بین رئوس در یک جهت پرش می‌کنیم، امید داریم که تعداد رئوس پیمایش شده، کم باشد.
راه حل یک برنامه خطی در دو مرحله به اجرا می‌رسد. در مرحله اول، که به فاز شناخته می‌شود، یک نقطه کرانی برای شروع جستجو ی شود. وابسته به طبیعت برنامه، این ممکن است کاری ناچیز باشد ولی عموماً با ارائه الگوریتم غیر مرکب به یک نسخه تصحیح شده نسبت به برنامه اولیه، این مسئله قابل حل است. نتایج محتمل فاز ۱، یا یک راه حل پایه‌ای عملی که پیدا می‌شود یا این که ناحیه محتمل خالی است. در مرحله دوم، فاز ۲، الگوریتم غیرمرکب به این گونه اعمال می‌شود که راه حل پایه‌ای عملی در فاز ۱ به عنوان نقطه شروع به آن داده می‌شود. نتایج محتمل در فاز ۲ یا یک راه حل پایه‌ای و عملی بهینه است یا یک گوشه بی‌کران که تابع مقصود در زیر آن بی‌کران است.

عملیات محوری

عملیات هندسی جابجایی از یک راه حل محتمل به یک راه حل پایه‌ای محتمل همجوار، با عملیات محوری پیاده‌سازی می‌شود. ابتدا، یک عنصر محوری غیر صفر در یک ستون غیر پایه‌ای انتخاب می‌شود. ردیفی که این عنصر را دربردارد ضربدر معکوس آن می‌شود تا این عنصر به ۱ تبدیل شود، و سپس ضرب شده‌های ردیف با ردیف‌های دیگر برای تغییر ورودی‌های ستون به صفر، جمع می‌شوند. نتیجه این می‌شود که، اگر عنصر محوری در ردیف r قرار دارد، در نتیجه ستون، r امین ستون ماتریس هویت خواهد بود. متغیر این ستون الان یک متغیر پایه‌ای است که با متغیری که متناظر با ستون r ام ماتریس هویت، جابجا می‌شود، البته قبل از عملیات. در حقیقت، متغیر متناظر با ستون محوری وارد دستهٔ متغیرهای پایه‌ای شده و نام آن می‌شود متغیر رونده. جدول همچنان به فرم مخروطی است ولی با مجموعه‌ای از متغیرهای پایه‌ای که با یک عنصر تغییر پیدا کرده‌اند.