# Linear Programming Help (Management Science)

## EC Problem Listing

All of the problems described below are taken from the 4th edition of a McGraw-Hill text entitled “Operations Management,” authored by Stevenson and Ozgur. | ||

This was the text formerly used for instruction in BMDS3371 until it went out of print in early 2013. | ||

EC Problem #1 | ||

Aviation Electronics produces three types of switching devices. Each type involves a two-step assembly operation. The assembly times are shown in the table below. | ||

Assembly Time per Unit | ||

Station #1 | Station #2 | |

Model A | 2.5 minutes | 3.0 minutes |

Model B | 1.8 minutes | 1.6 minutes |

Model C | 2.0 minutes | 2.2 minutes |

Each workstation has a daily working time of 7.5 hours. Manager Bob Parkes wants to obtain the greatest possible profit during the next five working days. Model A | ||

yields a profit of $8.25 per unit, Model B a profit of $7.50 per unit, and Model C a profit of $7.80 per unit. Assume the firm can sell all it produces during this time but it | ||

must fill outstanding orders for 20 units of each model type. | ||

Formulate the linear programming model of this problem. Solve the model to show the maximum amount of profit possible given the constraints outlined above. | ||

EC Problem #2 | ||

A farm consists of 600 acres of land, of which 500 acres will be planted with corn, soybeans, and wheat, according to these conditions: | ||

a.) At least half of the planted acreage should be in corn. | ||

b.) No more than 200 acres should be soybeans. | ||

c.) The ratio of corn to wheat planted should be 2:1. | ||

It costs $20 an acre to plant corn, $15 an acre to plant soybeans, and $12 an acre to plant wheat. | ||

Formulate this problem as an LP model that will minimize planting cost while achieving the specified conditions. | ||

EC Problem #3 | ||

Reproduce the LP model needed for #2 above but modify it to reflect the need to plant at least 500 acres. | ||

EC Problem #4 | ||

A high school dietician is planning menus for the upcoming month. A new item will be spaghetti with sauce. The dietician wants each serving to contain at least | ||

10 grams of protein and at least 40 grams of carbohydrates. Spaghetti contains 5 grams of protein and 32 grams of carbohydrates per cup, and the sauce contains | ||

4 grams of protein and 5 grams of carbohydrates per cup. For aesthetic reasons, the dietician wants the ratio of spaghetti to sauce to be 4:1. | ||

Spaghetti costs $0.30 per cup to buy and prepare, the sauce costs $0.40 per cup to buy and prepare. The dietician wants to minimize the cost per serving and keep | ||

the calories per serving to 330 or less. The sauce contains 100 calories per cup, and the spaghetti contains 160 calories per cup. | ||

Formulate a linear programming model that will minimize the cost per serving subject to the various constraints decribed above. |

## EC Problem #1 – Set Up

Assembly Time per Unit (minutes) | Profit per Unit | ||||

Station 1 | Station 2 | ||||

Model A | 2.5 | 3.0 | $ 8.25 | NOTE 1: As I start to set-up these spreadsheets, I ofen find it helpful to a.) repeat key information | |

Model B | 1.8 | 1.6 | $ 7.50 | from the problem AND format it in a way that will allow me to understand/remember what the heck | |

Model C | 2.0 | 2.2 | $ 7.80 | the numbers mean. So you will see that I have added labels wherever possible. | |

Total | 6.3 | 6.8 | This is for my benefit. Solver doesn’t really care one way or the other. | ||

Work Time Available | 2250 | 2250 | NOTE 2: As I start to set-up these spreadsheets, I ALWAYS keep in mind that Solver (or any other | ||

(per week) | LP) will ask me four types of questions. The first is to choose a target cell…the objective function. | ||||

In this case, my target is cell D21. See the formula inside that cell? Before you move on to the next | |||||

Work Time Used | 0 | 0 | problem, it is my sincerest hope that you understand how and why I placed this formula in this cell. | ||

(per week) | The second thing Solver will ask for is the choice of maximizing or minimizing. (Right?) | ||||

Yes, it might also ask if we want to set the objective function to a specific value…but we need not | |||||

Optimal Production Values | Totals | worry about this for these problems. The third question Solver will ask is “which cells/values shall we | |||

Station 1 | Station 2 | change?” to get our optimal solution. In this case, I’ve set-up the spreadsheet so that the cells | |||

Model A | 0.00 | 0.00 | 0.00 | to be changed are those from B16 to C18 (in yellow shaded area). | |

Model B | 0.00 | 0.00 | 0.00 | ||

Model C | 0.00 | 0.00 | 0.00 | NOTE 3: The last question that Solver will ask is one about the constraints required by the problem. | |

Some of these will be VERY easy to get Solver to digest. Some, however, will require a bit of | |||||

Total Profit | extra foresight/planning. I begin by listing the constraints below (see Cells A23 through A31). | ||||

$ – 0 | This listing is for my own benefit, sort of like a mental checklist I use to make sure that I have given | ||||

Solver all needed constraints. Let’s consider an “easy” constraint such as X1 >=20. Given the way | |||||

Define: Model A = X1, Model B = X2, Model C = X3 | I have set this spreadsheet up, I’ll tell Solver that the value in Cell D16 must be greater than or | ||||

Maximize: z= 8.25X1 + 7.50X2 + 7.80X3 | equal to 20. Do you see why I picked this cell and understand the formula I have placed within it? | ||||

Constraints: | Now, how to tackle a more complicated constraint such as either of the first two on the list? Well, | ||||

#1–2.5X1 + 1.8X2 + 2.0X3 <= 2,250 minutes | I had to think a little about this but decided to make use of formulas in Cells B11 (Constraint #1) | ||||

#2–3.0X1 + 1.6X2 + 2.2X3 <= 2,250 minutes | and C11 (Constraint #2). Take a close look at the formula in either of these cells (please). | ||||

#3–X1 >= 20 | Do they make sense to you? I’ll ask Solver to set B11 less than or equal to 2,250…and, in so | ||||

#4–X2 >= 20 | doing, will have tackled Constraint #1. I’ll do likewise with C11 to tackle Constraint #2. | ||||

#5–X3 >= 20 | |||||

X1, X2, X3 >= 0 | Ahem, given #3, 4, and 5, we don’t really have to worry about | NOTE 4: Please be advised that the approach I have given here is one of countless formats | |||

these non-negativity constraints. Right? | that could work. There is no one way to do these. I just thought I would share my approach as one | ||||

that I’ve found particularly helpful in prior terms/years when assisting students who have | |||||

no prior experience with linear programming. |

## EC Problem #2 – Set Up

Planting Costs | Amounts Planted | Amounts Spent | NOTE 1: So again, please notice that I began this set-up with a repeat of key info from the problem AND | |||

(per acre) | placed labels wherever I thought they’d be helpful (to my eye and mind). | |||||

X1 (corn) | $ 20.00 | $ – 0 | ||||

X2 (soybeans) | $ 15.00 | $ – 0 | NOTE 2: My target cell will be D6. The formula inside it is, essentially, the objective function (same as Row 12). | |||

X3 (wheat) | $ 12.00 | $ – 0 | Right? We will want to minimize these costs. | |||

Total | 0 | $ – 0 | ||||

NOTE 3: Now which cells/values will I ask Solver to “change”? Yep, C3 to C5. | ||||||

NOTE 4: How about the constraints? Well, these are a little trickier than Problem #2. Let’s start | ||||||

Part A | with the easier ones first. Constraint #3…I’ll ask Solver to make sure that the value in Cell C3 is greater than or | |||||

Define: Corn = X1, Soybeans B = X2, Wheat = X3 | equal to 250 acres. Constraint #4…I’ll ask Solver to make sure that the value in Cell C4 is less than or equal | |||||

Minimize: z= 20X1 + 15X2 + 12X3 | to 200 acres. Then I will add that the value in Cell C4 must be greater than or equal to zero and likewise for | |||||

Constraints: | the value in Cell C5. Let’s tackle Constraint #1 next. I’ll do this by asking Solver to set the value in Cell C6 | |||||

#1–X1 + X2 + X3 = 500 acres | exactly equal to 500 (acres). Right? Now, don’t answer too quickly please. First look at the formula I have | |||||

#2–X1 – 2X3 = 0 | 0 | 0 | 0 | placed in Cell C6. Make sense? | ||

#3–X1 >= 250 | ||||||

#4–X2 <= 200 | NOTE 5: The trickiest part of this set-up is, no doubt, how to get Solver to recognize the second constraint. | |||||

#5–X1, X2, X3 >= 0 | Again, there is more than one way to accomplish this goal. Here, I have broken the constraint up into | |||||

three parts. The first of these is “X1″…see Cell B15. The next is “-2X3″…see Cell C15. Now, look closely | ||||||

Ahem, X1>=0 is one non-negativity constraint that we won’t bother with. | at the formula I have placed in Cell D15. Summing B15 and C15 is my way of teaching you this approach AND | |||||

Do you see why? It is because we will have covered this base when we | getting Solver to do its magic. I’ll ask Solver to set this value equal to Zero. Yes? | |||||

get Solver to recognize/digest Constraint #3. |

## EC Problem #3 – Set Up

Planting Costs | Amounts Planted | Amounts Spent | NOTE 1: I intentionally decided not to place too many notes here. | ||

(per acre) | I am hopeful that my set-up here and notes from the prior worksheet | ||||

X1 (corn) | $ 20.00 | $ – 0 | allow you to understand most/all of what I have done here. | ||

X2 (soybeans) | $ 15.00 | $ – 0 | |||

X3 (wheat) | $ 12.00 | $ – 0 | |||

Total | 0 | $ – 0 | |||

Part B | |||||

Define: Corn = X1, Soybeans B = X2, Wheat = X3 | |||||

Minimize: z= 20X1 + 15X2 + 12X3 | |||||

Constraints: | |||||

#1–X1 + X2 + X3 >= 500 acres | |||||

#2–X1 + X2 + X3 <= 600 acres | |||||

#3–X1 – 2X3 = 0 | 0 | 0 | 0 | ||

#4–X1 – X2 – X3 >= 0 | 0 | NOTE 2: This is an added constraint which says at least of half of planted areage | |||

#5–X2 <= 200 | must be corn. X1 >= (X1 + X2 + X3)/2 (Does my math make sense to you?) | ||||

#6–X1, X2, X3 >= 0 | We multiply both sides by two. So 2 X1 >= (X1 + X2 + X3) | ||||

Then subtract X1 from both sides. So X1 >= X2 + X3 | |||||

Then subtract X2 and X3 from both sides. So X1 – X2 – X3 >= 0 | |||||

NOTE 3: We see a very interesting (some might say counterintuitive) result here… | |||||

as we compare this output to that which was obtained in Part A. Remember, | |||||

the difference between these two parts mainly involves the ability to plant | |||||

more crops. So one might initially expect larger values in the optimal solution. | |||||

Can you see why this actually isn’t the case here? |

## EC Problem #4 – Set Up

Cost to Prepare | Amounts | Total Cost | NOTE 1: No notes. Please look at what I have done here and let me know | ||

(per cup) | Prepared | (per serving) | what does and /or does NOT make sense to you? | ||

X1 – Spaghetti | $ 0.30 | 0.00 | $ – 0 | ||

X2 – Sauce | $ 0.40 | 0.00 | $ – 0 | ||

Total | $ 0.70 | 0.00 | $ – 0 | ||

Define: Spaghetti = X1, Sauce= X2 | |||||

Minimize: z= .3X1 + .4X2 | |||||

Constraints: | |||||

#1–5X1 + 4X2 >= 10 grams of protein (per serving) | 0.00 | 0.00 | 0 | So each serving will have ?? grams of protein and | |

#2–32X1 + 5X2 >= 40 carbohydrates (per serving) | 0.00 | 0.00 | 0.00 | each serving will have ??.?? carbs and | |

#3–X1 – 4X2 = 0 (not too much sauce per serving) | 0.00 | 0.00 | 0 | a spaghetti to sauce ratio of ?:? and | |

#4–160X1 + 100X2 <= 330 calories (per serving) | 0.00 | 0.00 | 0.00 | ???.?? calories per serving. | |

#5–X1, X2 >= 0 (all values must be non-negative) |