How Should the Company Allocate Machine Hours to Minimize Costs?

[fishturtle1]

Homework Statement

A company has three machines to make units of A. Input and output data for 1 hr of operation of each machine are as follows:
Input / Input / Output
Raw Material (lb) / Labor(worker-hrs) / units of A
Machine 1: 80 / 16 / 37
Machine 2: 50 / 35 / 43
Machine 3: 76 / 33 / 52

The company must produce 2000 units of A weekly. The company can purchase up to 1 ton of the raw material for $4/lb from one source and an unlimited amount from another source for $5.50 / lb. The firm was 900 hr of labor available at $8/hr, and an additional 200 hr of overtime available at $12/hr. The company pays only for the labor and raw material it uses. How many hours could each machine be used to meet demands at minimum cost?
Set up the problem but do not solve.

Homework Equations

The Attempt at a Solution

Let Machine 1 = X, Machine 2 = Y, and Machine 3 = Z

So to deal with raw materials: $80X + 50Y + 76Z - t \le 2,000$
where t is the amount bought for $5.50/lb.

To deal with the labor hours: $16X + 35Y + 33Z + s \le 1100$
and $s \le 200$
and $16X + 35Y + 33Z \le 900$

we also need 2000 units of A: $37X + 43Y + 52Z = 2000$

minimize: $4(80X + 50Y + 76Z) + 5.50t + 8(16X + 35Y + 33Z) + 12s$

i'm not really sure I did the raw materials right.. Is it enough to say "where t is the amount bought for $5.50" ?

 

[mfb]

You'll probably have to distinguish the different cases (more expensive material/labor needed yes or no). At least you have to add $t \geq 0$ and $s \geq 0$, and if they are zero, then you also have to take the cheaper labor/raw material cost into account.

 

[fishturtle1]

You'll probably have to distinguish the different cases (more expensive material/labor needed yes or no). At least you have to add $t \geq 0$ and $s \geq 0$, and if they are zero, then you also have to take the cheaper labor/raw material cost into account.

Thanks for the reply.

I undersand and agree that I need to set $s,t \ge 0$.. in addition I set $X,Y,Z \ge 0$.

Here is my rewritten answer based on cases(I think this is what you meant by cases):

$s,t,X,Y,Z \ge 0$

let TRM = total raw materials.
case 1:
if TRM > 2000, then $80X + 50Y + 76Z - t = 2000$. Let $C_{1a}$ be the price of the raw materials. So $C_{1a} = 4(2000) + 5.50(t)$.

case 2:
if TRM $\le 2000$, then $80X + 50Y + 76Z \le 2000$. Let $C_{1b}$ be the price of raw materials. So $C_{1b} = 4(80X + 50Y + 76Z)$

Similarly, we consider two cases for the cost of labor.
let TLH = total labour hours
case 1:
if 900 < TLH $\le$ 1100, then $16X + 35Y + 33Z - s = 900$, let $C_{2a}$ be the price of labor, so $C_{2a} = 8(900) + 12(s)$

case 2:
if TLH $\le$ 900, then $16X + 35Y + 33Z \le 900$, let $C_{2b}$ be the price of labor, so $C_{2b} = (16X + 35Y + 33Z)900$

Our objective function is $37X + 43Y + 52Z = 2000$.

So I guess we would have 4 lines to graph: C = $C_{1a}$ + $C_{2a}$, C = $C_{1a}$ + $C_{2b}$, C = $C_{1b}$ + $C_{2a}$,
C = $C_{1b}$ + $C_{2b}$.

If I were to solve this I would graph these 4 equations and see where they intersect with $37X + 43Y + 52Z = 2000$, then see which one has the lowest cost.

 

[FactChecker]

What class is this for? It seems like it might be an application of the Simplex method of Linear Programming. Is the Simplex method part of your course?

 

[fishturtle1]

What class is this for? It seems like it might be an application of the Simplex method of Linear Programming. Is the Simplex method part of your course?

Its for linear programming and yes simplex method is in the next chapter

 

[Ray Vickson]

Homework Statement

A company has three machines to make units of A. Input and output data for 1 hr of operation of each machine are as follows:
Input / Input / Output
Raw Material (lb) / Labor(worker-hrs) / units of A
Machine 1: 80 / 16 / 37
Machine 2: 50 / 35 / 43
Machine 3: 76 / 33 / 52

The company must produce 2000 units of A weekly. The company can purchase up to 1 ton of the raw material for $4/lb from one source and an unlimited amount from another source for $5.50 / lb. The firm was 900 hr of labor available at $8/hr, and an additional 200 hr of overtime available at $12/hr. The company pays only for the labor and raw material it uses. How many hours could each machine be used to meet demands at minimum cost?
Set up the problem but do not solve.

Homework Equations

The Attempt at a Solution

Let Machine 1 = X, Machine 2 = Y, and Machine 3 = Z

So to deal with raw materials: $80X + 50Y + 76Z - t \le 2,000$
where t is the amount bought for $5.50/lb.

To deal with the labor hours: $16X + 35Y + 33Z + s \le 1100$
and $s \le 200$
and $16X + 35Y + 33Z \le 900$

we also need 2000 units of A: $37X + 43Y + 52Z = 2000$

minimize: $4(80X + 50Y + 76Z) + 5.50t + 8(16X + 35Y + 33Z) + 12s$

i'm not really sure I did the raw materials right.. Is it enough to say "where t is the amount bought for $5.50" ?

Back when I was teaching this material I always stressed the importance of using sensible variable names; for example, if we want to know the numbers of tables, chairs and desks to produce it is much better to use names like Table, Chair, Desk (or T,C,D) instead of X1,X2,X3---especially if we want to product a "management report" recommending a policy. Basically, use $x_1, x_2, x_3$ or $x,y,z$ when discussing how the simplex method works, for example, but not when doing an actual model.

Anyway, if I were doing this problem I would use variable names like H1, H2, H3 = hours of production on machines 1,2,3, O = overtime hours used, S2 = lbs. of extra material purchased from supplier 2. Note that I would also include the units of measurement, and would subtract marks from any student that did not do that--- so just saying "H1 = machine 1", etc, would be classified as useless. Then I would get a formulation like yours, but I would not forget to include the all-important restrictions H1, H2, H3, O, S2 >= 0.

BTW: minimization of cost will automatically guarantee that no overtime will be used before all regular time is used up, and nothing is purchased from supplier 2 until the whole amount from suppler 1 is used up. (You should think about why that happens.)

 

[FactChecker]

BTW: minimization of cost will automatically guarantee that no overtime will be used before all regular time is used up, and nothing is purchased from supplier 2 until the whole amount from suppler 1 is used up. (You should think about why that happens.)

Good point. So both regular time and overtime can be put into the same Simplex problem, with a constraint on regular time. The Simplex algorithm will automatically do what is needed to optimize -- only include overtime if the regular time is used up. There is no need for separate cases. Same for suppliers.

The recommendation of meaningful variable names is also good.

But if this problem is intended to be done by hand without the simplex method in the next chapter, I don't know what the best approach would be.

 

[mfb]

BTW: minimization of cost will automatically guarantee that no overtime will be used before all regular time is used up, and nothing is purchased from supplier 2 until the whole amount from suppler 1 is used up. (You should think about why that happens.)

That is included in the cases already.
If you can use a computer algorithm that takes care of these cases automatically: even better.

 

[Ray Vickson]

Good point. So both regular time and overtime can be put into the same Simplex problem, with a constraint on regular time. The Simplex algorithm will automatically do what is needed to optimize -- only include overtime if the regular time is used up. There is no need for separate cases. Same for suppliers.

The recommendation of meaningful variable names is also good.

But if this problem is intended to be done by hand without the simplex method in the next chapter, I don't know what the best approach would be.

The OP was told to formulate it, not solve it. If you need a solution you can just put it into a spreadsheet and use a Solver tool. For example, the EXCEL Solver can handle linear programming problems having perhaps about 200 variables and 100 constraints. You can also have upper bounds on all the variables, which would amount to 300 constraints altogether (100 "functional" constraints and 200 bounds).

 

[fishturtle1]

Back when I was teaching this material I always stressed the importance of using sensible variable names; for example, if we want to know the numbers of tables, chairs and desks to produce it is much better to use names like Table, Chair, Desk (or T,C,D) instead of X1,X2,X3---especially if we want to product a "management report" recommending a policy. Basically, use $x_1, x_2, x_3$ or $x,y,z$ when discussing how the simplex method works, for example, but not when doing an actual model.

Anyway, if I were doing this problem I would use variable names like H1, H2, H3 = hours of production on machines 1,2,3, O = overtime hours used, S2 = lbs. of extra material purchased from supplier 2. Note that I would also include the units of measurement, and would subtract marks from any student that did not do that--- so just saying "H1 = machine 1", etc, would be classified as useless. Then I would get a formulation like yours, but I would not forget to include the all-important restrictions H1, H2, H3, O, S2 >= 0.

BTW: minimization of cost will automatically guarantee that no overtime will be used before all regular time is used up, and nothing is purchased from supplier 2 until the whole amount from suppler 1 is used up. (You should think about why that happens.)

Going forward i'll try to be more thoughtful about my variable names. And I'll make sure to set my variables greater than or equal to 0.

Your last paragraph does make sense.. if I can buy some item A from two sellers, Seller 1 sells A for $5 and Seller 2 sells A for 3$, then I would buy from Seller 2 until that is no longer an option, and then i'd switch to Seller 1.

So from this thread I understand that in these problems, they want us to think about using the cheapest option until that option is no longer available; the use of cases makes setting up the problem easier than what I was trying to do..

Thank you to everyone who commented on this thread.

 

[Ray Vickson]

Going forward i'll try to be more thoughtful about my variable names. And I'll make sure to set my variables greater than or equal to 0.

Your last paragraph does make sense.. if I can buy some item A from two sellers, Seller 1 sells A for $5 and Seller 2 sells A for 3$, then I would buy from Seller 2 until that is no longer an option, and then i'd switch to Seller 1.

So from this thread I understand that in these problems, they want us to think about using the cheapest option until that option is no longer available; the use of cases makes setting up the problem easier than what I was trying to do..

Thank you to everyone who commented on this thread.

No: your use of "cases" makes everything more complicated than it needs to be. The optimization (if formulated with care) automatically takes care of using the cheaper before the more expensive. That is, the minimization will take care of the "cases" aspect for you.

 

[fishturtle1]

I'm confused..

I just reread a similar example in the book, and it does use cases. It minimizes one equation that considers overtime, and minimizes another equation that does not consider overtime and then says we're done.

I hear you when you say the Simplex Method will make these problems simpler and takes away the need for cases, but are you saying that I should not use cases at all? or that there will come a time when I can use the Simplex Method instead of cases?

edit: I think your point is that use of cases is a complicated way of setting up a problem because the simplex method can use a simpler model because it automatically considers the cases. And so using cases may be right without the simplex method, but next chapter I won't have a need for the cases.

 

[FactChecker]

I'm confused..

I just reread a similar example in the book, and it does use cases. It minimizes one equation that considers overtime, and minimizes another equation that does not consider overtime and then says we're done.

I hear you when you say the Simplex Method will make these problems simpler and takes away the need for cases, but are you saying that I should not use cases at all? or that there will come a time when I can use the Simplex Method instead of cases?

edit: I think your point is that use of cases is a complicated way of setting up a problem because the simplex method can use a simpler model. And so using cases may be right without the simplex method, but next chapter I won't have a need for the cases.

If considering cases helps you understand, then ok. But it's good if you realize that the separate cases are part of a combined optimization problem. In this example, the cases will give feasible solutions where an optimization algorithm can smoothly go from one case to another, lead by the need to improve the solution. Some problems have different cases which are better to considered alone, each giving its optimal solution that must be compared to the other case optimums to get the global optimum. But in this example, all cases are just different parts of a larger convex solution space.

 

[fishturtle1]

If considering cases helps you understand, then ok. But it's good if you realize that the separate cases are part of a combined optimization problem. In this example, the cases will give feasible solutions where an optimization algorithm can smoothly go from one case to another, lead by the need to improve the solution. Some problems have different cases which are better to considered alone, each giving its optimal solution that must be compared to the other case optimums to get the global optimum. But in this example, all cases are just different parts of a larger convex solution space.

Ok i got it, Thank you.

 

[Ray Vickson]

Ok i got it, Thank you.

I realize now that you and I might really be saying the same thing in different ways. What I meant when I said that you can ignore cases is: the model will take care of the different cases for you. However, as FactChecker has pointed out, looking at the different cases may be helpful to you when trying to understand why the model "works".

To bring the discussion down to earth, let's look specifically at your current problem, and the issue of handling overtime labor (the same issue as we get when handling extra material from supplier 2). If the production-related decision variables are Hi = hours on machine i for i = 1,2,3, then
L (=labor hours used) = 16 H1 + 35 H2 + 33 H3, and the labor constraint says that L <= 900 + O, where O = overtime labor hours used. Overtime costs more than regular time, so there will be a penalty of some type for using O; that is, there will be a term $c_o O$ in the cost objective, where $c_o > 0$ is the overtime penalty.

I claim that the different cases that can arise are treated automatically in the optimization. To see this, let us look at cases.

(1) L <= 900 (so overtime is not needed---but still usable). For example, if L = 800 the constraint reads as 800 <= 900 + O. If O > 0 here, we could not possibly have an optimal solution, because reducing O to zero keeps feasibility of the policy but has a cheaper objective. So, when we don't need overtime, the model will not use overtime in an optimal solution. (Of course, non-optimal solutions could use less than full regular time while simultaneously using some overtime, so feasible solutions need not follow the no-overtime restriction.)

(2) L > 900. For example, suppose L = 975. Now the labor constraint reads as 975 <= 900 + O, and we absolutely need O > 0 now. However, we do not need to have and O larger than 75, and when we minimize cost we will get O = 75 at the optimum. (Again, though, non-optimal solutions may fail to use the best possible combinations.)

So, looking at different cases may assist you in understanding why the model works, but the model does not need to consider separate cases. That is, we don't need to do separate runs of Model 1 (no overtime) and Model 2 (use overtime) ; just a single run of the appropriate combined" model is all you need.

Similar remarks apply to the issue of ordering extra material from the more expensive supplier.