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

برنامه‌ریزی خطی قطعی — فرم کلاسیک برنامه‌ریزی خطی با پارامترهای معلوم

معرفی‌شده توسط
George B. Dantzig
سال
1947
نوع
Deterministic mathematical optimization
خانواده
Simulation / optimization

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

اندازه قلم

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

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

شهود پشت روش

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

تاریخ

برنامه‌ریزی خطی در سال ۱۹۴۷ توسط جورج بی. دانتزیگ با توسعه الگوریتم سیمپلکس در حین کار برای نیروی هوایی ایالات متحده رسمی شد. رساله دانتزیگ در سال ۱۹۶۳ مرجع اصلی شد. پسوند 'قطعی' با معرفی انواع برنامه‌ریزی خطی تصادفی (دانتزیگ و بیل، دهه ۱۹۵۰–۱۹۶۰) برای تمایز مدل پارامتر قطعی اصلی از تعمیم‌های احتمالی آن پدیدار شد.

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

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

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

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

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

نقاط قوت

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

کاربردها

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

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

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

1

متغیرهای تصمیم x (مثلاً مقادیر تولید، مقادیر جریان)، تابع هدف c^T x برای کمینه‌سازی یا بیشینه‌سازی، و مجموعه محدودیت Ax <= b با شرط x >= 0 را تعریف کنید. تمام ضرایب در c، A و b به عنوان مقادیر ثابت دقیق و معلوم در نظر گرفته می‌شوند — این همان چیزی است که مدل را قطعی می‌سازد. فرم استاندارد LP را بنویسید: min c^T x تحت شرط Ax = b, x >= 0.

فرمول
\min_{x} \; c^\top x \quad \text{s.t.} \quad Ax \leq b, \; x \geq 0
2

قبل از بهینه‌سازی، بررسی کنید که ناحیه شدنی غیرتهی باشد (مجموعه محدودیت حداقل یک راه‌حل داشته باشد) و تابع هدف کراندار باشد. اگر ناحیه شدنی تهی باشد، مسئله ناممکن (infeasible) است؛ اگر تابع هدف بی‌کران باشد، مدل اشتباه فرمول‌بندی شده است. این بررسی‌ها به طور خودکار توسط حل‌کننده‌ها انجام می‌شوند اما باید توسط تحلیلگر تفسیر شوند تا خطاهای فرمول‌بندی را تشخیص دهند.

3

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

4

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

فرمول
x^* = \arg\min \{ c^\top x : Ax \leq b,\; x \geq 0 \}
5

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

دام‌های رایج

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

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

چه چیزی LP را 'قطعی' در مقابل 'تصادفی' می‌سازد؟

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

آیا الگوریتم سیمپلکس همیشه کارآمد است؟

در عمل، بله — روش سیمپلکس تقریباً تمام LPهای دنیای واقعی را بسیار سریع حل می‌کند. از نظر تئوری، می‌تواند زمان نمایی در بدترین حالت (مثال‌های Klee–Minty) را بگیرد، اما روش‌های نقطه درونی (مثلاً الگوریتم کارمارکار) در زمان چندجمله‌ای اجرا می‌شوند و برای نمونه‌های بسیار بزرگ رقابتی هستند.

آیا می‌توانم از DLP استفاده کنم اگر برخی از متغیرهای تصمیم من باید اعداد صحیح باشند؟

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

قیمت‌های سایه پس از حل چگونه کمک می‌کنند؟

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

چه زمانی باید از DLP به LP مقاوم یا تصادفی ارتقا دهم؟

زمانی که عدم قطعیت پارامتر غیرقابل اغماض است و هزینه یک راه‌حل ناممکن یا ضعیف تحت مقادیر پارامتر تحقق یافته قابل توجه است، ارتقا دهید. اگر انحراف ۱۰ تا ۲۰ درصدی در یک ضریب کلیدی باعث تغییر راه‌حل ترجیحی شود یا باعث نقض محدودیت شود، فرض قطعیت DLP بیش از حد قوی است.

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

منابع

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

    شابک: 9780691059136
    کپی شد.
  2. Linear programming. Wikipedia.

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