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