1

Let $P$ be a polyhedron in $[0,1]^n$ defined by the constraints $Ax \leq b$ for $A \in \mathbb{R}^{m \times n}$, $x \in \mathbb{R}^n$, and $b \in \mathbb{R}^m$.

In the solutions of an exercise, the following is mentioned:

"Since the first $n$ constraints are linearly independent, they correspond to a basic solution of the system which, a priori, may be feasible or infeasible. This solution is obtained by replacing inequalities with equalities and computing the unique solution of this linear system."

So I am quite confused about this:

  1. Why does "linear independent constraints" imply that "basic solution"?

  2. Is a basic solution not always feasible?

glS
  • 6,818
user136457
  • 2,560
  • 1
  • 22
  • 41

1 Answers1

2

1) Linearly independant constraints define linearly independant hyperplanes at equality ($Ax=b$ for the lines concerned), the intersection of which is a point (or a vector, depending on your way of looking at this).

2) You have no guarantee that this point will satisfy all the other constraints.

Vincent
  • 2,318