Feasible solution

  • Thread starter dopey9
  • Start date
  • #1
32
0

Main Question or Discussion Point

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
 

Answers and Replies

  • #2
HallsofIvy
Science Advisor
Homework Helper
41,806
932
Think about the definition of "feasible solution" and show that any convex linear combination satisfies it.
 
  • #3
33
0
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:
Top