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

برنامه‌ریزی خطی — بهینه‌سازی اهداف خطی تحت قیود خطی

معرفی‌شده توسط
George B. Dantzig
سال
1947
نوع
Mathematical programming / continuous optimization

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

اندازه قلم

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

برنامه‌ریزی خطی (LP)، که توسط جورج بی. دانتزیگ در سال ۱۹۴۷ پیشگام شد، یک روش ریاضی برای یافتن بهترین مقدار یک تابع هدف خطی — مانند حداقل هزینه یا حداکثر سود — تحت مجموعه‌ای از قیود نامساوی و تساوی خطی است. این تکنیک بنیادی در تحقیق در عملیات است و مبنای برنامه‌ریزی تولید، تخصیص منابع، لجستیک، مسائل رژیم غذایی و سناریوهای بی‌شمار دیگر تصمیم‌گیری در مهندسی، اقتصاد و علوم طبیعی است.

شهود پشت روش

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

تاریخ

توسعه سیستماتیک برنامه‌ریزی خطی در سال ۱۹۴۷ آغاز شد، زمانی که جورج بی. دانتزیگ، که برای نیروی هوایی ایالات متحده کار می‌کرد، الگوریتم سیمپلکس را برای خودکارسازی برنامه‌ریزی لجستیک نظامی ابداع کرد. دانتزیگ نظریه بنیادی را در رساله خود در سال ۱۹۶۳ منتشر کرد که همچنان مرجع کانونی است. کارهای مستقل و موازی توسط لئونید کانتوروویچ در اتحاد جماهیر شوروی (۱۹۳۹) به برنامه‌ریزی تولید با استفاده از ایده‌های ریاضی مشابه پرداخت و کانتوروویچ به دلیل این مشارکت تا حدی جایزه نوبل اقتصاد را در سال ۱۹۷۵ دریافت کرد. مسئله نظری قابلیت حل در زمان چندجمله‌ای توسط روش بیضی خاچیان (۱۹۷۹) و بعدها توسط روش نقطه درونی کارمارکار (۱۹۸۴) حل شد که برای مسائل در مقیاس بزرگ عملاً سریع بودند. امروزه، حل‌کننده‌های LP تجاری و متن‌باز در برنامه‌ریزی منابع سازمانی، زمان‌بندی خطوط هوایی و سیستم‌های انرژی در سراسر جهان تعبیه شده‌اند.

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

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

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

  • الزام خطی بودن: اگر هدف یا هر قیدی غیرخطی باشد، مدل LP نادرست مشخص شده است و راه‌حل ممکن است نادرست یا ناممکن باشد.
  • فقط متغیرهای پیوسته: هنگامی که متغیرهای تصمیم باید مقادیر صحیح یا دودویی را بگیرند، استرخاء LP یک حد پایین ارائه می‌دهد اما یک راه‌حل معتبر نیست؛ باید از برنامه‌ریزی عدد صحیح استفاده شود.
  • قطعی: LP عدم قطعیت در پارامترها را مدل نمی‌کند؛ در صورت نامشخص بودن داده‌ها، برنامه‌ریزی تصادفی یا بهینه‌سازی قوی مورد نیاز است.
  • انحطاط و چرخه (Degeneracy and cycling): در موارد نادر، روش سیمپلکس می‌تواند بدون همگرایی در پایه‌های منحط بچرخد، اگرچه قوانین ضد چرخه (مانند قانون بلاند) این مشکل را حل می‌کنند.

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

نقاط قوت

  • بهینه سراسری تضمین‌شده: از آنجایی که ناحیه ممکن یک چندوجهی محدب است، هر بهینه محلی نیز یک بهینه سراسری است و هیچ خطری برای گیر افتادن در یک راه‌حل زیربهینه وجود ندارد.
  • مقیاس‌پذیری بالا: حل‌کننده‌های مدرن (HiGHS, Gurobi, CPLEX) مدل‌هایی با میلیون‌ها متغیر و قید را در چند ثانیه مدیریت می‌کنند.
  • اطلاعات غنی پس از حل: قیمت‌های سایه و دامنه‌های حساسیت بینش عملی در مورد ارزش منابع و استحکام راه‌حل بدون اجرای اضافی ارائه می‌دهند.
  • عدم وجود مفروضات توزیعی: LP یک مدل کاملاً جبری است، بنابراین به نرمال بودن یا هیچ ویژگی آماری داده‌ها نیاز ندارد.

کاربردها

  • برنامه‌ریزی تولید: یافتن ترکیب بهینه محصولات که سود را حداکثر می‌کند در حالی که ظرفیت ماشین و محدودیت‌های مواد خام را رعایت می‌کند.
  • لجستیک زنجیره تأمین و حمل و نقل: حداقل کردن هزینه‌های حمل و نقل در سراسر شبکه انبارها و مشتریان.
  • مسائل رژیم غذایی و ترکیبی: انتخاب مقادیر مواد تشکیل‌دهنده که نیازهای تغذیه‌ای را با حداقل هزینه برآورده می‌کنند.
  • بهینه‌سازی سبد سهام مالی: تخصیص سرمایه در میان دارایی‌ها برای حداکثر کردن بازده مورد انتظار تحت قیود ریسک و مقررات.
  • اعزام انرژی و زمان‌بندی شبکه برق: حداقل کردن هزینه سوخت در حالی که تقاضای برق و محدودیت‌های ظرفیت ژنراتور را برآورده می‌کند.
  • زمان‌بندی کارکنان و نیروی کار: تخصیص شیفت‌ها به کارگران برای پوشش تقاضا با حداقل هزینه نیروی کار.

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

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

1

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

2

مدل به شکل کانونی یا استاندارد که یک حل‌کننده می‌تواند پردازش کند، آورده می‌شود. نامساوی‌ها با معرفی متغیرهای کمکی (slack) یا مازاد (surplus) نامنفی به تساوی تبدیل می‌شوند و هر متغیر نامقید با تفاضل دو متغیر نامنفی جایگزین می‌شود. این مرحله مکانیکی، نمایش جدول (tableau) یا ماتریسی را تولید می‌کند که الگوریتم بر روی آن عمل می‌کند و مسئله را تغییر نمی‌دهد — فقط آن را برای محاسبه شکل می‌دهد.

3

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

4

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

دام‌های رایج

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

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

چه چیزی یک مسئله را از نظر LP «خطی» می‌سازد؟

هم تابع هدف و هم هر قید باید خطی باشند — به این معنی که هر جمله، ثابتی ضربدر یک متغیر تصمیم منفرد است، بدون حاصلضرب متغیرها، بدون توان و بدون توابع غیرخطی. اگر حتی یک قید یا هدف شامل، مثلاً، x ضربدر y یا x به توان دو باشد، LP استاندارد دیگر کاربرد ندارد و به یک حل‌کننده برنامه‌ریزی غیرخطی یا درجه دوم نیاز است.

چرا راه‌حل بهینه همیشه در گوشه‌ای از ناحیه ممکن قرار دارد؟

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

چه زمانی باید به جای LP از برنامه‌ریزی عدد صحیح استفاده کنم؟

هر زمان که یک یا چند متغیر تصمیم باید مقادیر صحیح یا دودویی (۰/۱) بگیرند — به عنوان مثال، آیا یک تأسیسات را باز کنیم (بله/خیر)، چند کامیون اعزام کنیم (اعداد صحیح)، یا کدام اقلام را در یک انتخاب بگنجانیم. صرفاً حل LP و گرد کردن راه‌حل پیوسته قابل اعتماد نیست: راه‌حل‌های گرد شده می‌توانند ناممکن یا دور از بهینه باشند. برنامه‌ریزی عدد صحیح به درستی یکپارچگی را مدیریت می‌کند، با هزینه محاسباتی بیشتر.

قیمت‌های سایه به من چه می‌گویند؟

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

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

منابع

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

    شابک: 9780691059136
    کپی شد.
  2. Vanderbei, R.J. (2014). Linear Programming: Foundations and Extensions. Springer.

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