1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Equal to 1? Or less-than-or-equal-to 1? $\endgroup$
    – tabstop
    Feb 21, 2014 at 4:27
  • $\begingroup$ It must be equal to $\endgroup$
    – user115573
    Feb 21, 2014 at 4:28

1 Answer 1

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .