3
$\begingroup$

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not having any redundancy in the constraints.

However, will $A$ not being of full row rank cause any problems in the application of the simplex algorithm? For example, if there is a degenerate basic feasible point that has not been preprocessed away, then the simplex algorithm (if unmodified) may go into an infinite loop and never terminate. How about when $A$ is not of full row rank?

$\endgroup$
0
$\begingroup$

Consider the following polyhedron:

$P = \{x\in\mathbb{R}^2| Ax = b, x\ge0 \}$, where $A = \left[\matrix{1&1 \\ 2&2}\right]$ and $b = \left[\matrix{1 \\ 2} \right]$.

Let the function we want to minimize be $c^Tx$, where $c = \left[\matrix{1 \\ 0}\right]$.

It is clear that $x = \left[\matrix{0 \\ 1}\right]$ is the only optimal solution to the problem. However this $x$ is not a basic feasible solution and, since the simplex method iterates over basic feasible solutions, the simplex method wouldn't succeed in finding the answer to the problem.

Further observations: Actually, the simplex method does not make sense if the rank of A does not equal the number of constrictions ($m$), because the method relies heavily on that hypothesis. Also note that the definition of basic feasible solution (http://www.math.chalmers.se/Math/Grundutb/CTH/tma947/1617/lectures/lecture9.pdf, page 4/30) is given in a standard polyhedron with rank $A = m$. Otherwise (if rank $A < m$), the definition is useless, for there is no subset of $m$ linearly independent columns of A, and therefore there is no basic feasible solution.

$\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.