바이피트 테이트 그래프에서 가장자리 통과의 비용을 최소화하기 위해 알고리즘을 찾고 제약 조건에 따라

Question

나는 각각 다른 양의 모래를 붙일 수있는 URN을 가지고 있습니다. 포터는 모래 단위당 운송 수수료를받는 각 URN에 모래를 전달할 수 있습니다. 각 포터는 각 URN에 전달할 수있는 유한 양의 모래를 가지고 있습니다. 목표는 총 비용을 최소화하면서 모든 사용 가능한 모래로 URN을 채우는 것입니다. 동기 부여가있는 예 :

>>

블랙 서클은 포터를 보여줍니다. 포터 서클의 중심의 값은 전송할 수있는 모래 양을 보여줍니다. 회색 사각형은 URNS를 보여줍니다. URN의 중심의 값은 URN이 보류 할 수있는 모래 양을 보여줍니다. Porter_urn 모서리는 주어진 URN으로 1 단위의 모래를 운반하는 비용을 보여줍니다. 이 예제를 사용하여 100 단위의 모래가있는 포터 1은 총 65 단위의 모래를 보유 할 수있는 50 ~ URN 3의 비용으로 1 단위의 모래를 수송 할 수 있습니다. 그것은 매우 비싸게 될 것입니다!

이 최적화 문제를 해결하기위한 알고리즘이 있습니까? 아마도 최대 흐름 문제점 또는 multi-kapsack 문제점? 또는 운영 연구에서 다른 알고리즘을 사용하고 있습니까?

Answer 1

이것은 최소 비용 흐름 문제 입니다.누락 된 것은 원가와 용량이 0이고 각 URN에서 싱크대와 동일한 용량으로 싱크대로 각 URN의 0 비용 에지가있는 각 포터의 가장자리입니다.