3
$\begingroup$

The artificial constraint method is used to find an intial basis to start executing the dual simplex algorithm to solve a linear programming programming problem (say we want to minimize $c^tx$). The method add the constraint $$\sum_{j=m+1}^{n}x_j\leq M$$ where the original problem constraints were $Ax=b$, being $A\in\mathfrak{M}_{m\times n}(\mathbb{R})$ with rank $m$ and $M$ is an ''arbitrarily large'' positive constant.

We suppose the the $m$ first columns of $A$ constitute a basis $B$ in which at least one reduced cost is strictly negative, where the definition of reduced cost for the $j$-th variable (induced by the basis $B$) is $\overline{c_j}:=c_B^t-B^{-1}a_j$, being $a_j$ the $j$-th column of $A$ and $c_B^t$ the sub-row vector of $c$ defined by the selection of coordinates of $c$ whose indexes correspond to the indexes in $B$.

Once the new problem is transformed to the standard formulation again, the simplex tableau looks like this (being $N$ the submatriz of $A$ obtained by substracting the columns of $B$). $$A'=\left(\begin{array}{c|c|c} 1 & 0 &1\\ \hline0 & I_m & B^{-1}N \end{array}\right) $$ notice that the two first columns by blocks constitute a basis $B'$ of $A'$.

The method sais that if we consider the basis $B^*=(B'\setminus a'_0)\cup a'_k$, being $a'_0$ the first column of $A'$ and $a'_k$ the column of $A'$ with the lowest reduced cost, we obtain a basis in wich every reduced cost is non negative, so we can apply the dual simplex method to solve the additionally restricted problem (this is easy to prove).

The problem is that, once the algorith finishes determining the optimal solution of the additionally restricted problem the following is said (and have no idea how to prove it)

  • If the last basis checked by the algorithm constains $a'_0$, then the original problem has an optimal solution, in fact, this solution is the one obtained by supressing the $0$-th coordinate of the additionally restricted optimal solution vector.
  • If the last basis does not contains $a'_0$, then two cases are distinguised. On one hand, if the value of the objective function ($c^tx$, which is the same for both problems) depends on $M$, then, the orginal problem is unbounded, otherwise, there are infinitly many optimal solutions.

My question is how to prove this two statements, for the first one I have tried saying that the feasible region of the restricted problem (for a large enought $M$) constains all the extreme points of the original feasible region (but I did not reach anything).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.