課程名稱︰最適化方法
課程性質︰工商管理學系二年級以上選修
課程教師︰蔣明晃
開課學院：管理學院
開課系所︰工商管理學系
考試日期︰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)