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

چرا دوگان در تصمیم‌گیری مهم است؟

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

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

۱. تبدیل مدل اولیه به دوگان

مدل اولیه زیر را در نظر بگیرید؛ هر ضریب تابع هدف، سود فرضی هر واحد محصول است و هر سمت راست قید، ظرفیت یک منبع را نشان می‌دهد:

Primal (P)
Max Z = 40x1 + 30x2
subject to
    x1 +  x2 <=  8
   2x1 +  x2 <= 10
    x1, x2 >= 0

برای مدل بیشینه‌سازی با قیود ≤ و متغیرهای نامنفی، قاعده تبدیل این است: هر قید اولیه یک متغیر نامنفی در دوگان می‌سازد، هر متغیر اولیه یک قید از نوع ≥ در دوگان می‌سازد، ماتریس ضرایب جابه‌جا (ترانهاده) می‌شود و بردار منابع به ضرایب تابع هدف دوگان تبدیل می‌شود.

Dual (D)
Min W = 8y1 + 10y2
subject to
    y1 + 2y2 >= 40
    y1 +  y2 >= 30
    y1, y2 >= 0

تفسیر y1 ارزش حاشیه‌ای یک واحد ظرفیت منبع اول و تفسیر y2 ارزش حاشیه‌ای یک واحد ظرفیت منبع دوم است؛ البته تا زمانی که ساختار جواب بهینه تغییر نکرده باشد.

مشتق‌کردن کران دوگان، بدون حفظ‌کردن فرمول

هر جواب مجاز اولیه x را در نظر بگیرید. چون ضرایب دوگان شرط Aᵀy ≥ c را دارند و x ≥ 0 است، از ضرب اسکالر به دست می‌آید cᵀx ≤ yᵀAx. از سوی دیگر Ax ≤ b و y ≥ 0، پس yᵀAx ≤ yᵀb و در نتیجه:

Weak duality:
        c^T x <= b^T y
(for every primal-feasible x and dual-feasible y)

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

۲. مثال کامل اول: گواه بهینگی برای کارگاه

در درس مقدماتی، جواب اولیه (x1,x2)=(2,6) پیدا شد؛ هر دو منبع دقیقاً مصرف می‌شوند. مقدار سود برابر است با 40×2 + 30×6 = 260. چون هر دو محصول تولید مثبت دارند، طبق مکمل‌بودن، قیود متناظر آن‌ها در دوگان باید با تساوی برقرار شوند:

 y1 + 2y2 = 40
 y1 +  y2 = 30
 ----------------
 y2 = 10, y1 = 20
 W = 8(20) + 10(10) = 260

(y1,y2)=(20,10) نامنفی است و هر دو قید دوگان را ارضا می‌کند. بنابراین دو جواب مجاز با مقدار هدف برابر ۲۶۰ داریم و طبق دوگانگی ضعیف، بهینگی هر دو ثابت می‌شود. اگر کسی سود ۲۷۰ ادعا کند، جواب او حتماً یکی از قیود مدل را نقض می‌کند یا ضرایب/واحدها را عوض کرده است.

مکمل‌بودن دقیقاً چه می‌گوید؟

برای هر قید اولیه داریم y_i × (b_i − a_i x) = 0. به این معنی که اگر منبعی اضافه بماند، قیمت سایه‌ای آن در یک جواب دوگان مکمل باید صفر باشد. برای هر متغیر اولیه نیز x_j × ((Aᵀy)_j − c_j) = 0؛ یعنی اگر محصولی در جواب بهینه مقدار مثبت دارد، قید متناظر آن در دوگان با تساوی برقرار است. برعکسِ ساده‌انگارانه‌ی این نتیجه الزاماً برقرار نیست: «قید فعال» لزوماً قیمت سایه‌ای مثبت ندارد، چون تباهی و چندگانگی امکان‌پذیر است.

۳. مثال دوم: چرا قیمت سایه‌ای همیشه قیمت بازار نیست؟

یک انبار در یک هفته می‌تواند با یک ساعت نیروی کاری اضافه، سود بهینه مدل را از ۲۶۰ به ۲۸۰ برساند؛ در این بازه ارزش محاسباتی ساعت اضافه ۲۰ واحد است. اما خرید آن ساعت ممکن است هزینه اضافه‌کاری، خرابی دستگاه، هزینه کیفیت یا محدودیت قانونی داشته باشد. بنابراین تصمیم اقتصادی درست مقایسه ارزش حاشیه‌ای ۲۰ با هزینه واقعی افزایش ظرفیت است؛ نه این‌که هر منبع با قیمت سایه‌ای مثبت حتماً خریدنی باشد.

از سوی دیگر، قیمت سایه‌ای فقط در بازه‌ای از تغییر منابع ثابت می‌ماند. اگر منبع اول به اندازه ۴ واحد افزایش یابد، مدل قبلی ممکن است ترکیب بهینه دیگری پیدا کند؛ ضرب کورکورانه 4×20 دیگر لزوماً معتبر نیست. این محدودیت در درس تحلیل حساسیت دقیق محاسبه می‌شود.

۴. حالت‌های خاص و دام‌های استدلال

• اگر مدل اولیه کمینه‌سازی با قید ≥ باشد، جهت نابرابری در دوگان برعکس الگوی بالا می‌شود؛ یک جدول تبدیل ثابت را بدون بررسی جهت مدل به کار نبرید.
• متغیر اولیه آزاد در علامت، در دوگان به قید تساوی متناظر می‌شود؛ قید اولیه تساوی، متغیر دوگان آزاد در علامت می‌سازد.
• مدل ناممکن ممکن است دوگانی نامحدود یا ناممکن داشته باشد؛ نگویید «هر مدل حتماً دو مقدار هدف برابر دارد». برابری بهینگی برای حالت‌های دارای جواب بهینه متناهی است.
• قیمت سایه‌ای به واحد اندازه‌گیری وابسته است. اگر ظرفیت از ساعت به دقیقه تبدیل شود، مقدار عددی قیمت واحد هم تغییر می‌کند.
• وقتی چند جواب دوگان بهینه وجود داشته باشد، «قیمت سایه‌ای یکتا» ممکن است تعریف‌نشده باشد و باید از بازه یا تحلیل اضافی استفاده کرد.

۵. چطور از دوگان در پروژه استفاده کنیم؟

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

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

سطح ۱ — تبدیل: برای Max 5x1+4x2 با قید 2x1+x2≤8 و متغیرهای نامنفی، دوگان را بنویسید.

سطح ۲ — گواه بهینگی: برای مثال کارگاه، مجازبودن (2,6) و (20,10) را مستقل بررسی کنید و از برابری دو مقدار هدف نتیجه بگیرید.

سطح ۳ — تحلیل: اگر مدل جواب بهینه چندگانه داشته باشد، آیا لزوماً قیمت سایه‌ای یک منبع یکتا است؟ یک استدلال درباره خطر نتیجه‌گیری از «قید فعال ⇒ قیمت مثبت» بنویسید.

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