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

فرموله‌کردن مسئلهٔ برنامه‌ریزی خطی و حالات خاص آن

چگونه یک بند نثرِ مدیریتی به متغیرهای تصمیم، یک تابع هدف خطی و مجموعه‌ای از محدودیت‌های خطی تبدیل می‌شود — شامل الگوهای کهن‌الگویی که کنکور دوست دارد (گلوگاه مونتاژ/ماکسی‌مین، سیاست‌های نسبتی و درصدی، متعادل‌سازی بار کاری با قدرمطلق اختلاف) و خطی‌سازی آن‌ها — و چگونه چهار حالت خاصِ مدلِ نهایی را نام ببریم: جواب بهینهٔ چندگانه، تبهگنی (موقت در برابر بهینه)، بی‌کرانی و نبود جواب موجه. پوشش شیفت با اندیس زمانی، افق چرخه‌ای و تصریح مفروضات شروع و پوشش را نیز دربر می‌گیرد.

کارت مفهوم کنکور ارشد مدیریت

اهمیت

۰/۵

۱. تعریف — Definition

برنامه‌ریزی خطی (linear programming, LP) یعنی بهینه‌سازی یک تابع هدف (objective function) خطی بر حسب متغیرهای تصمیم (decision variables) پیوسته، تحت مجموعه‌ای متناهی از محدودیت‌های (constraints) خطی و شرط نامنفی بودن (non-negativity restrictions). مدل‌سازی / فرموله‌کردن (formulation) کاری است که پیش از هر روش حلی انجام می‌شود: تبدیل یک بند از نثر مدیریتی به دقیقاً همان سه‌گانه. همه‌چیز به واژهٔ خطی آویخته است — هر جملهٔ متغیردار خطی، متغیری با توان یک دارد، فقط در یک ثابت ضرب می‌شود و جمله‌ها صرفاً با هم جمع می‌شوند؛ نه حاصل‌ضرب متغیرها، نه توان، نه نسبت متغیرها، و نه هیچ $\max$ / $\min$ /قدرمطلقِ باقی‌مانده. مدلی که با یکی از این شکل‌های ممنوع بیان شده باشد خودبه‌خود رد نمی‌شود: اگر بتوان با افزودن یک متغیر یا شکستن یک محدودیت آن را خطی‌سازی (linearization) کرد، باز هم یک LP است؛ و تشخیص اینکه کدام شکل‌ها خطی‌سازی‌پذیرند و کدام نیستند دقیقاً همان چیزی است که این بخش از آزمون می‌سنجد.

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

۲. خاستگاه — Origin and owners

بخش	صاحب نظریه	مسئله‌ای که برای حلش ابداع شد
مدل خطی برنامه‌ریزی تولید	ل. و. کانتوروویچ (۱۹۳۹)	تخصیص ماشین‌آلات و مواد کمیاب در صنعت شوروی برای بیشینه‌کردن ستانده
روش سیمپلکس (simplex method)	جرج ب. دانتزیگ (۱۹۴۷)	مسائل «برنامه‌ریزی» (زمان‌بندی و لجستیک) نیروی هوایی آمریکا که برای محاسبات سرانگشتی بیش از حد بزرگ بودند
تفسیر اقتصادی قیمت‌های دوگان	ت. س. کوپمنز — جایزهٔ نوبل اقتصاد ۱۹۷۵ مشترکاً به کانتوروویچ و کوپمنز برای نظریهٔ تخصیص بهینهٔ منابع رسید	چسباندن یک قیمت به هر منبع کمیاب، در دلِ خودِ بهینه‌سازی
پیوند دوگانگی LP با بازی‌های دو‌نفرهٔ مجموع‌صفر	جان فون نویمان، برخاسته از نظریهٔ بازی‌های او	پیوند دوگانگی LP با بازی‌های متناهی مجموع‌صفر؛ دریافتی‌های آفینِ ماکسی‌مین مدل LP می‌پذیرند

نکتهٔ تاریخی‌ای که برای آزمون اهمیت دارد: LP به‌عنوان ابزار تخصیص منابع زاده شد، پس خوانش پیش‌فرض هر محدودیت این است که «چیزی کمیاب مصرف می‌شود» ( $\le$ ) یا «تعهدی برآورده می‌شود» ( $\ge$ ). شکل‌های نامتعارف بند ۳.۵ همگی پیوندهای بعدی بر همین تنه‌اند.

۳. ساختار — The model and its parts

۳.۱ مدل متعارف

\text{Max (or Min)}\quad Z=\sum_{j=1}^{n} c_j x_j

\text{s.t.}\qquad \sum_{j=1}^{n} a_{ij}x_j \;\{\le,=,\ge\}\; b_i \quad (i=1,\dots,m), \qquad x_j\ \ge\ 0 \quad (j=1,\dots,n)

نماد	نام فارسی	معنا	در متن سؤال از کجا می‌آید
$x_j$	متغیر تصمیم	آنچه مدیر واقعاً انتخاب می‌کند	جمله‌ای که در آن «چند تا / چه مقدار / چه مدت» آمده است
$c_j$	ضریب تابع هدف	سهم یک واحد از $x_j$ در $Z$	سود، هزینه، زمان یا مسافت به‌ازای هر واحد
$a_{ij}$	ضریب فنی	مصرف منبع $i$ توسط یک واحد از $x_j$	بدنهٔ جدول داده‌ها
$b_i$	مقدار در دسترس / طرف راست	ظرفیت، نیاز یا هدف	حاشیهٔ جدول، یا جملهٔ سیاستی

سه فرم مرتباً با هم اشتباه گرفته می‌شوند. نام‌گذاری بین کتاب‌ها متفاوت است؛ قرارداد زیر را به کار ببرید:

فرم	نام فارسی	محدودیت‌ها	متغیرها
کلی / متعارف	فرم کلی	هر ترکیبی از $\le$ ، $=$ ، $\ge$	$x_j\ge 0$
فرم استاندارد	فرم استاندارد	همه تساوی، $b_i\ge 0$ (متغیر کمبود/slack $s_i$ به یک $\le$ اضافه می‌شود، از یک $\ge$ متغیر مازاد/surplus کم می‌شود، و هرجا پایهٔ شروع وجود ندارد متغیر مصنوعی/artificial افزوده می‌شود)	همه $\ge 0$
فرم ماتریسی	فرم ماتریسی	$Ax=b$	$x\ge 0$

۳.۲ چهار فرض (مفروضات) — و اینکه چه چیزی هرکدام را نقض می‌کند

فرض	نام فارسی	بیان	نقض‌کننده
تناسب	تناسب	دو برابر کردن $x_j$ سهم و مصرف منبع آن را دو برابر می‌کند	تخفیف مقداری، منحنی یادگیری، هزینهٔ راه‌اندازی
جمع‌پذیری	جمع‌پذیری	کل برابر مجموع اجزاست، بدون هیچ برهم‌کنشی	جمله‌ای مانند $x_1x_2$ ، یا دو محصول که با هم تداخل دارند
تقسیم‌پذیری	تقسیم‌پذیری	مقادیر کسری معنادارند	واحدهای تقسیم‌ناپذیر $\Rightarrow$ برنامه‌ریزی عدد صحیح
قطعیت	قطعیت	هر $c_j,a_{ij},b_i$ ثابتی معلوم است	تقاضای تصادفی $\Rightarrow$ برنامه‌ریزی تصادفی

فرض پنجم و ساختاری را هم اضافه کنید — نامنفی بودن: متغیری که واقعاً می‌تواند هر دو علامت را بگیرد به‌صورت $x = x^{+}-x^{-}$ با $x^{+},x^{-}\ge 0$ نوشته می‌شود و هرگز در جدول استاندارد «آزاد» رها نمی‌شود.

۳.۳ انتخاب متغیرهای تصمیم — گامی که همه‌چیز را تعیین می‌کند

بسیاری از گزینه‌های انحرافیِ فرموله‌کردن از خطای اندیس‌گذاری استفاده می‌کنند. پیش از نوشتن حتی یک ضریب، این جمله را کامل کنید: « $x_j$ تعداد ____ در هر ____ است».

اندیس روی چه چیزی حرکت می‌کند…	آنگاه درایهٔ جدول $a_{ij}$ یعنی…	هر سطر ماشین/منبع عبارت است از…
محصولات (تعداد واحدهای ساخته‌شده)	مصرف منبع $i$ به‌ازای هر واحد محصول $j$	یک سطر/ستون از جدول با وزن چند متغیر
زمان (روز یا ساعتی که یک واحد کار می‌کند)	ستانده در هر روزِ آن واحد	نرخ آن واحد ضرب‌در متغیر منحصر به خودش
الگوها / روش‌ها (مانند برش یا اختلاط)	چند قطعه از نوع $i$ با الگوی $j$ حاصل می‌شود	مجموع روی همهٔ الگوهای مجاز
تخصیص‌ها ( $x_{ij}$ ، اندیس دوگانه)	هزینهٔ جفت‌کردن $i$ با $j$	یک محدودیت به‌ازای هر سطر و یک به‌ازای هر ستون

اگر صورت سؤال سطر تعریفی مانند « $x_j$ : تعداد ...» چاپ کرده باشد، آن سطر بر هر شهودی دربارهٔ ظاهر جدول اولویت دارد. گزینه‌های انحرافی با تغییر اندیس‌گذاری ساخته می‌شوند — بیشتر اوقات با جمع‌زدن کل یک سطر یا ستون جدول و چسباندن آن مجموع به یک متغیر واحد، که فقط در صورتی درست است که اندیس روی همان بُعد حرکت کند.

۳.۳الف پوشش شیفت با اندیس زمانی

در زمان‌بندی کارکنان / ناوگان (staffing/vehicle scheduling)، $x_s$ تعداد واحدهایی است که شیفت مجاز $s$ را آغاز می‌کنند؛ تقاضای $d_p$ به دورهٔ $p$ تعلق دارد. ماتریس پوشش $A$ را بسازید: درایهٔ $a_{ps}=1$ یعنی شیفت $s$ کل بازهٔ نیاز $p$ را پوشش می‌دهد؛ در غیر این صورت صفر است. هزینهٔ شیفت یا، با هزینه‌های برابر و یک شیفت برای هر واحد، تعداد واحدهای تخصیص‌یافته را کمینه کنید:

\text{Min}\ Z=\sum_s c_sx_s,\qquad \sum_s a_{ps}x_s\ge d_p\quad\text{for every }p,\qquad x_s\ge0.

کارکنان یا اتوبوس‌های تقسیم‌ناپذیر متغیر صحیح می‌خواهند؛ حذف صحیح‌بودن، آرام‌سازی LP می‌دهد. ستون‌ها شروع‌های مجاز و سطرها نیازهای پوشش را می‌شمارند. نامنفی‌بودن، سطر کارکردیِ تقاضا نیست.

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

A=\begin{pmatrix}1&0&0&1\\1&1&0&0\\0&1&1&0\\0&0&1&1\end{pmatrix},\quad d=\begin{pmatrix}2\\3\\3\\2\end{pmatrix},\quad x=\begin{pmatrix}1\\2\\1\\1\end{pmatrix},\quad Ax=d.

پنج واحد کافی است. جمع سطرهای تقاضا می‌دهد $2\sum_sx_s\ge10$ ؛ پس پنج بهینه است. در افق محدود، پوشش انتقالیِ ابتدای افق را صریحاً بدهید و تکرار روز را فرض نکنید.

وقتی طول دورهٔ تقاضا و شیفت متفاوت است، در هر تغییر تقاضا، شروع و پایان شیفت بازه را بشکنید تا پوشش لحظه‌ای تضمین شود. شیفتی که فقط بخشی از دورهٔ تقاضا را می‌پوشاند، پوشش کامل نیست. هم‌پوشانی کسری، ساعت تأمین‌شده را بیان می‌کند، نه حداقل کارکنان هم‌زمان را. نسبت طول‌ها به‌تنهایی نه شروع‌های مجاز را انتخاب می‌کند و نه ماتریس پوشش را توجیه می‌کند؛ پیش از شمارش متغیر و محدودیت، قرارداد مدل را بیان کنید.

۳.۴ فهرست کهن‌الگوهای محدودیت

جملهٔ مدیریتی (نشانهٔ فارسی)	شکل جبری
ظرفیت / در دسترس بودن — «حداکثر»، «در دسترس»	$\sum_j a_{ij}x_j \le b_i$
نیاز / تعهد — «حداقل»، «باید تأمین شود»	$\sum_j a_{ij}x_j \ge b_i$
تقاضای دقیق / توازن — «دقیقاً»، «کل تولید برابر است با»	$\sum_j a_{ij}x_j = b_i$
نسبت ثابت میان دو متغیر — «نسبت الف به ب دو برابر»	$x_1 = 2x_2 \;\Rightarrow\; x_1-2x_2=0$
حداقل سهم از کل (اختلاط) — «حداقل ۳۰ درصد مخلوط»	$x_1 \ge 0.3(x_1+x_2+x_3)\;\Rightarrow\; 0.7x_1-0.3x_2-0.3x_3\ge 0$
سقف‌گذاری بر نسبت دو مجموع — «نسبت ضایعات به کل حداکثر $\alpha$ »	$\dfrac{A(x)}{B(x)}\le \alpha \;\Rightarrow\; A(x)-\alpha B(x)\le 0$
توازن دو بار کاری — «هیچ‌کدام بیش از $d$ از دیگری»	$\lvert L_1(x)-L_2(x)\rvert \le d$
گلوگاه / مونتاژ — «مونتاژ از $a$ قطعهٔ A و $b$ قطعهٔ B»	$Z=\operatorname{Min}\left\{\dfrac{\sum A}{a},\dfrac{\sum B}{b}\right\}$ ، که باید بیشینه شود
تسطیح بار / زمان تکمیل — «کمینه‌کردن بیشترین بار»	$Z=\operatorname{Max}\{L_1,\dots,L_k\}$ ، که باید کمینه شود
«یا این یا آن»، «اگر–آنگاه»، هزینهٔ راه‌اندازی	نیازمند متغیر دودویی و $M$ بزرگ است؛ از LP خالص خارج و وارد برنامه‌ریزی عدد صحیح می‌شود

۳.۵ خطی‌سازی — چه چیزی نجات‌پذیر است و چه چیزی نیست

توابع شاخه، بارها و صورت/مخرج نسبت در زیر باید آفین باشند. کران بالای قدرمطلق باید نامنفی باشد. کران پایینِ قدرمطلق فقط با مقدار مثبت و امکان هر دو علامت، تفکیک نامحدب است؛ دامنهٔ با علامت معلوم می‌تواند آن را ساده کند.

شکل بیان‌شده (غیرخطی)	معادل قابل‌قبول در LP	توضیح
$\text{Max } Z=\operatorname{Min}\{f_1,\dots,f_k\}$ (ماکسی‌مین)	$\text{Max } Z=y$ با شرط $y\le f_i$ برای هر $i$	متغیر به پوش پایینی می‌رسد؛ جز با توجیه نامنفی‌بودن، آن را آزاد بگیرید
$\text{Min } Z=\operatorname{Max}\{f_1,\dots,f_k\}$ (مینی‌ماکس)	$\text{Min } Z=y$ با شرط $y\ge f_i$ برای هر $i$	متغیر به پوش بالایی می‌رسد؛ جز با توجیه نامنفی‌بودن، آن را آزاد بگیرید
$\lvert f(x)\rvert \le d$	$-d \le f(x)\le d$ ، یعنی زوج $f\le d$ و $-f\le d$	محدب — کاملاً خطی
$\lvert f(x)\rvert \ge d$	عموماً با کران مثبت و امکان هر دو علامت، نامحدب است؛ از تفکیک منطقی / متغیر دودویی استفاده کنید	علامت $\ge$ روی یک قدرمطلق در هر گزینه‌ای پرچم قرمز است
$\dfrac{A(x)}{B(x)}\le \alpha$ ، با $B(x)>0$	$A(x)-\alpha B(x)\le 0$	طرفین وسطین کنید؛ مخرج یک عبارت متغیر باقی می‌ماند
$\operatorname{Min}\sum_i \lvert f_i(x)\rvert$	$\operatorname{Min}\sum_i (d_i^{+}+d_i^{-})$ با $f_i=d_i^{+}-d_i^{-}$ ، $d^{\pm}\ge 0$	ترفند متغیرهای انحراف در برنامه‌ریزی آرمانی
$x_j \in \{0,1\}$ ، حاصل‌ضرب $x_1x_2$ ، توان‌ها	LP خالص نیست؛ برخی حاصل‌ضرب‌های دودویی خطی‌سازی عدد صحیح مختلط می‌پذیرند	برنامه‌ریزی عدد صحیح / غیرخطی

۳.۶ حالات خاص

وجود بهینه را از یکتایی و تبهگنی جدا کنید: چندگانگی و تبهگنی می‌توانند هم‌زمان باشند. علامت‌های جدول زیر برای بیشینه‌سازی با قرارداد هزینهٔ کاهش‌یافتهٔ بیان‌شده است.

حالت	نام فارسی	امضای ترسیمی	امضا در جدول نهایی
بهینهٔ یکتا	جواب بهینهٔ منحصربه‌فرد	تابع هدف یک نقطه را انتخاب می‌کند؛ در حالت ترسیمی نامتبهگن، دقیقاً $n$ محدودیت فعال مستقل است	برای همهٔ ستون‌های غیرپایه $z_j-c_j>0$ کافی است؛ مثبت‌بودن همهٔ پایه‌ها همچنین نامتبهگنی می‌دهد
جواب بهینهٔ چندگانه	جواب بهینهٔ چندگانه	خط تابع هدف موازی یک ضلع فعال است؛ کل یک ضلع (بی‌نهایت نقطه) بهینه است	یک متغیر غیرپایه دارای $z_j-c_j=0$ است و حرکت موجه به نقطه‌ای متفاوت وجود دارد
تبهگنی	تبهگنی	بیش از $n$ محدودیت در یک رأس فعال‌اند (غالباً یک محدودیت زائد که دقیقاً از آن رأس می‌گذرد)	یک متغیر پایه برابر صفر است؛ زادهٔ تساوی در آزمون کمترین نسبت
— موقت	تبهگن موقت	رأس بیش‌ازحد‌تعیین‌شده یک رأس میانی است، نه بهینه	متغیر پایهٔ صفر در جدولی میانی ظاهر می‌شود و سپس خارج می‌شود؛ همین حالت است که خطر دور زدن (cycling) دارد
— بهینه	تبهگن بهینه	رأس بیش‌ازحد‌تعیین‌شده همان نقطهٔ بهینه است	متغیر پایهٔ صفر در جدول نهایی هنوز در پایه است
تابع هدف بی‌کران	جواب بی‌کران	ناحیه در جهت بهبود باز است	ستون ورودی‌ای که همهٔ درایه‌هایش $\le 0$ است: نه متغیر خروجی، نه آزمون نسبت
نبود جواب موجه	فاقد جواب موجه / ناحیهٔ موجه تهی	محدودیت‌ها هیچ ناحیهٔ مشترکی ندارند	یک متغیر مصنوعی در بهینگی با مقدار مثبت در پایه باقی می‌ماند
محدودیت زائد	محدودیت زائد	حذفش ناحیه را تغییر نمی‌دهد؛ می‌تواند مرز را لمس کند	استنتاج از سایر سطرها را ثابت کنید؛ الگوی کمبود به‌تنهایی کافی نیست

«فاقد جواب بهینه» (no optimal solution) اصطلاح چتری‌ای است که دو مورد از این‌ها را می‌پوشاند — نبود جواب موجه و بی‌کرانی — و نه هیچ‌چیز دیگر.

۴. طرز کار — رویهٔ فرموله‌کردن

۱. متغیرها را با کلمات و همراه واحد نام‌گذاری کنید. « $x_1$ = تن مخلوط A در هفته»، « $x_j$ = تعداد ورق‌های بریده‌شده با الگوی $j$ »، « $y_i$ = ساعت‌های کارکرد خط $i$ در روز». اگر صورت سؤال این سطر را داده است، عیناً رونویسی کنید؛ بُعد اندیس قابل مذاکره نیست. ۲. اگر متغیرها الگو هستند، گزینه‌ها را برشماری کنید. در مدل‌های برش/اختلاط فهرست متغیرها داده نمی‌شود — خودتان می‌سازیدش. با هزینهٔ یکسان شاخه‌ها و کران پایین تقاضا، الگوهای کارا را نگه دارید: الگویی که پس‌ماندش یک قطعهٔ دیگر را جا می‌دهد مغلوب است. تقاضای دقیق یا جریمهٔ اضافه‌تولید می‌تواند این قاعده را تغییر دهد. تعداد الگوهای بازمانده تعداد متغیرها را تعیین می‌کند و همین به‌تنهایی می‌تواند یک سؤال چهارگزینه‌ای را فیصله دهد. ۳. تابع هدف را بنویسید و جهتش را از «هدف» صورت سؤال تثبیت کنید. دقیقاً یک تابع هدف. اگر دو هدف ظاهر شد، یکی از آن‌ها در واقع یک محدودیت است (یا مدل، برنامه‌ریزی آرمانی است). ۴. جمله‌های محدودیت را یکی‌یکی بردارید و پس از هر کدام بپرسید «هر طرف با چه واحدی است؟». دقیقه در برابر ساعت، سانتی‌متر در برابر متر، ریال در برابر تومان — این ناسازگاری تله‌ای عمدی است ( $1$ ساعت در جدولی برحسب دقیقه به‌صورت $60$ وارد می‌شود). ۵. نرمال‌سازی کنید: متغیرها سمت چپ، ثابت‌ها سمت راست، بدون کسری که متغیر در مخرجش باشد، بدون قدرمطلق، بدون $\min/\max$ — بند ۳.۵ را چندان اعمال کنید تا هر سطر خطی شود. ۶. شرط نامنفی بودن را بیفزایید، و صحیح‌بودن را فقط اگر صورت سؤال واحدهای کامل خواسته است. ۷. آزمون سلامت با یک نقطهٔ آشکارا موجه (غالباً مبدأ) و یک نقطهٔ آشکارا ناموجه؛ محدودیتی که هیچ‌کدام را نپذیرد الزاماً وارونه نیست؛ جهت را با سیاست اصلی بسنجید، نه صرفاً با مبدأ.

خواندن یک مدل تمام‌شده برای تشخیص حالت خاصش: بهینه را پیدا کنید، سپس بشمارید. فرض کنید $n$ تعداد بُعد مؤثر پس از اعمال تساوی‌ها و $k$ تعداد نامساوی‌های فعال در مدل ترسیمیِ معمول با بُعد کامل باشد (نامنفی‌بودن را بشمارید و سطرهای تکراری را دوبار نشمارید):

k = n \;\Rightarrow\; \text{ordinary vertex}, \qquad k > n \;\Rightarrow\; \textbf{degenerate}, \qquad \text{objective } \parallel \text{ binding edge} \;\Rightarrow\; \textbf{multiple optima}

و اگر اصلاً بهینه‌ای وجود نداشت، میان ناحیهٔ تهی (فاقد جواب موجه) و جهت بهبودی که هرگز تمام نمی‌شود (بی‌کران) تصمیم بگیرید.

۵. مثال حل‌شده — Worked mini-examples

(الف) یک فرموله‌کردن کامل، از ابتدا تا انتها

کارگاهی دو مدل کابینت می‌سازد. به‌ازای هر واحد، مدل ۱ سود $40$ و مدل ۲ سود $60$ (هزار ریال) دارد؛ مدل ۱ مقدار $3\ \mathrm{m}^2$ تخته و $1$ نفرساعت کار، و مدل ۲ مقدار $5\ \mathrm{m}^2$ و $1$ نفرساعت مصرف می‌کند. هفتگی $150\ \mathrm{m}^2$ تخته و $40$ نفرساعت موجود است، و بازاریابی اصرار دارد که مدل ۱ دست‌کم ۴۰ درصد کل واحدهای تولیدی باشد.

متغیرها: $x_1,x_2$ = تعداد واحدهای مدل ۱ و مدل ۲ که در هفته تولید می‌شود.

تابع هدف:

\text{Max } Z = 40x_1+60x_2

منابع:

3x_1+5x_2 \le 150 \quad (\text{board}), \qquad x_1+x_2 \le 40 \quad (\text{labour})

سیاست سهم — توجه کنید که این یک نسبت است، پس پیش از آنکه بتواند محدودیت شود باید پاک‌سازی شود:

\frac{x_1}{x_1+x_2}\ \ge\ 0.4 \;\Longrightarrow\; x_1 \ge 0.4x_1+0.4x_2 \;\Longrightarrow\; 0.6x_1-0.4x_2 \ge 0 \;\Longrightarrow\; 3x_1-2x_2 \ge 0

به‌همراه $x_1,x_2\ge 0$ . حال رأس‌های ناحیه را ارزیابی کنید:

رأس	چگونه پدید می‌آید	موجه؟	$Z=40x_1+60x_2$
$(0,0)$	مبدأ	بله	$0$
$(40,0)$	نیروی کار فعال، $x_2=0$	تخته: $120\le150$ ✔	$1600$
$(25,15)$	تخته $\cap$ نیروی کار	سهم: $75\ge 30$ ✔	$40(25)+60(15)=1000+900=\mathbf{1900}$
$\left(\tfrac{100}{7},\tfrac{150}{7}\right)$	تخته $\cap$ سهم	بله	$\tfrac{4000+9000}{7}\approx 1857.1$

بهینه $x^{*}=(25,15)$ با $Z^{*}=1900$ (هزار ریال) است. در آن نقطه دو محدودیت فعال‌اند و دو متغیر داریم ( $k=n=2$ )، پس رأس عادی است: یک بهینهٔ یکتا و نامتبهگن، با محدودیت سهم به‌صورت شل — اطلاعاتی که به‌اندازهٔ خودِ پاسخ ارزش دارد، چون محدودیت شل قیمت سایه‌ای صفر دارد.

(ب) سه جمله‌ای که به خطی‌سازی نیاز دارند

گلوگاه / مونتاژ. هر ست کامل به $1$ واحد قطعهٔ P و $4$ واحد قطعهٔ Q نیاز دارد. خط ۱ که $y_1$ ساعت کار می‌کند، در هر ساعت $6$ قطعهٔ P و $8$ قطعهٔ Q تولید می‌کند؛ خط ۲ که $y_2$ ساعت کار می‌کند، در هر ساعت $2$ قطعهٔ P و $20$ قطعهٔ Q. قطعاتی که نتوان آن‌ها را در یک ست کامل جفت کرد بی‌ارزش‌اند، پس تعداد ست‌هایی که موجودی هر قطعه می‌تواند پشتیبانی کند برابر است با

n_P=\frac{6y_1+2y_2}{1}=6y_1+2y_2, \qquad n_Q=\frac{8y_1+20y_2}{4}=2y_1+5y_2

\text{Max } Z=\operatorname{Min}\{\,6y_1+2y_2,\;2y_1+5y_2\,\} \;\;\xrightarrow{\text{linearize}}\;\; \text{Max } Z=w \;\;\text{s.t.}\;\; w\le 6y_1+2y_2,\;\; w\le 2y_1+5y_2

توجه کنید که تقسیم بر نسبت‌های مونتاژ ترتیب خط‌ها را جابه‌جا می‌کند: خط ۲ تولیدکنندهٔ بهتر Q اما تولیدکنندهٔ بدتر P است، و دقیقاً به همین دلیل تابع هدف $\operatorname{Min}$ آن دو است و نه مجموعشان.

توازن بار کاری. با بارهای $L_1=3x_1+x_2$ و $L_2=x_1+4x_2$ برحسب دقیقه، «هیچ ماشینی نباید در روز بیش از نیم ساعت بیشتر از دیگری کار کند» یعنی

\lvert L_1-L_2\rvert \le 30 \;\Longrightarrow\; \lvert 2x_1-3x_2\rvert \le 30 \;\Longrightarrow\; \begin{cases} 2x_1-3x_2 \le 30\\ -2x_1+3x_2 \le 30\end{cases}

نسبت ضایعات. طول شاخهٔ اولیه $250$ سانتی‌متر؛ چهار الگوی برش به‌ترتیب $w=(25,10,5,0)$ سانتی‌متر ضایعات دارند؛ سیاست: ضایعات باید حداکثر $4$ درصد کل طول مصرف‌شده باشد. سهمیهٔ مجاز هر شاخه $0.04\times 250=10$ سانتی‌متر است و طرفین‌وسطین کردن نسبت می‌دهد

\frac{\sum_j w_j x_j}{250\sum_j x_j}\le 0.04 \;\Longrightarrow\; \sum_j (w_j-10)x_j \le 0 \;\Longrightarrow\; 15x_1+0x_2-5x_3-10x_4\le 0

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

\frac{\sum_j q_jx_j}{Q}\ge q_{\min}\;\Longleftrightarrow\;\sum_jq_jx_j\ge q_{\min}Q,\qquad \sum_jx_j=Q>0.

(ج) نام‌گذاری حالت خاص از روی یک مدل دومتغیره

مدل	مقادیر رأس‌ها	تشخیص
$\text{Max }2x_1+4x_2$ با $x_1+2x_2\le 8$ ، $x_1+x_2\le 6$	$(0,4)\!:16$ ، $(4,2)\!:16$ ، $(6,0)\!:12$	تابع هدف $\parallel$ محدودیت اول و دو رأس مساوی‌اند $\Rightarrow$ جواب بهینهٔ چندگانه: هر نقطه از ضلع میان آن‌ها بهینه است
$\text{Max }3x_1+2x_2$ با $x_1\le 2$ ، $x_2\le 2$ ، $x_1+x_2\le 4$	بهینه $(2,2)$ با $Z=10$	سه محدودیت فعال، ولی فقط دو متغیر (و $x_1+x_2\le4$ زائد است و ناحیه را تنها در همان یک نقطه لمس می‌کند) $\Rightarrow$ جواب تبهگن بهینه
$\text{Max }x_1+x_2$ با $x_1-x_2\le 1$ ، $x\ge 0$	هیچ بیشینهٔ متناهی‌ای ندارد	ناحیه در راستای $x_2\to\infty$ باز است و تابع هدف در همان جهت بهبود می‌یابد $\Rightarrow$ جواب بی‌کران
$\text{Min }x_1+x_2$ روی همان ناحیه	بهینه $(0,0)$ ، $Z=0$	ناحیه هنوز بی‌کران است، اما بهینه وجود دارد — ناحیهٔ بی‌کران با مسئلهٔ بی‌کران یکی نیست
هر مدلی با $x_1+x_2\le 2$ و $x_1+x_2\ge 5$	—	محدودیت‌های متناقض $\Rightarrow$ فاقد جواب موجه

۶. اشتباه نشود با… — Confused with

جفت مفاهیم	تفاوت واقعی	نشانهٔ لو‌دهنده
$\text{Max}\operatorname{Min}$ (ماکسی‌مین) در برابر $\text{Min}\operatorname{Max}$ (مینی‌ماکس)	ماکسی‌مین = ضعیف‌ترین مؤلفه را تا حد ممکن بالا ببر (گلوگاه، مونتاژ، بدترین‌حالت بازده)؛ مینی‌ماکس = قوی‌ترین مؤلفه را تا حد ممکن پایین بکش (تسطیح بار، زمان تکمیل، طولانی‌ترین انتظار)	عملگر بیرونی را با «هدف» صورت سؤال تطبیق دهید: «حداکثر کردن تولید» $\Rightarrow$ Max بیرونی؛ «کمینه‌کردن بیشترین بار» $\Rightarrow$ Min بیرونی. نیمی از گزینه‌ها فقط با همین می‌میرند
قطعات در برابر محصولات نهایی در تابع هدف گلوگاهی	دستور مونتاژ تقسیم می‌کند: $a$ قطعهٔ A برای هر واحد یعنی موجودی A از $\sum A/a$ محصول پشتیبانی می‌کند	اگر گزینه درایه‌های خام جدول را بدون تغییر حمل کند، دارد قطعات را می‌شمارد نه محصولات را
محدودیت نسبتی در برابر یک کران بالای ساده	مخرج یک نسبت خودش عبارتی متغیر است و باید با طرفین‌وسطین به چپ منتقل شود	با کل متغیر، مخرج را در $\le 0$ حفظ کنید؛ کل مثبتِ ثابت، طرف راست عددی را مجاز می‌کند
نسبت مجموع‌ها در برابر نسبت برای یک واحد	«ضایعات $\le 10$ درصد کل بریده‌شده» تجمعی است؛ «هر شاخه حداکثر $\le 15$ سانتی‌متر ضایعات» به‌ازای واحد است	نسخهٔ تجمعی $\sum x_j$ را در خود نگه می‌دارد؛ نسخهٔ واحدی نه
$\lvert f\rvert \le d$ در برابر $\lvert f\rvert \ge d$	حالت $\le$ محدب است و به دو محدودیت معمولی می‌شکند؛ حالت $\ge$ بیرونِ یک نوار را توصیف می‌کند — نامحدب، پس اصلاً محدودیت LP نیست	هر گزینه‌ای با $\ge$ روی قدرمطلق تقریباً همیشه گزینهٔ انحرافی است
«بیش از … نکند» در برابر «حداقل …»	اولی کران بالا $\le$ است و دومی کران پایین $\ge$	پیش از دست‌زدن به ضرایب، فعل را ترجمه کنید
اندیس روی محصولات در برابر اندیس روی ماشین‌ها/واحدها	اگر $j$ اندیس محصولات باشد، بار هر ماشین همهٔ متغیرها را با ضرایب متفاوت می‌آمیزد؛ اگر $j$ اندیس ماشین‌ها باشد، بار هر ماشین یک متغیر ضرب‌در یک مجموع ستونی است	ضرایبی که همان مجموع سطری یا ستونی جدول داده‌ها هستند، اندیس‌گذاری غلط را لو می‌دهند
جواب بهینهٔ چندگانه در برابر تبهگنی	چندگانه = چندین نقطهٔ بهینه (یک ضلع کامل)؛ تبهگنی = یک نقطه که با محدودیت‌های بیش از حد، بیش‌ازاندازه تعیین شده است	برای اولی $z_j-c_j$ های غیرپایه را وارسی کنید، برای دومی دنبال متغیر پایهٔ صفر بگردید. این دو می‌توانند هم‌زمان رخ دهند
تبهگنی موقت در برابر بهینه	موقت: متغیر پایهٔ صفر در جدولی میانی ظاهر و بعد خارج می‌شود (خطر دور زدن)؛ بهینه: در جدول نهایی هنوز آنجاست	بپرسید رأس بیش‌ازحدتعیین‌شده کجا قرار دارد: روی مسیر، یا در نقطهٔ بهینه
فاقد جواب موجه در برابر بی‌کران	فاقد جواب موجه = هیچ نقطه‌ای محدودیت‌ها را ارضا نمی‌کند؛ بی‌کران = نقاط فراوان‌اند، اما بهترینی وجود ندارد	هر دو پاسخ «فاقد جواب بهینه» می‌دهند، پس سؤالی که این عبارت را پیشنهاد می‌کند دارد اصطلاح چتری را می‌سنجد نه شاخه را
ناحیهٔ بی‌کران در برابر تابع هدف بی‌کران	ناحیهٔ موجه بی‌کران می‌تواند بهینهٔ متناهی داشته باشد؛ بهبود تابع هدف در امتداد نیم‌خط موجه را بررسی کنید	کمینه‌کردن یک هزینهٔ نامنفی روی ناحیه‌ای باز همیشه کران‌دار است
محدودیت زائد در برابر محدودیت فعال	زائد: حذفش ناحیه را تغییر نمی‌دهد؛ فعال: در بهینه تساوی برقرار است؛ سطر زائد می‌تواند فعال باشد و قیمت دوگانش لزوماً یکتا نیست	خط زائدی که ناحیه را دقیقاً در یک نقطه لمس می‌کند، سازندهٔ همیشگی تبهگنی است
LP در برابر برنامه‌ریزی عدد صحیح	تقسیم‌پذیری: LP مقدار $x=3.7$ را می‌پذیرد	«یا این یا آن»، «اگر–آنگاه»، هزینهٔ راه‌اندازی و انتخاب‌های بله/خیر همگی متغیر دودویی می‌خواهند و از LP خارج می‌شوند
LP در برابر برنامه‌ریزی آرمانی (goal programming)	LP یک تابع هدف را تحت محدودیت‌های سخت بهینه می‌کند؛ برنامه‌ریزی آرمانی انحراف‌های وزنی $d^{+},d^{-}$ از چند آرمان را کمینه می‌کند	ظاهرشدن متغیرهای انحراف، یا چند هدف رتبه‌بندی‌شده

نکتهٔ کنکوری: جهت، سپس شکل و سپس اندیس‌گذاری را بررسی کنید. ابتدا بیشینه/کمینه و کران بالا/پایین را ترجمه کنید. مخرج نسبت را با فرض مثبت‌بودن کل حذف کنید؛ کل ثابت می‌تواند طرف راست عددی بدهد. کران بالای قدرمطلق را بشکنید؛ کران پایین مثبت عموماً تفکیک منطقی می‌خواهد. پیش از انتخاب درایه یا مجموع جدول، تعریف چاپ‌شدهٔ متغیر را بخوانید. در حالات خاص، تعداد محدودیت‌های فعال را با بُعد مؤثر ترسیمی بسنجید و تبهگنی را با متغیر پایهٔ صفر تأیید کنید. هزینهٔ کاهش‌یافتهٔ صفرِ غیرپایه، نامزدِ بهینهٔ چندگانه است؛ حرکت موجه به نقطهٔ متفاوت را بررسی کنید. ناحیهٔ تهی ناموجه است؛ نیم‌خط موجهِ بهبوددهنده، تابع هدف بی‌کران می‌دهد.

فرمول‌های کلیدی

General linear programming model

\text{Max/Min } Z=\sum_{j=1}^{n} c_j x_j \quad \text{s.t.}\quad \sum_{j=1}^{n} a_{ij}x_j\;\{\le,=,\ge\}\;b_i,\qquad x_j\ge 0

Standard form (slack and surplus variables)

\sum_j a_{ij}x_j+s_i=b_i\ \ (\le),\qquad \sum_j a_{ij}x_j-s_i=b_i\ \ (\ge),\qquad s_i\ge 0

Assembly / bottleneck objective (a parts A and b parts B per unit)

\text{Max } Z=\operatorname{Min}\left\{\frac{\sum_j A_j x_j}{a},\;\frac{\sum_j B_j x_j}{b}\right\}

Maximin linearization

\text{Max }\operatorname{Min}\{f_1,\dots,f_k\}\;\Longleftrightarrow\;\text{Max } y\ \ \text{s.t.}\ \ y\le f_i\ \ \forall i

Minimax linearization

\text{Min }\operatorname{Max}\{f_1,\dots,f_k\}\;\Longleftrightarrow\;\text{Min } y\ \ \text{s.t.}\ \ y\ge f_i\ \ \forall i

Absolute-difference (workload balancing) constraint

\lvert L_1(x)-L_2(x)\rvert\le d\;\Longleftrightarrow\;-d\le L_1(x)-L_2(x)\le d

Ratio / percentage constraint linearization

\frac{A(x)}{B(x)}\le \alpha,\ B(x)>0\;\Longleftrightarrow\;A(x)-\alpha B(x)\le 0

Waste-ratio constraint over cutting patterns

\sum_j (w_j-\alpha L)\,x_j\le 0,\qquad \alpha L=\text{allowance per stock unit of length } L

Minimum-share (blending) constraint

x_1\ge \alpha\sum_{j} x_j\;\Longleftrightarrow\;(1-\alpha)x_1-\alpha\sum_{j\ne 1}x_j\ge 0

Degeneracy test at an optimal vertex

k=\#\{\text{active constraints}\}>n=\#\{\text{decision variables}\}\;\Rightarrow\;\text{degenerate optimal solution}

Graphical count applies to the usual full-dimensional inequality representation, including nonnegativity, after resolving equalities. The definitive algebraic criterion is a zero basic variable; a unique optimum may be degenerate.

Alternative optima in the final tableau

z_j-c_j=0\ \text{for a nonbasic }x_j\quad\text{and a distinct feasible zero-cost movement}\ \Rightarrow\ \text{multiple optima}

Time-indexed shift coverage

\text{Min}\ Z=\sum_s c_sx_s,\quad \sum_s a_{ps}x_s\ge d_p\quad\forall p,\quad x_s\ge0

Columns index permitted shifts; rows index coverage periods; refine partial overlaps and impose cyclic wrap-around only for a repeating horizon.

Weighted-average quality with a fixed positive total

\sum_jq_jx_j\ge q_{\min}Q,\quad \sum_jx_j=Q>0

#lp-formulation#objective-function#constraint-modelling#maximin#ratio-constraint#degeneracy#special-cases

کارت‌های مرتبط

الگوریتمتحقیق در عملیات

حمل‌ونقل، تخصیص و برنامه‌ریزی عدد صحیح

شاخهٔ «ساختار ویژه» در برنامه‌ریزی خطی: جدول حمل‌ونقل متوازن با m+n-1 خانهٔ پایه، آزمون بهینگی MODI/گام‌به‌گام و تحلیل حساسیت هزینه، مدل تخصیص و روش مجارستانی با تبهگنی ذاتی‌اش، و برنامه‌ریزی عدد صحیح/صفر و یک با قیدهای منطقی بزرگ-M، شاخه و کران و برش‌های گوموری. بالاس، شمارش ضمنی دودویی را با کاهش کمبود قیدها، کران‌های افزایشی و بازگشت به شاخه‌های قبلی می‌افزاید. مدل جهت‌دار فروشندهٔ دوره‌گرد، حذف زیرتور را به قیدهای درجهٔ تخصیص می‌افزاید. حساسیت تخصیص نمادین، خط‌های هزینهٔ کلِ مجاز و پوش پایین آن‌ها را در دامنهٔ پارامتر مقایسه می‌کند.

transportation-problemassignment-problemhungarian-methodmodi-method

الگوریتمتحقیق در عملیات

روش سیمپلکس و شیوهٔ خواندن جدول سیمپلکس

الگوریتم نقطهٔ گوشه‌ای برنامه‌ریزی خطی و — مهم‌تر از همه — شیوهٔ خواندن جدولی که تولید می‌کند: فرم استاندارد و متغیرهای کمبود/مازاد/مصنوعی، پایه و سطر z_j - c_j، قواعد ورود/خروج، علائم حالت‌های خاص، و خواندن وارونهٔ جدول که قیمت‌های سایه‌ای، هزینه‌های کاهش‌یافته، نرخ‌های جانشینی و حتی تابع هدف اولیه را بازیابی می‌کند. همچنین تبدیل با بخش منفی مشترک، بازیابی متغیرهای اولیهٔ علامت‌دار و تغییر سمت راست در عمل محوری را پوشش می‌دهد.

simplex-methodsimplex-tableauunrestricted-variablesshared-negative-part

سوالات تمرینی · 8/22

تحقیق در عملیاتمتوسطمدل‌سازی برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۵ — سؤال ۱۳۶

محصول «الف» از مونتاژ ۲ قطعه A و ۳ قطعه B ساخته می‌شود. تولید این قطعات در سه‌بخش تولیدی ۱، ۲ و ۳ کارخانه انجام می‌شود که ظرفیت تولید روزانه هر بخش به‌صورت جدول زیر است. اگر هدف حداکثر کردن تولید…

تحقیق در عملیاتسختمدل‌سازی برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۵ — سؤال ۱۳۷

یک شرکت شیشه‌بری ۳ سفارش به شرح زیر دریافت کرده است. تأمین‌کننده، شیشه‌هایی به طول ۱۵۰ سانتی‌متر در اختیار این شرکت قرار می‌دهد. قطعاتی که اندازه آن‌ها کمتر از ۴۰ سانتی‌متر باشد، ضایعات تلقی می‌شود.…

تحقیق در عملیاتمتوسطمدل‌سازی برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۵ — سؤال ۱۳۸

قطعات A و B به وسیله دو ماشین تولید می‌شود که زمان تولید هر قطعه با هر یک از ماشین‌ها (دقیقه) به‌صورت جدول زیر است. مدیر تولید تمایل دارد کار روی ماشین‌ها به‌نحوی تقسیم شود که هیچ‌کدام از ماشین‌ها یک…

تحقیق در عملیاتسختحل ترسیمی و حالت‌های خاص برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۵ — سؤال ۱۳۹

مسئله برنامه‌ریزی خطی زیر دارای چه حالت خاصی است؟ Max Z=Min ۳/۵x, x-۲ s.t. ۲≤ x≤ ۵

تحقیق در عملیاتسختمدل‌سازی برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۴ — سؤال ۱۳۷

در صورتی که مدل زیر، به مدل استاندارد برنامه‌ریزی خطی تبدیل شود؛ به‌ترتیب، دارای چند متغیر تصمیم و چند محدودیت خواهد بود؟ max Z=min(( ۳x_۱+x_۲ )/۴,( x_۱+۵x_۲…

تحقیق در عملیاتمتوسطحل ترسیمی و حالت‌های خاص برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۴ — سؤال ۱۳۸

مسئله برنامه‌ریزی خطی زیر، به‌ازای چه مقادیری از a ، دارای جواب بهینه چندگانه است؟ max Z, =x_۱+x_۲; s.t. x_۱+x_۲, ≤۶; ۲x_۱-ax_۲, ≤۰; x_۲, ≤۲; x_۱,x_۲, ≥۰

تحقیق در عملیاتمتوسطمدل‌سازی برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۴ — سؤال ۱۳۹

تعداد نیروی انسانی موردنیاز یک مرکز ارتباط با مشتری در ساعت i ام روز برابر b_i است. هر نیرو ۴ ساعت متوالی کار می‌کند که هزینه به‌کارگیری هر نفر برای هر ساعت ۵ است و در صورتی که تعداد نیروی…

تحقیق در عملیاتمتوسطمدل‌سازی برنامه‌ریزی خطیکنکور ارشد مدیریت ۱۴۰۳ — سؤال ۱۳۶

در یک مسئله انتخاب تأمین‌کننده (فروشنده) و تخصیص سفارش، اگر x_j بیانگر میزان خرید یک نوع کالا از تأمین‌کننده j ام باشد. فرض کنید به‌ترتیب، کیفیت کالای تأمین‌کنندگان ۱، ۲ و ۳ دارای عدد کیفیت ۹۷، ۹۶ و…

همهٔ 22 سؤال →