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$
  • $\begingroup$ Equal to 1? Or less-than-or-equal-to 1? $\endgroup$ – tabstop Feb 21 '14 at 4:27
  • $\begingroup$ It must be equal to $\endgroup$ – user115573 Feb 21 '14 at 4:28
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.