# Thread: Linear Programming Problem

1. ## 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.

2. 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 :

$\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

3. 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)

linear, problem, programming 