Given the following constraints x 1 + x 2 + x 3 + x 4 ≤ 10 x 1 − x 2 ≤ 0 x 1 − x 3 ≤ 2 x 1 + x 2 − x 4 ≤ 3 x i ∈ R ≥ 0 I want to find all basic feasible solutions. They are the extreme points of the convex polyhedra induced by these constraints. However, to solve these system we introduce as many slack variables as we have inequalities. This leads us to x 1 + x 2 + x 3 + x 4 + s 1 = 10 x 1 − x 2 + s 2 = 0 x 1 − x 3 + s 3 = 2 x 1 + x 2 − x 4 + s 4 = 3 x ^ i ∈ R ≥ 0 Now, a basic feasible solution would be x ^ ≡ ( x 1 , x 2 , x 3 , x 4 | s 1 , s 2 s 3 , s 4 ) = ( 0 , 0 , 0 , 0 | 10 , 0 , 2 , 3 ) T However,1. How do I find all basic feasible solutions from this starting basic feasible solution?2. These basic feasible solutions are basic feasible solutions for the modified system. How do I get basic feasible solutions for the original problem?

Question

Given the following constraints                              x          1                                    +                              x          2                                    +                              x          3                                    +                              x          4                                    ≤        10                                      x          1                                    −                              x          2                                                            ≤        0                                      x          1                                                −                              x          3                                                ≤        2                                      x          1                                    +                              x          2                                                −                              x          4                                    ≤        3                                      x          i                                                                        ∈                          R                      ≥            0                              I want to find all basic feasible solutions. They are the extreme points of the convex polyhedra induced by these constraints. However, to solve these system we introduce as many slack variables as we have inequalities. This leads us to                              x          1                                    +                              x          2                                    +                              x          3                                    +                              x          4                                    +                              s          1                                                                      =        10                                      x          1                                    −                              x          2                                                                      +                              s          2                                                    =        0                                      x          1                                                −                              x          3                                                                      +                              s          3                                        =        2                                      x          1                                    +                              x          2                                                −                              x          4                                                                      +                              s          4                            =        3                                                          x            ^                    i                                                                                                                      ∈                          R                      ≥            0                              Now, a basic feasible solution would be      x    ^    ≡  (      x    1    ,      x    2    ,      x    3    ,      x    4      |        s    1    ,      s    2        s    3    ,      s    4    )  =  (  0  ,  0  ,  0  ,  0    |    10  ,  0  ,  2  ,  3      )    T  However,1. How do I find all basic feasible solutions from this starting basic feasible solution?2. These basic feasible solutions are basic feasible solutions for the modified system. How do I get basic feasible solutions for the original problem?

Johnathan Morse · Accepted Answer

1. With real variables you probably have an infinite number of basic feasible solutions.2. The solution you show is a basic feasible solution for the original problem, with all variables equal to zero. To get a feasible solution for your original problem, with nonzero problem variables: Do the Simplex phase II for some times. In the first step you take in a problem variable as a basic variable. Then after another the other variables. Probably your optimal solution has some zero problem variables.Why do you want to have all basic feasible solutions?

rjawbreakerca · Accepted Answer

The basic feasible solutions of what you call &quot;original problem&quot; are exactly the same as the basic feasible solutions of the modified system: by adding slack variables you do not change the solution set; you just embed it in a higher dimensional space.The problem of findig all basic feasible solutions of a polyhedron is called Vertex Enumeration Problem. In order to find all vertices, you may first obtain an arbitrary one, call it your root solution, and then build a solution tree by searching for its neighbors, its neighbors&#039; neighbors, and so on. Each time you obtain a neighboring solution, you will have to check whether it is one that you already obtained; in which case you abandon the corresponding branch.

Given the following constraints <mtable columnalign="right left" rowspacing="3pt" columnspacing=

Answered question

Answer & Explanation

New Questions in Algebra I