0
$\begingroup$

Consider the following linear program: \begin{equation} \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} \end{equation} Let's reduce it to standard form: \begin{equation} \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} \end{equation} 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)?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brian Borchers Jul 9 at 12:10
  • $\begingroup$ 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? $\endgroup$ – Mark87 Jul 9 at 12:27
  • $\begingroup$ 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. $\endgroup$ – callculus Jul 9 at 12:35
  • $\begingroup$ @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? $\endgroup$ – Mark87 Jul 9 at 12:41
  • $\begingroup$ @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. $\endgroup$ – callculus Jul 9 at 12:47
0
$\begingroup$

No. Definition of basic feasible solution (b.f.s.) says if in a basic solution all basic variables are non-negative then that basic solution is called b.f.s. In the standard form, one more constraint is introduced hence b.f.s. of standard form will not be the same as the b.f.s. of non-standard problem. As the dimension of the basis matrix change in the standard form.

|cite|improve this answer
$\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.