37242 Optimisation in Quantitative Management
(part 3)
The theorem bellow was one of the exercises in Lecture Notes
(part 1).
Theorem 1
Let v1, …, vk be linearly independent m-vectors and w be an
m-vector such that, for some scalars α1, …, αk,
α1v1 + ::: + αkvk = w: (1)
If αi 6= 0, then the set of vectors, obtained from the set v1, …, vk
by replacing vi by w, is a set of linearly independent vectors.
Proof.
Without loss of generality assume that i = k and observe that
w 6= 0 because w = 0 together with αk 6= 0 contradicts the linear
independence of v1, …, vk.
Suppose that the vectors v1, …, vk-1, w are linearly dependent.
Then, there exist numbers β1, …, βk-1, βk which are not all zero
such that
β1v1 + ::: + βk-1vk-1 + βkw = 0: (2)
Then, βk 6= 0 because otherwise not all β1, …, βk-1 are zero
which together with (2) and βk = 0 contradicts the linear
independence of v1, …, vk-1.
Finally, the substitution of (1) into (2) gives
γ1v1 + ::: + γkvk = 0
where γk = αkβk 6= 0, which contradicts the linear independence
of v1, …, vk.
Consider the following linear programming problem in standard
form
min cT x (3)
subject to
Ax = b (4)
x ≥ 0 (5)
where A is m × n matrix, b 2 Em,
and A has rank m.
EXAMPLE 1
min -7×1 – 6×2 – x3 – 3×4 (6)
subject to
3×1 + 4×2 + x3 + 2×4 = 16 (7)
x1 + x2 + x4 = 6 (8)
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0: (9)
Let a1; :::; an be the columns of A and let
A = 2 4 aa· · · · · · · · · m1;;11 · · · · · · aam1;;nn 3 5 ; and c = 2 4 · · · ccn1 3 5 :
Let B be a matrix which is formed
by m linearly independent columns
in A and which satisfies the inequality
B-1b ≥ 0:
B = 1 2 0 1 ; B-1 = 1 0 1 -2
1 0 1 -2 16 6 = 4 6 ≥ 0 0
Let N be a matrix formed by all
remaining columns in A. N = 3 4 1 1
Let xB and xN be the vectors
formed by the variables associated
with B and N, respectively.
The variables in xB and xN are
listed in the same order as the
corrsponding columns in B and N.
xB = x x3 4 ; xN = x x1 2
Then, the linear program (3) – (5)
can be rewritten as
min cT B xB + cT N xN (10)
subject to
BxB + NxN = b (11)
x ≥ 0 (12)
where cB and cN are the vectors
formed by the coefficients of the
variables in xB and xN, respectively.
min
cT
N xN
z }|
-7×1 – 6×2
cT
B xB
z |
-x3 – 3×4
subject to
NxN
z |
BxB
z |
3×1 + 4×2 + x3 + 2×4 = 16
x1 + x2 + x4 = 6
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0:
cB = – -1 3 ; cN = – -7 6
The linear program (10) – (12) can
be rewritten as
min cT B xB + cT N xN
subject to
B-1 (BxB + NxN) = B-1b
x ≥ 0
or equivalently
min cT B xB + cT N xN (13)
subject to
xB = B-1b – B-1NxN (14)
x ≥ 0 (15)
Multiplying (4) by B-1 we have
B-1
BxB+NxN
z|
(Ax) = B-1b;
which augmented matrix can be
obtained by applying the corresponding elementary row operations.
These elementary row operations
transform the columns of B into
the columns of the identity matrix.
B
z |
3 4 1 2 16 1 1 0 1 6
1 2 1 0 4 1 1 0 1 6
This, by substituting (14) into
(13), gives
min cT B B-1b+(cT N -cT B B-1N)xN (16)
subject to
xB = B-1b – B-1NxN (17)
x ≥ 0 (18)
cT N – cT B B-1N = [-7; -6]
-[-1; -3] 1 0 1 -2 3 4 1 1 = [-3; -1]
Let z be the value of the objective function that corresponds to
the basic feasible solution associated with basis B.
It is convenient to perform all calculations using the following table

cT – cT B B-1A	-z
basic variables	B-1A	B-1b

(19)
This table is called the simplex tableau.
Observe that
cT – cT B B-1A x =
cT
B xB+cT N xN
z|z
BxB+NxN
= cT N – cT B B-1N xN
The entries of the vector
cT – cT B B-1A
are called the reduced costs. Note that the reduced cost of each
basic variable is zero.
The basic feasible solution
x0
B = B-1b and x0 N = 0 (20)
is a feasible solution for (16) –
(18).
The corresponding value of the objective function is cT B B-1b (obtained by substituting x0 N = 0 into
(16)).
cT B B-1b = [-1; -3] 1 0 1 -2 16 6
= -22
The corresponding simplex tableau
x1 x2 x3 x4

-3 -1 0 0	22
x3 x4	1 2 1 0 1 1 0 1	4 6

indicates that basic variables x3 =
4 and x4 = 6.
Note that the row vector
[-cT B B-1A; -cT B B-1b] = -cT B B-1[A b]
is the linear combination of the rows of the augmented matrix
[A b] where the coefficients are the entries of the vector -cT B B-1.
Hence, the row
cT – cT B B-1A
-z
z | z
value of (16)
for (20)
:
In other words, if all nonbasic variables have nonnegative reduced
costs , then (20) is optimal.
Assume that all nonbasic variables have positive reduced costs and
let x00 be an arbitrary feasible solution for the linear programming
problem (16) – (18), which differs from (20).
If x00
N = 0, then
b = Ax00 = Bx00 B +
0
z| z
value of (16) for xj>0
< cT B B-1b
|
1 0 + 1· 2 1
|
3 2 1 1
This new invertible matrix gives rise to the basic feasible solution
where

xj =	min fk: ^ ak;j>0g

b^k
a^k;j ;
is a new basic variable (called entering variable) and
xi = 0
is a new nonbasic variable (called departing variable).
Observe that cT
B B-1A in
cT – cT B B-1A
is a linear combination of the rows in A. Furthermore, if
cT B – αT B = 0T
then αT = cT
B B-1.
Hence, the new tableau can be obtained by elementary row
operations which transform a^j into a column of the identity matrix
and which make the coefficient of xj in the objective function
equals zero.
x1 x2 x3 x4

-3 -1 0 0	22
x3 x4	1 2 1 0 1 1 0 1	4 6

=)
x1 x2 x3 x4

0 5 3 0	34
x1 x4	1 2 1 0 0 -1 -1 1	4 2

Since all reduced costs are nonnegative, x1 = 4, x2 = 0, x3 = 0,
x4 = 2 is the optimal solution. The optimal value of the objective
function is -34.
Simplex Method
Step 1 Choose m linearly independent columns in A such that
B-1b ≥ 0.
Step 2 For the basic feasible solution xB = B-1b and xN = 0, create
the simplex tableau (19).
Step 3 If all reduced costs for nonbasic variables are nonnegative,
then stop. The current basic feasible solution is an optimal
solution.
Step 4 Choose a nonbasic variable xj with negative reduced cost
which has the largest absolute value of its reduced cost among
all nonbasic variables with the negative reduced costs.
Step 5 If B-1aj ≤ 0, then stop. The linear programming problem is
unbounded and does not have an optimal solution.
Step 6 Choose xj as a new basic variable (entering variable) and set

xj =

min fk: ^ ak;j>0g a^k;j

:

(22)

b^k

Step 7 As a result of (22), one of the basic variables, say xi, becomes
zero. This variable (departing variable) becomes a new
nonbasic variable.
Step 8 Using elementary row operations, update the tableau
transforming a^j into a column of the identity matrix with 1 in
the row that corresponds to xi and making the coefficient of
xj in the objective function zero.
Step 9 Go to Step 3.
The simplex method is an iterative method for solving linear
programming problems in standard form. It moves from one basic
feasible solution (extreme point) to another.
At each iteration the simplex method tests whether or not the
current extreme point (basic feasible solution) is optimal. If not, it
moves to an adjacent extreme point.
George Dantzig (1914 – 2005)
invented the simplex method
in 1947.
In 1954 Dantzig together
with Orchard Hays developed
the revised simplex algorithm.
EXERCISE 1
Is it possible to use in the solution above instead of the columns in
(7) – (8) associated with x3 and x4 the columns in (7) – (8)
associated with x2 and x3?
EXERCISE 2
I Prove that the columns in (7) – (8), which are associated with
x2 and x4, are linearly independent.
I Solve the linear programming problem (6) – (9) by choosing as
an initial basis the columns associated with x2 and x4.
EXAMPLE 2
Solve the following linear programming problem
max 2×1 + 5×2
subject to
x1 + x2 ≤ 4

x1	≤ 2 x2 ≤ 3

x1 ≥ 0; x2 ≥ 0
This maximisation program has the same optimal solution as
min -2×1 – 5×2
subject to
x1 + x2 ≤ 4

x1	≤ 2 x2 ≤ 3

x1 ≥ 0; x2 ≥ 0
The latter can be rewritten as
min -2×1 – 5×2
subject to
x1 + x2 + x3 = 4

x1

+ x4

= 2 + x5 = 3

x2

x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0; x5 ≥ 0
The obvious choice of the initial basis is columns associated with
the slack variables x3, x4, x5.
xB =
24
x3
x4
x5
35
; xN = x x1 2 ; B = 2 4 1 0 0 0 1 0 0 0 1 3 5 ; N = 2 4 1 1 1 0 0 1 3 5
cB =
24
0 0 0
35
; cN = – -2 5
cT N – cT B B-1N = [-2; -5]
x1 x2 x3 x4 x5

-2 -5 0 0 0	0
x3 x4 x5	1 1 1 0 0 1 0 0 1 0 0 1 0 0 1	4 2 3

entering variable x2, departing variable x5
x1 x2 x3 x4 x5

-2 0 0 0 5	15
x3 x4 x2	1 0 1 0 -1 1 0 0 1 0 0 1 0 0 1	1 2 3

entering variable x1, departing variable x3
x1 x2 x3 x4 x5

0 0 2 0 3	17
x1 x4 x2	1 0 1 0 -1 0 0 -1 1 1 0 1 0 0 1	1 1 3

The optimal solution is x1 = 1, x2 = 3, x3 = 0, x4 = 1, x5 = 0.
The optimal value of the objective function is -17.
The optimal solution for the original maximisation problem is
x1 = 1, x2 = 3. The optimal value of the original objective
function is 17.
EXERCISE 3
Using the simplex method, solve the following linear programming
problem
min -x1 – 2×2
subject to
x1 + x2 ≤ 3
-x1 + x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
EXAMPLE 3
Consider the following linear programming problem
min -x1 – x2 (23)
subject to

x1 + x2 ≤ 4 5×1 + 3×2 ≤ 15

(24) (25)

x1 ≥ 0; x2 ≥ 0 (26)
By introducing the slack variables, this problem can be rewritten as
min -x1 – x2
subject to
x1 + x2 + x3 = 4
5×1 + 3×2 + x4 = 15
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0; x4 ≥ 0
Then
xB = x x3 4 ; xN = x x1 2 ; B = 1 0 0 1 ; N = 1 1 5 3 ; b = 15 4
cB = 0 0 ; cN = – -1 1 ; cT B B-1 = [0; 0] 1 0 0 1 = [0; 0]
cT N – cT B B-1N = [-1; -1]; cT B B-1b = 0
x1 x2 x3 x4

-1 -1 0 0	0
x3 x4	1 1 1 0 5 3 0 1	4 15

entering variable x1, departing variable x4
x1 x2 x3 x4

0 -2 5 0 15	3
x3 x1	0 25 1 -15 1 35 0 15	1 3

entering variable x2, departing variable x3
x1 x2 x3 x4

0 0 1 0	4
x2 x1	0 1 5 2 -1 2 1 0 -3 2 1 2	5 2 3 2

This gives an optimal basic feasible solution is x1 = 3
2, x2 =
5 2
,
x3 = 0, x4 = 0. The optimal value of the objective function is -4.
Since the reduced cost for nonbasic variable x4 is zero, this variable
can be an entering variable. In this case, the departing variable is
x1.
x1 x2 x3 x4

0 0 1 0	4
x2 x4	1 1 1 0 2 0 -3 1	4 3

This gives another optimal basic feasible solution is x1 = 0, x2 = 4,
x3 = 0, x4 = 3. The optimal value of the objective function is -4.
Hence, the original linear programming problem (23) – (26) has
two optimal basic feasible solutions:
x1 =
3 2
and x2 = 5
2
and
x1 = 0 and x2 = 4
EXERCISE 4
I Using the simplex method, solve the following linear
programming problem
min -x1 – x2
subject to
x1 + x2 ≤ 3
x1 – x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
I Find two optimal basic feasible solutions.
I Show that this linear programming problem has infinitely
many optimal solutions.
I Solve this problem geometrically.
EXERCISE 5
Consider the linear programming problem
min cT x
subject to
Ax = b
x ≥ 0
Prove that if x0 and x00 are two optimal solutions, then, for any
0 ≤ α ≤ 1,
αx0 + (1 – α)x00
is an optimal solution.
EXERCISE 6
Find an optimal solution for the linear programming problem
min -4×1 – x2 – 3×3
subject to
2×2 – 3×3 ≤ 0
4×1 + 2×2 + 3×3 ≤ 12
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0
which is not a basic feasible solution.
Any point, obtained by moving from point x in direction d, can be
expressed as
x + αd
where α is a positive scalar.
EXAMPLE 4
Solve the following linear programming problem
min x1 – 2×2
subject to
-3×1 + x2 ≤ 2
2×1 – x2 ≤ 1
x1 ≥ 0; x2 ≥ 0
By introducing the slack variables, this problem can be rewritten as
min x1 – 2×2
subject to
-3×1 + x2 + x3 = 2
2×1 – x2 + x4 = 1
x1 ≥ 0; x2 ≥ 0
Then
xB = x x3 4 ; xN = x x1 2 ; B = 1 0 0 1 ; N = -3 1 2 -1
cB = 0 0 ; cN = -1 2
cT B B-1 = [0; 0]; cT B B-1b = 0; cT N – cT B B-1N = [1; -2]
x1 x2 x3 x4

1 -2 0 0	0
x3 x4	-3 1 1 0 2 -1 0 1	2 1

entering variable x2, departing variable x3
x1 x2 x3 x4

-5 0 2 0	4
x2 x4	-3 1 1 0 -1 0 1 1	2 3

(27)
Tableau (27) indicates that for the current basic feasible solution
xB = x x2 4 =
B-1b
z |
2 3 ; xN = x x1 3 = 0 0
B = -1 0 1 1 ; N = -3 1 2 0
Taking into account that
xB = B-1b – B-1NxN;
when x1 increases while x3 remains zero
x x2 4 = 2 3 – x1 1 0 1 1 -3 2 –
0
z |
x3 1 0 1 1 1 0
= 2 3 – x1 – -3 1 = 2 3 + x1 3 1
and
x x1 3 = x01 = 0 0 + x1 1 0 :
Summarising the above, each value of x1 gives the feasible point
2664
x1
x2
x3
x4
3775
=
current basic
feasible solution
z | {
2664
0 2 0 3
3775
+ x1
2664
1 3 0 1
3775
| z
direction in which
all points are feasible and the objective
function decreases
For any x1 > 0 the corresponding value of the objective function is
x1 – 2(2 + 3×1) = -4 – 5×1
So, the objective function decreasing infinitely and does not have
an optimal (smallest) value. This linear programming problem is
unbounded.
EXERCISE 7
Let
A = -1 4 1 0 1 -2 1 0 ; c =
2664
1
-5
0 0
3775
and b = 2 4 :
I Find all extreme points of the set
fx : Ax = b; x ≥ 0; x 2 E4g:
I Find an extreme point x0 and a vector d 2 E4 such that, for
any positive α,
x0 + αd 2 fx : Ax = b; x ≥ 0; x 2 E4g
and c · d < 0.
EXERCISE 8
Consider a positive number b and two n-vectors
c =
24
c1
· · ·
cn
35
>
24
0
· · ·
0
35
and a = 2 4 · · · aan1 3 5 > 2 4 · · · 0 0 3 5 :
Solve the following linear programming problem
max c · x
subject to
a · x ≤ b
x ≥ 0
EXERCISE 9
Solve the following linear programming problem
min -x1 – x2
subject to
x1 + 2×2 – x3 = 2
x1 ≥ 0; x2 ≥ 0; x3 ≥ 0
EXERCISE 10
Consider the following linear programming problem
min cT x (28)
subject to
Ax ≤ b (29)
x ≥ 0 (30)
Let x3, x4, x5 be slack variables and let
x1 x2 x3 x4 x5

0 0 0 1 2	13
x2 x1 x3	0 1 0 12 12 1 0 0 0 1 0 0 1 -12 32	5 3 3

(31)
be the final simplex tableau obtained for (28) – (30) after applying
the simplex method.
(a) Does (28) – (30) have an optimal solution which is not a basic
feasible solution? Justify your answer.
(b) Find the matrix B-1 and the vector cT B B-1 which correspond
to (31).
(c) Find the matrix A and the vectors c and b in (28) – (30).
(d) Solve the linear programming problem (28) – (30), obtained in
(c), geometrically.
(e) Solve the linear programming problem (28) – (30), obtained in
(c), using the simplex method.