Linear Programming

ritchie

New member
Joined
Aug 17, 2012
Messages
8
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
10.03380
20.051460
30.08890
Question: Show that the problem of determining the optimal blend can be modelled by the followingLinear Programming problem. Find X1, X2, X3 is in R (real) to minimize Z= 8X1 + 6X2 + 9X3 subject to:

  1. 3X1+ 5X2+ 8X3 ≤ 4
  2. 3X1+14X2+ 8X3 ≤ 5
  3. X1+ X2+ X3 ≤ 1

Non-negativity constraint = X1, X2, X3 ≥ 0.

Take care in your answer to define the decision variables and to explain briefly how the objective funtions and the constraints are derived.
 
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
1
0.03
3
80
2
0.05
14
60
3
0.08
8
90
Question: Show that the problem of determining the optimal blend can be modelled by the followingLinear Programming problem. Find X1, X2, X3 is in R (real) to minimize Z= 8X1 + 6X2 + 9X3 subject to:

  1. 3X1+ 5X2+ 8X3 ≤ 4
  2. 3X1+14X2+ 8X3 ≤ 5
  3. X1+ X2+ X3 ≤ 1

Non-negativity constraint = X1, X2, X3 ≥ 0.

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

What have you done so far on this? Once we see where you ar stuck we can give you some help/hints to proceed.
 
So, I think found that the variables are the grade, that X1 is Grade 1 and X2 is Grade 2 and X3 is Grade 3. In fact I don't know exactly how to tackle the question. I don't know if its good but check this:

0.03X1+0.05X2+0.08X3 ≤ 0.04 multiply by 100 (This is for Phosphorus)

We get: 3X1+ 5X2+ 8X3 ≤ 4

3X1+14X2+ 8X3 ≤ 5 (is for Ash)

X1+ X2+ X3 ≤ 1 this I don't know where this is derived.

Z= 8X1 + 6X2 + 9X3 the objective function is derived from the last column of the table which is then divided by 10 to get the answer.

I would like to know the decision variables and how the constraints and the objective function are derived.
 
Thanks to all of you for your help but i am still stuck. I must say that I am null in Maths and this is a module I am being obliged to do for my university course.

The question is to define how these decisions variables, the objective functions and the constraints are derived.

Please help me!!!!
 
I am assuming that you do not see any purpose of solving this type of problem for your said university course.

In that case, you should ask your instructor about usefulness of such an exercise.

May be you should ask the usefulness of such a course in your career development plan.

May be you need to change the development plan...

But finally it comes down to - if you want the credit (for solving the problem), you must work.

We are here to show you the way - but not do the "whole" work for you.
 
Subhotosh Khan
I am assuming that you do not see any purpose of solving this type of problem for your said university course.

In that case, you should ask your instructor about usefulness of such an exercise.

May be you should ask the usefulness of such a course in your career development plan.

May be you need to change the development plan...

But finally it comes down to - if you want the credit (for solving the problem), you must work.

We are here to show you the way - but not do the "whole" work for you.

I think you have misunterstood me. I am not questioning the usefulness of the exercise. I am saying that I am null in Maths and this module is a tough one for me. The first 2 equations and the objective function, I know where & how they are derived. The 3rd that is X1 + X2 + X3 ≤ 1 is what I don't know where it comes and what it is interpreting. As I said earlier, the 1st equation is from the phosphorus column and the 2nd one from the ash column. Objective function is from the last column.

You see, I have tried the question and all what I want is to confirm if it is good or not and get help for the 3rd equation.

Thanks
 
The 3rd that is X1 + X2 + X3 ≤ 1 is what I don't know where it comes and what it is interpreting.

Thanks

Okay - I misunderstood your intentions.

Before I get there to explaining the equation, please tell me what does X1, X2 and X3 stand for?
 
X1, X2, X3 are the decision variables and they are respectively grade 1, grade 2 and grade 3.
 
Dear Jeffm, the 3rd equation is I don't know where it comes and from which it is derived. Concerning the other 2 equations you makes them in percentage and then you multiply by 10000??

I have understand your view for
X1 is the percentage of Grade 1.

X2 is the percentage of Grade 2.

X3 is the percentage of Grade 3.

But the fact is how do u arrived to the equation of 3 variables then. Bcoz I took all the 3 values in the table of phosphorus to get the 1st equation and all the value of ash for the second equation.
 
Dear Jeffm, the 3rd equation is I don't know where it comes and from which it is derived.
X1+ X2+ X3 ≤ 1

Let's pretend the firm's mixing container can hold 2 tons.

Example A: 1 ton of grade 1, .5 tons grade 2, .5 tons grade 3.
1+.5+.5=2
divide everything by 2 to get:
.5+.25+.25=1
x1+x2+x3=1
They can't overfill the container without messy cleanup/waste so 100% or 1 is max.

Example B: .5 tons grade 1, .5 tons grade 2, .5 tons grade 3
.5+.5+.5<2
divide everything by 2
.25+.25+.25<1
x1+x2+x3<1
In this case they chose to not fill the container for some reason and only mixed up 1.5 tons of coal. This is where the < in ≤ comes from.

We don't know that the container is 2 tons so replace 2 with T. Sounds like you need something like:
A+B+C<=T
A/T+B/T+C/T<=1
x1+x2+x3<=1
Now you fill in the gaps/explanations...
 
Last edited:
Thanks to all of you for helping me. Now I the question follows. I would like to confirm if I have the correct answer.

Question: Use the equality constrains to eliminate the variable X3 from the linear programming problem. State Carefully the revised problem with 2 decision variables.

You remember the equations are: 3X1 + 5X2 + 8X3 ≤ 4 ------- Eqn 1
3X1 + 14X2 + 8X3 ≤ 5 ------- Eqn 2
X1 + X2 + X3 ≤ 1 ------------ Eqn 3
So, in order to eliminate X3, I have solve the equations simultaneously and have come to these answers below:

Eqn 1 - Eqn 2: X2 = 1/9

Eqn 1 - Eqn 3 *8: 5X1 + 3X2 = 4

Eqn 2 - Eqn 3 * 8: 5X1 - 6X2 = 3

Are the new equations correct??
 
Last edited:
Wouldn't X1+ X2+ X3 = 1 make more sense, if it isn't then you could just say Minimize Z= 8X1 + 6X2 + 9X3, OK... X1=X2=X3 = 0, Z=0 MINIMIZED!
 
I'm not sure what the argument here is- I'm coming into this late.

But certainly, since there are three types of coal, this is a three dimensional problem. You could solve this graphically by graphing the planes that form the boundary of the "feasible area'. Those are, of course, the inequalities with the inequality replaced by '='. Then the optimum solution will be a vertex of that region, where more than one of the equations are satisied. Even the more general simplex method does that, abstractly- moving from one vertex, i.e. one equation, to another. I am no expert on Karmakar's method but I believe that does use information from inside the feasible area.
 
So, don't worry I've been able to solve the equation to get 2 decision variables.

The new equations are:

Objective function, Z = 9 - X1 - 3X2

Functional Constraint: 5X1 + 3X2 ≥ 4

-5X1 + 6X2 ≤ -3

X1 + X2 ≤ 1

Now the question is to plot a graph and find the feasible region. I have plot the graph but I am not sure about the feasible region.

Here are the coordinates of my feasible region. I've got 3 feasible corners by the way. A(0.74, 0.1), B(0.84, 1.8), C(0.3, 0.84)

Can somebody tell if its correct and if not inform me about the coordinates of the correct one so that I can check it.

Thanks
 
Top