Theorem. EROs don’t change the solution of a system of linear equations
If x is a solution of an LP problem. Then Ax=b iff A’x=b’ where (A’,b’) is obtained from (a,b) by a finite number of elementary row operations
Theorem. Existence of optimal extreme point
Assume that the feasible region is non-empty. Then,
- A finite optimal solution exists iff cᵀdʲ≥0 for all j
- if there exists an extreme direction such that cᵀdʲ<0 then the optimal objective value of the LP is unbounded
- If an optimal solution exists, then at least one extreme point is optimal
[B,N]=
A
Consider the system Ax=b x≥0 where m is mxn and b∈ℝᵐ where A has maximal rank. Let A=[B,N] where B is mxm invertible matrix and N is mx(n-m) matrix.
What is a basic solution of this system?
xB = B-¹b, xN=0
dimension of B
mxm invertible
dimension of N
mx(n-m)
xB =
B-¹b
xN =
0
How to find the basic feasible solution for the LP problem min cᵀx s.t. Ax=b x≥0
- re-arrange columns of A so that the first m columns are L.I
- Define [B,N]
- Find the inverse of B
- Calculate B-¹b. for each possible B.
- If any of the xBs has a negative component discard this xB. This is how many BFS there are. (each xB is one)
The number of BFS is bounded by the number of ways of extracting m columns from A i.e. there are at most … BFS
n choose m
n!/(m!(n-m)!)
Theorem BFS and extreme point
Given an LP problem then a point is a BFS iff its an extreme point
Corollary. number of extreme points.
Given a polyhedron there are only a finite number of extreme points
Fundamental Theorem of linear Programming
(i) if there is a feasible solution then there is a basic feasible solution
(ii) if there is an optimal solution for an LP, then there is a BFS that is optimal
How to construct a BFS from a feasible point (from proof of FTLP)
- find the rank of A
- find p (the number of strictly positive co-ordinates in x
- if p=m take B = [a1,…,ap] and x is a BFS. then stop.
- solve the system Ay=0 and pick one solution y=(b1,…,bp)
- calculate Ɛ=min{xᵢ/yᵢ | i=1,…,p yᵢ>0}
- calculate the new feasible entries x*ᵢ = xᵢ-yᵢ
- if an element of x* is 0, you can remove the corresponding column from A
- repeat until all columns of A and L.I i.e. p=m
- xB = B-¹b where B is the matrix we found with the method
How to find the rank of A
- reduce to echelon form
- count non-zero rows
(i. e. no. L.I rows)
