1

I am currently studying linear programming and came across a specific problem that involves substitution and variable conversion. Although I have consulted relevant resources, I am still a bit confused about a few aspects. I would greatly appreciate it if someone could help clarify the following questions:

The Use of Substitution: In a linear programming problem I encountered, the author suggests applying the substitution $x_1 = x_1^+ - x_1^-$ and performing conversions as explained on page 6 of the "Linear programming problems" slides. I'm curious about the purpose and benefits of this substitution. Why is it necessary or advantageous to use such a substitution in this context?

Application Limited to $x_1$: Another aspect that puzzles me is that the substitution $x_1 = x_1^+ - x_1^-$ is only applied to $x_1$, while leaving $x_2$ unchanged. I would like to understand why the substitution is limited to $x_1$ and not extended to $x_2$ as well. Are there specific reasons or mathematical considerations behind this choice?

Problem

$\begin{array}{ll}\min & 3 x_1-2 x_2 \\ \text { s.t. } & 2 x_1+5 x_2 \geq 10 \\ & 4 x_1+2 x_2=8 \\ & -2 \leq x_1 \leq 7 \\ & 3 \leq x_2 \leq 10\end{array}$

Solution

I don't manage to convert this to clear LaTex, therefore a screenshot enter image description here

Here , $x_1$ is substituted with $x_{1}^{+}$ & $x_{1}^{-}$ , though $x_2$ is not substituted. Why ?

Prem
  • 9,669
Tim
  • 684
  • 1
    It is the last line which gives the Clue [[ The Answer is Non-Negativity ]] $x_{1}^{+}$ & $x_{1}^{-}$ & $x_{2}$ should not be Negative. We can not make that claim about $x_{1}$ which has Positive & 0 & Negative Possibilities. With that Substitution , we can make that Claim ! – Prem May 18 '23 at 12:11
  • @prem Thank you, I think I understand it better now – Tim May 18 '23 at 12:35
  • 1
    It will be great to include (1) the Author (2) the web-link to the Slides : The Post will be more Complete with that ! – Prem May 19 '23 at 12:53

1 Answers1

2

Elaborating my Earlier Comment :

In general , we use Non-Negative variables in linear Programming.

(1) When given variable $A$ is Directly Non-Negative , we have the Non-Negativity Constraint $A \ge 0$.

(2) When given variable $B$ is Directly Non-Positive , we have the Constraint $B \le 0$ , where we introduce new variable $B^{-}=-B$ & we add the Non-Negativity Constraint $B^{-} \ge 0$.

(3) When given variable $C$ is having Positive & Negative range , we have the Constraint $-X \le C \le +Y$ where we introduce new variables $C^{+},C^{-}$ where we make $C=C^{+}-C^{-}$. We then add the Constraints $C^{+}-C^{-} \ge -X$ & $C^{+}-C^{-} \le +Y$. We can then add the Non-Negativity Constraints $C^{-} \ge 0$ & $C^{+} \ge 0$.

These Substitutions will all result in variables which are Non-Negative.
The Original variables & the Solutions may or may not be Non-Negative.

Prem
  • 9,669