Linear Programming Help (Management Science)

/in /by

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)