MH3701 Basic Optimization AY 2017/18 S2

Tutorial 3: Answers
1. For each of the given linear program in standard inequality form,
(a) write down its augmented form, using si to denote the slack variable of the i’th
inequality constraint;
(b) find the feasible solution of its augmented form that is uniquely determined by
all equality constraints, together with setting the given variables to zero; and
(c) write down the corner point feasible solution of the given linear program whose
augmented solution is the feasible solution found above.
(i) Linear program:
maximize 8x1 − 5x2 − 4x3
subject to −2x1 − 3x2 + 3x3 ≤ 3
−4x1 + 3x3 ≤ 3
2x1 − 3x3 ≤ −3
4x1 + 3x2 − 3x3 ≤ −2
x1 , x2 , x3 ≥ 0
Variables: s1 , s2 , s4
Answer: Augmented form:
maximize 8x1 − 5x2 − 4x3
subject to −2x1 − 3x2 + 3x3 + s1 = 3
−4x1 + 3x3 + s2 = 3
2x1 − 3x3 + s3 = −3
4x1 + 3x2 − 3x3 + s4 = −2
x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥ 0
Feasible solution of augmented form: ( 21 , 31 , 1 32 , 0, 0, 1, 0)
Corner point feasible solution: ( 12 , 13 , 1 32 )
(ii) Linear program:
maximize 7x1 − 3x2 + 8x3
subject to −2x1 − 2x2 + 3x3 ≤ 1
2x2 − 3x3 ≤ −3
−4x1 − 2x2 + 3x3 ≤ −1
4x1 + 4x2 − 3x3 ≤ 2
x1 , x2 , x3 ≥ 0
Variables: x2 , s1 , s4
Answer: Augmented form:
maximize 7x1 − 3x2 + 8x3
subject to −2x1 − 2x2 + 3x3 + s1 = 1
2x2 −3x3 + s2 = −3
−4x1 − 2x2 + 3x3 + s3 = −1
4x1 + 4x2 − 3x3 + s4 = 2
x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥ 0
Feasible solution of augmented form: (1 21 , 0, 1 13 , 0, 1, 1, 0)
Corner point feasible solution: (1 21 , 0, 1 31 )

1
2

(iii) Linear program:

maximize 9x1 − 6x2 + 6x3
subject to −4x1 + x2 + 4x3 ≤ 6
x1 − x3 ≤ −1
4x1 − x2 − 2x3 ≤ −3
−2x1 + x3 ≤ 1
x1 , x2 , x3 ≥ 0
Variables: s1 , s2 , s3
Answer: Augmented form:
maximize 9x1 − 6x2 + 6x3
subject to −4x1 + x2 + 4x3 + s1 = 6
x1 − x3 + s2 = −1
4x1 − x2 − 2x3 + s3 = −3
−2x1 + x3 + s4 = 1
x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥ 0
Feasible solution of augmented form: ( 21 , 2, 1 21 , 0, 0, 0, 12 )
Corner point feasible solution: ( 12 , 2, 1 12 )
(iv) Linear program:
maximize 5x2 + 9x3
subject to −x1 − x3 ≤ −1
− x2 + 6x3 ≤ 5
3x1 + x2 − 3x3 ≤ −1
− x2 + 3x3 ≤ 2
x1 , x2 , x3 ≥ 0
Variables: x1 , s2 , s3
Answer: Augmented form:
maximize 5x2 + 9x3
subject to −x1 − x3 + s1 = −1
− x2 + 6x3 + s2 = 5
3x1 + x2 − 3x3 + s3 = −1
− x2 + 3x3 + s4 = 2
x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥ 0
Feasible solution of augmented form: (0, 3, 1 31 , 31 , 0, 0, 1)
Corner point feasible solution: (0, 3, 1 31 )
(v) Linear program:
maximize 6x1 + x2 + 5x3
subject to x2 − x3 ≤ −1
x2 − 2x3 ≤ −2
3x1 − x2 + 2x3 ≤ 3
3x1 − 2x2 + 2x3 ≤ 3
x1 , x2 , x3 ≥ 0
Variables: x1 , s1 , s3
Answer: Augmented form:
 3

maximize 6x1 + x2 +
5x3
subject to x2 −x3 + s1 = −1
x2 −
2x3 + s2 = −2
3x1 − x2 +
2x3 + s3 = 3
3x1 − 2x2 +
2x3 + s4 = 3
x1 , x2 , x3 , s1 , s2 , s3 , s4 ≥ 0
Feasible solution of augmented form: (0, 1, 2, 0, 1, 0, 1)
Corner point feasible solution: (0, 1, 2)
4

2. Determine if each of the given set of variables is a basis of the given system of
linear equations, and if it is, find the basic solution it determines.
(i) Linear system:
− 9x2 − x3 + 3x5 − 4x6 − 2x7 = −2
x1 + 6x2 + 2x3 + 2x4 − 3x5 + 3x6 − 2x7 = 1
x1 + 3x2 − 2x3 + 2x4 + 9x5 − 2x6 + x7 = 4
−3x1 + 3x2 + 4x3 + 4x4 − 6x5 + 3x6 + 3x7 = −1

(a) Set: {x2 , x3 , x5 , x6 }

Answer: {x2 , x3 , x5 , x6 } is not a basis.
(b) Set: {x1 , x3 , x5 , x7 }
Answer: {x1 , x3 , x5 , x7 } is a basis which determines the basic solution
(2, 0, 1, 0, 31 , 0, 1).
(c) Set: {x1 , x4 , x6 , x7 }
Answer: {x1 , x4 , x6 , x7 } is a basis which determines the basic solution
(2, 0, 0, 12 , 0, 0, 1).
(ii) Linear system:
−6x1 + 2x3 − 5x4 + x5 − 3x6 − x7 = −4
−4x1 − x2 + x3 − 3x4 + x5 − x6 − x7 = −2
2x1 − 3x2 + 3x3 − 2x4 − 4x5 − 3x6 − 3x7 = −6
4x1 − 2x2 − 4x3 + 3x4 − x5 + 4x6 − 2x7 = 2

(a) Set: {x4 , x5 , x6 , x7 }

Answer: {x4 , x5 , x6 , x7 } is not a basis.
(b) Set: {x1 , x2 , x3 , x6 }
Answer: {x1 , x2 , x3 , x6 } is a basis which determines the basic solution
(0, 1, 1, 0, 0, 2, 0).
(c) Set: {x1 , x4 , x5 , x7 }
Answer: {x1 , x4 , x5 , x7 } is not a basis.
(iii) Linear system:
−x1 − 6x3 − 8x4 − 3x5 − 2x6 − 2x7 = −6
−2x1 − 2x3 − 6x4 − 6x5 + x6 − 4x7 = −2
−x1 − 6x2 − 2x3 − 8x4 − 3x5 − 6x7 = −4
−x1 + 6x2 + 3x3 + 8x4 + 6x5 + x6 + 2x7 = 5

(a) Set: {x2 , x3 , x4 , x6 }

Answer: {x2 , x3 , x4 , x6 } is not a basis.
(b) Set: {x3 , x5 , x6 , x7 }
Answer: {x3 , x5 , x6 , x7 } is a basis which determines the basic solution
(0, 0, 0, 0, 13 , 2, 12 ).
(c) Set: {x1 , x2 , x5 , x6 }
Answer: {x1 , x2 , x5 , x6 } is a basis which determines the basic solution
(1, 31 , 0, 0, 31 , 2, 0).
 5

(iv) Linear system:

−2x1 + x2 − 3x3 + 3x5 + 6x6 − x7 = 1
2x1 + 6x3 + 4x4 + 6x5 − 3x6 + 5x7 = 4
−x1 + x2 + 5x3 + 2x4 + 6x5 − 3x6 + 4x7 = 3
−3x1 + 2x2 − 3x3 − x4 + 6x6 − x7 = 1

(a) Set: {x1 , x3 , x6 , x7 }

Answer: {x1 , x3 , x6 , x7 } is not a basis.
(b) Set: {x2 , x4 , x6 , x7 }
Answer: {x2 , x4 , x6 , x7 } is not a basis.
(c) Set: {x1 , x2 , x3 , x5 }
Answer: {x1 , x2 , x3 , x5 } is a basis which determines the basic solution
(1, 2, 0, 0, 31 , 0, 0).
(v) Linear system:
−9x1 − x2 − 2x3 − 3x4 − 4x5 − x6 − 4x7 = −5
x2 + 2x3 − 3x4 + x5 + x7 = 2
9x1 + 2x2 − 2x3 − 3x4 + 2x5 − x6 − x7 = 1
9x1 − 3x2 − 6x3 + 6x4 + 4x6 = −3

(a) Set: {x2 , x3 , x4 , x6 }

Answer: {x2 , x3 , x4 , x6 } is a basis which determines the basic solution
(0, 2, 12 , 13 , 0, 1, 0).
(b) Set: {x1 , x3 , x5 , x6 }
Answer: {x1 , x3 , x5 , x6 } is not a basis.
(c) Set: {x1 , x2 , x3 , x7 }
Answer: {x1 , x2 , x3 , x7 } is not a basis.
6

3. Determine if each of the given solutions is a basic solution of the given system of
linear equations, and if it is, find all bases that determine it.
(i) Linear system:
2x2 + 2x4 + x5 + 3x7 = 2
− 6x2 − 6x3 − 3x4 + 2x5 + 2x6 − 4x7 = −1
2x2 + 3x3 + 2x4 − x5 − 2x6 + x7 = 0
3x1 − 8x3 − x4 − 2x5 + 2x6 + 4x7 = 1

(a) Solution: (0, 0, 0, 31 , 13 , 31 , 31 )

Answer: (0, 0, 0, 13 , 31 , 31 , 13 ) is not a basic solution.
(b) Solution: (4, 0, 1, 0, 2, 21 , 0)
Answer: (4, 0, 1, 0, 2, 12 , 0) is determined by {x1 , x3 , x5 , x6 }.
(c) Solution: (1, 12 , 0, 0, 1, 0, 0)
Answer: (1, 12 , 0, 0, 1, 0, 0) is determined by {x1 , x2 , x3 , x5 }, {x1 , x2 , x4 , x5 },
and {x1 , x2 , x5 , x6 }.
(ii) Linear system:
−3x1 − 4x3 − x4 − 6x5 − 6x7 = −5
−x1 − 3x2 + 2x3 − 5x4 − 6x5 − 8x7 = −3
−2x1 + x2 + 4x3 − 3x4 + 9x5 − 2x7 = 1
4x1 − 4x2 + 2x3 − 4x4 − 9x5 − 9x6 − 6x7 = −2

(a) Solution: (1, 0, 0, 0, 13 , 31 , 0)

Answer: (1, 0, 0, 0, 31 , 13 , 0) is determined by {x1 , x2 , x5 , x6 }, {x1 , x3 , x5 , x6 },
{x1 , x4 , x5 , x6 }, and {x1 , x5 , x6 , x7 }.
(b) Solution: (1, 1, 21 , 0, 0, 31 , 0)
Answer: (1, 1, 21 , 0, 0, 13 , 0) is determined by {x1 , x2 , x3 , x6 }.
(c) Solution: (0, 0, 23 , 31 , 0, 0, 31 )
Answer: (0, 0, 23 , 13 , 0, 0, 31 ) is not a basic solution.
(iii) Linear system:
2x1 + 6x2 + x3 + 3x4 + 4x5 + 4x6 − 4x7 = 5
x1 + 4x2 − x3 + 4x5 + 2x6 + 2x7 = 3
−x1 − 3x2 + x3 − 3x5 − x6 − 2x7 = −2
2x1 + 8x2 + x3 + 3x4 + 3x5 + 2x7 = 4

(a) Solution: (0, 0, 0, 1, 0, 1, 12 )

Answer: (0, 0, 0, 1, 0, 1, 21 ) is determined by {x1 , x4 , x6 , x7 }, {x3 , x4 , x6 , x7 },
and {x4 , x5 , x6 , x7 }.
(b) Solution: (1, 0, 1, 0, 0, 1, 12 )
Answer: (1, 0, 1, 0, 0, 1, 21 ) is determined by {x1 , x3 , x6 , x7 }.
(c) Solution: (0, 13 , 13 , 0, 31 , 13 , 0)
Answer: (0, 31 , 31 , 0, 13 , 31 , 0) is not a basic solution.
(iv) Linear system:
−3x1 − 2x2 − 4x3 − 6x4 + 2x5 − 2x6 + x7 = −7
−x1 + 4x2 + 2x3 − 6x5 − x6 − 2x7 = 2
4x2 + 2x3 + x4 − 4x5 − x6 − x7 = 3
−2x1 + 6x2 − 2x3 + 2x4 + x6 + 9x7 = 5
 7

(a) Solution: (1, 1, 0, 0, 0, 1, 0)

Answer: (1, 1, 0, 0, 0, 1, 0) is determined by {x1 , x2 , x3 , x6 }, {x1 , x2 , x5 , x6 },
and {x1 , x2 , x6 , x7 }.
(b) Solution: (0, 1, 1, 0, 12 , 1, 0)
Answer: (0, 1, 1, 0, 21 , 1, 0) is determined by {x2 , x3 , x5 , x6 }.
(c) Solution: (0, 13 , 23 , 32 , 0, 0, 31 )
Answer: (0, 13 , 32 , 32 , 0, 0, 13 ) is not a basic solution.
(v) Linear system:
6x1 + x2 − 2x3 + 2x4 + x5 + 8x6 − 2x7 = 4
4x1 + x2 − 2x3 + 2x4 − x5 + 6x6 + 4x7 = 2
−3x1 + 3x2 + 3x3 − 4x4 + x5 − 6x6 + x7 = 0
7x1 − 2x2 − 2x3 + 6x4 + x5 + 9x6 − 9x7 = 5

(a) Solution: (0, 0, 1, 2, 4, 0, 1)

Answer: (0, 0, 1, 2, 4, 0, 1) is determined by {x3 , x4 , x5 , x7 }.
(b) Solution: (0, 1, 0, 1, 1, 0, 0)
Answer: (0, 1, 0, 1, 1, 0, 0) is determined by {x1 , x2 , x4 , x5 }, {x2 , x3 , x4 , x5 },
{x2 , x4 , x5 , x6 }, and {x2 , x4 , x5 , x7 }.
(c) Solution: ( 12 , 0, 1 12 , 0, 0, 21 , 0)
Answer: ( 21 , 0, 1 12 , 0, 0, 12 , 0) is not a basic solution.
8

4. For each of the given system of linear equations and the basic feasible solution
determined by the given feasible basis, determine the parametric equation of lines
containing edges emanating from it.
(i) Linear system:
2x1 − 3x2 + 2x3 − x5 = −2
−8x1 − 4x3 + x4 − x5 − 4x6 = −4
6x1 + 3x2 + 2x3 + x5 + 4x6 = 6
Feasible basis: {x4 , x5 , x6 }
Answer: {(x1 , 0, 0, 2 + 2x1 , 2 + 2x1 , 1 − 2x1 ) : x1 ∈ R},
{(0, x2 , 0, 2 − 3x2 , 2 − 3x2 , 1) : x2 ∈ R},
{(0, 0, x3 , 2 + 2x3 , 2 + 2x3 , 1 − x3 ) : x3 ∈ R}.
(ii) Linear system:
x1 + 2x2 + 2x4 = 2
2x1 + 2x2 − 2x3 − 3x5 − 3x6 = −6
3x1 + 6x2 − x3 + 5x4 − 3x5 = 2
Feasible basis: {x1 , x3 , x6 }
Answer: {(2 − 2x2 , x2 , 4, 0, 0, 32 − 23 x2 ) : x2 ∈ R},
{(2 − 2x4 , 0, 4 − x4 , x4 , 0, 23 − 23 x4 ) : x4 ∈ R},
{(2, 0, 4 − 3x5 , 0, x5 , 23 + x5 ) : x5 ∈ R}.
(iii) Linear system:
− x2 − x3 − x4 − 4x6 = −2
x1 + 2x2 + x3 + 2x4 + 8x6 = 4
4x1 + 3x2 − 3x3 + x4 + 4x5 + 8x6 = 10
Feasible basis: {x1 , x3 , x5 }
Answer: {(2 − x2 , x2 , 2 − x2 , 0, 2 − 21 x2 , 0) : x2 ∈ R},
{(2 − x4 , 0, 2 − x4 , x4 , 2, 0) : x4 ∈ R},
{(2 − 4x6 , 0, 2 − 4x6 , 0, 2 − x6 , x6 ) : x6 ∈ R}.
(iv) Linear system:
− x2 − x3 − 6x4 − 4x5 − 2x6 = −10
−x1 − x2 − x3 − 4x4 − 2x5 = −6
−2x1 − x3 + 2x4 + 2x5 + 4x6 = 4
Feasible basis: {x3 , x4 , x6 }
Answer: {(x1 , 0, 2 + x1 , 1 − 12 x1 , 0, 1 + x1 ) : x1 ∈ R},
{(0, x2 , 2 + x2 , 1 − 12 x2 , 0, 1 + 12 x2 ) : x2 ∈ R},
{(0, 0, 2 − 2x5 , 1, x5 , 1 − x5 ) : x5 ∈ R}.
(v) Linear system:
x1 − x2 + 3x3 + 4x4 + 6x5 + 2x6 = 0
x1 + x2 + 6x3 + 2x4 + 6x5 =6
3x2 + 3x3 − 4x4 − 2x5 − 4x6 = 8
Feasible basis: {x1 , x2 , x6 }
Answer: {(2 − 3x3 , 4 − 3x3 , x3 , 0, 0, 1 − 1 21 x3 ) : x3 ∈ R},
{(2 − 2x4 , 4, 0, x4 , 0, 1 − x4 ) : x4 ∈ R},
{(2 − 4x5 , 4 − 2x5 , 0, 0, x5 , 1 − 2x5 ) : x5 ∈ R}.