Looking to identify a "classic" problem and identify availble algorithms to solve it
I have a problem that I'm sure is a classic but I cant find the name of this problem. Since I am very bad at formalizing with mathematical formulas, here is a picture and a written explanation.
I have a product that is stored in n different warehouses W (on the left of the graph). I have stores S that can receive up to a given a quantity of this product (note capacity on the graph). I also have a "rubbish" that can handle the extra amount of products if the number of products in the warehouse exceed the capacity of the stores.
I have costs of distributing a single unit of the product from each warehouse to each store and also to rubish C(Wn,Sm) in blue for warehouse W1 in the graph I didnt add all the other C so that it is still readable.
I need to distribute all the products in the warehouse to all the stores (+ rubish eventually) while minimizing the cost (or maximising the gain if C is the price paid by store S to be supplied from warehouse W).
What is this problem called ? Is it NP complete ? What algorithm can solve it ? My first thought was Hungarian algorithm of assignment optimal but I found it dead end because that would be the best assignment from single W to single S.
When C is a matrix of all ones, I can find a solution using the max flow algorithm. But when C is different for each edge, I'm stuck.
Thanks for your help
This is commonly called a Transport or Network Model, which you can find in tomes such as Management Science Modelling by Albright & Winston.
So did this just to show:
Variations include trying to minimise the cost of rubbish - then W3 supplies S1:S3. You could have other criteria such as each W must use a minimum of some percentage of its capacity as in be "fair" to all suppliers...