2

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?

Chris K
  • 21

1 Answers1

2

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$

callculus42
  • 30,550
  • I like your answer. But I am not sure if this really answers the question why decision variables in a linear programming problem have to be non-negative. Can you elaborate on that a little more? Why do we have to reformulate the problem at hand if there are negative independent variables? – Gilfoyle Mar 31 '21 at 06:44
  • A decision variable must not be non-negative. But if you apply the simplex algorithm decision variables have to be non-negative. – callculus42 Mar 31 '21 at 07:12
  • Why does the simplex algorithm not accept negative decision variables? – Gilfoyle Mar 31 '21 at 07:54
  • I don´t know. I just take it for granted. So you can ask your question as a new question here on MSE. – callculus42 Mar 31 '21 at 07:58