# Feasible solution

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

HallsofIvy
Homework Helper
Think about the definition of "feasible solution" and show that any convex linear combination satisfies it.

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: