Solns to 2nd Homework
2 (a) the feasible region is the shaded part. And BFS are identified by A, B, C, D, E which
are vetex points of the feasible region.
4
2E D
1 Feasible Region
C
0A B
−1
−2
−3
−4
0 1 2 3 4 5 6 7 8
vertice:A(0, 0), B(0, 2), C(2, 2), D(14/3, 2/3), E(4, 0).
(b) Canonical form of constraint.
x1 + 2x2 + s1 = 6
x1 − x2 + s2 = 4
x2 + s3 = 2
with xj ≥0, j = 1, 2, 3. sj ≥ 0, j = 1, 2.
CPF corresponding BFS
(0, 0) (0, 0, 6, 4, 2)
(4, 0) (4, 0, 2, 0, 2)
(14/3, 2/3) (14/3, 2/3, 0, 0, 4/3)
(2, 2) (2, 2, 0, 4, 2)
(0, 2) (0, 2, 2, 6, 0)
(c) from the simplex table, we see the sequence is
(d) replace the optimal solution into constraints, we know that constraint 1, and 2 are tight
constraint, the solution makes equal. And constraint 3 is a slack constraint.
1
3 (a) The vertices are:(0, 0),(1, 0),(1, 80),(0, 100) by graphical way.From these vertices, we
get the corresponding BFS
120
100 D
80 C
60
40 Feasible Region
20
0A B
0 0.5 1 1.5 2 2.5 3 3.5 4
CPF corresponding BFS
(0, 0) (0, 0, 1, 100)
(1, 0) (1, 0, 0, 80)
(1, 80) (1, 80, 0, 0)
(0, 100) (0, 100, 1, 0)
(b) Do the simplex and find that the iteration goes this way: A,B,C,D in order.
iteration(0)
Basic Variable Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 -10 -1 0 0 0
s1 1 0 1 0 1 0 1 1
s2 2 0 20 1 0 1 100 5
iteration(1)
Basic Variable Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 0 -1 10 0 10
x1 1 0 1 0 1 0 1 NA
s2 2 0 0 1 -20 1 80 80
iteration (2)
Basic Variable Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 0 0 -10 1 90
x1 1 0 1 0 1 0 1
x2 2 0 0 1 -20 1 80 NA
iteration (3)
2
Basic Variable Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 10 0 0 1 100
s1 1 0 1 0 1 0 1
x2 2 0 20 1 0 1 100
3
4 The canonical form of this lP problem is:
Z − 5x1 + x2 = 0
x1 − 3x2 + s1 = 1
x1 − 4x2 + s2 = 3
with xj ≥0, j = 1, 2. sj ≥ 0, j = 1, 2.
See the simplex form:
iteration(0)
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 -5 1 0 0 0
s1 1 0 1 -3 1 0 1 1
s2 2 0 1 -4 0 1 3 3
iteration (1)
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 0 -14 5 0 0 5
x1 1 0 1 -3 1 0 1
s2 2 0 0 -1 -1 1 2
Note that the candidate entering variable is x2 , but there is no constraint on the entering
value, this means the entering value can be any number we want. So the LP problem is
unbounded.
4
5 Canonical form of this LP problem:
Z = 4x1 + 3x2 + 6x3
subject to:
3x1 + x2 + 3x3 + s1 = 30
2x1 + 2x2 + 3x3 + s2 = 30
with xj ≥0, j = 1, 2, 3. sj ≥ 0, j = 1, 2.
Initialization:First let x1 , x2 x3 be 0, then
Z − 4x1 − 3x2 − 6x3 = 0
3x1 + x2 + 3x3 + s1 = 30
2x1 + 2x2 + 3x3 + s2 = 40
Deciding entering variable: See the coefficient of x3 is -6,which is the negative max, thus x3
is the entering variable.
Deciding the leaving variable: see
3x3 ≤ 30, x1 ≤ 10
3x3 ≤ 40, x2 ≤ 40/3
thus the leaving variable is s1 .
Gauss elimination: Result is
Z + 2x1 − x2 + 2s1 = 60
x1 + 1/3x2 + x3 + 1/3s1 = 10
−x1 + x2 − s1 + s2 = 10
Deciding entering variable: See now the coefficient of x2 is -1,which is the negative max, thus
x2 is the entering variable.
Deciding the leaving variable: see
5
1/3x2 ≤ 10, x2 ≤ 30
x2 ≤ 10, x2 ≤ 10
thus the leaving variable is s2 .
Gauss elimination: Result is
Z + x1 + s1 + 2s2 = 70
4/3x1 + x3 + 2/3s1 − 1/3s2 = 20/3
−x1 + x2 − s1 + s2 = 10
Thus the max z=70 when x1 = 0, s1 = 0, s2 = 0, x2 = 10f romthesencondequationandx3 =
20/3f romthef irstequation.
6
6 The canonical form is
maximizeZ = 2x1 + 3x2 − M s2
subject to:
x1 + 2x2 + s1 = 4
x1 + x2 + s2 = 3
with xj ≥0, j = 1, 2, sj ≥ 0, j = 1, 2.
The simplex table goes
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 -2 -3 0 M 0
s1 1 0 1 2 1 0 4
s2 2 0 1 1 0 1 3
after Gauss elimination:
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 -M-2 -M-3 0 0 -3M
s1 1 0 1 2 1 0 4 2
s2 2 0 1 1 0 1 3 3
iteration(0)
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 -M-2 0 (M+3)/2 0 6-M
x2 1 0 1/2 1 1/2 0 2 4
s2 2 0 1/2 0 -1/2 1 1 2
iteration(01)
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 0 0 1 M+1 7
x2 1 0 0 1 0 -1 1
x1 2 0 1 0 -1 2 2
Thus the maximal Z = 7, when x1 = 2, x2 = 1.
7
7 Canonical form for the first phase:
maximize − Z = −a1 − a2
with constraints
x1 + 4x2 + 2x3 − s1 + a1 = 8
3x1 + 2x2 − s2 + a2 = 6
The simplex table for this phase is:
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 0 0 0 0 0 1 1 0
a1 1 0 1 4 2 -1 0 1 0 8
a2 2 0 3 2 0 0 -1 0 1 6
after Gauss elimination:
Basic Varible Row Z X1 X2 S1 S2 a1 a2 RHS Ratios
Z 0 1 -4 -6 -2 1 1 0 0 -14
a1 1 0 1 4 2 -1 0 1 0 8 2
a2 2 0 3 2 0 0 -1 0 1 6 3
iteration (0)
Basic Varible Row Z X1 X2 S1 S2 a1 a2 RHS Ratios
Z 0 1 -5/2 0 1 -1/2 1 3/2 0 -2
x2 1 0 1/4 1 1/2 -1/4 0 1/4 0 2 8
a2 2 0 5/2 0 -1 1/2 -1 -1/2 1 2 8/5
iteration(1)
Basic Varible Row Z X1 X2 S1 S2 a1 a2 RHS Ratios
Z 0 1 0 0 0 0 0 1 1 0
x2 1 0 0 1 6/10 -6/20 1/10 6/20 -1/10 9/5
x1 2 0 1 0 -2/5 1/5 -2/5 -1/5 2/5 4/5
see there is no negative number in the first line, thus go to phase 2. Drop the artificial
variable, we get
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 2 3 1 0 0 0
x2 1 0 0 1 6/10 -6/20 1/10 9/5
x1 2 0 1 0 -2/5 1/5 -2/5 4/5
8
after Gauss elimination
Basic Varible Row Z X1 X2 S1 S2 RHS Ratios
Z 0 1 0 0 0 1/2 5/10 -7
x2 1 0 0 1 6/10 -6/20 1/10 9/5
x1 2 0 1 0 -2/5 1/5 -2/5 4/5
Thus we know max −Z = −7, which means minZ = 7, when x1 = 4/5, x2 = 9/5, x3 = 0.
