Adjacency of basic feasible solution and hyperplanes


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.

 

Solution Preview :

Prepared by a verified Expert
Mathematics: Adjacency of basic feasible solution and hyperplanes
Reference No:- TGS01920482

Now Priced at $20 (50% Discount)

Recommended (90%)

Rated (4.3/5)