روش سیمپلکس؛ از جدول اولیه تا جواب بهینه

چرا شرط بهینگی جدول سیمپلکس معتبر است؟

در فرم استاندارد، وقتی یک پایه مجاز B داریم، هر متغیر غیربنیادی می‌تواند از مقدار صفر افزایش یابد. تابع هدف نسبت به تغییر این متغیر با «هزینه کاهش‌یافته» تغییر می‌کند. برای بیشینه‌سازی، اگر قرارداد هزینه کاهش‌یافته را r_j=c_j−c_BᵀB⁻¹A_j بگیریم، وجود r_j>0 امکان بهبود را نشان می‌دهد؛ اگر همه مقادیر r_j≤0 باشند، جواب پایه فعلی بهینه است. در نمایش جدول با قرارداد Z−Σcx علامت سطر هدف معکوس است. قرارداد جدول را قبل از انتخاب ستون ورودی بررسی کن.

Max Z = 3x + 2y
x+y <= 4,  x <= 2,  y <= 3
x,y >=0
First entering variable: x (objective coefficient 3)
Ratio test for x: 4/1=4, 2/1=2 -> x enters, second row leaves
Then y enters: x+y <=4 -> y=2
Optimal: (x,y)=(2,2), Z=10

این مثال دوم مستقل از مدل ۴۰ و ۳۰ ابتدای درس است. در نقطه بهینه، دو قید اول فعال و قید سوم یک واحد شل دارد. آزمون نسبت فقط روی ضرایب مثبت ستون ورودی انجام می‌شود؛ نسبت تقسیم بر صفر یا ضریب منفی مجاز نیست.

تباهی، چندجوابی و نامحدود بودن

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

نمونه تصمیم مدیریتی و محدودیت مدل

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

تمرین‌های تکمیلی با پاسخ

پایه: برای Max 3x+2y با قیود مثال دوم، مقدار هدف نقطه (۲،۲) را حساب کن.

میانی: در همان مثال، برای ورود x کدام قید آزمون نسبت را می‌بَرد؟

پیشرفته: اگر ضریب هدف x از ۳ به صفر تغییر کند، آیا همان جواب (۲،۲) لزوماً بهینه می‌ماند؟