# Linear Programming on a Network

• Jan 16th 2010, 04:26 AM
Rubberduckzilla
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?
• Jan 17th 2010, 02:17 AM
CaptainBlack
Quote:

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
• Jan 17th 2010, 03:25 AM
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?
• Jan 17th 2010, 04:22 AM
CaptainBlack
Quote:

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:

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

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

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

CB
• Jan 17th 2010, 04:51 AM
Rubberduckzilla
I'm also told that 'the company ships hundreds of goods crates every month to docks m and n' if that helps..
• Jan 17th 2010, 09:04 AM
CaptainBlack
Quote:

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
• Jan 17th 2010, 09:08 AM
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?
• Jan 17th 2010, 09:14 AM
CaptainBlack
Quote:

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
• Jan 17th 2010, 09:19 AM
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?
• Jan 17th 2010, 09:24 AM
CaptainBlack
Quote:

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
• Jan 17th 2010, 11:14 AM
CaptainBlack
Is not this problem solved more easily by the gready algorithm?

CB
• Jan 17th 2010, 10:29 PM
Rubberduckzilla
Quote:

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.

Quote:

Originally Posted by CaptainBlack
The flows along each edge are the variables. then the objective is:

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

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

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

CB

Minimizing
$O = \sum_{i,k} f_{i,k} d_{i,k}$
would be the same as maximizing
$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.
• Jan 18th 2010, 12:50 AM
CaptainBlack
Quote:

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

Minimizing
$O = \sum_{i,k} f_{i,k} d_{i,k}$
would be the same as maximizing
$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
• Jan 18th 2010, 01:13 AM
Rubberduckzilla
Quote:

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?