تحقیق در عملیات ( Operation Research)

بهینه سازی

Recovering an Optimal Basis from IPM solution
نویسنده : نعمت الله تقی نژاد - ساعت ٩:٠٢ ‎ب.ظ روز سه‌شنبه ٢٢ اسفند ۱۳٩۱
 

 

بازیابی یک پایه بهین از جواب روش نقطه داخلی

     برای یک مسئله برنامه ریزی خطی  (LP) روش معمولی و مورد استفاده در اکثر موارد روش سیمپلکس است که به طور طبیعی از یک جواب پایه ای در ناحیه شدنی شروع و به یک (یا یک جفت) جواب اولیه (یا دوگان) می رسد.

   الگوریتم روش نقطه داخلی  (Interior-Point Method)روش جدیدتری است که از یک نقطه در درون (Interior) ناحیه شدنی آغاز میشود و با استفاده از جفت معادلات مکمل اولیه-دوگان دنباله ای از نقاط را در درون ناحیه شدنی دنبال می کند تا به صورت حدی به جواب بهین مسئله برسد.

   اگر جواب های اولیه و دوگان (هر دو) وجود داشته باشد، جواب روش نقطه داخلی “ بین” دو جواب اولیه و دوگان خواهد بود.

         مزایای روش اخیر:

–   زمان اجرای چند جمله ای در  مسائل large scale
–  حل مسائل برنامه ریزی غیر خطی است.

       پاره ای مشکلات این روش:

–  اجرای روش نقطه داخلی در نزدیکی جواب بهین از نظر عددی دارای پایداری (stability) زیادی نمی باشد
 
– یک جواب پایه ای (دقیق) برای مسئله ارائه نمی کند و جواب ها تقریبی از جواب اصلی مسئله است، البته در نهایت این جواب، به جواب اصلی همگرا است.

  

دانلود رایگان فایل کامل پروژه


 
 
بررسی روش بیضوی(خاچیان) برای حل مسائل برنامه ریزی خطی
نویسنده : نعمت الله تقی نژاد - ساعت ۱۱:۱٩ ‎ق.ظ روز شنبه ۱٩ اسفند ۱۳٩۱
 

 

Ellipsoid Method or Khachiyan Method

 

مباحث اصلی پروژه:

  • مقدمه
  • تعاریف
  • روش بیضوی برای حل یک دستگاه از نامعادلات باز با دادهای صحیح
  • الگوریتم بیضوی
  • چرا روش بیضوی را نمی توان به طور مستقیم برای دستگاه نامعادلات خطی بسته حل کنیم
  • تفسیر هندسی و اثبات درستی
  • پیچیدگی روش بیضوی روی مسائل با داده های حقیقی
  • حل دستگاه های نامعادلات خطی بسته از طریق روش بیضوی
  •  چگونگی حل یک مسئله LP با استفاده از روش بیضوی
  • نتیجه گیری و جمع بندی
  • منابع

مقدمه :

از زمانیکه ثابت شد پیچیدگی الگوریتم سیمپلکس با بکارگیری بسیاری از قواعد انتخاب متغیر وارد شونده، کراندار چند جمله ای نیست، این سوال به ذهن رسید که آیا یک الگوریتم کراندار چند جمله ای برای حل مسائل برنامه ریزی خطی وجود دارد؟ در فوریه سال 1979 میلادی مقاله ای از یک محقق روسی به نام خاچیان تحت عنوان روشهای چند جمله ای در برنامه ریزی خطی در مجله ی علمی Doklady روسیه به چاپ رسید. چند ماه بعد هم این موضوع به طور غیررسمی مورد بحث محققین تحقیق در عملیات،علوم کامپیوترو ریاضیدانان قرار گرفت.

در پایان سال 1979 خبر روش خاچیان نه تنها در مجلات علمی بلکه در سر مقاله ی اغلب روزنامه های آمریکا، اروپا و ژاپن به عنوان یک تکنیک جدید جهت حل مسائل برنامه ریزی خطی چاپ گردید. درنتیجه، خاچیان یک مرتبه مشهور شد.

برای مطالعه کامل پروژه میتوانید آن را بطور رایگان از اینجا دانلود کنید 


 
 
فرمول بندی برنامه ریزی خطی برای پردازش زبان های طبیعی
نویسنده : نعمت الله تقی نژاد - ساعت ۱۱:۳۱ ‎ق.ظ روز جمعه ۱۱ اسفند ۱۳٩۱
 

 

A Linear Programming on Global Interface in Natural Language Tasks

 

   پردازش زبانهای طبیعی یکی اززیر شاخه های با اهمیت در حوزه گسترده هوش مصنوعی و نیز در دانش زبان شناسی است، تلاش عمده در این زمینه ماشینی کردن فرایند درک و برداشت مفاهیم بیان شده با یک زبان طبیعی انسانی است.

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

 هنوز سیستم کارامدی برای پردازش زبانهای طبیعی بوجود نیامده است

مشکلات موجود عبارتند از:

1- نیاز به درک معانی

2- دقیق نبودن دستور زبانها

 

 دانلود فایل کامل پروژه 

 


 
 
Crash algorithm
نویسنده : نعمت الله تقی نژاد - ساعت ۱٢:٤٥ ‎ق.ظ روز شنبه ٥ اسفند ۱۳٩۱
 

 

بعد از ابداع روش سیمپلکس توسط جرج بی دانتزیک در سال 1947و نیز اختراع کامپیوتر موضوعی که ذهن اکثر دانشمندان را به خود معطوف کرده بود این بود که چگونه میتوان در مسایل بزرگ و عملی سرعت محاسبات را بالاتر برد. به عبارت دیگر چگونه میتوان در مسایل بزرگ در وقت صرفه جویی کرد .

دانشمندان زیادی در این زمینه به فعالیت ومطالعه  پرداختند . اکثر روشهای مطرح شده روشهایی ابتکاری بودند کد باعث صرفه جویی در زمان می شدند . مجموعه ای از این روشها را می توان تحت عنوان crash algorithm نامگذاری کرد.

این الگوریتم در حالت خاص یک طرح برای کاهش زمان هر تکرار ارائه می دهد . استفاده از این الگوریتم بعضاً باعث افزایش کل تکرارها می شود . اما به علت افزایش سرعت هر تکرار ،کل زمان حل مسئله را کاهش می دهد .برای رسیدن به این مهم این الگوریتم از فرآیند مثلثی کردن استفاده می کند که شامل تعویض ستونهای متغیرهای مصنوعی پایه ای با ستونهایی از متغیر های غیر پایه ، وقتی ستون i ام از قسمت متغیرهای پایه ای با ستون j ام از متغیر های غیر پایه ای تعویض شود درایه i را درایه محوری می نامیم .ستونهایی از متغیر های غیر پایه ای می توانند به عنوان ستونهای ورودی انتخاب شوند که در تمامی سطر های محور گیریهای قبلی دارای درایه صفر باشند.

 

الگوریتم های میانی بکار رفته در این الگوریتم : 

  • الگوریتم gain switch off  
  • الگوریتم HYBRID

  دانلود پروژه  


 
 
 



backgroundcolor= class=#2f57a2width:230px; padding-top: 5px;td width=logo