MT 601 Optimization Methods of Operations Research Assignment 1 PDF

MT 601: Optimization Methods of Operations Research ASSIGNMENT 1 20-12-2024 1. Consider the dual of the following linear programming problem: Max z = c T x subject to Ax = b , x  0 , Let x * be a candidate sol...

MT 601: Optimization Methods of Operations Research ASSIGNMENT 1 20-12-2024 1. Consider the dual of the following linear programming problem: Max z = c T x subject to Ax = b , x  0 , Let x * be a candidate solution for the primal problem. a. Verify that if y * satisfies the constraints Ax * = b and x *  0 then it is feasible for the dual problem. b. If x * is not feasible, what condition must be violated in order for x * to be dual infeasible? 2. Consider the dual of the following linear programming problem: Min w = bT y subject to AT y  c , y  0 , Let y * be a candidate solution for the dual problem. a. Verify that if y * satisfies the constraints AT y *  c and y *  0 then it is feasible for the dual problem. b. If y * is not feasible, what condition must be violated in order for y * to be dual infeasible? 3. Explain the difference between the Weak Duality Theorem and the Strong Duality Theorem. Provide an example to illustrate each concept. 4. Prove the Weak Duality Theorem for the following primal and dual programs: 5. Prove the Strong Duality Theorem for a primal-dual pair assuming they satisfy the Slater’s condition. 6. Discuss the role of complementary slackness in verifying optimality for primal and dual solutions. a. Determine whether the given primal and dual solutions satisfy the complementary slackness condition: 1 7. Explain the concept of dual feasibility and primal feasibility. How do they relate to the duality theorems? 8. Solve the dual problem explicitly given the following primal solution: 9. How does sensitivity analysis in linear programming relate to the dual problem? 10. Use the Karush-Kuhn-Tucker (KKT) conditions to find the dual variables for the following optimization problem: 11. Consider the following primal problem: a. Solve both the primal and dual problems. b. Verify the Strong Duality Theorem for the above problem. c. Using complementary slackness, explain the relationship between the primal and dual solutions when both are optimal. d. If one constraint in the primal problem is removed, how would the dual problem change, and what impact would it have on complementary slackness? e. Propose a modification to the problem where one of the constraints becomes non- binding. Discuss the effect on the optimal solutions using complementary slackness. f. If the primal problem has an unbounded solution, discuss the implications for the dual problem according to the strong duality theorem. 2 12. Consider the following dual problem: a. Solve both the primal and dual problems. b. Using complementary slackness conditions, verify that the optimal values of the primal and dual problems are equal. c. Discuss the implications of complementary slackness in a scenario where both the primal and dual problems have infeasible solutions. d. If the objective functions were modified, explain how the complementary slackness conditions would adjust. e. Explain the significance of slackness in the context of dual variables. How does complementary slackness help in identifying the tightness of constraints? f. How does the strong duality theorem impact practical optimization problems in real- world applications such as resource allocation or transportation? 13. Consider the optimization problem: a. Use the method of Lagrange multipliers to find the critical points. b. Determine whether the critical points correspond to a maximum or minimum by using the second-order conditions. c. Find the value of the objective function at the optimal point and explain whether it represents a maximum or minimum. 14. Given the function f ( x, y) = x 3 − 3xy2 determine the critical points and investigate whether they are saddle points. a. Find the critical points of f ( x, y ). b. Use the second-order derivative test to classify the critical points. c. Show that (0,0) is a saddle point and discuss its geometric interpretation. 3 15. Consider the function f ( x, y) = 3x 2 + 4 y 2 − 2 xy + 5 x − 6 y a. Find the critical points of f ( x. y ). b. Determine whether the critical points correspond to a local maximum, local minimum, or saddle point using the second-order conditions. c. Find the global maximum or minimum, if any, over the region x, y  [−2,2]. 16. Consider the following optimization problem: Min f ( x) = x 2 + 4 y 2 subject to 2 x + y = 4 , y  0 a. Find the dual of the given problem and formulate the Lagrangian. b. Using the KKT conditions, find the optimal solutions for both the primal and dual problems. c. Discuss the relationship between the primal and dual optimal values. 17. Consider the piecewise function defined as: a. Show that f ( x. y ) is convex for x  . b. Prove that the point where the pieces join, x = 2 , is not a point of non-differentiability for the function. c. Investigate the convexity of the function for a different joining point, say x = 3 , and discuss the impact on the function's convexity. 18. Consider the following linear program in standard form: a. Formulate the dual of this linear program. b. Prove that under the strong duality theorem, the optimal values of the primal and dual are equal. c. Use the complementary slackness conditions to find the optimal solution of the primal and dual problems. 4