Systems Optimization Sample Final 2

Systems Optimization Final Exam Instructions You have two hours to complete the exam from the time you first begin it. Watch your time. If you are having difficulty with a question, you might wish to pass over it and return to it later if you have enough time at the end of the exam. The exam is open book: you may use any notes or text material. You are encouraged to use Excel to build your models. The exam is to be done individually, without collaboration with anyone else. Problem 1 Linear Forms (30 points) Consider the following AMPL models. In each case: a. Indicate hether or not the given model is a linear model as it is stated and b. If it is not a linear model as stated either show how to formulate an equivalent linear model (with no approximations) or state that no linear formulation is possible. Do not forget to answer both part a. and part b. i. We are trying to forecast future demand from historical demand. Our model of demand includes an initial level and a rate of growth -- both of which we are trying to estimate. param T; param Demand{1..T}; /* The number of past quarters of demand data */ /* The demand in quarter 1, 2, …, T */ var InitialLevel; /* The initial level of demand in quarter 0 for our forecast This could be negative as we are using it to fit the rest of the data */ var GrowthRate; /* The change in demand from quarter to quarter. This could be negative as we might be selling buggy whips */ var Estimate{1..T}; /* This variable is a convenience. It is simply the demand we estimate in each quarter given the values of the InitialLevel and GrowthRate */ /* We measure the quality of the forecast based on how well it fits historical data as estimated by the sum of the absolute differences between the forecast and actual demand in quarters 1, 2, …T */ minimize TotalError: sum{t = 1..T} abs(Estimate[t] - Demand[t]); s.t. DefineEstimate {t in 1..T}: Estimate[t] = InitialLevel + GrowthRate*t; Part a: Is this a linear model as it is given? Part b. If it is not written as a linear model, can it be expressed as a linear model? If so, show how to express it as a linear model. ii. A Petrochemical company wants to combine two crudes with different Sulfur contents to create blends with certain specified Sulfur levels. Set CRUDES; /* The set of crudes */ Set BLENDS; /* The set of blends to produce */ Param Cost{CRUDES}; Param Sulfur{CRUDES}; Param Price{BLENDS}; Param MinSulfur{BLENDS}; Param MaxSulfur{BLENDS}; /* Cost in $/barrel for each type of crude */ /* grams of Sulfur per barrel for each type of crude */ /* Selling price in $/barrel for each blend */ /* minimum grams of Sulfur per barrel in the blends */ /* maximum grams of Sulfur per barrel in the blends */ Param Supply{CRUDES}; Param MinProduction{BLENDS}; Param MaxProduction{BLENDS}; /* barrels of each crude available */ /* minimum barrels of each blend to make */ /* maximum barrels of each blend to make */ Var Allocation{CRUDES, BLENDS} >= 0; /* The barrels of each crude used in each blend */ /* The barrels of each blend made */ Var Blend{blend in BLENDS} >= MinProduction[blend], <= MaxProduction[blend]; /* The barrels of each crude used */ Var Crude{crude in CRUDES} >= 0, <= Supply[crude]; Maximize NetRevenue: Sum{blend in BLENDS} Price[blend]*Blend[blend] Sum{crude in CRUDES} Cost[crude]*Crude[crude]; s.t. DefineBlendProduction {blend in BLENDS}: sum{crude in CRUDES} Allocation[crude, blend] = Blend[blend]; s.t. DefineCrudeUsage {crude in CRUDES}: sum{blend in BLENDS} Allocation[crude, blend] = Crude[crude]; s.t. MeetMinSulfurTargets{blend in BLENDS}: (sum{crude in CRUDES} Sulfur[crude]*Allocation[crude, blend])/Blend[blend] >= MinSulfur[blend]; s.t. MeetMaxSulfurTargets{blend in BLENDS}: (sum{crude in CRUDES} Sulfur[crude]*Allocation[crude, blend])/Blend[blend] <= MaxSulfur[blend]; Part a: Is this a linear model as it is given? Part b. If it is not written as a linear model, can it be expressed as a linear model? If so, show how to express it as a linear model. iii. Pratt & Whitney is sequencing the blades on a fan to ensure proper balance of the assembly. We are only concerned with balance in the plane of rotation. For simplicity, we assume that blades only differ in their masses and so the problem is to sequence the different masses around the fan so that the resulting center of gravity is as close to the center of the fan as possible. set BLADES; /* The blades to be placed*/ /* The positions where the blades are to be placed are uniformly spaced positions around the circumference. There is one position for each blade set POSITIONS := 1..card(BLADES); */ param Mass {BLADES}; /* The mass of each blade */ param Factor{POSITIONS, POSITIONS}; let Factor{p1 in POSITIONS, p2 in POSITIONS} := cos(2*(p1-p2)*pi/n); var Assign{BLADES, POSITIONS} binary; /* The objective is to minimize the distance between the center of mass and the center of the fan */ minimize DistanceFromCenter: sum{b1 in BLADES, p1 in POSITIONS, b2 in BLADES, p2 in POSITIONS} Mass[b1]*Mass[b2]*Factor[p1, p2]*Assign[b1, p1]*Assign[b2, p2]; s.t. APositionForEachBlade{blade in BLADES}: sum{p in POSITIONS} Assign[blade, p] = 1; s.t. ABladeForEachPosition{position in POSITIONS}: sum{b in BLADES} Assign[b, position] = 1; Part a: Is this an integer linear model as it is given? Part b. If it is not written as an integer linear model, can it be expressed as an integer linear model? If so, show how to express it as an integer linear model. Problem 2 Sensitivity Analysis (10 points) Eastern Steel wishes to create a blended ore using raw ores from 4 mines. The customer will pay $850 per ton for up to 150,000 tons of the blend. Mine T1 can provide up to 21,000 tons of ore at a cost of $800 per ton, Mine T2 can provide up to 40,000 tons of ore at a cost of $400 per ton, Mine T3 can provide up to 15,000 tons of ore at a cost of $600 per ton and Mine T4 can provide up to 22,000 tons of ore at a cost of $500 per ton. The customer requires the blend to contain at least given minimum levels of three components A, B and C. The ores from the different mines contain different levels of these three components. Below (next page) is an Solver Model with optimum solution yielding a contribution margin of $30,500,000 as well as a Sensitivity report. Note the quantities of Blend produced and ores used are in thousands of tons. A. After solving the problem, the company learns it can have up to another 3,000 tons of ore from mine T1 at the standard price of $800/ton. One manager claims that since the shadow price on the constraint stipulating the limit on the ore available from mine T1 is 0, Eastern Steel should not purchase more ore. Is this correct? B. Suppose the constraint limiting the total tons of ore available were removed and the problem was re-solved (keeping the available tons of ore from mine T1 at 21,000). What would the shadow price on the constraint limiting the available ore from Mine T1 be? What would the shadow price on the constraint limiting the available ore from Mine T2 be? Product Qty. Prod. (000s) Contr. Mar. Blend 98.0 T1 21.0 T2 40.0 T3 15.0 T4 22.0 $ 850 $ (800) $ (400) $ (600) $ (500) Profit $ 30,500 Total Blended Ore Blended Limit Ore Limit Mine 1 Ore Limit Mine 2 Ore Limit Mine 3 Ore Limit Mine 4 Total Ore Avail. Minimum A Minimum B Minimum C 1 1 -1 -1 -1 -1 0 98 21 40 15 22 98 4 3065 119 1 1 1 1 5 -10 15 1 -2 50 -5 1 1 -3 75 7 1 3 -25 -10 = < < < < < < > > > RHS Slack 0 0 150 52 21 1E-04 40 0 15 0 22 0 98 0 0 4 0 3065 0 119 Microsoft Excel 9.0 Sensitivity Report Adjustable Cells Name Cell $B$2 Qty. Prod. (000s) Blend $C$2 Qty. Prod. (000s) T1 $D$2 Qty. Prod. (000s) T2 $E$2 Qty. Prod. (000s) T3 $F$2 Qty. Prod. (000s) T4 Constraints Cell $G$12 $G$13 $G$14 $G$5 $G$6 $G$7 $G$8 $G$9 $G$10 $G$11 Name Minimum A Total Minimum B Total Minimum C Total Blended Ore Total Blended Limit Total Ore Limit Mine 1 Total Ore Limit Mine 2 Total Ore Limit Mine 3 Total Ore Limit Mine 4 Total Total Ore Avail. Total Final Value 98.0 21.0 40.0 15.0 22.0 Final Value 4 3065 119 0 98 21 40 15 22 98 Reduced Cost 0.0 0.0 0.0 0.0 0.0 Shadow Price 0 0 0 850 0 0 400 200 300 50 Objective Coefficient 850 -800 -400 -600 -500 Constraint R.H. Side 0 0 0 0 150 21 40 15 22 98 Allowable Increase 1E+30 200 1E+30 1E+30 1E+30 Allowable Increase 4 3065 119 52 1E+30 1E+30 0.5714 2 0.5 0 Allowable Decrease 50 50 400 200 300 Allowable Decrease 1E+30 1E+30 1E+30 98 52 0 0 0 0 0.8 Problem 3 Basic Facts (30 points) Indicate whether each of the following questions is true or false. a. In solving an integer programming problem, Solver and CPLEX solve linear programming relaxations obtained by ignoring the integrality conditions on some of the variables. b. In solving an integer programming problem, Solver and CPLEX solve a linear programming relaxation obtained by ignoring the integrality conditions on all of the variables and then round the integer variables to integral values. c. The set of feasible solutions to a linear program describes a convex set. d. The set of feasible solutions to an integer program describes a convex set. e. The set of feasible solutions to a non-linear program describes a convex set. f. Linear functions are convex functions g. Linear functions are concave functions h. Quadratic functions are convex functions. i. If a real valued function f is a convex function then the function g(x) = 1-f(x) is a convex function j. The average objective value across the members of the population improves from one generation to the next in Standard Evolutionary Algorithms Problem 4 Relaxations and Restrictions (20 points) Consider a minimization problem with some integer variables. The problem need not be linear. Indicate all the guaranteed relations between the following values: 1. 2. 3. 4. The optimum objective value The objective value of a feasible solution The optimum objective value of the problem in which we relax the integrality constraints The optimum objective value of the problem in which we fix the values of some of the integer variables. 5. The optimum objective value of the problem in which we drop some of the constraints. Be sure to express all the guaranteed relationships you can --- but no more than that. Problem 5 Integer Programming Formulation (10 points) Formulate an integer linear model of the following situation. This is intended to be part of a larger, more complicated model so the fact that we can solve the problem easily is irrelevant -- we are only talking about a small piece of the problem. There are N items numbered 1, 2, N. If we choose item i, we earn r[i]. If we select exactly one of the items, we must pay b. We don't pay b if we chose two or more or if we don't choose any. We want to maximize net revenue. You may introduce other variables if you wish. You will certainly need to add an objective and constraints. param N; param r{1..N}; param b; # the number of items. # the revenue on each item # the cost incurred if we choose exactly one of the items var x{1..N} binary; # x[i] is one if we choose item i and 0 otherwise.