ISE 426 HW1

ISE 426. Optimization and Applications (Spring 2022) Prof. Karmel S. Shehadeh Homework #1–Due via Course Site at 9 AM on Feb 14, 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. • You should type all your homework assignments 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 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...ENJOY it :-) ”

ISE 426 Homework #1–Due via Course Site at 9 AM on Feb 14, 2022 Spring 2022 Question 1 (15 Points). Linear Programming Modeling. As a weapon shop owner in a video game, you produce and sell weapons to knights. The following table summarizes the sales profit, the quantities of the basic ingredients (iron and wood) for the production of sword and atgeir, and the required processing time. The data refer to the production of one kilogram (kg) of weapon. Type Profit Iron needed (kg) Wood needed (kg) Time (minute) Sword 10 1.00 0.10 10 Atgeir 8 0.70 0.32 5 The weapon shop has 100 kg of iron and 30 kg of wood. The workforce is available for no more than 10 hours in total. Formulate a Linear Program (decision variables, objective, and constraints) to decide the quantity (in kg) of sword and atgeir to produce in order to maximize the overall profit. In particular state the problem’s: 1. (5 points) Decision variables. 2. (3 points) Objective. 3. (7 points) Constraints. Lehigh University Page 1 of 7

ISE 426 Homework #1–Due via Course Site at 9 AM on Feb 14, 2022 Spring 2022 Question 3 (24 Points). Convexity. For each of the following problems, determine if they are convex or not , by looking at the constraints and the objective function. Justify your answers. (3 points for each problem) ( a ) min x + 10 y - z ( b ) max 5 x - 10 y + 2 z s.t. x - y + 3 z ≤ 1 s.t. 12 x + y + 3 z ≥ 5 4 x ≥ 50 2 y ≤ 20 y - 5 z ≤ 0 x - 2 y = 0 ( c ) max x + 2 y ( d ) min (2 x - y ) 2 s.t. x + y ≤ 4 s.t. x - y = 1 2 x - y ≤ 4 e x ≤ 2 x, y ∈ Z ( e ) min 2 x 2 + 4 y 2 + xy ( f ) min x 2 + y 2 + 3 xy s.t. 12 x + 25 y ≥ 21 s.t. 10 x + 10 y ≤ 100 100 x - y = 0 2 x + 3 y ≤ 3 x 2 + y 2 = 1 2 x 2 + 2 y 2 + xy ≤ 1 ( g ) min x 2 + e y + 5 z ( h ) min 2 x 2 + 2 y 2 - 2 xy s.t. e x + e z ≤ 2 s.t. x 2 + y 4 ≤ 2 x 2 + z 2 + 3 xy ≤ 1 2 x + y ≥ 1 x + 2 y = 0 Lehigh University Page 3 of 7

ISE 426 Homework #1–Due via Course Site at 9 AM on Feb 14, 2022 Spring 2022 Question 4 (20 Points). LP Graphical Method. Consider the two-variable Linear Program below: max 4 x 1 + 3 x 2 s.t. x 1 + x 2 ≤ 4 5 x 1 + 3 x 2 ≤ 15 x 1 + 2 x 2 ≤ 7 x 1 ≥ 0 , x 2 ≥ 0 and answer the following questions about it: 1. ( 12 points) Use the graphical method to solve the Linear Program (provide optimal solution and optimal value of the problem) 2. ( 2 points) To what class does this Linear Program belongs? 3. ( 3 points) Suppose that you are allowed to change only the values of the right hand side of the third inequality of the problem (i.e., change 7). What change of this value would lead to a problem that is infeasible? 4. ( 3 points) What would be the optimal solution of the Linear Program if suddenly we are told that the third constraint of the Linear Program must be satisfied with equality, instead of less than or equal; namely, instead of x 1 + 2 x 2 ≤ 7, we have x 1 + 2 x 2 = 7. Lehigh University Page 4 of 7

ISE 426 Homework #1–Due via Course Site at 9 AM on Feb 14, 2022 Spring 2022 Question 6 (20 Points). Linear Programming Modeling. In a machine shop, to produce a car engine, there are three necessary major components, C 1 , C 2 , and C 3 , and they need to be assembled. These components can be manufactured from the machine shop or purchased from outside sources. The costs per unit of components, if produced internally (internal costs exclude labor costs) or purchased externally, are as follows. Component C 1 ($) C 2 ($) C 3 ($) Production cost 49 60 52 Purchase price 65 81 73 For the internal manufacture of the components and the final assembly of the car engine, labor and machine time on two machines, M 1 and M 2 , are required. The requirements are as follows. Labor Machine Time Machine Time (hr/unit) M 1 (min/unit) M 2 (min/unit) Manufacture of C 1 0.3 10 8 Manufacture of C 2 0.5 15 20 Manufacture of C 3 1.0 13 12 Final assembly 7 35 25 Each week the shop has available 1600 hours of labor at a cost of $20 per hour, 400 hours of overtime at a cost of $30 per hour, and 180 hours of machine time for M 1 and 200 hours for M 2 . The profit from each engine is $425 per unit. 1. (15 points) Formulate a linear program to find the optimal production plan that maximizes the net profit (sales revenue minus manufacturing costs, purchasing costs, and labor costs). In particular, state the problem’s ( Hint : Use two sets of decision variables to model the quantity of components that are manufactured and purchased. Use two decision variables to separtely model labor regular working hour and labor overtime.) (a) (5 points) Decision variables. (b) (3 points) Objective. (c) (7 points) Constraints. 2. (5 points) Suppose now that additional unit of engine sold beyond 20 units can only pro- duce a profit of $350 instead of $425 (due to discount offered to customers). Modify the mathematical program you proposed in part 1 to take this new policy into consideration. (It is fine to write only the parts of your original mathematical formulation that need to be changed.) Lehigh University Page 6 of 7

ISE 426 Homework #1–Due via Course Site at 9 AM on Feb 14, 2022 Spring 2022 Question 7 (6 Points). • (3 points) What was your favorite question in this homework? And Why? • (3 points) What was the most challenging question? And why? Lehigh University Page 7 of 7