1

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

user115573
  • 31

1 Answers1

1

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

Stefano
  • 386