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

بهینه سازی

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

 

Ellipsoid Method or Khachiyan Method

 

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

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

مقدمه :

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

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

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


 
 
 



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