Homework5Solutions

IEOR 162 Homework 5 Linear Programs & Network Flows - Page 1 of 7Out: September 20, 2023 Due: September 29, 2023 1. A university department wishes to create a daily schedule for its classes using integer program- ming. The department has access to three classrooms with the following capacities: Room Capacity 1 50 2 100 3 150 Each classroom is available for five hours a day. Assume the schedule for each day must be identical (so that creating a daily schedule is the same as creating a weekly schedule). Five different courses must be scheduled according to the times in the table below: Course Enrollment Length (hours) A 40 3 B 50 2 C 90 2 D 130 3 E 140 2 Formulate an integer programming model that will produce a feasible schedule. Solution: Solution. Define the following binary variables: A i = 1 if course A is assigned to room i B i = 1 if course B is assigned to room i C i = 1 if course C is assigned to room i D i = 1 if course D is assigned to room i E i = 1 if course E is assigned to room i minimize 0 subject to C 1 = 0 D 1 + D 2 = 0 E 1 + E 2 = 0 3 A 1 + 2 B 1 + 2 C 1 + 3 D 1 + 2 E 1 ≤ 5 3 A 2 + 2 B 2 + 2 C 2 + 3 D 2 + 2 E 2 ≤ 5 3 A 3 + 2 B 3 + 2 C 3 + 3 D 3 + 2 E 3 ≤ 5 A 1 + A 2 + A 3 = 1 B 1 + B 2 + B 3 = 1 C 1 + C 2 + C 3 = 1 D 1 + D 2 + D 3 = 1 E 1 + E 2 + E 3 = 1 A i , B i , C i , D i , E i ∈ { 0 , 1 } , ∀ i.

IEOR 162 Homework 5 Linear Programs & Network Flows - Page 2 of 7Out: September 20, 2023 Due: September 29, 2023 2. IEOR 162 Inc. is opening up a package processing facility for its delivery business. The company is trying to select from 5 potential sites to build 2 facilities, which will serve customers in 3 different locations. The distances (in miles) between each site and each customer location is given in the table below: Site Customer 1 Customer 2 Customer 3 1 50 10 30 2 25 15 80 3 40 65 75 4 60 90 45 5 50 30 20 Formulate an integer programming problem to select the location of the two facilities such that the maximum distance of any customer to its assigned facility is minimized. Assume there are no capacity issues at the facilities. Solution: Solution. Define: x i = 1 if a facility is built in location i = 1 , 2 , 3 , 4 , 5 and 0 otherwise, y ij = 1 if customer j is assigned to facility i , j = 1 , 2 , 3 w = the maximum of the distances between each customer and its assigned facility minimize w subject to w ≥ 50 y 11 + 25 y 21 + 40 y 31 + 60 y 41 + 50 y 51 w ≥ 10 y 12 + 15 y 22 + 65 y 32 + 90 y 42 + 30 y 52 w ≥ 30 y 13 + 80 y 23 + 75 y 33 + 45 y 43 + 20 y 53 y 11 + y 12 + y 13 ≤ 3 x 1 y 21 + y 22 + y 23 ≤ 3 x 2 y 31 + y 32 + y 33 ≤ 3 x 3 y 41 + y 42 + y 43 ≤ 3 x 4 y 51 + y 52 + y 53 ≤ 3 x 5 y 11 + y 21 + y 31 + y 41 + y 51 = 1 y 12 + y 22 + y 32 + y 42 + y 52 = 1 y 13 + y 23 + y 33 + y 43 + y 53 = 1 x 1 + x 2 + x 3 + x 4 + x 5 = 2 x i , y ij ∈ { 0 , 1 } , ∀ i, j. 3. A power utility company believes it will need the amounts of generating capacity shown in the table below during the next five years. The company has a choice of building power plants with the specifications shown in the second table below. All capacities are given in tera-watt hours (TWh) and all costs are given in millions of dollars.

IEOR 162 Homework 5 Linear Programs & Network Flows - Page 4 of 7Out: September 20, 2023 Due: September 29, 2023 minimize 20 x 1 + 16 x 2 + 18 x 3 + 14 x 4 + 1 . 5( y 11 + y 12 + y 13 + y 14 + y 15 ) + 0 . 8( y 21 + y 22 + y 23 + y 24 + y 25 ) + 1 . 3( y 31 + y 32 + y 33 + y 34 + y 35 ) + 0 . 6( y 41 + y 42 + y 43 + y 44 + y 45 ) subject to 70 y 11 + 50 y 21 + 60 y 31 + 40 y 41 ≥ 80 70 y 12 + 50 y 22 + 60 y 32 + 40 y 42 ≥ 100 70 y 13 + 50 y 23 + 60 y 33 + 40 y 43 ≥ 120 70 y 14 + 50 y 24 + 60 y 34 + 40 y 44 ≥ 140 70 y 15 + 50 y 25 + 60 y 35 + 40 y 45 ≥ 160 y 11 + y 12 + y 13 + y 14 + y 15 ≤ 5 x 1 y 21 + y 22 + y 23 + y 24 + y 25 ≤ 5 x 2 y 31 + y 32 + y 33 + y 34 + y 35 ≤ 5 x 3 y 41 + y 42 + y 43 + y 44 + y 45 ≤ 5 x 4 y 12 ≥ y 11 , y 13 ≥ y 12 , y 14 ≥ y 13 , y 15 ≥ y 14 y 22 ≥ y 21 , y 23 ≥ y 22 , y 24 ≥ y 23 , y 25 ≥ y 24 y 32 ≥ y 31 , y 33 ≥ y 32 , y 34 ≥ y 33 , y 35 ≥ y 34 y 42 ≥ y 41 , y 43 ≥ y 42 , y 44 ≥ y 43 , y 45 ≥ y 44 x i , y it ∈ { 0 , 1 } ∀ i = 1 , 2 , 3 , 4 , t = 1 , 2 , 3 , 4 , 5 4. A mining company obtains iron ore from two sites (Mine 1 and Mine 2). The company also owns two storage facilities (Storage 1 and Storage 2) and a central steel mill (Plant). Every month, the company has to transport iron ore that produced from both of its mines to the steel mill. This month, 100 tons of iron ore must be shipped from the mines to the mill in order for the company to meet its steel production targets. We have the following information regarding the transport routes from the mines to the storage facilities: • Mines 1 and 2 will produce 40 and 60 tons of iron ore this month. • Mine 1 can ship to Storage 1 at a cost of $ 2,000/ton, and can ship up to 30 tons using this route. • Mine 1 can ship to Storage 2 at a cost of $ 1,700/ton, and can ship up to 30 tons using this route. • Mine 2 can ship to Storage 1 at a cost of $ 1,600/ton, and can ship up to 50 tons using this route. • Mine 2 can ship to Storage 2 at a cost of $ 1,100/ton, and can ship up to 50 tons using this route. We also have information regarding the routes from the storage facilities to the central processing facility:

IEOR 162 Homework 5 Linear Programs & Network Flows - Page 5 of 7Out: September 20, 2023 Due: September 29, 2023 • Storage 1 can ship to the Plant at a cost of $ 400/ton, and can ship up to 70 tons using this route. • Storage 2 can ship to the Plant at a cost of $ 800/ton, and can ship up to 70 tons using this route. (a) Formulate a linear programming model that allows the company to meet its steel produc- tion targets this month while minimizing transportation costs. Solution: Define decision variables: x ij = quantity of iron ore shipped from Mine i to Storage j , i = 1 , 2 and j = 1 , 2. Also define decision variables: y i = quantity of ore shipped from Storage 1 to the Plant. The linear programming formulation is minimize 2 x 11 + 1 . 7 x 12 + 1 . 6 x 21 + 1 . 1 x 22 + 0 . 4 y 1 + 0 . 8 y 2 subject to y 1 + y 2 ≥ 100 x 11 + x 21 = y 1 x 12 + x 22 = y 2 x 11 + x 12 ≤ 40 x 21 + x 22 ≤ 60 x 11 ≤ 30 x 12 ≤ 30 x 21 ≤ 50 x 22 ≤ 50 y 1 ≤ 70 y 2 ≤ 70 x 11 , x 12 , x 21 , x 22 , y 1 , y 2 ≥ 0 . • The objective represents the total transportation cost. • The first constraint ensures that demand at the plant is met from the output of the storage facilities. • The second and third constraints are “flow conservation” constraints, which en- sure that the quantity of ore shipped into the storage facility is equal to the quantity shipped out. • The next two constraints limit the amount shipped out of each mine to be no greater than the maximum production output of that mine. • The next six constraints are capacity constraints on the arcs. • Finally, we have non negativity constraints to ensure negative quantities of ore cannot be shipped. (b) Solve the problem with AMPL. Report the optimal solution and objective value as well as sensitivity results.

IEOR 162 Homework 5 Linear Programs & Network Flows - Page 7 of 7Out: September 20, 2023 Due: September 29, 2023 coefficients. Therefore, the optimal solution remains the same. To calculate the new objective value, we plug in the optimal solution in the adjusted objective: 2000 × 30 + 1700 × 10 + 1600 × 10 + 1100 × 50 + 400 × 40 + 750 × 60 = $209 , 000 . The new optimal objective value is $ 209,000. iii. Suppose the company made a mistake and realized that the truck that ships the ore from mine 1 to storage 1 (this truck can’t be used on other routes) has a capacity of 25 instead of 30 tons. How does this affect the optimal transportation cost? Solution: In this case, we are interested in the constraint capacityToWarehouse[1,1]. Currently, shipping up to 30 tons is allowed. As long as the capacity is between 20 and 40 the current basis (intersection) remains optimal. Furthermore, we observe that the shadow price is $ 100. This means that if we increase the capacity between mine 1 and storage 1 by one unit then the shipping cost will go down by $ 100. Since a capacity of 25 is in the allowed range (a decrease of 5 units), we know that the shipping cost will go up by $100 × 5 = $500. iv. What is the range for the capacity of the truck between mine 2 and storage 2 such that the same intersection of constraints remain optimal? Solution: To determine the allowed range we look at the constraint capacityTo- Warehouse[2,2]. The basis remains optimal if the capacity is within the allowed range of 20 (see var.down) and 60 (see var.up).