Combinatorial Optimization — DU B.Sc. (Hons) Computer Science Previous Year Question Papers

4. (a) Use Line Search method to minimize (10) (b) How is golden ratio, c = 1.618 derived in the Golden Section Rule. (5) 5. (a) Briefly explain any two methods used for finite-difference approximating derivatives? (7) (b) Find out the error of function f(0) = 03 using approximating gradient method. (8) 6. (a) How does an individual determine if a linear programming model has the unique/multiple/ infeasible solution when solved using I. Graphical Method II. Simplex Method? Write appropriate reason for each type of solution for each method. (7) (b) Find the points on a circle x? + y? = 80, which are the closest and the farthest from (1,2) using Lagrangian method. (8) 7. Use Conjugate Gradient method to minimize f(x, 2) = 3x2- 4x, x2 + 2x2 + 4x, + 6, where (x,X) E I2 with (0,0) as an initial solution. Can the Steepest descent method be used for this problem? Give appropriate reason for your answer. (15) 4. Answer all parts of a question together. 1. (a) What is a stationary point on a curve? Explain its three types. (5) (b) Formulate the linear programming problem for the following: (5) A company produces two types of computers (say A and B). Each computer of the type 'A' requires twice as much production time as that of type 'B'. If all computers are of type 'B' only, the company can produce a total of 500 computers a day. The market limits daily sales of type 'A' and type 'B' to 150 and 250 computers respectively. Assuming that the profit per computer for type 'A' and type 'B' is Rs. 8 (in thousands) and Rs. 5 (in thousands) respectively. (c) Solve the following constrained optimization ; problem using Lagrangian method : (5) f(x) = 2x + y subject to given constraint x2 + y = 1. (d) Find the point of global and local maxima for the following function : (5) f(x) = x3 - 12x2 + 36x + 17 on the interval (e) Define a Unimodal function. Describe any two methods to optimize a Unimodal function. (5) (f) Use Newton's method to minimize f(x,, X2) = 8x?, - 4x,x, + 5x? using initial approximation (5,2). (a) Define a convex function. Check whether the following function is convex or not f(x,y) = {x + y ≤ 6}. (5) (b) Consider the following Linear Programming subject to the following constraints: Solve the given problem graphically and find the optimal solution. 3. Consider the following Linear Programming Problem: max Z= 2x, - x2 + 3xg, subject to the following constraints : (a) Solve the given problem using Simplex method. (b) Check whether it has multiple optimal solutions or not? If yes, find three different optimal solutions.