ISE426 Homework 2

ISE 426. Optimization and Applications (Spring 2022) Prof. Karmel S. Shehadeh Homework #2–Due via Course Site at 9 AM on Feb 28, 2022 Instructions • Show all of the work leading to the solution of each problem. Points are allocated to all of the steps of the solution process, not just the final answer. • I strongly encourage you to type all your assignment solutions using your favorite typesetting system (e.g., MS Word, L A T E X, etc.). For your convenience, a L A T E X template for typing your solution is available in the assignment folder on the Course Site . • If you write an AMPL code to solve any problem, you are required to provide a carefully and detailed commented version of the code in an appendix of the assignment . Note that your code is NOT a substitute for a detailed written explanation of the approach you take to solve the problem and your results. • Include a title page with assignment number, your name and contact information, and the names of all students that you discussed your assignment with (if any). Make sure that you scan/compile your HW work into a single and legible PDF file. “ You got this! Good luck. ”

ISE 426 Homework #2–Due via Course Site at 9 AM on Feb 28, 2022 Spring 2022 Question 1 (15 points). Large-scale LP Formulation. Consider the following transportation problem. A paper manufacturer has n mills to produce newsprint, and m printing plants whose demand for the newsprint must be satisfied every week. Each mill i ∈ { 1 , . . . , n } can produce s i tons of newsprint every week. Each printing plant j ∈ { 1 , . . . , m } must receive d j tons of shipped newsprint. The shipping cost, in dollars per ton, from mill i to printing plant j is c i,j , for all i ∈ { 1 , . . . , n } and j ∈ { 1 , . . . , m } . Assume that the total supply from mills and total demand from printing plants are equal. Write a general linear programming formulation for the problem, where the aim is to satisfy the printing plants’ demand while minimizing total transportation costs and satisfying the supply constraints. In particular, clearly specify the 1. Decision variables. 2. Objective. 3. Constraints. For simplicity, assume that orders (in ton) from a mill to a printing plant need not be integers. Lehigh University Page 1 of 7

ISE 426 Homework #2–Due via Course Site at 9 AM on Feb 28, 2022 Spring 2022 Question 3 (20 points). Graphical Sensitivity Analysis for LP. Consider the following Linear Program: max x 1 + 2 x 2 s.t. x 1 ≤ 2 (1) x 2 ≤ 6 (2) 2 x 1 + x 2 ≤ 8 (3) x 1 ≥ 0 (4) x 2 ≥ 0 (5) 1. (5 points) Solve the Linear Program above graphically. 2. (3 points) For what range of values of the objective coefficient of variable x 1 would the optimal solution remain the same? 3. (3 points) What is the optimal basis? (Refer to the numbers at the right of the constraints) 4. (3 points) What is the range of values for the right hand side of the second constraint (2) in which the optimal basis will remain the same. 5. (6 points) What is the shadow price of the third constraint (3), and in what range is that shadow price valid? Lehigh University Page 3 of 7

ISE 426 Homework #2–Due via Course Site at 9 AM on Feb 28, 2022 Spring 2022 Question 4 (10 points). Sensitivity Analysis for Giapetto’s Woodcarving Problem. Consider Giapetto’s Woodcarving LP from lecture 7. max 3 x 1 + 2 x 2 (Objective) s.t. 2 x 1 + x 2 ≤ 100 (Finishing Constraint) (1) x 1 + x 2 ≤ 80 (Carpentry Constraint) (2) x 1 ≤ 40 (Constraint on demand for soldiers) (3) x 1 ≥ 0 , x 2 ≥ 0 (Non-negativity) (4) 1. (3 points) What is the range of values for the right hand side of the second constraint (2) in which the optimal basis (constraints (1) and (2)) will remain the same? 2. (4 points) What is the shadow price of constraint (2)? 3. (3 points) Show that if the weekly demand for soldiers is at least 20, then the current basis remain optimal, and Giapetto should still produce 20 soldiers and 60 trains. Lehigh University Page 4 of 7

ISE 426 Homework #2–Due via Course Site at 9 AM on Feb 28, 2022 Spring 2022 Question 6 (30 points). Linear Programming Modeling and AMPL A steel plant can employ three different processes to produce steel. Each process requires a different amount of labor, ore, and coal. Moreover, each process produces not only steels, but also a side product with a limited profit. The inputs and outputs for 1-hour operation of each process is as follows. Input Output Labor Ore Coal Steel Side Product (hour) (lb) (lb) (lb) (lb) Process 1 8 200 145 550 35 Process 2 11 140 120 735 15 Process 3 7 300 225 600 75 There is a cost when using each input resource, and the steel plant only has limited input resources. The cost and capacity for each input resource are given in the table below. Note that 1 ton is equal to 2 , 000 lbs. Resource Cost Capacity Labor $15 . 75/hr 350 hours Ore $43/ton 5 tons Coal $12/ton unlimited The steel produced can be sold for $850/ton, and up to 1 ton of the side product can be sold for $37/ton (any amount above 1 ton has no value). Moreover, due to the operational restrictions, no one single process can be employed for more than 40 hours. The objective is to determine the number of hours employed in each process to maximize the overall net profit. 1. (15 points) Write a Linear Programming formulation of the problem. In particular state the problem’s: (a) Decision variables. (b) Objective. (c) Constraints. 2. (5 points) Suppose now that there is an additional 8-hour labor overtime at a cost of $20/hr. Modify the mathematical program you proposed in the last question to take this new possibility into consideration. (It is fine to write only the parts of your original mathematical formulation that need to be changed.) 3. (10 points.) Model and solve the problem formulated in part 1 using AMPL. In particular, produce a print-out of the following (a) (5 points) AMPL code (model and data). (b) (2.5 points) Optimal solution. (c) (2.5 points) Optimal objective value. Lehigh University Page 6 of 7

ISE 426 Homework #2–Due via Course Site at 9 AM on Feb 28, 2022 Spring 2022 Question 7 (10 points). 1. ( 5 points ) If you were the ISE 426 instructor, which question(s) from this homework you would ask in the exam? And why?. Other questions? 2. ( 4 points ) What was the most challenging question in this homework? And why? 3. ( 1 point ) Do you want 1 extra credit or not? (Yes/No) Lehigh University Page 7 of 7