课程名称︰最适化方法 课程性质︰工商管理学系二年级以上选修 课程教师︰蒋明晃 开课学院：管理学院 开课系所︰工商管理学系 考试日期︰2013年04月15日，09:10-12:10 考试时限：180分钟 是否需发放奖励金：是 试题 : Optimization Method　　　　　　　　Midterm Exam　　　　　　　　　　Spring 2013 1. Each of the following tableaus represents the end of an iteration to a 　 maximiztion problem. Selecet one or more of the following conditions that 　 best describe the results indicated by each tableau, and then answer any 　 question in parentheses.(18 points)(Note: M is a large number, s_i is a 　 slack variable, e_i is a excess variable, a_i is a artificial variable) 　(1).Improvement in the value of the objective function is still possible. 　　　(Identify the variable should be brought into solution and the variable 　　　should be removed. And determine the total improvement in the objective 　　　function) 　(2).The original problem is infeasible. (Why?) 　(3).The solution is degenerate. (Which variable causes degenerate?) 　(4).The solution represented by the tableau is not a basic feasible solution. 　　　(Why?) 　(5).The unique solution is obtained. 　(6).One of the optimal solutions has been obtained, but an alternative 　　　optimum exists. (Find the alternative solution) 　(7).The optimal solution to the original problem is unbounded. (Why?) 　Tbleau 1 ┌─┬──┬─┬─┬──┬──┐ │ｚ│ x1 │x2│s1│ s2 │rhs │ ├─┼──┼─┼─┼──┼──┤ │１│ ０ │０│０│ ３ │ ６ │ ├─┼──┼─┼─┼──┼──┤ │０│17/2│０│１│-7/2│２８│ ├─┼──┼─┼─┼──┼──┤ │０│-1/2│１│０│ 1/2│ １ │ └─┴──┴─┴─┴──┴──┘ 　Tableau 2 ┌─┬─┬───┬─┬──┬──┐ │ｚ│x1│　x2　│s1│ s2 │rhs │ ├─┼─┼───┼─┼──┼──┤ │１│０│-1/12 │０│ 1/3│ ０ │ ├─┼─┼───┼─┼──┼──┤ │０│０│-1/12 │１│ 1/3│ ０ │ ├─┼─┼───┼─┼──┼──┤ │０│１│ -1/3 │０│ 1/3│ ０ │ └─┴─┴───┴─┴──┴──┘ 　Tableau 3 ┌─┬─┬─┬──┬──┬─┬──┐ │ｚ│x1│x2│ s1 │ s2 │s3│rhs │ ├─┼─┼─┼──┼──┼─┼──┤ │１│０│０│ 7/4│-1/2│０│１６│ ├─┼─┼─┼──┼──┼─┼──┤ │０│０│１│ １ │－１│０│ ２ │ ├─┼─┼─┼──┼──┼─┼──┤ │０│１│０│-1/4│ 1/2│０│ ２ │ ├─┼─┼─┼──┼──┼─┼──┤ │０│０│０│-3/4│ 1/2│１│ ０ │ └─┴─┴─┴──┴──┴─┴──┘ 　Tableau 4 ┌─┬─┬─┬─┬──┬──┐ │ｚ│x1│x2│s1│ s2 │rhs │ ├─┼─┼─┼─┼──┼──┤ │１│０│０│２│M-１│ ５ │ ├─┼─┼─┼─┼──┼──┤ │０│１│０│１│ -1 │ １ │ ├─┼─┼─┼─┼──┼──┤ │０│０│１│-1│ ２ │ ２ │ └─┴─┴─┴─┴──┴──┘ 　Tableau 5 ┌─┬─┬────┬─┬─┬────┬────┐ │ｚ│x1│ 　x2　 │e1│a1│　 a2　 │　rhs 　│ ├─┼─┼────┼─┼─┼────┼────┤ │１│０│(M-6)/3 │Ｍ│０│(5M-3)/3│-4-10M/3│ ├─┼─┼────┼─┼─┼────┼────┤ │０│０│　-1/3　│-1│１│　-2/3　│　10/3　│ ├─┼─┼────┼─┼─┼────┼────┤ │０│１│　 2/3　│０│０│　 1/3　│　4/3　 │ └─┴─┴────┴─┴─┴────┴────┘ 　Tableau 6 ┌─┬─┬──┬─┬─┬──┬──┬──┐ │ｚ│x1│ x2 │x3│s1│ s2 │ s3 │rhs │ ├─┼─┼──┼─┼─┼──┼──┼──┤ │１│０│ ５ │０│０│１０│１０│380 │ ├─┼─┼──┼─┼─┼──┼──┼──┤ │０│０│－２│０│１│ ２ │－８│４４│ ├─┼─┼──┼─┼─┼──┼──┼──┤ │０│０│－２│１│０│ ２ │－４│２８│ ├─┼─┼──┼─┼─┼──┼──┼──┤ │０│１│1.25│０│０│-0.5│ 1.5│－３│ └─┴─┴──┴─┴─┴──┴──┴──┘ 2. The starting and current tableaux of a given problem are shown below. 　 Find the values of the unknowns A thorugh L. 　Starting Tableau ┌─┬─┬─┬─┬─┬─┬──┐ │ｚ│x1│x2│x3│x4│x5│RHS │ ├─┼─┼─┼─┼─┼─┼──┤ │１│Ａ│１│-2│０│０│ ０ │ ├─┼─┼─┼─┼─┼─┼──┤ │０│Ｂ│Ｃ│ｄ│１│０│ ６ │ ├─┼─┼─┼─┼─┼─┼──┤ │０│-1│３│ｅ│０│１│ １ │ └─┴─┴─┴─┴─┴─┴──┘ 　Current Tableau ┌─┬─┬─┬─┬──┬─┬──┐ │ｚ│x1│x2│x3│ x4 │x5│RHS │ ├─┼─┼─┼─┼──┼─┼──┤ │１│０│７│Ｊ│ Ｋ │Ｌ│ ９ │ ├─┼─┼─┼─┼──┼─┼──┤ │０│Ｇ│２│-1│ 1/2│０│ Ｆ │ ├─┼─┼─┼─┼──┼─┼──┤ │０│Ｈ│Ｉ│１│ 1/2│１│ ４ │ └─┴─┴─┴─┴──┴─┴──┘ (24 points) 3. 　Consider the following problem. 　Maximize z = 3x1 + 4x2 + x3 + 5x4 　　　　s.t　x1 + 2x2 + x3 + 2x4 ≦ 5 　　　　　　2x1 + 3x2 + x3 + 3x4 ≦ 8 　　　　　　x1,x2,x3,x4 ≧ 0 　a. Construct the Dual problem.(4%) 　b. Solve the Dual problem.(4%) 　c. Find the primal problem using the Theorem of Complementary Slackness. 4. Consider the following problem. 　 Maximize Z = 2x1 + 4x2 + 3x3, 　subject to 　　x1 + 3x2 + 2x3 ＝ 20 　　x1 + 5x2　　　 ≧ 10 and 　　x1≧0,　x2≧0,　x3≧0. 　　＿　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 ＿ Let x4 be the artificial variable for the first constraint. Let x5 and x6 be the surplus variable and artificial variable, respectively, for the second constraint. 　　You are now given the information that a portion of the final simplex tableau is as follows: 　　　　│　　│　　　Coefficient of:　　 　｜ 　Basic │　　├─┬─┬─┬─┬──┬─┬─┤Right Variable│Eq. │Ｚ│x1│x2│x3│ x4 ｜x5｜x6｜ side ────┼──┼─┼─┼─┼─┼──┼─┼─┼─── 　　Z　 ｜(0) ｜　｜　｜　｜　｜M+2 ｜０｜Ｍ｜ ────┼──┼─┼─┼─┼─┼──┼─┼─┼─── 　　x1　｜(1) ｜　｜　｜　｜　｜ １ ｜０｜０｜ ────┼──┼─┼─┼─┼─┼──┼─┼─┼─── 　　x5　｜(2) ｜　｜　｜　｜　｜ １ ｜１｜-1｜ Please dentify the missing numbers in the final simplex tableau. Show your calculations. (24 points) 5. Consider the following problem. 　 Maximize Z = 3x1 + x2 + 2x3, subject to 　　x1 - x2 + 2x3 ≦ 20 　 2x1 + x2 - x3 ≦ 10 and 　x1≧0,　x2≧0,　x3≧0. Let x4 and x5 denote the slack variables for the respective functional constraints. After we apply the simplex method, the final simplex tableasu is 　　　　│　　｜　Coefficient of: 　　｜ 　Basic │　　├─┬─┬─┬─┬─┬─┤Right Variable│Eq. │Ｚ│x1│x2│x3│x4｜x5｜ side ────┼──┼─┼─┼─┼─┼─┼─┼─── 　　Z　 ｜(0) ｜１｜８｜０｜０｜３｜４｜ 100 ────┼──┼─┼─┼─┼─┼─┼─┼─── 　　x3　｜(1) ｜０｜３｜０｜１｜１｜１｜ 30 ────┼──┼─┼─┼─┼─┼─┼─┼─── 　　x2　｜(2) ｜０｜５｜１｜０｜１｜２｜ 40 (a) Use algebraic analysis to find the allowable range to stay optimal for each 　　c_j. (12 points) (b) Use algebraic analysis to find the allowable range for each b_i.(10 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.170.204.174 ※ 编辑: t0444564 来自: 118.170.204.174 (04/20 23:42)