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

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

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

کارت الگوریتم کنکور ارشد مدیریت

اهمیت

۰/۵

۱. تعریف — Definition

مدل حمل‌ونقل (مسئلهٔ حمل‌ونقل / transportation problem)، مدل تخصیص (مسئلهٔ تخصیص / assignment problem) و برنامه‌ریزی عدد صحیح (برنامه‌ریزی عدد صحیح / integer programming) سه شاخهٔ «ساختار ویژه» در برنامه‌ریزی خطی‌اند که کنکور آن‌ها را در قالب الگوریتم می‌سنجد، نه در قالب مدل‌سازی. دو مورد نخست، مسائل برنامه‌ریزی خطی‌ای هستند که ماتریس ضرایب قیدشان چنان ویژه است که می‌توان روش سیمپلکس را با یک جدول فشرده از سطرها و ستون‌ها جایگزین کرد — و جواب پایهٔ بهینه‌شان با عرضه و تقاضای صحیح به‌طور خودکار عدد صحیح درمی‌آید، حتی وقتی هیچ شرط صحیح‌بودنی تحمیل نشده باشد. مورد سوم دقیقاً حالت مقابل است: یک برنامهٔ خطی معمولی که شرط $x_j \in \mathbb{Z}$ (یا $x_j \in \{0,1\}$ ) به آن افزوده می‌شود، و همین تضمین نقطهٔ رأسی را از بین می‌برد و در نتیجه به ابزار مخصوص خود نیاز دارد — شاخه و کران (branch and bound) یا صفحات برش (cutting planes). تشخیص اینکه در کدام‌یک از این سه هستید، کل روش را تعیین می‌کند: در دو مورد نخست هرگز چیزی را گرد نمی‌کنید، و در مورد سوم هم حق گرد کردن ندارید — باید برش بزنید یا شاخه‌بندی کنید.

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

بخش	صاحب نظریه	مسئله‌ای که برای آن ابداع شد
مسئلهٔ حمل‌ونقل	صورت‌بندی‌شده به دست F. L. Hitchcock (1941) و مطالعه‌شده به‌طور مستقل توسط T. C. Koopmans؛ قابل حل با سیمپلکس دانتزیگ (Dantzig)	ارسال یک کالای همگن از $m$ مبدأ عرضه به $n$ مقصد تقاضا با کمترین هزینهٔ کل
سیمپلکس حمل‌ونقل — شمال‌غربی / کمترین هزینه / VAM برای شروع، گام‌به‌گام (stepping-stone) و MODI برای آزمون	قراردادهای محاسباتی جدول حمل‌ونقل	پرهیز از حمل جدول سیمپلکسِ $mn$ ستونی به‌صورت دستی
روش مجارستانی (Hungarian method)	H. W. Kuhn (1955)، که «مجارستانی» نامیده شد چون بر قضایای تطابق Kőnig و Egerváry استوار است	تطابق یک‌به‌یک $n$ عامل با $n$ کار
صفحات برش (برش گوموری)	R. E. Gomory (1958)	نخستین الگوریتم متناهی برای برنامهٔ خطی عدد صحیح خالص
شاخه و کران (branch and bound)	A. H. Land and A. G. Doig (1960)	شمارش ضمنی جواب‌های صحیح با استفاده از کران‌های برنامهٔ خطی

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

۳. ساختار — The models themselves

۳.۱ مدل حمل‌ونقل

\min Z = \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}\,x_{ij}

\text{s.t.}\quad \sum_{j=1}^{n} x_{ij} = a_i \;\;(i=1,\dots,m),\qquad \sum_{i=1}^{m} x_{ij} = b_j \;\;(j=1,\dots,n),\qquad x_{ij}\ge 0

که در آن $a_i$ عرضهٔ (supply) مبدأ $i$ ، $b_j$ تقاضای (demand) مقصد $j$ و $c_{ij}$ هزینهٔ حمل هر واحد است. مدل وقتی متوازن (balanced) است که

\sum_{i=1}^{m} a_i = \sum_{j=1}^{n} b_j

واقعیت ساختاری	مقدار	چرا مهم است
تعداد متغیرها	$mn$	جدول $m$ سطر $\times$ $n$ ستون است
تعداد قیدها	$m+n$	یکی برای هر سطر، یکی برای هر ستون
رتبهٔ ماتریس ضرایب	$m+n-1$	یک معادله زائد است (مجموع سطرها و مجموع ستون‌ها هر دو یک عدد کل را می‌دهند)
خانه‌های پُر (پایه) در یک جواب شدنی پایه	$m+n-1$	تخصیص‌های مثبتِ کمتر از این $\Rightarrow$ تبهگن (degenerate)
مدل نامتوازن	افزودن یک سطر یا ستون مجازی (dummy) با $c=0$	عرضهٔ مازاد یا تقاضای برآورده‌نشده را جذب می‌کند
مسیر ممنوع (prohibited route)	قرار دادن $c_{ij}=M$ (عددی بسیار بزرگ)	الگوریتم خودبه‌خود از آن خانه پرهیز می‌کند
تابع هدف بیشینه‌سازی	تبدیل به هزینه با استفاده از $\max c_{ij} - c_{ij}$ (یا منفی کردن)	آزمون‌های زیر برای کمینه‌سازی بیان شده‌اند
صحیح‌بودن	رایگان، هرگاه همهٔ $a_i,b_j$ صحیح باشند	ماتریس ضرایب تماماً یکه‌پیمان (totally unimodular) است

۳.۲ مدل تخصیص — حالت خاصِ حدی

قرار دهید $m=n$ و $a_i=b_j=1$ برای همهٔ $i,j$ :

\min Z=\sum_{i=1}^{n}\sum_{j=1}^{n} c_{ij}x_{ij},\qquad \sum_{j} x_{ij}=1,\quad \sum_{i} x_{ij}=1,\quad x_{ij}\in\{0,1\}

دقیقاً $n$ متغیر برابر $1$ می‌شوند — یکی در هر سطر و یکی در هر ستون — هر شکلی که ماتریس هزینه داشته باشد. همین یک واقعیت، کل حسابِ تبهگنی را می‌سازد:

حل‌شده به‌صورت…	اندازهٔ پایه	متغیرهای مثبت	متغیرهای تبهگن
جدول کاملِ $2n$ سطری با مصنوعی صفر برای معادلهٔ زائد	یک جایگاه پایه به ازای هر سطر $=2n$	$n$	$2n-n=n$
یک مسئلهٔ حمل‌ونقل	$m+n-1=2n-1$ خانهٔ پُر	$n$	$(2n-1)-n=n-1$

با حذف سطر زائد و متغیرهای مصنوعی، پایهٔ برنامهٔ خطی معمولی نیز رتبهٔ $2n-1$ و در نتیجه $n-1$ متغیر اصلی پایهٔ صفر دارد. شمار $n$ ، مصنوعی صفرِ باقی‌مانده را شامل می‌شود؛ رتبهٔ دیگری برای همان ماتریس نیست.

مسئلهٔ تخصیص از نظر ساختاری تبهگن است: برای هر $n\ge 2$ ، هر جواب شدنی پایهٔ آن تبهگن است و باید به تعداد لازم خانهٔ پایهٔ صفرِ مستقل را، بدون بستن حلقه، با یک $\varepsilon$ نمادین (صفر مجازی) مشخص کرد تا پایه کامل و دستگاه ضرایب (multiplier) قابل حل بماند.

۳.۲الف مدل جهت‌دار فروشندهٔ دوره‌گرد: تخصیص به‌علاوهٔ اتصال

مسئلهٔ فروشندهٔ دوره‌گرد (travelling-salesperson problem, TSP) توری بسته با کمترین هزینه می‌خواهد که هر شهر را یک بار بازدید کند. در مدل جهت‌دار، $V=\{1,\ldots,n\}$ و $x_{ij}=1$ به معنای انتخاب کمان از مبدأ $i$ به مقصد $j$ است؛ هزینهٔ دو جهت مخالف ممکن است متفاوت باشد. متغیرها را فقط برای $i\ne j$ تعریف کنید (یا معادل آن، $x_{ii}=0$ بگذارید).

\min Z=\sum_{i=1}^{n}\sum_{j\ne i}c_{ij}x_{ij},\qquad x_{ij}\in\{0,1\}

\sum_{j\ne i}x_{ij}=1\quad(i\in V),\qquad \sum_{i\ne j}x_{ij}=1\quad(j\in V)

جمع اول مبدأ را ثابت نگه می‌دارد و یک خروج (one departure) را انتخاب می‌کند؛ جمع دوم مقصد را ثابت نگه می‌دارد و یک ورود (one arrival) را انتخاب می‌کند. این قیدهای درجهٔ تخصیص، پوشش دوری (cycle cover) می‌سازند که ممکن است چند دور جدا داشته باشد. صحیح‌بودن، آن پوشش را متصل نمی‌کند.

در هر زیرمجموعهٔ سرهٔ شهرها، تشکیل یک زیرتور (subtour) بسته را ممنوع کنید:

\sum_{i\in S}\sum_{\substack{j\in S\\j\ne i}}x_{ij}\le\lvert S\rvert-1, \qquad S\subset V,\quad 2\le\lvert S\rvert\le n-1

مثال نقض: $1\to2\to1$ و $3\to4\to3$ همهٔ معادلات خروج و ورود را ارضا می‌کنند و کمان به خود ندارند، اما هر چهار شهر را در یک تور نمی‌پیمایند. برای $S=\{1,2\}$ جمع کمان‌های داخلی $2>1$ است؛ پس قید زیرمجموعه این جواب را حذف می‌کند. در مقابل، $1\to2\to3\to4\to1$ یک تور شدنی است؛ شدنی‌بودن به‌تنهایی کمترین هزینه را اثبات نمی‌کند.

مدل	تضمین معادلات درجه	الزام اضافی / روش
تخصیص (Assignment)	یک خانهٔ منتخب در هر سطر و ستون	روش مجارستانی کمترین هزینهٔ تطابق را گواهی می‌کند.
فروشندهٔ دوره‌گرد جهت‌دار (Directed TSP)	یک خروج و ورود برای هر شهر؛ احتمال چند دور	حذف زیرتور، تور واحد را تحمیل می‌کند؛ عموماً به بهینه‌سازی عدد صحیح نیاز است.

کاربرد: مسئلهٔ تخصیصِ آزادشده را حل کنید، دورها را بررسی و قید زیرمجموعهٔ نقض‌شده را اضافه کنید؛ دوباره بهینه کنید تا زیرتوری باقی نماند. کمترین هزینهٔ آن کران پایینِ بهینهٔ تور است. کاهش‌های مجارستانی تنها وقتی بهینگی TSP را گواهی می‌کنند که تخصیص بهینهٔ آنها از ابتدا یک تور مجاز واحد باشد.

تلهٔ رایج: خروج، مقصدها را جمع می‌زند؛ ورود، مبدأها را. یک کمان ورودی و یک کمان خروجی، تور واحد را تضمین نمی‌کنند.

۳.۳ برنامه‌ریزی عدد صحیح و صفر و یک

نوع	فارسی	شرط
عدد صحیح خالص (pure integer)	برنامه‌ریزی عدد صحیح خالص	همهٔ $x_j$ ها صحیح
عدد صحیح مختلط (mixed integer)	عدد صحیح مختلط	برخی $x_j$ ها صحیح، بقیه پیوسته
صفر و یک (binary / zero-one)	صفر و یک	$x_j\in\{0,1\}$ ، یعنی انتخاب / عدم انتخاب

قیدهای منطقی استاندارد با $x_j\in\{0,1\}$ ( $x_j=1$ یعنی «پروژهٔ $j$ انتخاب می‌شود»):

خواسته به زبان ساده	قید
حداکثر یکی از A و B (متقابلاً منحصربه‌فرد)	$x_A + x_B \le 1$
دقیقاً $k$ تا از $n$ پروژه	$\sum_j x_j = k$
دست‌کم $k$ انتخاب و حداکثر $n-k$ عدم انتخاب	$\sum_j x_j\ge k$ ، معادل $\sum_j(1-x_j)\le n-k$
حداکثر $k$ انتخاب	$\sum_j x_j\le k$
A مستلزم B است (وابستگی)	$x_A - x_B \le 0$
A و B هر دو یا هیچ‌کدام	$x_A - x_B = 0$
اگر C انتخاب شود، نه A و نه B نباید انتخاب شوند	$x_A + x_B + 2x_C \le 2$
یا قید ۱ یا قید ۲ باید برقرار باشد	$f_1(x)\le b_1 + My,\;\; f_2(x)\le b_2 + M(1-y)$
هزینهٔ ثابت (fixed charge): پرداخت هزینهٔ راه‌اندازی فقط اگر $x>0$	$x \le M y$ ، با $y$ صفر و یک

ابزار عمومیِ «اگر–آنگاه» همان کلید بزرگ- $M$ است: هر چه را که باید خاموش شود در سمت چپ بگذارید و بگذارید متغیر کلیدی یک $M$ دست‌کم به بزرگی بیشینهٔ سمت چپ را حمل کند:

f(x) \le M\,(1-y) \quad\Longleftrightarrow\quad f(x) + M y \le M

با فعال‌شدن کلید، $f(x)\le0$ تحمیل می‌شود؛ فقط با $f(x)\ge0$ ، صفرشدن نتیجه می‌شود. برای $f(x)=x_A+x_B$ صفر و یک، بیشینه برابر $2$ است، پس $M=2$ تنگ‌ترین ضریب مجاز است.

۴. طرز کار — How to apply

روش حمل‌ونقل — حل یک مسئلهٔ حمل‌ونقل

متوازن کنید (در صورت نیاز سطر/ستون مجازی)؛ بیشینه‌سازی را به ماتریس هزینه تبدیل کنید.
جواب شدنی پایهٔ اولیه — یکی از این‌ها:

روش	فارسی	ایده	کیفیت
North-west corner	گوشهٔ شمال غربی	از بالا-چپ شروع کن، هزینه‌ها را نادیده بگیر	سریع؛ بی‌توجه به هزینه، نه لزوماً بدترین
Least cost	کمترین هزینه	ارزان‌ترین خانهٔ موجود را پُر کن	ابتکاری؛ بدون تضمین بهینگی
VAM (Vogel)	تقریب ووگل	جریمهٔ هر سطر/ستون = (دومین ارزان‌ترین − ارزان‌ترین)؛ بزرگ‌ترین جریمه ابتدا خدمت می‌گیرد	اغلب شروع مفید؛ بدون تضمین بهینگی

شمارش را بررسی کنید: باید $m+n-1$ خانهٔ پُر باشد؛ اگر کمتر بود، یک $\varepsilon$ در خانه‌ای بگذارید که حلقه‌ای را نبندد. 3. آزمون بهینگی. یا روش گام‌به‌گام (روش گام به گام / مسیر بسته / stepping-stone) — برای هر خانهٔ خالی، حلقهٔ بستهٔ یکتای آن را از میان خانه‌های پُر ردیابی کنید و هزینه‌ها را با علامت‌های متناوب $+,-$ جمع کنید — یا MODI (روش توزیع اصلاح‌شده) که سریع‌تر است: قرار دهید $u_1=0$ و حل کنید

u_i + v_j = c_{ij}\quad \text{for every occupied cell}

سپس برای هر خانهٔ خالی محاسبه کنید

d_{ij} = c_{ij} - u_i - v_j

جدول (در کمینه‌سازی) وقتی بهینه است که $d_{ij}\ge 0$ برای همهٔ خانه‌های خالی برقرار باشد. مقدار $d_{ij}=0$ روی یک خانهٔ خالی نامزد جواب‌های بهینهٔ چندگانه (alternative optima) است؛ تخصیص شدنی متمایز را تأیید کنید، زیرا لولای تبهگن با حرکت صفر ممکن است فقط پایه را تغییر دهد. 4. بهبود دهید. منفی‌ترین $d_{ij}$ را وارد پایه کنید: روی حلقهٔ بستهٔ آن، $\theta = \min$ تخصیص‌های خانه‌های منفی را بگیرید، $\theta$ را به خانه‌های مثبت اضافه و از خانه‌های منفی کم کنید. از گام ۳ تکرار کنید.

قید دوگان $u_i+v_j\le c_{ij}$ است؛ پس کمکی نامنفی آن $L_{ij}=d_{ij}=c_{ij}-u_i-v_j$ است. مسیرهای پایه طبق مکملی، کمکی دوگان صفر دارند.

حساسیت — تحلیل دامنهٔ هزینه در جدول نهایی

این همان گامی است که دانشجویان بیش از همه برعکس انجام می‌دهند. قاعده کاملاً به این بستگی دارد که خانه خالی است یا پُر:

خانه	با تغییر هزینه‌اش چه چیزی تغییر می‌کند	دامنهٔ مجاز
خانهٔ خالی (غیرپایه) $(i,j)$	فقط $d_{ij}$ خودش	می‌تواند بدون حد بالا افزایش یابد و حداکثر به اندازهٔ $d_{ij}$ کاهش یابد: $\;c_{ij}-d_{ij}\le c_{ij}^{\text{new}}<\infty$
خانهٔ پُر (پایه) $(i,j)$	وارد دستگاه $u_i+v_j$ می‌شود، پس ضرایب را جابه‌جا می‌کند و در نتیجه چند $d$ را تغییر می‌دهد	هزینه را به‌صورت نماد $t$ حمل کنید، همهٔ $u_i,v_j$ را دوباره محاسبه کنید، شرط $d_{kl}=c_{kl}-u_k-v_l\ge 0$ را بر هر خانهٔ خالی تحمیل کنید و نامعادلات حاصل را اشتراک بگیرید

جهت‌ها خودکار به دست می‌آیند: خانهٔ خالی‌ای که حلقه‌اش با علامت منفی وارد خانهٔ تغییریافته می‌شود، $d=K-t\ge 0$ می‌دهد، یعنی یک کران بالا برای $t$ ؛ و حلقه‌ای که با علامت مثبت وارد شود، کران پایین می‌دهد. اگر یک حلقه را جا بیندازید، بازه بیش از حد گشاد درمی‌آید.

روش مجارستانی — the Hungarian method (مربعی، کمینه‌سازی)

کاهش سطری: کوچک‌ترین عنصر هر سطر را از آن سطر کم کنید.
کاهش ستونی: کوچک‌ترین عنصر هر ستون را از آن ستون کم کنید.
همهٔ صفرها را بپوشانید با کمترین تعداد ممکن خطوط افقی/عمودی.
اگر تعداد خطوط $=n$ شد، یک تخصیص بهینه در میان صفرها وجود دارد — آن را بخوانید و از سطر یا ستونی شروع کنید که دقیقاً یک صفر دارد. اگر تعداد خطوط $<n$ بود: کوچک‌ترین عنصر پوشیده‌نشده را بگیرید، آن را از هر عنصر پوشیده‌نشده کم کنید، به هر عنصری که در تقاطع دو خط است اضافه کنید، عناصر تک‌پوشش را دست‌نخورده بگذارید و به گام ۳ بازگردید.
نکات تکمیلی: ماتریس غیرمربعی یک سطر/ستون مجازی از صفرها می‌گیرد؛ مسئلهٔ بیشینه‌سازی ابتدا به ماتریس ندامت/هزینهٔ فرصت‌ازدست‌رفته ( $\max c - c_{ij}$ ) تبدیل می‌شود؛ و تخصیص ممنوع هزینهٔ $M$ می‌گیرد.

هزینه‌های نمادین تخصیص — حساسیت نسبت به پارامتر

ابتدا زوج‌های ممنوع را حذف کنید؛ این زوج‌ها مجاز نیستند، نه اینکه هزینهٔ محدود و بزرگی برای مبادله داشته باشند. نماد $M$ در بخش‌های دیگر، جریمه‌ای واقعاً بازدارنده در دامنهٔ داده‌شده را فرض می‌کند. اگر هیچ تخصیص کاملی باقی نماند، مدل ناموجه است. برای ماتریسی کوچک، جایگشت‌های مجاز $\pi$ را شمارش و هزینهٔ کل آفین هر یک را جمع کنید:

C_\pi(a)=\sum_i c_{i,\pi(i)}(a)=\alpha_\pi a+\beta_\pi,\qquad C^*(a)=\min_{\pi\ \mathrm{allowed}}C_\pi(a).

تقاطع‌های دوبه‌دو را بیابید، موارد داخل دامنهٔ داده‌شدهٔ پارامتر را نگه دارید و هزینه‌ها را در هر بازهٔ میان آن‌ها مقایسه کنید: مقدار بهینه، پوش پایین (lower envelope) آن‌هاست.

مثال کوچک: فرض کنید $a>0$ . ماتریسی $2\times2$ سطرهای $(a+3,a+1)$ و $(a+1,3)$ را دارد؛ هزینهٔ تخصیص قطری (A) و جابه‌جا (B) را جمع کنید:

تخصیص	هزینهٔ کل آفین	دامنهٔ بهینگی
A	$a+6$	$a\ge4$
B	$2a+2$	$0<a\le4$

حل $a+6=2a+2$ مقدار $a=4$ را می‌دهد؛ در $a=1$ ، هزینهٔ B برابر $4<7$ است؛ در $a=5$ ، هزینهٔ A برابر $11<12$ است. در نقطهٔ تغییر هر دو برابرند. عبارتی پیشنهادی ممکن است فقط در زیردامنه‌ای معتبر باشد؛ مثبت‌بودن به‌تنهایی یک خط را انتخاب نمی‌کند. تقاطع دو خط، اگر خط سومی زیر هر دو باشد، در پوش بهینه نقشی ندارد.

عدد صحیح — حل یک برنامهٔ عدد صحیح

نخست مسئلهٔ آزادشده (LP relaxation) را حل کنید. مقدار تابع هدف آن یک کران است: کران بالا برای مسئلهٔ بیشینه‌سازی و کران پایین برای کمینه‌سازی. اگر اتفاقاً صحیح درآمد، کار تمام است.
هرگز گرد نکنید. گرد کردن ممکن است ناشدنی شود، و حتی وقتی شدنی باشد غالباً بهینه نیست.
شاخه و کران: یک $x_j = \beta$ کسری را انتخاب کنید و دو زیرمسئله با $x_j \le \lfloor \beta \rfloor$ و $x_j \ge \lfloor \beta \rfloor + 1$ بسازید؛ گرهی را هرس کنید که مسئلهٔ آزادشده‌اش ناشدنی، صحیح، یا بدتر از بهترین جواب صحیح یافت‌شده تا آن لحظه (incumbent) باشد.
صفحهٔ برش گوموری: سطری با متغیرهای صحیح خالص از جدول بهینه را بگیرید که سمت راستش کسری است، هر ضریب و سمت راست را به‌صورت $a = \lfloor a \rfloor + f$ بنویسید که در آن بخش کسری $f = a - \lfloor a \rfloor \in [0,1)$ است، و این قید را اضافه کنید

\sum_{j \in \text{non-basic}} f_j\,x_j \;\ge\; f_0

یک برش معتبر باید (i) نقطهٔ کسری فعلیِ برنامهٔ خطی را حذف کند و (ii) هر نقطهٔ شدنی صحیح را حفظ کند. 5. بازگرداندن برش به متغیرهای اصلی — گامی محبوب در کنکور. برش در فضای جدول متولد می‌شود، پس به زبان متغیرهای کمکی سخن می‌گوید؛ هر متغیر کمکی را از قید خودش بخوانید،

s_i = b_i - \sum_{j} a_{ij}x_j

و جایگذاری و ضرایب را جمع کنید. در مثال زیر با ضرایب نامنفی، علامت $\ge$ برش به $\le$ تبدیل می‌شود؛ با ضرایب اصلی منفی، سطر حاصل را بررسی کنید و کاهش هر کمکی در هر متغیر را مفروض نگیرید.

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

بالاس — جست‌وجوی افزایشی دودویی بدون برنامهٔ خطی در هر گره

الگوریتم افزایشی بالاس (Balas's additive algorithm) انتخاب‌های دودویی را به‌طور ضمنی می‌شمارد. به کمینه‌سازی با هزینه‌های نامنفی نرمال کنید: متغیر با هزینهٔ منفی را با $x_j=1-y_j$ مکمل کنید و همهٔ قیدها و ثابت تابع هدف را تغییر دهید. سطرها را سازگار به شکل $Ay\ge b$ بنویسید. در هر گره، متغیرهای انتخاب‌شده را تثبیت و ابتدا متغیرهای آزاد را صفر کنید: این ارزان‌ترین تکمیل است، نه لزوماً تکمیل موجه.

۱. کمبود مثبت هر قید و مجموع آن را محاسبه کنید:

d_i=\max\{0,b_i-(Ay)_i\},\qquad I(y)=\sum_i d_i

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

j^*=\arg\max_{j\in F}\{I(y)-I(y+e_j)\}

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

آزمون کوچک: برای $2y_1+y_2\ge2$ و $y_1+2y_3\ge2$ ، بردار صفر $I=2+2=4$ می‌دهد. یک‌کردن تنها متغیر اول، دوم یا سوم به‌ترتیب مجموع‌های $1,3,2$ می‌دهد؛ پس قاعده ابتدا متغیر اول را می‌آزماید. هنوز برای موجه‌شدن متغیر دیگری لازم است؛ انتخاب اولین انشعاب گواه بهینگی نیست.

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

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

(الف) یک جدول حمل‌ونقل، حل‌شده و سپس تحلیل حساسیت‌شده

عرضه‌ها $a=(30,\,20)$ ، تقاضاها $b=(25,\,15,\,10)$ — متوازن در $50$ — با ماتریس هزینهٔ

	D1	D2	D3
S1	4	6	8
S2	5	3	7

شروع با کمترین هزینه: ارزان‌ترین خانه $(2,2)$ با $3$ است، مقدار $\min(20,15)=15$ تخصیص می‌دهیم؛ سپس $(1,1)$ با $4$ ، مقدار $\min(30,25)=25$ ؛ سپس $(2,3)$ با $7$ ، مقدار $5$ ؛ و در پایان $(1,3)=5$ . خانه‌های پُر $=4=m+n-1=2+3-1$ ، پس جواب غیرتبهگن است.

Z = 25(4) + 5(8) + 15(3) + 5(7) = 100+40+45+35 = 220

آزمون MODI با $u_1=0$ :

\begin{aligned} (1,1):\; u_1+v_1=4 &\Rightarrow v_1=4\\ (1,3):\; u_1+v_3=8 &\Rightarrow v_3=8\\ (2,3):\; u_2+v_3=7 &\Rightarrow u_2=-1\\ (2,2):\; u_2+v_2=3 &\Rightarrow v_2=4 \end{aligned}

خانه‌های خالی: $d_{12}=6-0-4=2\ge 0$ و $d_{21}=5-(-1)-4=2\ge 0$ ، پس جدول بهینه است.

تحلیل حساسیت خانهٔ خالی $(1,2)$ : فقط $d_{12}$ تغییر می‌کند، پس $c_{12}$ حداکثر به اندازهٔ $2$ می‌تواند کاهش یابد و بدون محدودیت می‌تواند افزایش یابد:

4 \le c_{12} < \infty

تحلیل حساسیت خانهٔ پُر $(2,3)$ : $c_{23}=7$ را با نماد $t$ جایگزین کنید و ضرایب را دوباره حساب کنید: $v_1=4$ ، $v_3=8$ ، $u_2=t-8$ ، $v_2=3-u_2=11-t$ . اکنون شرط نامنفی بودن را بر هر دو خانهٔ خالی تحمیل کنید:

d_{12}=6-0-(11-t)=t-5\ \ge 0 \;\Rightarrow\; t\ge 5, \qquad d_{21}=5-(t-8)-4=9-t\ \ge 0 \;\Rightarrow\; t\le 9

\boxed{\;5 \le c_{23} \le 9\;}

توجه کنید چگونه یک هزینهٔ پایه، دو ضریب را جابه‌جا کرد و دو کران تولید کرد — تمام تفاوت میان دو سطر جدول حساسیت بالا همین است.

(ب) یک تخصیص $3\times 3$ با روش مجارستانی

	J1	J2	J3
A1	9	11	14
A2	6	15	13
A3	12	13	16

کاهش سطری (کم کردن $9,6,12$ ) و سپس کاهش ستونی (کم کردن $0,1,4$ ) می‌دهد

\begin{bmatrix} 0 & 1 & 1\\ 0 & 8 & 3\\ 0 & 0 & 0 \end{bmatrix}

همهٔ صفرها با ستون ۱ به‌علاوهٔ سطر ۳ پوشیده می‌شوند — تنها $2$ خط که $<3$ است، پس ماتریس هنوز قابل حل نیست. کوچک‌ترین عنصر پوشیده‌نشده $1$ است: آن را از هر عنصر پوشیده‌نشده کم کنید و به عنصر دوبار پوشیده‌شدهٔ $(3,1)$ اضافه کنید:

\begin{bmatrix} 0 & 0 & 0\\ 0 & 7 & 2\\ 1 & 0 & 0 \end{bmatrix}

اکنون صفرها به $3$ خط نیاز دارند (سطر ۱، سطر ۳، ستون ۱)، پس تخصیص بهینه وجود دارد. سطر ۲ تنها یک صفر دارد، پس $A2\to J1$ ؛ سپس $A1$ و $A3$ ، کارهای $J2$ و $J3$ را میان خود تقسیم می‌کنند:

Z = 6 + 11 + 16 = 33 \qquad\text{or}\qquad Z = 6 + 14 + 13 = 33

دو تخصیص متفاوت با هزینهٔ یکسان — جواب‌های بهینهٔ چندگانه، که به دو تطابق کاملِ متمایز روی صفرهای ماتریس کاهش‌یافته نیاز دارند؛ صفرهای اضافی به‌تنهایی کافی نیستند.

(ج) بازگرداندن یک برش گوموری به متغیرهای اصلی

فرض کنید قیدهای اصلی $2x_1+5x_2\le 15$ و $x_1+x_2\le 4$ باشند، پس $s_1 = 15-2x_1-5x_2$ و $s_2 = 4-x_1-x_2$ . برای بیشینه‌سازی $x_1+2x_2$ ، بهینهٔ برنامهٔ خطی $(x_1,x_2)=(5/3,7/3)$ است؛ حذف متغیر اول این سطر را می‌دهد

x_2 + \tfrac{1}{3}s_1 - \tfrac{2}{3}s_2 = \tfrac{7}{3}

بخش‌های کسری — همیشه رو به پایین گرفته می‌شوند، پس $\lfloor -\tfrac{2}{3}\rfloor=-1$ است، نه $0$ :

f_{s_1}=\tfrac{1}{3},\qquad f_{s_2}=-\tfrac{2}{3}-(-1)=\tfrac{1}{3},\qquad f_0=\tfrac{7}{3}-2=\tfrac{1}{3}

\text{cut:}\quad \tfrac{1}{3}s_1+\tfrac{1}{3}s_2 \ \ge\ \tfrac{1}{3} \;\xrightarrow{\;\times 3\;}\; s_1+s_2\ \ge\ 1

با جایگذاری متغیرهای کمکی:

(15-2x_1-5x_2)+(4-x_1-x_2) \ge 1 \;\Longrightarrow\; 19-3x_1-6x_2 \ge 1 \;\Longrightarrow\; 3x_1+6x_2 \le 18

در این مثال، پس از جمع‌کردن جمله‌ها علامت $\ge$ به $\le$ تبدیل شد.

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

زوج مفاهیم	تفاوت واقعی	نشانهٔ تشخیص
حمل‌ونقل در برابر تخصیص	تخصیص همان مسئلهٔ حمل‌ونقل است با $m=n$ و همهٔ عرضه‌ها و تقاضاها برابر $1$	در تخصیص هر مبدأ دقیقاً به یک مقصد خدمت می‌دهد؛ در حمل‌ونقل یک مبدأ می‌تواند عرضه‌اش را تقسیم کند
تخصیص در برابر ترابری/انتقالی (transshipment)	در ترابری گره‌های میانی مجازند که هم دریافت و هم ارسال کنند	گره‌ای که هم به‌صورت سطر و هم به‌صورت ستون ظاهر می‌شود
گام‌به‌گام در برابر MODI	آزمون بهینگی یکسان، دفترداری متفاوت: گام‌به‌گام برای هر خانهٔ خالی یک حلقهٔ بسته ردیابی می‌کند؛ MODI یک‌بار $u_i,v_j$ را به دست می‌آورد و همهٔ خانه‌ها را قیمت‌گذاری می‌کند	MODI سریع‌تر است؛ اما گام‌به‌گام هنوز برای محاسبهٔ $\theta$ هنگام تخصیص مجدد لازم است
تحلیل حساسیت خانهٔ خالی در برابر خانهٔ پُر	خالی: یک $d_{ij}$ تغییر می‌کند $\Rightarrow$ دامنهٔ یک‌طرفه و بی‌کران از بالا. پُر: ضرایب تغییر می‌کنند $\Rightarrow$ دامنهٔ دوطرفه از همهٔ خانه‌های خالی	اگر خانه تخصیص دارد، باید دستگاه $u+v$ را به‌صورت نمادین حل کنید
$m+n-1$ در برابر شمار تبهگنی	$m+n-1$ اندازهٔ پایه است، نه شمارش متغیرهای تبهگن	تبهگن $=$ اندازهٔ پایه $-$ تخصیص‌های مثبت ( $n$ در هر مسئلهٔ تخصیص)
تبهگنی در برابر جواب‌های بهینهٔ چندگانه	تبهگنی $=$ یک متغیر پایه برابر صفر است؛ جواب‌های بهینهٔ چندگانه به تخصیص متمایز با هزینهٔ یکسان نیاز دارد؛ خانهٔ غیرپایه با $d_{ij}=0$ نامزد آن است	برای اولی خانه‌های پُر را بشمارید، برای دومی $d_{ij}$ ها را وارسی کنید
شاخه و کران در برابر صفحات برش	شاخه و کران ناحیهٔ شدنی را به زیرمسئله‌ها افراز می‌کند؛ برش، مسئلهٔ آزادشده را بدون تقسیم آن کوچک می‌کند	شاخه و کران درخت تولید می‌کند، گوموری در هر مرحله یک قید اضافه می‌سازد
گرد کردن جواب برنامهٔ خطی در برابر یک روش واقعی عدد صحیح	گرد کردن هیچ تضمین بهینگی ندارد و حتی ممکن است ناشدنی شود	فقط در حمل‌ونقل/تخصیص است که جواب برنامهٔ خطی رایگان صحیح درمی‌آید
سه گونهٔ بزرگ- $M$	(i) $M$ در سیمپلکس بزرگ- $M$ متغیرهای مصنوعی را جریمه می‌کند؛ (ii) $M$ در مسیر ممنوع یک هزینهٔ ساختگی بسیار بزرگ است؛ (iii) $M$ در قید منطقی یک کلید است و باید تا حد ممکن کوچک باشد	در (iii) اگر $M$ خیلی کوچک باشد منطق می‌شکند و اگر $M$ خیلی بزرگ باشد مسئلهٔ آزادشده ضعیف می‌شود
متوازن در برابر نامتوازن	نامتوازن یعنی $\sum a_i \ne \sum b_j$	راه‌حل، سطر/ستون مجازی با هزینهٔ صفر است — نه حذف کردن عرضه

نکتهٔ کنکوری: سه عدد، بیشتر پرسش‌های این خانواده را تعیین می‌کنند. $m+n-1$ یک اندازهٔ پایه است (خانه‌های پُر) و هرگز شمار تبهگنی نیست — برای آن باید تخصیص‌های مثبت را کم کنید، که در یک تخصیص $n\times n$ از مسیر جدول کامل با مصنوعی صفر $2n-n=n$ متغیر تبهگن و از مسیر حمل‌ونقل $(2n-1)-n=n-1$ می‌دهد. $d_{ij}=c_{ij}-u_i-v_j\ge 0$ تنها آزمونی است که پشت هر پرسش بهینگی و هر پرسش تحلیل حساسیت هزینه ایستاده است — و وقتی خانهٔ مورد بررسی پُر است، باید هزینه‌اش را به‌صورت مجهول در $u_i+v_j=c_{ij}$ حمل کنید و شرط‌های حاصل از همهٔ خانه‌های خالی را اشتراک بگیرید. و در برنامه‌ریزی عدد صحیح، قیدی که شامل حاصل‌ضرب متغیرهای تصمیم باشد (مثلاً $x_3(x_1+x_2)\le 1$ ) اصلاً قید خطی نیست — پیش از هر محاسبه‌ای آن را خط بزنید.

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

Transportation model (balanced, minimization)

\min Z=\sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}\quad \text{s.t.}\quad \sum_{j} x_{ij}=a_i,\;\; \sum_{i} x_{ij}=b_j,\;\; x_{ij}\ge 0

Balance condition (شرط توازن)

\sum_{i=1}^{m} a_i=\sum_{j=1}^{n} b_j

Number of occupied (basic) cells

\text{occupied cells}=m+n-1

MODI multipliers (occupied cells)

u_i+v_j=c_{ij},\qquad u_1=0

Optimality test for empty cells (minimization)

d_{ij}=c_{ij}-u_i-v_j\ \ge\ 0

Degenerate variables in an n x n assignment

\text{LP route: } 2n-n=n,\qquad \text{transportation route: } (2n-1)-n=n-1

Big-M switch: if y=1 then f(x) is nonpositive (zero when f is nonnegative)

f(x)\le M(1-y)\quad\Longleftrightarrow\quad f(x)+My\le M,\qquad y\in\{0,1\}

Gomory fractional cut

\sum_j f_j x_j\ \ge\ f_0,\qquad f=a-\lfloor a\rfloor\in[0,1)

Slack substitution to express a cut in the original variables

s_i=b_i-\sum_{j} a_{ij}x_j

Balas total constraint deficit

I(y)=\sum_i\max\{0,b_i-(Ay)_i\}

Balas maximum-infeasibility-reduction branching heuristic

j^*=\arg\max_{j\in F}\{I(y)-I(y+e_j)\}

Directed TSP departure and arrival constraints

\sum_{j\ne i}x_{ij}=1\ (i\in V),\qquad\sum_{i\ne j}x_{ij}=1\ (j\in V),\qquad x_{ij}\in\{0,1\},\quad x_{ii}=0

Directed TSP subtour elimination

\sum_{i\in S}\sum_{\substack{j\in S\\j\ne i}}x_{ij}\le\lvert S\rvert-1,\qquad S\subset V,\quad 2\le\lvert S\rvert\le n-1

Parametric assignment lower envelope over feasible matchings

C_\pi(a)=\sum_i c_{i,\pi(i)}(a)=\alpha_\pi a+\beta_\pi,\qquad C^*(a)=\min_{\pi\ \mathrm{allowed}}C_\pi(a)

#transportation-problem#assignment-problem#hungarian-method#modi-method#integer-programming#gomory-cutting-plane#balas-algorithm

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

قضیهتحقیق در عملیات

دوگانگی و قیمت‌های سایه‌ای

هر مسئلهٔ برنامه‌ریزی خطی یک مسئلهٔ آینه‌ای دارد که متغیرهایش قیمت‌های سایه‌ای منابع مسئلهٔ اولیه‌اند: ساختن دوگان، قضایای دوگانگی ضعیف/قوی و لَختی مکمل، و خواندن مستقیم قیمت‌های سایه‌ای و هزینه‌های کاهش‌یافته از روی جدول سیمپلکس نهایی.

dualityshadow-pricereduced-costcomplementary-slackness

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

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

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

simplex-methodsimplex-tableauunrestricted-variablesshared-negative-part

مفهومتحقیق در عملیات

تحلیل حساسیت و قاعدهٔ ۱۰۰ درصد

ضرایب تابع هدف و مقادیر سمت راست یک مسئلهٔ برنامه‌ریزی خطی تا کجا می‌توانند تغییر کنند پیش از آنکه پایهٔ بهینه از بین برود: خواندن معکوس ماتریس پایه، قیمت‌های سایه‌ای و هزینه‌های کاهش‌یافته از روی جدول نهایی، دامنهٔ امکان‌پذیری و دامنهٔ بهینگی، و قاعدهٔ ۱۰۰ درصد برای تغییرات هم‌زمان. همراه با تغییر مقیاس معادل ستون و ضریب هدف، حذف محدودیت و تمایز نامزدی هزینهٔ کاهش‌یافته از محورگیری شدنی.

sensitivity-analysisshadow-pricereduced-costrhs-ranging

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

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

جدول نهایی حل مسئله حمل‌ونقل با هدف حداقل‌سازی هزینه، به صورت زیر است. دامنه مجاز تغییرات هزینه انتقال از مبدأ ۲ به مقصد ۲ ( C_22 ) کدام است؟ (عدد داخل کادر کوچک هر خانه، هزینه واحد حمل و عدد داخل…

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

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

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

در برنامه‌ریزی سه‌پروژه ۱، ۲ و ۳ قید شده است؛ اگر پروژه ۱ یا ۲ انتخاب شود، پروژه ۳ انتخاب نمی‌شود. محدودیت متناظر با این محدودیت کدام است؟ ( X_j : بیانگر انتخاب یا عدم‌انتخاب پروژه jام است.)

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

در مدل برنامه‌ریزی عدد صحیح زیر، محدودیت برش به‌صورت 4/5s_1 + 3/5s_2 ≥ 2/5 است. این محدودیت جدید به‌صورت کدام محدودیت، در صورت مسئله اصلی ظاهر خواهد شد؟ max Z, = 4x_1 + 9x_2 ; s.t. 3x_1 + 7x_2, ≤ 13…

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

در یک مسئله برنامه‌ریزی صفر و یک سرمایه‌گذاری در سه پروژه A، B و C، محدودیتی به‌صورت x_A+x_B+x_C≥ ۲ تعریف شده است. کدام جمله در مورد این محدودیت، نادرست است؟

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

در یک مدل حمل‌ونقل با m مبدأ و n مقصد، اگر متغیرهای دوگان مربوط به محدودیت‌های عرضه را با u_i و متغیرهای دوگان مربوط به محدودیت‌های تقاضا را با v_j نشان دهیم، چنانچه مسیر i به j (متغیر x_ij ) در جواب…

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

جدول زیر، هزینه تخصیص چهار نفر به دو شغل را نشان می‌دهد. در صورت حل این مسئله با روش تخصیص، مسئله دارای جواب بهینه ................ با هزینه تخصیص ................ واحد است. شغل ۱ شغل ۲…

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

مسئله برنامه‌ریزی با اعداد صحیح و تابلوی نهایی حل آن بدون قید عدد صحیح بودن را در نظر بگیرید ( x_۴ و x_۵ به‌ترتیب متغیرهای کمکی دو محدودیت هستند). در صورتی که متغیر x_۳ برای صحیح شدن انتخاب شود، کدام…

همهٔ 26 سؤال →