Let P be a polyhedron in [ 0 , 1 ] n defined by the constraints A x ≤ b for A ∈ R m × n , x ∈ R n , and b ∈ 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?

Question

Let   P be a polyhedron in   [  0  ,  1      ]    n   defined by the constraints  A  x  ≤  b for   A  ∈        R          m      ×      n      ,   x  ∈        R    n  , and   b  ∈        R    m  .In the solutions of an exercise, the following is mentioned:&quot;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.&quot;So I am quite confused about this:1) Why does &quot;linear independent constraints&quot; imply that &quot;basic solution&quot;?2) Is a basic solution not always feasible?

sag2y8s · Accepted Answer

1) Linearly independant constraints define linearly independant hyperplanes at equality (  A  x  =  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.

Let P be a polyhedron in [ 0 , 1 ] n </msup> defined by the co

Answered question

Answer & Explanation

New Questions in Algebra I