Edexcel D2 textbook: transportation problem as a linear programming problem

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

Reply 1

ghostwalker

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?

Reply 2

Ian89

thanks for this.

Seems to confirm that the Edexcel textbook is wrong.

Reply 3

metaltron

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/migrationdocuments/QP%20GCE%20Curriculum%202000/Maths/D2_January_2006_Mark_Scheme.pdf

Paper is here:

https://www.google.co.uk/#q=edexcel+d2+january+2006+question+paper

Reply 4

ghostwalker

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

Reply 5

metaltron

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 :smile:

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! :tongue:

(edited 9 years ago)

Reply 6

ghostwalker

Original post by metaltron

Ah thank you :smile:

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....

Reply 7

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 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

Reply 8

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

Reply 9

metaltron

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:

Unparseable latex formula:

\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

Method 2:

Spoiler