Linear ProgrammingLP Exercise 214 Let P be a bounded polyhed

Linear Programming(LP)

Exercise 2.14 Let P be a bounded polyhedron in R^n, let a be a vector in R^n, and let b be some scalar. We define Q = {x in P | a\'x = b}. Show that every extreme point of Q is either an extreme point of P or a convex combination of two adjacent extreme points of P.

Solution

Assume x is an extreme point in Q

if this point coincides with an extreme point in P

then , there won\'t be anything there

now, let\'s assume it is not an extreme point in P

Since, it is an extreme point in Q

this is a basic feasible solution

it means that n of the constraints are active in x

we have given one constraints

ax=b

other active constraints

n1 of those constraints that are associated with the polyhedron P

Two adjacent extreme points are two points that by definition have n1 constraints

Hence, x lies in the segment that lies in between those two extreme points...........ANswer