# Linear program with bounded feasiblity set

Hey guys I've been stuck on this problem and was wondering if anyone could help.

Consider a linear programming problem in standard form with a bounded feasible set. Furthermore, suppose that we know the value of a scalar U such that any feasible solution satisfies $x_i$ $\leq$ U, for all i. Show that the problem can be transformed into an equivalent one that contains the constraint $\sum_{i=1}^n x_i$ = 1

The solution should of the form : min $c^T$x s.t. Ax=b ,$e^Tx$=1, x$\geq$0

• Equal to 1? Or less-than-or-equal-to 1? – tabstop Feb 21 '14 at 4:27
• It must be equal to – user115573 Feb 21 '14 at 4:28

$x_i \leq U \implies \sum x_i \leq nU \implies \sum x_i + x_{n+1} = nU$ where $x_{n+1}\geq0$ is a new slack variable.
Then define $\tilde{x_i}=x_i/nU$ for $i=1\dots n+1$ and you are done. I do not think you can solve this without introducing a new variable.