# Solving a linear programming problem: Are my formulations correct?

QUESTION

J (PTY) LTD is a fertilizer manufacturing enterprise that produces two types of fertilizers, namely white and gray. The white fertilizer is for crops like maize, sorghum, etc while the gray fertilizer is produced for shrubs, plants, etc in the garden.

Both products are produced using the same machines and raw materials (phosphate and ammonia nitrate). The company has a maximum of 600 machine hours and 10,000kg raw materials. The production engineers estimated that one bag of the white fertilizer utilizes 30 minutes of machine time. But the gray fertilizer requires an hour of machine time.

With regard to the raw materials usage, the white fertilizer needs 12.5kg while 10kg is required for the gray fertilizer. Due to the increasing competition from abroad, the marketing department estimated that 700 bags of white fertilizer could be sold for R4 per bag while only 400 bags of the gray one can be sold for R6 per bag.

Formulate a linear programming model for this problem and solve it graphically.

ATTEMPT

Here's a table with the data:

$$\begin{array}{c|ccc} Fertiliser & \text{Raw Materials (kg)} & \text{Machine Time (hrs)} \\ \hline White & 12.5 & 0.5 \\ Gray & 10 & 1.0 \\ \end {array}$$

I begin by trying to figure out what the constraint set could look like:

Let's have $w$ represent the White fertilizer and $g$ represent the gray fertiliser.

I am not entirely sure what the question is but I went ahead and assumed this is a profit maximization problem so the objective function would be:

$$\{max\} P = 4w + 7g$$ Constraints: $$\text{raw materials:} 12.5w + 10g \le 10,000$$ $$\text{machine hours:} 0.5w + 1g \le 600$$

As for the estimation of how many bags could be sold I'm not entirely sure how to convert that into a constraints set. Could it be:

$$w \ge 700 \text{, } g \ge 400$$

I actually don't even think I understand the question.

• So it looks like ... you're going to have to sell at least 700 bags of white and 400 bags of grey? Except you can't do both, because of the constraints. So I'm confused about the question. – Ian Coley Sep 2 '13 at 19:04
• I am so unbelievably confused about this question, too. Maybe I should ask the professor what the question is tomorrow? – Siyanda Sep 2 '13 at 19:19
• Probably. Sorry I can't help you further. – Ian Coley Sep 2 '13 at 19:19

Your objective function should be P = 4W + 6G which will be in units of R, whatever R is, assuming the R4 and R6 you have in the question have been copied correctly. If R represents rupees, then rupees are your units. It doen't really matter. Also, you need $W\le 700$ and $G\le 400$. This is because 'the marketing department estimated that 700 bags of white fertilizer could be sold for R4 per bag while only 400 bags of the gray one can be sold...' The phrase 'only 400 bags could be sold' tells us that 400 is the maximum number of bags that can be sold, hence we know that the number of bags will not be greater that this figure and hence it will be less than or equal to it. This implies that the estimate of 700 bags for W is also an estimate of the maximum number that will be sold. Your other constraints are correct.

Now for phase 2: solving the problem graphically. You can do this with Excel's Solver, which you may be shown later in your course, but it seems that in this question you should draw the graph by hand and solve. It's not difficult, but takes a little time. The method is as follows:

1. Pick any constraint and draw a line on a graph of G against W for the corresponding inequality by converting it to the corresponding equality, and reaaranging to make G or W (whichever is easier) the subject. For example, taking the constraint $12.5W + 10G \le 10000$ we first change this to an equality ($12.5W + 10G = 10000)$ and then make G the subject (since dividing by 10 is easier than dividing by 12.5) and find that $G = -1.25W + 1000$ (let's call this equation 1) from which we can easily draw a line on a graph of G (on the vertical axis) against W (on the horizontal). The G intercept is of course 1000 and by substituting G = 0 into equation 1 we find that the W intercept occurs at $W = 1000/1.25 = 800$. Now we simply connect these 2 points ((0,1000) and (800,0)) with a line. We know that since the inequality was $\le$, our solution must be a point either on or below (and to the left of) this line.

2. Repeat this process for each constraint and you find what's known as the feasible region, within which the maximal solution must occur.

3. Some smart person once proved (we don't have to thankfully) that the maximal solution occurs at one of the vertices of this feasible region i.e. where any 2 of our constraint lines cross. Vertices may also include where a line crosses the G or W axis if such a point is within the feasible region. I think these vertices are never maximal, but I advise you to check this detail with the professor is possible. Until you find out the answerfor sure, you amy want to consider any such vertex/vertices to make sure it isn't/neither of them/none of them are the maximal solution you're looking for.

4. Now all we need to do is find out the coordinates of each vertex, which is done the usual methods for solving a pair of simultaneous linear equations in two variables.

5. Then simply plug the values of G and W at each vertex into the objective function and find out which is the biggest and that's your answer.

I now continue to apply the method outlined in point 1-5 above to your specific problem.

We've found one of the lines we need: ($G = -1.25W + 1000$). Next let's take a look at this constraint: $0.5W + G \le 600$. First we change the $\le$ to = to get the line we need: $0.5W + G = 600$. More easily than in the case of the first constraint this rearranges to $G = -0.5W + 600$. The other 2 constraints are even easier. All we need to do in each case is change the $\le$ to = to get the lines $W = 700$ and $G = 400$.

So the 4 lines we need to draw on the graph are:

1. $G = -1.25W + 1000$
2. $G = -0.5W + 600$.
3. $W = 700$
4. $G = 400$.

I actually found it easier to draw lines 3 and 4 first. After drawing the graph of these lines, it's easy to see that there are 5 vertices that we need to consider as candidate solutions to the problem (actually only 3 I think but just to be sure, I'll consider the point at which line 3 croses the W axis and the point at which line 4 crosses the G axis as well). The other 3 vertices occur when (1) line 2 crosses line 4, (2) when line 1 crosses line 2 and (3) when line 1 crosses line 3. We don't need to consider the point where line 2 crosses line 3 beacuse it's outside of the feasible region.

Now we find the coordinates of the vertices as follows:

(1) We need to find the coordinates at which line 2 crosses line 4. The equation for line 4 tells us that $G = 400$ at the vertex. Since line 2 crosses this point too, we can substitute the value of $G$ at this point which we've just found (400) into the equation for line 2 ($G = -0.5W + 600$) which tells us that $400 = -0.5W + 600$ and so $W = (600-400)/0.5 = 400$, so the vertex has coordinates (400, 400).

(2) At the next vertex line 1 ($G = -1.25W + 1000$) crosses line 2 ($G = -0.5W + 600$), which are thus a pair of simultaneous linear equations in 2 variables (G and W). As such we can subtract the second equation from the first equation to give $0 = -0.75W + 400$ from which we find that $W = 400/0.75 = 533\frac{1}{3}$. Now subsituting this value of W back into the second equation gives $G = (-0.5)533\frac{1}{3} + 600 = 333\frac{1}{3}$ so the second vertex (and our second candidate solution) has coordinates $(533\frac{1}{3}, 333\frac{1}{3})$.

(3) When line 1 crosses line 3, the equation for line 3 tells us straight away that $W = 700$. Sub. this into the equation for line 1 to find $G = -1.25(700) + 1000 = 125$ and so the coordinates of the third vertex are (700, 125).

(4) The point where line 3 crosses the W axis is of course (700 ,0) and

(5) The point where line 4 crosses the G axis is (0, 400)

Finally, we just try each of these 5 points in our objective funtion $P(W,G) = 4W + 6G$ to see which gives the maximum profit as follows:

(1) $P(400, 400) = 4(400) + 6(400) = 1600 + 2400 = 4000$

(2) $P(533\frac{1}{3}, 333\frac{1}{3}) = 4(533\frac{1}{3}) + 6(333\frac{1}{3}) = 2123\frac{1}{3} + 2000 = 4123\frac{1}{3}$.

(3) $P(700, 125) = 4(700) + 6(125) = 2800 + 750 = 3550$.

(4) $P(700, 0)$ is obviously less than (3), so we don't need to compute it.

(5) $P(0, 400)$ is obviously less than (1) so it turns out we only needed to calculate the first 3 after all, of which the maximum is the second vertex $P(533\frac{1}{3}, 333\frac{1}{3}) = 4123\frac{1}{3}$. .

For completeness (and to get all the available marks in coursework and exams) it is important to write the units if you know them (which you generally do in questions like these), so your final answer would be the optimal solution is $P(533\frac{1}{3}, 333\frac{1}{3}) = R4123\frac{1}{3}$ which is $R4123.33$ in practice.

• This unbelievably great, thank you so much! And the R stands for Rands. That's South African currency. Thank you so much. Will work on it from your initial clarifications and compare my answers every step of the way. Thank you again! – Siyanda Sep 3 '13 at 9:34
• No probs. Thanks for the info on Rands. – George Tomlinson Sep 3 '13 at 15:20
• Hey, I worked on this and figured that P = 4w + 6g - was the correct objective function. Ultimately I found (400,400) to be the maximum point for this function. – Siyanda Sep 3 '13 at 20:10
• So are you saying you think there's an error in my answer? – George Tomlinson Sep 4 '13 at 11:01
• Only one mistake - its 4w + 6g not 4g + 6w...*winces* – Siyanda Sep 4 '13 at 11:05