Solving a Coal Blending Problem with LP

[Wilmer]

Can someone explain what is being asked in this problem. I find it quite confusing.
Particularly equation [3]. Thank you.
................
A firm selling cooking coal to power stations, requires to formulate a blend of
coal with a phosphorus content of at most 0.04% and ash impurity of at most 5%.
Three different grades of coal are available to blend; the phosphorus and ash
content and the price of each grade are given in the table below:

    Grade %Phosphorus %Ash  $/Tonne 
a     1      0.03       3     80 
b     2      0.05      14     60 
c     3      0.08       8     90

Question: Show that the problem of determining the optimal blend can be modeled
by the following Linear Programming problem.
Find a, b, c to minimize Z = 80a + 60b + 90c subject to:

3a + 5b + 8c ≤ 4 [1]
3a +14b + 8c ≤ 5 [2]
a + b + c ≤ 1 [3]

Non-negativity constraint = a, b, c ≥ 0.

Take care in your answer to define the decision variables and to explain briefly
how the objective funtions and the constraints are derived

 

[CaptainBlack]

Can someone explain what is being asked in this problem. I find it quite confusing.
Particularly equation [3]. Thank you.
................
A firm selling cooking coal to power stations, requires to formulate a blend of
coal with a phosphorus content of at most 0.04% and ash impurity of at most 5%.
Three different grades of coal are available to blend; the phosphorus and ash
content and the price of each grade are given in the table below:

    Grade %Phosphorus %Ash  $/Tonne 
a     1      0.03       3     80 
b     2      0.05      14     60 
c     3      0.08       8     90

Question: Show that the problem of determining the optimal blend can be modeled
by the following Linear Programming problem.
Find a, b, c to minimize Z = 80a + 60b + 90c subject to:

3a + 5b + 8c ≤ 4 [1]
3a +14b + 8c ≤ 5 [2]
a + b + c ≤ 1 [3]

Non-negativity constraint = a, b, c ≥ 0.

Take care in your answer to define the decision variables and to explain briefly
how the objective funtions and the constraints are derived

This is a linear programming problem, where 1 ton of product consists a, b, c tons of each available grade of coal.

Then the objective Z=80a + 60b + 90c is the cost of 1 ton of the blend, which is what you want to minimise.

Constraint [1] is the phosphorous content constraint (multiplied by 100)
Constraint [2] the ash constraint (again multiplied by 100)

Now constraint [3] is the interesting one, the actual constraint is that a+b+c=1 which is the requirement that we are blending 1 ton of coal. I imagine it is written as an inequality to conform to the linear programming paradigm. If this constraint is not active/tight in the solution to the LP problem as formulated then you will not have a viable solution.

CB

 

[Wilmer]

Constraint [2] the ash constraint (again multiplied by 100)

Thank you very much.
Isn't constraint[2] already multiplied by 100?

And it is evident that the major component will be grade 1, right?

 

[CaptainBlack]

Thank you very much.
Isn't constraint[2] already multiplied by 100?

And it is evident that the major component will be grade 1, right?

Yes and yes.

CB

 

[Wilmer]

IF the equations are set to equal the limits, then:
3a + 5b + 8c = 4 [1]
3a +14b + 8c = 5 [2]
1a + 1b + 1c = 1 [3]

System easily solved; a = 57/72, b = 8/72, c = 7/72

Phosphorus:
57 @ 3
8 @ 5
7 @ 8
------
72 @ 267/72 (~3.708333) ; must be at most 4, so ok

Ash:
57 @ 3
8 @ 14
7 @ 8
-------
72 @ 339/72 (~4.708333) ; must be at most 5, so ok

Now, this is where I'm confused; how to apply above to 1 ton.
Am I missing something evident? Thank you.

 

[CaptainBlack]

IF the equations are set to equal the limits, then:
3a + 5b + 8c = 4 [1]
3a +14b + 8c = 5 [2]
1a + 1b + 1c = 1 [3]

System easily solved; a = 57/72, b = 8/72, c = 7/72

Phosphorus:
57 @ 3
8 @ 5
7 @ 8
------
72 @ 267/72 (~3.708333) ; must be at most 4, so ok

Ash:
57 @ 3
8 @ 14
7 @ 8
-------
72 @ 339/72 (~4.708333) ; must be at most 5, so ok

Now, this is where I'm confused; how to apply above to 1 ton.
Am I missing something evident? Thank you.

Yes you are, you can't solve assuming equality for the constraints, because you then have no degrees of freedon left to do the optimisation. In a LP not all the constraints need be tight at the optimum, but in this case we do require the third one to be tight. Now it maybe that all the constraints are tight at the optimum, but that would be unusual, one or both of the first two constraints may not be tight (as I said befor the third is a problem, if it is not tight at the optimum of the problem as expressed then you do not have a solution to the real problem).

The natural way to solve this is to use the equality constraint to eliminate one of the variables which will leave you with a LP in two decision variables. The way it is expressed I believe is wrong and either the trick of elliminating one variable needs to be used, or some other trick for dealing with equality constraints is need, or luck so that the third constraint is tight in the solution of the problem as expressed.

Plan A should be to check for typos in either the question as given to you or in your transcription of the problem.

CB

 

[Wilmer]

I hear you...thanks!

Well, I "brute-strengthed" it in terms of 1000 tons:

a = 819, b = 181, c = 0, cost = 76380, phosphorus = 3.362, ash = 4.991

Pretty well as expected, simply by eyeballing the problem...

 

[CaptainBlack]

I hear you...thanks!

Well, I "brute-strengthed" it in terms of 1000 tons:

a = 819, b = 181, c = 0, cost = 76380, phosphorus = 3.362, ash = 4.991

Pretty well as expected, simply by eyeballing the problem...

Try a=9/11 and b=2/11.

I have to ask why are you attempting a LP problem when you apparently have not seen one before?

CB

 

[Wilmer]

Try a=9/11 and b=2/11.
I have to ask why are you attempting a LP problem when you apparently have not seen one before?

I was aware of that one: simply force a and b to combine for ash = 5;
3a + 14(1 - a) = 5; a = 9/11, so b = 2/11.
Cost 76.36 instead of the 76.38 I got using 1000 instead of 1.
It was the "eyeball" one I was referring to...

I have kinda "seen them before", but not as confusing as this one.
As to your "why?": trying to learn! Thanks.

 

[CaptainBlack]

I was aware of that one: simply force a and b to combine for ash = 5;
3a + 14(1 - a) = 5; a = 9/11, so b = 2/11.
Cost 76.36 instead of the 76.38 I got using 1000 instead of 1.
It was the "eyeball" one I was referring to...

I have kinda "seen them before", but not as confusing as this one.
As to your "why?": trying to learn! Thanks.

I hate to reply with yet another question, but the problem you posted has what appears to be a mistake or at least a peculiarity (that the sum of the proportions is less than or equal to 1 rather than equal to one). Is that question exactly as asked, and where was it asked?

CB

 

[Wilmer]

I hate to reply with yet another question, but the problem you posted has what appears to be a mistake or at least a peculiarity (that the sum of the proportions is less than or equal to 1 rather than equal to one). Is that question exactly as asked, and where was it asked?

Don't be shy!
If you look at my initial post again, you will see my reference to what you're saying:

"Particularly equation [3]
.....
a + b + c ≤ 1 [3] "

And what I posted is a "copy-paste" of the original problem; so exactly same.