Linear programming: modelling a transportation problem

Question

I have a transportation problem with a twist-- I have a set number of managers and a set number of stores (where there are way more stores than managers), and I'm trying to match the managers to stores. The twist is that each manager can have up to a certain number of stores (constraint), and no two managers share the same store. The goal is to minimise the distance between the manager and each store s/he manages. I haven't been able to figure out how to model this problem, or rather if it is even possible to formulate this problem into a linear programming model. Please let me know!

Answer 1

Let $x_{ij}$ be a binary variable that takes value $1$ if and only if manager $i$ is assigned to store $j$.

You want to minimize the total distance after assignment: $$ \sum_{i,j}d_{ij}x_{ij} $$ subject to :

• A manager $i$ cannot have more than $S_i$ stores : $$ \sum_{j}x_{ij} \le S_i\quad \forall i $$
• No two managers share the same store : $$ \sum_{i}x_{ij} =1 \quad \forall j $$
• Variables are binary : $$ x_{ij}\in \{0,1\} \quad \forall i,j $$