Basic Feasible Solutions

Question 1

Theorem. EROs don’t change the solution of a system of linear equations

Answer 1

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

Question 2

Theorem. Existence of optimal extreme point

Answer 2

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

Question 3

[B,N]=

Answer 3

A

Question 4

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?

Answer 4

xB = B-¹b, xN=0

Question 5

dimension of B

Answer 5

mxm invertible

Question 6

dimension of N

Answer 6

mx(n-m)

Question 7

xB =

Answer 7

B-¹b

Question 8

xN =

Answer 8

0

Question 9

How to find the basic feasible solution for the LP problem min cᵀx s.t. Ax=b x≥0

Answer 9

1. re-arrange columns of A so that the first m columns are L.I
2. Define [B,N]
3. Find the inverse of B
4. Calculate B-¹b. for each possible B.
5. If any of the xBs has a negative component discard this xB. This is how many BFS there are. (each xB is one)

Question 10

The number of BFS is bounded by the number of ways of extracting m columns from A i.e. there are at most … BFS

Answer 10

n choose m

n!/(m!(n-m)!)

Question 11

Theorem BFS and extreme point

Answer 11

Given an LP problem then a point is a BFS iff its an extreme point

Question 12

Corollary. number of extreme points.

Answer 12

Given a polyhedron there are only a finite number of extreme points

Question 13

Fundamental Theorem of linear Programming

Answer 13

(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

Question 14

How to construct a BFS from a feasible point (from proof of FTLP)

Answer 14

1. find the rank of A
2. find p (the number of strictly positive co-ordinates in x
3. if p=m take B = [a1,…,ap] and x is a BFS. then stop.
4. solve the system Ay=0 and pick one solution y=(b1,…,bp)
5. calculate Ɛ=min{xᵢ/yᵢ | i=1,…,p yᵢ>0}
6. calculate the new feasible entries x*ᵢ = xᵢ-yᵢ
7. if an element of x* is 0, you can remove the corresponding column from A
8. repeat until all columns of A and L.I i.e. p=m
9. xB = B-¹b where B is the matrix we found with the method

Question 15

How to find the rank of A

Answer 15

1. reduce to echelon form
2. count non-zero rows
   (i. e. no. L.I rows)