سوال ۱۳۷ کنکور ارشد مدیریت ۱۴۰۴

Official key / کلید رسمی: کلید رسمی گزینهٔ ۴، یعنی ۵ متغیر و ۸ محدودیت است؛ با قرارداد معمول نامنفی‌بودن متغیرها، مدل خطی معادل زیر ۵ متغیر و ۶ محدودیت ساختاری دارد و به گزینهٔ ۳ می‌رسد.

از خطی‌سازی کمینه و بیشینه (hypograph/epigraph linearization) استفاده می‌کنیم. در مدل چاپ‌شده، محدودیت علامت متغیرها ذکر نشده است؛ ابتدا فرض معمول مدل‌سازی یعنی $x_1,x_2,x_3\ge0$ را صریح می‌کنیم. در این حالت، عبارت داخل هر دو قدر مطلق نامنفی است و علامت قدر مطلق اثری ندارد.

متغیر $u$ را برای کمینه و متغیر $v$ را برای بیشینه تعریف می‌کنیم. چون تابع هدف اولی را افزایش و دومی را کاهش می‌دهد، نامساوی‌ها در نقطهٔ بهینه به مقدار موردنظر می‌رسند:

سه متغیر اصلی و دو متغیر کمکی داریم؛ برای هر متغیر کمکی نیز سه نامساوی لازم است:

گزینهٔ ۱ دو متغیر کمکی را حذف کرده است. گزینهٔ ۲ فقط چهار نامساوی شاخه‌ها را می‌شمارد و سقف ثابت و شاخهٔ آخر بیشینه را کنار می‌گذارد. ظاهراً گزینهٔ کلیدی ۴ برای هر شاخهٔ قدر مطلق دو قید شمرده است؛ برای متغیرهای نامنفی این کار لازم نیست و برای متغیرهای آزاد نیز معادل‌بودن مدل را اثبات نمی‌کند.

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

جایگذاری مستقیم نیز نادرستیِ میان‌بر دوطرفه را نشان می‌دهد. در $x_1=1,x_2=x_3=0$، کمینهٔ چاپ‌شده برابر $\min(\tfrac{3}{4},\tfrac{1}{2},25)=\tfrac{1}{2}$ است. اعمال هر دو علامت برای هر شاخه، به‌جای آن $u\le-\tfrac{3}{4}$ را تحمیل می‌کند و مقدار را به $-\tfrac{3}{4}$ تغییر می‌دهد. بنابراین دو نامساوی اضافیِ شاخه‌ها، تابع هدفِ نمایش‌داده‌شده را عوض می‌کنند و تبدیل معتبر قدر مطلق نیستند.

تلهٔ رایج: جایگزین‌کردن $u\le|a|$ با هر دو قید $u\le a$ و $u\le-a$ در واقع $u\le-|a|$ را تحمیل می‌کند که پوشِ مخالف است. اگر متغیرهای اصلی آزاد باشند، کمینهٔ قدر مطلق‌ها عموماً تابعی غیرمقعر است و با این میان‌بر دو نامساوی خطی نمی‌شود. بنابراین حذف دامنهٔ علامت متغیرها مؤثر است.