Explore BrainMass
Share

# Linear Programming : Adjacency of Basic Feasible Solution and Hyperplanes

Can anyone finish up this proof by continuing my preliminery work? I started but can't finish this. I know starting by adding up the point z is correct way, but just can't continue to show if and only if.

(See attached file for full problem description)

---
Assume , , with rank (A) = m are given. Two different basic feasible solutions u, v of Ax=b, 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, . Prove that u and v are adjacent if and only if there exists a supporting hyperplane H of P:={x:Ax=b, } such that

Let z = , satisfying Az=b
We can rewrite as
&#61664;
&#61664;
&#61664;
&#61664;

Since , (u, v are bfs of Ax=b, )
Thus u and v are in the same supporting hyperplane H.
---

#### Solution Summary

Adjacency of Basic Feasible Solution and Hyperplanes are investigated. The solution is detailed and well presented. The response received a rating of "5/5" from the student who originally posted the question.

\$2.19