Basic feasible solution: problem in non standard form

439 Views Asked by At

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)?

1

There are 1 best solutions below

0
On

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.