پاورپوینت برنامه ریزی خطی پیشرفته (21715)

پاورپوینت برنامه ریزی خطی پیشرفته (21715) (pptx) 37 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

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

قسمتی از متن PowerPoint (.pptx) :

1 بنام خدا برنامه ریزی خطی پیشرفته (21715) Advanced Linear Programming Lecture 6 Computational Complexity of the Simplex Algorithm 2 برنامه ریزی خطی پیشرفته (21715( گسترش شاخه های مختلف تحقیق درعملیات مانند برنامه ریزی خطی، برنامه ریزی غیر خطی و... ارایه روش های حل مختلف برای حل هر یک از شاخه ها نیاز به مقایسه و دسته بندی مناسب این نوع مساله ها و همچنین روش های حل ابداع شده برای حل آنها از لحاظ پیچیدگی و سختی محاسباتی 3 برنامه ریزی خطی پیشرفته (21715( توسعه تئوری پیچیدگی یک مساله بر پایه چارچوب ریاضی توسط منتقدان و دانشمندان علوم کامپیوتر تعریف های مقدماتی مساله (Problem): دسته ای از مساله های مشابه که حالت عمومی دارند. عبارتی که نیازمند اثبات و یا روش حل است. مثال: مساله تخصیص، حمل و نقل و یا مساله های متفاوت توالی عملیات مساله نمونه :(Instance) مثالی عددی از مساله مورد بررسی اندازه مساله نمونه (Size): طول رشته داده های مورد نیاز برای توصیف مساله نمونه 4 برنامه ریزی خطی پیشرفته (21715( ابداع بحث محاسبه پیچیدگی عملیاتی مساله ها و الگوریتم های تحقیق در عملیات توسط دانشمدان علوم کامپیوتر و تحقیق در عملیات از دهه هفتاد میلادی هدف از محاسبه پیچیدگی یک الگوریتم این است که تعداد محاسبه های ریاضی، مقایسه های مورد نیاز و یا سایر عملیات مورد نیاز برای حل یک مساله به کمک یک الگوریتم خاص مشخص شود. در این روش ها مساله یا الگوریتم مورد بحث بر اساس بدترین حالت ممکن برای حل و یا متوسط تعداد عملیات مورد نیاز برای حل ارزیابی می شود. 5 برنامه ریزی خطی پیشرفته (21715( این ارزیابی بر پایه اندازه گیری تابعی انجام می شود که بر پایه اندازه مساله ایجاد می شود. در این روش مقدار افزایش سختی حل مساله با بزرگ شدن اندازه مساله ارزیابی می شود. این محاسبه بیشینه تعداد عملیات مورد نیاز برای حل مساله و یا متوسط آن را نشان می دهد. 6 برنامه ریزی خطی پیشرفته (21715( مساله برنامه ریزی خطی زیر را در نظر بگیرید: Max Z = Cx Ax=b x ≥ 0 فرض کنید Am*n فرض کنید تمامی اعداد پارامترهای مساله بصورت عدد صحیح باشند. فرض عدد صحیح بودن پارامترها فرض امکان پذیری است. 7 برنامه ریزی خطی پیشرفته (21715( تعریف ها: اندازه یک مساله برنامه ریزی خطی: اندازه یک مساله برنامه ریزی خطی مشخص می کند که چه مقدار فضا (چند بیت) از فضای کامپیوتر برای تعریف مساله برنامه ریزی خطی لازم است. به عنوان مثال برای نمایش عدد 75 که میان 26 و 27 است به هفت بیت از حافظه کامپیوتر برای نمایش احتیاج داریم. در حالت کلی تعداد بیت برای محاسبه نمایش یک عدد مانند a را بصورت زیر محاسبه می کنیم: 2r ≤ a ≤2r+1 r ≤ log2 a ≤ r +1 8 برنامه ریزی خطی پیشرفته (21715( فاکتور پیچیدگی هر الگوریتم بر حسب تعداد عملیات محاسباتی مورد نیاز برای تکمیل آن محاسبه می شود. در مساله های برنامه ریزی خطی مشخص است که با افزایش تعداد متغیرهای تصمیم (n) و محدودیت های (m)مساله پیچیدگی مساله افزایش پیدا می کند. حتی در صورتی که تعداد متغیرهای تصمیم و محدودیت های مساله ثابت باشند، با تغییر مقدار پارامترهای مساله پیچیدگی مساله تغییر می کند. 9 برنامه ریزی خطی پیشرفته (21715( در این حالت اندازه یک مساله برنامه ریزی خطی با تابعی بصورت (m, n, L) نمایش داده می شود. در رابطه فوق L برابر تعداد بیت هایی است که برای ثبت مساله برنامه ریزی خطی در کامپیوتر لازم است.