0
$\begingroup$

Related chat here, reading the Bertsimas book now on pages 50-51. By the way, I am gathering Linear-Programming -related studying material here, welcome to read a book and have coffee :)

I cannot understand the point on p51 in the Bertsimas -book. You have a point $D=(0,0,0)$. Suppose you replace $x_1+x_2+x_3=1$ with $x_1+x_2+x_3\leq 1$ and $x_1+x_2+x_3\geq 1$. Now all of a sudden D transformed from non-basic solution into basic solution, why? $x_1+x_2+x_3\geq 1$ is not active with $(0,0,0)$ but the other is so the new two constraints are not active with logical AND but they are active with logical OR. But the LP -book uses the word AND instead of OR so dizzied!

Related book parts with pictures

CRUX-POINT: why this kind of distinction between the terms "basic" solution and "basic feasible" solution?

shoda explained that some Simplex methods exploits the basic -solutions in the intermediate steps. I think this is the crux point, it is the reason why we have this kind of odd distinction. Please, elaborate on this further -- which Simplex -methods have intermediates with basic solutions, not feasible basic solutions. Compare and contrast, thank you.

1 Answers 1

1

The reason Bertsimas uses AND is that the region $\{(x_1,x_2,x_3) : x_1+x_2+x_3=1\}$ is equal to the region $\{(x_1,x_2,x_3) : x_1+x_2+x_3 \leq 1 \text{ and } x_1 + x_2 + x_3 \geq 1\}$. Part of the reason this is confusing is that the definition of a basic solution depends on whether the constraints are expressed as equality constraints or inequality constraints. A solution $\mathbf{x^*}$ is basic if all equality constraints are satisfied by $\mathbf{x^*}$ and there are $n$ linearly independent inequalities that are satisfied by $\mathbf{x^*}$. Notice that a solution can be a basic solution and not feasible since not all the inequality constraints need to be satisfied for the solution to be considered a basic solution (read the definition carefully).

When we describe the region with the equality constraint, the point $(0,0,0)$ is not basic because it does not satisfy the equality constraint $x_1+x_2+x_3=1$. However, when we describe the region using the pair of inequalities instead of the equation then (1) there are no equality constraints to satisfy, (2) the inequalities $x_1>=0$, $x_2>=0$ and $x_1 + x_2 + x_3 \leq 1$ are all satisfied by $(0,0,0)$. These are 3 linearly independent inequalities satisfied by $(0,0,0)$; hence $(0,0,0)$ is a basic solution. Notice that $(0,0,0)$ is NOT feasible since it fails to satisfy $x_1 + x_2 + x_3 \geq 1$.

Hope this helps.

  • 0
    ...I see no sense with the definition of basic, it looks totally useless. Where is it needed? Why to make this kind of distiction between "basic" and "basic feasible"? Is the "basic" somehow referring to "basis".2012-08-29
  • 1
    There are variants of the simplex method that only require that you move between basic solutions during intermediate steps, that is, the intermediate solutions don't need to be basic feasible solutions. Clearly, the optimal solution (if it exists) needs to be feasible.2012-08-29
  • 0
    Could elaborate more on the variants of simplex methods because I think it is the crux point to understand why this kind of distinction first-hand is needed, thank you.2012-08-29