Results 1 to 3 of 3

Math Help - Linear Programming Problem

  1. #1
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by squarerootof2 View Post
    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 :

     <br />
Ob( \lambda \bold{x} + (1-\lambda)\bold{y})=\lambda Ob(\bold{x}) + (1-\lambda) Ob(\bold{y})<br />

    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:

     <br />
Ob( \bold{z})=\lambda Ob(\bold{x}) + (1-\lambda) Ob(\bold{y})=Ob( \bold{x}) <br />

    RonL
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2008
    From
    Seoul, South Korea
    Posts
    128
    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)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: August 16th 2011, 06:10 PM
  2. Linear Programming Problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 22nd 2010, 12:41 PM
  3. Need help with linear programming problem
    Posted in the Advanced Applied Math Forum
    Replies: 1
    Last Post: August 25th 2010, 09:43 PM
  4. Linear Programming Problem again
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: June 3rd 2009, 04:39 PM
  5. Linear Programming-Need help with one problem
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: November 17th 2007, 04:44 AM

Search Tags


/mathhelpforum @mathhelpforum