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
    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