# Linear Programming Problem

• Jul 12th 2008, 05:36 PM
squarerootof2
Linear 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 AM
CaptainBlack
Quote:

Originally Posted by squarerootof2
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.

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 :

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

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

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

RonL
• Jul 13th 2008, 09:40 PM
squarerootof2
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)