1
$\begingroup$

Why do the decision variables in a linear optimization problem have to be non-negative? I mean it makes sense in certain scenarios (when you are talking about how many pairs of two shoes to make for maximum profit) as you can't make negative shoes but why does this have to be the case isn't there some situation where one of the variables could be negative?

$\endgroup$
1
$\begingroup$

Yes, you are right. A variable can be negative. If at least one of the variable is negative (0 inclusive), then you can transform the problem to a problem with only non-negative variables. Therefore you still have the standard form.

Numerical example:

$\texttt{max} \ \ 2x_1-x_2$

$x_1-2x_2\leq 5$

$3x_1-x_2\leq 7$

$x_1\geq 0,\ x_2\leq 0$

Now you define $x_2=-x_2'$

The problem becomes

$\texttt{max} \ \ 2x_1+x_2'$

$x_1+2x_2'\leq 5$

$3x_1+x_2'\leq 7$

$x_1,\ x_2'\geq 0$

A transformation can be also done, if a variable is not restricted. Suppose that y is not restricted, then you define $y=y'-y''$, where $y', \ y'' \geq 0$

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