Crash Procedureنویسنده : نعمت الله تقی نژاد - ساعت ٩:٤۳ ‎ب.ظ روز سه‌شنبه ٢٥ تیر ۱۳٩٢
برنامه ریزی خطی، الگوریتم سیمپلکس، نقطه راسی، نقطه شدنی اولیه



هدف مسائل بهینه سازی مینیمم یا ماکزیمم کردن تابع حقیقی f(x)2 است

به طوری که: Ax=b , b1<=x<=b2

که در اینجا A یک ماتریس حقیقی m*n،یb یک بردار حقیقی m*1 و b1 , b2 بردارهای حقیقی n*1 هستند که می توانند حاوی مولفه های نا متناهی نیز باشند.

پیدا کردن یک جواب اولیه شدنی برای دستگاه معادلات بالا وقتی که m , n اعداد نسبتاّ بزرگی باشند کار ساده ای نیست.متأسفانه در برخی موارد مسأله پیدا کردن یک نقطه شدنی اولیه به سختی حل مسأله اصلی است

از آن جایی که اکثر الگوریتم هایی که برای حل مساله بهینه سازی طراحی شده اند از یک نقطه شدنی اولیه تکرار های خود را آغاز میکنند ، توجه محققین به روشهایی برای به دست آوردن یک جواب شدنی اولیه در زمان نسبتاّ کمتری معطوف گشت . از جمله این روشها می توان به موارد زیر اشاره کرد:

Crash techniques

Invert method

Multiple pricing

ایده تکنیک های crash بر مبنای استفاده از ماتریس های مثلثی در پایه است ، که در ادامه بیشتر مورد بحث قرار خواهند گرفت. در Invert method با استفاده از یک پایه پیشرفته تعداد تکرار ها برای رسیدن به بهینگی کاهش می یابد . این روش همچنین استفاده مهم دیگری در بحث مربوط به دقت عددی دارد . در روش Multiple pricing زیر مجموعه هایی از ماتریس ضرایب انتخاب و هر کدام بهینه می شوند تا زمانی که کل مسأله بهینه گردد .

نویسنده : نعمت الله تقی نژاد - ساعت ۱:٥٠ ‎ب.ظ روز سه‌شنبه ۱۸ تیر ۱۳٩٢
الگوریتم، پیچیدگی زمانی الگوریتم، پیچیدگی فضایی الگوریتم، انواع کلاسهای پیچیدگی




مقایسه ی بین دو الگوریتم

دو الگوریتم را که کار مشابهی انجام می دهند ، درنظر می گیریم،مقایسه آنها به چه معنا می باشد ؟ چه موقع میتوان گفت یکی بهتراست ؟ چه فاکتورهایی درکارایی الگوریتم مؤثر می باشد؟ چگونه کارایی را به دست می آوریم؟

نظریهٔ‌ پیچیدگی محاسباتی شاخه‌ای ازعلوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیله‌ی رایانه (به عبارت دقیق‌تر به‌ صورت الگوریتمی) می‌پردازد.
این نظریه با منابع مورد نیاز برای حل یک مسأله سروکار دارد. عمومی‌ترین منابع زمان (چقدر زمان برای حل کردن مسأله لازم است) و فضا (چقدر حافظه مورد نیاز است) می‌باشند.
تعریف 1:میزان حافظه یا پیچیدگی فضایی یک برنامه مقدار حافظه مورد نیاز برای اجرای کامل یک برنامه است.

تعریف 2: پیچیدگی زمانی یک برنامه ، مقدار زمان کامپیوتر است که برای اجرای کامل برنامه لازم است.



پیچیدگی فضایی الگوریتم

فضای مورد نیاز یک برنامه شامل موارد زیر می باشد:
1.نیازمندیهای فضای ثابت
2.نیازمندیهای فضای متغیر

اولین مورد به فضای مورد نیازیی که به تعداد و اندازه ورودی و خروجی برنامه بستگی ندارد ، اشاره می کند و شامل فضای دستورالعمل ها(فضای لازم برای ذخیره کد برنامه)،فضای لازم برای متغیرهای ساده،متغیرهای ساختاری با اندازه ثابت و....می باشد.

دومین مورد شامل فضای مورد نیاز متغیرهای ساخت یافته ای است که اندازه آنها بستگی به نمونه ای از مسأله ای که حل می شود دارد.

رابطه ی نقاط گوشه ای با جواب بهینه در برنامه ریزی خطینویسنده : نعمت الله تقی نژاد - ساعت ۱۱:٤۱ ‎ق.ظ روز جمعه ۳ خرداد ۱۳٩٢
برنامه ریزی خطی، نقطه راسی، نقاط گوشه ای، corner points



در ریاضیات، مسائل برنامه ریزی خطی شامل بهینه سازی تابع هدفی خطی است که بایستی یکسری محدودیت در فرم های تساوی های خطی و نامساوی برقرار شوند. به طور خیلی غیررسمی برنامه ریزی خطی استفاده از مدل ریاضی خطی برای بدست آوردن بهترین خروجی(به طور مثال حداکثر سود، حداقل کار) با توجه به شرط های داده شده (برای مثال فقط 30 ساعت کار در هفته، کار غیر قانونی انجام ندادن و غیره) است.

و به طور رسمی تر در یک چند سقفی (مانند چندضلعی یا چندوجهی) که تابعی با مقدار حقیقی بر روی آن تعریف شده است، هدف یافتن نقطه ای در این چند سقفی است که تابع هدف بیشترین یا کمترین مقدار را دارا باشد. این نقاط ممکن است موجود نباشد، اما اگر وجود داشته باشند جست و جو در میان رئوس چند ضلعی یافتن حداقل یکی از آن ها را تضمین می کند

الگوریتم سیمپلکس برای حل مسائل برنامه ریزی خطی که شامل قیود = و یا =< با سمت راست نامنفی می باشند جهت رفع نیاز شدنی بودن در نقطه آغازین به متغیرهای مصنوعی نیاز دارد. ما یک روش حل کلی تحت عنوان push and pull ارائه می دهیم که نیاز به کاربرد متغیرهای مصنوعی را برطرف می کند. این روش یک روش حل جدید میباشد که فهم آن راحت تر است و خالی از هر متغیر مصنوعی و تابع هدف مصنوعی و عبارت جریمه است.
این روش شامل دو فاز است:

1.فاز push:
این مرحله یک مجموعه از متغیرهای پایه ای (BVS)را کامل می کند بطوریکه این فاز با یک BVS اولیه خالی شروع می شود و سپس متغیرها یکی یکی وارد پایه می شوند اگر BVS کامل شود اما شرط بهینگی برقرار نباشد این مرحله تا برقرار شدن شرط بهینگی ادامه می یابد. حال چنانچه جدول بدست آمده شدنی نباشد فاز PULL وارد عمل می شود

2.فاز PULL:
این مرحله جواب بدست آمده را به سمت شدنی بودن سوق می دهد.این فاز قوانین سیمپلکس دوگان را بکار میگیرد. لذا در کل فاز PUSH از یک راس به راس دیگر جهت ارضا کردن شرط بهینگی جابجا می شود اگر راس بدست آمده شدنی نباشد فاز دوم یک جواب بهین و شدنی را با بکار بردن قوانین مشابه روش سیمپلکس دوگان تولید می کند.

زمان محاسبات الگوریتم سیمپلکس، پیچیدگی الگوریتم کارمارکار، پیچیدگی الگوریتم سیمپلکس، practical complexity



سیمپلکس یک الگوریتم دارای ‌پیچیدگی زمانی از مرتبه ی نمایی (O(n2 است.

در حالی که پیچیدگی زمانی الگوریتم کارمارکار (O(2n است .

در حالت کلی الگوریتم هایی که پیچیدگی آنها نمایی است ، پیشرفت تکنولوژی نمی تواند در حل مسأله هایی با اندازه های بزرگ ، کمک چندانی نماید. الگوریتم سیمپلکس با آنکه دارای پیچیدگی نمایی است ولی تجربه نشان داده که این الگوریتم در اغلب موارد حداکثر تا 3m تکرار به نقطه ی بهین خود می رسد به اصطلاح دارای Practical Complexity است .