Linear Programming

Samia Kerdjoudj
kerdjoudj_samia@[Link]

University of Blida 1.

2 novembre 2025
 Chapter 3
Primal Method for Solving a Linear Program

S. Kerdjoudj Linear programming 1/62

 Alternate Forms of Linear Programming General Form of a Linear Program

General Form of a Linear Program

 n
 X

 min or max(Z) = cj xj



 j=1



 Xn

 s.t. aij xj ≤ bi , ∀i ∈ I1





 j=1

 Xn

 aij xj = bi , ∀i ∈ I2
(P ) j=1

 n

 X

 aij xj ≥ bi , ∀i ∈ I3



 j=1




 xj ≥ 0,


∀j ∈ J1



 xj ≤ 0, ∀j ∈ J2


xj ∈ R, ∀j ∈ J3
I = I1 ∪ I2 ∪ I3 with |I| = m : number of constraints.
J = J1 ∪ J2 ∪ J3 with |J| = n : number of variables.
S. Kerdjoudj Linear programming 2/62
 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Canonical Form Type I

 n

 X

 max(Z) = cj xj



 j=1
Xn
(Pc )

 s.t. aij xj ≤ bi , ∀i ∈ {1, 2, . . . , m}



 j=1

 xj ≥ 0, ∀j ∈ {1, 2, . . . , n}

Canonical Form Type II

 n

 X

 min(Z) = cj xj



 j=1
Xn
(Pc )

 s.t. aij xj ≥ bi , ∀i ∈ {1, 2, . . . , m}



 j=1

 xj ≥ 0, ∀j ∈ {1, 2, . . . , n}

S. Kerdjoudj Linear programming 3/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Remarks
A linear programming problem is said to be in canonical form if :
All variables x1 , x2 , . . . , xn are required to be non-negative.
All other constraints are inequalities :
Minimization case : All constraints are of the form ≥ (i.e., lower
bound constraints).
Maximization case : All constraints are of the form ≤ (i.e., upper
bound constraints).

S. Kerdjoudj Linear programming 4/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Remarks
A linear programming problem is said to be in canonical form if :
All variables x1 , x2 , . . . , xn are required to be non-negative.
All other constraints are inequalities :
Minimization case : All constraints are of the form ≥ (i.e., lower
bound constraints).
Maximization case : All constraints are of the form ≤ (i.e., upper
bound constraints).

Theorem
Every linear program can be transformed into an equivalent linear
program in canonical form.

S. Kerdjoudj Linear programming 4/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Writing Rules
1 Any variable x ∈ R can be replaced by the difference of two
j
non-negative variables :

xj = x′j − x′′j where x′j ≥ 0 and x′′j ≥ 0

2 Any variable xj ≤ 0 can be replaced by a non-negative variable :

x′j = −xj ≥ 0

S. Kerdjoudj Linear programming 5/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Writing Rules
1 Any equality constraint can be written as two inequality constraints :
 n
X
   
 aij xj ≤ b
n 

X j=1
 aij xj = b ≡ X n


j=1 
 aij xj ≥ b

j=1

2 Any ≥ constraint can be written as a ≤ constraint :

   
Xn Xn
 aij xj ≥ b ≡  −aij xj ≤ −b
j=1 j=1

S. Kerdjoudj Linear programming 6/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Example 1 : Writing (P) in Canonical Form

LP in General Form


 max(Z) = x1 − x2 − x3





 5x + x2 + x3 ≥ 30

 1
(P ) 4x1 − x2 − x3 = 5





 x1 + x2 − x3 ≤ 10



x ≥ 0, x ≤ 0, x ∈ R
1 2 3

S. Kerdjoudj Linear programming 7/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Transformations
1 Let x′ = −x ≥ 0
2 2

2 Let x3 = x′3 − x′′3 , where x′3 , x′′3 ≥ 0

3 5x1 + x2 + x3 ≥ 30 ⇔ −5x1 − x2 − x3 ≤ −30

4x1 − x2 − x3 ≤ 5
4 4x1 − x2 − x3 = 5 ⇔
4x − x − x ≥ 5
 1 2 3
4x1 − x2 − x3 ≤ 5
⇔
−4x + x + x ≤ −5
1 2 3

S. Kerdjoudj Linear programming 8/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Canonical Form of (P)



 max(Z) = x1 + x′2 − x′3 + x′′3





 −5x1 + x′2 − x′3 + x′′3 ≤ −30




4x1 + x′ − x′ + x′′ ≤ 5
2 3 3
(Pc )

 −4x1 − x2 + x3 − x′′3 ≤ −5
′ ′





 ′ ′ ′′
x1 − x2 + x3 − x3 ≤ 10




x1 , x′2 , x′3 , x′′3 ≥ 0

S. Kerdjoudj Linear programming 9/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Example 2 : Writing (P) in Canonical Form

LP in General Form


 min(Z) = 7x1 + x2 + 10x3





 x + x2 + x3 ≤ 20

 1
(P ) 5x1 − 3x2 + x3 = 25





 2x1 − x2 + x3 ≥ 10



x ≤ 0, x ≥ 0, x ∈ R
1 2 3

S. Kerdjoudj Linear programming 10/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Transformations
1 Let x′ = −x ≥ 0
1 1

2 Let x3 = x′3 − x′′3 , where x′3 , x′′3 ≥ 0

3 x1 + x2 + x3 ≤ 20 ⇔ −x1 − x2 − x3 ≥ −20

5x1 − 3x2 + x3 ≤ 25
4 5x1 − 3x2 + x3 = 25 ⇔
5x − 3x + x ≥ 25
 1 2 3
−5x1 + 3x2 − x3 ≥ −25
⇔
5x − 3x + x ≥ 25
1 2 3

S. Kerdjoudj Linear programming 11/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Canonical Form of (P)



 min(Z) = −7x′1 + x2 + 10x′3 − 10x′′3



 ′

 x1 − x2 − x′3 + x′′3 ≥ −20




5x′ + 3x2 − x′ + x′′ ≥ −25
1 3 3
(Pc )

 −5x1 − 3x2 + x3 − x′′3 ≥ 25
′ ′





 ′ ′ ′′
−2x1 − x2 + x3 − x3 ≥ 10



 ′
x1 , x2 , x′3 , x′′3 ≥ 0

S. Kerdjoudj Linear programming 12/62

 Alternate Forms of Linear Programming Canonical Forms of Linear Programming

Any minimization problem can be written as a maximization problem :

   
Xn Xn
min(Z) = cj xj  ≡ − max(Z) = −cj xj 
j=1 j=1

Example :

Canonical Form Canonical Form

 
 
min(Z) = c1 x1 + c2 x2

 − max(Z) = −c1 x1 − c2 x2



 

a11 x1 + a12 x2 ≥ b1 −a11 x1 − a12 x2 ≤ −b1
(Pc ) ⇔ (Pc )

 a21 x1 + a22 x2 ≥ b2 
 −a21 x1 − a22 x2 ≤ −b2

 


 

x , x ≥ 0 x , x ≥ 0
1 2 1 2

S. Kerdjoudj Linear programming 13/62

 Alternate Forms of Linear Programming Standard Form of Linear Programming

Standard Form
 n

 X

 max or min(Z) = cj xj



 j=1
Xn
(Ps )

 s.t aij xj = bi , ∀i ∈ {1, 2, · · · , m}



 j=1

 xj ≥ 0, ∀j ∈ {1, 2, · · · , n}

S. Kerdjoudj Linear programming 14/62

 Alternate Forms of Linear Programming Standard Form of Linear Programming

Remarks
A linear programming problem is said to be in standard form if :
All variables x1 , x2 , . . . , xn are required to be non-negative.
All constraints (other than variable non-negativity) are expressed
as equalities.

S. Kerdjoudj Linear programming 15/62

 Alternate Forms of Linear Programming Standard Form of Linear Programming

Remarks
A linear programming problem is said to be in standard form if :
All variables x1 , x2 , . . . , xn are required to be non-negative.
All constraints (other than variable non-negativity) are expressed
as equalities.

Theorem
Every linear program can be transformed into an equivalent linear
program in standard form.

S. Kerdjoudj Linear programming 15/62

 Alternate Forms of Linear Programming Standard Form of Linear Programming

Conversion to Standard Form

Converting a linear program to standard form involves introducing
additional variables ei ≥ 0, called slack or surplus variables, in the
following way :
1 Any constraint of the form ≥ is converted into an equality by
subtracting a surplus variable ei :
n
! n
!
X X
aij xj ≥ bi ⇔ aij xj −ei = bi , ei ≥ 0
i=1 i=1

2 Any constraint of the form ≤ is converted into an equality by

adding a slack variable ei :
n
! n
!
X X
aij xj ≤ bi ⇔ aij xj +ei = bi , ei ≥ 0
i=1 i=1

S. Kerdjoudj Linear programming 16/62

 Alternate Forms of Linear Programming Standard Form of Linear Programming

Example of Converting a LP to Standard Form

General Form Standard Form

 

 max(Z) = 7x + x + 10x 
max(Z) = −7x′1 + x2 + 10x′3 − 10x′′3

 1 2 3 


 


x1 + x2 + x3 ≤ 20 
−x′ + x2 + x′3 − x′′3 +e1 = 20

 
 1
(P ) 5x1 − 3x2 + x3 = 25 ⇒ (Ps ) −5x′1 − 3x2 + x′3 − x′′3 = 25

 


 

2x1 − x2 + x3 ≥ 10
 
−2x′1 − x2 + x′3 − x′′3 −e2 = 10

 


 
x′ , x , x′ , x′′ , e , e ≥ 0
x1 ≤ 0, x2 ≥ 0, x3 ∈ R 1 2 3 3 1 2

S. Kerdjoudj Linear programming 17/62

 Alternate Forms of Linear Programming Matrix Form of a Linear Program

A LP problem can be represented in matrix form as follows :

Canonical Form Type 1 Canonical Form Type 2

 
 max(Z) = CX
  min(Z) = CX

(Pc ) s.t. AX ≤b (Pc ) s.t. AX ≥ b

 

X ≥0 X ≥0

Standard Form (Maximization) Standard Form (Minimization)

 
 max(Z) = CX
  min(Z) = CX

(Ps ) s.t. AX = b (Ps ) s.t. AX = b

 

X ≥0 X ≥0

X : Decision variables vector C : Cost vector (1 × n).

(n × 1).
A : Constraint matrix (m × n). b : Right-hand side vector (m × 1).
S. Kerdjoudj Linear programming 18/62
 Alternate Forms of Linear Programming Matrix Form of a Linear Program

 
a11 a12 ··· a1n
 
 a21 a22 ··· a2n 
Let A = 
 .. .. .. .. 
 be the constraint matrix (m × n) .
 . . . . 
am1 am2 · · · amn
We define :

Ai : The i-th row of matrix A ;

Aj : The j-th column of matrix A ;

AI : The submatrix of A formed by the set of rows indexed by I ;

AJ : The submatrix of A formed by the set of columns indexed by J.

S. Kerdjoudj Linear programming 19/62

 Feasible Basic Solution

Let us consider (Ps ) a standard linear programming problem :



 max or min(Z) = CX

(Ps ) s.t. AX = b,


 X≥0

The problem (Ps ) consists of :

1 An objective function to optimize.
2 A linear system AX = b.
3 A set of constraints on the variables X ≥ 0.

Solving (Ps ) means determining, among the solutions of the linear

system AX = b, the one that satisfies X ≥ 0 and gives Z an optimal
value.

S. Kerdjoudj Linear programming 20/62

 Feasible Basic Solution Reminder : Solving Linear Systems

Rank of a Matrix
Let A be an (m × n)-matrix.
1 The rank of A, denoted by rg(A), is the maximum number of
linearly independent columns (or rows) of A.
2 The matrix A is said to be of full rank if rg(A) = m.

S. Kerdjoudj Linear programming 21/62

 Feasible Basic Solution Reminder : Solving Linear Systems

Theorem
Let the system S = {AX = b} where A ∈ Rm×n , X ∈ Rn×1 , and
b ∈ Rm×1 .
Let (A|b) be the augmented matrix of S.
1 If rg(A) < rg(A|b), then S is inconsistent and has no solution.
2 If rg(A) = rg(A|b), then S is consistent. Furthermore :
If rg(A) < m, then S is redundant.
If rg(A) = m, then :
If m = n, then S has a unique solution X = A−1 b.
If m < n, then S has infinitely many solutions.

S. Kerdjoudj Linear programming 22/62

 Feasible Basic Solution Reminder : Solving Linear Systems

Example 1 : rg(A) <rg(A|b)



 2x1
 +3x2 −4x3 = 1
(S) x1 +x2 +x3 =1


 4x +6x2 −8x3 = 3
1
We have :
   
R1 2 3 −4 1 R1 2 3 −4 1
   
R2 
 1 1 1 1  ∼ R2 − 1 R1  0 − 1
 2  2 3 1
2


R3 4 6 −8 3 R3 − 2R1 0 0 0 1

Thus, rg(A) = 2 <rg(A|b) = 3 so (S) has no solution.

S. Kerdjoudj Linear programming 23/62

 Feasible Basic Solution Reminder : Solving Linear Systems

Example 2 : rg(A) = rg(A|b) < n



 2x1
 +3x2 −4x3 = 1
(S) x1 +x2 +x3 =1


 4x +6x2 −8x3 = 2
1
We have :
   
R1 2 3 −4 1 R1 2 3 −4 1
   
R2 
 1 1 1 1  ∼ R2 − 1 R1  0 − 1
 2  2 3 1
2


R3 4 6 −8 2 R3 − 2R1 0 0 0 0

Thus, rg(A) = rg(A|b) = 2 < 3. So equation 3 is redundant, it can be

omitted from (S), and the system therefore has infinitely many
 
2 − 7x3
 
solutions : X = −1 + 6x3  , ∀x3 ∈ R.
x3
S. Kerdjoudj Linear programming 24/62
 Feasible Basic Solution Reminder : Solving Linear Systems

Example 3 : rg(A) = rg(A|b) = n



 x1
 +x2 +x3 =7
(S) 2x1 +3x2 +2x3 = 6


 x +x2 +3x3 = 2
1
We have :
   
R1 1 1 1 7 R1 1 1 1 7
   
R2 
 2 3 2 6  ∼ R2 − 2R1  0 1 0 −8 
  
R3 1 1 3 2 R3 − R1 0 0 2 −5

Thus, rg(A) = rg(A|b) = 3 = n. So (S) admits a unique solution :

 
35
 2 
X=A b=
−1
 −8 

− 25
S. Kerdjoudj Linear programming 25/62
 Feasible Basic Solution Basic Variables

Let us consider a standard linear programming problem :



 max(Z) = CX

(Ps ) s.t. AX = b,


 X≥0
Assume the linear system AX = b is of full rank (i.e., rg(A) = m).
Basis – Basic Variables
An m-element subset J ⊂ {1, 2, . . . , n} is called a basis (with respect to
the matrix A) if the columns of A indexed by the elements in J are
linearly independent. In other words, the submatrix AJ , is invertible
(i.e., det(AJ ) 6= 0).
1 AJ is called the basis matrix .
2 The variables XJ = {xj | j ∈ J} are called basic variables.
3 The variables XJ = {xj | j ∈
/ J} are called non-basic variables.
S. Kerdjoudj Linear programming 26/62
 Feasible Basic Solution Basic Variables

Remarks
1 Under the full rank assumption, at least one non-empty basis exists.
n


2 There are at most m possible basiss.
3 Without loss of generality, by reordering the columns of A, we can always
write the following block decompositions :
A = (AJ A!
J
), AJ is the matrix formed by the columns Aj , j ∈
/ J.
XJ
X= .
XJ
The system AX = b is equivalent to : AJ XJ + AJ XJ = b.

The LP problem can be rewritten as :


J J
 max(Z) = C XJ + C XJ

(Ps ) J J
s.t A XJ + A XJ = b,


XJ ≥ 0, XJ ≥ 0
S. Kerdjoudj Linear programming 27/62
 Feasible Basic Solution Basic Feasible Solution

Consider the linear system {AX = b, X ≥ 0} and let J be a basis.

Then :

AX = b ⇒ AJ XJ + AJ XJ = b

⇒ (AJ )−1 AJ XJ + (AJ )−1 AJ XJ = (AJ )−1 b

⇒ XJ + (AJ )−1 AJ XJ = (AJ )−1 b

⇒ XJ = (AJ )−1 b − (AJ )−1 AJ XJ

S. Kerdjoudj Linear programming 28/62

 Feasible Basic Solution Basic Feasible Solution

Basic Solution (BS)

!
XJ
A vector X = is called a basic solution associated with the basis
XJ
J if XJ = 0 and XJ = (AJ )−1 b.

Basic Feasible Solution (BFS)

!
XJ
A basic solution X = is called a basic feasible solution if XJ = 0
XJ
and XJ = (AJ )−1 b ≥ 0.

Degenerate Basic Solution

A basic solution is said to be degenerate if some components of XJ are
zero (i.e., ∃j ∈ J such that xj = 0).

S. Kerdjoudj Linear programming 29/62

 Feasible Basic Solution Exemple

Example
Determine the basic solutions and the basic feasible solutions of the
following linear program :


 max(Z) = 2x1 +3x2


 x1 +x2 ≤ 6
(P )

 x2 ≤3



x1 , x2 ≥0

S. Kerdjoudj Linear programming 30/62

 Feasible Basic Solution Exemple

Standard Form of (P )


 max(Z) = 2x1 +3x2


 x1 +x2 +x3 =6
(Ps )

 x2 +x4 = 3



x1 , x2 , x3 , x4 ≥0

S. Kerdjoudj Linear programming 31/62

 Feasible Basic Solution Exemple

Standard Form of (P )


 max(Z) = 2x1 +3x2


 x1 +x2 +x3 =6
(Ps )

 x2 +x4 = 3



x1 , x2 , x3 , x4 ≥0

S. Kerdjoudj Linear programming 31/62

 Feasible Basic Solution Exemple

Standard Form of (P )


 max(Z) = 2x1 +3x2


 x1 +x2 +x3 =6
(Ps )

 x2 +x4 = 3



x1 , x2 , x3 , x4 ≥0

We have 2 constraints and 4 variables, and rg(A) = 2. Therefore, (P )

admits at most 42 = 2!2!
4!
= 6 basiss.

S. Kerdjoudj Linear programming 31/62

 Feasible Basic Solution Exemple

Standard Form of (P )


 max(Z) = 2x1 +3x2


 x1 +x2 +x3 =6
(Ps )

 x2 +x4 = 3



x1 , x2 , x3 , x4 ≥0

We have 2 constraints and 4 variables, and rg(A) = 2. Therefore, (P )

admits at most 42 = 2!2!
4!
= 6 basiss.

1 J1 = {1, 2} 3 J3 = {1, 4} 5 J5 = {2, 4}

2 J2 = {1, 3} 4 J4 = {2, 3} 6 J6 = {3, 4}

S. Kerdjoudj Linear programming 31/62

 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J1 = {1, 2} and J1 = {3, 4}

S. Kerdjoudj Linear programming 32/62

 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J1 = {1, 2} and J1 = {3, 4}

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0
0 1

S. Kerdjoudj Linear programming 32/62

 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J1 = {1, 2} and J1 = {3, 4}

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0
0 1
Therefore, J1 is a basis with x3 = 0 and x4 = 0.

S. Kerdjoudj Linear programming 32/62

 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J1 = {1, 2} and J1 = {3, 4}

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0
0 1
Therefore, J1 is a basis with x3 = 0 and x4 = 0.
! ! ! !
x1
−1 1 −1 6 3
XJ1 = = AJ1 b= = ≥0
x2 0 1 3 3
   
x1 3
   
x2  3
Thus, J1 is a basic feasible solution, with : X =    
x  = 0
 3  
x4 0
S. Kerdjoudj Linear programming 32/62
 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J2 = {1, 3} and J2 = {2, 4}.

!
1 1
AJ2 = ⇒ det(AJ2 ) = 0.
0 0

Therefore J2 is not a basis.

S. Kerdjoudj Linear programming 33/62

 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J3 = {1, 4} and J3 = {2, 3},

!
1 0
AJ3 = ⇒ det(AJ3 ) = 1 6= 0.
0 1
Therefore J3 is a basis with x2 = 0 and x3 = 0.
! ! ! !
x1

J3 −1 1 0 6 6
XJ3 = = A ×b= = ≥0
x4 0 1 3 3
   
x1 6
   
x2  0
Thus, J3 is a basic feasible solution with X =    
x  = 0
 3  
x4 3
S. Kerdjoudj Linear programming 34/62
 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J4 = {2, 3} and J4 = {1, 4},

!
1 1
AJ4 = ⇒ det(AJ4 ) = −1 6= 0.
1 0
Therefore J4 is a basis with x1 = 0 and x4 = 0.
! ! ! !
x2

J4 −1 0 1 6 3
XJ4 = = A ×b= = ≥0
x3 1 −1 3 3
   
0 x1
   
x2  3
Thus, J4 is a basic feasible solution with X =    
x  = 3
 3  
x4 0
S. Kerdjoudj Linear programming 35/62
 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
AX = b ⇔ .  2 =
 
0 1 0 1 x 3  3
x4

J5 = {2, 4} and J5 = {1, 3},

!
1 0
AJ5 = ⇒ det(AJ5 ) = 1 6= 0.
1 1

Therefore J5 is a basis with x1 = 0 and x3 = 0.

! ! ! !
x2

J5 −1 1 0 6 6
XJ5 = = A ×b= = ⇐ x4 ≤ 0
x4 −1 1 3 −3

J5 is not a basic feasible solution

S. Kerdjoudj Linear programming 36/62

 Feasible Basic Solution Exemple

 
! x1 !
1 1 1 0 x  6
 2
AX = b ⇔ .  =
0 1 0 1 x 3  3
x4

J6 = {3, 4} and J6 = {1, 2},

!
1 0
AJ6 = ⇒ det(AJ6 ) = 1 6= 0.
0 1
Therefore J6 is a b with x1 = 0 and x2 = 0.
! ! ! !
x3

J6 −1 1 0 6 6
XJ6 = = A ×b= ≥0 =
x4 3 0 1 3
   
x1 0
   
x2  0
J6 is a basic feasible solution avec X =    
x  = 6
 3  
x4 3
S. Kerdjoudj Linear programming 37/62
 Feasible Basic Solution Extreme Points and Basic Feasible Solutions

Theorem (Extreme Points and Basic Feasible Solutions)

Consider the feasible set S = {x ∈ Rn | Ax = b, x ≥ 0}. Then x is the
extreme points of S if and only if x is a basic feasible solutions of S.

Proof ( BFS ⇒ Extreme Point)

Suppose x is a BFS corresponding to a basis J.
Assume, for contradiction, that x is not an extreme point. Then

∃y, z ∈ S, y 6= z , λ ∈]0, 1[, x = λy + (1 − λ)z.

Since ∀j ∈ J, xj = 0 and y, z ≥ 0, it follows that ∀j ∈ J, yj = zj = 0.

Thus, y and z have the same basic and non-basic variables as x, which
means they represent the same BFS as x.
This contradicts the assumption that y 6= z.


S. Kerdjoudj Linear programming 38/62

 Feasible Basic Solution Extreme Points and Basic Feasible Solutions

Proof (Extreme Point ⇒ BFS)

Suppose x is an extreme point of S and assume, for contradiction, that is
not a BFS.
Hence, there is J = {j | xj > 0} with |J| = k and columns of AJ are
linearly dependent (otherwise x would be basic).
′
Then there exists a nonzero vector d ∈ Rk such that AJ d′ = 0.
d = d′ ∀j ∈ J
j j
Define the vector d ∈ Rn by setting
d = 0 otherwise.
j

For sufficiently small ε > 0, the points x+ = x + εd and x− = x − εd are

both distinct (since d 6= 0) and feasible (Ax± = b, and x± ≥ 0).
Then x = 21 x+ + 12 x− with x+ 6= x− , contradicting that x is an extreme
point.


S. Kerdjoudj Linear programming 39/62

 Feasible Basic Solution Extreme Points and Basic Feasible Solutions

Corollary
If there is an optimal solution, then there is an optimal basic feasible
solution.

S. Kerdjoudj Linear programming 40/62

 Feasible Basic Solution Extreme Points and Basic Feasible Solutions

Geometric View of Linear Programming

Extreme Points and Basic Feasible Solutions

Each extreme point of the feasible polyhedron corresponds to a basic
feasible solution of (P ).

Geometric Interpretation
Solving a linear program means walking along the edges of the feasible
region from vertex to vertex, seeking the one that maximizes (or
minimizes) the objective.

S. Kerdjoudj Linear programming 41/62

 Feasible Basic Solution Extreme Points and Basic Feasible Solutions

Example


 max(Z) = 2x1 +3x2


 x1 +x2 ≤6
(P )

 x2 ≤3


 x1 , x2 ≥0
x2

E non-feasible basis

feasible basis B C feasible basis

x2 = 3
▽Z

D
D feasible basis
x1
feasible basis A
x1 + x2 = 6

S. Kerdjoudj Linear programming 42/62

 Feasible Basic Solution Extreme Points and Basic Feasible Solutions



 max(Z) = 2x1 +3x2


 x1 +x2 ≤6
(P )

 x2 ≤3


 x , x2 ≥0
1

J Extreme Solution Nature of the Solution Z

point
{1, 2} C = (3, 3)T (3, 3, 0, 0)T Basic feasible, non-degenerate 15
{1, 3} – – Not a basis –
{1, 4} D = (6, 0)T (6, 0, 3, 0)T Basic feasible, non-degenerate 12
{2, 3} B = (0, 3)T (0, 3, 3, 0)T Basic feasible, non-degenerate 9
{2, 4} E = (0, 6)T (0, 6, 0, −3)T Basic solution, not feasible –
{3, 4} A = (0, 0)T (0, 0, 6, 3)T Basic feasible, non-degenerate 0
T
Conclusion : The optimal solution is at vertex C = (3, 3) with Z = 15.
S. Kerdjoudj Linear programming 43/62
Canonical form for a basis of a linear programming

Definition
A linear program written in standard form is said to be in canonical
form for a basis J if :
1 AJ is, up to a permutation of its columns, the identity matrix Im .
2 For all j ∈ J, C j = 0.

S. Kerdjoudj Linear programming 44/62

Canonical form for a basis of a linear programming Examples



 max(Z) = 4x1 +5x2





 2x1 +x2 +x3 =8
(P ) x1 +2x2 +x4 =7



 x2 +x5 = 3



 x , 1 x2 ,
x3 , x4 , x5 ≥0
 
1 0 0
 
If J = {3, 4, 5}, then A = I3 = 0 1 0
J  J
 and C = (0, 0, 0).
0 0 1
Hence (P ) is written in canonical form for thebasis
 J.  
x1 0
   
x2  0
   
   
Moreover, the BFS associated with J is X = x3  = 8
   
x  7
 4  
x5 3
S. Kerdjoudj Linear programming 45/62
Canonical form for a basis of a linear programming Examples



 max(Z) = 8x1 −9x3





 2x1 +x2 +x3 =3
(P ) x1 +2x3 +x4 =2



 x3 +x5 = 3



 x1 , x2 , x3 ,
x5 x4 ,
≥0
 
1 0 0
 
If J = {2, 4, 5}, then A = I3 = 0 1 0
J  J
 and C = (0, 0, 0).
0 0 1
Hence (P ) is written in canonical form for thebasis
 J.  
x1 0
   
x2  3
   
   
Moreover, the BFS associated with J is X = x3  = 0
   
x  2
 4  
x5 3
S. Kerdjoudj Linear programming 46/62
Canonical form for a basis of a linear programming Examples



 max(Z) = 4x1 +5x2 −x4





 2x1 +x2 +x3 =8
(P ) x1 +2x2 +x4 =7



 x2 +x5 = 3



 x1 , x2 ,
x3 , x4 , x5 ≥0
 
1 0 0
 
If J = {3, 4, 5}, then AJ = I3 = 
 0 1 0 and C J = (0, −1, 0) 6= 0.

0 0 1
Hence (P ) is not written in canonical form for the basis J.

S. Kerdjoudj Linear programming 47/62

Canonical form for a basis of a linear programming Écriture d’un PL SFC par rapport à une basis

Writing an LP in Canonical Form for a Basis (1/3)

Consider a linear program written in standard form :


 max(Z) = CX

(P ) s.t AX = b,


 X≥0
such that the linear system AX = b is of full rank (rank(A) = m).
Let J be a basis of (P ). Then (P ) can be rewritten as :


 max(Z) = C J XJ + C J XJ

(P ) s.t AJ XJ + AJ XJ = b, · · · · · · · · · (∗)


 X ,X ≥ 0 J J

S. Kerdjoudj Linear programming 48/62

Canonical form for a basis of a linear programming Écriture d’un PL SFC par rapport à une basis

Writing an LP in Canonical Form for a Basis (2/3)

−1
Multiplying (∗) by AJ yields :

−1
−1 J
−1
AJ AJ XJ + AJ A XJ = AJ b

−1
−1
XJ + AJ AJ XJ = AJ b

−1
−1 J
XJ = AJ b − AJ A XJ

Substituting into the objective function yields :


−1
−1 J 
max(Z) =C J AJ b − AJ A XJ + C J XJ

−1
−1 J
max(Z) =C J AJ b − C J AJ A XJ + C J XJ

−1 
−1 J 
max(Z) − C J AJ b = C J − C J AJ A XJ

S. Kerdjoudj Linear programming 49/62

Canonical form for a basis of a linear programming Écriture d’un PL SFC par rapport à une basis

Writing an LP in Canonical Form for a Basis (3/3)

−1
We set π = C J AJ and α = π b.
We obtain the following linear program (P C), equivalent to (P ) :

  

 max(Z) − α = C J − πAJ X
 J

−1 J

J −1 b
(P C) ≡ (P ) s.c X J + AJ A X = A

 J
 XJ , XJ ≥ 0

(P C) is said to be in canonical form for the basis J.

π is called the multiplier vector corresponding to the basis J.


b = (C J − πAJ , C J − πAJ ) = (0, C J − C J AJ −1 AJ ) : the
C
reduced cost vector corresponding to the basis J .

S. Kerdjoudj Linear programming 50/62

Canonical form for a basis of a linear programming Écriture d’un PL SFC par rapport à une basis

Summary
The LP in canonical form for the basis J can be written as

 b
 max(Z) − α
 = CX
(P C) s.t b =b
AX b


 X≥0

where


1 Ab = AJ −1 × A. 3 b = C − C J × A.
C b


2 bb = AJ −1 × b. 4 α = C J × bb.

S. Kerdjoudj Linear programming 51/62

Canonical form for a basis of a linear programming Example

Example
Write the following linear program in canonical form for the bases
J1 = {1, 2} and J2 = {1, 4}.


 max(Z) = 2x1 +x2 +6x3 −2x4 +5x5


 x1 +x2 +3x3 −x4 +4x5 = 4
(P )

 x2 +2x3 +x4 +2x5 = 3



x1 , x2 , x3 , x4 , x5 ≥0

! !
1 1 3 −1 4 4
A= b=
0 1 2
2 1 3
   t
C = 2 1 6 −2 5 X = x1 x2 x3 x4 x5

S. Kerdjoudj Linear programming 52/62

Canonical form for a basis of a linear programming Example

J1 = {1, 2} and J1 = {3, 4, 5}.

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0.
0 1
Hence J1 is a basis with x3 = 0, x4 = 0, x5 = 0.
! ! !
b= 1 −1 1 1 3 −1 4 1 0 1 −2 2
1 A =
0 1 0 1 2 1 2 0 1 2 1 2

S. Kerdjoudj Linear programming 53/62

Canonical form for a basis of a linear programming Example

J1 = {1, 2} and J1 = {3, 4, 5}.

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0.
0 1
Hence J1 is a basis with x3 = 0, x4 = 0, x5 = 0.
! ! !
b= 1 −1 1 1 3 −1 4 1 0 1 −2 2
1 A =
0 1 0 1 2 1 2 0 1 2 1 2
! ! !
1 −1 4 1
2 bb= = .
0 1 3 3

S. Kerdjoudj Linear programming 53/62

Canonical form for a basis of a linear programming Example

J1 = {1, 2} and J1 = {3, 4, 5}.

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0.
0 1
Hence J1 is a basis with x3 = 0, x4 = 0, x5 = 0.
! ! !
b= 1 −1 1 1 3 −1 4 1 0 1 −2 2
1 A =
0 1 0 1 2 1 2 0 1 2 1 2
! ! !
1 −1 4 1
2 bb= = .
0 1 3 3
!
    1 0 1 −2 2
3 Cb = 2 1 6 −2 5 − 2 1
0 1 2 1 2
 
b = 0 0 2 1 −1 .
C

S. Kerdjoudj Linear programming 53/62

Canonical form for a basis of a linear programming Example

J1 = {1, 2} and J1 = {3, 4, 5}.

!
J1 1 1
A = ⇒ det(AJ1 ) = 1 6= 0.
0 1
Hence J1 is a basis with x3 = 0, x4 = 0, x5 = 0.
! ! !
b= 1 −1 1 1 3 −1 4 1 0 1 −2 2
1 A =
0 1 0 1 2 1 2 0 1 2 1 2
! ! !
1 −1 4 1
2 bb= = .
0 1 3 3
!
    1 0 1 −2 2
3 Cb = 2 1 6 −2 5 − 2 1
0 1 2 1 2
 
b = 0 0 2 1 −1 .
C
!
  1
4 α = 2 1 = 5.
3
S. Kerdjoudj Linear programming 53/62
Canonical form for a basis of a linear programming Example

Therefore the canonical form for a basis J1 = {1, 2} of (P ) is



 max(Z) = +2x3 +x4 −x5 +5


 x1 +x3 −2x4 +2x5 = 1
(P C)

 x2 +2x3 +x4 +2x5 = 3



x1 , x2 , x3 , x4 , x5 ≥0

 t  t
X = x1 x2 x3 x4 x5 = 1 3 0 0 0 is the basic solution
associated with J1 , with Z(X) = 5.

S. Kerdjoudj Linear programming 54/62

Canonical form for a basis of a linear programming Example

Canonical Form for a basis Without Computing the Inverse)

J1 = {1, 2} and J1 = {3, 4, 5}. Write
! !
L1 1 1 3 −1 4 4 L1 − L2 1 0 1 −2 2 1
∼
L2 0 1 2 1 2 3 L1 0 1 2 1 2 3

Perform row reduction on A to get a leading one in the second column,

as shown above. The row-reduced matrix and augmented vector form
your new constraints :

( (
x1 +x3 −2x4 +2x5 = 1 x1 = 1 − x3 + 2x4 − 2x5
⇒
+x2 +2x3 +x4 +2x5 = 3 x2 = 3 − 2x3 − x4 − 2x5

Substitute x1 and x2 into the objective function :

max(Z) = 2x1 + x2 + 6x3 − 2x4 + 5x5 = 5 + 2x3 + x4 − x5

S. Kerdjoudj Linear programming 55/62

Canonical form for a basis of a linear programming Example

Hence the canonical form for the basis J1 = {1, 2} of (P ) is



 max(Z) = +2x3 +x4 −x5 +5


 x1 +x3 −2x4 +2x5 =1
(P C)

 x2 +2x3 +x4 +2x5 =3



x1 , x2 , x3 , x4 , x5 ≥0

S. Kerdjoudj Linear programming 56/62

Canonical form for a basis of a linear programming Example

J2 = {1, 4} and J2 = {2, 3, 5}.

!
1 −1
AJ1 = ⇒ det(AJ2 ) = 1 6= 0.
0 1

Hence J2 is a basis with x2 = 0, x3 = 0, x5 = 0. Then

! !
L1 1 1 3 −1 4 4 L1 + L2 1 2 5 0 6 7
∼
L2 0 1 2 1 2 3 L1 0 1 2 1 2 3

Therefore
( (
x1 +2x2 +5x3 +6x5 = 7 x1 = 7 − 2x2 − 5x3 − 6x5
⇒
+x2 +2x3 +x4 +2x5 = 3 x4 = 3 − x2 − 2x3 − 2x5

Substitue x1 and x4 in the objective function

max(Z) = 2x1 + x2 + 6x3 − 2x4 + 5x5 = 8 − x2 − 3x5

S. Kerdjoudj Linear programming 57/62

Canonical form for a basis of a linear programming Example

Thus, the canonical form for the basis J2 = {1, 4} of (P ) is



 max(Z) = −x2 −3x5 +8


 x1 +2x2 +5x3 +6x5 = 7
(P C)

 x2 +2x3 +x4 +2x5 = 3



x1 , x2 , x3 , x4 , x5 ≥0

 t  t
X = x1 x2 x3 x4 x5 = 7 0 0 3 0 is the basic feasible
solution associated with J1 with Z(X) = 8

S. Kerdjoudj Linear programming 58/62

 Optimality Criterion

Fundamental Theorem of Linear Programming

Let (P ) be a linear program written in standard form.
1 If (P ) has a feasible solution, then it has a basic feasible solution.
2 If (P ) has an optimal solution, then it has an optimal basic
solution.

S. Kerdjoudj Linear programming 59/62

 Optimality Criterion

Theorem – Optimality Criterion – Maximization Problem



 max(Z) = CX

Let the linear program (P ) s.t. AX = b .


 X≥0
If the reduced cost vector corresponding to a feasible basis J of (P ) is
non-positive (i.e., negative or zero), then the basic feasible solution
associated with the basis J is optimal.

Theorem – Optimality Criterion – Minimization Problem



 min(Z) = CX

Let the linear program (P ) s.t. AX = b .


 X≥0
If the reduced cost vector corresponding to a feasible basis J of (P ) is
non-negative (i.e., positive or zero), then the basic feasible solution
associated with the basis J is optimal.
S. Kerdjoudj Linear programming 60/62
 Optimality Criterion

Proof of the Theorem – Optimality Criterion

Let (P ) be an LP written in canonical form for the basis J :
  

 max(Z) − πb = C J − πAJ X

 J
J

−1 J
−1
(P C) s.t. XJ + A A XJ = AJ b



 XJ , XJ ≥ 0

Let X ∗ be a BFS of (P ) associated with the basis J. Then, Z(X ∗ ) = πb.

Let X be any feasible solution of (P ). Then we have :
   
Z(X) = πb + C J − πAJ XJ ⇒ Z(X) = Z(X ∗ ) + C J − πAJ XJ
 
⇒ Z(X) − Z(X ∗ ) = C J − πAJ XJ

If C J − πAJ ≤ 0, then : Z(X) − Z(X ∗ ) ≤ 0 ⇒ Z(X) ≤ Z(X ∗ )

S. Kerdjoudj Linear programming 61/62

 Optimality Criterion

Example
In the previous example


 max(Z) = 2x1 +x2 +6x3 −2x4 + x5


 x1 +x2 +3x3 − x4 +4x5 = 4
(P )

 x2 +2x3 + x4 +2x5 = 3



x1 , x2 , x3 , x4 , x5 ≥0

1 The basic feasible solution corresponding to J1= {1, 2} is not 

optimal, because the reduced cost vector Cb = 0 0 2 1 −1 is
not non-positive.
2 The basic feasible solution corresponding
 to J2 = {1, 4} is
 optimal,
because the reduced cost vector C b = 0 −1 0 0 −3 ≤ 0.
 t
Hence, X ∗ = 7 0 0 3 0 and Z ∗ = 8.
S. Kerdjoudj Linear programming 62/62