# Feasible solution

1. Mar 12, 2007

### dopey9

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. Mar 13, 2007

### HallsofIvy

Staff Emeritus
Think about the definition of "feasible solution" and show that any convex linear combination satisfies it.

3. Jan 16, 2008

Let $$v = \alpha_1 x_1 + \alpha_2 x_2 + \cdots$$, where $$\alpha_i \geq 0, \forall i$$ are real numbers in which $$\alpha_1 + \alpha_2 + \cdots = 1$$.

Then
$$\alpha_1 A x_1 + \alpha_2 A x_2 + \cdots \leq \alpha_1 b + \alpha_2 b + \cdots$$.

Hence
$$Av \leq b$$.

Note also that $$v \geq 0$$.

Last edited: Jan 16, 2008