# Basic feasible solution: problem in non standard form

Consider the following linear program: $$$$\begin{matrix} \displaystyle \min_{x_i} & \sum_{i=1}^{m} {c_i^Tx_i} \\ \textrm{s.t.} & \sum_{i=1}^{m} A_i x_i = b \\ & x_i \geq 0 & i=1,..,m \\ & x_i\leq d_i & i=1,...,m \\ \end{matrix}$$$$ Let's reduce it to standard form: $$$$\begin{matrix} \displaystyle \min_{x_i} & \sum_{i=1}^{m} {c_i^Tx_i} \\ \textrm{s.t.} & \sum_{i=1}^{m} A_i x_i = b \\ & x_i \geq 0 & i=1,..,m \\ & s_i \geq 0 & i=1,...,m \\ & x_i+s_i=d_i & i=1,...,m \\ \end{matrix}$$$$ Where $$s_i$$, $$i=1,...,m$$ are the added slack variables.

Is it true that a basic feasible solution for the problem in standard form is a basic feasible solution for the problem in non standard form (just ignoring the values of the slack variables)?

• Note that you've increased the number of constraints in the standard form version of the problem, so the number of variables in a basis will increase as well. – Brian Borchers Jul 9 at 12:10
• Yes, for the standard form problem the basis should include all $x_i$ and $s_i$ that are different from zero. But if we ignore the $s_i$ and consider only the portion of the basic solution that includes the $x_i$, can we say that that portion is a basic feasible solution for the non-standard form problem? – Mark87 Jul 9 at 12:27
• Here the $s_i$ variables aren´t slack variables. You can define a new variable. $y_i=d_i−x_i$. Slack variables come into play when you convert constraints from inequalities into equations. – callculus Jul 9 at 12:35
• @callculus The $s_i$ were added in order to transform the inequality constraints $x_i \leq d_i$ into equality ones, is it incorrect to call them slack variables? – Mark87 Jul 9 at 12:41
• @Mark87 When you introduce $y_i=d_i-x_i$ you get $y_i\geq 0$. There is no need for an equality if you want that all (decision) variables $x_i,y_i$ are non-negative. – callculus Jul 9 at 12:47