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, 04: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, 07: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 :

$\displaystyle

Ob( \lambda \bold{x} + (1-\lambda)\bold{y})=\lambda Ob(\bold{x}) + (1-\lambda) Ob(\bold{y})

$

Then, if $\displaystyle \lambda \in [0,1]$ , and $\displaystyle \bold{x}$ and $\displaystyle \bold{y}$ are points where the objective attains its optimum value, $\displaystyle Ob( \bold{x})=Ob( \bold{y}) $ then $\displaystyle \bold{z}=\lambda \bold{x} + (1-\lambda)\bold{y})$ is feasible and:

$\displaystyle

Ob( \bold{z})=\lambda Ob(\bold{x}) + (1-\lambda) Ob(\bold{y})=Ob( \bold{x})

$

RonL - Jul 13th 2008, 08: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)