0

In linear programming I ve seen two versions of the fundamental theorem, and I wonder whether there is a correspondance between them, so that given one version you don't have to prove the other one. The two versions I am talking about can be found in the links:

  1. http://www.math.udel.edu/~angell/basicth.pdf (theorem 1.4)
  2. https://en.wikipedia.org/wiki/Fundamental_theorem_of_linear_programming

Also is it really necessary for the matrix to be full row rank? How is this assumption used in each proof?

asdf
  • 323
  • 1
  • 10

1 Answers1

0

Yes they are two different versions of the same theorem. The first one is the so called algebraic version, because it refers to the feasible basic solutions of a system of $m$ equations. The second one is the geometric version, because it refers to the extreme points of a convex set. You do not need to prove the counterpart, given one version, because the following holds

Theorem: $x\in \mathbb{R}^n$ is an extrem point of $P=\{x \in \mathbb{R}^n \ |\ Ax=b, x\geq 0\}$ if an only if $x$ is a basic solution of $Ax=b$ and $x\geq 0$.

Note that the Wikipedia geometric version is stated for bounded polyhedra (polytopes), but it still holds for unbounded polyhedra.

As far as it concerns the rank of matrix $A$, the full-rank hypothesis is used in the case 1 of the proof of the algebraic version (following the link in your question)

  • I can't see how is this theorem you stated usefull. For example if I want to prove the theorem in version 1 given the version 2, how to I use the assumption in 1 that there is a feasible solution (not necessarily basic) ? – asdf Dec 21 '16 at 10:12
  • The assumption in 1 that there is a feasible solution corresponds in 2 to state that the polytope is not empty. – Marcello Sammarra Dec 21 '16 at 18:25