پاورپوینت مسائل با ابعاد بزرگ و الگوريتم تجزيه

فرمت فایل : ppt(قابل ویرایش و آماده پرینت و آماده ارائه درسی)

تعداد اسلاید: 38 اسلاید

قسمتی از متن :

مسائل با ابعاد بزرگ و الگوریتم تجزیه

به طور کلی مسائل برنامه ریزی خطی به دو گروه عمده قابل تقسیم هستند: مسائل دارای ساختاری خاص و مسائل فاقد این ویژگی. شاید با بعضی از مسائل مانند مدل حمل و نقل، تخصیص و یا شبکه ها که ساختاری خاص دارند، آشنا باشید. این مسائل به علت داشتن این ویژگی امکان استفاده از الگوریتم های کارا تری از سیمپلکس را یافته و این امر موجب کاهش محاسبات می گردند.دانتزیگ (Dantzig) تکنیک های محاسباتی کارا را به منظور کاهش محاسبات به دو گروه تقسیم می کند. تکنیک هایی که موجب «کاهش تعداد تکرارها» می گردد و تکنیک هایی که «موجب فشرده شدن ماتریس معکوس» می شود. «الگوریتم اولیه - ثانویه» و «الگوریتم تجزیه» به ترتیب نمونه هایی از این دو گروه هستند.4مسائل با ساختار خاصانواع خاص مسائل برنامه ریزی خطی که در این قسمت معرفی می گردد، «مسائل بزرگ مقیاس (large-scale)» است که تعداد بسیار زیادی محدودیت و متغیر دارند. از خصوصیات مهم این گونه مسائل با ابعاد بزرگ آن است که بسیاری از ضرایب متغیرهای تصمیم در محدودیت های مسأله، صفر هستند، و در بعضی از انواع مشخص، صرفاً معدودی ضرایب غیر صفر وجود دارد. در نتیجه، به منظور ایجاد شکل ساده و کاراتری از روش سیمپلکس می توان از ساختار ریاضی خاص آنها استفاده کرد و میزان محاسبات لازم را تا حد زیادی کاهش داد. در شکل صفحه بعد چهار نوع از مسائل بزرگ مقیاس را مشاهده می کنید. در این شکل فقط ساختار ضرایب غیر صفر نشان داده شده است.1-4مسائل چند بخشیمدلی با بخش های مستقلمسائل چند دوره ایمسائل چندبخشی – چند دوره ایمدلی با بخش های مستقلاین نوع مسائل وضعیت شرکت های بزرگی را نشان می دهد که شرکت های کاملاً مستقلی را تحت پوشش داشته و هیچ نظام کنترل متمرکزی برای اداره و یا کنترل آنها به کار نمی گیرد. مدل این نوع مسائل به صورت زیر است.Max Z =