Edexcel D2 textbook: transportation problem as a linear programming problem

Watch this thread
Ian89
Badges: 0
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 11 years ago
#1
I'm working independently through the Edexcel Decision Maths D2 textbook, and have got stuck on Sec 1.8, where it covers re-writing transportation problems as a linear programming problem. In particular Example 12.


I can't follow how it gets the inequalities in the Constraints.

If x(ij) is the number of units moved from Supplier i to Depot j, I can see why x(11) + x(12) + x(13) <= 15.
This is saying total supplied from Supplier 1 must be less than or equal to the available supply at that site (15 in this case).

But for the constraints on the individual Depots, I expected a GREATER THAN OR EQUAL inequality.
Book has x(11) + x(21) + x (31) <=30 which seems to say the total delivered to Depot 1 could be LESS than the total required demand at that depot.

I think this constraint should be:
x(11) + x(21) + x (31) >= 30 ie you've got to send AT LEAST AS MUCH to Depot 1 as is needed there.

The textbook's linear programming problem (minimise a Cost, with all the Constraints being "less than or equal to" ) seems to have the obvious solution of having all x(ij) equal to zero, which satisfies all the constraints given and minimises the Cost at zero. BUT this means nothing gets delivered anywhere - making it a rather pointless linear programming problem! And it is a different answer than in the Transportation version of the problem - so the two forms of the problem aren't consistent with each other.

All the subsequent exercises in the chapter have the same issue, so it doesn't look like a typo in the particular example.

What am I missing?

Many thanks
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report 11 years ago
#2
(Original post by Ian89)
...
Your reasoning seems sound, but I don't have the actual book, so....

Looking at another text I do have, the demand constraints although of the form \sum x_{ij}\ge D_j, they are sometimes written as -\sum x_{ij}\le -D_j. Don't know if that's any use?
0
reply
Ian89
Badges: 0
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report Thread starter 11 years ago
#3
thanks for this.

Seems to confirm that the Edexcel textbook is wrong.
0
reply
metaltron
Badges: 11
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report 8 years ago
#4
(Original post by ghostwalker)
Your reasoning seems sound, but I don't have the actual book, so....

Looking at another text I do have, the demand constraints although of the form \sum x_{ij}\ge D_j, they are sometimes written as -\sum x_{ij}\le -D_j. Don't know if that's any use?
Hi, sorry to bump this thread, but has there been any developments on this issue in the past couple of years?

I'm asking because a couple of years ago (Jan 06!) the edexcel mark scheme used the same approach as the textbook, which I believe is wrong for the reasons in the OP. Also an identical problem appeared in this year's exam. I was quite shocked to see the, quite likely, flawed method in the mark scheme, so I'm wondering what do you think of this?

It's Q3 here http://www.edexcel.com/migrationdocu...ark_Scheme.pdf

Paper is here:

https://www.google.co.uk/#q=edexcel+...question+paper
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report 8 years ago
#5
(Original post by metaltron)
Hi, sorry to bump this thread, but has there been any developments on this issue in the past couple of years?
Just checked through again, and I can see no justification for their use of \leq for the demand constraints, and think they should be \geq
1
reply
metaltron
Badges: 11
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report 8 years ago
#6
(Original post by ghostwalker)
Just checked through again, and I can see no justification for their use of \leq for the demand constraints, and think they should be \geq
Ah thank you What do you think the exam board will do... just change their answer this year so that it is correct? If they do the same thing as they did back in 06 that would be surprising to say the least... it makes no sense!
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report 8 years ago
#7
(Original post by metaltron)
Ah thank you What do you think the exam board will do... just change their answer this year so that it is correct? If they do the same thing as they did back in 06 that would be surprising to say the least... it makes no sense!
No idea what the board would do.

I find it strange that an official mark scheme should contain so gross an error, several years after the fact.

Perhaps I'm missing something....
0
reply
Arsey
Badges: 10
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report 8 years ago
#8
My reply on the other thread. In terms of an Edexcel solution, you should never use >

In an 'Edexcel' transportation problem, to solve the problem you find a solution that uses the supply and satisfies demand. In other words the objective is tominimise costs whilst satisfying demand.

That is why you cannot set Xij = 0 as you will not satisfy demand.

That is why the demand constraints cannot be > as you will have transported more than demand, which if you are to minimise costs you cannot do.

In a balanced problem all constraints should be = as the solutions requires you to meet the demands if you have enough stock. However, in an unbalanced problem when you do not have enough stock to meet demand you should use <=

So...

You should NEVER use > in constraints because

1) You can never transport more than you have in stock
2) You can never transport more than the demand
0
reply
Arsey
Badges: 10
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
Report 8 years ago
#9
My reply on the other thread. In terms of an Edexcel solution, you should never use >

In an 'Edexcel' transportation problem, to solve the problem you find a solution that uses the supply and satisfies demand. In other words the objective is to minimise costs whilst satisfying demand.

That is why you cannot set Xij = 0 as you will not satisfy demand.

That is why the demand constraints cannot be > as you will have transported more than demand, which if you are to minimise costs you cannot do.

In a balanced problem all constraints should be = as the solutions requires you to meet the demands if you have enough stock. However, in an unbalanced problem when you do not have enough stock to meet demand you should use <=

So...

You should NEVER use > in constraints because

1) You can never transport more than you have in stock
2) You can never transport more than the demand
0
reply
metaltron
Badges: 11
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report 8 years ago
#10
(Original post by Arsey)
My reply on the other thread. In terms of an Edexcel solution, you should never use >

In an 'Edexcel' transportation problem, to solve the problem you find a solution that uses the supply and satisfies demand. In other words the objective is to minimise costs whilst satisfying demand.

That is why you cannot set Xij = 0 as you will not satisfy demand.

That is why the demand constraints cannot be > as you will have transported more than demand, which if you are to minimise costs you cannot do.

In a balanced problem all constraints should be = as the solutions requires you to meet the demands if you have enough stock. However, in an unbalanced problem when you do not have enough stock to meet demand you should use <=

So...

You should NEVER use > in constraints because

1) You can never transport more than you have in stock
2) You can never transport more than the demand
ok so as I replied in the other thread...

1. You can never transport more than you have in stock...

This is true but it is covered by the <= stock inequalities.

2. As I said before if you have a balanced problem equality would be forced when using the => inequalities for demand.
If the problem is not balanced then the objective function will mean that you never end up supplying more than you need to.
If there is more demand than stock, then quite rightly, there will be no solution to the transportation problem using => inequalities.

Here is a balanced problem that I prepared earlier:

\begin{pmatrix} _ & Y & Z & Stock \\W & 33 & 19 & 50 \\X & 21 & 29 & 100 \\ Demand & 73 & 77 & _ \end{pmatrix}

I performed the NW corner method and stepping stone on this and got a best solution of P= 3266 when a =0 , b=50 , c=73 and d= 27.

The idea is to express this transportation problem as an LP problem. So let's have a look at both methods.

In both method let a be the number of units transported from W to Y
b be the number of units transported from W to Z
c be the number of units transported from X to Y
d be the number of units transported from X to Z.

Method 1:

Spoiler:
Show
Objective: Minimise  P = 33a + 19b + 21c + 29d

Subject to:  a+b \leq 50
 c+d \leq 100
 a + c \leq 73
 b + d \leq 77
 a,b,c,d \geq 0

Solving this problem using this http://www.zweigmedia.com/RealWorld/simplex.html

yields optimal solution  P=0, a=b=c=d=0 .


Method 2:

Spoiler:
Show
Objective: Minimise  P = 33a + 19b + 21c + 29d

Subject to:  a+b \leq 50
 c+d \leq 100
 a + c \geq 73
 b + d \geq 77
 a,b,c,d \geq 0

Solving this problem using this http://www.zweigmedia.com/RealWorld/simplex.html

yields optimal solution  P=3266, a = 0, b=50, c = 73, d =27 .


I don't think ghostwalker is going to be too pleased when he comes online with these two massive responses
0
reply
ghostwalker
Badges: 17
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Report 8 years ago
#11
(Original post by metaltron)
I don't think ghostwalker is going to be too pleased when he comes online with these two massive responses
I stand by my earlier statement.

If Edexcel, in their infinite wisdom, choose to look at it in one particular way, so be it.
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest

Do you know what you'll do if you don't get the grades you're hoping for?

Find something else in clearing (30)
27.03%
Take a gap year (17)
15.32%
Resit my exams (30)
27.03%
Look for alternate pathways to the career I want (17)
15.32%
I don't know yet (12)
10.81%
Something else (tell us in the thread) (5)
4.5%

Watched Threads

View All