Linear Programming

Lecture notes

Dr Jeremy Budd,
School of Mathematics
University of Birmingham
Birmingham B15 2TT, UK
Email: j.m.budd@bham.ac.uk
 Abstract

These are the lecture notes for the module “Linear Programming” covering LP modelling,
geometric method, duality theory, the simplex method and some extensions of the simplex
method.

Linear programming grew out of attempts to solve systems of linear inequalities, al-
lowing one to optimise linear functions subject to constraints expressed as inequalities.
The theory was developed independently at the time of World War II by the Soviet mathe-
matician Kantorovich, for production planning, and by Dantzig, to solve complex military
planning problems. Koopmans applied it to shipping problems and the technique enjoyed
rapid development in the postwar industrial boom. The first complete algorithm to solve
linear programming problems, called the simplex method, was published by Dantzig in
1947 and in the same year von Neumann established the theory of duality. In 1975, Kan-
torovich and Koopmans shared the Nobel Prize in Economics for their work and Dantzig’s
simplex method has been voted the second most important algorithm of the 20th century
after the Monte Carlo method. Linear programming is a modern and immensely powerful
technique that has numerous applications, not only in business and economics, but also
in engineering, transportation, telecommunications, and planning.

By the end of the module students should be able to:

• construct linear programming models of a variety of managerial problems and inter-

pret the results obtained by applying the linear programming techniques to these
problems,

• explain why and when the simplex method fails to provide a solution and how to
resolve such a situation

• present, prove and use the results of duality theory and interpret them,

• explain the computational complexity of SIMPLEX and LP

 1

Acknowledgments

These lecture notes are based on lecture notes written by Dr Yun-Bin Zhao, Dr Hon
Duong, and Prof. Marta Mazzocco. I would like to thank them for sharing their notes.
Contents

Abstract 1

1 Introduction to Linear Programming 5

1.1 What is optimisation? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 What is Linear Programming? . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Definition of LP: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.4 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.5 LP Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.6 Standard Forms of LPs: . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.7 Canonical Form of LPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.8 A brief history of LPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2 LPs with 2 Variables: Geometric Method 20

3 Introduction to Convex Analysis 24

3.1 Basic concepts in convex analysis . . . . . . . . . . . . . . . . . . . . . . . 24

3.2 Extreme Points, Directions, Representation of Polyhedra . . . . . . . . . . 29

4 Duality theory 34

4.1 Motivation and derivation of dual LP problems . . . . . . . . . . . . . . . 35

4.2 Primal and dual problems of LPs . . . . . . . . . . . . . . . . . . . . . . . 37

4.3 Duality theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.4 Network flow problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.5 Optimality Conditions & Complementary slackness . . . . . . . . . . . . . 46

2
 3

4.6 More Applications of Duality Theory . . . . . . . . . . . . . . . . . . . . . 51

5 The Simplex Method (I): Theory 53

5.1 Basic Feasible Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.1.1 Review of Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . 54

5.1.2 Existence of the Optimal Extreme Point . . . . . . . . . . . . . . . 55

5.1.3 Basic Feasible Solution . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.1.4 Correspondence between BFSs & extreme points . . . . . . . . . . 59

5.2 The simplex method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.2.1 Reformulation of LP by the current BFS . . . . . . . . . . . . . . . 63

5.2.2 Checking the Optimality . . . . . . . . . . . . . . . . . . . . . . . . 65

5.2.3 Principles and justification of simplex method: . . . . . . . . . . . . 66

6 The simplex method (II): Algorithm 70

6.1 The algorithm for minimisation problems . . . . . . . . . . . . . . . . . . . 70

6.2 The simplex method in Tableau Format . . . . . . . . . . . . . . . . . . . 72

6.2.1 Pivoting: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.2.2 Algorithm in tableau Format . . . . . . . . . . . . . . . . . . . . . . 76

6.3 Degeneracy and cycling in the simplex method . . . . . . . . . . . . . . . . 79

6.4 Efficiency of the simplex method . . . . . . . . . . . . . . . . . . . . . . . 82

6.5 Further Examples for Simplex Methods & Degeneracy . . . . . . . . . . . . 84

6.6 Extracting Information from the Optimal Simplex Tableau . . . . . . . . . 88

6.6.1 Find the inverse of optimal basis . . . . . . . . . . . . . . . . . . . 89

6.6.2 Recovering original LP problems from the optimal tableau . . . . . 90

7 The Dual Simplex Method (non-examinable) 92

7.1 Dual information from the (primal) optimal simplex tableau . . . . . . . . 93

7.2 Recovering missing data in simplex tableau . . . . . . . . . . . . . . . . . . 94

7.3 Complementary slack condition . . . . . . . . . . . . . . . . . . . . . . . . 95

7.4 Uniqueness of optimal solutions to a linear programming problem . . . . . 96

 4

7.5 The Dual Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

8 Sensitivity Analysis (non-examinable) 101

8.1 Change in the cost vector . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

8.2 Change in the right-hand-side . . . . . . . . . . . . . . . . . . . . . . . . . 104

8.3 Adding a new activity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

8.4 Adding a new constraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

9 The Two-Phase method and the Big-M Method (non-examinable) 111

9.1 The Two-phase Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.2 The Big-M method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Bibliography 128
Chapter 1

Introduction to Linear Programming

This chapter provides key concepts of LP that include its definition and terminologies,
standard and canonical forms. Some typically important realistic problems that can be
modelled and solved using LP are also discussed. The following topics will be covered:

• definition of LP,

• terminologies of LP,

• standard forms of LPs,

• canonical forms of LPs,

• LP modelling.

At the end of this section, students will be able to

• understand the definition of a LP and relevant terminologies.

• write LPs in standard and canonical forms,

• recognise and formulate some typical problems in real applications into LPs.

[BT97, Chapter 1] and [DT97, Chapter 1] discuss similar topics as in this chapter that
you may find useful.

5
 6

1.1 What is optimisation?

Mathematical optimisation (mathematical programming) is a mathematical method

for determining a way to achieve the best outcome (e.g., maximum profit or lowest cost)
in a given list of requirements (constraints).

We do this by representing the ways to achieve an outcome by a variable, e.g. x, and

the quality of the outcome by a function, f (x), called the objective function.

We then seek to find

max (or min) f (x)

subject to (s.t.) constraints

This value is the optimal value of the objective function. Sometimes, we will care
more about the optimiser(s), the value(s) of the variable which produce this optimal
value. This is written

argmax (or argmin) f (x)

subject to (s.t.) constraints

Optimisation is an extremely important area of modern applied mathematics, with

applications in just about every industry.

1.2 What is Linear Programming?

• Linear programming (LP) is a specific case of mathematical optimisation. It is a

technique for minimizing (or maximizing) a linear objective function, subject to
linear equality and/or linear inequality constraints.

A good understanding of the theory and algorithms for linear programming is essential
for understanding

• nonlinear programming (nonlinear optimisation),

• integer programming (integer optimisation),

 7

• combinatorial optimisation problems,

• game theory,

• big-data sparse representation.

So, the theory of LP serves as a guide and motivating force for developing results for other
mathematical optimisation problems with either continuous or discrete variables.

Example 1.1. A small machine shop manufactures two models: standard and deluxe.

• Each standard model requires 2 hours of grinding and 4 hours of polishing.

• Each deluxe module requires 5 hours of grinding and 2 hours of polishing.

• The manufacturer has three grinders and two polishers. Therefore in 40 hours week
there are 120 hours of grinding capacity and 80 hours of polishing capacity.

• There is a net profit of £3 on each standard model and £4 on each deluxe model.

To maximise the profit, the manager must decide on the allocation of the available pro-
duction capacity to standard and deluxe models.

Let x1 and x2 be the numbers of standard and deluxe models manufactured, respectively.

For this small machine shop, there are two constraints (restrictions):

• Grinding restriction:
2x1 + 5x2 ≤ 120.

• Polishing restriction:
4x1 + 2x2 ≤ 80.

The variables x1 , x2 are nonnegative:

x1 ≥ 0, x2 ≥ 0. (W hy?)

The net profit is

3x1 + 4x2 .
 8

Therefore, we obtain the following model:

maximise 3x1 + 4x2

subject to 2x1 + 5x2 ≤ 120,
4x1 + 2x2 ≤ 80,
x1 , x2 ≥ 0.

This is a linear programming problem.

1.3 Definition of LP:

Definition 1.2. A linear programming problem is the problem of minimizing or maximiz-

ing a linear function subject to linear constraints. The constraints may be equalities
or inequalities.

minimise (maximise) c1 x1 + c2 x2 + ... + cn xn

Subject to a11 x1 + a12 x2 + ... + a1n xn {≤, =, ≥} b1 ,

a21 x1 + a22 x2 + ... + a2n xn {≤, =, ≥} b2 ,

..
.

am1 x1 + am2 x2 + ... + amn xn {≤, =, ≥} bm ,

xj ≥ 0, j = 1, ..., n.

LP in matrix notation:

The LP can be written as

minimise (maximise) cT x

subject to Ax (≥, =, ≤) b,

x ≥ 0,

where (≥, =, ≤) denotes a diagonal matrix in which the ii-th component is the symbol
 9

{≤, =, ≥} in the i-th equation,

       
a a12 · · · a1n b1 c1 x1
 11       
 a21 a22 · · · a2n
       
  b2   c2   x2 
A=  .. .. ..
, b = 
  ..
, c = 
  ..
,x = 
  ..
.

 . . .   .   .   . 
       
am1 am2 · · · amn bm cn xn

All vectors are understood as column vectors, unless otherwise stated.

The problem can be also represented via the columns of A. Denoting

A = [a1 , a2 , ..., an ]

where aj is the jth column of A, the LP can be written as

n
X
minimise (maximise) cj x j
j=1
Xn
subject to aj xj (≥, =, ≤) b,
j=1
x ≥ 0.

1.4 Terminology

• The function
cT x = c1 x1 + ... + cn xn

is called the objective function (criterion function, goal, or target).

• c = (c1 , c2 , ..., cn )T is called the cost coefficient.

• x1 , x2 , ..., xn are called the decision variables.

• The inequality ‘Ax ≤ b’ is called the constraint, and

Pn
j=1 aij xj ≤ bi denotes the
ith constraint.

• A is called constraint matrix or coefficient matrix.

• b is called the right-hand-side vector.

• If x = (x1 , x2 , ..., xn )T satisfies all the constraints, it is called a feasible point, or

feasible solution.
 10

• The set of all such points is called the feasible region (or feasible set).

Example 1.3.

minimise 2x1 + x2

subject to x1 + x2 ≤ 8,

−3x1 + 5x2 ≤ 10,

x1 ≥ 0, x2 ≥ 0.

• What is the matrix form for this LP?

• What is the feasible region for this LP?

For this example, the problem has two decision variables x1 and x2 . The objective function
to be minimised is 2x1 + x2 . The LP problem is to find a point in the feasible region with
the smallest objective value.

1.5 LP Modeling

Linear programming is an extremely powerful tool for addressing a wide range of

practical problems. It is used extensively in business, economics, and engineering prob-
lems. LP models have been widely used in transportation, energy, telecommunications,
manufacturing, production planning, routing, flight crew scheduling, resource allocation,
assignment, and design, to name but a few.

Basic steps in the development of an LP model:

• Determine the decision variables.

• Determine the objective function.

• Determine the explicit constraints.

• Determine the implicit constraints.

 11

Example 1.4 (Production Planning).

• A manufacturing firm has to decide on the mix of Ipads and IPhones to be produced.

• A market research indicated that at most 1000 units of Ipads and 4000 units of
IPhones can be sold per month.

• The maximum number of work-hours available is 50,000 per month.

• To produce one unit, an Ipad requires 20 work-hours and an IPhone requires 15

work-hours.

• The unit profits of the Ipads and IPhones are £300 and £400 respectively.

It is desired to find the number of unites of Ipads and IPhones that the firm must produce
in order to maximise its profit.

Determine the decision variables. Suppose that the number of the units for Ipads is x1
and the number of the units for IPhones is x2 .

Determine the explicit constraints. There are two kinds of constraints: The market
constraints and work-hours restriction. For the former, we have

x1 ≤ 1000,

x2 ≤ 4000.

For the latter, we have

20x1 + 15x2 ≤ 50, 000.

Determine the objective function. The total profit is given by

300x1 + 400x2 .

Determine the implicit constraints. The number of Ipads and IPhones cannot be neg-
ative, so x1 , x2 ≥ 0.
 12

Therefore, the problem is formulated as the following linear programming problem:

maximise 300x1 + 400x2

subject to 20x1 + 15x2 ≤ 50, 000,

x1 ≤ 1000,

x2 ≤ 4000,

x1 , x2 ≥ 0.

Example 1.5 (The Workforce Planning Problem). Consider a restaurant that is open
seven days a week. Based on past experience, the number of workers needed on a partic-
ular day is given as follows:

Day Mon Tue Wed Thu Fri Sat Sun

Number 14 13 15 16 19 18 11

Every worker works five consecutive days, and then takes two days off, repeating this pat-
tern indefinitely. How can we minimise the number of workers that staff the restaurant?

Define the variables: Let the days be numbers 1 through 7 and let xi be the number of
workers who begin their five-day shift on day i.

Let us consider Monday as an example. People work on Monday must start to work on
Thur, Fri, Sat, Sun and Monday. Thus the total number of workers on Monday is

x1 + x4 + x5 + x6 + x7

which is at least 14. So we have the following constraints

x1 + x4 + x5 + x6 + x7 ≥ 14.

Similarly, we may consider other days. Thus, the linear programming model for this
problem is given as follow.
 13

7
X
min xi
i=1
s.t x1 + x4 + x5 + x6 + x7 ≥ 14 (M on),

x1 + x2 + x5 + x6 + x7 ≥ 13 (T ue),

x1 + x2 + x3 + x6 + x7 ≥ 15 (W ed),

x1 + x2 + x3 + x4 + x7 ≥ 16 (T hur),

x1 + x2 + x3 + x4 + x5 ≥ 19 (F ri),

x2 + x3 + x4 + x5 + x6 ≥ 18 (Sat),

x3 + x4 + x5 + x6 + x7 ≥ 11 (Sun),

xi ≥ 0, i = 1, ..., 7.

Example 1.6 (The Diet Problem).

• There are m different types of food, F1 , . . . , Fm , that supply varying quantities of the
n nutrients, N1 , . . . , Nn , that are essential to good health.

• Let cj be the minimum daily requirement of nutrient Nj .

• Let bi be the price per unit of food Fi .

• Let aij be the amount of nutrient Nj contained in one unit of food Fi .

The problem is to supply the required nutrients at minimum cost.

Let yi be the number of units of food Fi to be purchased per day.

The cost per day of such a diet is

b1 y1 + b2 y2 + · · · + bm ym . (1.1)

The amount of nutrient Nj contained in this diet is

a1j y1 + a2j y2 + · · · + amj ym

for j = 1, . . . , n.
 14

We need to ensure that all the minimum daily requirements are met, that is,

a1j y1 + a2j y2 + · · · + amj ym ≥ cj , j = 1, . . . , n. (1.2)

Of course, we cannot purchase a negative amount of food. So we have

y1 ≥ 0, y2 ≥ 0, . . . , ym ≥ 0. (1.3)

The problem is to minimise (1.1) subject to (1.2) and (1.3). This is exactly the following
LP problem:

minimise b1 y1 + b2 y2 + · · · + bm ym
s.t a1j y1 + a2j y2 + · · · + amj ym ≥ cj , j = 1, . . . , n,
y1 ≥ 0, y2 ≥ 0, . . . , ym ≥ 0.

Example 1.7 (The Transportation Problem).

• There are I production plants, P1 , ..., PI , that supply a certain commodity, and there
are J markets, M1 , . . . , MJ , to which this commodity must be shipped.

• Plant Pi possesses an amount si of the commodity (i = 1, 2, . . . , I), and market Mj

must receive the amount rj of the commodity (j = 1, . . . , J).

• Let cij be the cost of transporting one unit of the commodity from plant Pi to market
Mj .

The problem is to meet the market requirements at minimum transportation cost.

1) Let xij be the quantity of the commodity shipped from plant Pi to market Mj .

2) The total transportation cost is

I X
X J
xij cij . (1.4)
i=1 j=1
 15

The amount sent from plant Pi is

J
X
xij
j=1

and since the amount available at plant Pi is si , we must have

J
X
xij ≤ si , for i = 1, . . . , I. (1.5)
j=1

3) The amount sent to market Mj is

I
X
xij
i=1

and since the amount required there is rj , we must have

I
X
xij ≥ rj , j = 1, . . . , J. (1.6)
i=1

4) It is assumed that we cannot send a negative amount from plant Pi to Mj . So, we

have
xij ≥ 0, i = 1, . . . , I, j = 1, . . . , J. (1.7)

The problem is to minimise the objective (1.4) subject to the constraints (1.5), (1.6) and
(1.7), i.e.,

I X
X J
minimise xij cij
i=1 j=1
J
X
s.t xij ≤ si , i = 1, . . . , I,
j=1
I
X
xij ≥ rj , j = 1, . . . , J,
i=1
xij ≥ 0, i = 1, . . . , I, j = 1, . . . , J.

Example 1.8 (The Assignment Problem).

• There are 100 persons available for 10 jobs.

• The value of person i working 1 day at job j is aij (i = 1, . . . , 100, j = 1, . . . , 10).

 16

• Let us suppose that only one person is allowed on a job at a time (two people cannot
work on the same job at the same time).

The problem is to choose an assignment of persons to jobs to maximise the total value.

An assignment is a choice of numbers, xij, for i = 1, . . . , 100, and j = 1, . . . , 10, where

xij represents the proportion of person i’s time that is to be spent on job j. Thus,
10
X
xij ≤ 1, i = 1, . . . , 100, (1.8)
j=1

100
X
xij ≤ 1, j = 1, . . . , 10, (1.9)
i=1

and
xij ≥ 0, i = 1, . . . , 100, j = 1, . . . , 10. (1.10)

• Inequality (1.8) reflects the fact that a person cannot spend more than 100 percentage
of their time working.

• Inequality (1.9) means that the total time spent on a job is not allowed to exceed a
day.

• (1.10) says that no one can work a negative amount of time on any job.

Subject to constraints (1.8), (1.9) and (1.10), we wish to maximise the total value,
100 X
X 10
aij xij . (1.11)
i=1 j=1

This is the following LP problem:

100 X
X 10
max aij xij
i=1 j=1
10
X
s.t xij ≤ 1, i = 1, . . . , 100,
j=1
100
X
xij ≤ 1, j = 1, . . . , 10,
i=1
xij ≥ 0, i = 1, . . . , 100, j = 1, . . . , 10.
 17

1.6 Standard Forms of LPs:

minimise cT x

subject to Ax = b,

x ≥ 0.

Throughout this course, we call the above minimization problem as a standard form. In
fact, any LP problem can be converted to this form.

Reduction to the standard form:

• An inequality can be easily transformed into an equality by adding a slack vari-

able
dT x ≤ α ⇐⇒ dT x + t = α, t ≥ 0,

dT x ≥ α ⇐⇒ dT x − t = α, t ≥ 0.

In matrix form:
Ax ≤ b ⇐⇒ Ax + s = b, s ≥ 0.

• A ‘free’ variable can be replaced by two nonnegative variables: If xj is unrestricted

in sign, then
xj = x′j − x′′j , where x′j , x′′j ≥ 0.

• Converting a maximization (minimization) problem into a minimization (max-

imization) problem: Note that over any feasible region, we have

maximum cT x = −minimum (−cT x).

So, by multiplying the coefficients of the objective function by −1, the maximization
problem can be converted into a minimization problem.

• Eliminating upper and lower bounds:

Lj ≤ xj ≤ Uj ⇐⇒ xj ≤ Uj and xj ≥ Lj

which are reduced to the first case.

 18

Example 1.9. Write down the standard form of the following linear programming:

max 4x1 + x2 − x3
s.t. x1 + 3x3 ≤ 6,
3x1 + x2 + 3x3 ≥ 9,
x1 , x2 ≥ 0, x3 is unrestricted in sign.

Example 1.10. Write down the standard form of the following linear programming:

min 3x1 − 4x2 + 2x3

s.t. 5x1 − 3x2 + x3 ≥ 7,
−4x1 + 9x3 ≤ 10,
x1 + x2 − 2x3 = 5,
x1 ≥ 0, x3 ≥ 0.

1.7 Canonical Form of LPs

The LP problem

min cT x max cT x
s.t. Ax ≥ b (or in maximum form) s.t. Ax ≤ b
x≥0 x≥0

is called the canonical form of the LP.

Later, we will see that the canomical form is very useful in the duality representation
of LPs. Introducing a slack vector, the canonical form can be easily converted to the
standard form
min cT x
s.t. Ax − s = b
x ≥ 0, s ≥ 0.

Conversely, a standard from can be easily transformed to a canonical form. (Do this
exercise)
 19

1.8 A brief history of LPs

Linear programming was developed during the second world war to plan expenditures
and returns in order to reduce costs to the army and increase losses to the enemy.

It was kept secret until 1947. Postwar, many industries found its use in their daily
planning.

• Leonid Kantorovich, a Russian mathematician, developed linear programming

problems in 1939.

• George B. Dantzig published the simplex method in 1947.

• John von Neumann developed the theory of the duality in the same year.

• The linear programming problem was first shown to be solvable in polynomial time
by Leonid Khachiyan in 1979.

• A larger theoretical and practical breakthrough in the field came in 1984 when
Narendra Karmarkar introduced a new interior point method for solving linear
programming problems.
Chapter 2

LPs with 2 Variables: Geometric

Method

In this chapter, we will study LPs with 2 variables and how to solve them using the
geometric method. Topics that will be covered:

• notion of steepest descent,

• graphical method for solving LPs with two variables.

At the end of this chapter students should be able to use geometric method to solve a
two variable LP problem determining whether it is infeasible, unbounded or has a finite
solution.

[DT97, Chapter 2] presents similar topics to this chapter that you may find helpful.

20
 21

The following result contains the underlying idea of the geometric method for solving
LPs with two variables that we will study in this chapter.

Proposition 2.1. Let f (x) be a continuously differentiable function where x ∈ Rn . At

any point x, moving in the direction of gradient ∇f (x) ̸= 0 for any small stepsize, the
function value increases, and moving in the direction −∇f (x) for any small stepsize, the
function value decreases.

(Why?) This can be seen from the directional derivative:

f (x + λd) − f (x)
lim = ∇f (x)T d.
λ→0 λ
Corollary 2.2. Moving in the direction c, the value of the function cT x increases; moving
in the direction −c, the function value decreases.

Geometric solution:

Minimizing cT x corresponds to moving the line cT x =constant in the direction of −c

as far as possible.

• When the feasible region is unbounded, we might move the lane indefinitely while
always intersecting the feasible region, and hence the problem is unbounded .

• For a bounded and some unbounded feasible regions, the objective lane moves and
must stop at a certain point, otherwise it goes beyond the feasible region. In such
cases, the problem has a finite optimal solution.

• The feasible set might be empty, and hence the problem is infeasible.

Example 2.3 (Finite solution case). Solve the LP geometrically (or graphically)

minimise x1 + x2

subject to 2x1 + x2 ≤ 6,

−x1 + x2 ≤ 4,

x1 , x2 ≥ 0.
 22

Three steps to solve the problem:

1 . Sketch the feasible set

2 . Choose one point in the feasible set and draw the objective hyperplane (in the case
of in the direction of 2 variables this is just a line)

3 . For a minimisation problem, move the objective hyperplane in the direction of

−c to reach the optimal solution. For a maximisation problem, move the objective
hyperplane in the direction of c to obtain the optimal solution.

x2

-x1+x2=4

Objective
hyper plane

(0,0) x1 (0,0)

2x1+x2=6
-c

Figure 2.1: Geometric solution

Example 2.4 (Unbounded case). Solve the LP geometrically

maximise x1 + x2

subject to −x1 + x2 ≤ 4,

x1 , x2 ≥ 0.

Still, we follow the above three steps and it is easy to see from Figure 2 that this problem
has unbounded solution (no finite optimal solution).
 23

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
-x1+x2=4
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x2 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Unbounded
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
feasible region
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx c
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
x
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
x1
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx c
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Objective function

Figure 2.2: Geometric solution

Example 2.5 (Infeasible case). Solve the LP geometrically

minimise x1 + x 2

subject to −x1 + x2 ≥ 4,

x1 − 2x2 ≥ 6,

x1 , x2 ≥ 0.

In summary, given an LP, there are only three cases:

1 . The problem has a finite optimal solution (unique optimal solution or infinitely
many optimal solutions).

2 . The solution of LP is unbounded.

3 . The problem is infeasible, i.e., the feasible region is empty.

Chapter 3

Introduction to Convex Analysis

In this chapter, we study basic knowledge in convex analysis that will be used in
subsequent chapters. The following topics will be covered

• basic concepts in convex analysis (convex set, convex functions, etc)

• extreme points and directions,

• representation of polyhedra.

At the end of this section, students should be able to

• understand basics concepts in convex analysis,

• compute extreme points and extreme directions of simple convex sets.

[BT97, Chapter 2] contains similar material to this chapter that you may find useful.

3.1 Basic concepts in convex analysis

Hyperplane and half-space:

• A hyperplane H in Rn is a set of the form

{x : pT x = α}

where p is a nonzero vector called the normal or the gradient to the hyperplane.

24
 25

• A hyperplane divides Rn into two regions, called half-spaces. A half-space is the

collection of points of the form

{x : pT x ≥ α} or {x : pT x ≤ α}.

We often use the following symbols:

H = {x : pT x = α},

H + = {x : pT x ≤ α},

H − = {x : pT x ≥ α}.

Definition 3.1. • A polyhedron P ⊂ Rn is the set of points that satisfy a finite

number of linear inequalities, i.e.,

P = {x : Ax ≤ b},

where A is an m × n matrix and b ∈ Rm .

• A bounded polyhedron is called a polytope.

Convex set

A set T is a convex set if x1 , x2 ∈ T implies that λx1 + (1 − λ)x2 ∈ T for all 0 ≤ λ ≤ 1.

Proposition 3.2. (i) Any hyperplane H = {x : pT x = β} is convex.

(ii) The half-spaces {x : pT x ≥ β} and {x : pT x ≤ β} are convex.

Proof. Suppose x̂ and x̄ are elements in H. Then any point of the form

x(α) = αx̂ + (1 − α)x̄

where α can be any number in (0, 1), satisfies

pT x(α) = αpT x̂ + (1 − α)pT x̄ = αβ + (1 − α)β = β.

The proof for the half spaces is the same by changing the = signs into ≥ or ≤.
 26

y
x

x y

Convex Nonconvex

Figure 3.1: Convex and nonconvex sets

Proposition 3.3. (i) The intersection of convex sets is convex.

(ii) A polyhedron is convex.

Proof of (i). Let S1 , ..., Sn be convex sets in Rn . Let

n
\
S= Si
i=1

be the intersection of Si ’s. We now prove that S is a convex set. Indeed, let x, y ∈ S.
We now prove that for any α ∈ (0, 1), we have x(α) = αx + (1 − α)y ∈ S. In fact, since
x, y ∈ S which is the intersection of Si ’s, the vectors x and y are in Si for all i = 1, ..., n.
By the convexity of Si , we must have

x(α) = αx + (1 − α)y ∈ Si , ∀i = 1, ..., n.

Thus x(α) is in the intersection of these sets, and hence x ∈ S.

[Proof of (ii)] Since each half-space is convex, and a polyhedron is the intersection of
a finite number of half-spaces, any polyhedron is convex.

Proposition 3.4. If a linear programming problem has a finite optimal solution, then it
has either a unique solution or infinitely many solutions.

Proof. Consider the linear programming problem

min cT x
s.t Ax = b,
x ≥ 0.
 27

Suppose that the optimal solution of the LP is not unique. Then it has at least two
different optimal solutions, denoted by x
b and x̄.

Since x
b and x̄ are optimal solutions, they must be feasible to the problem, and the
objective values at these two solutions are equal, i.e.

Ax̂ = b, x̂ ≥ 0, Ax̄ = b, x̄ ≥ 0

and
cT x̂ = cT x̄ = z ∗ ,

where z ∗ denotes the optimal objective value.

Therefore x̂ and x̄ belong to the same hyperplane cT x = z ∗ and to the same polyhedron
{x|Ax = b} which are convex sets. This proves that any point in the segment αx̂+(1−α)x̄,
for α ∈ (0, 1) is a optimal solution.

Cone and Convex Cone

A set C is called a cone if x ∈ C implies that λx ∈ C for all λ ≥ 0. A convex cone is

a convex set and cone.

Proposition 3.5. A polyhedron is a cone if and only if it can be represented as

P = {x : Ax ≤ 0}

for some matrix A.

Proof. If the set can be represented as P = {x : Ax ≤ 0} for some matrix A, then for any
x ∈ P we have αx ∈ P for any α ≥ 0. Thus, P is a cone.

Conversely, if P is a polyhedron and a cone, then there exists a matrix A and a vector
b such that P can be represented as

P = {x : Ax ≤ b}.

Moreover, by the definition of cone, for any x ∈ P , it must hold that αx ∈ P for any
α ≥ 0. In particular, by taking α = 0, we see that 0 ∈ P , thus b ≥ 0. Let α > 0 be any
 28

sufficiently large number, it follows from A(αx) ≤ b that Ax ≤ 0. Thus P ⊆ {x : Ax ≤ 0}.

Since b ≥ 0, it further implies that

P ⊆ {x : Ax ≤ 0} ⊆ P,

so P = {x : Ax ≤ 0}.

Convex function

A function f of the vector (x1 , x2 , . . . , xn ) is said to be convex if the following inequality

holds for any two vectors x, y ∈ Rn :

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀λ ∈ [0, 1].

In 1-dimensional case, the foregoing inequality can be interpreted as follows: λf (x) +

(1 − λ)f (y) represents the height of the segment joining (x, f (x)) and (y, f (y)) at the
point λx + (1 − λ)y. The convexity means the height of the segment is at least as large
as the height of the function itself.

Proposition 3.6. The objective function cT x is convex.

Proof. This can be verified directly. Let x, y ∈ Rd and λ ∈ [0, 1], then

cT (λx + (1 − λ)y) = λcT x + (1 − λ)cT y.

Example 3.7. The function f (x) = x2 , x ∈ R, is convex. Indeed, let x, y ∈ R and

λ ∈ [0, 1]. We need to verify that

f (λx + (1 − λ)y) = (λx + (1 − λ)y)2 ≤ λf (x) + (1 − λ)f (y) = λx2 + (1 − λ)y 2 .

By subtracting the left-hand side from the right-hand side, the above equality is equivalent
to
λ(1 − λ)(x − y)2 ≥ 0,

which is true for all x, y ∈ R and λ ∈ [0, 1].

 29

A B

F C

E D

Extreme points

In summary,

• the feasible set of linear programming is a polyhedron,

• the feasible region of LPs is a convex set, and

• the objective of the LP is a convex function.

3.2 Extreme Points, Directions, Representation of

Polyhedra

Definition 3.8 (Extreme point). A point x in a convex set X is called an extreme point
of X, if x cannot be represented as a strict convex combination of two distinct points in
X. In other words, if x = λx1 + (1 − λ)x2 with 0 < λ < 1 and x1 , x2 ∈ X then it must
have x = x1 = x2 .

Definition 3.9 (Rays). Let d ̸= 0 be a vector and x0 be a point. The collection of points
of the form {x0 + λd : λ ≥ 0} is called a ray.

x0 is called the vertex of the ray, and d is the direction of the ray.

Definition 3.10 (Direction of a convex set). Given a convex set, a vector d ̸= 0 is called
direction (or recession direction) of the set, if for each x0 in the set, the ray {x0 + λd :
λ ≥ 0} also belongs to the set.

Therefore, starting at any point x0 in the set, one can recede along d for any step
length λ ≥ 0 and remain within the set.
 30

Example 3.11.

1. What is the direction of bounded convex set?

2. What is the direction of polyhedron X = {x : Ax ≤ b, x ≥ 0}?

3. What is the direction of polyhedron X = {x : Ax = b, x ≥ 0}?

Example 3.12. Consider the set

X = {(x1 , x2 )T : x1 − 2x2 ≥ −6, x1 − x2 ≥ −2, x1 ≥ 0, x2 ≥ 1}.

What is the direction of X?

Let x0 = (x1 , x2 )T be an arbitrary fixed feasible point. Then d = (d1 , d2 )T is a direction of

X if and only if
(d1 , d2 )T ̸= 0

and
x0 + λd = (x1 + λd1 , x2 + λd2 )T ∈ X, ∀λ ≥ 0.

Therefore,

x1 − 2x2 + λ(d1 − 2d2 ) ≥ −6,

x1 − x2 + λ(d1 − d2 ) ≥ −2,

x1 + λd1 ≥ 0,

x2 + λd2 ≥ 1,

for all λ ≥ 0. Since the last two inequalities must hold for fixed x1 and x2 and for all
λ ≥ 0, we conclude that d1 , d2 ≥ 0. Similarly, from the first two inequalities above, we
conclude that
d1 − 2d2 ≥ 0, d1 − d2 ≥ 0.

Since d1 , d2 ≥ 0, from d1 ≥ 2d2 it implies that d1 ≥ d2 . Therefore, (d1 , d2 )T is a direction

of X if and only if it satisfies the following conditions:

(d1 , d2 )T ̸= 0,

d1 ≥ 0, d2 ≥ 0, d1 ≥ 2d2 .
 31

Definition 3.13 (Extreme direction of a convex set). An extreme direction of a convex

set is a direction of the set that cannot be represented as a positive combination of two
distinct directions of the set.

Two directions d and d are said to be distinct if d cannot be represented as a positive

multiple of d, i.e., d ̸= αd for any α ≥ 0.

Example 3.14. 1. What is the extreme direction of the set X in Example 3.12?

2. What is the extreme direction of the first orthant {x : x ≥ 0}?

Theorem 3.15. A polyhedron

P = {x ∈ Rn : Ax ≤ b} =
̸ ∅

has a finite number of extreme points and extreme rays.

Proof. This theorem can be proved directly using convex analysis. However, that ap-
proach is beyond the scope of this course. Instead, as will be seen in Theorem 5.5, the
set of extreme points of a polyhedron is the same as the set of basic feasible solution of
a linear programming problem defined on the polyhedron. Thus the number of extreme
points is the same as the number of basic feasible solution, which is finite (cf. Section
1).

Theorem 3.16. Let P be a polyhedron. If the LP problem

min{cT x : x ∈ P }

has a finite optimal solution, then there is an optimal solution that is an extreme point.

Proof. Similarly as Theorem 3.15, this theorem can also be proved directly using convex
analysis. However, it can be seen as a direct consequences of Theorem 5.5 and Theorem
5.6 in Chapter 5.

How to find an extreme direction?

 32

Finding an extreme direction of a polyhedron can be converted into finding an extreme

point of another polyhedron called recession cone.

1). Consider the set

X = {x : Ax ≤ b, x ≥ 0}.

The direction of the set is characterized by the following conditions:

d ≥ 0, d ̸= 0, and Ad ≤ 0.

This defines a polyhedral cone, called recession cone.

To eliminate duplication, these directions may be normalized, e.g. eT d = 1. Then the set
of recession directions of X can be given by

D = {d : Ad ≤ 0, eT d = 1, d ≥ 0}.

Therefore, the extreme directions of X are precisely the extreme points of D.

2). Similarly, we may prove that the extreme directions of the nonempty polyhedral set

X = {x : Ax = b, x ≥ 0}

correspond to extreme points of the following set:

D = {d : Ad = 0, eT d = 1, d ≥ 0}.

Representation of a Polyhedron

Convex combination

When 0 ≤ α ≤ 1, the point αx + (1 − α)y is called the convex combination of x and y. It

is the line segment between x and y.

In general, we have the following definition.

Definition 3.17. A vector b is said to be convex combination of the vectors u1 , ..., uk if

k
X k
X
b= λj uj , where λj = 1, λj ≥ 0, j = 1, ..., k.
j=1 j=1
 33

 
2/3
Example 3.18. Write b =   as a convex combination of three vectors
1/2
     
1 0 1
u1 =   , u2 =   , u3 =  
0 1 1

We need to find α, β, γ ≥ 0 such that

b = αu1 + βu2 + γu3 and α + β + γ = 1.

These are equivalent to 




 α + γ = 2/3,



β + γ = 1/2,


α + β + γ = 1,







α, β, γ ≥ 0.


This system can be easily solved directly to obtain

α = 1/2, β = 1/3, γ = 1/6.

Thus b is written as a convex combination of {u1 , u2 , u3 } as

1 1 1
b = u1 + u2 + u3 .
2 3 6

The following theorem provides an important representation of a polyhedron in terms

of extremes points and extreme rays. The proof is beyond the scope of the lecture notes
and hence is omitted.

Theorem 3.19 (Minkowski’s Theorem). If P = {x ∈ Rn : Ax ≤ b} is nonempty and

rank (A) = n, then

n k
X l
X k
X
j i
P = x: x= λj x + µi d , λj = 1,
j=1 i=1 j=1
o
λj ≥ 0, j = 1, ..., k, µi ≥ 0, i = 1, ..., l

where {x1 , x2 , ..., xk } is the set of extreme points of P and {d1 , d2 , ..., dl } is the set of
extreme rays of P.
Chapter 4

Duality theory

In this chapter we will study an important topic of LP, namely duality theory. Duality
in linear programming is essentially a unifying theory that develops the relationships
between a given LP problem (the primal problem) and another related LP problem (the
dual problem). We also study the optimality condition, i.e., the so-called Karush-Kuhn-
Tucker (KKT) optimality condition, for LP problems. The duality theory and optimality
conditions form the backbone of linear and nonlinear optimisation problems.

The following topics will be covered

• definition of a dual problem,

• weak duality theorem,

• strong duality theorem,

• optimality conditions,

• complementary slackness condition,

• some further applications of duality theory.

At the end of this chapter, students should be able to

• formulate a dual problem of a LP,

• understand weak and strong duality theorems,

• understand the derivation of optimality conditions from duality theorems,

34
 35

• write down optimality conditions for a LP problem.

[BT97, Chapter 5] and [DT97, Chapter 5] contain relevant topics to this chapter that you
may find helpful.

4.1 Motivation and derivation of dual LP problems

Let us consider a common situation in economics: minimising cost vs. maximising

profit.

Example 4.1 (minimising cost vs. maximising profit). There are two products, A and
B, that are made up from two elements, e and f . Product A contains 5 units of element
e and 2 units of element f and can be sold with price 16 Yuan, while product B contains
3 units of element e and 4 units of element f and can be sold with price 10 Yuan.

Consumption/customer’s perspective: A customer wants to buy some product A and

B. To fulfill his/her task, the customer needs at least 100 units of element e and 60 units
of element f . How many (units of ) product A and B should the customer buy in order to
minimise the cost?

Let x and y be the units of product A and B that the customer buys. The above
problem can be formulated into a minimising LP problem as follows

Minimise 16x + 10y (the total cost)

subject to

5x + 3y ≥ 100 (the total units of element e),

2x + 4y ≥ 60 (the total units of element f ),

x, y ≥ 0 (the customer needs both products).

This LP can be written in a matrix form as follows

Minimise cT x̄,

subject to 
Ax̄ ≥ b,


x̄ ≥ 0,

 36

where        
x 5 3 100 16
x̄ =   , A= , b =  , c =  .
y 2 4 60 10

Production’s perspective. Now the supplier want to assign price for each unit of element
e and f so that the customer’s need can be met and the profit is maximal. Let u and v
be the price that the supplier should assign to each unit of element e and f . His/her task
can be formulated into the following maximising LP problem

maximise 100u + 60v (the total profit)

subject to

5u + 2v ≤ 16 (the price for product A should not exceed 16 Yuan),

3u + 4v ≤ 10 (the price for product B should not exceed 10),

u, v ≥ 0 (the prices for each unit of each element).

We also can write this LP in a matrix form using the notations above as

maximise bT ȳ,

subject to 
AT ȳ ≤ c,


ȳ ≥ 0,


where ȳ = (u, v)T . These are two dual problems.

Suppose now in Example above we only know the minimisation problem. How do we
attempt to solve this? Since we are looking for a minimum value of the objective function,
we first need to find a lower bound for it. To do so, we combine the constraints to obtain
a lower bound of the type

u(5x + 3y) + v(2x + 4y) = (5u + 2v)x + (3u + 4v)y ≥ 100u + 60v, (4.1)

by multiplying the first and second constraints by u ≥ 0 and v ≥ 0 respectively then

adding them up. To ensure that the newly obtained estimate provides a lower bound for
the objective function, we require that

5u + 2v ≤ 16 and 3u + 4v ≤ 10.
 37

Finally to achieve the best optimal lower bound for the objective function, we should
maximise the lower bound in (4.1)

maximise 100u + 60v.

Bringing all steps together, we end up with the following problem

maximise 100u + 60v.

subject to 
5u + 2v ≤ 16,






 3u + 4v ≤ 10,



u, v ≥ 0


This is exactly the problem from the production’s perspective in Example 4.1.

4.2 Primal and dual problems of LPs

Duality deals with pairs of LPs and the relationship between their solutions. One
problem is called primal and the other the dual. It does not matter which problem is
called the primal since the dual of the dual is the primal (see Proposition 6.5 below).

Let A be an m × n matrix, b ∈ Rm and c ∈ Rn . We define the standard LP as the primal

problem.

Primal Problem:

(LP ) minimise cT x

s.t. Ax = b, x ≥ 0.

The key idea of duality begins by observing that every feasible x produces an upper bound,
cT x, for the minimum of (LP). Solving (LP) corresponds to minimising upper bounds.
But what if we instead maximise lower bounds?

That is, we want to solve a problem that looks like

maximise ξ T y

s.t. ???,
 38

so that for every feasible y, ξ T y ≤ cT x for all feasible x. How is this possible, how can ξ
know about x for every feasible x? Well, one of the only things we know about x is that
Ax = b, so lets try ξ = b and see what happens. Then,

bT y = (Ax)T y = xT AT y = (AT y)T x

and so, since x ≥ 0 for all feasible x, all we need to get our desired bT y ≤ cT x, for all
feasible x, is to require that AT y ≤ c.

Therefore, (LP)’s dual problem is defined by

Dual problem:

(DP ) maximise bT y

s.t. AT y ≤ c,

where y ∈ Rm .

By introducing a slack vector, the dual problem can be equivalently written as

(DP ) maximise bT y

s.t. AT y + s = c, s ≥ 0

where s ∈ Rn is called the dual slack variable.

Example 4.2. Find the dual problem to the LP

minimise 6x1 + 8x2

s.t. 3x1 + x2 − x3 = 4,

5x1 + 2x2 − x4 = 7,

x1 , x2 , x3 , x4 ≥ 0.

By the definition, the dual problem of the above LP is

maximise 4w1 + 7w2

s.t. 3w1 + 5w2 ≤ 6

w1 + 2w2 ≤ 8

−w1 ≤ 0

−w2 ≤ 0.
 39

When an LP is not given in standard form, we may first convert them to the standard
form, and then write down their dual problems.

Example 4.3. Find the dual problem to the LP

minimise 6x1 + 8x2

s.t. 3x1 + x2 − x3 ≥ 4,

5x1 + 2x2 − x4 ≤ 7,

x1 , x2 , x3 ≥ 0, x4 is free.

Proposition 4.4. If the primal problem is given by (canonical form)

(LP ) minimise cT x

s.t. Ax ≥ b, x ≥ 0,

then its dual problem is

(DP ) maximise bT y

s.t. AT y ≤ c, y ≥ 0.

Example 4.5. Find the dual problem to the LP

minimise 6x1 + 8x2

s.t. 3x1 + x2 − x3 ≥ 4,

5x1 + 2x2 − x4 ≤ 7,

x1 , x2 , x3 , x4 ≥ 0.

Proposition 4.6. The dual of the dual is the primal.

Proof. Suppose that the following standard LP is the primal problem:

(LP ) minimise cT x

s.t. Ax = b, x ≥ 0.

According to the definition, the dual problem of the LP is given by

(DP ) maximise bT y

s.t. AT y + s = c, s ≥ 0.
 40

We now consider the dual of (DP). First we transform this problem as the standard form.
Thus we have

(DP ) minimise −bT y ′ + bT y ′′

s.t. AT y ′ − AT y ′′ + s = c, s ≥ 0, y ′ ≥ 0, y ′′ ≥ 0.

This can be written as

 
′
y
 
(DP ) minimise (−bT , bT , 0T )  y ′′ 
 
 
s
   
y′ y′
   
s.t. (AT , −AT , I)  y ′′  = c,  y ′′  ≥ 0.
   
   
s s

The dual of this standard form is given by

(DDP ) maximise cT z
 
−b
 
s.t. (AT , −AT , I)T z ≤  b  ,
 
 
0

which can be further written as

(DDP ) maximise cT z

s.t. Az ≤ −b, −Az ≤ b, z ≤ 0.

It is equivalent to

(DDP ) minimise −cT z

s.t. −Az = b, z ≤ 0.

Setting w = −z, the above problem becomes

(DDP ) minimise cT w

s.t. Aw = b, w ≥ 0.

This is the primal problem.

 41

4.3 Duality theorem

Denote by Fp and Fd the feasible regions of primal and dual problems, respectively,
i.e.
Fp = {x : Ax = b, x ≥ 0},

Fd = {(y, s) : AT y + s = c, s ≥ 0}.

The following result shows that the objective value at any primal feasible solution is at
least as large as the objective value at any feasible dual solution.

Theorem 4.7 (Weak duality Theorem). Let x be any feasible point of the primal problem,
i.e. x ∈ Fp and y be any feasible point of the dual problem, i.e., (y, s) ∈ Fd . Then

cT x ≥ bT y.

Proof. For any feasible point x ∈ Fp and (y, s) ∈ Fd , we have Ax = b and x ≥ 0, and
s = c − AT y ≥ 0, and thus

cT x − bT y = cT x − (Ax)T y = xT (c − AT y) = xT s ≥ 0.

The last inequality above follows form the fact that (x, s) ≥ 0.

The quantity cT x − bT y is often called the duality gap. From the weak duality theorem
we have the following immediate consequences:

Corollary 4.8. If the primal LP is unbounded (i.e., cT x → −∞) , then the dual LP must
be infeasible.

Corollary 4.9. If the dual LP is unbounded, then the primal LP must be infeasible.

Thus, if either problem has an unbounded objective value, then the other problem pos-
sesses no feasible solution.

Corollary 4.10. If x is feasible to the primal LP, y is feasible to the dual LP, and
cT x = bT y, then x must be optimal to the primal LP and y must be optimal to the dual
LP.
 42

Unboundedness in one problem implies infeasibility in the other problem.

• Is this property symmetric?

• Does infeasibility in one problem imply unboundedness in the other?

The answer is “not necessarily”.

Example 4.11. Consider the primal problem

minimise −x1 − x2

s.t. x1 − x2 ≥ 1,

−x1 + x2 ≥ 1,

x1 , x2 ≥ 0.

Its dual problem is given by

maximise w1 + w2

s.t. w1 − w2 ≤ −1,

−w1 + w2 ≤ −1,

w1 , w2 ≥ 0.

Both problems are infeasible.

The last corollary above identifies a sufficient condition for the optimality of a primal-
dual pair of feasible solutions, namely that their objective values coincide. One natural
question to ask is whether this is a necessary condition. The answer is yes, as shown by
the next result.

Theorem 4.12 (Strong Duality Theorem). If both the primal LP and the dual LP have
feasible solutions, then they both have optimal solutions, and for any primal optimal so-
lution x and dual optimal solution y we have that cT x = bT y.

Proof. As will be seen in Chapter 7 one can solve both the primal and the dual problem
simultaneously using the simplex method.

Therefore, for LPs, exactly one of the following statements is true

 43

• Both problems have optimal solutions x∗ and (y ∗ , s∗ ) with cT x∗ = bT y ∗ .

• One problem has unbounded objective value, in which case the other problem must
be infeasible.

• Both problems are infeasible.

In Summary,

P optimal ⇔ D optimal

P unbounded ⇒ D infeasible

D unbounded ⇒ P infeasible

P infeasible ⇒ D unbounded or infeasible

D infeasible ⇒ P unbounded or infeasible

4.4 Network flow problems

A flow network (also known as a transportation network) is a directed graph where

each edge has a capacity and each edge receives a flow. The amount of flow on an edge
cannot exceed the capacity of the edge. Often in operations research, a directed graph is
called a network, the vertices are called nodes and the edges are called arcs. A flow must
satisfy the restriction that the amount of flow into a node equals the amount of flow out
of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming
flow. A network can be used to model traffic in a computer network, circulation with
demands, fluids in pipes, currents in an electrical circuit, or anything similar in which
something travels through a network of nodes.

Definition 4.13. A network N = (V, E) is a directed graph where V and E are respec-
tively the set of vertices (nodes) and edges (arcs). Given two vertices i, j ∈ V we denote
the edge between them by (i, j).
 44

Definition 4.14. The capacity of an edge is the maximum amount of flow that can pass
through an edge in both directions. Formally it is a map c : E → R+ , called the capacity
map.

In most networks there are one or more nodes which are distinguished. A source is a
node such that all edges trough it are oriented away from it. Similarly a sink is a node
such that all edges trough it are oriented towards it.

Given a function g on the edges g : E → R, denote by gij the value of g on (i, j) ∈ E.

Definition 4.15. A flow is a map f : E → R+ that satisfies the following constraints:

• capacity constraint: The flow of an edge cannot exceed its capacity, in other words:
fij ≤ cij , for each (i, j) ∈ E;

• conservation of flows: The sum of the flows entering a node must equal the sum
P
of the flows exiting that node, except for the sources and the sinks: i:(i,j)∈E fij =
P
k:(jk)∈E fjk , for each v ∈ V \ {S, T }.

In brief: flows generate at sources and terminate at sinks.

Example 4.16 (The max-flow problem). Let N = (V, E) be a directed network with only
one source S ∈ V , only one sink T ∈ V and a set of intermediate nodes. Assume the flow
is never negative, namely if along an edge (i, j) the flow fij is strictly positive, then the
flow fji in the opposite direction is 0. The maximal flow problem is to maximise the flow
from source to sink subject to the network edge capacities and conservation of flow:
X
maximise fSj
i:(S,j)∈E

subject to fij ≤ cij , for each (i, j) ∈ E,

X X
fij = fjk , for each j ∈ V \ {S, T }
i:(i,j)∈E k:(j,k)∈E

fij ≥ 0 for each (i, j) ∈ E.

In the context of flow analysis, there is only an interest in considering how units are
transferred between source and sink. Namely, we can re-write the above linear problem by
considering the whole paths from S to T . Let P be the set of all possible paths from S to
T . We associate with each path p ∈ P a quantity xp specifying how much of the flow from
 45

S to T is being transferred along the path. With this view, the conservation constraint
above is unnecessary and we obtain the following simpler linear programming problem
X
maximise xp
p∈P
X
subject to xp ≤ cij , for each (i, j) ∈ E,
p∈P :(i,j)∈p
xp ≥ 0, for all p ∈ P.

Example 4.17 (The min-cut problem). In graph theory, a cut is a partition of the vertices
of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that
have one endpoint in each subset of the partition. These edges are said to cross the cut.
In a connected graph, each cut-set determines a unique cut, and in some cases cuts are
identified with their cut-sets rather than with their vertex partitions.

In a flow network, an s–t cut is a cut that requires the source and the sink to be in
different subsets, and its cut-set only consists of edges going from the source’s side to the
sink’s side. The capacity of an s–t cut is defined as the sum of the capacity of each edge
in the cut-set

In an unweighted undirected graph, the size or weight of a cut is the number of edges
crossing the cut. In a weighted graph, the value or weight is defined by the sum of the
weights of the edges crossing the cut.

Let N = (V, E) be a directed network with only one source S ∈ V , only one sink
T ∈ V and a set of intermediate nodes. Let yij denote the weight to assign to an edge
(i, j). The problem is to separate S and T with minimum total weighted capacity. The
condition that source and sink are separated can be stated as follows: for every path p ∈ P
from the source S to the sink T , the weight of the path is at least 1.
X
Minimise cij yij
(i,j)∈E
X
subject to yij ≥ 1 ∀p ∈ P
(i,j)∈p

yij ≥ 0 (i, j) ∈ E.

This is the dual problem to the max-flow problem.

The max-flow min-cut theorem is a special case of the duality theorem. It states that
in a flow network, the maximum amount of flow passing from the source to the sink is
 46

equal to the total weight of the edges in the minimum cut. The max-flow min-cut theorem
has many practical applications in networks, transportation and scheduling.

4.5 Optimality Conditions & Complementary slack-

ness

The optimality condition can be obtained by the strong duality theorem from the last
lecture.

The strong duality theorem provides the condition to identify optimal solutions:

x ∈ Rn is an optimal solution of LP if and only if it satisfies the following three conditions:

• x is feasible to the primal, i.e., Ax = b, x ≥ 0.

• There exists a y ∈ Rm such that y is feasible to the dual, i.e., AT y ≤ c.

• There is no duality gap, i.e., cT x = bT y.

Thus we have the following theorem.

Theorem 4.18 (Optimality Condition). Consider the standard LP problem:

minimise cT x

s.t. Ax = b, x ≥ 0,

where b ∈ Rm , c ∈ Rn , and A an m × n matrix. Then x̄ is an optimal solution to the LP

if and only if there exists ȳ such that the following three conditions hold

AT ȳ ≤ c, (4.2)

Ax̄ = b, x̄ ≥ 0, (4.3)

bT ȳ = cT x̄. (4.4)

Proof. (⇒) Suppose that x̄ is optimal to the LP:

• Then x̄ is feasible, so (4.3) holds.

 47

• Since LP is feasible and bounded, the dual problem DP is feasible.

• Hence DP has an optimal solution ȳ with cT x̄ = bT ȳ, by the Strong Duality theorem.
Therefore (4.2) and (4.4) hold.

(⇐) Suppose there exists ȳ such that (4.2), (4.3), and (4.4) hold:

• By (4.2) and (4.3), x̄ is feasible for LP and ȳ is feasible for DP.

• Therefore, by the Strong Duality theorem, there exists x∗ optimal for LP and y ∗
optimal for DP, with cT x∗ = bT y ∗ .

• Therefore bT ȳ ≤ bT y ∗ = cT x∗ ≤ cT x̄.

• Combining this with (4.4), it follows that cT x∗ = cT x̄ and so x̄ is optimal.

Remark. Similarly, the optimality condition for the duality problem is the same as
above.

Therefore, by solving an optimality conditions, we can obtain the optimal solutions for
primal and dual problems at the same time.

The optimality conditions (4.2) - (4.4), can be restated by adding the slack variable
vector s̄ to inequality (4.2), and using the proof of the weak duality problem

cT x̄ − bT ȳ = x̄T s̄.

Therefore, we note that at the optimal solution x∗ and (ȳ, s̄), we have x̄T s̄ = 0, which is
equivalent to x̄j s̄j = 0 for every j = 1, ..., n since the nonnegativity of x̄ and s̄. Thus, at the
optimal solution, one of the terms x̄j and s̄j must be zero. This is called complementary
slackness condition.

As a result, we may restate the optimality conditions as follows.

Theorem 4.19 (Optimality Condition). Consider the standard LP problem

minimise cT x

s.t. Ax = b, x ≥ 0
 48

where b ∈ Rm , c ∈ Rn , A ∈ Rm×n . Then x̄ is an optimal solution to the LP if and only if

there exists ȳ such that the following three conditions hold

AT ȳ + s̄ = c, s̄ ≥ 0. (Dual feasibility)

Ax̄ = b, x̄ ≥ 0. (Primal feasibility)

x̄T s̄ = 0. (Complementary slackness condition)

Example 4.20. What is the optimality condition of the following LP?

minimise −2x1 − x2

s.t. x1 + 2x2 ≥ 15,

−x1 − x2 ≥ −20,

x1 , x2 ≥ 0.

Verify that whether (15,0) and (20, 0) are optimal solutions to the problem.

Outline of the solution:

• Introduce slack variables x3 and x4 and transform the problem to the standard form

minimise −2x1 − x2

s.t. x1 + 2x2 − x3 = 15,

−x1 − x2 − x4 = −20,

x1 , x2 , x3 , x4 ≥ 0.

• The optimality conditions for this LP are given as follows:

x1 + 2x2 − x3 = 15,

−x1 − x2 − x4 = −20,

x1 , x2 , x3 , x4 ≥ 0,

y1 − y2 ≤ −2,

2y1 − y2 ≤ −1,

−y1 ≤ 0, −y2 ≤ 0,

−2x1 − x2 = 15y1 − 20y2 .

 49

• Consider the point (x1 , x2 ) = (15, 0). From the first two equalities above, we see that
(x3 , x4 ) = (0, 5) satisfies the first three conditions. Thus at x = (15, 0, 0, 5)T the
above optimality conditions are reduced to

y1 − y2 ≤ −2

2y1 − y2 ≤ −1

−y1 ≤ 0, −y2 ≤ 0

−30 = 15y1 − 20y2 .

It is easy to very that this system is inconsistent (there exists no y satisfies these
conditions). Thus, (x1 , x2 ) = (15, 0) is not an optimal solution to the LP.

• Consider the point (x1 , x2 ) = (20, 0). Clearly, this point, together with (x3 , x4 ) =
(5, 0), satisfies the first three conditions of the optimality. We now check if there
exists a y satisfying the remaining conditions, i.e.,

y1 − y2 ≤ −2

2y1 − y2 ≤ −1

−y1 ≤ 0, −y2 ≤ 0

−40 = 15y1 − 20y2 .

Clearly, (y1 , y2 ) = (0, 2) satisfies these conditions, thus the point (x1 , x2 ) = (20, 0)
is an optimal solution to the LP problem.

Example 4.21. Consider the linear program

min 5x1 + 12x2 + 4x3

s.t. x1 + 2x2 + x3 = 10,
2x1 − x2 + 3x3 = 8,
x1 , x2 , x3 ≥ 0.

You are given the information that x2 and x3 are positive in the optimal solution. Use
the complementary slackness condition to solve the dual problem.
 50

Solution: The dual problem is

max 10y1 + 8y2

s.t. y1 + 2y2 ≤ 5,
2y1 − y2 ≤ 12,
y1 + 3y2 ≤ 4.

Since x2 and x3 are positive in the optimal solutions, the corresponding constraints in
the dual problem become equalities. Thus y = (y1 , y2 ) is an optimal solution to the dual
problem if and only if it satisfies the first constraint and the following system

2y1 − y2 = 12 and y1 + 3y2 = 4.

40
Solving this system gives y1 = 7
, y2 = − 47 , which satisfies the first constraint since
32
y1 + 2y2 = < 5.
7
Thus it is an optimal solution to the dual problem.

Note that we can also use this information to find the optimal solution to the primal
problem. In fact, since the first constraint in the dual problem is an inequality, by the
complementary slackness conditions, the first variable in the primal problem is zero, that
22 26
is x1 = 0. Substituting this to the primal constraints, we obtain x2 = 7
, x3 = 7
, which
are nonnegative. Also we can verify that the objective values coincide:
368
10y1 + 8y2 = 5x1 + 12x2 + 4x3 = .
7
Thus y = (40/7, −4/7) and x = (0, 22/7, 26/7) are respectively optimal solutions to the
primal and the dual problems.

If the solution satisfies that (x∗ )T s∗ = 0 and x∗ + s∗ > 0. Such solution is called strictly
complementary solution. The following result shows that an LP always has such a solution,

Theorem 4.22 (Strict Complementarity). If primal and dual problems both have feasible
solutions, then both problems have a pair of strictly complementary solutions x∗ ≥ 0 and
s∗ ≥ 0 with
(x∗ )T s∗ = 0, x∗ + s∗ > 0.

Moveover, the supports

I ∗ = {j : x∗j > 0} and J ∗ = {j : s∗j > 0}

 51

are invariant for all pairs of strictly complementary solutions.

The proof of this theorem can be found in [Gre94] where it is proved that a primal-
dual pair of optimal solutions is unique if and only if it is a strictly complementary pair
of basic solutions, see also Remark 7.4 in Chapter 8 for more discussions.

4.6 More Applications of Duality Theory

Example 4.23. Solve the following LP

minimise x1 + x2 + 6x3

s.t. −x1 + x2 + x3 ≥ 2,

x1 − 2x2 + 2x3 ≥ 6,

x1 , x2 , x3 ≥ 0.

Example 4.24. Using duality theory to prove the Farkas’s Lemma: Only one of the
following systems has a solution (feasible)

• (System 1) Ax = b, x ≥ 0.

• (System 2) AT y ≤ 0, bT y > 0.

Proof. If System 1 has a solution, then for any y such that AT y ≤ 0 we have

bT y = (Ax)T y = xT (AT y) ≤ 0.

The inequality follows from the fact that AT y ≤ 0 and x ≥ 0. So, the System 2 is
impossible to have a solution.

Suppose that the System 1 has no solution, then the following LP

minimise 0T x

s.t. Ax = b, x ≥ 0

is infeasible. According to the duality theorem, its dual problem which is given as

maximise bT y

s.t. AT y ≤ 0
 52

is either unbounded or infeasible. However, this dual problem is feasible (y = 0 a feasible

point), so the dual problem must be unbounded. As a result, there exists a y such that
AT y ≤ 0, bT y > 0 , and the System 2 has a solution.
Chapter 5

The Simplex Method (I): Theory

How to solve a LP problem? George B. Dantzig introduced the simplex method

for solving LPs in 1947. The method has been selected by the editors of Computing
in Science & Engineering / CiSE (January/February 2000, pp. 22-23, vol. 2) as the
second most significant algorithm in the 20-th century. In this chapter, we start to learn
this important method. This chapter will introduce essential concepts and develops the
theory underlying the simplex method. The implementation and analysis of method will
be discussed in subsequent chapters. The following topics will be covered

• review of Linear Algebra,

• basic feasible solutions (BFS),

• reformulation of a LP by the current BFS,

• termination of the iteration and declaration of optimality.

At the end of this chapter, students should be able to

• compute basic feasible solutions,

• formulate a LP by the current BFS,

• understand the principles of the simplex method.

[BT97, Chapter 3] and [DT97, Chapter 3] contain relevant material to this chapter that
you may find useful.

53
 54

5.1 Basic Feasible Solution

5.1.1 Review of Linear Algebra

For matrices, we may perform some elementary row operations. These operations are
most helpful in solving a system of linear equations and in finding the inverse of a matrix.

Elementary row operations:

An elementary row operation on a matrix A is one of the following operations:

1. Row i and row j are interchanged.

2. Row i is multiplied by a nonzero scalar α.

3. Row i is replaced by row i plus α times row j.

Elementary row operation on a matrix is equivalent to pre-multiplying A by a specific

matrix. Elementary column operation on a matrix is equivalent to post-multiplying A by
a specific matrix.

Solving a system of linear equations:

Theorem 5.1. Ax = b if and only if A′ x = b′ , where (A′ , b′ ) is obtained from (A, b)

by a finite number of elementary row operations. (Any elementary row operations never
change the solution of the system of linear equations)

By row operations, A′ can be upper triangular, and then we can solve the system by back
substitution. The process of reducing A to an upper triangular matrix with ones on the
diagonal is called Gaussian Reduction of the system, by further reduction, we may reduce
A to the identity matrix, the process is called a Gauss-Jordan reduction of the system.

Calculation of inverse: By elementary row operations, reducing (A I) to (I B), then

B = A−1 .
 55

5.1.2 Existence of the Optimal Extreme Point

Still, we consider the standard form of LP:

min{cT x : Ax = b, x ≥ 0},

for which we have the following result

Theorem 5.2 (Existence of Optimal Extreme Point). Assume that the feasible region is
nonempty. Then

• an (finite) optimal solution exists if and only if cT dj ≥ 0 for j = 1, ..., l, where

d1 , ..., dl are the extreme directions of the feasible region.

• Otherwise, if there is an extreme direction such that cT dj < 0, then the optimal
objective value of LP is unbounded.

• If an optimal solution exists, then at least one extreme point is optimal.

Proof. Let x1 , x2 , ..., xk be the extreme points of the constraint set. And let d1 , ..., dl be
the extreme directions. By Minkowski’s theorem, any feasible point x can be represented
as
k
X l
X
j
x= λj x + µj dj ,
j=1 j=1

where
k
X
λj = 1, λj ≥ 0, j = 1, ..., k,
j=1

µj ≥ 0, j = 1, ..., l.

Thus, LP can be transformed into the following problem in variables λ and µ:

k
X l
X
T j
Minimize (c x )λj + (cT dj )µj
j=1 j=1
k
X
s.t. λj = 1, λj ≥ 0, j = 1, ..., k,
j=1
µj ≥ 0, j = 1, ..., l.

Since the µj ’s can be made arbitrarily large, the minimum is −∞ if cT dj < 0 for some j.
Thus, the necessary condition for the existence of the optimal solution is

cT dj ≥ 0, ∀j = 1, ..., l.
 56

If this condition holds, we can show that the optimal solution exists and attains at an
extreme point. In fact, if cT dj ≥ 0 for j ≤ l, in order to minimize the objective function,
µj should be taken to be zero for all j. In order to minimize the first term of the objective,
we simply find the minimum cT xj , say cT xp , and let λp = 1, and all other λj ’s equal to
zero.

• In summary, the optimal solution of the linear programming is finite if and only if
cT dj ≥ 0 for all extreme directions.

• Furthermore, if this is the case, then we find the minimum point by picking the
minimum objective value among all extreme points.

• This shows that if an optimal solution exists, we must be able to find an optimal
extreme point.

5.1.3 Basic Feasible Solution

To solve a linear programming algebraically, we need to address the following several

issues.

• How to identify (recognize) an extreme point?

• If the current extreme pint is not optimal, how to move from it to the next better
extreme point?

• How to terminate the algorithm and declare optimality?

To address the first issue, we need the concept of Basic Feasible Solution (or basic
feasible point).

Definition 5.3 (Basic Feasible Solution). Consider the system

Ax = b, x ≥ 0.

where A is an m × n and b ∈ Rm . Suppose A is full rank, i.e., Rank(A) = m. After

possibly rearranging the columns of A, let

A = [B, N ],
 57

 B is an m × m invertible matrix and N is an m × (n − m) matrix. Denote

where
xB
x=  . Then the system become
xN
 
xB
[B, N ]   = b,
xN

i.e.,
BxB + N xN = b.

Note that
xB = B −1 b, xN = 0

is a solution to the above system. This solution is called a basic solution. Thus a basic
solution has at least n−m zero variables. In addition, if x is a basis solution then columns
of A corresponding to non-zero variables of x are linearly independent.

• B —— the basic matrix (or simply basis),

• N —— the nonbasic matrix (or simply nonbasis).

• xB —– basic variable

• xN —– nonbasic variable

• If xB ≥ 0, (B −1 b, 0) is called a basic feasible solution of the system.

• If xB = B −1 b > 0, then x = (B −1 b, 0) is called a non-degenerate basic feasible

solution, otherwise degenerate basic feasible solution.

Remark 1. The possible number of basic feasible solutions is bounded by the number of
ways of extracting m columns from A to form the basis, so in general,
 
n n!
the number of basic feasible solution ≤  = .
m m!(n − m)!

Example 5.4. Consider the polyhedral set:

x1 + x2 + x3 = 6,

x2 + x4 = 3,
 58

x1 , x2 , x3 , x4 ≥ 0.

The constraint matrix

 
1 1 1 0
A = [a1 , a2 , a3 , a4 ] =  .
0 1 0 1

The basic feasible solution corresponds to finding 2 × 2 invertible submatrix B. The fol-
lowing are possible ways of extracting B out of A.
         
1 1 x1 3 x 0
1. B = [a1 , a2 ] =   , xB =   = B −1 b =   , xN =  3  =  .
0 1 x2 3 x4 0
         
1 0 x1 6 x 0
2. B = [a1 , a4 ] =   , xB =   = B −1 b =   , xN =  2  =  .
0 1 x4 3 x3 0
         
1 1 x2 3 x 0
3. B = [a2 , a3 ] =   , xB =   = B −1 b =   , xN =  1  =  .
1 0 x3 3 x4 0
       
1 0 x2 6 x
4. B = [a2 , a4 ] =   , xB =   = B −1 b =   , xN =  1  =
1 1 x4 −3 x3
 
0
 .
0
         
1 0 x3 6 x1 0
5. B = [a3 , a4 ] =   , xB =   = B −1 b =   , xN =  = .
0 1 x4 3 x2 0

Note that the points corresponding to 1,2,3, and 5 are basic feasible solutions. The
point obtained in 4 is not a basic feasible solution because it violates the nonnegativity
restrictions. In other words, we have four basic feasible solutions, namely
       
3 6 0 0
       
       
 3   0   3   0 
x1 = 
 
 , x2 =   , x3 =   , x4 =   .
     
 0   0   3   6 
       
0 3 0 3

These points belong to R4 since after introducing the slack variables we have four variables.
There basic feasible solutions, projected in R2 —that is, in the (x1 , x2 )-plane — give rise
to the following four points (3, 3), (6, 0), (0, 3) and (0, 0). These points are precisely the
extreme points of the feasible region.
 59

5.1.4 Correspondence between BFSs & extreme points

Theorem 5.5. A point is a basic feasible solution if and only if it is an extreme point.

Proof. Let S = {x ∈ Rn : Ax = b, x ≥ 0} be the feasible region. Suppose that x is a

basic feasible solution. Then there exists a basis B and a non-basis N such that xN = 0.
Suppose that y, z ∈ S are such that x = λy + (1 − λ)z for some 0 ≤ λ ≤ 1. We have
0 = xN = λyN + (1 − λ)zN . Since yN , zN ≥ 0 we must have yN = zN = 0. Furthermore
since y, z ∈ S, we have

Ay = ByB + N yN = b = Az = BzB + N xN

which implies ByB = BzB = b so B(yB − zB ) = 0. Since B is invertible, we have yB = zB .

Hence y = z. This means x must be extreme.

Now suppose that x is not a basic feasible solution, we need to show that it is not
extreme. Let P = {i : xi > 0} and O = {i : xi = 0}. Since x is feasible Ax =
AP xP + AO xO = b, thus AP xP = b. Since x is not a basic feasible solution, the columns
of AP are linearly dependent. As you have seen in Linear Algebra, there exists a non-zero
k
 yP∈ R , where k is the cardinality of P , such that AP yP = 0. We take yO = 0 and
vector
yP
y =  . Consider two points x + ϵy and x − ϵy for small ϵ. For ϵ > 0 small enough,
yO
these two points are both feasible since A(x ± ϵy) = Ax ± ϵy = b and x ± ϵy ≥ 0. Hence
1 1
x = (x + ϵy) + (x − ϵy).
2 2
So x is not extreme, as desired.

Thus, the set of basic feasible solutions coincides with the set of extreme points (the
former is an algebraic description and the latter is a geometric description). Since an LP
with a finite optimal value has an optimal solution at an extreme point, an optimal basic
feasible solution can always be found for such problems.

Theorem 5.6 (Fundamental theorem of Linear Programming).

i) If there is a feasible solution, i.e., {x : Ax = b, x ≥ 0} =

̸ ∅, then there is a basic feasible
solution

ii) If there is an optimal solution for LP, there is a basic feasible solution that is optimal.
 60

Proof. i) Let P = {x : Ax = b, x ≥ 0} be the feasible region. Suppose that P ̸= ∅ and

x is a feasible solution, that is, Ax = b and x ≥ 0. We will construct a basic feasible
solution from x. Suppose that only first p coordinates of x are strictly positive. Thus

a1 x1 + . . . + ap xp = b, (5.1)

where aj is the j-th column of A. We consider two cases.

Case 1: If a1 , . . . , ap are linearly independent. Then p ≤ m = rank(A).

• If p = m, we take B = [a1 , . . . , ap ], then x is a basic feasible solution with respect

to this basis.

• If p < m, then we can find (m − p) columns from ap+1 , . . . , an to form a basis B to

which x is a basis feasible solution.

Case 2: If {a1 , . . . , ap } are linearly dependent. Then there exist y1 , . . . , yp , not all zero,
such that
y1 a1 + . . . + yp ap = 0. (5.2)

Without loss of generality we can assume that yi > 0 for some i ∈ {1, . . . , p} (otherwise,
we can multiply the above equation by −1). From (5.1) and (5.2) we deduce that

(x1 − εy1 )a1 + . . . + (xp − εyp )ap = b.

Hence A(x − εy) = b where y = (y1 , . . . , yp , 0, . . . , 0)T . For sufficiently small ε we have

x1 − εy1 ≥ 0, . . . , xp − εyp ≥ 0.

We choose ε by
nx o
i
ε = min i = 1, . . . , p; yi > 0 .
yi
Then we have
(x − εy) ≥ 0 and A(x − εy) = b.

Thus (x − εy) is a feasible solution. In addition, due to the choice of ε, the first p
coordinates of (x − εy) are non-negative and at least one of them is zero. Hence we reduce
p by at least 1. By repeating this process, we will either Case 1 or p = 0. In both cases,
there will be a basic feasible solution. This completes the proof of Part i).
 61

Part ii). Suppose that x is an optimal solution. Without loss of generality we assume
that x has minimal number of positive ordinates. We will construct a basic feasible
optimal solution from x. If x = 0 then x is basic (and the cost is zero). If x ̸= 0, let
I = {i1 , . . . , ip } is the set of index such that xij > 0. Similarly as in Part i), there are two
cases
Case 1: the column vectors {ai1 , . . . , aip } of A are linearly independent. This case we can
proceed exactly the same as in Part i) and obtain a basic feasible optimal solution. Note
that the optimality does not change in this case.
Case 2: the column vectors {ai1 , . . . , aip } of A are linearly dependent. We also proceed
similarly as in the second case in Part i. However, we need to show that the optimality is
preserved during the process. To show that x − εy is optimal, we consider its objective
value
cT (x − εy) = cT x − εcT y

For sufficiently small |ε|, the vector x − εy is a feasible solution (for positive or negative
values of ε). It follows that we must have cT y = 0, since otherwise, we could find a small
ε of the proper sign such that cT (x − εy) < cT x, which would violate the optimality of x.
Thus x − εy is still optimal.

Example 5.7. Consider the LP problem in standard form with

 
3
     
−1 3 0 0 0 3  2 
 
     
A =  0 2 −1 −1 0  b= 2  x= 1 
     
     
0 0 0 −1 1
 
0  1 
 
1

Let us see how to construct a BFS from the feasible point x = (3, 2, 1, 1, 1)T . The given x
has no zero entries, so if we try to replicate the proof of the theorem 5.6, we have m = 3
and p = 5. Therefore we need to solve the system Ay = 0 and pick one solution, for
example y = (0, 0, 1, −1, −1)T .
n
Note that y has only one component y3 that is strictly positive, so ε = min xyii i =
o
1, . . . , p; yi > 0 = xy33 = 1 and x − y = (3, 2, 0, 2, 2)T . We take this as our new x̃ =
 62

(3, 2, 0, 2, 2)T this is still a feasible point. It has one coordinate equal to 0, so let us take
 
−1 3 0 0
 
à = [a1 , a2 , a4 , a5 ] =  0 2 −1 0  .
 
 
0 0 −1 1

Let us solve the system Ãy ′ = 0 and pick one solution, for example y ′ = (3, 1, 2, 2)T . We
n o n o
calculate ε = min x̃ỹii i = 1, . . . , 5; yi > 0 = min 33 , 21 , 22 , 22 = 1. Again we take x̃ − ỹ =
(0, 1, 0, 0, 0)T where ỹ = (3, 1, 0, 2, 2)T . This is a BFS. Infact, if we select the matrix B
made of the second, fourth and fifth columns of A, we can see that (1, 0, 0)T = B −1 b.

In the next section, we are going to study how to solve LPs by simplex method.

5.2 The simplex method

• The simplex method is to proceed from one BFS to an adjacent or neighboring one
in such a way as to improve the value of the objective function (moving from an
extreme point to another with a better at least not worse objective).

• It also discovers whether the feasible region is empty, and whether the optimal
solution is unbounded. In practice, the method only enumerates a small portion of
the extreme points of the feasible region.

• The key to the simplex method lies in recognizing the optimality of a given extreme
point solution based on local consideration without having to enumerate all extreme
points or basic feasible solutions.

• The basic idea of the simplex method is to confine the search to extreme points of
the feasible region in a most intelligent way. The key for the simplex method is to
make computers find extreme points.
 63

5.2.1 Reformulation of LP by the current BFS

For simplicity, throughout the remainder of this course we always assume that the
problem is in standard form

min cT x

s.t. Ax = b, x ≥ 0,

where A is an m × n matrix with full rank, i.e., rank(A) = m, and b a vector in Rm , and
c is a vector in Rn .

Initial basis and corresponding objective value

 
−1
B b
Suppose that we have a basic feasible solution  . The corresponding objective
0
value f0 is given by  
B −1 b
f0 = (cTB cTN )   = cTB B −1 b.
0

For this given basis B, we would like to check if it is an optimal solution of the problem.

If it is not, we would like to find another basic feasible solution at which the objective
value is smaller than the current objective value f0 .

Reformulation of the problem

Let x be a feasible solution of Ax = b, and let xB and xN be its basic and nonbasic
variables for this given basis. Thus, we have
 
xB
b = Ax = [B, N ]   = BxB + N xN .
xN

Multiplying by B −1 we have

xB = B −1 b − B −1 N xN .
 64

The corresponding objective value is given by

f = cT x

= cTB xB + cTN xN

= (cTB B −1 b − cTB B −1 N xN ) + cTN xN

= cTB B −1 b − cTB B −1 N − cTN xN

= f0 − (z T − cTN )xN ,

where the vector z is defined as

z T = cTB B −1 N.

In components, denote by aj the jth column vector of A, we observe that

B −1 N = [B −1 am+1 , . . . , B −1 an ] = [y m+1 , . . . , y n ]

where y j = B −1 aj for j = m + 1, . . . , n, so that

zj = cTB B −1 aj = cTB y j , j ∈ R.

where R is the set of indices such that aj is a column of N for j ∈ R.

Therefore, LP can be written as

X
Minimize f = f0 − (zj − cj )xj
j∈R
X
subject to (y j )xj + xB = b̄ (5.3)
j∈R
xj ≥ 0, j ∈ R, and xB ≥ 0.

For this problem, xB can be viewed as a slack variable, so the above LP can be further
rewritten as
X
Minimize f = f0 − (zj − cj )xj
j∈R
X
subject to (y j )xj ≤ b̄ (5.4)
j∈R
xj ≥ 0, j ∈ R.

Definition: The value −(zj −cj ) = cj −zj is referred to be as reduced cost coefficient.
 65

5.2.2 Checking the Optimality

Case 1: zj − cj ≤ 0 for all j ∈ R.

Proposition 5.8. From (5.4), we see that if (zj − cj ) ≤ 0 for all j ∈ R, then the current
basic feasible solution is optimal.

P
Proof. Since zj − cj ≤ 0 for all j ∈ R, from f = f0 − j∈R (zj − cj )xj we see that f ≥ f0
for any feasible solution. For the current (basic) feasible solution, we know that f = f0
since xj = 0 for all j ∈ R. So, the current feasible solution is optimal.

Case 2: zj − cj > 0 for some j ∈ R.

For such j, there are two possible cases:

• If zj − cj > 0 and the vector

y j = B −1 aj ≤ 0,

then LP has an unbounded solution (or simply, we say that the LP is unbounded)
since we can send xj to +∞ in (5.4).

• If zj − cj > 0 and the vector

y j = B −1 aj = (y1j , ..., ymj )T

has a positive component. In this case, the current objective value can be further
decreased (if the current BFS is non-degenerated).

Example 5.9. Let us consider the following problem in standard form

min x1 + 3x2

s.t. Ax = b, x ≥ 0,

where the constraint matrix A and the vector b are the same as in example 5.4:
   
1 1 1 0 6
A = [a1 , a2 , a3 , a4 ] =  , b =  .
0 1 0 1 3

Consider the basic feasible solution xT = (3, 3, 0, 0). For this solution B = [a1 , a2 ], N =
[a3 , a4 ], f0 = 12, cTB = (1, 3), cTN = (0, 0).
 66

Then     
1 −1 1 0 1 −1
[y 3 , y 4 ] := B −1 N =   = ,
0 1 0 1 0 1
and
z T := cTB B −1 N = (1, 2),

so that z3 − c3 = 1 and z4 − c4 = 2.

So we see that for j = 3, zj − cj > 0. Let us look at the corresponding y j , namely

    
1 −1 1 1
y 3 = B −1 a3 =    =  ,
0 1 0 0

we see that it has a positive component, so we know that the value f0 = 12 is not optimal.
Similarly, for j = 4, zj − cj > 0. Let us look at the corresponding y j , namely
    
1 −1 0 −1
y 4 = B −1 a4 =    =  ,
0 1 1 1

again we have a positive component, which tells us that there is scope for improvement.

We shall continue this example at the end of the next subsection, after explaining how
to construct a new BFS that improves the objective value.

5.2.3 Principles and justification of simplex method:

The simplex procedure moves from one BFS to an adjacent one, by introducing a non
zero component into the zero part of the BFS, and removing a non zero component from
it.

The criteria for “entering” and “leaving” are summarised below.

• Entering: If zk − ck > 0, xk may “enter” the basis.

• Leaving: If  
b̄r b̄i
≡ min : yik > 0
yrk 1≤i≤m yik
then xBr (the rth component of xB ) may be set to 0, namely it “leaves” the basis.

During the process, if

 67

1. zj − cj ≤ 0 for all nonbasic variables xN , terminate. We have an optimal solution

2. If for some k ∈ R, we have zk − ck > 0, and yk = B −1 ak ≤ 0, then LP is unbounded.

3. Otherwise, according to the above rule to choose entering variable, and leaving variable,
to form new basis, and get improved basic feasible solution.

Let us explain why this works. We start from a given BFS, (b̄, 0, . . . , 0). Choose one
of the positive number like zk − ck , and perhaps the most positive of all the zj − cj , j ∈ R.
Set
xj = 0, for j ∈ R − {k}.

We want to choose xk in such a way that xN = (0, . . . , 0, xk , 0, . . . , 0)T leads to a solution

of the LP (5.3).

The objective value changes as we can see from (5.3)

f = f0 − (zk − ck )xk (5.5)

and      
x b̄ y1k
 B1   1   
 xB2  b̄2   y2k
     
 
 ..  ..   ..
     
 
 .   .   . 
xB =   = b̄ − (y k )xk =  −  xk , (5.6)
     
 xBr   b̄r   yrk 
 ..  ..   ..
     
 
 .   .   . 
     
xBm b̄m ymk
where ylk , l = 1, . . . , m are the components of the vector y k .

Assume the current basic feasible solution is not degenerated, i.e. b̄ > 0. Now let us
analyse what will happen when we increase the value of xk .

(i) From (5.5), the objective value will decrease.

(ii) For those yik ≤ 0, when xk increases, (5.6) implies that the component xBi will
increase, continuing to be positive.
 68

(iii) For those yik > 0, increasing xk , the corresponding component xBi will decrease.
So we need to be increase xk but not too much. From (5.6), the first basic variable
dropping to zero corresponds to the minimum of b̄i /yik for positive yik . More precisely, we
can increase xk until it reaches the following value
 
b̄r b̄i
≡ min : yik > 0 . (5.7)
yrk 1≤i≤m yik
b̄r
Let us choose xk = yrk
. Under non-degeneracy, xk > 0. From (5.5) and fact that
zk − ck > 0, it follows that objective can be strictly improved, as xk increases from level
0 to br /yrk , a new improved feasible solution is obtained. Substituting xk given by (5.7)
into (5.6) yields the following:

 xBi = b̄i − yyik b̄r , i = 1, 2, ..., m,


 rk
b̄r (5.8)
xk = yrk ,


 all other (x )′ s are zero.

j

From (5.8), we have xBr = 0, and hence at most m variables are positive. We want to
prove that this is also a BFS.

Proposition 5.10. (5.8) is the a basic feasible solution corresponding the basis

e = [aB1 , aB2 , ..., aBr−1 , ak , aBr+1 , ..., aBm ],

B

which is formed by replacing rth column of B with ak .

Proof. First of all, the matrix B

e is invertible, or equivalently its columns are linearly

independent vectors. This is a consequence of the following lemma (see Linear Algebra):

Lemma 5.11. Let a1 , a2 , ..., an form a basis of Rn . Then any vector a can be represented
as
n
X
a= λ j aj .
j=1

Let’s replace aj by a, then the vectors a1 , ..., aj−1 , a, aj+1 , ..., an are linearly independent if
and only if, in the above representation, λj ̸= 0.

To apply this lemma to our situation, we notice that by the definition of yk , i.e.,
yk = B −1 ak , we have

ak = Byk = aB1 y1k + ... + aBr yrk + ... + aBm ymk

 69

with yrk ̸= 0. So if we replace the rth column of B by ak , the resulting vectors are still
linearly independent.

Let’s verify that

 
x
 B1 
 xB2
 

 ..
 

 . 
[aB1 , aB2 , ..., aBr−1 , ak , aBr+1 , ..., aBm ] 

=b

 xk 
 ..
 

 . 
 
xBm

where xB1 , xB2 , ..., xk , ..., xBm is given by (5.8). In fact, the left-hand-side
   
y1k B1 b̄r k ymk
b̄1 − b̄r a + ... + a + ... + b̄m − b̄r aBm
yrk yrk yrk
= b̄1 − y1k xk aB1 + ... + xk ak + ... + b̄m − ymk xk aBm

X m
b̄j aBj + −b̄r aBr − y1k xk aB1 − ... − y(r−1)k xk aBr−1 + xk ak − ... − ymk xk aBm


=
j=1
m m
!
X X
= b̄j aBj + xk − yjk aBj + ak
j=1 j=1

= B b̄ + xk (ak − B(y k ))

= b + 0 = b,

where the last equality follows from the fact y k = B −1 ak .

Chapter 6

The simplex method (II): Algorithm

In this chapter, we continue studying the simple method focusing on algorithmic

aspect. We will study how to implement the simplex method in practices. The following
topics will be covered

• description of the simplex algorithm,

• the simplex method in tableau format,

• further examples of the simplex methods,

• extracting information form optimal simplex tableau,

At the end of the chapter, students should be able to

• understand the main steps of the simplex algorithm,

• apply the algorithm to solve a LP problem using tableau format,

• extract useful information from the optimal simplex tableau.

[BT97, Chapter 3] and [DT97, Chapter 3] have similar material in this chapter that you
may find useful.

6.1 The algorithm for minimisation problems

Here we describe the algorithm for minimisation problems in standard form.

70
 71

Initial Step

Choose a starting basic feasible solution with basis B.

Main Step

Step 1. Solve the system BxB = b. Set

xB = B −1 b = b̄,

xN = 0,

f = cTB xB = cTB B −1 b = cTB b̄.

Step 2. Set z = cTB B −1 N. Calculate

zj − cj for all nonbasic variables, i.e. j ∈ R.

where R is the current set of indices associated with the nonbasic variables. Choose k
such that
zk − ck = max{zj − cj }.
j∈R

If zk − ck ≤ 0, then stop (the current basic feasible solution is an optimal solution).

Otherwise, go to Step 3.

Step 3. Calculate yk = B −1 ak . If yk ≤ 0, then stop (the optimal value of LP is un-

bounded). Otherwise, go to step 4.

Step 4. This step deals with removing a variable in the basis and adding one from the
non basis. Let xk enter the basis.

4.1. Determine the index r by the following minimum ratio test:

 
b̄r b̄i
≡ min : yik > 0
yrk 1≤i≤m yik
b̄r
where yik denotes the ith component of yk . Put xk := yrk
.
 72

4.2. Update the basis B where ak replaces aBr , update the index set R, and go to
step 1.

Remarks: At each iteration, one of the following three actions is executed.

• We may stop with an optimal solution if zk − ck ≤ 0;

• We may stop with an unbounded optimal value if zk − ck > 0 and yk ≤ 0;

• or else we generate a new basic feasible solution if zk − ck > 0 and yk ̸≤ 0, and the
objective function strictly decreases.

Therefore, in the absence of degeneracy (i.e. xB > 0), the objective strictly decreases at
each iteration, and hence the basic feasible solution generated by the simplex method are
distinct. Since there is only a finite number of basic feasible solutions, the method would
stop in a finite number of steps with either an optimal solution or an unbounded optimal
value.

Theorem 6.1 (Convergence). In the absence of degeneracy (and assuming feasibility),

the simplex method stops in a finite number of iterations, either with an optimal basic
feasible optimal solution or with the conclusion that the optimal value is unbounded.

6.2 The simplex method in Tableau Format

All the operations in simplex method can be performed in a Tableau. Let B be a

starting basis. The LP problem can be represented as follows:

minimise f

subject to f − cTB xB − cTN xN = 0 (6.1)

BxB + N xN = b (6.2)

xB , xN ≥ 0.

This LP has the following constraint matrix

 
1 −cTB −cTN
 .
0 B N
 73

We now reformulate this LP once again. Observe that (6.2) can be written as

xB + B −1 N xN = B −1 b.

Multiplying both sides by cTB yields

cTB xB + cTB B −1 N xN = cTB B −1 b.

Adding this equality to (6.1) leads to

f + 0xB + cTB B −1 N − cTN xN = cTB B −1 b.

So the LP is reformulated as

minimise f

subject to f + 0xB + cTB B −1 N − cTN xN = cTB B −1 b,

xB + B −1 N xN = B −1 b,

xB , xN ≥ 0.

Here we think of f as a variable to be minimised. We put all information of the above

problem in the following tableau:

xB xN RHS
f 0 cTB B −1 N − cTN cTB B −1 b
xB I B −1 N B −1 b

The tableau contains all information of the linear programming that we need to proceed
with the simplex method:

• The top element in the RHS column gives us the objective value,

• The bottom element in the RHS column gives basic variable value B −1 b,

• The top element in the xN column gives us the values zj − cj for nonbasic variables,
or in other words the minus reduced cost,

• The bottom element in the xN column gives B −1 N , namely the vectors yj , j ∈ R.

 74

We use the following language: the row labelled by f is called zeroth row. The rows
labelled by xBi are called i-th row.

To minimise f we need to go from one BFS to the next, therefore we need a scheme to
do the following:

(i) Update the basic variable and their values

(ii) Update the zj − cj values of the new nonbasic variables.

(iii) Update the yj columns.

In the next subsection, we show that all of the tasks can be simultaneously accomplished
by simple pivoting operations which are actually equivalent to a series of matrix elemen-
tary row operations on the matrix
 
1 cTB cTN 0
 .
0 B N b

6.2.1 Pivoting:

In general, an element of a matrix, or of an array, which is selected first by an algorithm

(e.g. Gaussian elimination, simplex algorithm, etc.), to do certain calculations is called
pivot. Finding this element is called pivoting. Pivoting may be followed by an interchange
of rows or columns to bring the pivot to a fixed position and allow the algorithm to proceed
successfully, and possibly to reduce round-off error.

If xk enters the basis and xBr leaves the basis, then pivoting on yrk includes the
following operations:

• Divide row r by yrk .

• For i = 1, ..., m and i ̸= r, update the ith row by adding to it −yik times the new
rth row.

• Update row zero by adding to it −(zk − ck ) times the new rth row.
 75

The following two tables show the situation before and after pivoting operations.

Table 6.1: Before pivoting

xB1 xBr xBm xj xk RHS

f 0 ··· 0 ··· 0 ··· zj − cj ··· zk − ck ··· cTB b̄
xB1 1 ··· 0 ··· 0 ··· y1j ··· y1k ··· b̄1
.. .. .. .. .. .. ..
. . . . . . .
xBr 0 ··· 1 ··· 0 ··· yrj ··· yrk ∗ ··· b̄r
.. .. .. .. .. .. ..
. . . . . . .
xBm 0 ··· 0 ··· 1 ··· ymj ··· ymk ··· b̄m

Table 6.2: After pivoting

xB1 xBr xBm xj xk RHS

zk −ck
(zj − cj )−
f 0 ··· yrk
··· 0 ··· ··· 0 ··· cTB b̄ − (zk − ck ) yb̄rkr
y (zk −ck )
− rj yrk
−y1k yrj y1k
xB 1 1 ··· yrk
··· 0 ··· y1j − yrk y1k ··· 0 ··· b̄1 − b̄
yrk r
.. .. .. .. .. .. ..
. . . . . . .
1 yrj b̄r
xk 0 ··· yrk
··· 0 ··· yrk
··· 1 ··· yrk
.. .. .. .. .. .. ..
. . . . . . .
−ymk yrj ymk
xBm 0 ··· yrk
··· 1 ··· ymj − y
yrk mk
··· 0 ··· b̄m − b̄
yrk r

Implication of the pivoting operation:

• xk entered and xBr left the basis. This is illustrated on the left-hand-side of the
tableau by replacing xBr with xk .

• The right-hand-side gives the current values of the basic variables. The nonbasic
variables are kept zero.

• Suppose that the original columns for the new basic and nonbasic variables are B̂
and N̂ , respectively. The pivoting operation which is a sequence of elementary row
 76

operations results in a new tableau that gives the new B̂ −1 N̂ under the nonbasic
variables, and updated set of zj − cj ’s for the new nonbasic variables, and the values
of the new basic variables and objective.

6.2.2 Algorithm in tableau Format

Initialization step:

Find an initial basic feasible solution with basis B. Form the following initial tableau.

xB xN RHS
f 0 cTB B −1 N − cTN cTB B −1 b
xB I B −1 N B −1 b

Main Step:

Step 1. Let zk − ck = max{zj − cj : j ∈ R}.

• If zk − ck ≤ 0, stop. The current point is optimal.

• Otherwise, xk will enter, and go to Step 2

Step 2. Examine yk .

• If yk ≤ 0, then stop (The LP is unbounded).

• Otherwise, go to Step 3

Step 3. Determine the index r by minimum ratio test to find the variable xBr to leave.

Step 4.

• Update the tableau by pivoting at yrk .

• Update the basic and nonbasic variables where xk enters the basis and xBr leaves
the basis, and repeat the main step.
 77

Example 6.2. Solve the following LP problem by the simplex method

Minimise x1 + x2 − 4x3

s.t. x1 + x2 + 2x3 ≤ 9,

x1 + x2 − x3 ≤ 2,

−x1 + x2 + x3 ≤ 4,

x1 , x2 , x3 ≥ 0.

Adding slack variables leads to

Minimise x1 + x2 − 4x3 + 0x4 + 0x5 + 0x6

subject to x1 + x2 + 2x3 + x4 = 9,

x1 + x2 − x 3 + x5 = 2,

−x1 + x2 + x3 + x6 = 4,

x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.

Since b = (9, 2, 4)T > 0, initial basis can be chosen as B = [a4 , a5 , a6 ] = I. so B −1 b = b̄ >
0. Thus, initial tableau is given by

Initial iteration

x1 x2 x3 x4 x5 x6 RHS
f −1 −1 4 0 0 0 0
x4 1 1 2 1 0 0 9
x5 1 1 −1 0 1 0 2
x6 −1 1 1∗ 0 0 1 4

• From this table, we see that x3 is a nonbasic variable, and z3 − c3 = 4 > 0. Thus,
the current basic feasible solution (x4 , x5 , x6 ) = (9, 2, 4) is not optimal. x3 will enter
the basis.

• Now we are going to determine which vector among x4 , x5 , x6 will leave the basis.
By checking y3 = (2, −1, 1)T , we note that it has two positive components. By the
minimum ratio test: min{ 29 , 41 } = 4. The vector x6 leaves the basis, and the marked
elements in the above table is the pivoting element.
 78

• We do pivoting operations to get a new basic feasible solution. Thus the algorithm
proceeds to the next iteration.

Iteration 1.

x1 x2 x3 x4 x5 x6 RHS
f 3 −5 0 0 0 −4 −16
x4 3∗ −1 0 1 0 −2 1
x5 0 2 0 0 1 1 6
x3 −1 1 1 0 0 1 4

• x1 is a nonbasic variable, and z1 − c1 = 3 > 0. Thus, the current basic feasible

solution (x4 , x5 , x3 ) = (1, 6, 4) is not optimal. x1 will enter the basis.

• Now we determine which vector among x4 , x5 , x3 will leave the basis. By checking
y1 = (3, 0, −1)T and the minimum ratio test indicates that x4 should leave the basis.

• We do pivoting operations, and get the following tableau:

Iteration 2.

x1 x2 x3 x4 x5 x6 RHS
f 0 −4 0 −1 0 −2 −17
x1 1 −1/3 0 1/3 0 −2/3 1/3
x5 0 2 0 0 1 1 6
x3 0 2/3 1 1/3 0 1/3 13/3

Now, zj − cj ≤ 0 for all nonbasic variables, and thus an optimal solution is found and it
is given by
x∗1 = 1/3, x∗2 = 0, x∗3 = 13/3.

The optimal value is

z ∗ = −17.

The optimal basis B consists of the column a1 , a5 and a3 , i.e., B = [a1 , a5 , a3 ].

 79

6.3 Degeneracy and cycling in the simplex method

When applying the simplex method to solve a linear programming problem, it is

possible that one starts from some basic feasible solution and ends up at the exact same
basic feasible solution after a sequence of pivots. This phenomena is called “cycling” and
can occur when a basic feasible solution is degenerate. In the worst scenario, the simplex
method can cycle forever. The first cycling example was given by Hoffman in 1952 which
had 11 variables and 3 equations. Since then, many examples have been constructed. To
demonstrate the cycling phenomena, we consider the following famous example which was
given by E. M. L. Beale in 1955 [Bea55]. It is conjectured that this is the simplest example
of cycling which is not totally degenerate in the sense that none can be constructed with
fewer variables regardless of the number of equations.

Example 6.3 (Beale 1955). Solve the following LP by using simplex method:

3 1
Minimise − x4 + 20x5 − x6 + 6x7
4 2
1
subject to x1 + x4 − 8x5 − x6 + 9x7 = 0,
4
1 1
x2 + x4 − 12x5 − x6 + 3x7 = 0,
2 2
x3 + x6 = 1,

x1 , . . . , x7 ≥ 0.

In each iteration below, the pivoting entry is marked by an asterisk.

Initial tableau

x1 x2 x3 x4 x5 x6 x7 RHS
f 0 0 0 3/4 -20 1/2 -6 0
x1 1 0 0 1/4∗ -8 -1 9 0
x2 0 1 0 1/2 -12 -1/2 3 0
x3 0 0 1 0 0 1 0 1

Iteration 1. The maximum value of the minus reduced cost is 3/4, so k = 4. The
minimum ratio test is satisfied for r = 1, 2, for example choose r = 1. So we pivot with
respect to y14
 80

x1 x2 x3 x4 x5 x6 x7 RHS
f -3 0 0 0 4 7/2 -33 0
x4 4 0 0 1 -32 -4 36 0
x2 -2 1 0 0 4∗ 3/2 -15 0
x3 0 0 1 0 0 1 0 1

Iteration 2. The maximum value of the minus reduced cost is 4, so k = 5. The minimum
ratio test is satisfied for r = 2, so we pivot with respect to y25

x1 x2 x3 x4 x5 x6 x7 RHS
f -1 -1 0 0 0 2 -18 0
x4 -12 8 0 1 0 8∗ -84 0
x5 -1/2 1/4 0 0 1 3/8 -15/4 0
x3 0 0 1 0 0 1 0 1

Iteration 3. Here we could pivot both at y46 and y56 , we choose y46 :

x1 x2 x3 x4 x5 x6 x7 RHS
f 2 -3 0 -1/4 0 0 3 0
x6 -3/2 1 0 1/8 0 1 -21/2 0
x5 1/16 -1/8 0 -3/64 1 0 3/16∗ 0
x3 3/2 -1 1 -1/8 0 0 21/2 1

Iteration 4.

x1 x2 x3 x4 x5 x6 x7 RHS
f 1 -1 0 1/2 -16 0 0 0
x6 2∗ -6 0 -5/2 56 1 0 0
x7 1/3 -2/3 0 -1/4 16/3 0 1 0
x3 -2 6 1 5/2 -56 0 0 1

Iteration 5.
 81

x1 x2 x3 x4 x5 x6 x7 RHS
f 0 2 0 7/4 -44 -1/2 0 0
x1 1 -3 0 -5/4 28 1/2 0 0
x7 0 1/3∗ 0 1/6 -4 -1/6 1 0
x3 0 0 1 0 0 1 0 1

Iteration 6.

x1 x2 x3 x4 x5 x6 x7 RHS
f 0 0 0 3/4 -20 1/2 -6 0
x1 1 0 0 1/4 -8 -1 9 0
x2 0 1 0 1/2 -12 -1/2 3 0
x3 0 0 1 0 0 1 0 1
This tableau is exactly as the initial tableau. Therefore, the simplex method will cycle
endlessly. We observe that the basic feasible solution in each iteration is degenerate (but
not totally degenerate) and the objective function actually does not change.

It is this degeneracy that causes cycling. We see that throughout the process we were
faced several times by a non-unique choice of pivoting. There are several ways to avoid
cycling. The most commonly used method is to fix a rule to make choices when faced with
more that 1 possible pivoting candidate. The most common rule is Bland’s rule which is
formally stated as follows:

1. Choose the lowest-numbered (i.e., leftmost) nonbasic column with a negative re-
duced cost - in the tableau this means “choose the leftmost column with a positive
entry yil .

2. If there are more that one row that satisfy the minimum ratio test, choose the row
with the lowest-numbered column basic variable in it.

This means that in the previous example we should pivot w.r.t. y24 in the first
iteration.

Example 6.4. If Bland’s rule does not work, we can modify the rule and start again. For
example we can change the rule by saying that instead of the lowest-numbered nonbasic
column with a negative reduced cost we should choose the highest, or that instead of the
highest numbered column basic variable, we should choose the lowest.
 82

6.4 Efficiency of the simplex method

An interesting property of the simplex method is that is remarkably efficient in prac-

tice. However, in 1972, Klee and Minty [KM72] provided an example, which is now known
as the Klee–Minty cube, showing that the worst-case complexity of simplex method as
formulated by Dantzig is exponential time. Since then the Klee–Minty cube has been used
to analyze the performance of many algorithms both in the worst case and on average.
The Klee-Minty example is given by

Example 6.5 (Klee-Minty cube).

Maximise 2n−1 x1 + 2n−2 x2 + . . . + 2xn−1 + xn

subject to x1 ≤ 5,

4x1 + x2 ≤ 25,

8x1 + 4x2 + x3 ≤ 125,

..
.

2n x1 + 2n−1 x2 + . . . + 4xn−1 + xn ≤ 5n ,

x1 , . . . , xn ≥ 0.

The LP has n variables, n constraints and 2n extreme points. The simplex method,
starting from the origin, will go through each of the extreme points before obtaining the
optimal solution at (0, 0, . . . , 5n ). To illustrate this, we consider the Klee-Minty cube for
the case n = 3, that is

Maximise 4x1 + 2x2 + x3

subject to x1 ≤ 5,

4x1 + x2 ≤ 25,

8x1 + 4x2 + x3 ≤ 125,

x1 , x2 , x3 ≥ 0.

It is easy to see that 4x1 + 2x2 + x3 ≤ 8x1 + 4x2 + x3 = 125 and the inequality becomes
equality when x1 = x2 = 0, x3 = 125. Thus the optimal value is 125 and is achieved
at (x1 , x2 , x3 ) = (0, 0, 125). Adding s1 , s2 , s3 as slack variables to obtain the following
 83

problem

Maximise 4x1 + 2x2 + x3

subject to x1 + s1 = 5,

4x1 + x2 + s2 = 25,

8x1 + 4x2 + x3 + s3 = 125,

x1 , x2 , x3 , s1 , s2 , s3 ≥ 0.

Below are all the tableaux

x1 x2 x3 s1 s2 s3 RHS x1 x2 x3 s1 s2 s3 RHS
−f 4 2 1 0 0 0 0 −f 0 2 1 -4 0 0 -20
s1 1 0 0 1 0 0 0 x1 1 0 0 1 0 0 5
s2 4 1 0 0 0 0 0 s2 0 1 0 -4 1 0 5
s3 8 4 1 0 0 1 0 s3 0 4 1 -8 0 1 85

x1 x2 x3 s1 s2 s3 RHS x1 x2 x3 s1 s2 s3 RHS
−f 0 0 1 4 -2 0 -30 −f -4 0 1 0 -2 0 -50
x1 1 0 0 1 0 0 5 s1 0 0 0 1 0 0 5
x2 0 1 0 -4 1 0 5 x2 4 1 0 0 1 0 25
s3 0 0 1 8 -4 1 65 s3 -8 0 1 0 -4 1 25

x1 x2 x3 s1 s2 s3 RHS x1 x2 x3 s1 s2 s3 RHS
−f 4 0 0 0 2 -1 -75 −f 0 0 0 -4 2 -1 -95
s1 1 0 0 1 0 0 5 x1 1 0 0 1 0 0 5
x2 4 1 0 0 1 0 25 x2 0 1 0 -4 1 0 5
x3 -8 0 1 0 -4 1 25 x3 0 0 1 8 -4 1 65

x1 x2 x3 s1 s2 s3 RHS x1 x2 x3 s1 s2 s3 RHS
−f 0 -2 0 4 0 -1 -105 −f -4 -2 0 0 0 -1 -125
x1 1 0 0 1 0 0 5 s1 1 0 0 1 0 0 5
s2 0 1 0 -4 1 0 5 s2 4 1 0 0 1 0 25
x3 0 4 1 -8 0 1 85 x3 8 4 1 0 0 1 125

Thus the simplex method applied to the Klee-Minty cube for n = 3, starting at the origin,
goes through all of the 8 vertices before reaching the optimal value.
 84

Remark 2. There are other algorithms for solving linear-programming problems. In par-
ticular, interior-point methods refer to class of methods for solving linear programming
problems that move through the interior of the feasible region such as Khachiyan’s ellip-
soidal algorithm and Karmarkar’s algorithm. This is in contrast to the simplex algorithm,
which finds an optimal solution by traversing the edges between vertices of the feasible re-
gion. Interior-point methods often have worst-case polynomial complexity; however, in
most practical applications, the simplex method is often very efficient.

Remark 3 (Open problems in Linear Programming). In 1998 the mathematician Stephen

Smale (Fields Medal in 1966) compiled a list of 18 problems in mathematics to be solved
in the 21st century, known as Smale’s problems. This list was compiled in the spirit of
Hilbert’s famous list of problems produced in 1900 for the 20th century. The 9-th problem
in the list is the following

The linear programming problem: Find a strongly-polynomial time algorithm which for
given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b.

6.5 Further Examples for Simplex Methods & De-

generacy

Example 6.6. Solve the following LP by using simplex method:

Minimise −3x1 + x2

s.t. x1 + 2x2 ≤ 4,

−x1 + x2 ≤ 1,

x1 , x2 , x3 , x4 ≥ 0.

Example 6.7. Solve the following LP by using simplex method:

Minimise −x1 − 3x2

s.t. x1 − 2x2 ≤ 4,

−x1 + x2 ≤ 3,

x1 , x2 ≥ 0.
 85

The following tables and figure summarise the result.

x1 x2 x3 x4 RHS
f 1 3 0 0 0
x3 1 −2 1 0 4
x4 −1 1∗ 0 1 3

x1 x2 x3 x4 RHS
f 4 0 0 −3 −9
x3 −1 0 1 2 10
x2 −1 1 0 1 3

Since z1 − c1 = 4 > 0, x1 should enter the basis, however, the corresponding y1 =

(−1, −1)T ≤ 0. Thus, the LP problem has unbounded optimal value.

Example 6.8. Solve the following LP by using simplex method

Maximise −3x1 + x2

s.t. x1 − 3x2 ≥ −3,

2x1 + x2 ≥ −2,

2x1 + x2 ≤ 8,

x1 and x2 are unrestricted.

Degeneracy cases

When the right-hand-side vector b̄ is not positive (at least one of its components is zero),
we can still use the simplex method to solve the problem. The following is such an exam-
ple.

Example 6.9 (Investment problem). Someone has $ 20,000 to finance various invest-
ments. There are five categories of investments, each with an associated return and risk:
 86

Investment Return Risk

Mortgages 8 2
Commercial loans 10 6
Government securities 0 6
Personal loans 12 8
Savings 3 0

Their goal is to allocate the money to the categories so as to maximise the return, subject
to the following constraints:

(a) An average risk is no more than 6 (all averages taken over the invested money, not
over the savings).

(b) The amount in mortgages and personal loans combined should be no higher than the
amount in commercial.

Model the problem:

Since there is no return from government securities, we do not consider such an invest-
ment. Denote

• x1 — the amount invested in mortgages,

• x2 — the amount allocated to commercial loans,

• x3 and x4 are the amounts invested in personal loans and savings, respectively.

Note that the constraint (a) implies that

2x1 + 6x2 + 8x3

≤ 6,
x1 + x2 + x3

which can be written as

−4x1 + 2x3 ≤ 0.

We may formulate the problem as follows:

 87

x1 x2 x3 x4 x5 x6 RHS
f 5 7 9 0 0 0 −60, 000
x5 1 −1 1∗ 0 1 0 0
x6 −4 0 2 0 0 1 0
x4 1 1 1 1 0 0 20,000

Replacing x5 by x3 , the next table will be

x1 x2 x3 x4 x5 x6 RHS
f −4 16 0 0 −9 0 −60, 000
x3 1 −1 1 0 1 0 0
x6 −6 2∗ 0 0 −2 1 0
x4 0 2 0 1 −1 0 20,000

Replacing x6 by x2 , we have

x1 x2 x3 x4 x5 x6 RHS
f 44 0 0 0 7 −8 −60, 000
x3 −2 0 1 0 0 1/2 0
x2 −3 1 0 0 −1 1/2 0
x4 6∗ 0 0 1 1 −1 20,000

Replacing x4 by x1 , we have

x1 x2 x3 x4 x5 x6 RHS
f 0 0 0 −22/3 −1/3 −2/3 −620, 000/3
x3 0 0 1 1/3 1/3 1/6 20,000/3
x2 0 1 0 1/2 −1/2 0 10,000
x1 1 0 0 1/6 1/6 −1/6 10,000/3

The optimal solution is given by

 
10, 000 20, 000
(x∗1 , x∗2 , x∗3 , x∗4 ) = , 10, 000, ,0 .
3 3
Thus, he will allocate $ 10,000/3 to mortgages, $10,000 to commercial loans, $20,000/3
to personal loans, and no allocation to savings. Note that the optimal value of problem
 88

(P1 ) is −620, 000/3, and thus the maximum return for the original problem (P2 ) is

620, 000
f∗ = .
3

6.6 Extracting Information from the Optimal Sim-

plex Tableau

Suppose that we get the final tableau (optimal tableau) of simplex method. What in-
formation can be obtained from this final tableau? and how this information can be
used?

Example 6.10. The optimal tableau is given as follows:

x1 x2 x3 x4 x5 x6 RHS
f 0 0 0 −22/3 −1/3 −2/3 −620, 000/3
x3 0 0 1 1/3 1/3 1/6 20,000/3
x2 0 1 0 1/2 −1/2 0 10,000
x1 1 0 0 1/6 1/6 −1/6 10,000/3

The optimal solution is given by

   
x∗1 10, 000/3
   
x∗2   10, 000
   
 
   
x∗3
   
   20, 000/3 
 = .
x∗4
   
   0 
   
x∗5
   
   0 
   
x∗6 0

The optimal value of objective function is

f ∗ = −620, 000/3.
 89

6.6.1 Find the inverse of optimal basis

At each iteration, the current B −1 can be obtained immediately from the current tableau,
and the inverse of the optimal basis can be found in optimal tableau.

Assume that the original tableau has an identity matrix. The process of reducing the
basis matrix B of the original tableau to an identity matrix in the current tableau, is
equivalent to premultiplying rows 1 through m of the original tableau by B −1 to produce
the current tableau. This also converts the identity matrix of the original tableau to B −1 .
Therefore, B −1 can be extracted from the current tableau as the submatrix in rows 1
through m under the original identity columns.

Example 6.11. Consider the problem

Minimise −8x1 − 10x2 − 12x3 − 3x4

subject to x1 − x2 + x3 ≤ 0,

−4x1 + 2x3 ≤ 0,

x1 + x2 + x3 + x4 = 20, 000,

x1 , x2 , x3 , x4 ≥ 0.

Introducing the slack variables x5 , x6 leads to

minimise −8x1 − 10x2 − 12x3 − 3x4

subject to x1 − x2 + x3 + x5 = 0,

−4x1 + 2x3 + x6 = 0,

x1 + x2 + x3 + x4 = 20, 000,

x1 , x2 , x3 , x4 , x5 , x6 ≥ 0.

Initial table is given as

x1 x2 x3 x4 x5 x6 RHS
f 8 10 12 3 0 0 0
x5 1 −1 1 0 1 0 0
x6 −4 0 2 0 0 1 0
x4 1 1 1 1 0 0 20,000
 90

Final tableau (optimal tableau) is given by

x1 x2 x3 x4 x5 x6 RHS
f 0 0 0 −22/3 −1/3 −2/3 −620, 000/3
x3 0 0 1 1/3 1/3 1/6 20,000/3
x2 0 1 0 1/2 −1/2 0 10,000
x1 1 0 0 1/6 1/6 −1/6 10,000/3

What is B and B −1 ?

   
1 −1 1 1/3 1/6 1/3
   
3 2 1
B = [a , a , a ] =  2 0 −4  , B −1 =  −1/2 1/2  .
   
0
   
1 1 1 1/6 −1/6 1/6

Example 6.12. The following simplex tableau shows the optimal solution of a linear
programming. It is known that x4 and x5 are the slack variables in the first and second
constraints of the original problem. The constraints of the original problem are of the ‘≤’
type.

x1 x2 x3 x4 x5 RHS
f 0 −2 0 −3 −2 −35
x3 0 1/4 1 1/2 0 5/2
x1 1 −1/2 0 −1/6 1/3 5/2

The initial identity basis corresponds to x4 and x5 . So in the optimal tableau, the
inverse of the optimal basis B is given by
 
1/2 0
B −1 =  .
−1/6 1/3

6.6.2 Recovering original LP problems from the optimal tableau

In many situations, from the optimal tableau, we may recover the original LP problem.

Example 6.13. (Same example as Example 6.12) The following simplex tableau shows
the optimal solution of a linear programming. It is knows that x4 and x5 are the slack
 91

variables in the first and second constraints of the original problem. The constraints are
of the ‘≤’ type

x1 x2 x3 x4 x5 RHS
f 0 −2 0 −3 −2 −35
x3 0 1/4 1 1/2 0 5/2
x1 1 −1/2 0 −1/6 1/3 5/2

1. Determine optimal basis B.

The basic variables are x3 and x1 , thus, B = [a3 , a1 ] and

   
1/2 0 2 0
B −1 =  ⇒B= 
−1/6 1/3 1 3
Therefore, the third and first columns of A are obtained.

2. Determine the second column of A, i.e., a2 .

Since B −1 a2 = y2 in the simplex tableau, where B −1 and y2 are known, i.e,

   
1/2 0 1/4
  a2 =  .
−1/6 1/3 −1/2
Solving this system yields  
1/2
a2 =  
−5/4
Therefore, A is recovered.

3. Find the RHS vector b.

Notice that b̄ = (5/2, 5/2) and

B −1 b = b̄

Thus solving the system

    
1/2 0 b1 5/2
  = 
−1/6 1/3 b2 5/2
leads to  
5
b= 
10

4. Determine the cost coefficient c of the objective - this will be done by using the dual
simplex method.
Chapter 7

The Dual Simplex Method

(non-examinable)

In this chapter, we study another extension/variant of the simplex method, the dual
simplex method. This method is useful and necessary in, for instances, the following
situations.

• In certain instances, it is difficult to find a starting basic feasible solution (i.e. b̄ ≥ 0)

to a linear program without adding artificial variables.

• However, in these same instances, it is often possible to find a starting basis, which
is not necessary to be primal feasible, but which is dual feasible (i.e., all zj − cj ≤ 0
for minimization problem).

• The dual simplex method is a variant of the simplex method that would produce a
series of simplex tableau that maintain dual feasibility and complementary slackness
and strive toward primal feasibility.

• The dual simplex method solves the dual problem directly on the (primal) simplex
tableau. At each iteration we move from a basic feasible solution of the dual problem
to an improved basic feasible solution until optimality of the dual (and also the
primal) is reached, or else until we conclude that the dual is unbounded and that
the primal is infeasible.

92
 93

7.1 Dual information from the (primal) optimal sim-

plex tableau

Consider the following LP in canonical form:

Minimise cT x

subject to Ax ≥ b

x ≥ 0.

As seen in Proposition 4.4, the dual problem is the following

Maximise bT w

subject to AT w ≤ c

w ≥ 0.

As usual we assume that A is a m × n matrix of maximal rank m and we introduce m

slack variables xn+1 , ..., xn+m in the primal problem to transform it to the standard form.

Assume we run the simplex method for a few iterations and reach an optimal tableau:

x1 x2 ··· xn xn+1 ··· xn+m RHS

f z1 − c1 z2 − c2 ··· zn − cn zn+1 − cn+1 ··· zn+m − cn+m cB b
xB 1 y11 y12 ··· y1n y1,n+1 ··· y1,n+m b̄1
xB 2 y21 y22 ··· y2n y2,n+1 ··· y2,n+m b̄2
.. .. .. .. .. .. .. .. ..
. . . . . . . . .
xBm ym1 ym2 ··· ymn ym,n+1 ··· ym,n+m b̄m

where we assume that for the indices i such that xi is one of the base variables, say xBl ,
we take the column entries yji to be all 0 except yBl i that is equal to 1. Similarly for those
columns, the values of zi − ci are set to be 0. Because the solution is optimal, the slack
variables can be chosen to be 0 (they don’t contribute to the final cost), so for simplicity
assume that the optimal BFS contains the slack variables within the non basic part.

From this optimal tableau, we may also get the optimal solution to the dual problem:

Theorem 7.1. At optimality of the primal minimisation problem in the canonical form,

w̄T := cTB B −1
 94

is an optimal solution to the dual problem and has the following components

wi = cn+i − zn+i , i = 1, . . . , m.

Proof. The tableau for the primal is optimal if and only if

zj − cj ≤ 0, ∀j ∈ R,

where R is the set of indices corresponding to the non-basic variables. Since, by definition
of z and w̄
zj − cj = cTB B −1 aj − cj = w̄T aj − cj = [AT w̄]j − cj ,

we have that AT w̄ ≤ c if and only if the tableau is optimal. Moreover, because for the
slack variables the columns ai+n are given by the canonical vectors, namely ai+n = −ei ,
we have
zn+i − cn+i = w̄T an+i − cn+i = −w̄T ei − 0 = −wi ,

so that zn+i − cn+i ≤ 0 if and only if w̄ ≥ 0.

So indeed w̄ is feasible for the dual problem if and only if the tableau is optimal.
Moreover, w̄ is optimal for the dual problem because

cT x̄ = cTB x̄B = cTB B −1 b = w̄T b = bT w̄.

Remark 4. Note that in the previous theorem 7.1, we have assumed that the primal is
in canonical form, namely, the constraints are in the form Ax ≥ b. If the constraints are
the other way around, namely Ax ≤ b, then the components of wT := cTB B −1 are given by
wi = zn+i − cn+i .

Therefore, when the optimal solution is attained, from the final tableau of the simplex
method, we may get both the primal and dual optimal solutions.

7.2 Recovering missing data in simplex tableau

Example 7.2. (Same example as Example 6.13. By using Remark 4, we extract the
optimal solution of the dual problem by looking at the 0-row components corresponding to
x4 and x5 :
w∗ = (−3, −2)T .
 95

Now, since, thanks to the same theorem, (−3, −2) = cTB B −1 , we calculate
 
2 0
cTB = (−3, −2)   = (−8, −6).
1 3

To compute cN , we use the fact that in the non basic part of the 0-th row, we have the
values of cTB B −1 N − cTN . In this example, the only component of cN that we need to find
is the second, as the cost of the slack variables is 0. So we have
 
1/2
−2 = cTB B −1 a2 − c2 = (−3, −2)   − c2
−5/4

from which we obtain c2 = 3.

The data in the simplex tableaux might be lost or corrupted, in which case we need
to recover these data.

Example 7.3. The following is the optimal tableau of simplex method for a given min-
imisation problem. The objective is to minimise −2x1 + 3x2 , and the slack variables are
x3 and x4 corresponding to the first and second inequalities, respectively. The constraints
are of the ‘≤’ type.

x1 x2 x3 x4 RHS
f b −1 f g -6
x3 c 0 1 1/5 4
x1 d e 0 2 a

Find the values of a, b, c, d, e, f, g in the above tableau.

7.3 Complementary slack condition

Introducing slack variables in both primal and dual we can state the dual problems
as:

Primal Dual
Minimise cT x Maximise bT w
subject to Ax + t = b subject to AT w + s = c
x ≥ 0 w ≥ 0.
 96

Thanks to the complementary slackness condition, we have that if (x̄T , t̄T ) and (w̄T , s̄T )
are optimal, then
x̄T s̄ = w̄T t̄ = 0.

This means that

1. Slack variables of the primal problem correspond to the dual variables

2. The variables of the primal problem correspond to the dual slack variables.

7.4 Uniqueness of optimal solutions to a linear pro-

gramming problem

It has been proved [Gre94] that a primal-dual pair of optimal solutions is unique if
and only if it is a strictly complementary pair of basic solutions (see Theorem 4.22 for
the definition of a strictly complementary solution). However, in general, it may happen
that both the primal and the dual linear programming problems have multiple optimal
solutions. For example, consider the following LP problem

Minimise x1 + x2 + 2x3

subject to x1 + x3 = 1,

x2 + x3 = 1,

x3 ≤ 0,

x1 , x2 ≥ 0.

This problem has multiple solution, for instance (1, 1, 0) and (0, 1, 1). In fact, any feasible
point is optimal. The dual problem is

Maximise y1 + y2

subject to y1 ≤ 1,

y2 ≥ 1,

y1 + y2 ≤ 2.

The dual also has multiple solutions, for example (1, 1) and (0, 2).
 97

7.5 The Dual Simplex Method

Consider the linear program:

min{cx : Ax = b, x ≥ 0},

and suppose that we have a dual feasible point, i.e., the initial table of simplex method
is given as follows:

x1 x2 ··· xn RHS
f z1 − c1 z2 − c2 ··· zn − cn cTB b
xB 1 y11 y12 ··· y1n b̄1
xB 2 y21 y22 ··· y2n b̄2
.. .. .. .. .. ..
. . . . . .
xBm ym1 ym2 ··· ymn b̄m

Where
zj − cj ≤ 0, i = 1, ...., n.

We have several cases:

Case 1. If b̄ ≥ 0, then the current point is already optimal to the linear program.

Case 2. If b̄r < 0 for some r, and the rth row vector is nonnegative, i.e., yrj ≥ 0, for
all j = 1, ..., n, then the dual is unbounded (and hence the primal problem is infeasible).
To see why this is true, we need to go back to section 5.2.1. There we saw that the primal
problem in standard form can be reformulated as in (5.4) :
X
Minimise f = f0 − (zj − cj )xj
j∈R
X
j
subject to (y )xj ≤ b̄ (7.1)
j∈R
xj ≥ 0, j ∈ R,

where R is the set of indices belonging to the non basis. The constraints can be written
in matrix form as
X
(y j )xj = B −1 N xN ≤ b̄,
j∈R
 98

so that we can write the dual problem as follows

Maximise b̄T wN

subject to N T B −T wN ≥ c − z (7.2)

w ≥ 0,

where we denote by wN the dual variable to xN . Note that the entries of the matrix
N T B −T are all strictly positive, so wN is unbounded.

Case 3. If b̄r < 0 for some r, and there exists at least one element yrj < 0 in the rth
row. In this case, let xBr leave, and use the following minimum ratio test to determine
the variable to enter:

 
zk − ck zj − cj
= min : yrj < 0 .
yrk yrj

After pivoting at yrk , it is easy to see that

yrj
(zj − cj )′ = (zj − cj ) − (zk − ck ) ≤ 0,
yrk
and hence the dual feasibility is kept. Furthermore, we may show that the dual objective
is improved, in fact, the new objective value is

cTB B −1 b − (zk − ck )b̄r /yrk ≥ cTB B −1 b,

which follows from the fact

zk − ck ≤ 0, b̄r < 0, yrk < 0.

Thus, after a pivoting, the dual simplex method moves from one dual basic feasible point
to another one with improved function value. Under non-degeneracy assumption, the al-
gorithm terminates after finite iterations and finds the primal and dual optimal solutions.

Summary of the dual simplex method (minimisation problem)

Initialization Step: Find a basis B of the primal such that zj − cj ≤ 0 for all j.
 99

Main Step:

Step 1. If b̄ = B −1 b ≥ 0, stop, the current solution is optimal. Otherwise, select the

pivot row r with b̄r < 0, say, b̄r = min{b̄i }.

Step 2. If yrj ≥ 0 for all j, stop, the dual is unbounded (and hence the primal is
infeasible). Otherwise, select the pivot column k by the following minimum ratio test:
 
zk − ck zj − cj
= min : yrj < 0 .
yrk yrj

Step 3. Pivot at yrk and return to Step 1.

Example 7.4. Solve the following LP problem:

Minimise 2x1 + 3x2 + 4x3

s.t. x1 + 2x2 + x3 ≥ 3,

2x1 − x2 + 3x3 ≥ 4,

x1 , x2 , x3 ≥ 0.

Multiplying both sides of the inequalities by −1 and adding slack variables x4 and x5 , we
may form the first table as follows:

x1 x2 x3 x4 x5 RHS
f −2 −3 −4 0 0 0
x4 −1 −2 −1 1 0 −3
x5 −2∗ 1 −3 0 1 −4

Since b2 = −4 < 0, x5 leaves the basis. Which one to enter the basis? By minimum
ratio test,
z1 − c1 z3 − c3 −2 −4
min{ , } = min{ , } = min{1, 4/3} = 1
y21 y23 −2 −3
which indicates that x1 enters the basis. So after pivoting operations, we get the next
tableau.
 100

x1 x2 x3 x4 x5 RHS
f 0 −4 −1 0 −1 4
x4 0 −(5/2)∗ 1/2 1 −1/2 −1
x1 1 −1/2 3/2 0 −1/2 2

Since b̄1 = −1 < 0, x4 must leave the basis. By the minimum ratio test, x2 enters the
basis. After pivoting, we get the optimal tableau

x1 x2 x3 x4 x5 RHS
f 0 0 −9/5 −8/5 −1/5 28/5
x2 0 1 −1/5 −2/5 1/5 2/5
x1 1 0 7/5 −1/5 −2/5 11/5

Thus the optimal solution is

x∗ = (11/5, 2/5, 0),

and optimal value

f ∗ = 28/5.
Chapter 8

Sensitivity Analysis
(non-examinable)

What is sensitivity and why do we have to care about it?

• In most practical applications, some of the problem data are uncertain or cannot be
known exactly. In this situation, the problem data are estimated. It is important to
be able to find the new optimal solution of the problem as other estimates of some
of the data become available, without the expensive task of resolving the problem
from scratch.

• Also at early stages of problem formulation some factors may be overlooked. It is

important to update the current solution in a way that takes care of these factors.

• Furthermore, in many situations the constraints are not very rigid. For example,
a constraint may reflect the availability of some resources. This availability can
be increased by extra purchase, and the like. It is desirable to examine the effect
of relaxing some of the constraints on the value of the optimal objective without
having to resolve the problem.

These and other related topics constitute sensitivity analysis.

[BT97, Chapter 5] and [DT97, Chapter 7] have similar material in this chapter that you
may find useful.

101
 102

We still consider the standard linear programming problem:

min{cx : Ax = b, x ≥ 0}.

Suppose that the simplex method produces an optimal basis B.

We shall describe how to make use of the optimality conditions in order to find a new
optimal solution, if some of the problem data change, without resolving the problem from
scratch. In particular, the following variations in the problem will be considered.

• Change in the cost vector c.

• Change in the right-hand-side vector b.

• Change in the constraint matrix A.

• Addition of a new activity.

• Addition of a new constraint.

8.1 Change in the cost vector

Changes of the cost vector c will change the cost row of the final tableau, that is, the
dual feasibility may be affected (lost). Suppose ck is changed to c′k . This includes two
cases:

[Case I]: xk is a nonbasic variable.

[Case II]: xk is a basic variable.

Case I

In this case ck is changed to c′k and xk is nonbasic.

In this case, cB is not changed, and hence zj = cB B −1 aj is not changed.

• For j ̸= k, the reduced cost coefficient zj − cj is not changed, and it satisfies that
zj − cj ≤ 0.
 103

• For j = k, we have
zk − c′k = (zk − ck ) + (ck − c′k ).

Thus, if ck is increased, i.e., if c′k ≥ ck , then we still have zk − c′k ≤ 0, the current
solution remains to be optimal. More general, if c′k ≥ zk , the solution is no change.
Otherwise, zk − c′k > 0, in which case xk must be introduced into the basis and the
simplex method is continued as usual.

Example 8.1. Consider the problem

Minimise −2x1 + x2 − x3

s.t. x1 + x2 + x3 ≤ 6,

−x1 + 2x2 ≤ 4,

x1 , x2 , x3 ≥ 0.

The optimal tableau is given by

x1 x2 x3 x4 x5 RHS
f 0 −3 −1 −2 0 −12
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10

Suppose that c2 = 1 is changed to c′2 = −3. Since x2 is nonbasic, then

z2 − c′2 = (z2 − c2 ) + (c2 − c′2 ) = −3 + 4 = 1 > 0,

and all other zj − cj are unaffected. Hence x2 enters the basis to replace x5 in the basis.
So we get the following table

x1 x2 x3 x4 x5 RHS
f 0 1 −1 −2 0 −12
x1 1 1 1 1 0 6
x5 0 3∗ 1 1 1 10

Continue the simplex iteration, and find the new optimal solution as follows.
 104

x1 x2 x3 x4 x5 RHS
f 0 0 −4/3 −7/3 −1/3 −46/3
x1 1 0 2/3 2/3 −1/3 8/3
x2 0 1 1/3 1/3 1/3 10/3

So the solution of the changed LP is (x∗1 , x∗2 ) = (8/3, 10/3), and the optimal value is
−46/3.

Case II

In this case xk is basic, for example xk = xB1 . The change of c to c′ changes the value
of z to z ′ = c′B T B −1 N and hence

T
zj′ −cj = c′B B −1 aj −cj = cTB B −1 aj −cj +(0, . . . , 0, c′B1 −cB1 , 0, . . . , 0)y j = zj −cj +(c′B1 −cB1 )yB1 j .

This means that we can just update the 0-th row by replacing zj − cj with zj − cj + (c′B1 −
cB1 )yB1 j for j non basic, while all entries corresponding to the basic variables remain equal
to 0. The new objective function is also changed to

T
c′B B −1 b = cB T B −1 b + (c′B1 − cB1 )b̄B1 .

Example 8.2. In the LP case as in Exercise 8.1, imagine to change the cost c1 to c′1 = −4,
so that c′1 − c1 = −2. The the optimal tableau is updated to:

x1 x2 x3 x4 x5 RHS
f 0 −5 −3 −4 0 −24
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10

We see that this is no longer an optimal solution as we have a positive number in the 0-th
row. We need to run the simplex method to find an optimal solution.

8.2 Change in the right-hand-side

Suppose that the RHS vector b is changed to b′ . Then

• zj − cj = cTB B −1 aj − cj has no change,

 105

• and the solution B −1 b is changed to B −1 b′ . Thus, the primal feasibility might be

affected. If one of the components of B −1 b′ is negative, the simplex method can be
continued on the final tableau by using the dual simplex method.

Otherwise, if B −1 b′ is nonnegative, the current basis remains to be an optimal basis,

and the new optimal value would be cB B −1 b′ .

Example 8.3. Consider the problem

Minimise −2x1 + x2 − x3

s.t. x1 + x2 + x3 ≤ 6,

−x1 + 2x2 ≤ 4,

x1 , x2 , x3 ≥ 0.

The optimal tableau is given by

x1 x2 x3 x4 x5 RHS
f 0 −3 −1 −2 0 −12
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10

i) Suppose that the right-hand-side vector b = (6, 4)T is replaced by b′ = (5, 4)T . Check
if this change will affect the current optimal solution of the problem.

ii) What if the RHS vector is replaced by b′ = (−3, 4)T ?

Solutions: the initial identity basis corresponds to x4 and x5 . So in the optimal tableau,
the inverse of the optimal basis B is given by
 
1 0
B −1 =  .
1 1

Suppose that the RHS vector b = (6, 4)T is replaced by b′ = (5, 4)T . We compute
    
1 0 5 5
B −1 b′ =     =   > 0.
1 1 4 9
 106

Thus the current basis is still optimal. The optimal solution become
   
x1 5
xB =   = B −1 b′ =   .
x5 9

The optimal objective value is

 
 5
cB B −1 b′ = −2 0   = −10.
9

Now suppose that the RHS vector is changed to b′ = (−3, 4)T . We compute
    
1 0 −3 −3
B −1 b′ =    =  .
1 1 4 1

Since B −1 b′ has a negative entry, the current basis becomes infeasible. The dual simplex
method implies that the dual problem is unbounded. Hence the changed problem is infea-
sible. For this specific case, we can deduce that the changed problem is infeasible directly
since the first constraint is replaced by

x1 + x2 + x3 ≤ −3,

which is impossible for x1 , x2 , x3 ≥ 0.

8.3 Adding a new activity

Suppose that a new activity xn+1 with cost cn+1 and consumption column an+1 is con-
sidered for possible production. Without resolving the problem, we can easily determine
whether producing xn+1 is worthwhile. First calculate zn+1 − cn+1 .

• If zn+1 − cn+1 ≤ 0 (minimization problem), then x∗n+1 = 0 since it is nonbasic

variable, and current solution is optimal.

• If zn+1 − cn+1 > 0, then xn+1 is introduced into the basis and the simplex method
continues to find the new optimal solution.
 107

Example 8.4. Consider the problem

Minimise −2x1 + x2 − x3

s.t. x1 + x2 + x3 ≤ 6,

−x1 + 2x2 ≤ 4,

x1 , x2 , x3 ≥ 0.

The optimal tableau is given by

x1 x2 x3 x4 x5 RHS
f 0 −3 −1 −2 0 −12
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10

Let’s find new optimal solution if a new activity x6 ≥ 0 with c6 = 1 and a6 = (−1, 2)T is
introduced.

From the optimal tableau, we find that the the inverse of the optimal basis B is
 
1 0
B −1 =  .
1 1
We compute
  
  1 0 −1
z6 − c6 = cTB B −1 a6 − c6 = −2 0     − 1 = 1 > 0.
1 1 2
    
1 0 −1 −1
y6 = B −1 a6 =    =  .
1 1 2 1
We incorporate this information into the last optimal simplex tableau:

x1 x2 x3 x4 x5 x6 RHS
f 0 −3 −1 −2 0 1 −12
x1 1 1 1 1 0 -1 6
x5 0 3 1 1 1 1∗ 10

We continue using the simplex method: x6 enters the basis and x5 leaves. By pivoting
around the pivoting entry, which is marked with a star on the above tableau, we obtain
the following tableau
 108

x1 x2 x3 x4 x5 x6 RHS
f 0 −6 −2 −3 -1 0 −22
x1 1 4 2 2 1 0 16
x6 0 3 1 1 1 1 10

This is an optimal solution. Thus the optimal solution to the changed problem is (x∗1 , x∗2 , x∗3 , x∗6 ) =
(16, 0, 0, 10), the optimal value is −22.

8.4 Adding a new constraint

Suppose that a new constraint is added to the problem.

• If the optimal solution to the original problem satisfies the added constraint, it is
then obvious that the point is also an optimal solution to the new problem.

• If the optimal solution to the original problem does not satisfy the new constraint,
i.e., if the constraint cut away the optimal point, we can use the dual simplex method
to find the new optimal solution.

Example 8.5. Consider the problem

Minimise −2x1 + x2 − x3

s.t. x1 + x2 + x3 ≤ 6,

−x1 + 2x2 ≤ 4,

x1 , x2 , x3 ≥ 0.

The optimal tableau is given by

x1 x2 x3 x4 x5 RHS
f 0 −3 −1 −2 0 −12
x1 1 1 1 1 0 6
x5 0 3 1 1 1 10

Consider the problem with the added constraint

−x1 + 2x3 ≥ 2.
 109

Clearly the optimal point (x1 , x2 , x3 ) = (6, 0, 0) does not satisfy this constraint. The
constraint −x1 + 2x2 ≥ 2 is rewritten as

x1 − 2x3 + x6 = −2,

where x6 is a nonnegative slack variable. This row is added to the optimal tableau of the
above problem to obtain the following tableau.

x1 x2 x3 x4 x5 x6 RHS
f 0 −3 −1 −2 0 0 −12
x1 1 1 1 1 0 0 6
x5 0 3 1 1 1 0 10
x6 1 0 −2 0 0 1 −2

Multiply row 1 by −1 and add to row 3 in order to restore column x1 to a unit vector.

x1 x2 x3 x4 x5 x6 RHS
f 0 −3 −1 −2 0 0 −12
x1 1 1 1 1 0 0 6
x5 0 3 1 1 1 0 10
x6 0 −1 −3∗ −1 0 1 −8

The dual simplex method can then be applied to the above tableau. By minimum ratio test
of the dual simplex method, we see that x3 enters the basis to replace x6 . Thus, we get the
following tableau.

x1 x2 x3 x4 x5 x6 RHS
f 0 −8/3 0 −5/3 0 −1/3 −28/3
x1 1 2/3 0 2/3 0 1/3 10/3
x5 0 8/3 0 2/3 1 1/3 22/3
x3 0 1/3 1 1/3 0 −1/3 8/3

So the optimal solution of the changed problem is

(x∗1 , x∗2 , x∗3 ) = (10/3, 0, 8/3).

In summary, when a constraint is added, restore the simplex tableau first, and then con-
tinue simplex iterations (by using dual simplex method) until new solution is found.
 110

The above example introduces the idea of how to handle the case when the optimal
solution to the original problem does not satisfy the new constraint. Suppose that B is
the optimal basis before the constraint

am+1 x ≤ bm+1

is added. As seen is section 6.2, the corresponding system is given by the following system

f + (cB B −1 N − cN )xN = cB B −1 b,

xB + B −1 N xN = B −1 b.

Notice that the new constraint can be written as

am+1
B xB + am+1
N xN + xn+1 = bm+1 .

Here am+1 is decomposed into am+1

B , am+1
N and xn+1 is a nonnegative slack variable. Multi-
plying the above second equation by am+1
B and subtracting from the new constraint gives
the following system:



 f + (cB B −1 N − cN )xN = cB B −1 b,

xB + B −1 N xN = B −1 b,


 (am+1 − am+1 B −1 N )x + x

=b − am+1 B −1 b.
N B N n+1 m+1 B

The basic feasible solution to this system is

xB = B −1 b

xN = 0

xn+1 = bm+1 − am+1

B B −1 b.

The only possible violation of optimality of the new problem is the sign of bm+1 −am+1
B B −1 b.
If
bm+1 − am+1
B B −1 b ≥ 0,

then the current solution is optimal. Otherwise, if

bm+1 − am+1
B B −1 b < 0,

then the dual simplex method is used to restore feasibility.

Chapter 9

The Two-Phase method and the

Big-M Method (non-examinable)

The simplex method assumes that an initial basic feasible solution (BFS) is at hand. In
many cases, such a BFS is not readily available. There are some work may be needed to
get the simplex method started.

Example 9.1. Consider the following two groups of constraints

1.

x1 + 2x2 ≤ 4,

−x1 + x2 ≤ 1,

x1 , x2 ≥ 0.

2.

x1 + x2 + x3 ≤ 6,

−2x1 + 3x2 + 2x3 ≥ 3,

x1 , x2 , x3 ≥ 0.

For the first group of constraints, an initial basis can be found without any difficulty.
However, the second one is not. Some extra work is needed to get the initial basis.

In this chapter we will study two procedures that can be used to construct initial basis:

111
 112

• The two-phase method.

• The big-M method.

Both involve artificial variables to obtain an initial basic feasible solution.

At the end of this chapter, students should be able to apply the two-phase method
and the big-M method to solve some LPs.

9.1 The Two-phase Method

Suppose we want to solve the following LP:

Minimise cT x

subject to Ax ≤ b

x ≥ 0.

with b ≥ 0. The most convenient way to find a BFS is to introduce some slack variables
s so that the problem is re-formulated as

Minimise cT x

subject to Ax + s = b

x, s ≥ 0.

Now we pick x = 0 and s = b as BFS. This is feasible because b ≥ 0. Since the basic
variables coincide with the slack variables, z = 0 and f = 0. So our initial tableau is very
simple:

x s RHS
f −cT 0 0
s A 1 b

and we can start our simplex method.

However, in general, we may not be that lucky. In particular we may have that we
don’t have enough slack variables to construct a BFS, or that the non all component of b
are non negative and/or A does not have an identity sub–matrix.
 113

Example 9.2. Consider the following constraints

x1 + x2 + x3 ≤ 6,

−2x1 + 3x2 + 2x3 ≥ 3,

x2 , x3 ≥ 0.

Note that x1 is unrestricted, therefore we introduce x′1 , x′′1 ≥ 0, and put x1 = x′1 − x′′1 . We
also introduce slack variables x4 , x5 :

x′1 − x′′1 + x2 + x3 + x4 = 6,

−2x′1 + 2x′′1 + 3x2 + 2x3 − x5 = 3,

x′1 , x′′1 , x2 , x3 , x4 , x5 ≥ 0.

We see that the new constraint matrix does not contain an identity 2 × 2 sub-matrix and
therefor an obvious feasible basis cannot be extracted.

Let us start with an LP in the following form:

Minimise cT x

subject to Ax = b

x ≥ 0,

where b ≥ 0. Indeed, given any LP in standard form, if some component br of b is negative,

we can just multiply the r-th row by −1 to map it to this form.

If A has a m × m identity sub-matrix, then we know a quick way to select out BFS.
Otherwise, we may face some difficulty. In this case, we apply the 2-phase method. This
consists in adding further artificial variables xa to the constraints in order to force the
appearance of an identity sub-matrix. Specifically we modify the constraints as follows,

Ax + xa = b, x, xa ≥ 0,

so that the new constraint matrix is [A, 1] and we have an immediate BFS in the form
x = 0, xa = b.
 114

Note the difference between slack variables and artificial variables: slack variables are
introduced to transform problems in non-standard form to problems in standard form.
The artificial variables are introduced after having reduced the problem in standard form
and are not legitimate variables.

The two-phase method consist in a Phase I problem which is used to find a basic
feasible solution for the original constraints, then we can initiate Phase II wherein the
Simplex Method is applied to solve the original linear programming problem.

Phase 1. Solve the following linear programming problem starting with the basic
feasible solution x = 0 and xa = b :

Minimise eT xa

subject to Ax + xa = b,

x, xa ≥ 0,

where e denotes the vector wit all components equal to 1.

• If at optimality xa ̸= 0, then stop. The original problem has no feasible solution

because if it did have a feasible solution x∗ then (x∗ , 0) would be an optimal solution
of the Phase I problem.

• Otherwise, this means we have reached optimality in the form (x̄, 0). By construc-
tion, x̄ is feasible for the original problem. Lets split it in basic and nonbasic
variables be xB and xN . This step is simple: put all non zero variables in the basic
and then add enough 0 to reach a total of m variables.

Phase II. Having chosen xB , we now have B and we can solve the following linear
programming problem starting with the basic feasible solution xB = B −1 b and xN = 0 :

Minimise cB x B + cN x N

subject to xB + B −1 N xN = B −1 b,

xB , xN ≥ 0.

The purpose of the phase I is to get us to an extreme point of the feasible

region, while phase II takes us from this feasible point to an optimal point.
 115

Remark: For the system Ax = b and x ≥ 0, we change the restrictions by adding an

artificial vector xa leading to the system

Ax + xa = b, x ≥ 0, xa ≥ 0.

This gives an immediate basic feasible solution of the new system, namely xa = b and
x = 0. Even though we now have a starting basic feasible solution and the simplex method
can be applied, we have in fact changed the problem. In order to get back to our original
problem, we must force these artificial variables to zero, because Ax = b if and only if
Ax + xa = b with xa = 0. In other words, artificial variables are only a tool to get the
simplex method started, however, we must guarantee that these variables will eventually
drop to zero.

Example 9.3. Solve the following LP by using two-phase method

Minimise x1 − 2x2

subject to x1 + x2 ≥ 2,

−x1 + x2 ≥ 1,

x2 ≤ 3,

x1 , x2 ≥ 0.

By introducing the slack variables x3 , x4 and x5 , the problem becomes

Minimise x1 − 2x2

subject to x1 + x2 − x3 = 2,

−x1 + x2 − x4 = 1,

x2 + x5 = 3,

x1 , x2 , x3 , x4 , x5 ≥ 0.

Phase I
 116

Adding artificial variables x6 and x7 and consider the Phase-I problem:

Minimise x6 + x7

subject to x1 + x2 − x3 + x6 =2

−x1 + x2 − x4 + x7 = 1

x2 + x5 =3

x1 , x2 , x3 , x4 , x5 ≥ 0.

Let f0 = x6 + x7 . The Phase I minimises the objective f0 . Since x5 , x6 , x7 are basic

variables, cTB = (0, 1, 1) and we have

x1 x2 x3 x4 x5 x6 x7 RHS
f0 0 2 −1 −1 0 0 0 3
x6 1 1 −1 0 0 1 0 2
x7 −1 1* 0 −1 0 0 1 1
x5 0 1 0 0 1 0 0 3

Since z2 −c2 = 2 > 0, x7 is replaced by x2 , after pivoting operations, we have the following
table

x1 x2 x3 x4 x5 x6 x7 RHS
f0 2 0 −1 1 0 0 −2 1
x6 2* 0 −1 1 0 1 −1 1
x2 −1 1 0 −1 0 0 1 1
x5 1 0 0 1 1 0 −1 2

Replacing x6 by x1 , we have

x1 x2 x3 x4 x5 x6 x7 RHS
f0 0 0 0 0 0 −1 −1 0
x1 1 0 −1/2 1/2 0 1/2 −1/2 1/2
x2 0 1 −1/2 −1/2 0 1/2 1/2 3/2
x5 0 0 1/2 1/2 1 −1/2 −1/2 3/2

which is the optimal tableau of the Phase I. There is no artificial variable in the optimal
basis of the first phase. We have a starting basic feasible solution for proceeding to the
second phase.
 117

Phase II

Removing the artificial variables from the table, we do not consider it any more.
Replace the first row by the coefficients of the equation f − x1 + 2x2 = 0 since the original
objective is f = x1 − 2x2 .

x1 x2 x3 x4 x5 RHS
f −1 2 0 0 0 0
x1 1 0 −1/2 1/2 0 1/2
x2 0 1 −1/2 −1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2

Restoring the simplex tableau gives rise to

x1 x2 x3 x4 x5 RHS
f 0 0 1/2 3/2 0 −5/2
x1 1 0 −1/2 (1/2)* 0 1/2
x2 0 1 −1/2 −1/2 0 3/2
x5 0 0 1/2 1/2 1 3/2

Since z4 − c4 = 3/2 > 0, x4 is the entering variable. By minimum ratio test, x1 is the
leaving variable.

x1 x2 x3 x4 x5 RHS
f −3 0 2 0 0 −4
x4 2 0 −1 1 0 1
x2 1 1 −1 0 0 2
x5 −1 0 1* 0 1 1

It is evident that x3 is the entering variable and x5 is the leaving variable.

f x1 x2 x3 x4 x5 RHS
f 1 −1 0 0 0 −2 −6
x4 0 1 0 0 1 1 2
x2 0 0 1 0 0 1 3
x3 0 −1 0 1 0 1 1
 118

The optimal solution to the original LP problem is given by

x∗ = (x∗1 , x∗2 ) = (0, 3).

Note that phase I moves from the infeasible point (0,0) to the infeasible point (0,1),
and finally to the feasible point (1/2, 3/2). From this extreme point, phase II moves to
the feasible point (0,2) and finally to the optimal point (0, 3).

Analysis of the Two-Phase Method:

At the end of phase I, there are possible cases:

Case A: xa ̸= 0. In this case, the original problem is infeasible.

Proof. In fact, if there is an x ≥ 0 with Ax = b, then (x, 0) is a feasible solution of the

phase I problem and objective value at this feasible solution is 0, violating the optimality
of xa at which the objective is positive.

Case B: xa = 0. There are two subcases:

• If all artificial variables are out of the basis, remove from the last form the artificial
and construct the initial simplex step since there is a basic feasible solution at hand,
and hence proceed to Phase II.

• If some artificial variables are in the basis at zero level, we have two ways to continue.
We may first eliminate the columns corresponding to the nonbasic artificial variables
of Phase I, and then proceed to phase II directly to continue to replace those left
artificial variables without increasing the original objective values.

Example 9.4. Solve the following LP problem:

Minimise 2x1 + 3x2 + 4x3

s.t. x1 + 2x2 + x3 ≥ 3,

2x1 − x2 + 3x3 ≥ 4,

x1 , x2 , x3 ≥ 0.
 119

First, we introduce slack variables x4 and x5 , to write the problem in the standard form

Minimise 2x1 + 3x2 + 4x3

s.t. x1 + 2x2 + x3 − x4 = 3,

2x1 − x2 + 3x3 − x5 = 4,

x1 , ..., x5 ≥ 0.

Phase I: now we introduce artificial variables x6 and x7 and consider the following phase-I
problem

Minimise x6 + x7

s.t. x1 + 2x2 + x3 − x4 + x6 = 3,

2x1 − x2 + 3x3 − x5 + x7 = 4,

x1 , ..., x7 ≥ 0.

x1 x2 x3 x4 x5 x6 x7 RHS
f0 0 0 0 0 0 −1 −1 0
x6 1 2 1 -1 0 1 0 3
x7 2 1 3 0 -1 0 1 4

Restore the initial simplex method.

x1 x2 x3 x4 x5 x6 x7 RHS
f0 3 1 4 -1 -1 0 0 7
x6 1 2 1 -1 0 1 0 3
x7 2 1 3∗ 0 -1 0 1 4

x3 enters, x7 leaves

x1 x2 x3 x4 x5 x6 x7 RHS
f0 1/3 7/3 0 -1 1/3 0 -4/3 5/3
x6 1/3 7/3 0 -1 1/3 1 -1/3 5/3
x3 2/3 -1/3 1 0 -1/3 0 1/3 4/3

x2 enters, x6 leaves.
 120

x1 x2 x3 x4 x5 x6 x7 RHS
f0 0 0 0 0 0 -1 -1 0
x2 1/7 1 0 -3/7 1/7 3/7 -1/7 5/7
x3 5/7 0 1 -1/7 -2/7 1/7 3/7 11/7

This is an optimal solution to the phase I problem. The artificial variables x6 and x7 are
not basic variable at optimality. Thus we remove columns x6 and x7 and move to phase
II.

Phase II: we replace the original cost function to obtain the tableau:

x1 x2 x3 x4 x5 RHS
f -2 -3 -4 0 0 0
x2 1/7 1 0 -3/7 1/7 5/7
x3 5/7 0 1 -1/7 -2/7 11/7

We restore the simplex tableau:

x1 x2 x3 x4 x5 RHS
f 9/7 0 0 -13/7 -5/7 59/7
x2 1/7 1 0 -3/7 1/7 5/7
x3 5/7∗ 0 1 -1/7 -2/7 11/7

x1 enters, x3 leaves.

x1 x2 x3 x4 x5 RHS
f 0 0 −9/5 −8/5 −1/5 28/5
x2 0 1 −1/5 −2/5 1/5 2/5
x1 1 0 7/5 −1/5 −2/5 11/5

Thus the optimal solution is

x∗ = (11/5, 2/5, 0),

and optimal value

f ∗ = 28/5.
 121

Example 9.5. Solve the following LP problem:

Minimise −x1 + 2x2 − 3x3

s.t. x1 + x2 + x3 = 6,

−x1 + x2 + 2x3 = 4,

2x2 + 3x3 = 10,

x3 ≤ 2,

x1 , x2 , x3 ≥ 0

First, we introduce the slack variable x4 to write the problem in the standard form

Minimise −x1 + 2x2 − 3x3

s.t. x1 + x2 + x3 = 6,

−x1 + x2 + 2x3 = 4,

2x2 + 3x3 = 10,

x3 + x4 = 2,

x1 , x2 , x3 , x4 ≥ 0.

Phase I:

Minimise x5 + x6 + x7

s.t. x1 + x2 + x3 + x5 = 6,

−x1 + x2 + 2x3 + x6 = 4,

2x2 + 3x3 + x7 = 10,

x3 + x4 = 2,

x1 , x2 , x3 , x4 , x4 , x6 , x7 ≥ 0.

This corresponds to the tableau (because cTB = (0, 1, 1, 1))

x1 x2 x3 x4 x5 x6 x7 RHS
f 0 4 6 0 0 0 0 20
x5 1 1 1 0 1 0 0 6
x6 −1 1 2 0 0 1 0 4
x7 0 2 3 0 0 0 1 10
x4 0 0 1 1 0 0 0 2
 122

Pivot at y43 :

x1 x2 x3 x4 x5 x6 x7 RHS
f 0 4 0 −6 0 0 0 8
x5 1 1 0 −1 1 0 0 4
x6 −1 1 0 −2 0 1 0 0
x7 0 2 0 −3 0 0 1 4
x3 0 0 1 1 0 0 0 2

Pivot at y62 :

x1 x2 x3 x4 x5 x6 x7 RHS
f 4 0 0 2 0 −4 0 8
x5 2 0 0 1 1 −1 0 4
x2 −1 1 0 −2 0 1 0 0
x7 2 0 0 1 0 −2 1 4
x3 0 0 1 1 0 0 0 2

Pivot at y51 :

x1 x2 x3 x4 x5 x6 x7 RHS
f 0 0 0 0 −2 −2 0 0
x1 1 0 0 1/2 1/2 −1/2 0 2
x2 0 1 0 −3/2 1/2 1/2 0 2
x7 0 0 0 0 −1 −1 1 0
x3 0 0 1 1 0 0 0 2

We have reached optimality. However, we see that we still have an artificial variable in
the basis. This is not a problem because its value is 0, therefore we can eliminate the
corresponding row all together. The Phase II tableau is then obtained by inserting the
original cost function at row 0:

x1 x2 x3 x4 RHS
f 1 −2 3 0 0
x1 1 0 0 1/2 2
x2 0 1 0 −3/2 2
x3 0 0 1 1 2
 123

9.2 The Big-M method

The big-M approach is also based on introducing artificial variables, but to get rid of
the artificial variables by assigning coefficients for those artificial variables in the original
objective function in such way as to make their presence in the basis at a positive level very
unattractive from the objective function point of view. Consider the following problem:

Minimize cT x + M (eT xa )

subject to Ax + xa = b,

x, xa ≥ 0.

where M is a very large positive number.

The term M eT xa can be interpreted as a penalty to be paid by any solution with xa ̸= 0.

Even though the starting solution x = 0, xa = b is feasible to the above problem, it has a
very unattractive objective value.

Therefore, the simplex method will try to get the artificial variables out the basis, and
then continue to find an optimal solution of the original problem.

Analysis of the Big-M method.

Two cases may arise after solving the Big-M problem by the simplex method:

• Arrive at an optimal solution of Big-M problem.

• The Big-M problem has an unbounded optimal solution.

Relationship between the Big-M problem and the Original LP problem

Case A: The Big-M problem has an finite optimal solution. There are two subcases:

• (x, xa ) = (x∗ , 0) is an optimal solution of the Big-M problem. Then x∗ is the optimal
solution to the original problem.
 124

Proof. In fact, if x is an arbitrary feasible point of the original LP, then (x, 0) is a
feasible solution to the Big-M problem. Since (x∗ , 0) is the optimal solution to the
Big-M problem, we have
cT x∗ + 0 ≤ cT x + 0,

i.e.,
cT x ∗ ≤ cT x

which implies that x∗ is indeed an optimal solution of the original LP problem.

• (x∗ , x∗a ) is an optimal solution to the Big-M problem and x∗a ̸= 0.

In this case, the original LP has no feasible point, i.e., the problem is infeasible.

Proof. Suppose by contradiction that x is a feasible point of the original LP. Then
(xT , 0) is feasible for the Big-M problem. By optimality of (x∗ , x∗a ), we have

cT x∗ + M x∗a ≤ cT x

which is impossible because M is very large and x∗a > 0.

Case B: The Big-M problem has an unbounded optimal value. Assume that
zk − ck = max(zj − cj ) > 0 and yk ≤ 0, then we have the following two cases:

• all the artificial are equal to zero, then the original LP has an unbounded optimal
solution.

Proof. In this case, the optimal solution of the Big-M problem has the form (x∗ T , 0),
therefore x∗ is feasible for the original LP, but because (x∗ T , 0) is unbounded, then
x∗ is unbounded. This solution is also optimal because if it wasn’t there would be
another optimal solution x̄ such of the LP and (x̄, 0) would be a feasible solution of
the Big-M problem with better objective value, which is not allowed.

• not all the artificial are equal to zero, then the original LP is infeasible.

Proof. Omitted.
 125

In summary:

Solve the Big-M problem

A. Optimal is finite B. Optimal is unbounded
A1. x̄a = 0 A2. x̄a ̸= 0 B1. x̄a = 0 B2. x̄a ̸= 0
x̄ optimal OLP infeasible OLP x̄ unbounded OLP infeasible OLP

Example 9.6. Solve the LP by Big-M method

Minimise x1 − 2x2

subject to x1 + x2 ≥ 2,

x2 ≤ 3,

x1 , x2 ≥ 0.

Adding slack variables x3 and x4 and artificial variables x5 , the Big-M LP can be written
as

Minimise x1 − 2x2 + M x5

subject to x1 + x2 − x3 + x5 = 2,

x2 + x4 = 3,

x1 , x2 , x3 , x4 , x5 ≥ 0.

The initial basic variables are x5 and x4 ,

   
1 0 1 1 −1
B = [a5 a4 ] =   , N = [a1 a2 a3 ] =  ,
0 1 0 1 0

cB = (c5 c4 ) = (M 0), cN = (c1 c2 c3 ) = (1 − 2 0).

Note that in the simplex method, we work with tableau (including the initial one) of the
form

xB xN RHS
f 0 cB B −1 N − cN cB B −1 b
xB I B −1 N B −1 b
 126

where the reduce cost zj − cj are zero for all basic variables.

Let us find the initial tableau:

 
  1 1 −1    
−1
cB B N − cN = M 0   − 1 −2 0 = M − 1 M + 2 −M ,
0 1 0
     
  2 1 1 −1 2
cB B −1 b = M 0   = 2M, B −1 N = N =   , B −1 b = b =   .
3 0 1 0 3

Thus we obtain the following initial tableau for the simplex method

x1 x2 x3 x4 x5 RHS
f M − 1 M+2 −M 0 0 2M
x5 1 1∗ −1 0 1 2
x4 0 1 0 1 0 3

Now we apply the simplex method: x2 enters and x5 leaves:

x1 x2 x3 x4 x5 RHS
f −3 0 2 0 −(M + 2) −4
x2 1 1 −1 0 1 2
x4 −1 0 1∗ 1 −1 1

x3 enters and x4 leaves:

x1 x2 x3 x4 x5 RHS
f −1 0 0 −2 −M −6
x2 0 1 0 1 0 3
x3 −1 0 1 1 −1 1

So the optimal solution of the original problem is

x∗ = (x∗1 , x∗2 ) = (0, 3)

and the optimal value is

f ∗ = −6.
 127

Example 9.7. Solve the LP by using Big-M method

Minimise −x1 − 3x2 + x3

subject to x1 + x2 + 2x3 ≤ 4,

−x1 + x3 ≥ 4,

x3 ≥ 3,

x1 , x2 , x3 ≥ 0.

Example 9.8. Solve the LP by using Big-M method

Minimise −x1 − x2

subject to x1 − x2 − x3 = 1,

−x1 + x2 + 2x3 − x4 = 1,

x1 , x2 , x3 , x4 ≥ 0.
Bibliography

[Bea55] E. M. L. Beale. Cycling in the dual simplex algorithm. Naval Research Logistics
Quarterly, pages 269–275, 1955.

[BT97] D. Bertsimas and J.N. Tsitsiklis. Introduction to Linear Optimization. Athena

Scientific series in optimization and neural computation. Athena Scientific, 1997.

[DT97] George B. Dantzig and Mukund N. Thapa. Linear programming. 1. Springer

Series in Operations Research. Springer-Verlag, New York, 1997. Introduction,
With 1 CD-ROM for Windows.

[Gre94] Harvey J. Greenberg. The use of the optimal partition in a linear programming
solution for postoptimal analysis. Operations Research Letters, 15(4):179 – 185,
1994.

[KM72] V. Klee and G.J. Minty. How good is the simplex algorithm? In O. Shisha,
editor, Inequalities, III, pages 159–175, 1972.

128