مسألة النقل

مسألة النقل (Transportation Problem) — تُسمّى أيضًا مسألة هيتشكوك أو مسألة هيتشكوك-كوبمانز — هي المسألة الكلاسيكية للبرمجة الخطية (LP) لتخصيص الشحنات الأسبوعية بين m مصدر (مصانع، مستودعات) وn هدف (عملاء، نقاط توزيع). لكلّ مصدر طاقة ثابتة (s_i)، ولكلّ هدف طلب ثابت (d_j)، ولكلّ زوج مصدر-هدف تكلفة نقل وحدوية (c_ij)؛ متغيّر القرار x_ij ≥ 0 يقلّل التكلفة الإجمالية. متوازنة عندما يكون العرض الكلّي مساويًا للطلب الكلّي؛ الحالات غير المتوازنة تُحلّ بإضافة مصدر أو هدف وهمي. أسّسها هيتشكوك (1941) وكوبمانز (1947)؛ طوّر دانتزيغ (1951) طريقة Simplex على هذه المسألة. مسألة التخصيص حالة خاصّة (عدد المصادر = الأهداف، الطاقة = الطلب = 1). تحلّ solvers LP الحديثة آلاف أزواج المصدر-الهدف في ثوانٍ؛ المتغيّرات المزدوجة (الأسعار الظلّيّة) مدخل مباشر لقرارات الطاقة الهامشية.