Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 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.

share|improve this answer
    
...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". –  hhh Aug 29 '12 at 7:00
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. –  shoda Aug 29 '12 at 14:51
    
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. –  hhh Aug 29 '12 at 15:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.