課程名稱︰最適化方法 課程性質︰工商管理學系二年級以上選修 課程教師︰蔣明晃 開課學院：管理學院 開課系所︰工商管理學系 考試日期︰2013年06月17日，09:00-12:10 考試時限：190分鐘 是否需發放獎勵金：是 試題 : Final Exam of Optimization Methods　　　　　　　　　　　　2013/6/17 1. (9 points) Consider the following quadratic programming problem. 　　　　　　　　Maximize f(X) = 2x1 + 3x2 - x1^2 - x2^2 　　Subgect to x1 + x2 ≦ 2, and x1 ≧ 0, x2 ≧ 0 　　a. Use the KT conditions to derive an optimal solution directly. (5 points) 　　b. Now suppose that this problem is to besolved by the Wolfe's method. 　　　 Formulate the linear programming problem that is to be addressed 　　　 explicitly, and then identify the additional complementary constraint 　　　 that is enforced automatically by the algorithm. 2. (16 points) For the following functions, determine whether the given 　　stationary point corresponding to a local minimum, local maximum, or saddle 　　point. 　　a. f(x,y) = (1/3)x^3 + xy^2 - 4xy + 1 at point (0,4) 　　b. f(x,y) = 3x^2 - xy + y^2 at point (0,0) 　　c. f(x,y) = (1/3)x^3 - (1/3)y^2 + 3xy + 2x - 2y at point (1,-1) 　　d. f(x,y,z) = (-1/4)(x^(-4) + y^(-4) + z^(-4)) + yz -x -2y - 2z 　　　 at point (1,1,1) 3. A company is planning its advertising strategy for next year for its three major products. Since the three products are quite different, each adertising effort will focus on a single product. In units of millions of dollars, a total of 6 available for advertising next year, where the advertising expenditure for marketing has established the objective: Determine how much to spend on each product in order to maximize total sales. The following table gives the estimated increase in sales (in appropriate units) for the different advertising expenditures. ┌──────┬────┐ │Advertising ｜ Product｜ │Expenditrue │ 1 2 3｜ ├──────┼────┤ ｜　　 1　　　｜ 7 4 6｜ ｜　　 2　　　｜10 8 9｜ ｜　　 3　　　｜14 11 13｜ ｜　　 4　　　｜17 14 15｜ └──────┴────┘ Formulate this problem to be a dynamic programming problem and solve it. (20 points) 4. Consider the following convex programming problem 　　　　Maximize f(x) = 10x1 - 2x1^2 - x1^3 + 8x2 - x2^2, 　subject to 　　　　x1 + x2 ≦ 2, x1 ≧ 0, x2 ≧ 0. (a) Use the KKT conditions to demonstrate that (x1,x2) = (1,1) is not an optimal solution. (10 points) (b) Use the KKT conditions to derive an optimal solution. (10 points) 5. The parameter table given below shows the transportation problem formulation for a particular problem. Suppose that the current solution for this transportation problem has the following basic variables: 　　x12 = 30,　x13 = 30,　x15 = 15,　x24 = 15,　x25 = 60,　x31 = 20,　x34 = 25 Is this current solution an optimal solution? If not, derive the optimal solution for this transportation problem. (20 points) 　　　　｜Cost per Unit Distrbuted｜ 　　　　├────────────┤ 　　　　｜　Destination(Product)　｜ 　　　　｜　　1 2 3 4 5(D)　　｜Supply ────┼────────────┼─── 　　　 1｜ 　41 27 28 24　　0　　 ｜　75 Source 2｜ 　40 29 Ｍ 23　　0　　 ｜　75 　　　 3｜ 　37 30 27 21　　0　　 ｜　45 ────┼────────────┼─── Demand　｜ 　20 30 30 40 　75　　 ｜ ────┴────────────┴─── 6. Consider the minimum cost flow problem shown below, arc AD and arc BE have finite capacity (the capacity arc AD is 40 and the acpacity of arc BE is 40). The rest of arcs are unlimited capacity. Suppose there is an initial basic solution which the flow through arc AC is 130, the flow through arc BA is 80, the flow through arc CD is 70, and the flow through arc CE is 60. Use network simplex method to solve this problem. (15 points) 　　　　　　6 　50 Ａ→→→→→Ｄ -70 　　　↑↘4　　 ↗ 　　　↑　↘　↗3 　　 1↑　　Ｃ 　　　↑ 2↗　↘5 　　　↑↗　　　↘ 　80　Ｂ→→→→→Ｅ -60 　　　　　　5　 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.252.31