1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Feasible solution

  1. Mar 12, 2007 #1
    Let x1, . . . , xk be feasible solutions of the linear programming problem:

    Maximize z = (c^t)*x subject to Ax < = b and x >= 0,
    so for i= 1, . . . , k, Axi <=b and xi >=0,

    Let v be any convex linear combination of x1, . . . , xk.

    i want to show that v is also a feasible solution of the problem..does anyone know how to show this
     
  2. jcsd
  3. Mar 13, 2007 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Think about the definition of "feasible solution" and show that any convex linear combination satisfies it.
     
  4. Jan 16, 2008 #3
    Let [tex]v = \alpha_1 x_1 + \alpha_2 x_2 + \cdots [/tex], where [tex]\alpha_i \geq 0, \forall i[/tex] are real numbers in which [tex]\alpha_1 + \alpha_2 + \cdots = 1[/tex].

    Then
    [tex]\alpha_1 A x_1 + \alpha_2 A x_2 + \cdots \leq \alpha_1 b + \alpha_2 b + \cdots[/tex].

    Hence
    [tex]Av \leq b[/tex].

    Note also that [tex]v \geq 0[/tex].
     
    Last edited: Jan 16, 2008
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Feasible solution
  1. Forbidden Solution (Replies: 23)

  2. Solution to a system (Replies: 4)

  3. Solution space (Replies: 5)

Loading...