Thread: Linear Programming on a Network

OK, goods are transported from both docks m and n to depots a b and c (see attached image). m can handle up to twice as many goods as n and the capacity of each depot is equal. I have the distances between each point and my task is to use linear programming to minimize the total distance traveled.
My problem is I don't know how linear programming can be adapted to this kind of problem with both capacities and distances. Can anyone start me off please?

Originally Posted by Rubberduckzilla

OK, goods are transported from both docks m and n to depots a b and c (see attached image). m can handle up to twice as many goods as n and the capacity of each depot is equal. I have the distances between each point and my task is to use linear programming to minimize the total distance traveled.
My problem is I don't know how linear programming can be adapted to this kind of problem with both capacities and distances. Can anyone start me off please?

The objective is to minimise the total (or may be the average) distance that goods are transported. The link capacities give you the constraints.

There does appear to be something missing, like the arrival rate/quantity of goods at the docks. Otherwise this is a standard LP problem.

CB

That's all the information I'm given. I'm allowed to make simplifying assumptions so there may be further restrictions or practical considerations. But I don't know what these would be.
Edit:
If i say the distances are:
m-a=94
m-b=126
m-c=208
n-a=117
n-b=258
n-c=181
wouldn't there be a variable for each road/edge? is that still solvable or am i over-complicating it?

Originally Posted by Rubberduckzilla

That's all the information I'm given. I'm allowed to make simplifying assumptions so there may be further restrictions or practical considerations. But I don't know what these would be.
Edit:
If i say the distances are:
m-a=94
m-b=126
m-c=208
n-a=117
n-b=258
n-c=181
wouldn't there be a variable for each road/edge? is that still solvable or am i over-complicating it?

The flows along each edge are the variables. then the objective is:

$\displaystyle O = \sum_{i,k} f_{i,k} d_{i,k}$

where $\displaystyle f_{i,k}$ denotes the flow from source $\displaystyle i$ to sink $\displaystyle k$ and $\displaystyle d_{i,k}$ is the distance from source $\displaystyle i$ to sink $\displaystyle k$. The $\displaystyle f $'s are the variables.

But I am still suspicious that there is missing data or information.

CB

I'm also told that 'the company ships hundreds of goods crates every month to docks m and n' if that helps..

Originally Posted by Rubberduckzilla

I'm also told that 'the company ships hundreds of goods crates every month to docks m and n' if that helps..

Not really since if the quantity of goods is less than the capacity of both m and a the flow will all be along the link m-a, only if the capacity of one or the other will any other link be utilised. How the flow distributes itself across the links depends on the size of the flow.

CB

Can I get by this by making the total goods shipped to the docks a variable, G? Would it still be solvable via LP?

Originally Posted by Rubberduckzilla

Can I get by this by making the total goods shipped to the docks a variable, G? Would it still be solvable via LP?

That might be possible but what will you do about the objective? If you do that the above objective will be minimised when G=0.

CB

If I leave it in terms of G then after solving I should be able to input a value for G when needed and find each of the variables. This makes the model useful to the company because G could change each month. Am I right?

Originally Posted by Rubberduckzilla

If I leave it in terms of G then after solving I should be able to input a value for G when needed and find each of the variables. This makes the model useful to the company because G could change each month. Am I right?

I doubt you can easily find a general solution for such a LP problem. With a properly set up model with G as a parameter a run can be done each month to find the optimal flow once G is known. So in a sense a properly formulated model is the general solution that you require.

CB

Is not this problem solved more easily by the gready algorithm?

CB

Originally Posted by CaptainBlack

Is not this problem solved more easily by the gready algorithm?

CB

I was told I had to use LP, but yes, that probably would be a much more suitable method.

Originally Posted by CaptainBlack

The flows along each edge are the variables. then the objective is:

$\displaystyle O = \sum_{i,k} f_{i,k} d_{i,k}$

where $\displaystyle f_{i,k}$ denotes the flow from source $\displaystyle i$ to sink $\displaystyle k$ and $\displaystyle d_{i,k}$ is the distance from source $\displaystyle i$ to sink $\displaystyle k$. The $\displaystyle f $'s are the variables.

But I am still suspicious that there is missing data or information.

CB

Minimizing
$\displaystyle O = \sum_{i,k} f_{i,k} d_{i,k}$
would be the same as maximizing
$\displaystyle O = -\sum_{i,k} f_{i,k} d_{i,k}$
right?
but that would mean there are no negatives in the objective row, which is a problem.

Originally Posted by Rubberduckzilla

I was told I had to use LP, but yes, that probably would be a much more suitable method.



Minimizing
$\displaystyle O = \sum_{i,k} f_{i,k} d_{i,k}$
would be the same as maximizing
$\displaystyle O = -\sum_{i,k} f_{i,k} d_{i,k}$
right?
but that would mean there are no negatives in the objective row, which is a problem.

Yes maximising what you give is the same as minimising the earlier expression. I'm not clear why this would be a problem is it something to do with your solver?

CB

Originally Posted by CaptainBlack

Yes maximising what you give is the same as minimising the earlier expression. I'm not clear why this would be a problem is it something to do with your solver?

CB

I'm using simplex method to solve, is there a more suitable way I'm not aware of?