show that if the optimal value of the objective function of a linear programming problem is attained at several extreme points, then it is also attained at any convex combination of these extreme points.

Printable View

- Jul 12th 2008, 05:36 PMsquarerootof2Linear Programming Problem
show that if the optimal value of the objective function of a linear programming problem is attained at several extreme points, then it is also attained at any convex combination of these extreme points.

- Jul 13th 2008, 08:22 AMCaptainBlack

As the feasible region is a convex closed polytope the line segment between any two of the points where the objective attains its maximum is in the feasible region.

As the objective is linear :

Then, if , and and are points where the objective attains its optimum value, then is feasible and:

RonL - Jul 13th 2008, 09:40 PMsquarerootof2
so would the question here actually be pertaining to the case when the maximum is attained at two points instead of "several" points? and also, when you say Ob(λx+(1-λ)y) does this represent the arbitrary convex combination of two extreme pts? (i know this might be a stupid question)