تبحث عن خوارزمية لتقليل تكلفة اجتياز الحافة في رسم بياني ثنائي القيود تخضع للقيود

Question

لدي مجموعة من urns التي يمكن أن تحمل كل من كميات مختلفة من الرمال. يمكن للحمالين تقديم الرمال إلى كل urn تخضع لرسوم النقل لكل وحدة من الرمال. كل بورتر لديه كمية محدودة من الرمال، أنها قادرة على التسليم لكل جرة. الهدف هو ملء الحور مع كل الرمال المتاحة مع تقليل التكلفة الإجمالية. إليك مثال محفز:

href="https://i.stack.imgur.com/ftbun.png" rel="nofollow noreferrer">

الدوائر السوداء عرض الحمالين. تظهر القيمة في وسط الدوائر الحرة المبلغ الإجمالي للرمال التي يمكنهم نقلها. المربعات الرمادية تظهر urns. تظهر القيمة في مركز الجرار كمية الرمال التي يمكن أن تعقدها Urn. تظهر حواف Porter_urn تكلفة نقل وحدة 1 من الرمال إلى جرة معينة. باستخدام هذا المثال، يمكن للناصي 1، التي لديها 100 وحدة من الرمل نقل وحدة واحدة من الرمل بتكلفة 50 إلى urn 3، والتي يمكن أن تعقد ما مجموعه 65 وحدة من الرمال. سيكون ذلك مكلفا للغاية!

هل هناك خوارزمية لحل مشكلة التحسين هذه؟ يبدو أنه ربما ربما يكون الحد الأقصى للتدفق مشكلة أو ربما متعددة الحمل

Answer 1

هذا مستقيم عن مشكلة تدفق الحد الأدنى من التكلفة .كل ما في عداد المفقودين هو ميزة من المصدر إلى كل بورتر بتكلفة صفرية وسعة تساوي الحمال، وتكلفة صفرية من كل جرة إلى الحوض بالسعة تساوي urn.