بخشی از پاورپوینت
اسلاید 1 :
بنام خدا
برنامه ریزی خطی پیشرفته (21715)
Advanced Linear Programming
اسلاید 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 برابر تعداد بیت هایی است که برای ثبت مساله برنامه ریزی خطی در کامپیوتر لازم است.
اسلاید 10 :
برنامه ریزی خطی پیشرفته (21715(
اندازه یک مساله برنامه ریزی خطی از رابطه زیر محاسبه می شود:
در رابطه فوق مقدارهای m و n با اضافه کردن متغیرهای لنگی و مصنوعی هستند.
اسلاید 11 :
برنامه ریزی خطی پیشرفته (21715(
با خلاصه سازی مطالب بیان شده نتیجه می گیریم که برای مقایسه پیچیدگی الگوریتم ها معمولا از دو روش استفاده می کنند که عبارتند از:
روش بدترین حالت (The worst Case)
روش میانه (The Average Case)
اسلاید 12 :
برنامه ریزی خطی پیشرفته (21715(
روش بدترین حالت (The Worst Case)
در این نوع ارزیابی طولانی ترین حالت ممکن برای حل مساله در نظر گرفته شده و تعداد عملیات مورد نیاز برای انجام آن در نظر گرفته می شود.
در موارد زیادی مقایسه الگوریتم ها بر مبنای این روش انجام می شود.
روشی متداول برای بررسی کارایی الگوریتم ها در دهه های 60 الی 90 میلادی
اسلاید 13 :
برنامه ریزی خطی پیشرفته (21715(
روش میانه (The Average Case)
در این روش برای تعداد زیادی از مساله های نمونه روش مورد بحث برای حل به کار گرفته شده و تعداد عملیات انجام شده برای حل مساله محاسبه می شود.
از اشکال های این روش تعریف مساله های مختلف نمونه است که نمی توان مساله هایی تعریف کرد که تمامی حالت ها را در نظر بگیرد.
این روش برای مقایسه عملکرد الگوریتم ها در مواردی به کار می رود.
اسلاید 14 :
برنامه ریزی خطی پیشرفته (21715(
مشکلات استفاده از روش میانه
اگر چه استدلال در مورد پیچیدگی یک الگوریتم از این روش معقول تر به نظر می رسد، ولی دارای مشکلات زیر هنگام کاربرد است:
تعریف مساله متوسط چیست؟
تعریف عملیات چیست؟
آیا مساله های نمونه ایجاد شده نماینده مساله های واقعی هستند (تعداد مساله های تصادفی تبهگن و تعداد مساله های واقعی تبهگن)؟
اسلاید 15 :
برنامه ریزی خطی پیشرفته (21715(
عملکرد الگوریتم سیمپلکس
از ابتدای توسعه الگوریتم سیمپلکس سوال اصلی این بود که عملکرد این الگوریتم برای حل مساله های برنامه ریزی خطی چگونه است.
تجربه های عملی حل مساله های واقعی دال بر قابل قبول بودن این الگوریتم حتی برای حل مساله های بزرگ و پیچیده داشت.
محاسبات پیچیدگی الگوریتم سیمپلکس برای روش بدترین حالت مساله ای را خلاف این امر بیان می کرد.
اسلاید 16 :
برنامه ریزی خطی پیشرفته (21715(
عملکرد الگوریتم سیمپلکس(ادامه)
این تفاوت باعث ایجاد سوال های متعددی شد.
الگوریتم سیمپلکس الگوریتمی است که در اندازه گیری شاخص بدترین حالت ممکن دارای عملکرد مناسبی نبوده ولی در شاخص average case بسیار مناسب عمل می کند.
توجه کنید روش های مناسبی برای اندازه گیری پیچیدگی الگوریتم ها بر اساس شاخص average case وجود ندارد.
اسلاید 17 :
برنامه ریزی خطی پیشرفته (21715(
عملکرد الگوریتم سیمپلکس(ادامه)
روش بدترین حالت در مورد الگوریتم سیمپلکس به این معنی است که برای رسیدن به جواب بهینه تمامی گوشه های مساله امتحان شوند.
با توجه به زیاد بودن تعداد گوشه ها در مساله های برنامه ریزی خطی می توان بیان کرد که عملکرد الگوریتم سیمپلکس بر مبنای شاخص بدترین حالت، حداقل از دیدگاه تئوری روش مناسبی نیست.
اسلاید 18 :
برنامه ریزی خطی پیشرفته (21715(
عملکرد الگوریتم سیمپلکس(ادامه)
زمان برترین بخش فعالیت الگوریتم سیمپلکس قدم های حرکت از یک جدول(گوشه) به جدول دیگر است.
لذا اندازه گیری محاسبه های لازم برای حل یک مساله برنامه ریزی خطی باید به این صورت انجام شود که چه تعداد تکرار برای حل مساله لازم است.
اگر گوشه موجه ابتدایی موجود نباشد، حجم این محاسبه ها بیشتر می شود.
اسلاید 19 :
برنامه ریزی خطی پیشرفته (21715(
پاسخ به این سوال بستگی به تعداد متغیرهای تصمیم، محدودیت های مساله، مقدار پارامترهای مساله و جواب موجه ابتدایی دارد.
به زبان حرفه ای تر: میانگین تعداد تکرارهای مورد نیاز برای حل یک مساله برنامه ریزی خطی بر پایه تعداد متغیرهای تصمیم، محدودیت ها و اندازه مساله چقدر است؟
پاسخ به مقدار این تابع یک سوال آماری بوده که پاسخ دقیق به آن بسیار مشکل است.
اسلاید 20 :
برنامه ریزی خطی پیشرفته (21715(
محاسبه پیچیدگی الگوریتم سیمپلکس با شاخص average case روش آسانی نیست.
بر پایه تحقیقی که سالهای گذشته با حل تعداد بسیار زیادی مساله صورت گرفته است بصورت تقریبی مشاهده شده است که متوسط تعداد تکرارها برای حل مساله های برنامه ریزی خطی تابعی خطی از تعداد محدودیت های مساله (m) است که همواره مقدار آن کمتر از 3m است*.
در تحقیقی دیگر برای مساله های برنامه ریزی خطی تعداد متوسط تکرارها برای رسیدن به جواب بهینه برابر 3m/2 ادعا شده است.
