مسألة الـ Transportation: Northwest Corner وLeast Cost وVogel
مسألة الـ transportation بتشحن البضاعة من مصادر لوجهات بأقل تكلفة. هتتعلم الـ balancing والتلات طرق للحل الابتدائي وإزاي تتأكد إنه optimal.
مسألة الـ transportation فيها m مصدر بكميات عرض وn وجهة بكميات طلب، وتكلفة للوحدة على كل طريق. الهدف تحدد كام تشحن على كل طريق علشان كل العرض والطلب يتغطوا بأقل تكلفة كلية. لازم المسألة تبقى balanced: مجموع العرض = مجموع الطلب. لو العرض أكبر ضيف وجهة وهمية dummy تكلفتها صفر، ولو الطلب أكبر ضيف مصدر dummy.
في تلات طرق بتدّي حل أساسي ابتدائي. طريقة الـ northwest corner بتبدأ من الخلية اللي فوق شمال وتوزع أكبر كمية ممكنة وبعدين تتحرك يمين أو تحت من غير ما تبص للتكلفة، فهي سريعة بس غالبًا بعيدة عن الـ optimal. طريقة الـ least cost بتوزع الأول على أرخص خلية وبعدين اللي بعدها، وبتدّي بداية أحسن. وطريقة Vogel approximation بتحسب لكل صف وعمود الـ penalty (الفرق بين أصغر تكلفتين)، وتوزع في الصف أو العمود اللي penalty بتاعه أكبر على أرخص خلية فيه، وغالبًا بتدّي أحسن حل ابتدائي.
الحل الأساسي بيكون فيه m + n - 1 خلية موزعة. لو أقل يبقى degenerate وبتضيف توزيع صفري. ولاختبار الـ optimality استخدم طريقة MODI (u-v): خلي u1 = 0، ولاقي u وv من الخلايا الموزعة (ui + vj = cij)، وبعدين احسب الـ opportunity cost وهو cij - ui - vj لكل خلية فاضية. لو كلها غير سالبة الحل optimal، غير كده الخلية الأكتر سلبية بتدخل وبتعيد التوزيع حوالين loop مقفولة.
أهم النقاط
- وازن المسألة بـ dummy source أو destination.
- الـ Northwest corner بتتجاهل التكلفة. والـ least cost وVogel بيستخدموها.
- Vogel بتستخدم penalties للصفوف والأعمدة وغالبًا الأقرب للـ optimal.
- الحل الأساسي فيه m + n - 1 توزيع.
- MODI: optimal لما كل cij - ui - vj غير سالبة.
مثال محلول
مصدرين عرضهم 20 و30، ووجهتين طلبهم 25 و25. التكاليف: S1 لـ D1 = 4 وS1 لـ D2 = 6 وS2 لـ D1 = 5 وS2 لـ D2 = 3. مجموع العرض 50 يساوي مجموع الطلب 50 فهي balanced. Northwest corner: S1 لـ D1 = 20، وبعدين S2 لـ D1 = 5 وS2 لـ D2 = 25. التكلفة = 20 × 4 + 5 × 5 + 25 × 3 = 80 + 25 + 75 = 180. عندنا 3 توزيعات وهي تساوي m + n - 1 = 3.
أسئلة شائعة
لو العرض مش بيساوي الطلب أعمل إيه؟
ضيف وجهة أو مصدر dummy بتكلفة صفر علشان توازن المسألة.
أنهي طريقة بتدّي أحسن بداية؟
غالبًا طريقة Vogel approximation.
مواضيع مرتبطة
- مسألة الـ Assignment: طريقة Hungarian خطوة بخطوة
- البرمجة الخطية: الـ Formulation وطريقة الرسم Graphical
- طريقة Simplex: الخطوات والـ Slack Variables والـ Tableau
- كل المواضيع: الأوبريشنز ريسيرش
بصمجلي مشروع طلابي مستقل، مش موقع رسمي لجامعة الدلتا. ارجع لمحاضراتك ودكتورك دايمًا.