Skip to content
بازگشت به نتایج جست‌وجو

روش سیمپلکس

معرفی‌شده توسط
George Dantzig
سال
1947
نوع
algorithm
خانواده
Optimization

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

روش سیمپلکس، که توسط جورج دانتزیگ در سال ۱۹۴۷ ابداع شد، یک الگوریتم بنیادی برای حل مسائل برنامه‌ریزی خطی است. این روش به طور سیستماتیک رئوس ناحیه شدنی را بررسی می‌کند تا راه‌حل بهینه را بیابد که در آن تابع هدف تحت قیود خطی بیشینه یا کمینه می‌شود.

شهود پشت روش

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

تاریخ

جورج دانتزیگ روش سیمپلکس را در سال ۱۹۴۷ معرفی کرد که عملیات تحقیق را متحول کرد و برای دهه‌ها به الگوریتم استاندارد برنامه‌ریزی خطی تبدیل شد. کلی و مینتی (۱۹۷۲) پیچیدگی نمایی بدترین حالت را نشان دادند، با این حال به صورت تجربی این روش سریع باقی ماند. دهه ۱۹۸۰ شاهد توسعه روش‌های نقطه داخلی به عنوان جایگزین بود، اما روش سیمپلکس به دلیل استحکام و پیچیدگی پیاده‌سازی‌های مدرن، برای بسیاری از کاربردهای عملی غالب باقی ماند.

چه زمانی استفاده شود

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

محدودیت‌ها و ملاحظات

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

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • تضمین یافتن راه‌حل بهینه در زمان محدود برای برنامه‌های خطی
  • کارآمد در عمل با پیاده‌سازی دقیق و مدیریت تباهیدگی
  • به طور گسترده پیاده‌سازی شده و توسط کتابخانه‌های بهینه‌سازی بالغ پشتیبانی می‌شود
  • مبنایی برای درک الگوریتم‌های بهینه‌سازی پیشرفته‌تر

کاربردها

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

چگونه کار می‌کند

چگونه کار می‌کند

1

برنامه خطی را با متغیرهای کمکی به فرم استاندارد تبدیل کنید و یک راه‌حل اساسی شدنی اولیه (معمولاً مبدأ در صورت شدنی بودن) را شناسایی کنید.

2

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

3

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

دام‌های رایج

  • عدم مدیریت صحیح چرخه هنگام مواجهه با پایه‌های تباهیده (از قانون بلاند یا روش‌های اغتشاش استفاده کنید)
  • انتخاب محوری نادرست یا خطاهای محاسباتی در به‌روزرسانی‌های جدول که منجر به ناپایداری عددی می‌شود
  • عدم بررسی بی‌کرانگی یا ناشدنی بودن قبل از شروع الگوریتم

پرسش‌های متداول

چرا روش سیمپلکس «سیمپلکس» نامیده می‌شود؟

اصطلاح «سیمپلکس» به ساده‌ترین شکل یک چندوجهی در هر بعد معین اشاره دارد. این الگوریتم با حرکت در امتداد یال‌ها و رئوس چندوجهی تعریف شده توسط قیود کار می‌کند.

تفاوت بین روش سیمپلکس و روش نقطه داخلی چیست؟

روش سیمپلکس در مرز ناحیه شدنی در رئوس باقی می‌ماند، در حالی که روش‌های نقطه داخلی از طریق فضای داخلی حرکت می‌کنند. روش‌های نقطه داخلی پیچیدگی بدترین حالت بهتری دارند، اما سیمپلکس اغلب در عمل برای مسائل با اندازه متوسط سریع‌تر است.

چگونه ناشدنی بودن یا بی‌کرانگی را مدیریت می‌کنید؟

از روش سیمپلکس دو فازی استفاده کنید: فاز اول یک مسئله کمکی را حل می‌کند تا یک راه‌حل اساسی شدنی پیدا کند یا ناشدنی بودن را تعیین کند؛ فاز دوم روش سیمپلکس استاندارد را برای مسئله اصلی به کار می‌برد.

تباهیدگی چیست و چرا اهمیت دارد؟

تباهیدگی زمانی رخ می‌دهد که یک راه‌حل اساسی شدنی بیش از یک نمایش پایه داشته باشد، که می‌تواند باعث چرخه شود. آن را با استفاده از قانون بلاند (انتخاب متغیرها بر اساس ترتیب شاخص) یا روش‌های اغتشاش مدیریت کنید.

روش‌های مرتبط

منابع

  1. Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.

    باز کردن مرجع DOI
    کپی شد.
  2. Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.

    باز کردن مرجع DOI
    کپی شد.