ISYE 6669 A,Q Homework #2 Solutions The data from the diet ...

ISYE 6669 A,Q Homework #2 Solutions Due Friday, August 31

1. The data from the diet problem we saw in class is available at

In this diet problem, our objective was to minimize the total cost of our food while satisfying certain nutritional constraints.

The optimal solution is a diet of raw carrots, peanut butter, air-popped popcorn, baked potatoes, and skim milk. UGH!

Suppose that you, like me, wouldn't be satisfied with a diet of these 5 foods, and you would be willing to spend up to $5.00/day to get the tastiest meal possible that still satisfied the nutritional constraints.

(a) Describe how you would modify the model so that it would give you a tasty diet (the tastiest diet available that satisfies the nutritional constraints and costs less than $5.00). Include any additions, deletions, or changes to the set of variables and constraints, and be sure to describe how you would quantify the notion of "tastiness", as well as how you would incorporate it into the model.

There's more than one way to solve this problem. Here's one method.

Instead of having j cjxj as the objective function, make it a constraint: j cjxj 5. That ensures a daily cost of no more than $5. Now, define tj

to be the "tastiness" of food j. This number will just be your own opinion of each food. The objective can now be written as "maximze

j tjxj" to maximize tastiness.

You might also think that variety is important. So, you might pick groups of foods, and require that you eat at least something from that group. For example, let C be the set of all breakfast cereals. You

might include a constraint that said jC xj 1, meaning that the

total cereal you eat must be at least one serving.

(b) In the original model, everyone's optimal diet was the same when all foods were eligible. In the new model you have created in part (a), will everyone's optimal diet still be the same? Why or why not?

Because everyone has a different idea of what's tasty and what isn't, the optimal diets won't be the same. Everyone will have different values for tj, so a diet that one person thinks is tasty might not be appreciated by someone else.

(c) Do you expect that your changes in part (a) will increase the number of

foods recommended each day, decrease the number of foods recommended

each day, or keep them about the same? Why? (Note ? you may want to wait until after Wednesday August 29th's class to answer this part of the

problem.)

Remember, we'll have at most one positive variable in the optimal solution for each constraint in the formulation. So, if we add one or more constraints, we might add positive variables as well. So, the number of foods might go up.

2. Artificial Heart Valve Production. Problem #2, Page 73.

Variables: xj = amount of valves ordered from supplier j Minimize 5 x1 + 4 x2 + 3 x3

Subject to

0.4 x1 + 0.3 x2 + 0.2 x3 500 0.4 x1 + 0.35 x2 + 0.2 x3 300 0.2 x1 + 0.35 x2 + 0.6 x3 300

(buy enough large valves) (buy enough med. valves) (buy enough small valves)

x1 500 x2 500 x3 500

(each supplier can supply at most 500 valves each month)

x1, x2, x3 0 (nonnegativity)

3. Minnesota Brass, Inc. (MBI) manufactures musical instruments. Specifically, they make bugles, mellophones, baritones, and contrabasses. Each of the four types of instruments can be silver-plated or chrome-plated.

The base materials needed in the manufacturing process cost $100 for bugles, $200 for mellophones, $400 for baritones, and $800 for contrabasses. Chrome plating costs $20 for each type of instrument, and silver plating costs $200 for each type of instrument.

To meet demand, MBI must manufacture a total of 100 small instruments (bugles and mellophones) and 50 large instruments (baritones and contrabasses). At least 50% of all instruments manufactured must be silver-plated.

(a) Formulate a linear programming model that MBI can use to minimize the cost of its production while obeying its demand and silver-plating restrictions. Be sure to clearly indicate what your variables, objective function, and constraints are. You do not need to include a restriction that your variables must be integers.

Variables: Ci = number of chrome instruments of type i made Si = number of silver instruments of type i made

(for both variables, i {b,m,a,c} where b = bugles, m = mellophones, a = baritones, and c = contrabasses)

Minimize i 20 Ci + i 200 Si + 100 (Cb + Sb) + 200 (Cm + Sm) + 400 (Ca +

Sa) + 800 (Cc + Sc)

Subject to

Cb + Sb + Cm + Sm 100 Ca + Sa + Cc + Sc 50

i Si (i Si + i Ci)

(small instrument minimum) (large instrument minimum) (silver instrument minimum)

Si, Ci 0 for all i

(nonnegativity)

(b) Since the model in part (a) does not restrict variables to be integers, you might end up with a fractional solution. Do you think that rounding off the solution to the nearest integer would be acceptable? Why or why not?

Because the numbers are so big, rounding off isn't a major problem. The numbers aren't entirely certain anyway ? for example, it's not definite that you'll sell exactly 100 small instruments, so if you happen to manufacture 101 or 99 it won't make much difference.

4. Gasoline Production Planning. Problem #14, Page 93. (Formulation only ? do not solve.)

(a) Formulate the problem using the given data.

Variables: xkj = amount of input k used to make product j (k {r,f,i,p,m,b} (reformate, FCG, ISO, POL, MTB, BUT) and j {r,p} (regular, premium)

Maximize [29.49 ? 8.5(0.15/0.1)] k xkr + [31.43 ? 8.5(0.15/0.1)] k xkp

Subject to

98.9 xrr + 93.2 xfr + 86.1 xir + 97 xpr + 117 xmr + 98 xbr 90 (xrr + xfr + xir + xpr + xmr + xbr) (RON minimum for regular)

98.9 xrp + 93.2 xfp + 86.1 xip + 97 xpp + 117 xmp + 98 xbp 96 (xrp + xfp + xip + xpp + xmp + xbp) (RON minimum for premium)

?5 xrr + 57 xfr + 107 xir + 7 xpr + 98 xmr + 130 xbr 10 (xrr + xfr + xir + xpr + xmr + xbr) (ASTM70 minimum for regular)

?5 xrp + 57 xfp + 107 xip + 7 xpp + 98 xmp + 130 xbp 10 (xrp + xfp + xip + xpp + xmp + xbp) (ASTM70 minimum for premium)

46 xrr + 103 xfr + 100 xir + 73 xpr + 100 xmr + 100 xbr 10 (xrr + xfr + xir + xpr + xmr + xbr) (ASTM130 minimum for regular)

46 xrp + 103 xfp + 100 xip + 73 xpp + 100 xmp + 100 xbp 10 (xrp + xfp + xip + xpp + xmp + xbp) (ASTM130 minimum for premium)

7.66 xrr + 9.78 xfr + 29.52 xir + 14.51 xpr + 13.45 xmr + 166.99 xbr 21.18 (xrr + xfr + xir + xpr + xmr + xbr) (RVP maximum for regular)

7.66 xrp + 9.78 xfp + 29.52 xip + 14.51 xpp + 13.45 xmp + 166.99 xbp 21.18 (xrp + xfp + xip + xpp + xmp + xbp) (RVP maximum for premium)

xfr 0.38(xrr + xfr + xir + xpr + xmr + xbr) (FCG min. for reg.) xfp 0.38(xrp + xfp + xip + xpp + xmp + xbp) (FCG min. for prem.)

xrr + xfr + xir + xpr + xmr + xbr 9800

(regular demand)

xrp + xfp + xip + xpp + xmp + xbp 30000 (premium demand)

xrr + xrp 15572 xfr + xfp 15434 xir + xip 6709 xpr + xpp 1190 xmr + xmp 748

(reformate avail.) (FCG avail.) (ISO avail.) (POL avail.) (MTB avail.)

All xkj 0

(nonnegativity)

Note that there are no variables for the total amounts of each input used, or for the total amounts of each product made. We could include those variables ? for example, we could have the variable yr = amount of regular gasoline produced. This variable would make all of the regular gasoline constraints, and the regular gasoline part of the objective function, easier to write. We would need to add an extra constraint, that yr = xrr + xfr + xir + xpr + xmr + xbr, if we added this extra variable.

Also, note that there is no availability constraint for BUT, because there is an unlimited supply.

(b) Formulate the problem algebraically, specifying the notation for each piece of data. For example, pi might be your notation for the selling price of gasoline type i.

Data: Variables:

pj = selling price per liter of gasoline type j cj = cost per liter of removing lead from gasoline type j dj = demand (in liters) of gasoline type j sk = availability (in liters) of input type k aik = value of attribute i in input type k

(for example, aRON,FCG = 93.2) lij = minimum (lower bound) of attribute i in product j

(for example, lRON,regular = 90) uij = maximum (upper bound) of attribute i in product j (Note: lij = ?infinity if there is no minimum, and uij =

infinity if there is no maximum.) fj = maximum FCG in gasoline type j

xkj = amount of input k used to make product j

Maximize j (pj ? cj) k xkj

Subject to

k aik xkj lij k xkj for all i, j k aik xkj uij k xkj for all i, j xFCG,j fj k xkj for all j k xkj dj for all j j xkj sk for all k

(attribute minima) (attribute maxima) (FCG maxima) (demands) (availabilities)

xkj 0 for all k, j (c) Which was easier to write, (a) or (b)?

(nonnegativity)

The formulation of part (b) seems much easier to write! It takes 8 lines instead of a whole page.

(Note ? this was an opinion question, so if you answered that (a) was easier, you still got full credit for your answer. However, once you get used to it, (b) really is much easier (trust me... in a real-life situation you might have hundreds of inputs and hundreds of products, and if you tried writing it down like (a) you'd be writing for hours!), so I'd like you to know how to do both (a) and (b).)

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download