تحلیل حساسیت در برنامه‌ریزی خطی

انگیزه: جواب بهینه امروز، فردا هم بهینه می‌ماند؟

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

تحلیل حساسیت کلاسیک معمولاً تغییر یک پارامتر در هر بار را فرض می‌کند. بازه‌های مجاز برای تغییر هم‌زمان چند ظرفیت یا چند ضریب را نباید بدون محاسبه مجدد با هم جمع کرد.

۱. مبنای جبری: چرا ماتریس پایه مهم است؟

در یک برنامه خطی با فرم استاندارد Ax=b و x≥0، اگر مجموعه متغیرهای پایه انتخاب شود و ماتریس ستون‌های متناظر را B بنامیم، جواب پایه از رابطه x_B=B⁻¹b به‌دست می‌آید. برای حفظ مجازبودن همین پایه، همه مؤلفه‌های B⁻¹b باید نامنفی بمانند. برای حفظ بهینگی همین پایه، هزینه‌های کاهش‌یافته با قرارداد متناسب با نوع مسئله باید علامت مناسب داشته باشند.

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

۲. مثال کامل اول: تغییر ظرفیت منبع اول

مدل اصلی کارگاه:

Max Z = 40x1 + 30x2
x1 + x2 <= 8
2x1 + x2 <= 10
x1, x2 >= 0

جواب فعلی x1=2، x2=6 و Z=260 است. هر دو قید در این نقطه فعال‌اند، پس رابطه زیر برقرار است:

B = [[1,1], [2,1]]
B^(-1) = [[-1,1], [2,-1]]
x1 = b2 - b1
x2 = 2b1 - b2

اگر فقط ظرفیت اول را از ۸ به 8+δ تغییر دهیم و ظرفیت دوم ۱۰ بماند، آنگاه x1=2−δ و x2=6+2δ. برای نامنفی‌ماندن هر دو متغیر لازم است δ≤2 و δ≥−3. بنابراین بازه تغییر ظرفیت اول با حفظ پایه برابر −3≤δ≤2، یا به بیان ظرفیت 5≤b1≤10 است.

For -3 <= delta <= 2:
 x1(delta) = 2 - delta
 x2(delta) = 6 + 2delta
 Z(delta)  = 260 + 20delta

چرا ضریب ۲۰ ظاهر شد؟ چون قیمت سایه‌ای منبع اول از مدل دوگان y1=20 است. در این بازه، افزایش یک واحد ظرفیت اول، سود بهینه را ۲۰ واحد افزایش می‌دهد. برای مثال با δ=1 ترکیب جدید (1,8) و سود 280 به دست می‌آید. اما δ=3 به x1=−1 می‌رسد و دیگر مجاز نیست؛ در نتیجه تعمیم خطی جواب قبلی از این نقطه معتبر نیست.

تغییر ظرفیت دوم را جداگانه حساب کنیم

اگر b1=8 ثابت بماند و b2=10+ε شود، داریم x1=2+ε و x2=6−ε. در نتیجه −2≤ε≤6 و Z(ε)=260+10ε. قیمت سایه‌ای منبع دوم برابر ۱۰ است. این دو بازه برای تغییرات جداگانه محاسبه شده‌اند؛ نمی‌توان هر دو ظرفیت را تا انتهای بازه خود تغییر داد و بدون بررسی مشترک انتظار حفظ پایه داشت.

۳. مثال کامل دوم: تغییر سود هر واحد محصول

اگر ظرفیت‌ها ثابت بمانند ولی سود محصول اول از ۴۰ به c1 تغییر کند، ممکن است نقطه (2,6) همچنان بهینه باشد. چون هر دو محصول مثبت‌اند، برای پابرجاماندن همین پایه، قیمت‌های دوگان باید از رابطه Bᵀy=c به دست آیند:

 y1 + 2y2 = c1
 y1 +  y2 = 30
 -----------------
 y1 = 60 - c1
 y2 = c1 - 30

برای مجازبودن دوگان باید y1≥0 و y2≥0 باشد؛ بنابراین 30≤c1≤60. درون این بازه، (2,6) همچنان بهینه است و مقدار هدف جدید Z=2c1+180 می‌شود. در مرزهای ۳۰ و ۶۰ ممکن است جواب‌های بهینه دیگری نیز وجود داشته باشند، پس حفظ بهینگی یک جواب لزوماً به معنی یکتایی آن نیست.

اگر سود محصول دوم را به c2 تغییر دهیم و c1=40 ثابت باشد، تحلیل مشابه y1=2c2−40 و y2=40−c2 را می‌دهد؛ پس 20≤c2≤40 بازه حفظ پایه است.

۴. تفاوت سه پرسش مهم

1. آیا جواب قبلی هنوز مجاز است؟ اگر فقط تابع هدف تغییر کند، مجموعه مجاز عوض نمی‌شود و جواب قبلی همچنان مجاز می‌ماند؛ اما ممکن است بهینه نباشد.

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

3. آیا جواب جدید را می‌توان با قیمت سایه‌ای پیش‌بینی کرد؟ فقط برای تغییر RHS در بازه‌ای که پایه و شرایط مناسب برقرار باشد؛ قیمت سایه‌ای یک رابطه جهانی برای همه ظرفیت‌ها نیست.

۵. تحلیل حساسیت در یک مثال مدیریتی

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

۶. خطاهای رایج و کنترل کیفیت نتیجه

• بازه RHS را با بازه ضریب تابع هدف اشتباه نگیرید؛ یکی عمدتاً مجازبودن پایه و دیگری بهینگی آن را بررسی می‌کند.
• اگر یک متغیر پایه در انتهای بازه صفر شود، تباهی رخ می‌دهد و ممکن است چند پایه، همان نقطه را نمایش دهند.
• قیمت سایه‌ای را برای یک تغییر بسیار بزرگ بدون حل مجدد به کار نبرید.
• تغییر هم‌زمان چند ضریب، معمولاً نیازمند تحلیل برداری یا حل مجدد است؛ بازه‌های تک‌پارامتری کافی نیستند.
• واحدهای ظرفیت و سود را بنویسید. «۲۰» به‌تنهایی نتیجه مدیریتی نیست؛ «۲۰ واحد سود به ازای یک واحد منبع اول» معنی دارد.
• حل‌گرهای عددی ممکن است به‌دلیل تلرانس، متغیرهای بسیار کوچک یا قیود تقریباً فعال نشان دهند؛ نتیجه را با کنترل مانده قیود تأیید کنید.

تمرین‌های درجه‌بندی‌شده

سطح ۱: در مدل اصلی، اگر ظرفیت اول به ۹ برسد، ترکیب تولید و مقدار هدف را با روابط حساسیت محاسبه کنید.

سطح ۲: اگر ظرفیت دوم به ۸ کاهش یابد و ظرفیت اول ثابت بماند، آیا رابطه خطی معتبر است؟ جواب جدید چیست؟

سطح ۳: اگر c1=65 شود و c2=30 بماند، آیا تضمین حفظ بهینگی (2,6) برقرار است؟ با مقایسه دو نقطه مجاز استدلال کنید.

وضعیت تحریریه: آموزشی · بازبینی محاسبات نمونه‌ها انجام شده · بازبینی علمی مستقل در انتظار. این درس برای تصمیم مهندسی واقعی بدون کنترل داده و مدل کافی نیست. صفحه تا ثبت تأیید علمی مستقل noindex است.