مسئله حمل‌ونقل؛ مدل، حل و گواه بهینگی

مسئله: از چند انبار به چند مقصد با کمترین هزینه

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

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

۱. مدل ریاضی حمل‌ونقل

اگر x_ij مقدار ارسالی از مبدأ i به مقصد j، و c_ij هزینه هر واحد روی آن مسیر باشد، مدل متوازن با عرضه s_i و تقاضای d_j چنین است:

Min C = sum_i sum_j c_ij * x_ij
subject to
    sum_j x_ij = s_i      for each origin i
    sum_i x_ij = d_j      for each destination j
    x_ij >= 0

Balanced case: sum_i s_i = sum_j d_j

در مدل متوازن، یکی از معادله‌های تساوی از بقیه وابسته است؛ زیرا مجموع کل ارسال از دید عرضه و تقاضا یکی است. این خاصیت در تعداد متغیرهای پایه اهمیت دارد. یک جواب پایه غیرتباه در شبکه‌ای با m مبدأ و n مقصد، معمولاً m+n−1 خانه مثبت دارد؛ در حالت تباه ممکن است تعداد خانه‌های مثبت کمتر باشد.

۲. مثال کامل: دو انبار و سه فروشگاه

دو انبار داریم: انبار A با عرضه ۲۰ واحد و انبار B با عرضه ۳۰ واحد. تقاضای فروشگاه‌های ۱، ۲ و ۳ به‌ترتیب ۱۰، ۲۵ و ۱۵ واحد است. جمع عرضه و تقاضا هر دو ۵۰ است. هزینه واحد ارسال به‌شکل زیر فرض می‌شود:

یک جواب اولیه: روش گوشه شمال‌غربی

ابتدا خانه A→۱ را با ۱۰ واحد پر می‌کنیم تا تقاضای فروشگاه ۱ صفر شود. ۱۰ واحد عرضه A باقی می‌ماند؛ آن را به فروشگاه ۲ می‌فرستیم. فروشگاه ۲ هنوز ۱۵ واحد نیاز دارد؛ از B به آن ۱۵ واحد می‌فرستیم. ۱۵ واحد باقیمانده B هم به فروشگاه ۳ می‌رود.

Northwest-corner feasible shipping plan
A -> (10, 10,  0)
B -> ( 0, 15, 15)
Cost = 10*4 + 10*6 + 15*3 + 15*7 = 250

این جواب مجاز است، چون عرضه‌ها و تقاضاها دقیقاً رعایت شده‌اند؛ اما لزوماً بهینه نیست. روش گوشه شمال‌غربی هزینه‌ها را هنگام تخصیص در نظر نمی‌گیرد.

یک جواب بهتر و گواه بهینگی

یک طرح پیشنهادی دیگر عبارت است از ارسال ۱۰ واحد از A به فروشگاه ۱، ۱۰ واحد از A به فروشگاه ۳، ۲۵ واحد از B به فروشگاه ۲ و ۵ واحد از B به فروشگاه ۳.

Optimal candidate
A -> (10,  0, 10)
B -> ( 0, 25,  5)
Cost = 10*4 + 10*8 + 25*3 + 5*7 = 230

این طرح ۲۰ واحد کمتر از جواب اولیه هزینه دارد. برای اثبات بهینگی، فقط نشان‌دادن ارزان‌تر بودن کافی نیست؛ باید یک گواه مستقل بسازیم. در دوگان مسئله حمل‌ونقل با قیود تساوی، متغیرهای پتانسیل u_i و v_j آزاد در علامت هستند و باید برای همه مسیرها شرط u_i+v_j≤c_ij را رعایت کنند. برای مثال حاضر انتخاب زیر معتبر است:

u_A=1, u_B=0
v_1=3, v_2=3, v_3=7
Check costs:
A1: 1+3 <= 4      A2: 1+3 <= 6      A3: 1+7 <= 8
B1: 0+3 <= 5      B2: 0+3 <= 3      B3: 0+7 <= 7
Dual value = 20*1 + 30*0 + 10*3 + 25*3 + 15*7 = 230

مقدار تابع هدف دوگان و هزینه طرح پیشنهادی هر دو ۲۳۰ است. بنا بر دوگانگی ضعیف، ۲۳۰ کمترین هزینه ممکن است. این استدلال حتی بدون اجرای یک حل‌گر بزرگ، یک گواه قابل بررسی برای بهینگی می‌دهد.

۳. روش‌های حل عملی و تفاوتشان

برای جواب اولیه، روش گوشه شمال‌غربی ساده‌ترین است؛ روش کمترین هزینه و روش تقریب وُگل (VAM) ممکن است جواب اولیه بهتری بسازند، اما به‌تنهایی بهینگی را تضمین نمی‌کنند. برای آزمون و بهبود، روش پتانسیل‌ها (MODI / u–v) هزینه کاهش‌یافته خانه‌های خالی را می‌سنجد. در حالت کمینه‌سازی، وقتی تمام هزینه‌های کاهش‌یافته c_ij−u_i−v_j نامنفی باشند، جواب موجود بهینه است. اگر هزینه کاهش‌یافته خانه‌ای منفی شود، می‌توان با ساخت چرخه بسته در جدول حمل، جواب را بهبود داد؛ البته در حالت تباه باید قاعده انتخاب پایه و مدیریت چرخه‌ها دقیق باشد.

از دید محاسبات عمومی‌تر، مدل حمل‌ونقل را می‌توان به‌عنوان مسئله جریان با کمترین هزینه (min-cost flow) حل کرد. در سیستم‌های دارای ظرفیت مسیر، چند کالای متفاوت یا شبکه بزرگ، این فرمول‌بندی اغلب مناسب‌تر از روش دستی جدول حمل است.

۴. اگر عرضه و تقاضا برابر نباشند چه؟

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

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

۵. سناریوی دوم: افزایش هزینه مسیر

در طرح بهینه، مسیر A→۲ استفاده نشده است؛ چون هزینه ۶ آن از مجموع پتانسیل‌های متناظر یعنی u_A+v_2=4 بزرگ‌تر است. هزینه کاهش‌یافته آن ۲ است؛ به‌صورت محلی به این معنی که اگر یک واحد جریان را از طریق این مسیر وارد یک چرخه مجاز کنیم، در ساختار فعلی حداقل ۲ واحد هزینه اضافه می‌شود. این استدلال قاعده تحلیلی یک پایه مشخص است؛ برای تغییرات بزرگ یا هم‌زمان چند هزینه باید دوباره بهینگی را ارزیابی کرد.

۶. خطاهای رایج در مدل‌سازی حمل‌ونقل

• مسافت و هزینه را یکسان فرض نکنید: عوارض، سوخت، محدودیت جاده و هزینه تخلیه ممکن است مسیری طولانی‌تر را ارزان‌تر کنند.
• در مدل تک‌کالایی پیوسته، محدودیت «تعداد صحیح کامیون» وجود ندارد؛ اگر حمل بسته‌ای یا کامل‌بار اجباری است، مدل صحیح‌عدد لازم است.
• فراموش نکنید هزینه مسیر A→۱ با هزینه B→۱ مستقل است؛ تقارن الزامی نیست.
• خانه خالی در جواب پایه لزوماً به معنای مسیر ممنوع نیست؛ ممکن است فقط در جواب فعلی غیرفعال باشد.
• قیمت‌های دوگان قیود تساوی می‌توانند منفی باشند؛ برخلاف الگوی ساده دوگان بیشینه‌سازی با قیود ≤، آن‌ها را بی‌دلیل نامنفی نکنید.
• برای داده‌های واقعی، عدم توازن عرضه و تقاضا، ظرفیت هر مسیر و زمان تحویل را قبل از حل بررسی کنید.

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

سطح ۱: بررسی کنید طرح A→(۱۰،۰،۱۰) و B→(۰،۲۵،۵) تمام عرضه‌ها و تقاضاها را رعایت می‌کند.

سطح ۲: هزینه روش گوشه شمال‌غربی را حساب کنید و با طرح بهینه مقایسه کنید.

سطح ۳: در همان داده‌ها، اگر هزینه A→۲ از ۶ به ۴ کاهش یابد، آیا گواه دوگان فعلی هنوز معتبر است؟ آیا یکتایی جواب بهینه تضمین می‌شود؟

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