Mixed-Integer Linear Programming for Civil Systems Analysis

WESTERN MICHIGAN UNIVERSITY CCE-6100-100 - Civil Systems Analysis HW.7 Done by: Aws Tarawneh

1. Consider the following mixed-integer linear program: a. Graph the constraints for this problem. Indicate on your graph all feasible mixed- integer solutions. Feasible area feasible mixed-integer solutions are (0,7),(4,0),(0,0),(1.96,5.48),(2.5,4.5) b. Find the optimal solution to the LP Relaxation. Round the value of x2 down to find a feasible mixed-integer solution. Specify upper and lower bounds on the value of the optimal solution to the mixed-integer linear program. The optimal solution is x1=1.96 , x2= 5.48 max = 7.44 Rounding the value of x2 down the optimal solution will become x1=1.96 x2=5 max = 6.96 c. Find the optimal solution to the mixed-integer linear program.

When we round up X1=1.29 X2=6 max= 7.29 When we round down X1=2.22 X2=5 max= 7.22 The optimal solution to the MILP is X1=1.29 X2=6 max= 7.29 2. An automobile manufacturer a. Develop a table that lists every possible option available to management. As part of your table, indicate the total engine block capacity and transmission capacity for each possible option, whether the option is feasible based on the projected needs, and the total modernization cost for each option. 1= Michigan plant 2= New York plant 1 3= New York plant 2 4= Ohio plant 5= California plant We can’t meet the requirements by modernizing only one plant we will have to modernize 2 plants 1 2 3 4 5 Total Engine block capacity Total Transmissio n capacity Cover the requirements cost 1300 700 No 60 900 1100 Yes 60 1400 900 Yes 65 700 600 No 45 1200 1200 Yes 70 1700 1000 Yes 75 1000 700 No 55 1300 1400 Yes 75 600 1100 No 55 1100 900 Yes 60 b. Based on your analysis in part (a), what recommendation would you provide management? I recommend to modernize either plant 1&3 or plant 4&5 c. Formulate a 0-1 integer programming model that could be used to determine the optimal solution to the modernization question facing management.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Min 25X1+35X2+35X3+40X4+25X5 s.t. 300X1+400X2+800X3+600X4+300X5>=900 500X1+800X2+400X3+900X4+200X5>=900 Xi=1,0 i=1,2,3,4,5 d. Solve the model formulated in part (c) to provide a recommendation for management. Optimal solution X1=X3=1 3. The Bayside Art Gallery a. Formulate a 0-1 integer linear programming model that will enable Bayside’s management to determine the locations for the camera systems. Let xi = 1 if a camera is located at opening i; 0 if not. min x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13 s.t. x1 + x4 + x6 ≥ 1 Room 1 x6 + x8 + x12 ≥ 1 Room 2 x1 + x2 + x3 ≥ 1 Room 3 x3 + x4 + x5 + x7 ≥ 1 Room 4 x7 + x8 + x9 + x10 ≥ 1 Room 5 x10 + x12 + x13 ≥ 1 Room 6 x2 + x5 + x9 + x11 ≥ 1 Room 7 x11 + x13 ≥ 1 Room 8 b. Solve the model formulated in part (a) to determine how many two-way cameras to purchase and where they should be located. x1 = x5 = x8 = x13 = 1. Thus, cameras should be located at 4 openings: 1, 5, 8, and 13. An alternative optimal solution is x1 = x7 = x11 = x12 = 1. c. Suppose that management wants to provide additional security coverage for room 7. Specifically, management wants room 7 to be covered by two cameras. How would your model formulated in part (a) have to change to accommodate this policy restriction? Change the constraint for room 7 to x2 + x5 + x9 + x11 ≥ 2 d. With the policy restriction specified in part (c), determine how many two-way camera systems will need to be purchased and where they will be located x3 = x6 = x9 = x11 = x12 = 1. Cameras should be located at openings 3, 6, 9, 11, and 12. An alternate optimal solution is x2 = x4 = x6 = x10 = x11 = 1. Optimal Value = 5 Case Problem 2: Yeager National Bank

A mixed integer linear programming (MILP) model can be used advantageously to assist in preparing a report for Mr. Wolff. Since the annual fixed costs of operating the lockboxes are not known exactly we formulate a model that can be used without that information. Then determine if information more precise than the $20,000 - $30,000 estimate is needed to make a final decision. We formulate a model that can be solved to find the best set of locations with a given number of lockboxes. It is then solved 4 times to find the best set of locations with 1 lockbox, up to 2 lockboxes, up to 3 lockboxes, and up to 4 lockboxes. We then can address the question of whether annual operating cost information is needed from some or all of the potential lockbox locations. We use the following variable definitions: P = 1 if a lockbox is in Phoenix; 0 otherwise S = 1 if a lockbox is in Salt Lake City; 0 otherwise A = 1 if a lockbox is in Atlanta; 0 otherwise B = 1 if a lockbox is in Boston; 0 otherwise PNW = 1 if the Northwest region is assigned to Phoenix; 0 otherwise PSW = 1 if the Southwest region is assigned to Phoenix; 0 otherwise . . . BSE = 1 if the Southeast region is assigned to Boston; 0 otherwise The MILP model has 24 variables and 26 constraints. The objective function calls for minimizing lost interest income. To see how the objective function coefficients are computed, consider assigning the Northwest region to Phoenix. Daily collections are $80,000 and it takes 4 days to receive and process payments. At a 15% rate Yeager could save $48,000 = (.15)(4) ($80,000) annually over this assignment if the Northwest collections could be credited to their account instantaneously. A similar calculation is made for all the other potential assignments. The objective function coefficients for P, S, A, and B are zero since we are not including the cost of operating the lockboxes at this stage. Constraints (1) to (5) ensure that each region is assigned a lock box. Constraints (6) to (25) ensure that a region is only assigned to a lockbox location that is open. And, constraint (26) is a limitation on the number of lockbox locations that may be chosen. The right-hand-side of that

constraint will be varied from 1 to 4 as the problem is solved 4 times. Shown below is the MILP model that is solved to find the optimal solution when up to 2 lockboxes may be used. INTEGER LINEAR PROGRAMMING PROBLEM MIN 48PNW + 27PSW + 112.5PCE + 135PNE + 60PSE + 24SNW + 40.5SSW + 67.5SCE + 108SNE + 90SSE + 48ANW + 54ASW + 67.5ACE + 81ANE + 30ASE + 48BNW + 81BSW + 90BCE + 54BNE + 45BSE S.T. 1PNW+1SNW+1ANW+1BNW=1 +1PSW+1SSW+1ASW+1BSW=1 +1PCE+1SCE+1ACE+1BCE=1 +1PNE+1SNE+1ANE+1BNE=1 +1PSE+1SSE+1ASE+1BSE=1 1PNW-1P<0 +1PSW-1P<0 +1PCE-1P<0 +1PNE-1P<0 +1PSE-1P<0 +1SNW-1S<0 +1SSW-1S<0 +1SCE-1S<0 +1SNE-1S<0 +1SSE-1S<0 +1ANW-1A<0 +1ASW-1A<0 +1ACE-1A<0 +1ANE-1A<0 +1ASE-1A<0 +1BNW-1B<0 +1BSW-1B<0 +1BCE-1B<0

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

+1BNE-1B<0 +1BSE-1B<0 +1P+1S+1A+1B<2 By Lingo Program Global optimal solution found. Objective value: 231.0000 Infeasibilities: 0.000000 Total solver iterations: 10 Model Class: LP Total variables: 24 Nonlinear variables: 0 Integer variables: 0 Total constraints: 27 Nonlinear constraints: 0 Total nonzeros: 84 Nonlinear nonzeros: 0 Variable Value Reduced Cost PNW 0.000000 10.50000 PSW 0.000000 0.000000 PCE 0.000000 45.00000 PNE 0.000000 66.00000 PSE 0.000000 15.00000 SNW 1.000000 0.000000 SSW 1.000000 0.000000 SCE 1.000000 0.000000 SNE 0.000000 39.00000 SSE 0.000000 45.00000 ANW 0.000000 9.000000 ASW 0.000000 13.50000 ACE 0.000000 0.000000 ANE 0.000000 12.00000 ASE 0.000000 0.000000 BNW 0.000000 9.000000 BSW 0.000000 40.50000 BCE 0.000000 22.50000 BNE 1.000000 0.000000 BSE 1.000000 0.000000 P 0.000000 0.000000 S 1.000000 0.000000 A 0.000000 0.000000 B 1.000000 0.000000 Row Slack or Surplus Dual Price 1 231.0000 -1.000000 2 0.000000 -39.00000 3 0.000000 -40.50000 4 0.000000 -67.50000 5 0.000000 -69.00000 6 0.000000 -45.00000 7 0.000000 1.500000 8 0.000000 13.50000 9 0.000000 0.000000 10 0.000000 0.000000

11 0.000000 0.000000 12 0.000000 15.00000 13 0.000000 0.000000 14 0.000000 0.000000 15 1.000000 0.000000 16 1.000000 0.000000 17 0.000000 0.000000 18 0.000000 0.000000 19 0.000000 0.000000 20 0.000000 0.000000 21 0.000000 15.00000 22 1.000000 0.000000 23 1.000000 0.000000 24 1.000000 0.000000 25 0.000000 15.00000 26 0.000000 0.000000 27 0.000000 15.00000 With 2 lockbox locations, the lost interest income is $231,000. Resolving with values of 1, 3, and 4 on the right-hand-side of constraint 26 provides the following: No. of Lockboxes Locations Lost Interest Income ($) 1 Atlanta 280,500 2 Salt Lake City & Boston 231,000 3 Salt Lake City, Atlanta & Boston 216,000 4 Salt Lake City, Phoenix, Atlanta & Boston 202,500

CCE 6100 HW7

Related Documents