linear programming problem solving

Question

I have written in lp solve and obtain the solution of 0.58 highqualitymeat and 0.41 lowqualitymeat

the thing that confuses is doing it through a graph as: let x be high quality meat and y be low quality meat

we will have a standard constraint : x + y = 1 and the fat constraint of 0.2x + 0.32y <= 25

when we try to do x = 0 then y = 0.78 which doesn't make sense to me because 0.78 will still have 32% fat so x can not be 0 in the graph as the low quality(y) meat has to be mixed with high quality meat (x) to be lowered down

also is there a easy way of finding the ratio of the meats to obtain the 0.25% fat other than trial and error

thanks

Answer 1

So you want to:

Minimise cost = $80 x + 60 y$

such that

$x + y = 1$

$20 x + 32 y <= 25$

Let's consider to start with the more usual constraint $x + y <= 1$. In theory a burger could contain some other material as filler.

Then the graph required should consist of the two lines $x+y=1$ and $20x+32y=25$. The feasible region is the region bounded by the lines and the x-axis and y-axis. This quadrilateral has the following vertices:

$(0, 0)$

$(1, 0)$

$(0, 0.78125)$

$(\frac 7 {12}, \frac 5 {12})$

This last vertex is found by solving simultaneously the equations $x + y = 1$ and $20 x + 32 y <= 25$, which I think answers your question about trial and error.

In Linear Programming, we have the fact that the objective function (in this case the cost) is a maximum or a minimum at one of the vertices of the feasible region.

You therefore have to work out $80x+60y$ at each of the four vertices above to find which is the minimum cost.

Of course this yields the useless answer $(0, 0)$, which achieves a minimum cost of 0 p by including no meat at all!

So here is where we return to the constraint $x+y=1$ rather than the inequality we had earlier. This changes the feasible region from a quadrilateral to a straight line segment from $(1, 0)$ to $(\frac 7 {12}, \frac 5 {12})$. There are now just two vertices to consider.

At $(1,0)$ the cost is 80 p.

At $(\frac 7 {12}, \frac 5 {12})$ the cost is $\frac {560} {12} + \frac {300} {12} = \frac {860} {12} = 71.67$ p.