Problem:
Linear Programming : Adjacency of Basic Feasible Solution and Hyperplanes
Can anyone finish up this proof by continuing my preliminery work?
Assume A ∈ Rmxn b€Rm, with rank (A) = m are given. Two different basic feasible solutions u, v of Ax=b, x≥0 are said to be adjacent if they correspond to two bases that have exactly m-1 elements in common.
Suppose u, v are two different basic feasible solutions of Ax=b,x≥0. Prove that u and v are adjacent if and only if there exists a supporting hyperplane H of P:={x:Ax=b,x≥0.} such that H∩P = conv{u,v}
Let Z = λu+(1-λ)v,satisfying AZ = b
We can rewrite as aiT Z = bi
→ Σ ajT Z = Σjbj
→ Σ a [λu+(1-λ)v]= Σbj
→ λΣ ajT u +(1-λ)Σ ajT v = Σ bj
→ Σ ajv+λΣaj(u-v) = Σ bj
Since Σ aj v = Σbj (u,v are bfs of AX=b,x≥0)
Σaj(u-v)=0 Thus u and v are in the same supporting hyperplane H.