پیاده سازی روش سیمپلکس دوگان برای حل مسایل برنامه ریزی خطی بزرگ مقیاس

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

کلیدواژه ها:

مسایل برنامه ریزی خطی بزرگ مقیاس ، روش سیمپلکس دوگان ، پیاده سازی کامپیوتری