数据、模型与决策(运筹学)课后习题和案例答案017s.doc

数据、模型与决策(运筹学)课后习题和案例答案017s

———————————————————————————————— 作者：
———————————————————————————————— 日期：

2

个人收集整理 勿做商业用途
CD SUPPLEMENT TO CHAPTER 17
MORE ABOUT THE SIMPLEX METHOD
Review Questions
17s。1-1 No.
17s.1—2 The adjacent corner points that are better than the current corner point are candidates to be the next one.
17s。1-3 The best adjacent corner point criteria and best rate of improvement criteria.
17s.14 The simplex method starts by selecting some corner point as the initial corner point.
17s。1-5 If none of the adjacent corner points are better (as measured by the value of the objective function) than the current corner point， then the current corner point is an optimal solution。
17s。1-6 Choose the best adjacent corner point.
17s.1-7 Choose the next corner point by picking the adjacent corner point has the lowest objective function value rather than highest when getting started. There may only be one adjacent corner point if the feasible region is unbounded。
17s。2-1 It is analagous to standing in the middle of a room and looking toward one corner where two walls and the floor meet.
17s。2—2 There are three (at most) adjacent corner points.
17s。2-3 Yes。
17s。2-4 With three decision variables， the constraint boundaries are planes.
17s.2-5 A system of n variables and n equations must be solved。
17s.3-1 The name derives from the fact that the slack variable for a ≤ constraint represents the slack （gap） between the two sides of the inequality。
17s。3—2 A nonnegative slack variable implies that the left-hand side is not larger than the right—hand side。
17s。3—3 For the Wyndor problem， the slack variables represent unused production times in the various plants.
17s.3—4 It is much simpler for an algebraic procedure to deal with equations than with inequalities.
17s。3-5 A nonbasic variable has a value of zero。
17s.3-6 A basic feasible solution is simply a corner point that has been augmented by including the values of the slack variables。
17s。3—7 A surplus variable gives the amount by which the left—hand side of a ≥ constraint exceeds the right—hand side。
17s.4-1 (1) Determine the entering basic variable; (2） determine the leaving basic variable; （3) Solve for the new basic feasible solution
17s。4—2 The entering basic variable is the current nonbasic variable that should become a basic variable for the next basic feasible solution. Among the nonbasic variables with a negative coefficient in equation 0, choose the one whose coefficient has the largest absolute value to be the entering basic variable。
17s。4—3 The leaving basic variable is the current basic variable that should become a nonbasic variable for the next basic feasible solution. For each equation that has a strictly positive coefficient （neither zero nor negative) for the entering basic variable, take the ratio of the right—hand side to this coefficient. Identify the equation that has the minimum ratio, and select the basic variable in this equation to be the leaving basic variable.
17s.4—4 The initialization step sets up to start the iterations and finds the initial basic feasible solution.
17s.4—5 Examine the current equation 0。 If none of the nonbasic variables have a negative coefficient, then the current basic feasible solution is optimal。
17s。4-6 （1） Equation 0 does not contain any basic variables; (2） each of the other equations contains exactly one basic variable； (3） an equation’s one basic variable has a coefficient of 1; （4) an equation’s one basic variable does not appear inn any other equation。
17s。4-7 The tabular form performs exactly the same steps as the algebraic form, but records the information more compactly。
Problems
17s.1

Getting Started： Select （0， 0) as the initial corner point.
Checking for Optimality: Both （0， 3) and （3, 0） have better objective function values (Z = 6 and 9， respectively）, so （0, 0） is not optimal。
Moving On: （3, 0） is the best adjacent corner point， so move to (3, 0).
Checking for Optimality： （2， 2) has a better objective function value （Z = 10), so (3， 0) is not optimal。
Moving On： Move from (3, 0） to （2， 2).
Checking for Optimality: （0， 3) has lower objective function values （Z = 6)， so (2, 2） is optimal.个人收集整理，勿做商业用途文档为个人收集整理,来源于网络
17s。2

Getting Started： Select （0, 0) as the initial corner point.
Checking for Optimality： Both （0, 2。667) and （4, 0) have better objective function values (Z = 5.333 and 4， respectively）, so （0, 0） is not optimal。
Moving On： (0, 2。667) is the best adjacent corner point, so move to (0， 2。667).
Checking for Optimality: （2, 2) has a better objective function value （Z = 6), so （0, 2。667) is not optimal.
Moving On: Move from (0， 2。667） to （2， 2).
Checking for Optimality： （4, 0） has a lower objective function values （Z = 4）， so (2, 2） is optimal.文档为个人收集整理，来源于网络个人收集整理，勿做商业用途
17s。3

Getting Started： Select （0， 0） as the initial corner point。
Checking for Optimality： Both (0， 5) and (4， 0） have better objective function values （Z = 10 and 12, respectively）， so (0, 0) is not optimal.
Moving On： (4， 0） is the best adjacent corner point， so move to (4, 0).
Checking for Optimality: (4， 2) has a better objective function value (Z = 16）, so (4， 0) is not optimal.
Moving On: Move from （4， 0) to (4， 2).
Checking for Optimality： （3， 4） has a better objective function value （Z = 17）， so (4, 2） is not optimal。
Moving On: Move from （4， 2） to （3， 4）。
Checking for Optimality: （0， 5) has a lower objective function values (Z = 10), so (3, 4） is optimal。本文为互联网收集,请勿用作商业用途文档为个人收集整理，来源于网络
17s。4 a）

Getting Started: Select （0, 0) as the initial corner point.
Checking for Optimality： Both （2, 0） and （0， 5） have better objective function values (Z = 4 and 5， respectively）， so (0, 0) is not optimal。
Moving On： （0, 5) is the best adjacent corner point， so move to （0， 5）。
Checking for Optimality： (2, 5） has a better objective function value （Z = 9), so （0, 5) is not optimal。
Moving On： Move from (0， 5) to （2， 5）.
Checking for Optimality: (2, 0) has a lower objective function values (Z = 4）， so (2, 5) is optimal.文档为个人收集整理，来源于网络本文为互联网收集，请勿用作商业用途
b) Getting Started: Select （0， 0) as the initial corner point。
Checking for Optimality: Moving toward either (2， 0） or （0， 5） improves the objective function value， so （0, 0） is not optimal。
Moving On: Moving toward （2, 0） improves the objective function faster than moving toward （0， 5） (a rate of 2 vs。 a rate of 1）, so move to （2, 0）.
Checking for Optimality： Moving toward （2， 5） improves the objective function value， so （2， 0) is not optimal.
Moving On： Move from （2， 0） to (2, 5)。
Checking for Optimality： Moving toward （0, 5） lowers the objective function values, so （2, 5） is optimal。本文为互联网收集，请勿用作商业用途本文为互联网收集，请勿用作商业用途
17s.5 a）

b) The eight corner points are （x1， x2, x3) = （0, 0, 0）， （0， 0, 1), (0， 1， 0), (0, 1， 1), (1, 0, 0), (1, 0， 1）， (1， 1, 0), and (1, 1， 1）。
c) Objective Function： Profit = x1 + 2x2 + 3x3
Optimal Solution: （x1， x2, x3) = (1, 1， 1) and Profit = 6。
Corner Point （x1， x2, x3）
Profit = x1 + 2x2 + 3x3
(0， 0， 0)
0
（0， 0， 1)
3
（0， 1， 0)
2
（0, 1， 1）
5
（1， 0, 0）
1
(1， 0， 1）
4
（1, 1, 0)
3
(1， 1， 1）
6

d） The simplex method would start at (0， 0， 0）, move to the best adjacent corner point at （0， 0， 1）， then to (0, 1, 1）, and finally to the optimal solution at （1， 1， 1).
17s.6 a）

b) The ten corner points are (x1， x2, x3） = （0, 0, 0)， (2， 0, 0)， （2， 2, 0)， (1, 3， 0), (0, 3， 0）， (0， 0， 2）, (2, 0, 2）， (2， 2， 2）, （1， 3, 2）, （0， 3， 2)
c) Objective Function: Profit = 2x1 + x2 – x3
Optimal Solution： (x1， x2 x3) = (2， 2, 0) and Profit = 6.
Corner Point （x1， x2, x3）
Profit = 2x1 + x2 – x3
（0, 0， 0)
0
(2, 0, 0)
4
（2， 2, 0)
6
（1, 3, 0）
5
（0, 3， 0）
3
(0, 0， 2)
–2
（2, 0， 2)
2
(2, 2, 2）
4
（1, 3， 2)
3
(0， 3, 2)
1

d) The simplex method would start at （0， 0， 0）， move to the best adjacent corner point at （2, 0， 0）, and then to the optimal solution at (2， 2, 0).

17s.7 a) s1 = 10 – x2
s2 = 20 – 2x1 – x2
b） s1 ≥ 0 and s2 ≥ 0.
c） x2 + s1 = 10
2x1 + x2 + s2 = 20
d) Values of the slack variables at （x1, x2) = (10, 0) are s1 = 10 and s2 = 0.
The equations for the constraint boundary lines on which （10, 0) lies are
x2 = 0
2x1 + x2 = 20
The corresponding basic feasible solution is (x1， x2， s1, s2） = (10， 0， 10, 0)。
The basic variables are x1 and s1； the nonbasic variables are x2 and s2.
17s。8 a) 25x1 + 40x2 + 50x3 ≤ 500。
b) s ≥ 0.
c) s = 0。
17s.9 a） Objective Function： Profit = 2x1 + x2
Optimal Solution： （x1， x2) = (4， 3) and Profit = 11
Corner Point (x1, x2)
Profit = 2x1 + x2
（0， 0)
0
(5, 0）
10
（4， 3）
11
(0， 5)
5

b) The graphical simplex method would start at (0, 0)， move to the best adjacent corner point at (5, 0)， and finally move to the optimal solution at (4, 3)。
c） 3x1 + 2x2 + s1 = 15
x1 + 2x2 + s2 = 10
d）
Basic Feasible Solution （x1， x2， s1, s2)
Basic Variables
Nonbasic Variables
（0， 0， 15， 10)
s1, s2
x1， x2
(5， 0, 0, 5)
x1, s2
x2， s1
（4, 3, 0, 0）
x1, x2
s1， s2
(0， 5， 5, 0)
x2, s1
x1, s2

e) The graphical simplex method would start at (0， 0, 15, 10), move to the best adjacent corner point at (5， 0, 0， 5), and finally move to the optimal solution at （4, 3， 0, 0）.
17s。10 a） s1 = 2x1 + 3x2 – 21.
s2 = 5x1 + 3x2 – 30。
b) s1 ≥ 0 and s2 ≥ 0.
c） 2x1 + 3x2 – s1 = 21.
5x1 + 3x2 – s2 = 30。
d） Values of the surplus variables at （x1, x2) = (3, 5） are s1 = 0 and s2 = 0.
The equations for the constraint boundary lines on which (3， 5） lies are
2x1 + 3x2 = 21
5x1 + 3x2 = 30
The corresponding basic feasible solution is （x1, x2， s1， s2) = （3, 5， 0， 0)。
The basic variables are x1 and x2； the nonbasic variables are s1 and s2。
17s。11 a) 20x1 + 10x2 ≥ 100。
b） s ≥ 0。
c) s = 0.
17s.12 a）

Getting Started： Select （16， 0) as the initial corner point. (Cost = 32。）
Checking for Optimality: Both （15， 0） and （0， 24） have better objective function values (Cost = 30 and 24, respectively), so (16, 0) is not optimal.
Moving On: (0, 24) is the best adjacent corner point， so move to （0， 24)。 (Cost = 24.）
Checking for Optimality: （0, 20) has a better objective function value (Cost = 20)， so (0, 24) is not optimal.
Moving On: Move from （0， 24） to (0， 20）。 （Cost = 20。)
Checking for Optimality: (7。5， 7.5) has a higher objective function values (Cost = 22.5), so （0， 20) is optimal。 (Cost = 20）。本文为互联网收集，请勿用作商业用途本文为互联网收集,请勿用作商业用途
b) Getting Started: Select (16, 0) as the initial corner point. （Cost = 32。）
Checking for Optimality: Moving toward either (15, 0) or (0， 24） improve the objective function value， so (16， 0) is not optimal.
Moving On: Moving toward （15, 0） improves the objective function at a faster rate (2 per unit) than moving toward （0， 24） (rate = 1/3）， so move to （15, 0)。 (Cost = 30。)
Checking for Optimality: Moving toward （7.5, 7.5) improves the objective function value， so (15， 0） is not optimal.
Moving On: Move from (15， 0) to (7.5， 7.5).
Checking for Optimality: Moving toward （0， 20) improves the objective function value, so （7。5， 7。5) is not optimal。
Moving On： Move from （7.5, 7.5) to (0， 20)。 (Cost = 20。）
Checking for Optimality: Moving toward (0, 24) increases the objective function value, so （0, 20) is optimal. (Cost = 20。)个人收集整理,勿做商业用途本文为互联网收集，请勿用作商业用途
c） Sequence of basic feasible solutions （x1， x2, s1, s2, s3）： （16， 0， 20， 0, 1）, (0, 24, 12, 0， 9)， (0， 20， 0， 8, 5）.
17s.13 a)

Getting Started： Select （0， 0) as the initial corner point。 （Profit = 0.）
Checking for Optimality： Both （7， 0) and (0, 2） have better objective function values （Profit = 7 and 6, respectively), so （0, 0） is not optimal。
Moving On： （7, 0） is the best adjacent corner point， so move to (7, 0）。 （Profit = 7。）
Checking for Optimality: (7, 2） has a better objective function value (Profit = 13), so (7， 0) is not optimal.
Moving On： Move from （7, 0) to (7， 2）。 （Profit = 13.)
Checking for Optimality： （0， 2） has a lower objective function value (Profit = 6), so （7， 2) is optimal. (Profit = 13.)文档为个人收集整理,来源于网络个人收集整理，勿做商业用途
b） Getting Started： Select (0， 0) as the initial corner point。 （Profit = 0.)
Checking for Optimality: Moving toward either （7, 0） and (0， 2) improves the objective function value, so (0, 0） is not optimal.
Moving On: Moving toward (0， 2) improves the objective function value faster than moving toward （7， 0） （rate = 3 toward （0， 2） and 1 toward （7, 0））， so move to (0, 2）. (Profit = 6。)
Checking for Optimality： Moving toward (7, 2） improves the objective function value， so （0， 2） is not optimal.
Moving On: Move from （0， 2) to (7, 2）. (Profit = 13.)
Checking for Optimality: Moving toward (7, 2） decreases the objective function value， so (7， 2） is optimal. （Profit = 13。）本文为互联网收集,请勿用作商业用途个人收集整理，勿做商业用途
c) x1 + s1 = 7
x2 + s2 = 2
d）

Geometric Progression
Algebraic Progression
Iteration
Corner Point
CBE
Nonbasic
Variables
Basic
Variables
Basic
Feasible
Solution
(x1, x2, s1, s2)
0
（0， 0)
3， 4
x1, x2
s1, s2
(0， 0， 7， 2）
1
(0， 2）
2， 3
x1， s2
x2, s1
(0， 2， 7, 0)
2
（7， 2）
1, 2
s1， s2
x1， x2
（7， 2, 0, 0）

e) Iteration 0：
0） Z –1x1 –3x2 +0s1 +0s2 = 0
1) +1x1 +0x2 +1s1 +0s2 = 7
2) +0x1 +1x2 +0s1 +1s2 = 2
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0。
Iteration 1：
0) Z –1x1 +0x2 +0s1 +3s2 = 6
1) +1x1 +0x2 +1s1 +0s2 = 7
2） +0x1 +1x2 +0s1 +1s2 = 2
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0， s2 ≥ 0.
Iteration 2：
0） Z +0x1 +0x2 +1s1 +3s2 = 13
1) +1x1 +0x2 +1s1 +0s2 = 7
2) +0x1 +1x2 +0s1 +1s2 = 2
x1 ≥ 0, x2 ≥ 0， s1 ≥ 0, s2 ≥ 0.
17s.14 a）

Getting Started: Select 0， 0） as the initial corner point. (Profit = 0.）
Checking for Optimality: Both （2， 0） and (0, 2） have better objective function values （Profit = 2 and 4, respectively)， so （0, 0) is not optimal.
Moving On： （0， 2） is the best adjacent corner point， so move to (0， 2）. (Profit = 4.)
Checking for Optimality: （1， 2) has a better objective function value （Profit = 5）, so （2， 0) is not optimal.
Moving On: Move from (2， 0） to (1, 2)。 （Profit = 5.）
Checking for Optimality: (2， 1) has a lower objective function value （Profit = 4）， so (1， 2） is optimal. (Profit = 5.)个人收集整理,勿做商业用途本文为互联网收集，请勿用作商业用途
b） Getting Started： Select (0, 0) as the initial corner point。 （Profit = 0.）
Checking for Optimality： Moving toward either （2， 0） and (0， 2) improves the objective function value， so （0, 0） is not optimal.
Moving On: Moving toward (0, 2） improves the objective function value faster than moving toward （2, 0） （rate = 2 toward （0， 2） and 1 toward （2， 0）)， so move to （0, 2)。 (Profit = 4。)
Checking for Optimality： Moving toward （1, 2） improves the objective function value, so （0， 2） is not optimal。
Moving On: Move from (0, 2） to （1, 2). (Profit = 5。）
Checking for Optimality: Moving toward (2，