0
$\begingroup$

A simplex is a polytope of n+1 extreme points in $R^n$.

In linear programming, the algorithm of the simplex method works by iteratively constructing simplexes. Each iteration involves both an entering variable, which has the largest reduced cost, and an exiting variable, which is the variable which must leave in order to allow all of the constraints to be satisfied, when the entering variable enters.

Eventually we find a simplex which corresponds to the optimal solution. Each simplex corresponds to a basic feasible solution, with each extreme point/vertex of the simplex corresponding to a basic variable.

(this implies that all simplexes have n+1 extreme points). My question is - how do we know that the solution will have exactly n+1 basic variables?

Edits this is the resource i have been using: https://www.youtube.com/watch?v=Ci1vBGn9yRc

$\endgroup$
1
$\begingroup$

I'm not sure your understanding of the simplex method is correct. it iterates over the vertexs/extreme points of a given polytope (given by the constraints). One of those extreme points is the maximum/minimum because the polytope(like all polytopes) is convex.

A simplex does not have to have a certain number of extreme points. although it will have extreme points for all intersection of constraints that are feasible and only those, it however can be difficult to see which intersections will be feasible .

$\endgroup$
  • $\begingroup$ This resource is making me think it is a bunch of simplexes: youtube.com/watch?v=Ci1vBGn9yRc $\endgroup$ – Hunle Jun 1 '17 at 13:57
  • 1
    $\begingroup$ @Hunle Ah, now I see, I had not heard this explanantion before. This is indeed correct. I was (slightly) wrong with terminology(I called a polytope which is not a simplex a simplex). This way of thinking about it is somewhat more complex than how I describe it. The simplex that that professor is talking about is the space spanned by a basic solution, it has n vertices by assign. It has to have them because the solution always has n constraints and each constarint corresponds with a basic variable. The space in which it exists has dimension n-1 (so it is equivalent to your statement) $\endgroup$ – zen Jun 1 '17 at 17:13
  • 1
    $\begingroup$ @Hunle continuation: what is n is ofcourse not really important but what you should understand is that the number of basic variables is equal to the number of restrictions. so equal to the dimension of a column of the restriction matrix A. Note that slack variables can be basic variables, therefore the simplex alwys has the desired number of points. This is neccessary because we only look at the outside of the polytope of the feasible region and so all inequaliteis must hold. Therefore for each constriant there needs to be a basic variable to balance the equation. $\endgroup$ – zen Jun 1 '17 at 17:20
  • 1
    $\begingroup$ @Hunle I have slightly changed my answer I can include what I said in the comments as well. I do not like this interpretation though. It gives more insight in why the simplex method works algebraically nand how to derive it. But it is much harder to see why it works intuitively. $\endgroup$ – zen Jun 1 '17 at 17:23
  • $\begingroup$ OKay, thank you @zen. Would you be able to give an explanation for how it works intuitively? There is a bounty out :) $\endgroup$ – Hunle Jun 4 '17 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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