Share
Explore BrainMass

Proof of Vertex, Extreme Point, Basic Feasible Solution

Can you please let me know how to approach those proof questions.

Consider the polyhedron P = {x  Rn : xi > 0 for all i = 1 ... n}.

a)Prove that the origin (i.e. the vector of all 0's) is a vertex of P, according to the definition of a vertex (i.e. do not rely on the fact that vertex = extreme point = basic feasible solution).
b) Prove that the origin is an extreme point of P, according to the definition of an extreme point (i.e. do not rely on the fact that vertex = extreme point = basic feasible solution).
c) Prove that the origin is a basic feasible solution of P, according to the definition of a basic feasible solution (i.e. do not rely on the fact that vertex = extreme point = basic feasible solution).
d)Prove that the origin is the only "corner" of P. [You may show it is the only vertex, extreme point, or basic feasible solution.]
e) Identify all cost vectors c for which the origin is uniquely optimal (i.e. there is no other optimal solution).
f) Identify a cost vector c for which the origin is optimal but not uniquely so (i.e. there are other optimal solutions).
g) Identify a cost vector c for which the origin is not an optimal solution.

See attached file for full problem description with complete equations.

Attachments

Solution Preview

Please see the attached file.
..........................

Answers:

(a)
Definition:
Vertex of an n-dimensional polyhedron is a point at which faces meet.
The faces are planes x_i = 0, I = 1,...,n. All these faces meet at the origin
Therefore the origin is a vertex.

(b)
Definition:
Extreme point is a point that lies on the end of any straight line segment contained in the polygon and containing this point
Any segment containing the origin will have the form ...

$2.19