New version page

CMU ISM 95760 - Man Sci I, Final Exam

Documents in this Course
Load more

This preview shows page 1-2-3 out of 8 pages.

View Full Document
View Full Document

End of preview. Want to read all 8 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

90-722: Man Sci I, Final Exam (AFTERNOON), Spring 2017Do not turn the page until you are told to do so. Write your answers below each question.Note how much each problem is worth and budget your time. Total points possible: 129Name: ______________________________Q1: _________ out of 15 possible pointsQ2: _________ out of 20 possible pointsQ3: _________ out of 20 possible pointsQ4: _________ out of 10 possible pointsQ5: _________ out of 32 possible pointsQ6: _________ out of 32 possible pointsTotal Possible Points: 1291Question #1 (15 points): Fill in the blanks below with the appropriate number or numbers corresponding to the following list of algorithms that we discussed for solving optimization problems. (Write the number(s) neatly)1. Simplex2. Graphical approach to solving LPs3. Evolutionary4. Enumerating all extreme points (aka “vertices”)5. Branch & Bound6. Simulated Annealing7. GRG or “hill climbing”8. Greedy algorithm9. Brute force search over all possible values of the decision variablesWhich algorithm or algorithms …a) involve randomness? _____________b) is/are effective for smooth, convex NLPs but is/are prone to get stuck at local optima? _____________c) is/are most commonly applied to IPs? _____________d) suffer badly from a curse of dimensionality? _____________e) Produce sensitivity reports that specify shadow prices, reduced costs, and allowable increases and decreases? _____________2For Questions #2 - #4: Recall that in HW #1, Problem #6, Howie’s friend Harold convinced Howie to commit to selling at least 45 “Super Bowl” kits that do-it-yourselfers (DIY) can assemble at home. I’ve pasted the spreadsheet from the optimization problem below.Its algebraic formulation is:Letting the subscripts denote the hot tub types, i = 1, 2, 3Maximize 350 X1 + 375 X2 + 750 X3 s.t.X1 + X2 + 2 X3 ≤ 180 9 X1 + 6 X2 ≤ 150012 X1 + 16 X2 + 40 X3 ≤ 2400 X3 ≥ 45 Xi ≥ 0 for all i.Problems #2 - #3 ask you to write the algebraic formulation for various extensions of this problem. Only write down what is new or changed; do not re-write portions of the formulation that are unchanged. Question #2: (20 Points): Modify the formulation so that (a) Howie incurs a fixed cost of $2,500 for each model he produces, and (b) If he sells more than 20 Aqua Spas then he must sell at least 10 Hydroluxes.3Question #3: (20 Points): [Start over with the 3-product Howie problem without the additions from Problem #2.] Making and selling one Aqua Spa produces 3 units of pollution, one Hydrolux procures 2 units of pollution, and one Super Bowl produces 1 unit of pollution. Howie wants to both maximize profit and minimize the amount of pollution produced. Suppose targets for these two goals are $50,000 and 180 units, respectively. Augment the formulation so Howie can minimize the maximum percentage deviation from these two targets.Question #4: (10 Points): Sketch the shape of the efficient frontier that would be produced by solving the previous problemas a Goal Program. That would repeatedly minimize a weighted sum of the deviations (or percentage deviations), varying the weights between runs. On your graph, put attainment on Goals #1 and #2 on the horizontal and vertical axes, respectively. Label the axes with the actual goal (not “Goal #1” and “Goal #2”). Put a smiley face in the corner that would be ideal. Label one side of the frontier “infeasible” and the other side “suboptimal”. 4Question #5: (32 Points): Consider a “linear city” meaning all people and facilities are strung out along one long straight road, so location is specified by a single number not a pair of numbers as with specifying a location with its longitude and latitude. This city begins at location“0” and stretches for 26 miles. So, for example, the location “10” means 10 miles along the road.There are 26 customers located at mile points 1, 2, 3, … 26. There are nine locations at which facilities could be built to serve these customers, with locations and costs as follows.Assume a customer can be considered “covered” if a facility is built 3 or fewer miles from the customer and the city wants to figure out how to cover all 26 customers at the lowest possible cost.a) What kind of optimization problem is this? (Be specific)b) How many decision variables are there and what do they mean or stand for?c) Write the algebraic expression for the constraints guaranteeing that customers #1, #8, and#15 are covered. (Do not use summation notation.)d) How many such constraints are there?e) What is the algebraic expression for the objective function?f) Suppose that for legal reasons a facility could only be built at site #4 if facilities are also built at both sites #1 and #7. Write the algebraic expression for the constraint enforcing that restriction. 5Question #6: (32 Points): I have pasted below the node-arc incidence representation of a transshipment problem. (It happens to be the one we solved in recitation.)a) (4 points) What does the 15 in cell A7 mean?6b) (4 points) Show how the Solver dialog box was filled in.c) (4 points) Write the algebraic expression for the flow balance constraint on node #3.d) (4 points) If you have implemented this optimization problem with the Chapter 3 approach of reserving an entire rectangle of cells for the decision variables (DVs), how many more cells would have been set aside for DV’s than are used in this node-arc incidence approach?e) (8 points) How would you modify this spreadsheet to “balance” supply and demand with a dummy node?7f) (8 points) How would you modify this spreadsheet and Solver dialog box to determine what is the maximum flow from node #2 to node #7? (Note: Several changes are required. Be sure to mention them


View Full Document
Loading Unlocking...
Login

Join to view Man Sci I, Final Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Man Sci I, Final Exam and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?