Linear Programming Simplex Algorithm
https://www.jeremykun.com/2014/12/01/linear-programming-and-the-simplex-algorithm/
Linear Programming and the Simplex Algorithm
2014-12-01
None
<div><p>This article was ported from my old Wordpress blog <a href="https://jeremykun.wpcomstaging.com/2014/12/01/linear-programming-and-the-simplex-algorithm/">here,</a> If you see any issues with the rendering or layout, please <a href="mailto:mathintersectprogramming@gmail.com">send me an email</a>.</p><div><p>In <a href="https://www.jeremykun.com/2014/06/02/linear-programming-and-the-most-affordable-healthy-diet-part-1">the last post in this series</a> we saw some simple examples of linear programs, derived the concept of a dual linear program, and saw the duality theorem and the complementary slackness conditions which give a rough sketch of the stopping criterion for an algorithm. This time we’ll go ahead and <em>write</em> this algorithm for solving linear programs, and <a href="http://jeremykun.com/2017/09/24/linear-programming-and-healthy-diets-part-2/">next time</a> we’ll apply the algorithm to an industry-strength version of the nutrition problem we saw last time. The algorithm we’ll implement is called the <em>simplex algorithm</em>. It was the first algorithm for solving linear programs, invented in the 1940’s by George Dantzig, and it’s still the leading practical algorithm, and it was a key part of <a href="http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/1975/kantorovich-lecture.html">a Nobel Prize</a>. It’s by far one of the most important algorithms ever devised.</p><p>As usual, we’ll post <a href="https://github.com/j2kun/simplex-algorithm">all of the code</a> written in the making of this post on <a href="https://github.com/j2kun/">this blog’s Github page</a>.</p><h2>Slack variables and equality constraints</h2><p>The simplex algorithm can solve any kind of linear program, but it only accepts a special form of the program as input. So first we have to do some manipulations. Recall that the primal form of a linear program was the following minimization problem.</p><p>$$\min \left \langle c, x \right \rangle \\\ \textup{s.t. } Ax \geq b, x \geq 0$$</p><p>where the brackets mean “dot product.” And its dual is</p><p>$$\max \left \langle y, b \right \rangle \\\ \textup{s.t. } A^Ty \leq c, y \geq 0$$</p><p>The linear program can actually have more complicated constraints than just the ones above. In general, one might want to have “greater than” and “less than” constraints in the same problem. It turns out that this isn’t any harder, and moreover the simplex algorithm only uses <em>equality</em> constraints, and with some finicky algebra we can turn any set of inequality or equality constraints into a set of equality constraints.</p><p>We’ll call our goal the “standard form,” which is as follows:</p><p>$$\max \left \langle c, x \right \rangle \\\ \textup{s.t. } Ax = b, x \geq 0$$</p><p>It seems impossible to get the usual minimization/maximization problem into standard form until you realize there’s nothing stopping you from adding more variables to the problem. That is, say we’re given a constraint like:</p><p>$$\displaystyle x_7 + x_3 \leq 10,$$</p><p>we can add a new variable $ \xi$, called a <em>slack variable</em>, so that we get an equality:</p><p>$$\displaystyle x_7 + x_3 + \xi = 10$$</p><p>And now we can just impose that $ \xi \geq 0$. The idea is that $ \xi$ represents how much “slack” there is in the inequality, and you can always choose it to make the condition an equality. So if the equality holds and the variables are nonnegative, then the $ x_i$ will still satisfy their original inequality. For “greater than” constraints, we can do the same thing but subtract a nonnegative variable. Finally, if we have a minimization problem “$ \min z$” we can convert it to $ \max -z$.</p><p>So, to combine all of this together, if we have the following linear program with each kind of constraint,</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/10/screen-shot-2014-10-05-at-12-06-19-am.png?ssl=1"></a><figcaption><h4>Screen Shot 2014-10-05 at 12.06.19 AM</h4></figcaption></figure><p>We can add new variables $ \xi_1, \xi_2$, and write it as</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/10/screen-shot-2014-10-05-at-12-06-41-am.png?ssl=1"></a><figcaption><h4>Screen Shot 2014-10-05 at 12.06.41 AM</h4></figcaption></figure><p>By defining the vector variable $ x = (x_1, x_2, x_3, \xi_1, \xi_2)$ and $ c = (-1,-1,-1,0,0)$ and $ A$ to have $ -1, 0, 1$ as appropriately for the new variables, we see that the system is written in standard form.</p><p>This is the kind of tedious transformation we can automate with a program. Assuming there are $ n$ variables, the input consists of the vector $ c$ of length $ n$, and three matrix-vector pairs $ (A, b)$ representing the three kinds of constraints. It’s a bit annoying to describe, but the essential idea is that we compute a rectangular “identity” matrix whose diagonal entries are $ \pm 1$, and then join this with the original constraint matrix row-wise. The reader can see the full implementation in <a href="https://github.com/j2kun/simplex-algorithm">the Github repository for this post</a>, though we won’t use this particular functionality in the algorithm that follows.</p><p>There are some other additional things we could do: for example there might be some variables that are completely unrestricted. What you do in this case is take an unrestricted variable $ z$ and replace it by the difference of <em>two</em> unrestricted variables $ z’ – z”$. For simplicity we’ll ignore this, but it would be a fruitful exercise for the reader to augment the function to account for these.</p><h2>What happened to the slackness conditions?</h2><p>The “standard form” of our linear program raises an obvious question: how can the complementary slackness conditions make sense if everything is an equality? It turns out that one can redo all the work one did for linear programs of the form we gave last time (minimize w.r.t. greater-than constraints) for programs in the new “standard form” above. We even get the same complementary slackness conditions! If you want to, you can do this entire routine quite a bit faster if you <a href="http://jeremykun.com/2013/11/30/lagrangians-for-the-amnesiac/">invoke the power of Lagrangians</a>. We won’t do that here, but the tool shows up as a way to work with primal-dual conversions in many other parts of mathematics, so it’s a good buzzword to keep in mind.</p><p>In our case, the only difference with the complementary slackness conditions is that one of the two is trivial: $ \left \langle y^*, Ax^* – b \right \rangle = 0$. This is because if our candidate solution $ x^*$ is feasible, then it will have to satisfy $ Ax = b$ already. The other one, that $ \left \langle x^*, A^Ty^* – c \right \rangle = 0$, is the only one we need to worry about.</p><p>Again, the complementary slackness conditions give us inspiration here. Recall that, informally, they say that when a variable is used at all, it is used as much as it can be to fulfill its constraint (the corresponding dual constraint is tight). So a solution will correspond to a choice of some variables which are either used or not, and a choice of nonzero variables will correspond to a solution. We even saw this happen in <a href="http://jeremykun.com/2014/06/02/linear-programming-and-the-most-affordable-healthy-diet-part-1/">the last post</a> when we observed that broccoli trumps oranges. If we can get a good handle on how to navigate the set of these solutions, then we’ll have a nifty algorithm.</p><p>Let’s make this official and lay out our assumptions.</p><h2>Extreme points and basic solutions</h2><p><a href="http://jeremykun.com/2014/06/02/linear-programming-and-the-most-affordable-healthy-diet-part-1/">Remember</a> that the graphical way to solve a linear program is to look at the line (or hyperplane) given by $ \langle c, x \rangle = q$ and keep increasing $ q$ (or decreasing it, if you are minimizing) until the very last moment when this line touches the region of feasible solutions. Also recall that the “feasible region” is just the set of all solutions to $ Ax = b$, that is the solutions that satisfy the constraints. We imagined this picture:</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/05/lp-visualization.png"></a><figcaption><h4>The constraints define a convex area of 'feasible solutions.' Image source: Wikipedia.</h4></figcaption></figure><p>With this geometric intuition it’s clear that there will always be an optimal solution on a <em>vertex</em> of the feasible region. These points are called <em>extreme points</em> of the feasible region. But because we will almost never work in the plane again (even introducing slack variables makes us relatively high dimensional!) we want an algebraic characterization of these extreme points.</p><p>If you have a little bit of practice with convex sets the correct definition is very natural. Recall that a set $ X$ is <em>convex</em> if for any two points $ x, y \in X$ every point on the line segment between $ x$ and $ y$ is also in $ X$. An algebraic way to say this (thinking of these points now as vectors) is that every point $ \delta x + (1-\delta) y \in X$ when $ 0 \leq \delta \leq 1$. Now an <em>extreme</em> point is just a point that isn’t on the inside of any such line, i.e. can’t be written this way for $ 0 &lt; \delta &lt; 1$. For example,</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/06/extremepoint.png?ssl=1"></a><figcaption><h4>A convex set with extremal points in red. Image credit Wikipedia.</h4></figcaption></figure><p>Another way to say this is that if $ z$ is an extreme point then whenever $ z$ can be written as $ \delta x + (1-\delta) y$ for some $ 0 &lt; \delta &lt; 1$, then actually $ x=y=z$. Now since our constraints are all linear (and there are a finite number of them) they won’t define a convex set with weird curves like the one above. This means that there are a finite number of extreme points that just correspond to the intersections of some of the constraints. So there are at most $ 2^n$ possibilities.</p><p>Indeed we want a characterization of extreme points that’s specific to linear programs in standard form, “$ \max \langle c, x \rangle \textup{ s.t. } Ax=b, x \geq 0$.” And here is one.</p><p><strong>Definition:</strong> Let $ A$ be an $ m \times n$ matrix with $ n \geq m$. A solution $ x$ to $ Ax=b$ is called <em>basic</em> if at most $ m$ of its entries are nonzero.</p><p>The reason we call it “basic” is because, under some mild assumptions we describe below, a basic solution corresponds to a vector space basis of $ \mathbb{R}^m$. Which basis? The one given by the $ m$ columns of $ A$ used in the basic solution. We don’t need to talk about bases like this, though, so in the event of a headache just think of the basis as a set $ B \subset \{ 1, 2, \dots, n \}$ of size $ m$ corresponding to the nonzero entries of the basic solution.</p><p>Indeed, what we’re doing here is looking at the matrix $ A_B$ formed by taking the columns of $ A$ whose indices are in $ B$, and the vector $ x_B$ in the same way, and looking at the equation $ A_Bx_B = b$. If all the parts of $ x$ that we removed were zero then this will hold if and only if $ Ax=b$. One might worry that $ A_B$ is not invertible, so we’ll go ahead and assume it is. In fact, we’ll assume that <em>every</em> set of $ m$ columns of $ A$ forms a basis and that the rows of $ A$ are also linearly independent. This isn’t without loss of generality because if some rows or columns are not linearly independent, we can remove the offending constraints and variables without changing the set of solutions (this is why it’s so nice to work with the standard form).</p><p>Moreover, we’ll assume that every basic solution has <em>exactly</em> $ m$ nonzero variables. A basic solution which doesn’t satisfy this assumption is called <em>degenerate</em>, and they’ll essentially be special corner cases in the simplex algorithm. Finally, we call a basic solution <em>feasible</em> if (in addition to satisfying $ Ax=b$) it satisfies $ x \geq 0$. Now that we’ve made all these assumptions it’s easy to see that choosing $ m$ nonzero variables uniquely determines a basic feasible solution. Again calling the sub-matrix $ A_B$ for a basis $ B$, it’s just $ x_B = A_B^{-1}b$. Now to finish our characterization, we just have to show that under the same assumptions basic feasible solutions are exactly the extremal points of the feasible region.</p><p><strong>Proposition:</strong> A vector $ x$ is a basic feasible solution if and only if it’s an extreme point of the set $ \{ x : Ax = b, x \geq 0 \}$.</p><p><em>Proof.</em> For one direction, suppose you have a basic feasible solution $ x$, and say we write it as $ x = \delta y + (1-\delta) z$ for some $ 0 &lt; \delta &lt; 1$. We want to show that this implies $ y = z$. Since all of these points are in the feasible region, all of their coordinates are nonnegative. So whenever a coordinate $ x_i = 0$ it must be that both $ y_i = z_i = 0$. Since $ x$ has exactly $ n-m$ zero entries, it must be that $ y, z$ both have at least $ n-m$ zero entries, and hence $ y,z$ are both basic. By our non-degeneracy assumption they both then have exactly $ m$ nonzero entries. Let $ B$ be the set of the nonzero indices of $ x$. Because $ Ay = Az = b$, we have $ A(y-z) = 0$. Now $ y-z$ has all of its nonzero entries in $ B$, and because the columns of $ A_B$ are linearly independent, the fact that $ A_B(y-z) = 0$ implies $ y-z = 0$.</p><p>In the other direction, suppose that you have some extreme point $ x$ which is feasible but not basic. In other words, there are more than $ m$ nonzero entries of $ x$, and we’ll call the indices $ J = \{ j_1, \dots, j_t \}$ where $ t &gt; m$. The columns of $ A_J$ are linearly dependent (since they’re $ t$ vectors in $ \mathbb{R}^m$), and so let $ \sum_{i=1}^t z_{j_i} A_{j_i}$ be a nontrivial linear combination of the columns of $ A$. Add zeros to make the $ z_{j_i}$ into a length $ n$ vector $ z$, so that $ Az = 0$. Now</p><p>$$A(x + \varepsilon z) = A(x – \varepsilon z) = Ax = b$$</p><p>And if we pick $ \varepsilon$ sufficiently small $ x \pm \varepsilon z$ will still be nonnegative, because the only entries we’re changing of $ x$ are the strictly positive ones. Then $ x = \delta (x + \varepsilon z) + (1 – \delta) \varepsilon z$ for $ \delta = 1/2$, but this is very embarrassing for $ x$ who was supposed to be an extreme point. $ \square$</p><p>Now that we know extreme points are the same as basic feasible solutions, we need to show that any linear program that has <em>some</em> solution has a basic feasible solution. This is clear geometrically: any time you have an optimum it has to either lie on a line or at a vertex, and if it lies on a line then you can slide it to a vertex without changing its value. Nevertheless, it is a useful exercise to go through the algebra.</p><p><strong>Theorem.</strong> Whenever a linear program is feasible and bounded, it has a basic feasible solution.</p><p><em>Proof.</em> Let $ x$ be an optimal solution to the LP. If $ x$ has at most $ m$ nonzero entries then it’s a basic solution and by the non-degeneracy assumption it must have exactly $ m$ nonzero entries. In this case there’s nothing to do, so suppose that $ x$ has $ r &gt; m$ nonzero entries. It can’t be a basic feasible solution, and hence is not an extreme point of the set of feasible solutions (as proved by the last theorem). So write it as $ x = \delta y + (1-\delta) z$ for some feasible $ y \neq z$ and $ 0 &lt; \delta &lt; 1$.</p><p>The only thing we know about $ x$ is it’s optimal. Let $ c$ be the cost vector, and the optimality says that $ \langle c,x \rangle \geq \langle c,y \rangle$, and $ \langle c,x \rangle \geq \langle c,z \rangle$. We claim that in fact these are equal, that $ y, z$ are both optimal as well. Indeed, say $ y$ were not optimal, then</p><p>$$\displaystyle \langle c, y \rangle &lt; \langle c,x \rangle = \delta \langle c,y \rangle + (1-\delta) \langle c,z \rangle$$</p><p>Which can be rearranged to show that $ \langle c,y \rangle &lt; \langle c, z \rangle$. Unfortunately for $ x$, this implies that it was not optimal all along:</p><p>$$\displaystyle \langle c,x \rangle &lt; \delta \langle c, z \rangle + (1-\delta) \langle c,z \rangle = \langle c,z \rangle$$</p><p>An identical argument works to show $ z$ is optimal, too. Now we claim we can use $ y,z$ to get a new solution that has fewer than $ r$ nonzero entries. Once we show this we’re done: inductively repeat the argument with the smaller solution until we get down to exactly $ m$ nonzero variables. As before we know that $ y,z$ must have at least as many zeros as $ x$. If they have more zeros we’re done. And if they have exactly as many zeros we can do the following trick. Write $ w = \gamma y + (1- \gamma)z$ for a $ \gamma \in \mathbb{R}$ we’ll choose later. Note that no matter the $ \gamma$, $ w$ is optimal. Rewriting $ w = z + \gamma (y-z)$, we just have to pick a $ \gamma$ that ensures one of the nonzero coefficients of $ z$ is zeroed out while maintaining nonnegativity. Indeed, we can just look at the index $ i$ which minimizes $ z_i / (y-z)_i$ and use $ \delta = – z_i / (y-z)_i$. $ \square$.</p><p>So we have an immediate (and inefficient) combinatorial algorithm: enumerate all subsets of size $ m$, compute the corresponding basic feasible solution $ x_B = A_B^{-1}b$, and see which gives the biggest objective value. The problem is that, even if we knew the value of $ m$, this would take time $ n^m$, and it’s not uncommon for $ m$ to be in the tens or hundreds (and if we don’t know $ m$ the trivial search is exponential).</p><p>So we have to be smarter, and this is where the simplex tableau comes in.</p><h2>The simplex tableau</h2><p>Now say you have any basis $ B$ and any feasible solution $ x$. For now $ x$ might not be a basic solution, and even if it is, its basis of nonzero entries might not be the same as $ B$. We can decompose the equation $ Ax = b$ into the basis part and the non basis part:</p><p>$$A_Bx_B + A_{B’} x_{B’} = b$$</p><p>and solving the equation for $ x_B$ gives</p><p>$$x_B = A^{-1}_B(b – A_{B’} x_{B’})$$</p><p>It may look like we’re making a wicked abuse of notation here, but both $ A_Bx_B$ and $ A_{B’}x_{B’}$ are vectors of length $ m$ so the dimensions actually do work out. Now our feasible solution $ x$ has to satisfy $ Ax = b$, and the entries of $ x$ are all nonnegative, so it must be that $ x_B \geq 0$ and $ x_{B’} \geq 0$, and by the equality above $ A^{-1}_B (b – A_{B’}x_{B’}) \geq 0$ as well. Now let’s write the maximization objective $ \langle c, x \rangle$ by expanding it first in terms of the $ x_B, x_{B’}$, and then expanding $ x_B$.</p><p>$ \displaystyle \begin{aligned} \langle c, x \rangle &amp; = \langle c_B, x_B \rangle + \langle c_{B’}, x_{B’} \rangle \\\
&amp; = \langle c_B, A^{-1}_B(b – A_{B’}x_{B’}) \rangle + \langle c_{B’}, x_{B’} \rangle \\\
&amp; = \langle c_B, A^{-1}_Bb \rangle + \langle c_{B’} – (A^{-1}_B A_{B’})^T c_B, x_{B’} \rangle \end{aligned}$</p><p>If we want to maximize the objective, we can just maximize this last line. There are two cases. In the first, the vector $ c_{B’} – (A^{-1}_B A_{B’})^T c_B \leq 0$ and $ A_B^{-1}b \geq 0$. In the above equation, this tells us that making any component of $ x_{B’}$ bigger will <em>decrease</em> the overall objective. In other words, $ \langle c, x \rangle \leq \langle c_B, A_B^{-1}b \rangle$. Picking $ x = A_B^{-1}b$ (with zeros in the non basis part) meets this bound and hence must be optimal. In other words, no matter what basis $ B$ we’ve chosen (i.e., no matter the candidate basic feasible solution), if the two conditions hold then we’re done.</p><p>Now the crux of the algorithm is the second case: if the conditions <em>aren’t</em> met, we can pick a positive index of $ c_{B’} – (A_B^{-1}A_{B’})^Tc_B$ and increase the corresponding value of $ x_{B’}$ to increase the objective value. As we do this, other variables in the solution will change as well (by decreasing), and we have to stop when one of them hits zero. In doing so, this changes the basis by removing one index and adding another. In reality, we’ll figure out how much to increase ahead of time, and the change will correspond to a single elementary row-operation in a matrix.</p><p>Indeed, the matrix we’ll use to represent all of this data is called a <em>tableau</em> in the literature. The columns of the tableau will correspond to variables, and the rows to constraints. The last row of the tableau will maintain a candidate solution $ y$ to the dual problem. Here’s a rough picture to keep the different parts clear while we go through the details.</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/06/tableau.png?ssl=1"></a><figcaption><h4>tableau</h4></figcaption></figure><p>But to make it work we do a slick trick, which is to “left-multiply everything” by $ A_B^{-1}$. In particular, if we have an LP given by $ c, A, b$, then for any basis it’s equivalent to the LP given by $ c, A_B^{-1}A, A_{B}^{-1} b$ (just multiply your solution to the new program by $ A_B$ to get a solution to the old one). And so the actual tableau will be of this form.</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/11/tableau-symbols1.gif?ssl=1"></a><figcaption><h4>tableau-symbols</h4></figcaption></figure><p>When we say it’s in this form, it’s really only true up to rearranging columns. This is because the chosen basis will always be represented by an identity matrix (as it is to start with), so to find the basis you can find the embedded identity sub-matrix. In fact, the beginning of the simplex algorithm will have the initial basis sitting in the <em>last</em> few columns of the tableau.</p><p>Let’s look a little bit closer at the last row. The first portion is zero because $ A_B^{-1}A_B$ is the identity. But furthermore with this $ A_B^{-1}$ trick the dual LP involves $ A_B^{-1}$ everywhere there’s a variable. In particular, joining all but the last column of the last row of the tableau, we have the vector $ c – A_B^T(A_B^{-1})^T c$, and setting $ y = A_B^{-1}c_B$ we get a candidate solution for the dual. What makes the trick even slicker is that $ A_B^{-1}b$ is already the candidate solution $ x_B$, since $ (A_B^{-1}A)_B^{-1}$ is the identity. So we’re implicitly keeping track of two solutions here, one for the primal LP, given by the last column of the tableau, and one for the dual, contained in the last row of the tableau.</p><p>I told you the last row was the dual solution, so why all the other crap there? This is the final slick in the trick: the last row further encodes the complementary slackness conditions. Now that we recognize the dual candidate sitting there, the complementary slackness conditions simply ask for the last row to be non-positive (this is just another way of saying what we said at the beginning of this section!). You should check this, but it gives us a stopping criterion: if the last row is non-positive then stop and output the last column.</p><h2>The simplex algorithm</h2><p>Now (finally!) we can describe and implement the simplex algorithm in its full glory. Recall that our informal setup has been:</p><ol><li>Find an initial basic feasible solution, and set up the corresponding tableau.</li><li>Find a positive index of the last row, and increase the corresponding variable (adding it to the basis) just enough to make another variable from the basis zero (removing it from the basis).</li><li>Repeat step 2 until the last row is nonpositive.</li><li>Output the last column.</li></ol><p>This is almost correct, except for some details about how increasing the corresponding variables works. What we’ll really do is represent the basis variables as pivots (ones in the tableau) and then the first 1 in each row will be the variable whose value is given by the entry in the last column of that row. So, for example, the last entry in the first row may be the optimal value for $ x_5$, if the fifth column is the first entry in row 1 to have a 1.</p><p>As we describe the algorithm, we’ll illustrate it running on a simple example. In doing this we’ll see what all the different parts of the tableau correspond to from the previous section in each step of the algorithm.</p><figure><a href="https://www.jeremykun.com/wp-content/uploads/2014/11/example2.gif?ssl=1"></a><figcaption><h4>example</h4></figcaption></figure><p>Spoiler alert: the optimum is $ x_1 = 2, x_2 = 1$ and the value of the max is 8.</p><p>So let’s be more programmatically formal about this. The main routine is essentially pseudocode, and the difficulty is in implementing the helper functions</p><div><pre><code></code></pre></div><p>Let’s start with the initial tableau. We’ll assume the user’s inputs already include the slack variables. In particular, our example data <em>before</em> adding slack is</p><div><pre><code></code></pre></div><p>And after adding slack:</p><div><pre><code></code></pre></div><p>Now to set up the initial tableau we need an initial feasible solution in mind. The reader is recommended to work this part out with a pencil, since it’s much easier to write down than it is to explain. Since we introduced slack variables, our initial feasible solution (basis) $ B$ can just be $ (0,0,1,1)$. And so $ x_B$ is just the slack variables, $ c_B$ is the zero vector, and $ A_B$ is the 2×2 identity matrix. Now $ A_B^{-1}A_{B’} = A_{B’}$, which is just the original two columns of $ A$ we started with, and $ A_B^{-1}b = b$. For the last row, $ c_B$ is zero so the part under $ A_B^{-1}A_B$ is the zero vector. The part under $ A_B^{-1}A_{B’}$ is just $ c_{B’} = (3,2)$.</p><p>Rather than move columns around every time the basis $ B$ changes, we’ll keep the tableau columns in order of $ (x_1, \dots, x_n, \xi_1, \dots, \xi_m)$. In other words, for our example the initial tableau should look like this.</p><div><pre><code></code></pre></div><p>So implementing <code>initialTableau</code> is just a matter of putting the data in the right place.</p><div><pre><code></code></pre></div><p>As an aside: in the event that we <em>don’t</em> start with the trivial basic feasible solution of “trivially use the slack variables,” we’d have to do a lot more work in this function. Next, the <code>primalSolution()</code> and <code>objectiveValue()</code> functions are simple, because they just extract the encoded information out from the tableau (some helper functions are omitted for brevity).</p><div><pre><code></code></pre></div><p>Similarly, the <code>canImprove()</code> function just checks if there’s a nonnegative entry in the last row</p><div><pre><code></code></pre></div><p>Let’s run the first loop of our simplex algorithm. The first step is checking to see if anything can be improved (in our example it can). Then we have to find a pivot entry in the tableau. This part includes some edge-case checking, but if the edge cases aren’t a problem then the strategy is simple: find a positive entry corresponding to some entry $ j$ of $ B’$, and then pick an appropriate entry in that column to use as the pivot. Pivoting increases the value of $ x_j$ (from zero) to whatever is the largest we can make it without making some other variables become negative. As we’ve said before, we’ll stop increasing $ x_j$ when some other variable hits zero, and we can compute which will be the first to do so by looking at the current values of $ x_B = A_B^{-1}b$ (in the last column of the tableau), and seeing how pivoting will affect them. If you stare at it for long enough, it becomes clear that the first variable to hit zero will be the entry $ x_i$ of the basis for which $ x_i / A_{i,j}$ is minimal (and $ A_{i,j}$ has to be positve). This is because, in order to maintain the linear equalities, every entry of $ x_B$ will be decreased by that value during a pivot, and we can’t let <em>any</em> of the variables become negative.</p><p>All of this results in the following function, where we have left out the degeneracy/unboundedness checks.</p><p><strong>[UPDATE 2018-04-21]:</strong> The pivot choices are not as simple as I thought at the time I wrote this. See the discussion on this <a href="https://github.com/j2kun/simplex-algorithm/issues/1">issue</a>, but the short story is that I was increasing the variable too much, and to fix it it’s easier to update the pivot column choice to be the smallest positive entry of the last row. The code on github is updated to reflect that, but this post will remain unchanged.</p><div><pre><code></code></pre></div><p>For our example, the minimizer is the $ (1,0)$ entry (second row, first column). Pivoting is just doing the usual elementary row operations (we covered this in a primer a while back on row-reduction). The pivot function we use here is no different, and in particular mutates the list in place.</p><div><pre><code></code></pre></div><p>And in our example pivoting around the chosen entry gives the new tableau.</p><div><pre><code></code></pre></div><p>In particular, $ B$ is now $ (1,0,1,0)$, since our pivot removed the second slack variable $ \xi_2$ from the basis. Currently our solution has $ x_1 = 1, \xi_1 = 3$. Notice how the identity submatrix is still sitting in there, the columns are just swapped around.</p><p>There’s still a positive entry in the bottom row, so let’s continue. The next pivot is (0,1), and pivoting around that entry gives the following tableau:</p><div><pre><code></code></pre></div><p>And because all of the entries in the bottom row are negative, we’re done. We read off the solution as we described, so that the first variable is 2 and the second is 1, and the objective value is the opposite of the bottom right entry, 8.</p><p>To see all of the source code, including the edge-case-checking we left out of this post, see the <a href="https://github.com/j2kun/simplex-algorithm">Github repository for this post</a>.</p><h2>Obvious questions and sad answers</h2><p>An obvious question is: what is the runtime of the simplex algorithm? Is it polynomial in the size of the tableau? Is it even guaranteed to stop at some point? The surprising truth is that nobody knows the answer to all of these questions! Originally (in the 1940’s) the simplex algorithm actually had an exponential runtime in the worst case, though <a href="http://www.ams.org/mathscinet-getitem?mr=332165">this was not known until 1972</a>. And indeed, to this day while some variations <a href="http://en.wikipedia.org/wiki/Bland%27s_rule">are known to terminate</a>, no variation is known to have polynomial runtime in the worst case. Some of the choices we made in our implementation (for example, picking the <em>first</em> column with a positive entry in the bottom row) have the potential to cycle, i.e., variables leave and enter the basis without changing the objective at all. Doing something like picking a <em>random</em> positive column, or picking the column which will increase the objective value by the largest amount are alternatives. Unfortunately, every single pivot-picking rule is known to give rise to exponential-time simplex algorithms in the worst case (in fact, this was discovered <a href="http://cs.au.dk/~tdh/slides/simplex2.pdf">as recently as 2011!</a>). So it remains open whether there is a variant of the simplex method that runs in guaranteed polynomial time.</p><p>But then, in a stunning turn of events, <a href="http://en.wikipedia.org/wiki/Leonid_Khachiyan">Leonid Khachiyan</a> proved in the 70’s that in fact linear programs can always be solved in polynomial time, via a completely different algorithm called the <em>ellipsoid method</em>. Following that was a method called the <a href="http://en.wikipedia.org/wiki/Interior_point_method"><em>interior point method</em></a>, which is significantly more efficient. Both of these algorithms generalize to problems that are harder than linear programming as well, so we will probably cover them in the distant future of this blog.</p><p>Despite the celebratory nature of these two results, people still use the simplex algorithm for industrial applications of linear programming. The reason is that it’s much faster in practice, and much simpler to implement and experiment with.</p><p>The next obvious question has to do with the poignant observation that whole numbers are great. That is, you often want the solution to your problem to involve integers, and not real numbers. But adding the constraint that the variables in a linear program need to be integer valued (even just 0-1 valued!) is NP-complete. This problem is called <em>integer linear programming,</em> or just <em>integer programming</em> (IP). So we can’t hope to solve IP, and rightly so: the reader can verify easily that boolean satisfiability instances can be written as linear programs where each clause corresponds to a constraint.</p><p>This brings up a very interesting theoretical issue: if we take an integer program and just remove the integrality constraints, and solve the resulting linear program, how far away are the two solutions? If they’re close, then we can hope to give a good <em>approximation</em> to the integer program by solving the linear program and somehow turning the resulting solution back into an integer solution. In fact this is a very popular technique called <em>LP-rounding</em>. We’ll also likely cover that on this blog at some point.</p><p>Oh there’s so much to do and so little time! Until next time.</p></div></div>||||I|||| / Math ∩ Programming / Posts
 * Main Content
 * Primers
 * All articles
 * About
 * rss

Linear Programming and the Simplex Algorithm

 #exponential time algorithms #integer programming #linear algebra #linear programming #lp-relaxation #optimization #row reduction #simplex algorithm
 2014-12-01


 This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email.

 In the last post in this series we saw some simple examples of linear programs, derived the concept of a dual linear program, and saw the duality theorem and the complementary slackness conditions which give a rough sketch of the stopping criterion for an algorithm. This time we’ll go ahead and write this algorithm for solving linear programs, and next time we’ll apply the algorithm to an industry-strength version of the nutrition problem we saw last time. The algorithm we’ll implement is called the simplex algorithm. It was the first algorithm for solving linear programs, invented in the 1940’s by George Dantzig, and it’s still the leading practical algorithm, and it was a key part of a Nobel Prize. It’s by far one of the most important algorithms ever devised.

 As usual, we’ll post all of the code written in the making of this post on this blog’s Github page.

 Slack variables and equality constraints

 The simplex algorithm can solve any kind of linear program, but it only accepts a special form of the program as input. So first we have to do some manipulations. Recall that the primal form of a linear program was the following minimization problem.

 $$\min \left \langle c, x \right \rangle \\\ \textup{s.t. } Ax \geq b, x \geq 0$$

 where the brackets mean “dot product.” And its dual is

 $$\max \left \langle y, b \right \rangle \\\ \textup{s.t. } A^Ty \leq c, y \geq 0$$

 The linear program can actually have more complicated constraints than just the ones above. In general, one might want to have “greater than” and “less than” constraints in the same problem. It turns out that this isn’t any harder, and moreover the simplex algorithm only uses equality constraints, and with some finicky algebra we can turn any set of inequality or equality constraints into a set of equality constraints.

 We’ll call our goal the “standard form,” which is as follows:

 $$\max \left \langle c, x \right \rangle \\\ \textup{s.t. } Ax = b, x \geq 0$$

 It seems impossible to get the usual minimization/maximization problem into standard form until you realize there’s nothing stopping you from adding more variables to the problem. That is, say we’re given a constraint like:

 $$\displaystyle x_7 + x_3 \leq 10,$$

 we can add a new variable $ \xi$, called a slack variable, so that we get an equality:

 $$\displaystyle x_7 + x_3 + \xi = 10$$

 And now we can just impose that $ \xi \geq 0$. The idea is that $ \xi$ represents how much “slack” there is in the inequality, and you can always choose it to make the condition an equality. So if the equality holds and the variables are nonnegative, then the $ x_i$ will still satisfy their original inequality. For “greater than” constraints, we can do the same thing but subtract a nonnegative variable. Finally, if we have a minimization problem “$ \min z$” we can convert it to $ \max -z$.

 So, to combine all of this together, if we have the following linear program with each kind of constraint,

 Screen Shot 2014-10-05 at 12.06.19 AM

 We can add new variables $ \xi_1, \xi_2$, and write it as

 Screen Shot 2014-10-05 at 12.06.41 AM

 By defining the vector variable $ x = (x_1, x_2, x_3, \xi_1, \xi_2)$ and $ c = (-1,-1,-1,0,0)$ and $ A$ to have $ -1, 0, 1$ as appropriately for the new variables, we see that the system is written in standard form.

 This is the kind of tedious transformation we can automate with a program. Assuming there are $ n$ variables, the input consists of the vector $ c$ of length $ n$, and three matrix-vector pairs $ (A, b)$ representing the three kinds of constraints. It’s a bit annoying to describe, but the essential idea is that we compute a rectangular “identity” matrix whose diagonal entries are $ \pm 1$, and then join this with the original constraint matrix row-wise. The reader can see the full implementation in the Github repository for this post, though we won’t use this particular functionality in the algorithm that follows.

 There are some other additional things we could do: for example there might be some variables that are completely unrestricted. What you do in this case is take an unrestricted variable $ z$ and replace it by the difference of two unrestricted variables $ z’ – z”$. For simplicity we’ll ignore this, but it would be a fruitful exercise for the reader to augment the function to account for these.

 What happened to the slackness conditions?

 The “standard form” of our linear program raises an obvious question: how can the complementary slackness conditions make sense if everything is an equality? It turns out that one can redo all the work one did for linear programs of the form we gave last time (minimize w.r.t. greater-than constraints) for programs in the new “standard form” above. We even get the same complementary slackness conditions! If you want to, you can do this entire routine quite a bit faster if you invoke the power of Lagrangians. We won’t do that here, but the tool shows up as a way to work with primal-dual conversions in many other parts of mathematics, so it’s a good buzzword to keep in mind.

 In our case, the only difference with the complementary slackness conditions is that one of the two is trivial: $ \left \langle y^*, Ax^* – b \right \rangle = 0$. This is because if our candidate solution $ x^*$ is feasible, then it will have to satisfy $ Ax = b$ already. The other one, that $ \left \langle x^*, A^Ty^* – c \right \rangle = 0$, is the only one we need to worry about.

 Again, the complementary slackness conditions give us inspiration here. Recall that, informally, they say that when a variable is used at all, it is used as much as it can be to fulfill its constraint (the corresponding dual constraint is tight). So a solution will correspond to a choice of some variables which are either used or not, and a choice of nonzero variables will correspond to a solution. We even saw this happen in the last post when we observed that broccoli trumps oranges. If we can get a good handle on how to navigate the set of these solutions, then we’ll have a nifty algorithm.

 Let’s make this official and lay out our assumptions.

 Extreme points and basic solutions

 Remember that the graphical way to solve a linear program is to look at the line (or hyperplane) given by $ \langle c, x \rangle = q$ and keep increasing $ q$ (or decreasing it, if you are minimizing) until the very last moment when this line touches the region of feasible solutions. Also recall that the “feasible region” is just the set of all solutions to $ Ax = b$, that is the solutions that satisfy the constraints. We imagined this picture:

 The constraints define a convex area of 'feasible solutions.' Image source: Wikipedia.

 With this geometric intuition it’s clear that there will always be an optimal solution on a vertex of the feasible region. These points are called extreme points of the feasible region. But because we will almost never work in the plane again (even introducing slack variables makes us relatively high dimensional!) we want an algebraic characterization of these extreme points.

 If you have a little bit of practice with convex sets the correct definition is very natural. Recall that a set $ X$ is convex if for any two points $ x, y \in X$ every point on the line segment between $ x$ and $ y$ is also in $ X$. An algebraic way to say this (thinking of these points now as vectors) is that every point $ \delta x + (1-\delta) y \in X$ when $ 0 \leq \delta \leq 1$. Now an extreme point is just a point that isn’t on the inside of any such line, i.e. can’t be written this way for $ 0 < \delta < 1$. For example,

 A convex set with extremal points in red. Image credit Wikipedia.

 Another way to say this is that if $ z$ is an extreme point then whenever $ z$ can be written as $ \delta x + (1-\delta) y$ for some $ 0 < \delta < 1$, then actually $ x=y=z$. Now since our constraints are all linear (and there are a finite number of them) they won’t define a convex set with weird curves like the one above. This means that there are a finite number of extreme points that just correspond to the intersections of some of the constraints. So there are at most $ 2^n$ possibilities.

 Indeed we want a characterization of extreme points that’s specific to linear programs in standard form, “$ \max \langle c, x \rangle \textup{ s.t. } Ax=b, x \geq 0$.” And here is one.

 Definition: Let $ A$ be an $ m \times n$ matrix with $ n \geq m$. A solution $ x$ to $ Ax=b$ is called basic if at most $ m$ of its entries are nonzero.

 The reason we call it “basic” is because, under some mild assumptions we describe below, a basic solution corresponds to a vector space basis of $ \mathbb{R}^m$. Which basis? The one given by the $ m$ columns of $ A$ used in the basic solution. We don’t need to talk about bases like this, though, so in the event of a headache just think of the basis as a set $ B \subset \{ 1, 2, \dots, n \}$ of size $ m$ corresponding to the nonzero entries of the basic solution.

 Indeed, what we’re doing here is looking at the matrix $ A_B$ formed by taking the columns of $ A$ whose indices are in $ B$, and the vector $ x_B$ in the same way, and looking at the equation $ A_Bx_B = b$. If all the parts of $ x$ that we removed were zero then this will hold if and only if $ Ax=b$. One might worry that $ A_B$ is not invertible, so we’ll go ahead and assume it is. In fact, we’ll assume that every set of $ m$ columns of $ A$ forms a basis and that the rows of $ A$ are also linearly independent. This isn’t without loss of generality because if some rows or columns are not linearly independent, we can remove the offending constraints and variables without changing the set of solutions (this is why it’s so nice to work with the standard form).

 Moreover, we’ll assume that every basic solution has exactly $ m$ nonzero variables. A basic solution which doesn’t satisfy this assumption is called degenerate, and they’ll essentially be special corner cases in the simplex algorithm. Finally, we call a basic solution feasible if (in addition to satisfying $ Ax=b$) it satisfies $ x \geq 0$. Now that we’ve made all these assumptions it’s easy to see that choosing $ m$ nonzero variables uniquely determines a basic feasible solution. Again calling the sub-matrix $ A_B$ for a basis $ B$, it’s just $ x_B = A_B^{-1}b$. Now to finish our characterization, we just have to show that under the same assumptions basic feasible solutions are exactly the extremal points of the feasible region.

 Proposition: A vector $ x$ is a basic feasible solution if and only if it’s an extreme point of the set $ \{ x : Ax = b, x \geq 0 \}$.

 Proof. For one direction, suppose you have a basic feasible solution $ x$, and say we write it as $ x = \delta y + (1-\delta) z$ for some $ 0 < \delta < 1$. We want to show that this implies $ y = z$. Since all of these points are in the feasible region, all of their coordinates are nonnegative. So whenever a coordinate $ x_i = 0$ it must be that both $ y_i = z_i = 0$. Since $ x$ has exactly $ n-m$ zero entries, it must be that $ y, z$ both have at least $ n-m$ zero entries, and hence $ y,z$ are both basic. By our non-degeneracy assumption they both then have exactly $ m$ nonzero entries. Let $ B$ be the set of the nonzero indices of $ x$. Because $ Ay = Az = b$, we have $ A(y-z) = 0$. Now $ y-z$ has all of its nonzero entries in $ B$, and because the columns of $ A_B$ are linearly independent, the fact that $ A_B(y-z) = 0$ implies $ y-z = 0$.

 In the other direction, suppose that you have some extreme point $ x$ which is feasible but not basic. In other words, there are more than $ m$ nonzero entries of $ x$, and we’ll call the indices $ J = \{ j_1, \dots, j_t \}$ where $ t > m$. The columns of $ A_J$ are linearly dependent (since they’re $ t$ vectors in $ \mathbb{R}^m$), and so let $ \sum_{i=1}^t z_{j_i} A_{j_i}$ be a nontrivial linear combination of the columns of $ A$. Add zeros to make the $ z_{j_i}$ into a length $ n$ vector $ z$, so that $ Az = 0$. Now

 $$A(x + \varepsilon z) = A(x – \varepsilon z) = Ax = b$$

 And if we pick $ \varepsilon$ sufficiently small $ x \pm \varepsilon z$ will still be nonnegative, because the only entries we’re changing of $ x$ are the strictly positive ones. Then $ x = \delta (x + \varepsilon z) + (1 – \delta) \varepsilon z$ for $ \delta = 1/2$, but this is very embarrassing for $ x$ who was supposed to be an extreme point. $ \square$

 Now that we know extreme points are the same as basic feasible solutions, we need to show that any linear program that has some solution has a basic feasible solution. This is clear geometrically: any time you have an optimum it has to either lie on a line or at a vertex, and if it lies on a line then you can slide it to a vertex without changing its value. Nevertheless, it is a useful exercise to go through the algebra.

 Theorem. Whenever a linear program is feasible and bounded, it has a basic feasible solution.

 Proof. Let $ x$ be an optimal solution to the LP. If $ x$ has at most $ m$ nonzero entries then it’s a basic solution and by the non-degeneracy assumption it must have exactly $ m$ nonzero entries. In this case there’s nothing to do, so suppose that $ x$ has $ r > m$ nonzero entries. It can’t be a basic feasible solution, and hence is not an extreme point of the set of feasible solutions (as proved by the last theorem). So write it as $ x = \delta y + (1-\delta) z$ for some feasible $ y \neq z$ and $ 0 < \delta < 1$.

 The only thing we know about $ x$ is it’s optimal. Let $ c$ be the cost vector, and the optimality says that $ \langle c,x \rangle \geq \langle c,y \rangle$, and $ \langle c,x \rangle \geq \langle c,z \rangle$. We claim that in fact these are equal, that $ y, z$ are both optimal as well. Indeed, say $ y$ were not optimal, then

 $$\displaystyle \langle c, y \rangle < \langle c,x \rangle = \delta \langle c,y \rangle + (1-\delta) \langle c,z \rangle$$

 Which can be rearranged to show that $ \langle c,y \rangle < \langle c, z \rangle$. Unfortunately for $ x$, this implies that it was not optimal all along:

 $$\displaystyle \langle c,x \rangle < \delta \langle c, z \rangle + (1-\delta) \langle c,z \rangle = \langle c,z \rangle$$

 An identical argument works to show $ z$ is optimal, too. Now we claim we can use $ y,z$ to get a new solution that has fewer than $ r$ nonzero entries. Once we show this we’re done: inductively repeat the argument with the smaller solution until we get down to exactly $ m$ nonzero variables. As before we know that $ y,z$ must have at least as many zeros as $ x$. If they have more zeros we’re done. And if they have exactly as many zeros we can do the following trick. Write $ w = \gamma y + (1- \gamma)z$ for a $ \gamma \in \mathbb{R}$ we’ll choose later. Note that no matter the $ \gamma$, $ w$ is optimal. Rewriting $ w = z + \gamma (y-z)$, we just have to pick a $ \gamma$ that ensures one of the nonzero coefficients of $ z$ is zeroed out while maintaining nonnegativity. Indeed, we can just look at the index $ i$ which minimizes $ z_i / (y-z)_i$ and use $ \delta = – z_i / (y-z)_i$. $ \square$.

 So we have an immediate (and inefficient) combinatorial algorithm: enumerate all subsets of size $ m$, compute the corresponding basic feasible solution $ x_B = A_B^{-1}b$, and see which gives the biggest objective value. The problem is that, even if we knew the value of $ m$, this would take time $ n^m$, and it’s not uncommon for $ m$ to be in the tens or hundreds (and if we don’t know $ m$ the trivial search is exponential).

 So we have to be smarter, and this is where the simplex tableau comes in.

 The simplex tableau

 Now say you have any basis $ B$ and any feasible solution $ x$. For now $ x$ might not be a basic solution, and even if it is, its basis of nonzero entries might not be the same as $ B$. We can decompose the equation $ Ax = b$ into the basis part and the non basis part:

 $$A_Bx_B + A_{B’} x_{B’} = b$$

 and solving the equation for $ x_B$ gives

 $$x_B = A^{-1}_B(b – A_{B’} x_{B’})$$

 It may look like we’re making a wicked abuse of notation here, but both $ A_Bx_B$ and $ A_{B’}x_{B’}$ are vectors of length $ m$ so the dimensions actually do work out. Now our feasible solution $ x$ has to satisfy $ Ax = b$, and the entries of $ x$ are all nonnegative, so it must be that $ x_B \geq 0$ and $ x_{B’} \geq 0$, and by the equality above $ A^{-1}_B (b – A_{B’}x_{B’}) \geq 0$ as well. Now let’s write the maximization objective $ \langle c, x \rangle$ by expanding it first in terms of the $ x_B, x_{B’}$, and then expanding $ x_B$.

 $ \displaystyle \begin{aligned} \langle c, x \rangle & = \langle c_B, x_B \rangle + \langle c_{B’}, x_{B’} \rangle \\\ & = \langle c_B, A^{-1}_B(b – A_{B’}x_{B’}) \rangle + \langle c_{B’}, x_{B’} \rangle \\\ & = \langle c_B, A^{-1}_Bb \rangle + \langle c_{B’} – (A^{-1}_B A_{B’})^T c_B, x_{B’} \rangle \end{aligned}$

 If we want to maximize the objective, we can just maximize this last line. There are two cases. In the first, the vector $ c_{B’} – (A^{-1}_B A_{B’})^T c_B \leq 0$ and $ A_B^{-1}b \geq 0$. In the above equation, this tells us that making any component of $ x_{B’}$ bigger will decrease the overall objective. In other words, $ \langle c, x \rangle \leq \langle c_B, A_B^{-1}b \rangle$. Picking $ x = A_B^{-1}b$ (with zeros in the non basis part) meets this bound and hence must be optimal. In other words, no matter what basis $ B$ we’ve chosen (i.e., no matter the candidate basic feasible solution), if the two conditions hold then we’re done.

 Now the crux of the algorithm is the second case: if the conditions aren’t met, we can pick a positive index of $ c_{B’} – (A_B^{-1}A_{B’})^Tc_B$ and increase the corresponding value of $ x_{B’}$ to increase the objective value. As we do this, other variables in the solution will change as well (by decreasing), and we have to stop when one of them hits zero. In doing so, this changes the basis by removing one index and adding another. In reality, we’ll figure out how much to increase ahead of time, and the change will correspond to a single elementary row-operation in a matrix.

 Indeed, the matrix we’ll use to represent all of this data is called a tableau in the literature. The columns of the tableau will correspond to variables, and the rows to constraints. The last row of the tableau will maintain a candidate solution $ y$ to the dual problem. Here’s a rough picture to keep the different parts clear while we go through the details.

 tableau

 But to make it work we do a slick trick, which is to “left-multiply everything” by $ A_B^{-1}$. In particular, if we have an LP given by $ c, A, b$, then for any basis it’s equivalent to the LP given by $ c, A_B^{-1}A, A_{B}^{-1} b$ (just multiply your solution to the new program by $ A_B$ to get a solution to the old one). And so the actual tableau will be of this form.

 tableau-symbols

 When we say it’s in this form, it’s really only true up to rearranging columns. This is because the chosen basis will always be represented by an identity matrix (as it is to start with), so to find the basis you can find the embedded identity sub-matrix. In fact, the beginning of the simplex algorithm will have the initial basis sitting in the last few columns of the tableau.

 Let’s look a little bit closer at the last row. The first portion is zero because $ A_B^{-1}A_B$ is the identity. But furthermore with this $ A_B^{-1}$ trick the dual LP involves $ A_B^{-1}$ everywhere there’s a variable. In particular, joining all but the last column of the last row of the tableau, we have the vector $ c – A_B^T(A_B^{-1})^T c$, and setting $ y = A_B^{-1}c_B$ we get a candidate solution for the dual. What makes the trick even slicker is that $ A_B^{-1}b$ is already the candidate solution $ x_B$, since $ (A_B^{-1}A)_B^{-1}$ is the identity. So we’re implicitly keeping track of two solutions here, one for the primal LP, given by the last column of the tableau, and one for the dual, contained in the last row of the tableau.

 I told you the last row was the dual solution, so why all the other crap there? This is the final slick in the trick: the last row further encodes the complementary slackness conditions. Now that we recognize the dual candidate sitting there, the complementary slackness conditions simply ask for the last row to be non-positive (this is just another way of saying what we said at the beginning of this section!). You should check this, but it gives us a stopping criterion: if the last row is non-positive then stop and output the last column.

 The simplex algorithm

 Now (finally!) we can describe and implement the simplex algorithm in its full glory. Recall that our informal setup has been:

 1. Find an initial basic feasible solution, and set up the corresponding tableau.
 2. Find a positive index of the last row, and increase the corresponding variable (adding it to the basis) just enough to make another variable from the basis zero (removing it from the basis).
 3. Repeat step 2 until the last row is nonpositive.
 4. Output the last column.

 This is almost correct, except for some details about how increasing the corresponding variables works. What we’ll really do is represent the basis variables as pivots (ones in the tableau) and then the first 1 in each row will be the variable whose value is given by the entry in the last column of that row. So, for example, the last entry in the first row may be the optimal value for $ x_5$, if the fifth column is the first entry in row 1 to have a 1.

 As we describe the algorithm, we’ll illustrate it running on a simple example. In doing this we’ll see what all the different parts of the tableau correspond to from the previous section in each step of the algorithm.

 example

 Spoiler alert: the optimum is $ x_1 = 2, x_2 = 1$ and the value of the max is 8.

 So let’s be more programmatically formal about this. The main routine is essentially pseudocode, and the difficulty is in implementing the helper functions

 def simplex(c, A, b):
 tableau = initialTableau(c, A, b)
 
 while canImprove(tableau):
 pivot = findPivotIndex(tableau)
 pivotAbout(tableau, pivot)
 
 return primalSolution(tableau), objectiveValue(tableau)
 

 Let’s start with the initial tableau. We’ll assume the user’s inputs already include the slack variables. In particular, our example data before adding slack is

 c = [3, 2]
 A = [[1, 2], [1, -1]]
 b = [4, 1]
 

 And after adding slack:

 c = [3, 2, 0, 0]
 A = [[1, 2, 1, 0],
 [1, -1, 0, 1]]
 b = [4, 1]
 

 Now to set up the initial tableau we need an initial feasible solution in mind. The reader is recommended to work this part out with a pencil, since it’s much easier to write down than it is to explain. Since we introduced slack variables, our initial feasible solution (basis) $ B$ can just be $ (0,0,1,1)$. And so $ x_B$ is just the slack variables, $ c_B$ is the zero vector, and $ A_B$ is the 2×2 identity matrix. Now $ A_B^{-1}A_{B’} = A_{B’}$, which is just the original two columns of $ A$ we started with, and $ A_B^{-1}b = b$. For the last row, $ c_B$ is zero so the part under $ A_B^{-1}A_B$ is the zero vector. The part under $ A_B^{-1}A_{B’}$ is just $ c_{B’} = (3,2)$.

 Rather than move columns around every time the basis $ B$ changes, we’ll keep the tableau columns in order of $ (x_1, \dots, x_n, \xi_1, \dots, \xi_m)$. In other words, for our example the initial tableau should look like this.

 [[ 1, 2, 1, 0, 4],
 [ 1, -1, 0, 1, 1],
 [ 3, 2, 0, 0, 0]]
 

 So implementing initialTableau is just a matter of putting the data in the right place.

 def initialTableau(c, A, b):
 tableau = [row[:] + [x] for row, x in zip(A, b)]
 tableau.append(c[:] + [0])
 return tableau
 

 As an aside: in the event that we don’t start with the trivial basic feasible solution of “trivially use the slack variables,” we’d have to do a lot more work in this function. Next, the primalSolution() and objectiveValue() functions are simple, because they just extract the encoded information out from the tableau (some helper functions are omitted for brevity).

 def primalSolution(tableau):
 # the pivot columns denote which variables are used
 columns = transpose(tableau)
 indices = [j for j, col in enumerate(columns[:-1]) if isPivotCol(col)]
 return list(zip(indices, columns[-1]))
 
 def objectiveValue(tableau):
 return -(tableau[-1][-1])
 

 Similarly, the canImprove() function just checks if there’s a nonnegative entry in the last row

 def canImprove(tableau):
 lastRow = tableau[-1]
 return any(x > 0 for x in lastRow[:-1])
 

 Let’s run the first loop of our simplex algorithm. The first step is checking to see if anything can be improved (in our example it can). Then we have to find a pivot entry in the tableau. This part includes some edge-case checking, but if the edge cases aren’t a problem then the strategy is simple: find a positive entry corresponding to some entry $ j$ of $ B’$, and then pick an appropriate entry in that column to use as the pivot. Pivoting increases the value of $ x_j$ (from zero) to whatever is the largest we can make it without making some other variables become negative. As we’ve said before, we’ll stop increasing $ x_j$ when some other variable hits zero, and we can compute which will be the first to do so by looking at the current values of $ x_B = A_B^{-1}b$ (in the last column of the tableau), and seeing how pivoting will affect them. If you stare at it for long enough, it becomes clear that the first variable to hit zero will be the entry $ x_i$ of the basis for which $ x_i / A_{i,j}$ is minimal (and $ A_{i,j}$ has to be positve). This is because, in order to maintain the linear equalities, every entry of $ x_B$ will be decreased by that value during a pivot, and we can’t let any of the variables become negative.

 All of this results in the following function, where we have left out the degeneracy/unboundedness checks.

 [UPDATE 2018-04-21]: The pivot choices are not as simple as I thought at the time I wrote this. See the discussion on this issue, but the short story is that I was increasing the variable too much, and to fix it it’s easier to update the pivot column choice to be the smallest positive entry of the last row. The code on github is updated to reflect that, but this post will remain unchanged.

 def findPivotIndex(tableau):
 # pick first nonzero index of the last row
 column = [i for i,x in enumerate(tableau[-1][:-1]) if x > 0][0]
 quotients = [(i, r[-1] / r[column]) for i,r in enumerate(tableau[:-1]) if r[column] > 0]
 
 # pick row index minimizing the quotient
 row = min(quotients, key=lambda x: x[1])[0]
 return row, column
 

 For our example, the minimizer is the $ (1,0)$ entry (second row, first column). Pivoting is just doing the usual elementary row operations (we covered this in a primer a while back on row-reduction). The pivot function we use here is no different, and in particular mutates the list in place.

 def pivotAbout(tableau, pivot):
 i,j = pivot
 
 pivotDenom = tableau[i][j]
 tableau[i] = [x / pivotDenom for x in tableau[i]]
 
 for k,row in enumerate(tableau):
 if k != i:
 pivotRowMultiple = [y * tableau[k][j] for y in tableau[i]]
 tableau[k] = [x - y for x,y in zip(tableau[k], pivotRowMultiple)]
 

 And in our example pivoting around the chosen entry gives the new tableau.

 [[ 0., 3., 1., -1., 3.],
 [ 1., -1., 0., 1., 1.],
 [ 0., 5., 0., -3., -3.]]
 

 In particular, $ B$ is now $ (1,0,1,0)$, since our pivot removed the second slack variable $ \xi_2$ from the basis. Currently our solution has $ x_1 = 1, \xi_1 = 3$. Notice how the identity submatrix is still sitting in there, the columns are just swapped around.

 There’s still a positive entry in the bottom row, so let’s continue. The next pivot is (0,1), and pivoting around that entry gives the following tableau:

 [[ 0. , 1. , 0.33333333, -0.33333333, 1. ],
 [ 1. , 0. , 0.33333333, 0.66666667, 2. ],
 [ 0. , 0. , -1.66666667, -1.33333333, -8. ]]
 

 And because all of the entries in the bottom row are negative, we’re done. We read off the solution as we described, so that the first variable is 2 and the second is 1, and the objective value is the opposite of the bottom right entry, 8.

 To see all of the source code, including the edge-case-checking we left out of this post, see the Github repository for this post.

 Obvious questions and sad answers

 An obvious question is: what is the runtime of the simplex algorithm? Is it polynomial in the size of the tableau? Is it even guaranteed to stop at some point? The surprising truth is that nobody knows the answer to all of these questions! Originally (in the 1940’s) the simplex algorithm actually had an exponential runtime in the worst case, though this was not known until 1972. And indeed, to this day while some variations are known to terminate, no variation is known to have polynomial runtime in the worst case. Some of the choices we made in our implementation (for example, picking the first column with a positive entry in the bottom row) have the potential to cycle, i.e., variables leave and enter the basis without changing the objective at all. Doing something like picking a random positive column, or picking the column which will increase the objective value by the largest amount are alternatives. Unfortunately, every single pivot-picking rule is known to give rise to exponential-time simplex algorithms in the worst case (in fact, this was discovered as recently as 2011!). So it remains open whether there is a variant of the simplex method that runs in guaranteed polynomial time.

 But then, in a stunning turn of events, Leonid Khachiyan proved in the 70’s that in fact linear programs can always be solved in polynomial time, via a completely different algorithm called the ellipsoid method. Following that was a method called the interior point method, which is significantly more efficient. Both of these algorithms generalize to problems that are harder than linear programming as well, so we will probably cover them in the distant future of this blog.

 Despite the celebratory nature of these two results, people still use the simplex algorithm for industrial applications of linear programming. The reason is that it’s much faster in practice, and much simpler to implement and experiment with.

 The next obvious question has to do with the poignant observation that whole numbers are great. That is, you often want the solution to your problem to involve integers, and not real numbers. But adding the constraint that the variables in a linear program need to be integer valued (even just 0-1 valued!) is NP-complete. This problem is called integer linear programming, or just integer programming (IP). So we can’t hope to solve IP, and rightly so: the reader can verify easily that boolean satisfiability instances can be written as linear programs where each clause corresponds to a constraint.

 This brings up a very interesting theoretical issue: if we take an integer program and just remove the integrality constraints, and solve the resulting linear program, how far away are the two solutions? If they’re close, then we can hope to give a good approximation to the integer program by solving the linear program and somehow turning the resulting solution back into an integer solution. In fact this is a very popular technique called LP-rounding. We’ll also likely cover that on this blog at some point.

 Oh there’s so much to do and so little time! Until next time.


 ← Previous: Learning a single-variable polynomial, or the power of adaptive queries Next: A Motivation for Quantum Computing →
This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email.  In the last post in this series we saw some simple examples of linear programs, derived the concept of a dual linear program, and saw the duality theorem and the complementary slackness conditions which give a rough sketch of the stopping criterion for an algorithm. This time we’ll go ahead and write this algorithm for solving linear programs, and next time we’ll apply the algorithm to an industry-strength version of the nutrition problem we saw last time. The algorithm we’ll implement is called the simplex algorithm. It was the first algorithm for solving linear programs, invented in the 1940’s by George Dantzig, and it’s still the leading practical algorithm, and it was a key part of a Nobel Prize. It’s by far one of the most important algorithms ever devised. As usual, we’ll post all of the code written in the making of this post on this blog’s Github page. Slack variables and equality constraints The simplex algorithm can solve any kind of linear program, but it only accepts a special form of the program as input. So first we have to do some manipulations. Recall that the primal form of a linear program was the following minimization problem. $$\min \left \langle c, x \right \rangle \\\ \textup{s.t. } Ax \geq b, x \geq 0$$ where the brackets mean “dot product.” And its dual is $$\max \left \langle y, b \right \rangle \\\ \textup{s.t. } A^Ty \leq c, y \geq 0$$ The linear program can actually have more complicated constraints than just the ones above. In general, one might want to have “greater than” and “less than” constraints in the same problem. It turns out that this isn’t any harder, and moreover the simplex algorithm only uses equality constraints, and with some finicky algebra we can turn any set of inequality or equality constraints into a set of equality constraints. We’ll call our goal the “standard form,” which is as follows: $$\max \left \langle c, x \right \rangle \\\ \textup{s.t. } Ax = b, x \geq 0$$ It seems impossible to get the usual minimization/maximization problem into standard form until you realize there’s nothing stopping you from adding more variables to the problem. That is, say we’re given a constraint like: $$\displaystyle x_7 + x_3 \leq 10,$$ we can add a new variable $ \xi$, called a slack variable, so that we get an equality: $$\displaystyle x_7 + x_3 + \xi = 10$$ And now we can just impose that $ \xi \geq 0$. The idea is that $ \xi$ represents how much “slack” there is in the inequality, and you can always choose it to make the condition an equality. So if the equality holds and the variables are nonnegative, then the $ x_i$ will still satisfy their original inequality. For “greater than” constraints, we can do the same thing but subtract a nonnegative variable. Finally, if we have a minimization problem “$ \min z$” we can convert it to $ \max -z$. So, to combine all of this together, if we have the following linear program with each kind of constraint,     Screen Shot 2014-10-05 at 12.06.19 AM   We can add new variables $ \xi_1, \xi_2$, and write it as     Screen Shot 2014-10-05 at 12.06.41 AM   By defining the vector variable $ x = (x_1, x_2, x_3, \xi_1, \xi_2)$ and $ c = (-1,-1,-1,0,0)$ and $ A$ to have $ -1, 0, 1$ as appropriately for the new variables, we see that the system is written in standard form. This is the kind of tedious transformation we can automate with a program. Assuming there are $ n$ variables, the input consists of the vector $ c$ of length $ n$, and three matrix-vector pairs $ (A, b)$ representing the three kinds of constraints. It’s a bit annoying to describe, but the essential idea is that we compute a rectangular “identity” matrix whose diagonal entries are $ \pm 1$, and then join this with the original constraint matrix row-wise. The reader can see the full implementation in the Github repository for this post, though we won’t use this particular functionality in the algorithm that follows. There are some other additional things we could do: for example there might be some variables that are completely unrestricted. What you do in this case is take an unrestricted variable $ z$ and replace it by the difference of two unrestricted variables $ z’ – z”$. For simplicity we’ll ignore this, but it would be a fruitful exercise for the reader to augment the function to account for these. What happened to the slackness conditions? The “standard form” of our linear program raises an obvious question: how can the complementary slackness conditions make sense if everything is an equality? It turns out that one can redo all the work one did for linear programs of the form we gave last time (minimize w.r.t. greater-than constraints) for programs in the new “standard form” above. We even get the same complementary slackness conditions! If you want to, you can do this entire routine quite a bit faster if you invoke the power of Lagrangians. We won’t do that here, but the tool shows up as a way to work with primal-dual conversions in many other parts of mathematics, so it’s a good buzzword to keep in mind. In our case, the only difference with the complementary slackness conditions is that one of the two is trivial: $ \left \langle y^*, Ax^* – b \right \rangle = 0$. This is because if our candidate solution $ x^*$ is feasible, then it will have to satisfy $ Ax = b$ already. The other one, that $ \left \langle x^*, A^Ty^* – c \right \rangle = 0$, is the only one we need to worry about. Again, the complementary slackness conditions give us inspiration here. Recall that, informally, they say that when a variable is used at all, it is used as much as it can be to fulfill its constraint (the corresponding dual constraint is tight). So a solution will correspond to a choice of some variables which are either used or not, and a choice of nonzero variables will correspond to a solution. We even saw this happen in the last post when we observed that broccoli trumps oranges. If we can get a good handle on how to navigate the set of these solutions, then we’ll have a nifty algorithm. Let’s make this official and lay out our assumptions. Extreme points and basic solutions  Remember that the graphical way to solve a linear program is to look at the line (or hyperplane) given by $ \langle c, x \rangle = q$ and keep increasing $ q$ (or decreasing it, if you are minimizing) until the very last moment when this line touches the region of feasible solutions. Also recall that the “feasible region” is just the set of all solutions to $ Ax = b$, that is the solutions that satisfy the constraints. We imagined this picture:     The constraints define a convex area of 'feasible solutions.' Image source: Wikipedia.   With this geometric intuition it’s clear that there will always be an optimal solution on a vertex of the feasible region. These points are called extreme points of the feasible region. But because we will almost never work in the plane again (even introducing slack variables makes us relatively high dimensional!) we want an algebraic characterization of these extreme points. If you have a little bit of practice with convex sets the correct definition is very natural. Recall that a set $ X$ is convex if for any two points $ x, y \in X$ every point on the line segment between $ x$ and $ y$ is also in $ X$. An algebraic way to say this (thinking of these points now as vectors) is that every point $ \delta x + (1-\delta) y \in X$ when $ 0 \leq \delta \leq 1$. Now an extreme point is just a point that isn’t on the inside of any such line, i.e. can’t be written this way for $ 0 &lt; \delta &lt; 1$. For example,     A convex set with extremal points in red. Image credit Wikipedia.   Another way to say this is that if $ z$ is an extreme point then whenever $ z$ can be written as $ \delta x + (1-\delta) y$ for some $ 0 &lt; \delta &lt; 1$, then actually $ x=y=z$. Now since our constraints are all linear (and there are a finite number of them) they won’t define a convex set with weird curves like the one above. This means that there are a finite number of extreme points that just correspond to the intersections of some of the constraints. So there are at most $ 2^n$ possibilities. Indeed we want a characterization of extreme points that’s specific to linear programs in standard form, “$ \max \langle c, x \rangle \textup{ s.t. } Ax=b, x \geq 0$.” And here is one.  Definition: Let $ A$ be an $ m \times n$ matrix with $ n \geq m$. A solution $ x$ to $ Ax=b$ is called basic if at most $ m$ of its entries are nonzero. The reason we call it “basic” is because, under some mild assumptions we describe below, a basic solution corresponds to a vector space basis of $ \mathbb{R}^m$. Which basis? The one given by the $ m$ columns of $ A$ used in the basic solution. We don’t need to talk about bases like this, though, so in the event of a headache just think of the basis as a set $ B \subset \{ 1, 2, \dots, n \}$ of size $ m$ corresponding to the nonzero entries of the basic solution. Indeed, what we’re doing here is looking at the matrix $ A_B$ formed by taking the columns of $ A$ whose indices are in $ B$, and the vector $ x_B$ in the same way, and looking at the equation $ A_Bx_B = b$. If all the parts of $ x$ that we removed were zero then this will hold if and only if $ Ax=b$. One might worry that $ A_B$ is not invertible, so we’ll go ahead and assume it is. In fact, we’ll assume that every set of $ m$ columns of $ A$ forms a basis and that the rows of $ A$ are also linearly independent. This isn’t without loss of generality because if some rows or columns are not linearly independent, we can remove the offending constraints and variables without changing the set of solutions (this is why it’s so nice to work with the standard form). Moreover, we’ll assume that every basic solution has exactly $ m$ nonzero variables. A basic solution which doesn’t satisfy this assumption is called degenerate, and they’ll essentially be special corner cases in the simplex algorithm. Finally, we call a basic solution feasible if (in addition to satisfying $ Ax=b$) it satisfies $ x \geq 0$. Now that we’ve made all these assumptions it’s easy to see that choosing $ m$ nonzero variables uniquely determines a basic feasible solution. Again calling the sub-matrix $ A_B$ for a basis $ B$, it’s just $ x_B = A_B^{-1}b$. Now to finish our characterization, we just have to show that under the same assumptions basic feasible solutions are exactly the extremal points of the feasible region.  Proposition: A vector $ x$ is a basic feasible solution if and only if it’s an extreme point of the set $ \{ x : Ax = b, x \geq 0 \}$.  Proof. For one direction, suppose you have a basic feasible solution $ x$, and say we write it as $ x = \delta y + (1-\delta) z$ for some $ 0 &lt; \delta &lt; 1$. We want to show that this implies $ y = z$. Since all of these points are in the feasible region, all of their coordinates are nonnegative. So whenever a coordinate $ x_i = 0$ it must be that both $ y_i = z_i = 0$. Since $ x$ has exactly $ n-m$ zero entries, it must be that $ y, z$ both have at least $ n-m$ zero entries, and hence $ y,z$ are both basic. By our non-degeneracy assumption they both then have exactly $ m$ nonzero entries. Let $ B$ be the set of the nonzero indices of $ x$. Because $ Ay = Az = b$, we have $ A(y-z) = 0$. Now $ y-z$ has all of its nonzero entries in $ B$, and because the columns of $ A_B$ are linearly independent, the fact that $ A_B(y-z) = 0$ implies $ y-z = 0$. In the other direction, suppose that you have some extreme point $ x$ which is feasible but not basic. In other words, there are more than $ m$ nonzero entries of $ x$, and we’ll call the indices $ J = \{ j_1, \dots, j_t \}$ where $ t &gt; m$. The columns of $ A_J$ are linearly dependent (since they’re $ t$ vectors in $ \mathbb{R}^m$), and so let $ \sum_{i=1}^t z_{j_i} A_{j_i}$ be a nontrivial linear combination of the columns of $ A$. Add zeros to make the $ z_{j_i}$ into a length $ n$ vector $ z$, so that $ Az = 0$. Now $$A(x + \varepsilon z) = A(x – \varepsilon z) = Ax = b$$ And if we pick $ \varepsilon$ sufficiently small $ x \pm \varepsilon z$ will still be nonnegative, because the only entries we’re changing of $ x$ are the strictly positive ones. Then $ x = \delta (x + \varepsilon z) + (1 – \delta) \varepsilon z$ for $ \delta = 1/2$, but this is very embarrassing for $ x$ who was supposed to be an extreme point. $ \square$ Now that we know extreme points are the same as basic feasible solutions, we need to show that any linear program that has some solution has a basic feasible solution. This is clear geometrically: any time you have an optimum it has to either lie on a line or at a vertex, and if it lies on a line then you can slide it to a vertex without changing its value. Nevertheless, it is a useful exercise to go through the algebra.  Theorem. Whenever a linear program is feasible and bounded, it has a basic feasible solution.  Proof. Let $ x$ be an optimal solution to the LP. If $ x$ has at most $ m$ nonzero entries then it’s a basic solution and by the non-degeneracy assumption it must have exactly $ m$ nonzero entries. In this case there’s nothing to do, so suppose that $ x$ has $ r &gt; m$ nonzero entries. It can’t be a basic feasible solution, and hence is not an extreme point of the set of feasible solutions (as proved by the last theorem). So write it as $ x = \delta y + (1-\delta) z$ for some feasible $ y \neq z$ and $ 0 &lt; \delta &lt; 1$. The only thing we know about $ x$ is it’s optimal. Let $ c$ be the cost vector, and the optimality says that $ \langle c,x \rangle \geq \langle c,y \rangle$, and $ \langle c,x \rangle \geq \langle c,z \rangle$. We claim that in fact these are equal, that $ y, z$ are both optimal as well. Indeed, say $ y$ were not optimal, then $$\displaystyle \langle c, y \rangle &lt; \langle c,x \rangle = \delta \langle c,y \rangle + (1-\delta) \langle c,z \rangle$$ Which can be rearranged to show that $ \langle c,y \rangle &lt; \langle c, z \rangle$. Unfortunately for $ x$, this implies that it was not optimal all along: $$\displaystyle \langle c,x \rangle &lt; \delta \langle c, z \rangle + (1-\delta) \langle c,z \rangle = \langle c,z \rangle$$ An identical argument works to show $ z$ is optimal, too. Now we claim we can use $ y,z$ to get a new solution that has fewer than $ r$ nonzero entries. Once we show this we’re done: inductively repeat the argument with the smaller solution until we get down to exactly $ m$ nonzero variables. As before we know that $ y,z$ must have at least as many zeros as $ x$. If they have more zeros we’re done. And if they have exactly as many zeros we can do the following trick. Write $ w = \gamma y + (1- \gamma)z$ for a $ \gamma \in \mathbb{R}$ we’ll choose later. Note that no matter the $ \gamma$, $ w$ is optimal. Rewriting $ w = z + \gamma (y-z)$, we just have to pick a $ \gamma$ that ensures one of the nonzero coefficients of $ z$ is zeroed out while maintaining nonnegativity. Indeed, we can just look at the index $ i$ which minimizes $ z_i / (y-z)_i$ and use $ \delta = – z_i / (y-z)_i$. $ \square$. So we have an immediate (and inefficient) combinatorial algorithm: enumerate all subsets of size $ m$, compute the corresponding basic feasible solution $ x_B = A_B^{-1}b$, and see which gives the biggest objective value. The problem is that, even if we knew the value of $ m$, this would take time $ n^m$, and it’s not uncommon for $ m$ to be in the tens or hundreds (and if we don’t know $ m$ the trivial search is exponential). So we have to be smarter, and this is where the simplex tableau comes in. The simplex tableau Now say you have any basis $ B$ and any feasible solution $ x$. For now $ x$ might not be a basic solution, and even if it is, its basis of nonzero entries might not be the same as $ B$. We can decompose the equation $ Ax = b$ into the basis part and the non basis part: $$A_Bx_B + A_{B’} x_{B’} = b$$ and solving the equation for $ x_B$ gives $$x_B = A^{-1}_B(b – A_{B’} x_{B’})$$ It may look like we’re making a wicked abuse of notation here, but both $ A_Bx_B$ and $ A_{B’}x_{B’}$ are vectors of length $ m$ so the dimensions actually do work out. Now our feasible solution $ x$ has to satisfy $ Ax = b$, and the entries of $ x$ are all nonnegative, so it must be that $ x_B \geq 0$ and $ x_{B’} \geq 0$, and by the equality above $ A^{-1}_B (b – A_{B’}x_{B’}) \geq 0$ as well. Now let’s write the maximization objective $ \langle c, x \rangle$ by expanding it first in terms of the $ x_B, x_{B’}$, and then expanding $ x_B$. $ \displaystyle \begin{aligned} \langle c, x \rangle &amp; = \langle c_B, x_B \rangle + \langle c_{B’}, x_{B’} \rangle \\\
&amp; = \langle c_B, A^{-1}_B(b – A_{B’}x_{B’}) \rangle + \langle c_{B’}, x_{B’} \rangle \\\
&amp; = \langle c_B, A^{-1}_Bb \rangle + \langle c_{B’} – (A^{-1}_B A_{B’})^T c_B, x_{B’} \rangle \end{aligned}$ If we want to maximize the objective, we can just maximize this last line. There are two cases. In the first, the vector $ c_{B’} – (A^{-1}_B A_{B’})^T c_B \leq 0$ and $ A_B^{-1}b \geq 0$. In the above equation, this tells us that making any component of $ x_{B’}$ bigger will decrease the overall objective. In other words, $ \langle c, x \rangle \leq \langle c_B, A_B^{-1}b \rangle$. Picking $ x = A_B^{-1}b$ (with zeros in the non basis part) meets this bound and hence must be optimal. In other words, no matter what basis $ B$ we’ve chosen (i.e., no matter the candidate basic feasible solution), if the two conditions hold then we’re done. Now the crux of the algorithm is the second case: if the conditions aren’t met, we can pick a positive index of $ c_{B’} – (A_B^{-1}A_{B’})^Tc_B$ and increase the corresponding value of $ x_{B’}$ to increase the objective value. As we do this, other variables in the solution will change as well (by decreasing), and we have to stop when one of them hits zero. In doing so, this changes the basis by removing one index and adding another. In reality, we’ll figure out how much to increase ahead of time, and the change will correspond to a single elementary row-operation in a matrix. Indeed, the matrix we’ll use to represent all of this data is called a tableau in the literature. The columns of the tableau will correspond to variables, and the rows to constraints. The last row of the tableau will maintain a candidate solution $ y$ to the dual problem. Here’s a rough picture to keep the different parts clear while we go through the details.     tableau   But to make it work we do a slick trick, which is to “left-multiply everything” by $ A_B^{-1}$. In particular, if we have an LP given by $ c, A, b$, then for any basis it’s equivalent to the LP given by $ c, A_B^{-1}A, A_{B}^{-1} b$ (just multiply your solution to the new program by $ A_B$ to get a solution to the old one). And so the actual tableau will be of this form.     tableau-symbols   When we say it’s in this form, it’s really only true up to rearranging columns. This is because the chosen basis will always be represented by an identity matrix (as it is to start with), so to find the basis you can find the embedded identity sub-matrix. In fact, the beginning of the simplex algorithm will have the initial basis sitting in the last few columns of the tableau. Let’s look a little bit closer at the last row. The first portion is zero because $ A_B^{-1}A_B$ is the identity. But furthermore with this $ A_B^{-1}$ trick the dual LP involves $ A_B^{-1}$ everywhere there’s a variable. In particular, joining all but the last column of the last row of the tableau, we have the vector $ c – A_B^T(A_B^{-1})^T c$, and setting $ y = A_B^{-1}c_B$ we get a candidate solution for the dual. What makes the trick even slicker is that $ A_B^{-1}b$ is already the candidate solution $ x_B$, since $ (A_B^{-1}A)_B^{-1}$ is the identity. So we’re implicitly keeping track of two solutions here, one for the primal LP, given by the last column of the tableau, and one for the dual, contained in the last row of the tableau. I told you the last row was the dual solution, so why all the other crap there? This is the final slick in the trick: the last row further encodes the complementary slackness conditions. Now that we recognize the dual candidate sitting there, the complementary slackness conditions simply ask for the last row to be non-positive (this is just another way of saying what we said at the beginning of this section!). You should check this, but it gives us a stopping criterion: if the last row is non-positive then stop and output the last column. The simplex algorithm Now (finally!) we can describe and implement the simplex algorithm in its full glory. Recall that our informal setup has been:  Find an initial basic feasible solution, and set up the corresponding tableau. Find a positive index of the last row, and increase the corresponding variable (adding it to the basis) just enough to make another variable from the basis zero (removing it from the basis). Repeat step 2 until the last row is nonpositive. Output the last column.  This is almost correct, except for some details about how increasing the corresponding variables works. What we’ll really do is represent the basis variables as pivots (ones in the tableau) and then the first 1 in each row will be the variable whose value is given by the entry in the last column of that row. So, for example, the last entry in the first row may be the optimal value for $ x_5$, if the fifth column is the first entry in row 1 to have a 1. As we describe the algorithm, we’ll illustrate it running on a simple example. In doing this we’ll see what all the different parts of the tableau correspond to from the previous section in each step of the algorithm.     example   Spoiler alert: the optimum is $ x_1 = 2, x_2 = 1$ and the value of the max is 8. So let’s be more programmatically formal about this. The main routine is essentially pseudocode, and the difficulty is in implementing the helper functions       Let’s start with the initial tableau. We’ll assume the user’s inputs already include the slack variables. In particular, our example data before adding slack is       And after adding slack:       Now to set up the initial tableau we need an initial feasible solution in mind. The reader is recommended to work this part out with a pencil, since it’s much easier to write down than it is to explain. Since we introduced slack variables, our initial feasible solution (basis) $ B$ can just be $ (0,0,1,1)$. And so $ x_B$ is just the slack variables, $ c_B$ is the zero vector, and $ A_B$ is the 2×2 identity matrix. Now $ A_B^{-1}A_{B’} = A_{B’}$, which is just the original two columns of $ A$ we started with, and $ A_B^{-1}b = b$. For the last row, $ c_B$ is zero so the part under $ A_B^{-1}A_B$ is the zero vector. The part under $ A_B^{-1}A_{B’}$ is just $ c_{B’} = (3,2)$. Rather than move columns around every time the basis $ B$ changes, we’ll keep the tableau columns in order of $ (x_1, \dots, x_n, \xi_1, \dots, \xi_m)$. In other words, for our example the initial tableau should look like this.       So implementing initialTableau is just a matter of putting the data in the right place.       As an aside: in the event that we don’t start with the trivial basic feasible solution of “trivially use the slack variables,” we’d have to do a lot more work in this function. Next, the primalSolution() and objectiveValue() functions are simple, because they just extract the encoded information out from the tableau (some helper functions are omitted for brevity).       Similarly, the canImprove() function just checks if there’s a nonnegative entry in the last row       Let’s run the first loop of our simplex algorithm. The first step is checking to see if anything can be improved (in our example it can). Then we have to find a pivot entry in the tableau. This part includes some edge-case checking, but if the edge cases aren’t a problem then the strategy is simple: find a positive entry corresponding to some entry $ j$ of $ B’$, and then pick an appropriate entry in that column to use as the pivot. Pivoting increases the value of $ x_j$ (from zero) to whatever is the largest we can make it without making some other variables become negative. As we’ve said before, we’ll stop increasing $ x_j$ when some other variable hits zero, and we can compute which will be the first to do so by looking at the current values of $ x_B = A_B^{-1}b$ (in the last column of the tableau), and seeing how pivoting will affect them. If you stare at it for long enough, it becomes clear that the first variable to hit zero will be the entry $ x_i$ of the basis for which $ x_i / A_{i,j}$ is minimal (and $ A_{i,j}$ has to be positve). This is because, in order to maintain the linear equalities, every entry of $ x_B$ will be decreased by that value during a pivot, and we can’t let any of the variables become negative. All of this results in the following function, where we have left out the degeneracy/unboundedness checks.  [UPDATE 2018-04-21]: The pivot choices are not as simple as I thought at the time I wrote this. See the discussion on this issue, but the short story is that I was increasing the variable too much, and to fix it it’s easier to update the pivot column choice to be the smallest positive entry of the last row. The code on github is updated to reflect that, but this post will remain unchanged.       For our example, the minimizer is the $ (1,0)$ entry (second row, first column). Pivoting is just doing the usual elementary row operations (we covered this in a primer a while back on row-reduction). The pivot function we use here is no different, and in particular mutates the list in place.       And in our example pivoting around the chosen entry gives the new tableau.       In particular, $ B$ is now $ (1,0,1,0)$, since our pivot removed the second slack variable $ \xi_2$ from the basis. Currently our solution has $ x_1 = 1, \xi_1 = 3$. Notice how the identity submatrix is still sitting in there, the columns are just swapped around. There’s still a positive entry in the bottom row, so let’s continue. The next pivot is (0,1), and pivoting around that entry gives the following tableau:       And because all of the entries in the bottom row are negative, we’re done. We read off the solution as we described, so that the first variable is 2 and the second is 1, and the objective value is the opposite of the bottom right entry, 8. To see all of the source code, including the edge-case-checking we left out of this post, see the Github repository for this post. Obvious questions and sad answers An obvious question is: what is the runtime of the simplex algorithm? Is it polynomial in the size of the tableau? Is it even guaranteed to stop at some point? The surprising truth is that nobody knows the answer to all of these questions! Originally (in the 1940’s) the simplex algorithm actually had an exponential runtime in the worst case, though this was not known until 1972. And indeed, to this day while some variations are known to terminate, no variation is known to have polynomial runtime in the worst case. Some of the choices we made in our implementation (for example, picking the first column with a positive entry in the bottom row) have the potential to cycle, i.e., variables leave and enter the basis without changing the objective at all. Doing something like picking a random positive column, or picking the column which will increase the objective value by the largest amount are alternatives. Unfortunately, every single pivot-picking rule is known to give rise to exponential-time simplex algorithms in the worst case (in fact, this was discovered as recently as 2011!). So it remains open whether there is a variant of the simplex method that runs in guaranteed polynomial time. But then, in a stunning turn of events, Leonid Khachiyan proved in the 70’s that in fact linear programs can always be solved in polynomial time, via a completely different algorithm called the ellipsoid method. Following that was a method called the  interior point method , which is significantly more efficient. Both of these algorithms generalize to problems that are harder than linear programming as well, so we will probably cover them in the distant future of this blog. Despite the celebratory nature of these two results, people still use the simplex algorithm for industrial applications of linear programming. The reason is that it’s much faster in practice, and much simpler to implement and experiment with. The next obvious question has to do with the poignant observation that whole numbers are great. That is, you often want the solution to your problem to involve integers, and not real numbers. But adding the constraint that the variables in a linear program need to be integer valued (even just 0-1 valued!) is NP-complete. This problem is called integer linear programming, or just integer programming (IP). So we can’t hope to solve IP, and rightly so: the reader can verify easily that boolean satisfiability instances can be written as linear programs where each clause corresponds to a constraint. This brings up a very interesting theoretical issue: if we take an integer program and just remove the integrality constraints, and solve the resulting linear program, how far away are the two solutions? If they’re close, then we can hope to give a good approximation to the integer program by solving the linear program and somehow turning the resulting solution back into an integer solution. In fact this is a very popular technique called LP-rounding. We’ll also likely cover that on this blog at some point. Oh there’s so much to do and so little time! Until next time.
Linear Programming and the Simplex Algorithm
https://jeremykun.com/2014/12/01/linear-programming-and-the-simplex-algorithm/
<div><div>


<div>
<p>Welcome to the Cornell University Computational Optimization Open Textbook</p>
<p>This electronic textbook is a student-contributed open-source text covering a variety of topics on process optimization.<br/>
<b>If you have any comments or suggestions on this open textbook, please contact <a href="https://www.engineering.cornell.edu/faculty-directory/fengqi-you">Professor Fengqi You</a>.</b>
</p>
</div>
</div></div>||||I||||  Main Page

      From Cornell University Computational Optimization Open Textbook - Optimization Wiki
    Jump to navigation Jump to search
            Welcome to the Cornell University Computational Optimization Open Textbook                                            
                                                                                                                                  
          This electronic textbook is a student-contributed open-source text covering a variety of topics on process optimization.
          If you have any comments or suggestions on this open textbook, please contact Professor Fengqi You.                     
                                                                                                                                  
                                                                                                                                  
          
            Linear Programming (LP)                                    Mixed-Integer Linear Programming (MILP)              
                                                                                                                            
            * Duality                                                  * Mixed-integer cuts                                 
            * Simplex algorithm                                        * Disjunctive inequalities                           
            * Computational complexity                                 * Lagrangean duality                                 
            * Network flow problem                                     * Column generation algorithms                       
            * Interior-point method for LP                             * Heuristic algorithms                               
            * Optimization with absolute values                        * Branch and cut                                     
            * Matrix game (LP for game theory)                         * Local branching                                    
            NonLinear Programming (NLP)                                Mixed-Integer NonLinear Programming (MINLP)          
                                                                                                                            
            * Line search methods                                      * Signomial problems                                 
            * Trust-region methods                                     * Mixed-integer linear fractional programming (MILFP)
            * Interior-point method for NLP                            * Convex generalized disjunctive programming (GDP)   
            * Conjugate gradient methods                               * Nonconvex generalized disjunctive programming (GDP)
            * Quasi-Newton methods                                     * Branch and bound (BB) for MINLP                    
            * Quadratic programming                                    * Branch and cut for MINLP                           
            * Sequential quadratic programming                         * Generalized Benders decomposition (GBD)            
            * Subgradient optimization                                 * Outer-approximation (OA)                           
            * Mathematical programming with equilibrium constraints    * Extended cutting plane (ECP)                       
            * Dynamic optimization                                     Optimization under Uncertainty                       
            * Geometric programming                                                                                         
            * Nondifferentiable Optimization                           * Stochastic programming                             
            Deterministic Global Optimization                          * Chance-constraint method                           
                                                                       * Fuzzy programming                                  
            * Exponential transformation                               * Classical robust optimization                      
            * Logarithmic transformation                               * Adaptive robust optimization                       
            * McCormick envelopes                                      * Data driven robust optimization                    
            * Piecewise linear approximation                           Optimization for Machine Learning and Data Analytics 
            * Spatial branch and bound method                                                                               
            Dynamic Programming                                        * Stochastic gradient descent                        
                                                                       * Momentum                                           
            * Markov decision process                                  * AdaGrad                                            
            * Bellman equation                                         * RMSProp                                            
            * Eight step procedures                                    * Adam                                               
            * Stochastic dynamic programming                           * Frank-Wolfe                                        
            Traditional Applications                                   * Sparse Reconstruction with Compressed Sensing      
                                                                       Emerging Applications                                
            * Facility location problem                                                                                     
            * Traveling salesman problem                               * Wing shape optimization                            
            * Set covering problem                                     * Optimization in game theory                        
            * Quadratic assignment problem                             * Quantum computing for optimization                 
            * Job shop scheduling                                                                                           
            * Newsvendor problem                                                                                            
            * Unit commitment problem                                                                                       
            * Portfolio optimization                                                                                        
                                                                                                                            
            

            Sponsor


            Retrieved from "https://optimization.cbe.cornell.edu/index.php?title=Main_Page&oldid=6709"

      Navigation menu

        Personal tools

            * Log in
            * Request account

          Namespaces

              * Main Page
              * Discussion
          English

          Views

              * Read
              * View source
              * View history
          More

        Navigation

            * Textbook Home
            * About This Text
            * Recent changes
            * Wiki Editing Help
            * Feedback (2021)
            * Feedback (2020)

        Tools

            * What links here
            * Related changes
            * Special pages
            * Printable version
            * Permanent link
            * Page information
      * This page was last edited on 9 October 2023, at 21:45.
      * Privacy policy
      * About Cornell University Computational Optimization Open Textbook - Optimization Wiki
      * Disclaimers
      * 
Welcome to the Cornell University Computational Optimization Open Textbook
This electronic textbook is a student-contributed open-source text covering a variety of topics on process optimization.
If you have any comments or suggestions on this open textbook, please contact Professor Fengqi You.
Main Page
https://optimization.cbe.cornell.edu/index.php
https://towardsdatascience.com/linear-programming-and-discrete-optimization-with-python-using-pulp-449f3c5f6e99
Linear programming and discrete optimization with Python using PuLP
2021-10-28T08:26:20Z
Tirthajyoti Sarkar
<html><body><div><div><div><h2>Linear and integer programming are key techniques for discrete optimization problems and they pop up pretty much everywhere in modern business and technology sectors. We will discuss how to tackle such problems using Python library PuLP and get a fast and robust solution.</h2><div><a href="https://medium.com/@tirthajyoti?source=post_page-----449f3c5f6e99--------------------------------"><div><p></p></div></a><a href="https://towardsdatascience.com/?source=post_page-----449f3c5f6e99--------------------------------"><div><p></p></div></a></div></div><h2>Introduction</h2><p><a href="https://neos-guide.org/optimization-tree">Discrete optimization</a> is a branch of optimization methodology which deals with discrete quantities i.e. non-continuous functions. It is quite ubiquitous in as diverse applications such as <a href="https://study.com/academy/lesson/financial-applications-of-linear-programs-for-portfolio-selection-financial-planning-financial-mix-strategy.html">financial investment</a>, <a href="https://neos-guide.org/content/diet-problem">diet planning</a>, <a href="https://www.quora.com/How-do-I-solve-a-manufacturing-problem-in-linear-programming">manufacturing processes</a>, and <a href="https://www2.cs.duke.edu/courses/fall10/cps296.1/joe_siyang.pdf">player or schedule selection for professional sports</a>.</p><p><strong>Linear and (mixed) integer programming</strong> are techniques to solve problems which can be formulated within the framework of discrete optimization.</p><p>Knowledge of such optimization techniques is extremely useful for data scientists and machine learning (ML) practitioners as discrete and continuous optimization lie at the heart of modern ML and AI systems as well as <a href="https://www.edx.org/course/optimization-methods-business-analytics-mitx-15-053x">data-driven business analytics processes</a>.</p><blockquote><p>There are many commercial optimizer tools, but having hands-on experience with a programmatic way of doing optimization is invaluable.</p></blockquote><p>There is a <a href="https://www.math.uni-bielefeld.de/documenta/vol-ismp/25_bixby-robert.pdf">long and rich history of the theoretical development of robust and efficient solvers</a> for optimization problems. However, focusing on practical applications, we will skip that history and move straight to the part of learning how to use programmatic tools to formulate and solve such optimization problems.</p><p>There are many excellent optimization packages in Python. In this article, we will specifically talk about <strong>PuLP</strong>. But before going to the Python library, let us get a sense of the kind of problem we can solve with it.</p><h2>An example problem (or two)</h2><p>Suppose you are <strong>in charge of the diet plan for high school lunch</strong>. Your job is to make sure that the students get the right balance of nutrition from the chosen food.</p><figure></figure></div></div></body></html>
Linear and integer programming are key techniques for discrete optimization problems and they pop up pretty much everywhere in modern business and technology sectors. We will discuss how to tackle such problems using Python library PuLP and get a fast and robust solution.                Introduction  Discrete optimization is a branch of optimization methodology which deals with discrete quantities i.e. non-continuous functions. It is quite ubiquitous in as diverse applications such as financial investment, diet planning, manufacturing processes, and player or schedule selection for professional sports.  Linear and (mixed) integer programming are techniques to solve problems which can be formulated within the framework of discrete optimization. Knowledge of such optimization techniques is extremely useful for data scientists and machine learning (ML) practitioners as discrete and continuous optimization lie at the heart of modern ML and AI systems as well as data-driven business analytics processes.  There are many commercial optimizer tools, but having hands-on experience with a programmatic way of doing optimization is invaluable.  There is a long and rich history of the theoretical development of robust and efficient solvers for optimization problems. However, focusing on practical applications, we will skip that history and move straight to the part of learning how to use programmatic tools to formulate and solve such optimization problems. There are many excellent optimization packages in Python. In this article, we will specifically talk about PuLP. But before going to the Python library, let us get a sense of the kind of problem we can solve with it. An example problem (or two) Suppose you are in charge of the diet plan for high school lunch. Your job is to make sure that the students get the right balance of nutrition from the chosen food.
Linear programming and discrete optimization with Python using PuLP
https://towardsdatascience.com/linear-programming-and-discrete-optimization-with-python-using-pulp-449f3c5f6e99
https://colleenyoung.org/a-level-16/a-level-further-mathematics/linear-programming/
Linear Programming
2020-03-15
None
<div><div>
	
<article>
	<div>
	<header><a href="https://colleenyoung.org/a-level-16-resources/a-level-further-mathematics/"><strong>Return to A Level Further Mathematics Menu</strong></a></header>
<header>…………………………………………………………..</header>
<div>
<p><a href="https://www.transum.org/Maths/Activity/Graph/Linear_Programming.asp"></a></p>
<p>I am pleased to see that a reminder of <a href="https://www.transum.org/Software/SW/Starter_of_the_day/Students/InequalitiesB.asp?Level=8"><strong>Inequalities</strong></a> is the first activity, something I always start with when teaching Linear Programming. Levels 1 to 5 provide 5 different problems providing very typical linear programming problems and we also have Exam Style Questions. The very generous Free model on Transum allows access to the extensive library of resources including checking answers such as illustrated here;  a subscription additionally provides answers to all of the pupil online exercises such as Exam Questions, quizzes and puzzles as well as additional benefits.</p>
<p>Students are required not just to solve these probems but to interpret solutions to such problems. For Linear Programming there are some excellent ways of using technology to help  learning. We can look at online utilities from <a href="https://www.zweigmedia.com/index.php?lang=en">zweigmedia</a> and the use of the Excel Solver.</p>
<div>
<p>This example from MEI (MEI Decision 1 Legacy Specimen Paper) will be used to illustrate the use of these tools.</p>
<p>A vet is treating a farm animal. He must provide minimum daily requirements of an antibiotic, a vitamin and a nutrient. He has two types of medicine available, tablets and liquid. The table summarises what the medicines contain and the requirements.<br />
<br />
The tablets cost £0.38 each and liquid medicine costs £1 per dose.<br />
The vet wants to find the cheapest way to treat the animal.<br />
We have x as the number of tablets which the vet prescribes per day, and y is the number of doses of liquid medicine, giving us the linear programming problem:<br />
Minimise    0.38x + y<br />
Subject to<br />
3x +   2y   ≥ 18<br />
2x +   4y   ≥ 16<br />
10x + 50y ≥ 100</p>
<p>Firstly we will look at zweigmedia’s <a href="http://www.zweigmedia.com/utilities/lpg/index.html?lang=en"><strong>Linear Programming Grapher</strong></a>. This is intuitive to use. Note the option to see examples. Fraction mode is selected here.<br />
Selecting Solve gives a clear solution illustrated graphically.</p>
<p><a href="http://www.zweigmedia.com/utilities/lpg/index.html?lang=en"></a></p>
<p>We see that the optimal solution, if x and y can take any values, is a cost of £3.20,<br />
with x = 20/3 and y = 2/3.</p>
<p><a href="http://www.zweigmedia.com/utilities/lpg/index.html?lang=en"></a></p>
<p>We could also solve the problem using the <a href="http://www.zweigmedia.com/simplex/simplex.php?lang=en"><strong>Simplex Tool</strong></a>. As well as a solution it is possible to see the simplex tableaus. The Simplex Tool is needed for any problems with more than two variables.<br />
</p>
<p>If we wish to restrict x and y to integers, we can turn to Excel and use Solver. This allows a choice of making x and y integer or not.</p>
<p>Using the same example, we can set up the problem in Excel.<br />
<strong><a href="https://mathematicsforstudents.files.wordpress.com/2018/03/vet-problem-with-excel-solver.xlsx">Vet Problem with Excel Solver</a> </strong>is the Excel spreadsheet with annotation to explain the answer report and for full instructions on setting up the spreadsheet, use this file:<br />
<strong><a href="https://mathematicsforstudents.files.wordpress.com/2018/03/solver-excel-to-solve-lp-problems-colleen-young.pdf">Solver Excel to solve LP problems – Colleen Young</a></strong></p>
<p><a href="https://mathematicsforstudents.files.wordpress.com/2018/03/vet-problem-with-excel-solver.xlsx"></a></p>
<p>and use Solver..</p>
<p><a href="https://mathematicsforstudents.files.wordpress.com/2018/03/vet-problem-with-excel-solver.xlsx"></a></p>
<p>We could choose to restrict x and y to integers with Solver.<br />
<br />
giving us the solution:<br />
</p>
<p>For a further example, this time a maximisation problem from Edexcel have a look at this Excel file, <strong><a href="https://mathematicsforstudents.files.wordpress.com/2018/03/badges-lp-edexcel.xlsx">Badges LP Edexcel.</a></strong> Each sheet in the workbook is fully annotated to explain the method.<br />
<br />
</p>
</div>
<p>A version of this post is also available for students on <a href="https://wordpress.com/post/mathematicsforstudents.wordpress.com/3617"><strong>Mathematics for Students</strong></a>. Note the excellent <a href="http://www.cimt.org.uk/projects/mepres/alevel/discrete_ch5.pdf"><strong>notes and examples on Linear Programming</strong></a> available from CIMT, one of a series of chapters on <a href="https://www.cimt.org.uk/projects/mepres/alevel/alevel.htm"><strong>Discrete Mathematics</strong></a>.</p>
</div>
	</div>
</article>
	</div>||||I|||| Mathematics, Learning and Technology

 Main menu

 Skip to content
 * Home
 * Lesson Planning
 + 5 Minute Lesson Plan
 + Lesson Planning Reference
 + Retrieval Practice
 + Starters
 + Starters – Posts
 + Knowledge Organisers
 + Lesson Activities
 + Misconceptions
 + Vocabulary
 + Homework
 + Tools & Calculators
 o Algebra Tiles
 o Bar Modelling
 o Calculators
 o GeoBoard Activities
 o PhET Sims – Index
 o PhET Simulations
 o Random Name Pickers
 o Wisweb Applets HTML5
 * Primary
 * KS3 (11-14)
 * GCSE/IGCSE/L2 Further Maths (14-16)
 + Number
 + Ratio
 + Algebra
 + Geometry
 + Probability and Statistics
 + GCSE Content
 + GCSE Content – Resources
 + AQA GCSE
 + AQA Level 2 Further Maths
 + Edexcel GCSE
 + OCR GCSE
 + IGCSE
 + Learning & Teaching GCSE Mathematics
 * A Level (16+)
 + GCSE to A Level Transition
 + Core Maths
 + A Level (16+) Resources
 + A Level Further Mathematics
 o Subject Content
 o Mapping Documents
 o Specifications, Sample & Practice Papers
 o Exam questions by topic
 o Teaching Resources
 o Decision Mathematics
 o Decision Mathematics – Teaching Resources
 o Further Calculus
 o Differential Equations
 o Linear Programming
 o Mechanics – Dimensional Analysis
 o Notes & Examples
 o Legacy Papers
 o Into the archives …
 + Mathematics for Science
 + Mathematics in Psychology
 + University Admissions Tests
 + Data Science
 * Problems & Activities
 + Problems & Activities – Links
 + Problems & Activities Resources
 + Examination Board Teaching Resources
 + Multiple Choice Questions
 + Great teaching toolkit: Evidence review
 + Exploration and Investigation with Technology
 + Mathematical Advent Calendars
 + Christmas Mathematics Resources
 + Happy New Year
 + Mathematics for Easter
 + World Book Day
 + For Valentine’s Day
 * Rich Tasks
 + Age 11-16
 + Age 16+
 + Underground Mathematics
 o Introduction
 o Underground Maths: A Level Mapping
 o Video Tutorials & How to Guide
 o Building Blocks
 o Review Questions GCSE 9-1
 o Coordinate Geometry
 o Save & Organise Favourite Resources
 o BCME 9 Conference Session
 * Resources
 + Resources – Index
 + Algebra
 + Geometry
 + Number
 + Ratio
 + Statistics
 o Probability Revision
 o Worked Exam Examples
 + Investigations
 o Links & Resources
 o Diffy
 o Happy Numbers
 o Pick’s Theorem
 o Palindromes
 + Standards Unit
 o S4 Understanding Mean, Median, Mode and Range
 + Excel Resources-Mike Hadden
 + Bingo
 + Dynamic Maths – David Watkins
 + Resourceaholic
 + JustMaths
 + Spot the Mistake
 + Tarsia Puzzles
 + TES Resources
 + STEM Learning
 + PowerPoint Collection
 o Algebra
 o Geometry
 o Number
 o Proof
 o Statistics
 + Autograph
 * Revision
 + Highlighting is a Waste of Time
 + MadAsMaths (16+)
 + UK A Level (16-18) Exam Questions & Solutions
 + GCSE Revision 2022
 + GCSE (14-16)
 + Chasing the highest grades?
 + Mini-Tests
 + Corbettmaths 5-a-day
 + Multiple Choice Questions
 + Building Blocks
 + Loop Activities / Treasure Hunts
 + Dynamic Maths
 + Diagnostic Exam Questions
 + MathsBox
 + For Students …
 + Other Revision Ideas – a collection
 * Use of Technology
 + Use of Technology – Introduction
 + Autograph
 o Introduction
 o Autograph – Web Version
 o Autograph – Useful Links
 o Numerical Methods
 o Transformations
 + Desmos
 o Desmos-Index
 o Getting Started
 o Desmos Slideshows
 o User Guide & Knowledge Base
 o YouTube Channel
 o Useful Links
 o Desmos – Standards Unit
 o Projector Mode
 o Share Pages
 o Sliders
 o Inequalities
 o Parametric Equations
 o Add an Image (and dance!)
 o Connect points
 o Activity Builder
 o Graph Art
 o Tangents to a Curve (& Folders)
 o Circle & Tangent
 o Transformations
 o Transformations – Advanced
 + GeoGebra
 o KS3 GeoGebra Activities
 o Tutorials
 o GeoGebra Resources – Edexcel
 o GeoGebra Resources – Nrich and MEI
 o GeoGebra Institute of MEI
 o Data Analysis
 o GeoGebra – Investigations and Problems
 + Graspable Math
 o User Guide
 o Graspable Math – Webinars
 o Activity Bank
 o Solving Equations
 o Formulas
 o Examples – Don Steward
 o Examples – Open Middle
 o Examples – Increasingly Difficult Questions
 + Math Whiteboard
 o Math Whiteboard – Introduction
 o Learn Math Whiteboard
 o Highlight equivalence
 + Maths White Board
 + Infinity Whiteboard
 + PhET Simulations
 + NCTM Illuminations
 + Standards Unit – Software
 + WolframAlpha
 o Introduction
 o Examples – Mathematics Syntax
 o Learn to use WolframAlpha
 o Widgets
 o Handwritten Style
 o Fun Curves
 o Fun Facts
 o Words with WolframAlpha
 o Handwriting Recognition
 + Interactives and Calculators
 + Mathigon
 + Apps
 * Calculators
 + Casio fx-991EX
 + Casio FX991EX-Classwiz
 + Casio Graphical Calculators
 + Texas Instruments
 + Mathematics for Students – Calculators
 * Reference
 * Reading
 + Blogs – Learning & Teaching
 + Books (free)
 + Mathematics Book Recommendations
 + Newsletters and Magazines
 + Reference
 + Research – Learning & Teaching
 + Research – Mathematics Learning & Teaching
 + Presentations
 o Assessment & Feedback
 o Low Stakes Testing in the Mathematics Classroom
 o Problem Solving
 o Problem Solving : 16-19
 o Top >10 Mathematics Websites
 o Good Mathematicians Can Go Backwards!
 o Resolutions for (Maths) Teachers
 o Learning with Technology
 o Diagnostic Questions – Create Quiz
 o Formulae GCSE (14-16)
 o Colour in Mathematics
 o Lesson Endings
 o ClassCharts – Record behaviour & seating plans
 o 11 Commandments
 o GeoBoards
 o Dijkstra’s Algorithm
 o Completing the Square
 o Equations – linear calculator
 o Calculus – mini test
 o Desmos
 o WolframAlpha
 o Somerset Training
 * Puzzles & Games
 + Reading
 + Collections
 + Puzzles
 + Logic
 + Vocabulary & Crossnumber
 + Nim
 + Counters
 + Tables
 + Number
 + Algebra
 + Geometry
 + Probability & Statistics
 + Pencil and Paper
 + Bingo
 + Memory Games
 + Underground Maths
 * I’m Looking For…
 + Site Index
 + Resources
 + Search Posts
 + All pages
 + Calculators & Tools
 + Mathematics Posters
 + Great Questions
 + Independent Homework
 + End of term activities
 + Younger Students
 + Videos
 + UK Assessment
 o Examinations 2023
 o Examinations – Mathematics November 2022
 o Exams & Assessments 2022
 o Results 2022
 o National Curriculum UK
 o Assessment Without Levels KS3 (11-14)
 o A Level
 - A Level Resources
 * Knowledge Organisers
 * TLMaths
 * Transition
 * Worked Examples – A Level
 * Underground Maths
 * MEI
 * Further Maths Support Network
 * STEM Learning
 * Nrich
 * Rich Starting Points (RISPS)
 * Edexcel
 * crashMaths
 * Check In Tests & More – OCR
 * The Standards Unit
 * TeachIt Maths
 * Dr Frost Maths
 * Multiple Choice Questions
 * 16+ Challenge Questions
 * Formulae
 - Mapping Documents
 - Specifications & Support
 - AQA
 - Edexcel
 - OCR (MEI)
 - OCR
 - Use of Technology
 - Statistics – Large Data Sets
 - Vocabulary & Notation
 o Mathematics for Science
 o Mathematics in Psychology
 o Examinations 2021
 o Results 2020
 o Results 2019
 o Results 2018
 o Analyse School Performance (DfE)
 o Progress 8
 o GCSE Predictions
 * About

 Linear Programming

 Return to A Level Further Mathematics Menu
 …………………………………………………………..
 From Transum, try Linear Programming which provides a really easy way for teachers to illustrate several Linear Programming problems. Students could try these as an online activity.

 I am pleased to see that a reminder of Inequalities is the first activity, something I always start with when teaching Linear Programming. Levels 1 to 5 provide 5 different problems providing very typical linear programming problems and we also have Exam Style Questions. The very generous Free model on Transum allows access to the extensive library of resources including checking answers such as illustrated here; a subscription additionally provides answers to all of the pupil online exercises such as Exam Questions, quizzes and puzzles as well as additional benefits.

 Students are required not just to solve these probems but to interpret solutions to such problems. For Linear Programming there are some excellent ways of using technology to help learning. We can look at online utilities from zweigmedia and the use of the Excel Solver.

 This example from MEI (MEI Decision 1 Legacy Specimen Paper) will be used to illustrate the use of these tools.

 A vet is treating a farm animal. He must provide minimum daily requirements of an antibiotic, a vitamin and a nutrient. He has two types of medicine available, tablets and liquid. The table summarises what the medicines contain and the requirements.

 The tablets cost £0.38 each and liquid medicine costs £1 per dose.
 The vet wants to find the cheapest way to treat the animal.
 We have x as the number of tablets which the vet prescribes per day, and y is the number of doses of liquid medicine, giving us the linear programming problem:
 Minimise 0.38x + y
 Subject to
 3x + 2y ≥ 18
 2x + 4y ≥ 16
 10x + 50y ≥ 100

 Firstly we will look at zweigmedia’s Linear Programming Grapher. This is intuitive to use. Note the option to see examples. Fraction mode is selected here.
 Selecting Solve gives a clear solution illustrated graphically.

 We see that the optimal solution, if x and y can take any values, is a cost of £3.20,
 with x = 20/3 and y = 2/3.

 We could also solve the problem using the Simplex Tool. As well as a solution it is possible to see the simplex tableaus. The Simplex Tool is needed for any problems with more than two variables.

 If we wish to restrict x and y to integers, we can turn to Excel and use Solver. This allows a choice of making x and y integer or not.

 Using the same example, we can set up the problem in Excel.
 Vet Problem with Excel Solver is the Excel spreadsheet with annotation to explain the answer report and for full instructions on setting up the spreadsheet, use this file:
 Solver Excel to solve LP problems – Colleen Young

 and use Solver..

 We could choose to restrict x and y to integers with Solver.

 giving us the solution:

 For a further example, this time a maximisation problem from Edexcel have a look at this Excel file, Badges LP Edexcel. Each sheet in the workbook is fully annotated to explain the method.


 A version of this post is also available for students on Mathematics for Students. Note the excellent notes and examples on Linear Programming available from CIMT, one of a series of chapters on Discrete Mathematics.

 Share this:

 * Twitter
 * More
 * 

 Like this:

 Like Loading...

 Featured Posts

 * Examinations 2023
 * Custom Maths Revision Starters
 * Rosenshine’s Principles in the Mathematics Classroom
 * Good Mathematicians Can Go Backwards!
 * Fill in the blanks …
 * Here’s the diagram…
 * Literacy Skills in Mathematics
 * Knowledge Organisers – Mathematics
 Search

 Search posts by category

 Search posts by category Select Category Algebra Applets Apps Assessment Astronomy Aural Books Calculus Christmas Coding Decision Mathematics Desmos diagnostic questions Diagrams End of term activities Enrichment Excel Feedback For students Further Mathematics A Level Games & Puzzles GeoGebra Geometry Graphs Graspable Math Have you seen…? Homework IWB KS3 Learning Lesson Planning Mathematical Miscellany Mathematics Maths At Home Mechanics News Notes Number Online Tools Online Whiteboards Presentations Probability Questions Ratio Reading Reference Resolutions for Maths Teachers Resources Revision Rich Tasks Starters Statistics Teaching Testing Underground Mathematics Videos Web2.0 WolframAlpha

 Links

 * Calculators & Tools
 * Facebook Page
 * Mathematics blog for students

 Email Subscription

 Enter your email address to follow this blog and receive notifications of new posts by email.

 Email Address

 Sign me up!

 RSS Links

 * RSS - Posts
 * RSS - Comments

 Mathematics for Students

 For Christmas…

 University Admissions Tests

 Reading

 Top Posts & Pages (last 48 hours)

 This slideshow requires JavaScript.

 Previous Posts

 Previous Posts Select Month February 2023 January 2023 December 2022 November 2022 October 2022 September 2022 August 2022 July 2022 June 2022 May 2022 April 2022 March 2022 February 2022 January 2022 December 2021 November 2021 October 2021 September 2021 August 2021 July 2021 June 2021 May 2021 April 2021 March 2021 February 2021 January 2021 December 2020 November 2020 October 2020 September 2020 August 2020 July 2020 June 2020 May 2020 April 2020 March 2020 February 2020 January 2020 December 2019 November 2019 October 2019 September 2019 August 2019 July 2019 June 2019 May 2019 April 2019 March 2019 February 2019 January 2019 December 2018 November 2018 October 2018 September 2018 August 2018 July 2018 June 2018 May 2018 April 2018 March 2018 February 2018 January 2018 December 2017 November 2017 October 2017 September 2017 August 2017 July 2017 June 2017 May 2017 April 2017 March 2017 February 2017 January 2017 December 2016 November 2016 October 2016 September 2016 August 2016 July 2016 June 2016 May 2016 April 2016 March 2016 February 2016 January 2016 December 2015 November 2015 October 2015 September 2015 August 2015 July 2015 June 2015 May 2015 April 2015 March 2015 February 2015 January 2015 December 2014 November 2014 October 2014 September 2014 August 2014 July 2014 June 2014 May 2014 April 2014 March 2014 February 2014 January 2014 December 2013 November 2013 October 2013 September 2013 August 2013 July 2013 June 2013 May 2013 April 2013 March 2013 February 2013 January 2013 December 2012 November 2012 October 2012 September 2012 August 2012 July 2012 June 2012 May 2012 April 2012 March 2012 February 2012 January 2012 December 2011 November 2011 October 2011 September 2011 August 2011 July 2011 June 2011 May 2011 April 2011 March 2011 February 2011 January 2011 December 2010 November 2010 September 2010 July 2010 May 2010 April 2010 February 2010 November 2009 October 2009 September 2009 August 2009 May 2009 February 2009 January 2009
 February 2023
 M T W T F S S 
 1 2 3 4 5 
 6 7 8 9 10 11 12
 13 14 15 16 17 18 19
 20 21 22 23 24 25 26
 27 28 
 
 « Jan
 Powered by WordPress.com.
 %d bloggers like this:
Return to A Level Further Mathematics Menu  
…………………………………………………………..
   
I am pleased to see that a reminder of  Inequalities  is the first activity, something I always start with when teaching Linear Programming. Levels 1 to 5 provide 5 different problems providing very typical linear programming problems and we also have Exam Style Questions. The very generous Free model on Transum allows access to the extensive library of resources including checking answers such as illustrated here;  a subscription additionally provides answers to all of the pupil online exercises such as Exam Questions, quizzes and puzzles as well as additional benefits.
Students are required not just to solve these probems but to interpret solutions to such problems. For Linear Programming there are some excellent ways of using technology to help  learning. We can look at online utilities from zweigmedia and the use of the Excel Solver.
This example from MEI (MEI Decision 1 Legacy Specimen Paper) will be used to illustrate the use of these tools.
A vet is treating a farm animal. He must provide minimum daily requirements of an antibiotic, a vitamin and a nutrient. He has two types of medicine available, tablets and liquid. The table summarises what the medicines contain and the requirements.
The tablets cost £0.38 each and liquid medicine costs £1 per dose.
The vet wants to find the cheapest way to treat the animal.
We have x as the number of tablets which the vet prescribes per day, and y is the number of doses of liquid medicine, giving us the linear programming problem:
Minimise    0.38x + y
Subject to
3x +   2y   ≥ 18
2x +   4y   ≥ 16
10x + 50y ≥ 100
Firstly we will look at zweigmedia’s  Linear Programming Grapher . This is intuitive to use. Note the option to see examples. Fraction mode is selected here.
Selecting Solve gives a clear solution illustrated graphically.
   
We see that the optimal solution, if x and y can take any values, is a cost of £3.20,
with x = 20/3 and y = 2/3.
   
We could also solve the problem using the  Simplex Tool . As well as a solution it is possible to see the simplex tableaus. The Simplex Tool is needed for any problems with more than two variables.
If we wish to restrict x and y to integers, we can turn to Excel and use Solver. This allows a choice of making x and y integer or not.
Using the same example, we can set up the problem in Excel.
 Vet Problem with Excel Solver is the Excel spreadsheet with annotation to explain the answer report and for full instructions on setting up the spreadsheet, use this file:
 Solver Excel to solve LP problems – Colleen Young  
   
and use Solver..
   
We could choose to restrict x and y to integers with Solver.
giving us the solution:
For a further example, this time a maximisation problem from Edexcel have a look at this Excel file,  Badges LP Edexcel.  Each sheet in the workbook is fully annotated to explain the method.
A version of this post is also available for students on  Mathematics for Students . Note the excellent  notes and examples on Linear Programming  available from CIMT, one of a series of chapters on  Discrete Mathematics .
Linear Programming
https://colleenyoung.org/a-level-16/a-level-further-mathematics/linear-programming/
https://www.fm-magazine.com/issues/2019/feb/linear-programming-microsoft-excel.html
Solve problems with linear programming and Excel
2019-02-01
Clarence Goh; Ph D
<div><div>
 <article><header>
 
 
 Management accountants tasked with figuring out the way to make the most of limited resources can employ a form of mathematical optimisation to determine the best approach.
 
 
 
 
</header>
<figure>
 
 
 
 
</figure>
<div>
 <p>A management accountant's knowledge of relevant revenues and costs is important for many decisions, among them capital budgeting, outsourcing, special orders, product mix, and the adding or dropping of specific product lines. Many of these decisions require management accountants to determine or recommend specific courses of action that would lead to an optimal outcome (such as maximising profits or minimising costs) given a limited set of resources (such as production inputs). It is therefore important that they apply appropriate analytical techniques in approaching such decisions. Linear programming is one technique that accountants can often readily apply to determine the best outcome in these situations.</p>
<p>This article provides a description of linear programming, demonstrates how it can be performed using Microsoft Excel's free Solver add-in, and illustrates its use through an example from management accounting.</p>
<p>Linear programming</p>
<p>Linear programming is a form of mathematical optimisation that seeks to determine the best way of using limited resources to achieve a given objective. The key elements of a linear programming problem include:</p>
<ul>
<li><b>Decision variables:</b> Decision variables are often unknown when initially approaching the problem. These variables usually represent identifiable "things" or inputs that a manager can control (ie, how many of each specific model of washing machines to produce). The goal, then, is to determine those values that maximise or minimise the objective function.</li>
<li><b>Objective function:</b> This is a math-ematical function that incorporates decision variables to express a manager's goals. A manager's goal is to either maximise or minimise the objective function.</li>
<li><b>Constraints:</b> These are mathematical functions that incorporate decision variables to express boundaries on possible solutions.</li>
<li><b>Variable bounds:</b> Decision variables are rarely allowed to take on any value (from minus infinity to plus infinity). Instead, they usually have bounds (eg, ≥ 0).</li>
</ul>
<p>It should also be noted that while all the mathematical expressions for the objective function and constraints in linear programming are necessarily linear in nature (hence the name; see the sidebar "Limitations of Linear Programming" at the bottom of the page), the technique remains one of the most widely used methods of optimisation, and the largest and most complex linear programming problems have millions of decision variables and hundreds of thousands of constraints.</p>
<p>Before we continue, it's important to note that this article is not intended to be an exhaustive course in linear programming. It's instead an introduction to the topic and how the Excel Solver add-in can be used to help with this type of complex problem.</p>
<p>The example below demonstrates how a management accountant could use the Solver tool to perform linear programming to determine an optimal product mix that maximises profits given a limited set of resources. This example provides one setting where linear programming can be applied. The technique can be used in many other accounting and business settings to help decision-makers determine optimal outcomes given limited resources.</p>
<hr />
<p><b>Mathematical representation of Beacon's business problem</b></p>
</div>
<div><p></p>
</div>
<div>
 <p><br />
An example from management accounting</p>
<p>Beacon Co. is a manufacturer of washing machines. It currently sells two models of washing machines: the Arkel and the Kallex. At the start of every production cycle, Beacon must decide how many units of each washing machine to produce, given its available resources. In the coming production cycle, Beacon faces key resource constraints. In particular, it has only 3,132 hours of labour, 1,440 feet of rubber hosing, and 200 drums available.</p>
<p>Selling each Arkel unit earns the company a profit of $350 while selling each Kallex unit earns the company a profit of $300. At the same time, manufacturing each Arkel unit requires 18 hours of labour, 6 feet of rubber hosing, and 1 drum, while manufacturing each Kallex unit requires 12 hours of labour, 8 feet of rubber hosing, and 1 drum. Details of the relevant facts are summarised in the table "Summary of Production of Washing Machines".</p>
<p>Based on these facts and the assumption that 100% of production will be sold, Beacon must decide how many units of each washing machine to produce in the coming production run to maximise profits.</p>
<hr />
<p><b>Summary of production of washing machines</b></p>
</div>
<div><p></p>
</div>
<div>
 <p><br />
Doing linear programming in Excel</p>
<p>The first step in linear programming is to develop a mathematical representation of the business problem and to model it on a spreadsheet. Mathematically, the problem in the example can be represented as shown in the chart "Mathematical Representation of Beacon's Business Problem", where X<sub>1</sub> and X<sub>2</sub> represent the decision variables, that is, the number of Arkel and Kallex units produced, respectively.</p>
<p>Next, we implement the mathematical model in an Excel spreadsheet. See the table "Spreadsheet Model" for the spreadsheet model used, and the table "Excel Formulas" for details of the formulas used in the model.</p>
<hr />
<p><b>Spreadsheet model</b></p>
</div>
<div><p></p>
</div>
<div><div><p></p>
</div>
 <div><p>You can also download an Excel file with the Spreadsheet Model <b><a href="https://www.fm-magazine.com/content/dam/fmm/issues/2019/feb/spreadsheet-model.xlsx">here</a></b>. X<sub>1</sub> and X<sub>2</sub> are represented in cells C3 and D3. The values of these decision variables are unknown at the start of the problem. The unit profits expected from the sale of each unit of Arkel and Kallex are entered in cells C4 and D4. Cell E4 represents the <i>objective function</i> (which is to maximise profits) and calculates the total profit that Beacon can expect in this production cycle based on the corresponding production quantity and unit profit information in cells C3:D4.</p>
</div>
 </div>
<div>
 <p><br />
Cells C7:C9 contain the amount of each production input required in the production of each unit of Arkel, while cells D7:D9 contain the amount of each production input required in the production of each unit of Kallex. Cells E7:E9 calculate the total amounts of each production input that will be used in the production cycle based on the corresponding number of units of Arkel and Kallex that are produced. Cells F7:F9 contain the total amount of each production input available to Beacon in this production cycle. Together, cells E7:E9 and F7:F9 represent the drum, labour, and rubber hosing <i>constraint functions</i> stated in our original mathematical model. Specifically, cells E7:E9 represent the left-hand side of the constraint functions while cells F7:F9 represent the right-hand side of the constraint functions.</p>
<p>Having implemented the mathematical model in the spreadsheet, we can then use Solver to find the optimal solution to the problem. Solver, as mentioned earlier in the article, is a free Excel add-in that must be installed before it can be launched (see <a href="https://support.office.com/en-us/article/load-the-solver-add-in-in-excel-612926fc-d53b-46b4-872c-e24772f078ca">support.office.com</a> for instructions). Once the add-in is installed in Excel, go to <b>Data</b> → <b>Analysis</b> → <b>Solver</b>.</p>
<hr />
<p><b>Solver parameters</b></p>
</div>
<div><p></p>
</div>
<div>
 <p><br />
The Solver parameter inputs used in our example are shown in the screenshot "Solver Parameters". In Solver, we need to define three key components of our spreadsheet model. First, we need to define an objective cell (and whether its value should be maximised or minimised). This cell should correspond to the cell in the spreadsheet that represents the <i>objective function</i> in the mathematical model. Second, we need to define variable cells. These cells should correspond to cells in the spreadsheet that represent <i>decision variables</i> in the mathematical model. Third, we need to define constraints. These cells should correspond to cells in the spreadsheet that represent the various constraint functions in the mathematical model. Further, indicating that unconstrained variables should be non-negative sets the decision variable bound where both X1 and X2 are greater than or equal to 0. Given that we are executing linear programming, we select Simplex LP as the solving method in Solver.</p>
<p>Once these input parameters have been defined, click "Solve" to instruct Solver to solve for an optimal allocation of production between Arkel and Kallex that maximises profits.</p>
<p>The table "Spreadsheet Model — With Solver Solution" presents the Solver solution to our example. Solver automatically solves for the number of units of Arkel and Kallex washing machines that Beacon should produce to meet the stated objective of maximising profits. Our spreadsheet indicates that Beacon should produce 122 units of Arkel and 78 units of Kallex washing machines (cells C3 and D3), leading to an optimised profit of $66,100 (cell E4).</p>
<hr />
<p><b>Spreadsheet model — with solver solution</b></p>
</div>
<div><p></p>
</div>
<div>
 <p><br />
Proving its value</p>
<p>Linear programming, as demonstrated by applying Excel's Solver feature, is a viable and cost-effective tool for analysing multi-variable financial and operational problems.</p>
<p>In the example, it was unclear at the outset what the optimal production quantity of each washing machine was given the stated objective of profit maximisation. An intuitive response might have been to focus all production on the washing machine that provides the greater profits per unit (ie, Arkel). However, because of the resource constraints in our example, following such an intuition would not have led to a situation where profits are maximised. Instead, relying on linear programming to analyse the business problem leads to a production mix that definitively maximises profits. While this example is simple, it is reflective of many more complex real-life scenarios in which accountants face situations that require them to fulfil a variety of business objectives while contending with practical constraints. Where required, the modelling can be scaled up to deal with more complicated business problems.</p>
<hr /><p>Limitations of linear programming</p>
<p>Linear programming is one of several optimisation techniques that can be employed to determine the most efficient way to use resources. While it is a powerful technique that can be applied to many business situations, it should only be used to solve optimisation problems that involve a single linear objective function and linear constraints that <i>cannot</i> be violated.</p>
<p>There may be situations where linear programming may not be the most appropriate optimisation technique to employ. For example, where optimisation problems involve multiple objectives, nonlinear objective functions and/or constraints, or soft constraints (that can be violated) rather than hard constraints (that cannot be violated), other more appropriate optimisation techniques such as multiple objective linear programming, goal programming, or nonlinear programming should be identified and employed instead.</p>
<hr />
<p><i><b>Clarence Goh, CA (Singapore), Ph.D.</b>, is an assistant professor of accounting (practice) and director of professional development for the School of Accountancy at Singapore Management University. To comment on this article or to suggest an idea for another article, contact Jeff Drew, an </i>FM<i> magazine senior editor, at <a href="mailto:Jeff.Drew@aicpa-cima.com">Jeff.Drew@aicpa-cima.com</a>.</i></p>
</div>
</article>
</div>||||I|||| This site uses cookies to store information on your computer. Some are essential to make our site work; others help us improve the user experience. By using the site, you consent to the placement of these cookies. Read our privacy policy to learn more.

 close this window
 Advertisement
 Menu
 Search
 Close
 * HOME
 * ARTICLES
 * COVID-19
 * LEADERSHIP
 * TECH
 * STRATEGY
 * Digital Edition
 * Podcast
 Visit Our Sites
 * Association
 * CIMA
 * AICPA
 * CGMA
 * Store
 * Competency & Learning
 Search Search

 Solve problems with linear programming and Excel

 Management accountants tasked with figuring out the way to make the most of limited resources can employ a form of mathematical optimisation to determine the best approach. By Clarence Goh, Ph.D.
 * Technology and analytics
 * Excel

 A management accountant's knowledge of relevant revenues and costs is important for many decisions, among them capital budgeting, outsourcing, special orders, product mix, and the adding or dropping of specific product lines. Many of these decisions require management accountants to determine or recommend specific courses of action that would lead to an optimal outcome (such as maximising profits or minimising costs) given a limited set of resources (such as production inputs). It is therefore important that they apply appropriate analytical techniques in approaching such decisions. Linear programming is one technique that accountants can often readily apply to determine the best outcome in these situations.

 This article provides a description of linear programming, demonstrates how it can be performed using Microsoft Excel's free Solver add-in, and illustrates its use through an example from management accounting.

 Linear programming

 Linear programming is a form of mathematical optimisation that seeks to determine the best way of using limited resources to achieve a given objective. The key elements of a linear programming problem include:

 * Decision variables: Decision variables are often unknown when initially approaching the problem. These variables usually represent identifiable "things" or inputs that a manager can control (ie, how many of each specific model of washing machines to produce). The goal, then, is to determine those values that maximise or minimise the objective function.
 * Objective function: This is a math -ematical function that incorporates decision variables to express a manager's goals. A manager's goal is to either maximise or minimise the objective function.
 * Constraints: These are mathematical functions that incorporate decision variables to express boundaries on possible solutions.
 * Variable bounds: Decision variables are rarely allowed to take on any value (from minus infinity to plus infinity). Instead, they usually have bounds (eg, ≥ 0).

 It should also be noted that while all the mathematical expressions for the objective function and constraints in linear programming are necessarily linear in nature (hence the name; see the sidebar "Limitations of Linear Programming" at the bottom of the page), the technique remains one of the most widely used methods of optimisation, and the largest and most complex linear programming problems have millions of decision variables and hundreds of thousands of constraints.

 Before we continue, it's important to note that this article is not intended to be an exhaustive course in linear programming. It's instead an introduction to the topic and how the Excel Solver add-in can be used to help with this type of complex problem.

 The example below demonstrates how a management accountant could use the Solver tool to perform linear programming to determine an optimal product mix that maximises profits given a limited set of resources. This example provides one setting where linear programming can be applied. The technique can be used in many other accounting and business settings to help decision-makers determine optimal outcomes given limited resources.

 Mathematical representation of Beacon's business problem


 An example from management accounting

 Beacon Co. is a manufacturer of washing machines. It currently sells two models of washing machines: the Arkel and the Kallex. At the start of every production cycle, Beacon must decide how many units of each washing machine to produce, given its available resources. In the coming production cycle, Beacon faces key resource constraints. In particular, it has only 3,132 hours of labour, 1,440 feet of rubber hosing, and 200 drums available.

 Selling each Arkel unit earns the company a profit of $350 while selling each Kallex unit earns the company a profit of $300. At the same time, manufacturing each Arkel unit requires 18 hours of labour, 6 feet of rubber hosing, and 1 drum, while manufacturing each Kallex unit requires 12 hours of labour, 8 feet of rubber hosing, and 1 drum. Details of the relevant facts are summarised in the table "Summary of Production of Washing Machines".

 Based on these facts and the assumption that 100% of production will be sold, Beacon must decide how many units of each washing machine to produce in the coming production run to maximise profits.

 Summary of production of washing machines


 Doing linear programming in Excel

 The first step in linear programming is to develop a mathematical representation of the business problem and to model it on a spreadsheet. Mathematically, the problem in the example can be represented as shown in the chart "Mathematical Representation of Beacon's Business Problem", where X1 and X2 represent the decision variables, that is, the number of Arkel and Kallex units produced, respectively.

 Next, we implement the mathematical model in an Excel spreadsheet. See the table "Spreadsheet Model" for the spreadsheet model used, and the table "Excel Formulas" for details of the formulas used in the model.

 Spreadsheet model

 Excel formulas

 You can also download an Excel file with the Spreadsheet Model here. X1 and X2 are represented in cells C3 and D3. The values of these decision variables are unknown at the start of the problem. The unit profits expected from the sale of each unit of Arkel and Kallex are entered in cells C4 and D4. Cell E4 represents the objective function (which is to maximise profits) and calculates the total profit that Beacon can expect in this production cycle based on the corresponding production quantity and unit profit information in cells C3:D4.


 Cells C7:C9 contain the amount of each production input required in the production of each unit of Arkel, while cells D7:D9 contain the amount of each production input required in the production of each unit of Kallex. Cells E7:E9 calculate the total amounts of each production input that will be used in the production cycle based on the corresponding number of units of Arkel and Kallex that are produced. Cells F7:F9 contain the total amount of each production input available to Beacon in this production cycle. Together, cells E7:E9 and F7:F9 represent the drum, labour, and rubber hosing constraint functions stated in our original mathematical model. Specifically, cells E7:E9 represent the left-hand side of the constraint functions while cells F7:F9 represent the right-hand side of the constraint functions.

 Having implemented the mathematical model in the spreadsheet, we can then use Solver to find the optimal solution to the problem. Solver, as mentioned earlier in the article, is a free Excel add-in that must be installed before it can be launched (see support.office.com for instructions). Once the add-in is installed in Excel, go to Data → Analysis → Solver.

 Solver parameters


 The Solver parameter inputs used in our example are shown in the screenshot "Solver Parameters". In Solver, we need to define three key components of our spreadsheet model. First, we need to define an objective cell (and whether its value should be maximised or minimised). This cell should correspond to the cell in the spreadsheet that represents the objective function in the mathematical model. Second, we need to define variable cells. These cells should correspond to cells in the spreadsheet that represent decision variables in the mathematical model. Third, we need to define constraints. These cells should correspond to cells in the spreadsheet that represent the various constraint functions in the mathematical model. Further, indicating that unconstrained variables should be non-negative sets the decision variable bound where both X 1 and X 2 are greater than or equal to 0. Given that we are executing linear programming, we select Simplex LP as the solving method in Solver.

 Once these input parameters have been defined, click "Solve" to instruct Solver to solve for an optimal allocation of production between Arkel and Kallex that maximises profits.

 The table "Spreadsheet Model — With Solver Solution" presents the Solver solution to our example. Solver automatically solves for the number of units of Arkel and Kallex washing machines that Beacon should produce to meet the stated objective of maximising profits. Our spreadsheet indicates that Beacon should produce 122 units of Arkel and 78 units of Kallex washing machines (cells C3 and D3), leading to an optimised profit of $66,100 (cell E4).

 Spreadsheet model — with solver solution


 Proving its value

 Linear programming, as demonstrated by applying Excel's Solver feature, is a viable and cost-effective tool for analysing multi-variable financial and operational problems.

 In the example, it was unclear at the outset what the optimal production quantity of each washing machine was given the stated objective of profit maximisation. An intuitive response might have been to focus all production on the washing machine that provides the greater profits per unit (ie, Arkel). However, because of the resource constraints in our example, following such an intuition would not have led to a situation where profits are maximised. Instead, relying on linear programming to analyse the business problem leads to a production mix that definitively maximises profits. While this example is simple, it is reflective of many more complex real-life scenarios in which accountants face situations that require them to fulfil a variety of business objectives while contending with practical constraints. Where required, the modelling can be scaled up to deal with more complicated business problems.

 Limitations of linear programming

 Linear programming is one of several optimisation techniques that can be employed to determine the most efficient way to use resources. While it is a powerful technique that can be applied to many business situations, it should only be used to solve optimisation problems that involve a single linear objective function and linear constraints that cannot be violated.

 There may be situations where linear programming may not be the most appropriate optimisation technique to employ. For example, where optimisation problems involve multiple objectives, nonlinear objective functions and/or constraints, or soft constraints (that can be violated) rather than hard constraints (that cannot be violated), other more appropriate optimisation techniques such as multiple objective linear programming, goal programming, or nonlinear programming should be identified and employed instead.

 Clarence Goh, CA (Singapore), Ph.D., is an assistant professor of accounting (practice) and director of professional development for the School of Accountancy at Singapore Management University. To comment on this article or to suggest an idea for another article, contact Jeff Drew, an FM magazine senior editor, at Jeff.Drew@aicpa-cima.com.

 Advertisement

 MOST POPULAR

 Advertisement

 Related Articles

 Related Resources

 Association of International Certified Professional Accountants

 FM is published by the Association of International Certified Professional Accountants, the most influential body of professional accountants, combining the strengths of the American Institute of CPAs (AICPA) and The Chartered Institute of Management Accountants (CIMA) to power opportunity, trust and prosperity for people, businesses and economies worldwide.

 About FM

 * Contact us
 * Advertise
 * News
 * Podcast
 * Site map

 Our Websites

 * Association
 * CIMA
 * AICPA
 * CGMA
 * Store
 * Competency & Learning

 Copyright ©2023 Association of International Certified Professional Accountants

 * FM site privacy policy
 * FM site terms and conditions
Management accountants tasked with figuring out the way to make the most of limited resources can employ a form of mathematical optimisation to determine the best approach.
 
 
 
 
 
 
 
 
 A management accountant's knowledge of relevant revenues and costs is important for many decisions, among them capital budgeting, outsourcing, special orders, product mix, and the adding or dropping of specific product lines. Many of these decisions require management accountants to determine or recommend specific courses of action that would lead to an optimal outcome (such as maximising profits or minimising costs) given a limited set of resources (such as production inputs). It is therefore important that they apply appropriate analytical techniques in approaching such decisions. Linear programming is one technique that accountants can often readily apply to determine the best outcome in these situations.
This article provides a description of linear programming, demonstrates how it can be performed using Microsoft Excel's free Solver add-in, and illustrates its use through an example from management accounting.
Linear programming
Linear programming is a form of mathematical optimisation that seeks to determine the best way of using limited resources to achieve a given objective. The key elements of a linear programming problem include:
 Decision variables: Decision variables are often unknown when initially approaching the problem. These variables usually represent identifiable "things" or inputs that a manager can control (ie, how many of each specific model of washing machines to produce). The goal, then, is to determine those values that maximise or minimise the objective function.
 Objective function: This is a math-ematical function that incorporates decision variables to express a manager's goals. A manager's goal is to either maximise or minimise the objective function.
 Constraints: These are mathematical functions that incorporate decision variables to express boundaries on possible solutions.
 Variable bounds: Decision variables are rarely allowed to take on any value (from minus infinity to plus infinity). Instead, they usually have bounds (eg, ≥ 0).
It should also be noted that while all the mathematical expressions for the objective function and constraints in linear programming are necessarily linear in nature (hence the name; see the sidebar "Limitations of Linear Programming" at the bottom of the page), the technique remains one of the most widely used methods of optimisation, and the largest and most complex linear programming problems have millions of decision variables and hundreds of thousands of constraints.
Before we continue, it's important to note that this article is not intended to be an exhaustive course in linear programming. It's instead an introduction to the topic and how the Excel Solver add-in can be used to help with this type of complex problem.
The example below demonstrates how a management accountant could use the Solver tool to perform linear programming to determine an optimal product mix that maximises profits given a limited set of resources. This example provides one setting where linear programming can be applied. The technique can be used in many other accounting and business settings to help decision-makers determine optimal outcomes given limited resources.
 Mathematical representation of Beacon's business problem 
  
  
An example from management accounting
Beacon Co. is a manufacturer of washing machines. It currently sells two models of washing machines: the Arkel and the Kallex. At the start of every production cycle, Beacon must decide how many units of each washing machine to produce, given its available resources. In the coming production cycle, Beacon faces key resource constraints. In particular, it has only 3,132 hours of labour, 1,440 feet of rubber hosing, and 200 drums available.
Selling each Arkel unit earns the company a profit of $350 while selling each Kallex unit earns the company a profit of $300. At the same time, manufacturing each Arkel unit requires 18 hours of labour, 6 feet of rubber hosing, and 1 drum, while manufacturing each Kallex unit requires 12 hours of labour, 8 feet of rubber hosing, and 1 drum. Details of the relevant facts are summarised in the table "Summary of Production of Washing Machines".
Based on these facts and the assumption that 100% of production will be sold, Beacon must decide how many units of each washing machine to produce in the coming production run to maximise profits.
 Summary of production of washing machines 
  
  
Doing linear programming in Excel
The first step in linear programming is to develop a mathematical representation of the business problem and to model it on a spreadsheet. Mathematically, the problem in the example can be represented as shown in the chart "Mathematical Representation of Beacon's Business Problem", where X1 and X2 represent the decision variables, that is, the number of Arkel and Kallex units produced, respectively.
Next, we implement the mathematical model in an Excel spreadsheet. See the table "Spreadsheet Model" for the spreadsheet model used, and the table "Excel Formulas" for details of the formulas used in the model.
 Spreadsheet model 
  
   
  You can also download an Excel file with the Spreadsheet Model  here . X1 and X2 are represented in cells C3 and D3. The values of these decision variables are unknown at the start of the problem. The unit profits expected from the sale of each unit of Arkel and Kallex are entered in cells C4 and D4. Cell E4 represents the objective function (which is to maximise profits) and calculates the total profit that Beacon can expect in this production cycle based on the corresponding production quantity and unit profit information in cells C3:D4.
 
  
Cells C7:C9 contain the amount of each production input required in the production of each unit of Arkel, while cells D7:D9 contain the amount of each production input required in the production of each unit of Kallex. Cells E7:E9 calculate the total amounts of each production input that will be used in the production cycle based on the corresponding number of units of Arkel and Kallex that are produced. Cells F7:F9 contain the total amount of each production input available to Beacon in this production cycle. Together, cells E7:E9 and F7:F9 represent the drum, labour, and rubber hosing constraint functions stated in our original mathematical model. Specifically, cells E7:E9 represent the left-hand side of the constraint functions while cells F7:F9 represent the right-hand side of the constraint functions.
Having implemented the mathematical model in the spreadsheet, we can then use Solver to find the optimal solution to the problem. Solver, as mentioned earlier in the article, is a free Excel add-in that must be installed before it can be launched (see support.office.com for instructions). Once the add-in is installed in Excel, go to Data → Analysis → Solver.
 Solver parameters 
  
  
The Solver parameter inputs used in our example are shown in the screenshot "Solver Parameters". In Solver, we need to define three key components of our spreadsheet model. First, we need to define an objective cell (and whether its value should be maximised or minimised). This cell should correspond to the cell in the spreadsheet that represents the objective function in the mathematical model. Second, we need to define variable cells. These cells should correspond to cells in the spreadsheet that represent decision variables in the mathematical model. Third, we need to define constraints. These cells should correspond to cells in the spreadsheet that represent the various constraint functions in the mathematical model. Further, indicating that unconstrained variables should be non-negative sets the decision variable bound where both X1 and X2 are greater than or equal to 0. Given that we are executing linear programming, we select Simplex LP as the solving method in Solver.
Once these input parameters have been defined, click "Solve" to instruct Solver to solve for an optimal allocation of production between Arkel and Kallex that maximises profits.
The table "Spreadsheet Model — With Solver Solution" presents the Solver solution to our example. Solver automatically solves for the number of units of Arkel and Kallex washing machines that Beacon should produce to meet the stated objective of maximising profits. Our spreadsheet indicates that Beacon should produce 122 units of Arkel and 78 units of Kallex washing machines (cells C3 and D3), leading to an optimised profit of $66,100 (cell E4).
 Spreadsheet model — with solver solution 
  
  
Proving its value
Linear programming, as demonstrated by applying Excel's Solver feature, is a viable and cost-effective tool for analysing multi-variable financial and operational problems.
In the example, it was unclear at the outset what the optimal production quantity of each washing machine was given the stated objective of profit maximisation. An intuitive response might have been to focus all production on the washing machine that provides the greater profits per unit (ie, Arkel). However, because of the resource constraints in our example, following such an intuition would not have led to a situation where profits are maximised. Instead, relying on linear programming to analyse the business problem leads to a production mix that definitively maximises profits. While this example is simple, it is reflective of many more complex real-life scenarios in which accountants face situations that require them to fulfil a variety of business objectives while contending with practical constraints. Where required, the modelling can be scaled up to deal with more complicated business problems.
 Limitations of linear programming
Linear programming is one of several optimisation techniques that can be employed to determine the most efficient way to use resources. While it is a powerful technique that can be applied to many business situations, it should only be used to solve optimisation problems that involve a single linear objective function and linear constraints that cannot be violated.
There may be situations where linear programming may not be the most appropriate optimisation technique to employ. For example, where optimisation problems involve multiple objectives, nonlinear objective functions and/or constraints, or soft constraints (that can be violated) rather than hard constraints (that cannot be violated), other more appropriate optimisation techniques such as multiple objective linear programming, goal programming, or nonlinear programming should be identified and employed instead.
  Clarence Goh, CA (Singapore), Ph.D., is an assistant professor of accounting (practice) and director of professional development for the School of Accountancy at Singapore Management University. To comment on this article or to suggest an idea for another article, contact Jeff Drew, an FM magazine senior editor, at Jeff.Drew@aicpa-cima.com.
Solve problems with linear programming and Excel
https://www.fm-magazine.com/issues/2019/feb/linear-programming-microsoft-excel.html
https://secure.mysimplexes.com/
Agent Portal : Login
None
None
<div><div>
<h2>Improve Your Experience</h2>
<p>
 You're using a web browser we don't support.
 </p>
<p>
 Try one of these options to have a better experience. We support the latest version of each browser below. Click a logo to download a supported browser.
 </p>
</div></div>||||I|||| Unable to Login

 Username
 Password
 Forgot password?

 Questions? Call 866.270.2090 or email clientsupport@pathward.com

 I acknowledge that I have read, understand, and agree to the website Terms of Use.

 ×

 Improve Your Experience

 You're using a web browser we don't support.

 Try one of these options to have a better experience. We support the latest version of each browser below. Click a logo to download a supported browser.

 Close
Unable to Login
 Username
 Password
 Forgot password?
 Questions? Call 866.270.2090 or email clientsupport@pathward.com
 I acknowledge that I have read, understand, and agree to the website Terms of Use.
 ×
 Improve Your Experience
 You're using a web browser we don't support.
 Try one of these options to have a better experience. We support the latest version of each browser below. Click a logo to download a supported browser.
 Close
Agent Portal : Login
https://secure.mysimplexes.com/
https://en.wikipedia.org/wiki/Simplex
Simplex - Wikipedia
2002-02-19
None
<div><div>
<div><p><a href="/wiki/File:Simplexes.jpg"></a></p><div><p>The four simplexes which can be fully represented in 3D space.</p></div></div>
<p>In <a href="/wiki/Geometry">geometry</a>, a <b>simplex</b> (plural: <b>simplexes</b> or <b>simplices</b>) is a generalization of the notion of a <a href="/wiki/Triangle">triangle</a> or <a href="/wiki/Tetrahedron">tetrahedron</a> to arbitrary <a href="/wiki/Dimensions">dimensions</a>. The simplex is so-named because it represents the simplest possible <a href="/wiki/Polytope">polytope</a> in any given dimension. For example,
</p>
<ul><li>a 0-dimensional simplex is a <a href="/wiki/Point_(mathematics)">point</a>,</li>
<li>a 1-dimensional simplex is a <a href="/wiki/Line_segment">line segment</a>,</li>
<li>a 2-dimensional simplex is a <a href="/wiki/Triangle">triangle</a>,</li>
<li>a 3-dimensional simplex is a <a href="/wiki/Tetrahedron">tetrahedron</a>, and</li>
<li>a 4-dimensional simplex is a <a href="/wiki/5-cell">5-cell</a>.</li></ul>
<p>Specifically, a <b><i>k</i>-simplex</b> is a <i>k</i>-dimensional <a href="/wiki/Polytope">polytope</a> which is the <a href="/wiki/Convex_hull">convex hull</a> of its <i>k</i> + 1 <a href="/wiki/Vertex_(geometry)">vertices</a>. More formally, suppose the <i>k</i> + 1 points are <a href="/wiki/Affinely_independent">affinely independent</a>, which means are <a href="/wiki/Linearly_independent">linearly independent</a>.
Then, the simplex determined by them is the set of points
</p>
<dl><dd></dd></dl>
<p>This representation in terms of weighted vertices is known as the <a href="/wiki/Barycentric_coordinate_system">barycentric coordinate system</a>.
</p><p>A <b>regular simplex</b><sup><a href="#cite_note-1">[1]</a></sup> is a simplex that is also a <a href="/wiki/Regular_polytope">regular polytope</a>. A regular <i>k</i>-simplex may be constructed from a regular (<i>k</i> − 1)-simplex by connecting a new vertex to all original vertices by the common edge length.
</p><p>The <b>standard simplex</b> or <b>probability simplex</b><sup><a href="#cite_note-Boyd-2">[2]</a></sup> is the <i>k - 1</i> dimensional simplex whose vertices are the <i>k</i> standard <a href="/wiki/Unit_vectors">unit vectors</a>, or
</p>
<dl><dd></dd></dl>
<p>In <a href="/wiki/Topology">topology</a> and <a href="/wiki/Combinatorics">combinatorics</a>, it is common to "glue together" simplices to form a <a href="/wiki/Simplicial_complex">simplicial complex</a>. The associated combinatorial structure is called an <a href="/wiki/Abstract_simplicial_complex">abstract simplicial complex</a>, in which context the word "simplex" simply means any <a href="/wiki/Finite_set">finite set</a> of vertices.
</p>
<h2>History[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=1">edit</a>]</h2>
<p>The concept of a simplex was known to <a href="/wiki/William_Kingdon_Clifford">William Kingdon Clifford</a>, who wrote about these shapes in 1886 but called them "prime confines". 
<a href="/wiki/Henri_Poincar%C3%A9">Henri Poincaré</a>, writing about <a href="/wiki/Algebraic_topology">algebraic topology</a> in 1900, called them "generalized tetrahedra".
In 1902 <a href="/wiki/Pieter_Hendrik_Schoute">Pieter Hendrik Schoute</a> described the concept first with the <a href="/wiki/Latin">Latin</a> superlative <i>simplicissimum</i> ("simplest") and then with the same Latin adjective in the normal form <i>simplex</i> ("simple").<sup><a href="#cite_note-3">[3]</a></sup>
</p><p>The <b>regular simplex</b> family is the first of three <a href="/wiki/Regular_polytope">regular polytope</a> families, labeled by <a href="/wiki/Donald_Coxeter">Donald Coxeter</a> as <i>α<sub>n</sub></i>, the other two being the <a href="/wiki/Cross-polytope">cross-polytope</a> family, labeled as <i>β<sub>n</sub></i>, and the <a href="/wiki/Hypercube">hypercubes</a>, labeled as <i>γ<sub>n</sub></i>. A fourth family, the <a href="/wiki/Hypercubic_honeycomb">tessellation of <i>n</i>-dimensional space by infinitely many hypercubes</a>, he labeled as <i>δ<sub>n</sub></i>.<sup><a href="#cite_note-FOOTNOTECoxeter1973120–124§7.2-4">[4]</a></sup>
</p>
<h2>Elements[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=2">edit</a>]</h2>
<p>The <a href="/wiki/Convex_hull">convex hull</a> of any <a href="/wiki/Empty_set">nonempty</a> <a href="/wiki/Subset">subset</a> of the <i>n</i> + 1 points that define an <i>n</i>-simplex is called a <b>face</b> of the simplex. Faces are simplices themselves. In particular, the convex hull of a subset of size <i>m</i> + 1 (of the <i>n</i> + 1 defining points) is an <i>m</i>-simplex, called an <b><i>m</i>-face</b> of the <i>n</i>-simplex. The 0-faces (i.e., the defining points themselves as sets of size 1) are called the <b>vertices</b> (singular: vertex), the 1-faces are called the <b>edges</b>, the (<i>n</i> − 1)-faces are called the <b>facets</b>, and the sole <i>n</i>-face is the whole <i>n</i>-simplex itself. In general, the number of <i>m</i>-faces is equal to the <a href="/wiki/Binomial_coefficient">binomial coefficient</a> .<sup><a href="#cite_note-FOOTNOTECoxeter1973120-5">[5]</a></sup> Consequently, the number of <i>m</i>-faces of an <i>n</i>-simplex may be found in column (<i>m</i> + 1) of row (<i>n</i> + 1) of <a href="/wiki/Pascal%27s_triangle">Pascal's triangle</a>. A simplex <i>A</i> is a <b>coface</b> of a simplex <i>B</i> if <i>B</i> is a face of <i>A</i>. <i>Face</i> and <i>facet</i> can have different meanings when describing types of simplices in a <a href="/wiki/Simplicial_complex">simplicial complex</a>; see <a href="/wiki/Simplicial_complex#Definitions">simplical complex</a> for more detail.
</p><p>The number of 1-faces (edges) of the <i>n</i>-simplex is the <i>n</i>-th <a href="/wiki/Triangle_number">triangle number</a>, the number of 2-faces of the <i>n</i>-simplex is the (<i>n</i> − 1)th <a href="/wiki/Tetrahedron_number">tetrahedron number</a>, the number of 3-faces of the <i>n</i>-simplex is the (<i>n</i> − 2)th 5-cell number, and so on.
</p>
<table>
<caption><i>n</i>-Simplex elements<sup><a href="#cite_note-6">[6]</a></sup>
</caption>
<tbody><tr>
<th>Δ<sup><i>n</i></sup>
</th>
<th>Name
</th>
<th><a href="/wiki/Schl%C3%A4fli_symbol">Schläfli</a><br /><a href="/wiki/Coxeter%E2%80%93Dynkin_diagram">Coxeter</a>
</th>
<th>0-<br />faces<br /><small>(vertices)</small>
</th>
<th>1-<br />faces<br /><small>(edges)</small>
</th>
<th>2-<br />faces<br /><small>(faces)</small>
</th>
<th>3-<br />faces<br /><small>(cells)</small>
</th>
<th>4-<br />faces<br /><small> </small>
</th>
<th>5-<br />faces<br /><small> </small>
</th>
<th>6-<br />faces<br /><small> </small>
</th>
<th>7-<br />faces<br /><small> </small>
</th>
<th>8-<br />faces<br /><small> </small>
</th>
<th>9-<br />faces<br /><small> </small>
</th>
<th>10-<br />faces<br /><small> </small>
</th>
<th><b>Sum</b><br />= 2<sup><i>n</i>+1</sup> − 1
</th></tr>
<tr>
<th>Δ<sup>0</sup>
</th>
<td>0-<i>simplex</i><br />(<a href="/wiki/Vertex_(geometry)">point</a>)
</td>
<td>( )<br />
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>1</b>
</td></tr>
<tr>
<th>Δ<sup>1</sup>
</th>
<td>1-<i>simplex</i><br />(<a href="/wiki/Edge_(geometry)">line segment</a>)
</td>
<td>{ } = ( ) ∨ ( ) = 2 ⋅ ( )<br />
</td>
<td>2
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>3</b>
</td></tr>
<tr>
<th>Δ<sup>2</sup>
</th>
<td>2-<i>simplex</i><br />(<a href="/wiki/Triangle">triangle</a>)
</td>
<td>{3} = 3 ⋅ ( )<br />
</td>
<td>3
</td>
<td>3
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>7</b>
</td></tr>
<tr>
<th>Δ<sup>3</sup>
</th>
<td>3-<i>simplex</i><br />(<a href="/wiki/Tetrahedron">tetrahedron</a>)
</td>
<td>{3,3} = 4 ⋅ ( )<br />
</td>
<td>4
</td>
<td>6
</td>
<td>4
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>15</b>
</td></tr>
<tr>
<th>Δ<sup>4</sup>
</th>
<td>4-<i>simplex</i><br />(<a href="/wiki/5-cell">5-cell</a>)
</td>
<td>{3<sup>3</sup>} = 5 ⋅ ( )<br />
</td>
<td>5
</td>
<td>10
</td>
<td>10
</td>
<td>5
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>31</b>
</td></tr>
<tr>
<th>Δ<sup>5</sup>
</th>
<td><a href="/wiki/5-simplex">5-<i>simplex</i></a>
</td>
<td>{3<sup>4</sup>} = 6 ⋅ ( )<br />
</td>
<td>6
</td>
<td>15
</td>
<td>20
</td>
<td>15
</td>
<td>6
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>63</b>
</td></tr>
<tr>
<th>Δ<sup>6</sup>
</th>
<td><i><a href="/wiki/6-simplex">6-simplex</a></i>
</td>
<td>{3<sup>5</sup>} = 7 ⋅ ( )<br />
</td>
<td>7
</td>
<td>21
</td>
<td>35
</td>
<td>35
</td>
<td>21
</td>
<td>7
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>127</b>
</td></tr>
<tr>
<th>Δ<sup>7</sup>
</th>
<td><i><a href="/wiki/7-simplex">7-simplex</a></i>
</td>
<td>{3<sup>6</sup>} = 8 ⋅ ( )<br />
</td>
<td>8
</td>
<td>28
</td>
<td>56
</td>
<td>70
</td>
<td>56
</td>
<td>28
</td>
<td>8
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td> 
</td>
<td><b>255</b>
</td></tr>
<tr>
<th>Δ<sup>8</sup>
</th>
<td><a href="/wiki/8-simplex">8-<i>simplex</i></a>
</td>
<td>{3<sup>7</sup>} = 9 ⋅ ( )<br />
</td>
<td>9
</td>
<td>36
</td>
<td>84
</td>
<td>126
</td>
<td>126
</td>
<td>84
</td>
<td>36
</td>
<td>9
</td>
<td>1
</td>
<td> 
</td>
<td> 
</td>
<td><b>511</b>
</td></tr>
<tr>
<th>Δ<sup>9</sup>
</th>
<td><a href="/wiki/9-simplex">9-simplex</a>
</td>
<td>{3<sup>8</sup>} = 10 ⋅ ( )<br />
</td>
<td>10
</td>
<td>45
</td>
<td>120
</td>
<td>210
</td>
<td>252
</td>
<td>210
</td>
<td>120
</td>
<td>45
</td>
<td>10
</td>
<td>1
</td>
<td> 
</td>
<td><b>1023</b>
</td></tr>
<tr>
<th>Δ<sup>10</sup>
</th>
<td><a href="/wiki/10-simplex">10-<i>simplex</i></a>
</td>
<td>{3<sup>9</sup>} = 11 ⋅ ( )<br />
</td>
<td>11
</td>
<td>55
</td>
<td>165
</td>
<td>330
</td>
<td>462
</td>
<td>462
</td>
<td>330
</td>
<td>165
</td>
<td>55
</td>
<td>11
</td>
<td>1
</td>
<td><b>2047</b>
</td></tr></tbody></table>
<p>In layman's terms, an <i>n</i>-simplex is a simple shape (a polygon) that requires <i>n</i> dimensions. Consider a line segment <i>AB</i> as a "shape" in a 1-dimensional space (the 1-dimensional space is the line in which the segment lies). One can place a new point <i>C</i> somewhere off the line. The new shape, triangle <i>ABC</i>, requires two dimensions; it cannot fit in the original 1-dimensional space. The triangle is the 2-simplex, a simple shape that requires two dimensions. Consider a triangle <i>ABC</i>, a shape in a 2-dimensional space (the plane in which the triangle resides). One can place a new point <i>D</i> somewhere off the plane. The new shape, tetrahedron <i>ABCD</i>, requires three dimensions; it cannot fit in the original 2-dimensional space. The tetrahedron is the 3-simplex, a simple shape that requires three dimensions. Consider tetrahedron <i>ABCD</i>, a shape in a 3-dimensional space (the 3-space in which the tetrahedron lies). One can place a new point <i>E</i> somewhere outside the 3-space. The new shape <i>ABCDE</i>, called a 5-cell, requires four dimensions and is called the 4-simplex; it cannot fit in the original 3-dimensional space. (It also cannot be visualized easily.) This idea can be generalized, that is, adding a single new point outside the currently occupied space, which requires going to the next higher dimension to hold the new shape. This idea can also be worked backward: the line segment we started with is a simple shape that requires a 1-dimensional space to hold it; the line segment is the 1-simplex. The line segment itself was formed by starting with a single point in 0-dimensional space (this initial point is the 0-simplex) and adding a second point, which required the increase to 1-dimensional space. 
</p><p>More formally, an (<i>n</i> + 1)-simplex can be constructed as a join (∨ operator) of an <i>n</i>-simplex and a point, ( ). An (<i>m</i> + <i>n</i> + 1)-simplex can be constructed as a join of an <i>m</i>-simplex and an <i>n</i>-simplex. The two simplices are oriented to be completely normal from each other, with translation in a direction orthogonal to both of them. A 1-simplex is the join of two points: ( ) ∨ ( ) = 2 ⋅ ( ). A general 2-simplex (scalene triangle) is the join of three points: ( ) ∨ ( ) ∨ ( ). An <a href="/wiki/Isosceles_triangle">isosceles triangle</a> is the join of a 1-simplex and a point: { } ∨ ( ). An <a href="/wiki/Equilateral_triangle">equilateral triangle</a> is 3 ⋅ ( ) or {3}. A general 3-simplex is the join of 4 points: ( ) ∨ ( ) ∨ ( ) ∨ ( ). A 3-simplex with mirror symmetry can be expressed as the join of an edge and two points: { } ∨ ( ) ∨ ( ). A 3-simplex with triangular symmetry can be expressed as the join of an equilateral triangle and 1 point: 3.( )∨( ) or {3}∨( ). A <a href="/wiki/Regular_tetrahedron">regular tetrahedron</a> is 4 ⋅ ( ) or {3,3} and so on.
</p>
<table>
<tbody><tr>
<td><div><p><a href="/wiki/File:Pascal%27s_triangle_5.svg"></a></p><div><p>The numbers of faces in the above table are the same as in <a href="/wiki/Pascal%27s_triangle">Pascal's triangle</a>, without the left diagonal.</p></div></div>
</td></tr>
<tr>
<td><div><p><a href="/wiki/File:Tesseract_tetrahedron_shadow_matrices.svg"></a></p><div><p>The total number of faces is always a <a href="/wiki/Power_of_two">power of two</a> minus one. This figure (a projection of the <a href="/wiki/Tesseract">tesseract</a>) shows the centroids of the 15 faces of the tetrahedron.</p></div></div>
</td></tr></tbody></table>
<p>In some conventions,<sup><a href="#cite_note-7">[7]</a></sup> the empty set is defined to be a (−1)-simplex. The definition of the simplex above still makes sense if <i>n</i> = −1. This convention is more common in applications to algebraic topology (such as <a href="/wiki/Simplicial_homology">simplicial homology</a>) than to the study of polytopes.
</p>
<h2>Symmetric graphs of regular simplices[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=3">edit</a>]</h2>
<p>These <a href="/wiki/Petrie_polygon">Petrie polygons</a> (skew orthogonal projections) show all the vertices of the regular simplex on a <a href="/wiki/Circle">circle</a>, and all vertex pairs connected by edges.
</p>
<table>
<tbody><tr>
<td><a href="/wiki/File:1-simplex_t0.svg"></a><br /><a href="/wiki/Line_segment">1</a>
</td>
<td><a href="/wiki/File:2-simplex_t0.svg"></a><br /><a href="/wiki/Triangle">2</a>
</td>
<td><a href="/wiki/File:3-simplex_t0.svg"></a><br /><a href="/wiki/Tetrahedron">3</a>
</td>
<td><a href="/wiki/File:4-simplex_t0.svg"></a><br /><a href="/wiki/5-cell">4</a>
</td>
<td><a href="/wiki/File:5-simplex_t0.svg"></a><br /><a href="/wiki/5-simplex">5</a>
</td></tr>
<tr>
<td><a href="/wiki/File:6-simplex_t0.svg"></a><br /><a href="/wiki/6-simplex">6</a>
</td>
<td><a href="/wiki/File:7-simplex_t0.svg"></a><br /><a href="/wiki/7-simplex">7</a>
</td>
<td><a href="/wiki/File:8-simplex_t0.svg"></a><br /><a href="/wiki/8-simplex">8</a>
</td>
<td><a href="/wiki/File:9-simplex_t0.svg"></a><br /><a href="/wiki/9-simplex">9</a>
</td>
<td><a href="/wiki/File:10-simplex_t0.svg"></a><br /><a href="/wiki/10-simplex">10</a>
</td></tr>
<tr>
<td><a href="/wiki/File:11-simplex_t0.svg"></a><br /><a href="/wiki/11-simplex">11</a>
</td>
<td><a href="/wiki/File:12-simplex_t0.svg"></a><br /><a href="/wiki/12-simplex">12</a>
</td>
<td><a href="/wiki/File:13-simplex_t0.svg"></a><br /><a href="/wiki/13-simplex">13</a>
</td>
<td><a href="/wiki/File:14-simplex_t0.svg"></a><br /><a href="/wiki/14-simplex">14</a>
</td>
<td><a href="/wiki/File:15-simplex_t0.svg"></a><br /><a href="/wiki/15-simplex">15</a>
</td></tr>
<tr>
<td><a href="/wiki/File:16-simplex_t0.svg"></a><br /><a href="/wiki/16-simplex">16</a>
</td>
<td><a href="/wiki/File:17-simplex_t0.svg"></a><br /><a href="/wiki/17-simplex">17</a>
</td>
<td><a href="/wiki/File:18-simplex_t0.svg"></a><br /><a href="/wiki/18-simplex">18</a>
</td>
<td><a href="/wiki/File:19-simplex_t0.svg"></a><br /><a href="/wiki/19-simplex">19</a>
</td>
<td><a href="/wiki/File:20-simplex_t0.svg"></a><br /><a href="/wiki/20-simplex">20</a>
</td></tr></tbody></table>
<h2>The standard simplex[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=4">edit</a>]</h2>
<div><p><a href="/wiki/File:2D-simplex.svg"></a></p><div><p>The standard 2-simplex in <b>R</b><sup>3</sup></p></div></div>
<p>The <b>standard <i>n</i>-simplex</b> (or <b>unit <i>n</i>-simplex</b>) is the subset of <b>R</b><sup><i>n</i>+1</sup> given by
</p>
<dl><dd></dd></dl>
<p>The simplex Δ<sup><i>n</i></sup> lies in the <a href="/wiki/Affine_hyperplane">affine hyperplane</a> obtained by removing the restriction <i>t</i><sub><i>i</i></sub> ≥ 0 in the above definition.
</p><p>The <i>n</i> + 1 vertices of the standard <i>n</i>-simplex are the points <i>e</i><sub><i>i</i></sub> ∈ <b>R</b><sup><i>n</i>+1</sup>, where
</p>
<dl><dd><i>e</i><sub>0</sub> = (1, 0, 0, ..., 0),</dd>
<dd><i>e</i><sub>1</sub> = (0, 1, 0, ..., 0),</dd>
<dd>⋮</dd>
<dd><i>e</i><sub><i>n</i></sub> = (0, 0, 0, ..., 1).</dd></dl>
<p>There is a canonical map from the standard <i>n</i>-simplex to an arbitrary <i>n</i>-simplex with vertices (<i>v</i><sub>0</sub>, ..., <i>v</i><sub><i>n</i></sub>) given by
</p>
<dl><dd></dd></dl>
<p>The coefficients <i>t</i><sub><i>i</i></sub> are called the <a href="/wiki/Barycentric_coordinates_(mathematics)">barycentric coordinates</a> of a point in the <i>n</i>-simplex. Such a general simplex is often called an <b>affine <i>n</i>-simplex</b>, to emphasize that the canonical map is an <a href="/wiki/Affine_transformation">affine transformation</a>. It is also sometimes called an <b>oriented affine <i>n</i>-simplex</b> to emphasize that the canonical map may be <a href="/wiki/Orientation_(vector_space)">orientation preserving</a> or reversing.
</p><p>More generally, there is a canonical map from the standard -simplex (with <i>n</i> vertices) onto any <a href="/wiki/Polytope">polytope</a> with <i>n</i> vertices, given by the same equation (modifying indexing):
</p>
<dl><dd></dd></dl>
<p>These are known as <a href="/wiki/Generalized_barycentric_coordinates">generalized barycentric coordinates</a>, and express every polytope as the <i>image</i> of a simplex: 
</p><p>A commonly used function from <b>R</b><sup><i>n</i></sup> to the interior of the standard -simplex is the <a href="/wiki/Softmax_function">softmax function</a>, or normalized exponential function; this generalizes the <a href="/wiki/Standard_logistic_function">standard logistic function</a>.
</p>
<h3>Examples[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=5">edit</a>]</h3>
<ul><li>Δ<sup>0</sup> is the point 1 in <b>R</b><sup>1</sup>.</li>
<li>Δ<sup>1</sup> is the line segment joining (1, 0) and (0, 1) in <b>R</b><sup>2</sup>.</li>
<li>Δ<sup>2</sup> is the <a href="/wiki/Equilateral_triangle">equilateral triangle</a> with vertices (1, 0, 0), (0, 1, 0) and (0, 0, 1) in <b>R</b><sup>3</sup>.</li>
<li>Δ<sup>3</sup> is the <a href="/wiki/Regular_tetrahedron">regular tetrahedron</a> with vertices (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) in <b>R</b><sup>4</sup>.</li>
<li>Δ<sup>4</sup> is the regular <a href="/wiki/5-cell">5-cell</a> with vertices (1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0) and (0, 0, 0, 0, 1) in <b>R</b><sup>5</sup>.</li></ul>
<h3>Increasing coordinates[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=6">edit</a>]</h3>
<p>An alternative coordinate system is given by taking the <a href="/wiki/Indefinite_sum">indefinite sum</a>:
</p>
<dl><dd></dd></dl>
<p>This yields the alternative presentation by <i>order,</i> namely as nondecreasing <i>n</i>-tuples between 0 and 1:
</p>
<dl><dd></dd></dl>
<p>Geometrically, this is an <i>n</i>-dimensional subset of (maximal dimension, codimension 0) rather than of (codimension 1). The facets, which on the standard simplex correspond to one coordinate vanishing, here correspond to successive coordinates being equal, while the <a href="/wiki/Interior_(topology)">interior</a> corresponds to the inequalities becoming <i>strict</i> (increasing sequences).
</p><p>A key distinction between these presentations is the behavior under permuting coordinates – the standard simplex is stabilized by permuting coordinates, while permuting elements of the "ordered simplex" do not leave it invariant, as permuting an ordered sequence generally makes it unordered. Indeed, the ordered simplex is a (closed) <a href="/wiki/Fundamental_domain">fundamental domain</a> for the <a href="/wiki/Group_action">action</a> of the <a href="/wiki/Symmetric_group">symmetric group</a> on the <i>n</i>-cube, meaning that the orbit of the ordered simplex under the <i>n</i>! elements of the symmetric group divides the <i>n</i>-cube into mostly disjoint simplices (disjoint except for boundaries), showing that this simplex has volume Alternatively, the volume can be computed by an iterated integral, whose successive integrands are 
</p><p>A further property of this presentation is that it uses the order but not addition, and thus can be defined in any dimension over any ordered set, and for example can be used to define an infinite-dimensional simplex without issues of convergence of sums.
</p>
<h3>Projection onto the standard simplex[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=7">edit</a>]</h3>
<p>Especially in numerical applications of <a href="/wiki/Probability_theory">probability theory</a> a <a href="/wiki/Graphical_projection">projection</a> onto the standard simplex is of interest. Given with possibly negative entries, the closest point on the simplex has coordinates 
</p>
<dl><dd></dd></dl>
<p>where is chosen such that 
</p><p> can be easily calculated from sorting .<sup><a href="#cite_note-8">[8]</a></sup>
The sorting approach takes complexity, which can be improved to complexity via <a href="/wiki/Selection_algorithm">median-finding</a> algorithms.<sup><a href="#cite_note-9">[9]</a></sup> Projecting onto the simplex is computationally similar to projecting onto the ball.
</p>
<h3>Corner of cube[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=8">edit</a>]</h3>
<p>Finally, a simple variant is to replace "summing to 1" with "summing to at most 1"; this raises the dimension by 1, so to simplify notation, the indexing changes:
</p>
<dl><dd></dd></dl>
<p>This yields an <i>n</i>-simplex as a corner of the <i>n</i>-cube, and is a standard orthogonal simplex. This is the simplex used in the <a href="/wiki/Simplex_method">simplex method</a>, which is based at the origin, and locally models a vertex on a polytope with <i>n</i> facets.
</p>
<h2>Cartesian coordinates for a regular <i>n</i>-dimensional simplex in <b>R</b><sup><i>n</i></sup>[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=9">edit</a>]</h2>
<p>One way to write down a regular <i>n</i>-simplex in <b>R</b><sup><i>n</i></sup> is to choose two points to be the first two vertices, choose a third point to make an equilateral triangle, choose a fourth point to make a regular tetrahedron, and so on. Each step requires satisfying equations that ensure that each newly chosen vertex, together with the previously chosen vertices, forms a regular simplex. There are several sets of equations that can be written down and used for this purpose. These include the equality of all the distances between vertices; the equality of all the distances from vertices to the center of the simplex; the fact that the angle subtended through the new vertex by any two previously chosen vertices is ; and the fact that the angle subtended through the center of the simplex by any two vertices is .
</p><p>It is also possible to directly write down a particular regular <i>n</i>-simplex in <b>R</b><sup><i>n</i></sup> which can then be translated, rotated, and scaled as desired. One way to do this is as follows. Denote the <a href="/wiki/Basis_(linear_algebra)">basis vectors</a> of <b>R</b><sup><i>n</i></sup> by <b>e</b><sub>1</sub> through <b>e</b><sub><i>n</i></sub>. Begin with the standard (<i>n</i> − 1)-simplex which is the convex hull of the basis vectors. By adding an additional vertex, these become a face of a regular <i>n</i>-simplex. The additional vertex must lie on the line perpendicular to the barycenter of the standard simplex, so it has the form (<i>α</i>/<i>n</i>, ..., <i>α</i>/<i>n</i>) for some <a href="/wiki/Real_number">real number</a> <i>α</i>. Since the squared distance between two basis vectors is 2, in order for the additional vertex to form a regular <i>n</i>-simplex, the squared distance between it and any of the basis vectors must also be 2. This yields a <a href="/wiki/Quadratic_equation">quadratic equation</a> for <i>α</i>. Solving this equation shows that there are two choices for the additional vertex:
</p>
<dl><dd></dd></dl>
<p>Either of these, together with the standard basis vectors, yields a regular <i>n</i>-simplex.
</p><p>The above regular <i>n</i>-simplex is not centered on the origin. It can be translated to the origin by subtracting the mean of its vertices. By rescaling, it can be given unit side length. This results in the simplex whose vertices are:
</p>
<dl><dd></dd></dl>
<p>for , and
</p>
<dl><dd></dd></dl>
<p>Note that there are two sets of vertices described here. One set uses in each calculation. The other set uses in each calculation.
</p><p>This simplex is inscribed in a hypersphere of radius .
</p><p>A different rescaling produces a simplex that is inscribed in a unit hypersphere. When this is done, its vertices are
</p>
<dl><dd></dd></dl>
<p>where , and
</p>
<dl><dd></dd></dl>
<p>The side length of this simplex is .
</p><p>A highly symmetric way to construct a regular <i>n</i>-simplex is to use a representation of the <a href="/wiki/Cyclic_group">cyclic group</a> <b>Z</b><sub><i>n</i>+1</sub> by <a href="/wiki/Orthogonal_matrix">orthogonal matrices</a>. This is an <i>n</i> × <i>n</i> orthogonal matrix <i>Q</i> such that <i>Q</i><sup><i>n</i>+1</sup> = <i>I</i> is the <a href="/wiki/Identity_matrix">identity matrix</a>, but no lower power of <i>Q</i> is. Applying powers of this <a href="/wiki/Matrix_(mathematics)">matrix</a> to an appropriate vector <b>v</b> will produce the vertices of a regular <i>n</i>-simplex. To carry this out, first observe that for any orthogonal matrix <i>Q</i>, there is a choice of basis in which <i>Q</i> is a block diagonal matrix
</p>
<dl><dd></dd></dl>
<p>where each <i>Q</i><sub><i>i</i></sub> is orthogonal and either 2 × 2 or 1 × 1. In order for <i>Q</i> to have order <i>n</i> + 1, all of these matrices must have order <a href="/wiki/Divisor">dividing</a> <i>n</i> + 1. Therefore each <i>Q</i><sub><i>i</i></sub> is either a 1 × 1 matrix whose only entry is 1 or, if <i>n</i> is <a href="/wiki/Parity_(mathematics)">odd</a>, −1; or it is a 2 × 2 matrix of the form
</p>
<dl><dd></dd></dl>
<p>where each <i>ω</i><sub><i>i</i></sub> is an <a href="/wiki/Integer">integer</a> between zero and <i>n</i> inclusive. A sufficient condition for the orbit of a point to be a regular simplex is that the matrices <i>Q</i><sub><i>i</i></sub> form a basis for the non-trivial irreducible real representations of <b>Z</b><sub><i>n</i>+1</sub>, and the vector being rotated is not stabilized by any of them.
</p><p>In practical terms, for <i>n</i> <a href="/wiki/Parity_(mathematics)">even</a> this means that every matrix <i>Q</i><sub><i>i</i></sub> is 2 × 2, there is an equality of sets
</p>
<dl><dd></dd></dl>
<p>and, for every <i>Q</i><sub><i>i</i></sub>, the entries of <b>v</b> upon which <i>Q</i><sub><i>i</i></sub> acts are not both zero. For example, when <i>n</i> = 4, one possible matrix is
</p>
<dl><dd></dd></dl>
<p>Applying this to the vector (1, 0, 1, 0) results in the simplex whose vertices are
</p>
<dl><dd></dd></dl>
<p>each of which has distance √5 from the others.
When <i>n</i> is odd, the condition means that exactly one of the diagonal blocks is 1 × 1, equal to −1, and acts upon a non-zero entry of <b>v</b>; while the remaining diagonal blocks, say <i>Q</i><sub>1</sub>, ..., <i>Q</i><sub>(<i>n</i> − 1) / 2</sub>, are 2 × 2, there is an equality of sets
</p>
<dl><dd></dd></dl>
<p>and each diagonal block acts upon a pair of entries of <b>v</b> which are not both zero. So, for example, when <i>n</i> = 3, the matrix can be
</p>
<dl><dd></dd></dl>
<p>For the vector (1, 0, 1/√2), the resulting simplex has vertices
</p>
<dl><dd></dd></dl>
<p>each of which has distance 2 from the others.
</p>
<h2>Geometric properties[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=10">edit</a>]</h2>
<h3>Volume[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=11">edit</a>]</h3>
<p>The <a href="/wiki/Volume">volume</a> of an <i>n</i>-simplex in <i>n</i>-dimensional space with vertices (<i>v</i><sub>0</sub>, ..., <i>v</i><sub><i>n</i></sub>) is
</p>
<dl><dd></dd></dl>
<p>where each column of the <i>n</i> × <i>n</i> <a href="/wiki/Determinant">determinant</a> is a <a href="/wiki/Vector_(geometry)">vector</a> that points from vertex <i>v</i><sub>0</sub> to another vertex <i>v</i><sub><i>k</i></sub>.<sup><a href="#cite_note-10">[10]</a></sup> This formula is particularly useful when is the origin.
</p><p>The expression
</p>
<dl><dd></dd></dl>
<p>employs a <a href="/wiki/Gram_determinant">Gram determinant</a> and works even when the <i>n</i>-simplex's vertices are in a Euclidean space with more than <i>n</i> dimensions, e.g., a triangle in . 
</p><p>A more symmetric way to compute the volume of an <i>n</i>-simplex in is
</p>
<dl><dd></dd></dl>
<p>Another common way of computing the volume of the simplex is via the <a href="/wiki/Cayley%E2%80%93Menger_determinant">Cayley–Menger determinant</a>, which works even when the n-simplex's vertices are in a Euclidean space with more than n dimensions.<sup><a href="#cite_note-11">[11]</a></sup>
</p><p>Without the 1/<i>n</i>! it is the formula for the volume of an <i>n</i>-<a href="/wiki/Parallelepiped#Parallelotope">parallelotope</a>. 
This can be understood as follows: Assume that <i>P</i> is an <i>n</i>-parallelotope constructed on a basis of .
Given a <a href="/wiki/Permutation">permutation</a> of , call a list of vertices a <i>n</i>-path if 
</p>
<dl><dd></dd></dl>
<p>(so there are <i>n</i>! <i>n</i>-paths and does not depend on the permutation). The following assertions hold:
</p><p>If <i>P</i> is the unit <i>n</i>-hypercube, then the union of the <i>n</i>-simplexes formed by the convex hull of each <i>n</i>-path is <i>P</i>, and these simplexes are congruent and pairwise non-overlapping.<sup><a href="#cite_note-12">[12]</a></sup> In particular, the volume of such a simplex is
</p>
<dl><dd></dd></dl>
<p>If <i>P</i> is a general parallelotope, the same assertions hold except that it is no longer true, in dimension &gt; 2, that the simplexes need to be pairwise congruent; yet their volumes remain equal, because the <i>n</i>-parallelotope is the image of the unit <i>n</i>-hypercube by the <a href="/wiki/Linear_isomorphism">linear isomorphism</a> that sends the canonical basis of to . As previously, this implies that the volume of a simplex coming from a <i>n</i>-path is:
</p>
<dl><dd></dd></dl>
<p>Conversely, given an <i>n</i>-simplex of , it can be supposed that the vectors form a basis of . Considering the parallelotope constructed from and , one sees that the previous formula is valid for every simplex.
</p><p>Finally, the formula at the beginning of this section is obtained by observing that 
</p>
<dl><dd></dd></dl>
<p>From this formula, it follows immediately that the volume under a standard <i>n</i>-simplex (i.e. between the origin and the simplex in <b>R</b><sup><i>n</i>+1</sup>) is
</p>
<dl><dd></dd></dl>
<p>The volume of a regular <i>n</i>-simplex with unit side length is
</p>
<dl><dd></dd></dl>
<p>as can be seen by multiplying the previous formula by <i>x</i><sup><i>n</i>+1</sup>, to get the volume under the <i>n</i>-simplex as a function of its vertex distance <i>x</i> from the origin, differentiating with respect to <i>x</i>, at   (where the <i>n</i>-simplex side length is 1), and normalizing by the length of the increment, , along the normal vector.
</p>
<h3>Dihedral angles of the regular n-simplex[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=12">edit</a>]</h3>
<p>Any two (<i>n</i> − 1)-dimensional faces of a regular <i>n</i>-dimensional simplex are themselves regular (<i>n</i> − 1)-dimensional simplices, and they have the same <a href="/wiki/Dihedral_angle">dihedral angle</a> of cos<sup>−1</sup>(1/<i>n</i>).<sup><a href="#cite_note-13">[13]</a></sup><sup><a href="#cite_note-14">[14]</a></sup> 
</p><p>This can be seen by noting that the center of the standard simplex is , and the centers of its faces are coordinate permutations of . Then, by symmetry, the vector pointing from to is perpendicular to the faces. So the vectors normal to the faces are permutations of , from which the dihedral angles are calculated.
</p>
<h3>Simplices with an "orthogonal corner"[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=13">edit</a>]</h3>
<p>An "orthogonal corner" means here that there is a vertex at which all adjacent edges are pairwise orthogonal. It immediately follows that all adjacent <a href="/wiki/Face_(geometry)">faces</a> are pairwise orthogonal. Such simplices are generalizations of right triangles and for them there exists an <i>n</i>-dimensional version of the <a href="/wiki/Pythagorean_theorem">Pythagorean theorem</a>:
</p><p>The sum of the squared (<i>n</i> − 1)-dimensional volumes of the facets adjacent to the orthogonal corner equals the squared (<i>n</i> − 1)-dimensional volume of the facet opposite of the orthogonal corner.
</p>
<dl><dd></dd></dl>
<p>where are facets being pairwise orthogonal to each other but not orthogonal to , which is the facet opposite the orthogonal corner.<sup><a href="#cite_note-15">[15]</a></sup>
</p><p>For a 2-simplex the theorem is the <a href="/wiki/Pythagorean_theorem">Pythagorean theorem</a> for triangles with a right angle and for a 3-simplex it is <a href="/wiki/De_Gua%27s_theorem">de Gua's theorem</a> for a tetrahedron 
with an orthogonal corner.
</p>
<h3>Relation to the (<i>n</i> + 1)-hypercube[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=14">edit</a>]</h3>
<p>The <a href="/wiki/Hasse_diagram">Hasse diagram</a> of the face lattice of an <i>n</i>-simplex is isomorphic to the graph of the (<i>n</i> + 1)-<a href="/wiki/Hypercube">hypercube</a>'s edges, with the hypercube's vertices mapping to each of the <i>n</i>-simplex's elements, including the entire simplex and the null polytope as the extreme points of the lattice (mapped to two opposite vertices on the hypercube). This fact may be used to efficiently enumerate the simplex's face lattice, since more general face lattice enumeration algorithms are more computationally expensive.
</p><p>The <i>n</i>-simplex is also the <a href="/wiki/Vertex_figure">vertex figure</a> of the (<i>n</i> + 1)-hypercube. It is also the <a href="/wiki/Facet_(geometry)">facet</a> of the (<i>n</i> + 1)-<a href="/wiki/Orthoplex">orthoplex</a>.
</p>
<h3>Topology[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=15">edit</a>]</h3>
<p><a href="/wiki/Topology">Topologically</a>, an <i>n</i>-simplex is <a href="/wiki/Topologically_equivalent">equivalent</a> to an <a href="/wiki/Ball_(mathematics)"><i>n</i>-ball</a>. Every <i>n</i>-simplex is an <i>n</i>-dimensional <a href="/wiki/Manifold_with_corners">manifold with corners</a>.
</p>
<h3>Probability[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=16">edit</a>]</h3>
<p>In probability theory, the points of the standard <i>n</i>-simplex in (<i>n</i> + 1)-space form the space of possible probability distributions on a finite set consisting of <i>n</i> + 1 possible outcomes. The correspondence is as follows: For each distribution described as an ordered (<i>n</i> + 1)-tuple of probabilities whose sum is (necessarily) 1, we associate the point of the simplex whose <a href="/wiki/Barycentric_coordinates">barycentric coordinates</a> are precisely those probabilities. That is, the <i>k</i>th vertex of the simplex is assigned to have the <i>k</i>th probability of the (<i>n</i> + 1)-tuple as its barycentric coefficient. This correspondence is an affine homeomorphism.
</p>
<h3>Compounds[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=17">edit</a>]</h3>
<p>Since all simplices are self-dual, they can form a series of compounds;
</p>
<ul><li>Two triangles form a <a href="/wiki/Hexagram">hexagram</a> {6/2}.</li>
<li>Two tetrahedra form a <a href="/wiki/Compound_of_two_tetrahedra">compound of two tetrahedra</a> or <a href="/wiki/Stellated_octahedron">stella octangula</a>.</li>
<li>Two 5-cells form a <a href="/wiki/Compound_of_two_5-cells">compound of two 5-cells</a> in four dimensions.</li></ul>
<h2>Algebraic topology[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=18">edit</a>]</h2>
<p>In <a href="/wiki/Algebraic_topology">algebraic topology</a>, simplices are used as building blocks to construct an interesting class of <a href="/wiki/Topological_space">topological spaces</a> called <a href="/wiki/Simplicial_complex">simplicial complexes</a>. These spaces are built from simplices glued together in a <a href="/wiki/Combinatorics">combinatorial</a> fashion. Simplicial complexes are used to define a certain kind of <a href="/wiki/Homology_(mathematics)">homology</a> called <a href="/wiki/Simplicial_homology">simplicial homology</a>.
</p><p>A finite set of <i>k</i>-simplexes embedded in an <a href="/wiki/Open_subset">open subset</a> of <b>R</b><sup><i>n</i></sup> is called an <b>affine <i>k</i>-chain</b>. The simplexes in a chain need not be unique; they may occur with <a href="/wiki/Multiplicity_(mathematics)">multiplicity</a>. Rather than using standard set notation to denote an affine chain, it is instead the standard practice to use plus signs to separate each member in the set. If some of the simplexes have the opposite <a href="/wiki/Orientability">orientation</a>, these are prefixed by a minus sign. If some of the simplexes occur in the set more than once, these are prefixed with an integer count. Thus, an affine chain takes the symbolic form of a sum with integer coefficients.
</p><p>Note that each facet of an <i>n</i>-simplex is an affine (<i>n</i> − 1)-simplex, and thus the <a href="/wiki/Boundary_(topology)">boundary</a> of an <i>n</i>-simplex is an affine (<i>n</i> − 1)-chain. Thus, if we denote one positively oriented affine simplex as
</p>
<dl><dd></dd></dl>
<p>with the denoting the vertices, then the boundary of <i>σ</i> is the chain
</p>
<dl><dd></dd></dl>
<p>It follows from this expression, and the linearity of the boundary operator, that the boundary of the boundary of a simplex is zero:
</p>
<dl><dd></dd></dl>
<p>Likewise, the boundary of the boundary of a chain is zero: .
</p><p>More generally, a simplex (and a chain) can be embedded into a <a href="/wiki/Manifold">manifold</a> by means of smooth, differentiable map . In this case, both the summation convention for denoting the set, and the boundary operation commute with the <a href="/wiki/Embedding">embedding</a>. That is,
</p>
<dl><dd></dd></dl>
<p>where the are the integers denoting orientation and multiplicity. For the boundary operator , one has:
</p>
<dl><dd></dd></dl>
<p>where ρ is a chain. The boundary operation commutes with the mapping because, in the end, the chain is defined as a set and little more, and the set operation always commutes with the <a href="/wiki/Function_(mathematics)">map operation</a> (by definition of a map).
</p><p>A <a href="/wiki/Continuous_function_(topology)">continuous map</a> to a <a href="/wiki/Topological_space">topological space</a> <i>X</i> is frequently referred to as a <b>singular <i>n</i>-simplex</b>. (A map is generally called "singular" if it fails to have some desirable property such as continuity and, in this case, the term is meant to reflect to the fact that the continuous map need not be an embedding.)<sup><a href="#cite_note-16">[16]</a></sup>
</p>
<h2>Algebraic geometry[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=19">edit</a>]</h2>
<p>Since classical <a href="/wiki/Algebraic_geometry">algebraic geometry</a> allows one to talk about polynomial equations but not inequalities, the <i>algebraic standard n-simplex</i> is commonly defined as the subset of affine (<i>n</i> + 1)-dimensional space, where all coordinates sum up to 1 (thus leaving out the inequality part). The algebraic description of this set is
</p><div><p></p></div>
<p>which equals the <a href="/wiki/Scheme_(mathematics)">scheme</a>-theoretic description with
</p><div><p></p></div>
<p>the ring of regular functions on the algebraic <i>n</i>-simplex (for any <a href="/wiki/Ring_(mathematics)">ring</a> ).
</p><p>By using the same definitions as for the classical <i>n</i>-simplex, the <i>n</i>-simplices for different dimensions <i>n</i> assemble into one <a href="/wiki/Simplicial_object">simplicial object</a>, while the rings assemble into one cosimplicial object (in the <a href="/wiki/Category_(mathematics)">category</a> of schemes resp. rings, since the face and degeneracy maps are all polynomial).
</p><p>The algebraic <i>n</i>-simplices are used in higher <a href="/wiki/K-theory">K-theory</a> and in the definition of higher <a href="/wiki/Chow_group">Chow groups</a>.
</p>
<h2>Applications[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=20">edit</a>]</h2>
<table><tbody><tr><td><a href="/wiki/File:Wiki_letter_w_cropped.svg"></a></td><td><p>This section <b>needs expansion</b>. You can help by <a href="https://en.wikipedia.org/w/index.php?title=Simplex&amp;action=edit&amp;section=">adding to it</a>. <i>(December 2009)</i></p></td></tr></tbody></table>
<ul><li>In <a href="/wiki/Statistics">statistics</a>, simplices are sample spaces of <a href="/wiki/Compositional_data">compositional data</a> and are also used in plotting quantities that sum to 1, such as proportions of subpopulations, as in a <a href="/wiki/Ternary_plot">ternary plot</a>.</li>
<li>In <a href="/wiki/Applied_statistics#industrial">industrial statistics</a>, simplices arise in problem formulation and in algorithmic solution. In the design of bread, the producer must combine yeast, flour, water, sugar, etc. In such <a href="/wiki/Mixture">mixtures</a>, only the relative proportions of ingredients matters: For an optimal bread mixture, if the flour is doubled then the yeast should be doubled. Such mixture problem are often formulated with normalized constraints, so that the nonnegative components sum to one, in which case the feasible region forms a simplex. The quality of the bread mixtures can be estimated using <a href="/wiki/Response_surface_methodology">response surface methodology</a>, and then a local maximum can be computed using a <a href="/wiki/Nonlinear_programming">nonlinear programming</a> method, such as <a href="/wiki/Sequential_quadratic_programming">sequential quadratic programming</a>.<sup><a href="#cite_note-17">[17]</a></sup></li>
<li>In <a href="/wiki/Operations_research">operations research</a>, <a href="/wiki/Linear_programming">linear programming</a> problems can be solved by the <a href="/wiki/Simplex_algorithm">simplex algorithm</a> of <a href="/wiki/George_Dantzig">George Dantzig</a>.</li>
<li>In <a href="/wiki/Geometric_design">geometric design</a> and <a href="/wiki/Computer_graphics">computer graphics</a>, many methods first perform simplicial <a href="/wiki/Triangulation_(topology)">triangulations</a> of the domain and then <a href="/wiki/Interpolation">fit interpolating</a> <a href="/wiki/Polynomial_and_rational_function_modeling">polynomials</a> to each simplex.<sup><a href="#cite_note-18">[18]</a></sup></li>
<li>In <a href="/wiki/Chemistry">chemistry</a>, the hydrides of most elements in the <a href="/wiki/P-block">p-block</a> can resemble a simplex if one is to connect each atom. <a href="/wiki/Neon">Neon</a> does not react with hydrogen and as such is <a href="/wiki/Monatomic_gas">a point</a>, <a href="/wiki/Fluorine">fluorine</a> bonds with one hydrogen atom and forms a line segment, <a href="/wiki/Oxygen">oxygen</a> bonds with two hydrogen atoms in a <a href="/wiki/Bent_molecular_geometry">bent</a> fashion resembling a triangle, <a href="/wiki/Nitrogen">nitrogen</a> reacts to form a <a href="/wiki/Trigonal_pyramidal_molecular_geometry">tetrahedron</a>, and <a href="/wiki/Carbon">carbon</a> forms <a href="/wiki/Tetrahedral_molecular_geometry">a structure</a> resembling a <a href="/wiki/Schlegel_diagram">Schlegel diagram</a> of the 5-cell. This trend continues for the heavier analogues of each element, as well as if the hydrogen atom is replaced by a <a href="/wiki/Halogen">halogen</a> atom.</li>
<li>In some approaches to <a href="/wiki/Quantum_gravity">quantum gravity</a>, such as <a href="/wiki/Regge_calculus">Regge calculus</a> and <a href="/wiki/Causal_dynamical_triangulation">causal dynamical triangulations</a>, simplices are used as building blocks of discretizations of spacetime; that is, to build <a href="/wiki/Simplicial_manifold">simplicial manifolds</a>.</li></ul>
<h2>See also[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=21">edit</a>]</h2>
<div>
<ul><li><a href="/wiki/3-sphere">3-sphere</a></li>
<li><a href="/wiki/Aitchison_geometry">Aitchison geometry</a></li>
<li><a href="/wiki/Causal_dynamical_triangulation">Causal dynamical triangulation</a></li>
<li><a href="/wiki/Complete_graph">Complete graph</a></li>
<li><a href="/wiki/Delaunay_triangulation">Delaunay triangulation</a></li>
<li><a href="/wiki/Distance_geometry">Distance geometry</a></li>
<li><a href="/wiki/Geometric_primitive">Geometric primitive</a></li>
<li><a href="/wiki/Hill_tetrahedron">Hill tetrahedron</a></li>
<li><a href="/wiki/Hypersimplex">Hypersimplex</a></li>
<li><a href="/wiki/List_of_regular_polytopes">List of regular polytopes</a></li>
<li><a href="/wiki/Metcalfe%27s_law">Metcalfe's law</a></li>
<li>Other regular <i>n</i>-<a href="/wiki/Polytope">polytopes</a>
<ul><li><a href="/wiki/Cross-polytope">Cross-polytope</a></li>
<li><a href="/wiki/Hypercube">Hypercube</a></li>
<li><a href="/wiki/Tesseract">Tesseract</a></li></ul></li>
<li><a href="/wiki/Polytope">Polytope</a></li>
<li><a href="/wiki/Schl%C3%A4fli_orthoscheme">Schläfli orthoscheme</a></li>
<li><a href="/wiki/Simplex_algorithm">Simplex algorithm</a>—a method for solving optimization problems with inequalities.</li>
<li><a href="/wiki/Simplicial_complex">Simplicial complex</a></li>
<li><a href="/wiki/Simplicial_homology">Simplicial homology</a></li>
<li><a href="/wiki/Simplicial_set">Simplicial set</a></li>
<li><a href="/wiki/Spectrahedron">Spectrahedron</a></li>
<li><a href="/wiki/Ternary_plot">Ternary plot</a></li></ul>
</div>
<h2>Notes[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=22">edit</a>]</h2>
<div>
<ol>
<li><b><a href="#cite_ref-1">^</a></b> <cite><a href="/wiki/Emanuel_Lodewijk_Elte">Elte, E.L.</a> (2006) [1912]. "IV. five dimensional semiregular polytope". <i>The Semiregular Polytopes of the Hyperspaces</i>. Simon &amp; Schuster. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4181-7968-7"><bdi>978-1-4181-7968-7</bdi></a>.</cite>
</li>
<li><b><a href="#cite_ref-Boyd_2-0">^</a></b> <a href="#CITEREFBoydVandenberghe2004">Boyd &amp; Vandenberghe 2004</a>
</li>
<li><b><a href="#cite_ref-3">^</a></b> <cite>Miller, Jeff, <a href="http://jeff560.tripod.com/s.html">"Simplex"</a>, <i>Earliest Known Uses of Some of the Words of Mathematics</i>, retrieved 2018-01-08</cite>
</li>
<li><b><a href="#cite_ref-FOOTNOTECoxeter1973120–124§7.2_4-0">^</a></b> <a href="#CITEREFCoxeter1973">Coxeter 1973</a>, pp. 120–124, §7.2.
</li>
<li><b><a href="#cite_ref-FOOTNOTECoxeter1973120_5-0">^</a></b> <a href="#CITEREFCoxeter1973">Coxeter 1973</a>, p. 120.
</li>
<li><b><a href="#cite_ref-6">^</a></b> <cite><a href="/wiki/Neil_Sloane">Sloane, N. J. A.</a> (ed.). <a href="https://oeis.org/A135278">"Sequence A135278 (Pascal's triangle with its left-hand edge removed)"</a>. <i>The <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences">On-Line Encyclopedia of Integer Sequences</a></i>. OEIS Foundation.</cite>
</li>
<li><b><a href="#cite_ref-7">^</a></b> Kozlov, Dimitry, <i>Combinatorial Algebraic Topology</i>, 2008, Springer-Verlag (Series: Algorithms and Computation in Mathematics)
</li>
<li><b><a href="#cite_ref-8">^</a></b> <cite>Yunmei Chen; Xiaojing Ye (2011). "Projection Onto A Simplex". <a href="/wiki/ArXiv_(identifier)">arXiv</a>:<a href="//arxiv.org/abs/1101.6081">1101.6081</a> [<a href="//arxiv.org/archive/math.OC">math.OC</a>].</cite>
</li>
<li><b><a href="#cite_ref-9">^</a></b> <cite>MacUlan, N.; De Paula, G. G. (1989). "A linear-time median-finding algorithm for projecting a vector on the simplex of n". <i>Operations Research Letters</i>. <b>8</b> (4): 219. <a href="/wiki/Doi_(identifier)">doi</a>:<a href="https://doi.org/10.1016%2F0167-6377%2889%2990064-3">10.1016/0167-6377(89)90064-3</a>.</cite>
</li>
<li><b><a href="#cite_ref-10">^</a></b> A derivation of a very similar formula can be found in <cite>Stein, P. (1966). "A Note on the Volume of a Simplex". <i>American Mathematical Monthly</i>. <b>73</b> (3): 299–301. <a href="/wiki/Doi_(identifier)">doi</a>:<a href="https://doi.org/10.2307%2F2315353">10.2307/2315353</a>. <a href="/wiki/JSTOR_(identifier)">JSTOR</a> <a href="//www.jstor.org/stable/2315353">2315353</a>.</cite>
</li>
<li><b><a href="#cite_ref-11">^</a></b> <cite>Colins, Karen D. <a href="https://mathworld.wolfram.com/">"Cayley-Menger Determinant"</a>. <i><a href="/wiki/MathWorld">MathWorld</a></i>.</cite>
</li>
<li><b><a href="#cite_ref-12">^</a></b> Every <i>n</i>-path corresponding to a permutation is the image of the <i>n</i>-path by the affine isometry that sends to , and whose linear part matches to for all <i>i</i>. hence every two <i>n</i>-paths are isometric, and so is their convex hulls; this explains the congruence of the simplexes. To show the other assertions, it suffices to remark that the interior of the simplex determined by the <i>n</i>-path is the set of points , with and Hence the components of these points with respect to each corresponding permuted basis are strictly ordered in the decreasing order. That explains why the simplexes are non-overlapping. The fact that the union of the simplexes is the whole unit <i>n</i>-hypercube follows as well, replacing the strict inequalities above by "". The same arguments are also valid for a general parallelotope, except the isometry between the simplexes.
</li>
<li><b><a href="#cite_ref-13">^</a></b> <cite><a href="/wiki/Harold_R._Parks">Parks, Harold R.</a>; Wills, Dean C. (October 2002). "An Elementary Calculation of the Dihedral Angle of the Regular <i>n</i>-Simplex". <i>American Mathematical Monthly</i>. <b>109</b> (8): 756–8. <a href="/wiki/Doi_(identifier)">doi</a>:<a href="https://doi.org/10.2307%2F3072403">10.2307/3072403</a>. <a href="/wiki/JSTOR_(identifier)">JSTOR</a> <a href="//www.jstor.org/stable/3072403">3072403</a>.</cite>
</li>
<li><b><a href="#cite_ref-14">^</a></b> <cite>Wills, Harold R.; Parks, Dean C. (June 2009). <a href="http://ir.library.oregonstate.edu/xmlui/handle/1957/11929"><i>Connections between combinatorics of permutations and algorithms and geometry</i></a> (PhD). Oregon State University. <a href="/wiki/Hdl_(identifier)">hdl</a>:<a href="//hdl.handle.net/1957%2F11929">1957/11929</a>.</cite>
</li>
<li><b><a href="#cite_ref-15">^</a></b> <cite>Donchian, P. S.; Coxeter, H. S. M. (July 1935). "1142. An n-dimensional extension of Pythagoras' Theorem". <i>The Mathematical Gazette</i>. <b>19</b> (234): 206. <a href="/wiki/Doi_(identifier)">doi</a>:<a href="https://doi.org/10.2307%2F3605876">10.2307/3605876</a>. <a href="/wiki/JSTOR_(identifier)">JSTOR</a> <a href="//www.jstor.org/stable/3605876">3605876</a>. <a href="/wiki/S2CID_(identifier)">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:125391795">125391795</a>.</cite>
</li>
<li><b><a href="#cite_ref-16">^</a></b> <cite>Lee, John M. (2006). <a href="https://books.google.com/books?id=AdIRBwAAQBAJ&amp;pg=PR1"><i>Introduction to Topological Manifolds</i></a>. Springer. pp. 292–3. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-387-22727-6"><bdi>978-0-387-22727-6</bdi></a>.</cite>
</li>
<li><b><a href="#cite_ref-17">^</a></b> 
<cite>Cornell, John (2002). <i>Experiments with Mixtures: Designs, Models, and the Analysis of Mixture Data</i> (third ed.). Wiley. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-471-07916-2"><bdi>0-471-07916-2</bdi></a>.</cite>
</li>
<li><b><a href="#cite_ref-18">^</a></b> <cite>Vondran, Gary L. (April 1998). <a href="http://www.hpl.hp.com/techreports/98/HPL-98-95.pdf">"Radial and Pruned Tetrahedral Interpolation Techniques"</a> (PDF). <i>HP Technical Report</i>. HPL-98-95: 1–32.</cite>
</li>
</ol></div>
<h2>References[<a href="/w/index.php?title=Simplex&amp;action=edit&amp;section=23">edit</a>]</h2>
<ul><li><cite><a href="/wiki/Walter_Rudin">Rudin, Walter</a> (1976). <i>Principles of Mathematical Analysis</i> (3rd ed.). McGraw-Hill. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-07-054235-X"><bdi>0-07-054235-X</bdi></a>.</cite> <i>(See chapter 10 for a simple review of topological properties.)</i></li>
<li><cite><a href="/wiki/Andrew_S._Tanenbaum">Tanenbaum, Andrew S.</a> (2003). "§2.5.3". <i>Computer Networks</i> (4th ed.). Prentice Hall. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-13-066102-3"><bdi>0-13-066102-3</bdi></a>.</cite></li>
<li><cite>Devroye, Luc (1986). <a href="https://web.archive.org/web/20090505034911/http://cg.scs.carleton.ca/~luc/rnbookindex.html"><i>Non-Uniform Random Variate Generation</i></a>. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-387-96305-7"><bdi>0-387-96305-7</bdi></a>. Archived from <a href="http://cg.scs.carleton.ca/~luc/rnbookindex.html">the original</a> on 2009-05-05.</cite></li>
<li><cite><a href="/wiki/Harold_Scott_MacDonald_Coxeter">Coxeter, H.S.M.</a> (1973). <a href="/wiki/Regular_Polytopes_(book)"><i>Regular Polytopes</i></a> (3rd ed.). Dover. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-486-61480-8"><bdi>0-486-61480-8</bdi></a>.</cite>
<ul><li>pp. 120–121, §7.2. see illustration 7-2<small>A</small></li>
<li>p. 296, Table I (iii): Regular Polytopes, three regular polytopes in <i>n</i> dimensions (<i>n</i> ≥ 5)</li></ul></li>
<li><cite><a href="/wiki/Eric_W._Weisstein">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/Simplex.html">"Simplex"</a>. <i><a href="/wiki/MathWorld">MathWorld</a></i>.</cite></li>
<li><cite><a href="/wiki/Stephen_P._Boyd">Boyd, Stephen</a>; <a href="/w/index.php?title=Lieven_Vandenberghe&amp;action=edit&amp;redlink=1">Vandenberghe, Lieven</a> (2004). <a href="https://books.google.com/books?id=IUZdAAAAQBAJ"><i>Convex Optimization</i></a>. Cambridge University Press. <a href="/wiki/ISBN_(identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-107-39400-1"><bdi>978-1-107-39400-1</bdi></a>.</cite> As <a href="https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf">PDF</a></li></ul>
<table>
<tbody><tr>
<th><div><ul><li><a href="/wiki/Template:Polytopes"><abbr>v</abbr></a></li><li><a href="/wiki/Template_talk:Polytopes"><abbr>t</abbr></a></li><li><a href="https://en.wikipedia.org/w/index.php?title=Template:Polytopes&amp;action=edit"><abbr>e</abbr></a></li></ul></div><div><p>Fundamental convex <a href="/wiki/Regular_polytope">regular</a> and <a href="/wiki/Uniform_polytope">uniform polytopes</a> in dimensions 2–10</p></div>
</th></tr>
<tr>
<th><a href="/wiki/Coxeter_group#Finite_Coxeter_groups">Family</a>
</th>
<td><a href="/wiki/Simple_Lie_group#A_series"><i>A</i><sub><i>n</i></sub></a>
</td>
<td><a href="/wiki/Simple_Lie_group#B_series"><i>B</i><sub><i>n</i></sub></a>
</td>
<td><i>I</i><sub>2</sub>(p) / <a href="/wiki/Simple_Lie_group#D_series"><i>D</i><sub><i>n</i></sub></a>
</td>
<td><a href="/wiki/E6_(mathematics)"><i>E</i><sub>6</sub></a> / <a href="/wiki/E7_(mathematics)"><i>E</i><sub>7</sub></a> / <a href="/wiki/E8_(mathematics)"><i>E</i><sub>8</sub></a> / <a href="/wiki/F4_(mathematics)"><i>F</i><sub>4</sub></a> / <a href="/wiki/G2_(mathematics)"><i>G</i><sub>2</sub></a>
</td>
<td><a href="/wiki/H4_(mathematics)">H<sub>n</sub></a>
</td></tr>
<tr>
<th><a href="/wiki/Regular_polygon">Regular polygon</a>
</th>
<td><a href="/wiki/Equilateral_triangle">Triangle</a>
</td>
<td><a href="/wiki/Square">Square</a>
</td>
<td><a href="/wiki/Regular_polygon">p-gon</a>
</td>
<td><a href="/wiki/Hexagon">Hexagon</a>
</td>
<td><a href="/wiki/Pentagon">Pentagon</a>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_polyhedron">Uniform polyhedron</a>
</th>
<td><a href="/wiki/Tetrahedron">Tetrahedron</a>
</td>
<td><a href="/wiki/Octahedron">Octahedron</a> • <a href="/wiki/Cube">Cube</a>
</td>
<td><a href="/wiki/Tetrahedron">Demicube</a>
</td>
<td>
</td>
<td><a href="/wiki/Regular_dodecahedron">Dodecahedron</a> • <a href="/wiki/Regular_icosahedron">Icosahedron</a>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_polychoron">Uniform polychoron</a>
</th>
<td><a href="/wiki/5-cell">Pentachoron</a>
</td>
<td><a href="/wiki/16-cell">16-cell</a> • <a href="/wiki/Tesseract">Tesseract</a>
</td>
<td><a href="/wiki/16-cell">Demitesseract</a>
</td>
<td><a href="/wiki/24-cell">24-cell</a>
</td>
<td><a href="/wiki/120-cell">120-cell</a> • <a href="/wiki/600-cell">600-cell</a>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_5-polytope">Uniform 5-polytope</a>
</th>
<td><a href="/wiki/5-simplex">5-simplex</a>
</td>
<td><a href="/wiki/5-orthoplex">5-orthoplex</a> • <a href="/wiki/5-cube">5-cube</a>
</td>
<td><a href="/wiki/5-demicube">5-demicube</a>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_6-polytope">Uniform 6-polytope</a>
</th>
<td><a href="/wiki/6-simplex">6-simplex</a>
</td>
<td><a href="/wiki/6-orthoplex">6-orthoplex</a> • <a href="/wiki/6-cube">6-cube</a>
</td>
<td><a href="/wiki/6-demicube">6-demicube</a>
</td>
<td><a href="/wiki/1_22_polytope">1<sub>22</sub></a> • <a href="/wiki/2_21_polytope">2<sub>21</sub></a>
</td>
<td>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_7-polytope">Uniform 7-polytope</a>
</th>
<td><a href="/wiki/7-simplex">7-simplex</a>
</td>
<td><a href="/wiki/7-orthoplex">7-orthoplex</a> • <a href="/wiki/7-cube">7-cube</a>
</td>
<td><a href="/wiki/7-demicube">7-demicube</a>
</td>
<td><a href="/wiki/1_32_polytope">1<sub>32</sub></a> • <a href="/wiki/2_31_polytope">2<sub>31</sub></a> • <a href="/wiki/3_21_polytope">3<sub>21</sub></a>
</td>
<td>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_8-polytope">Uniform 8-polytope</a>
</th>
<td><a href="/wiki/8-simplex">8-simplex</a>
</td>
<td><a href="/wiki/8-orthoplex">8-orthoplex</a> • <a href="/wiki/8-cube">8-cube</a>
</td>
<td><a href="/wiki/8-demicube">8-demicube</a>
</td>
<td><a href="/wiki/1_42_polytope">1<sub>42</sub></a> • <a href="/wiki/2_41_polytope">2<sub>41</sub></a> • <a href="/wiki/4_21_polytope">4<sub>21</sub></a>
</td>
<td>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_9-polytope">Uniform 9-polytope</a>
</th>
<td><a href="/wiki/9-simplex">9-simplex</a>
</td>
<td><a href="/wiki/9-orthoplex">9-orthoplex</a> • <a href="/wiki/9-cube">9-cube</a>
</td>
<td><a href="/wiki/9-demicube">9-demicube</a>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th><a href="/wiki/Uniform_10-polytope">Uniform 10-polytope</a>
</th>
<td><a href="/wiki/10-simplex">10-simplex</a>
</td>
<td><a href="/wiki/10-orthoplex">10-orthoplex</a> • <a href="/wiki/10-cube">10-cube</a>
</td>
<td><a href="/wiki/10-demicube">10-demicube</a>
</td>
<td>
</td>
<td>
</td></tr>
<tr>
<th>Uniform <i>n</i>-<a href="/wiki/Polytope">polytope</a>
</th>
<td><i>n</i>-<a>simplex</a>
</td>
<td><i>n</i>-<a href="/wiki/Cross-polytope">orthoplex</a> • <i>n</i>-<a href="/wiki/Hypercube">cube</a>
</td>
<td><i>n</i>-<a href="/wiki/Demihypercube">demicube</a>
</td>
<td><a href="/wiki/Uniform_1_k2_polytope">1<sub>k2</sub></a> • <a href="/wiki/Uniform_2_k1_polytope">2<sub>k1</sub></a> • <a href="/wiki/Uniform_k_21_polytope">k<sub>21</sub></a>
</td>
<td><i>n</i>-<a href="/wiki/Pentagonal_polytope">pentagonal polytope</a>
</td></tr>
<tr>
<th>Topics: <a href="/wiki/Polytope_families">Polytope families</a> • <a href="/wiki/Regular_polytope">Regular polytope</a> • <a href="/wiki/List_of_regular_polytopes_and_compounds">List of regular polytopes and compounds</a>
</th></tr></tbody></table>
</div>||||I|||| Jump to content
 Toggle sidebar
 Search
 * Create account
 Personal tools
 * Create account
 * Log in

 Pages for logged out editors learn more

 * Talk
 * Contributions
 Navigation
 * Main page
 * Contents
 * Current events
 * Random article
 * About Wikipedia
 * Contact us
 * Donate
 Contribute
 * Help
 * Learn to edit
 * Community portal
 * Recent changes
 * Upload file
 Tools
 * What links here
 * Related changes
 * Upload file
 * Special pages
 * Permanent link
 * Page information
 * Cite this page
 * Wikidata item
 Print/export
 * Download as PDF
 * Printable version
 In other projects
 * Wikimedia Commons
 Languages
 On this Wikipedia the language links are at the top of the page across from the article title. Go to top.

 Contents

 move to sidebar hide
 * (Top)
 * 1 History
 * 2 Elements
 * 3 Symmetric graphs of regular simplices
 * 4 The standard simplex
 + 4.1 Examples
 + 4.2 Increasing coordinates
 + 4.3 Projection onto the standard simplex
 + 4.4 Corner of cube
 * 5 Cartesian coordinates for a regular n-dimensional simplex in Rn
 * 6 Geometric properties
 + 6.1 Volume
 + 6.2 Dihedral angles of the regular n-simplex
 + 6.3 Simplices with an "orthogonal corner"
 + 6.4 Relation to the (n + 1)-hypercube
 + 6.5 Topology
 + 6.6 Probability
 + 6.7 Compounds
 * 7 Algebraic topology
 * 8 Algebraic geometry
 * 9 Applications
 * 10 See also
 * 11 Notes
 * 12 References
 Toggle the table of contents

 Simplex

 32 languages
 * বাংলা
 * Български
 * Català
 * Чӑвашла
 * Čeština
 * Deutsch
 * Español
 * Esperanto
 * Euskara
 * فارسی
 * Français
 * 한국어
 * Հայերեն
 * Italiano
 * עברית
 * Қазақша
 * Magyar
 * Nederlands
 * 日本語
 * Norsk bokmål
 * Polski
 * Português
 * Română
 * Русский
 * Shqip
 * Simple English
 * Slovenčina
 * Slovenščina
 * Svenska
 * ไทย
 * Українська
 * 中文
 Edit links
 * Article
 * Talk
 English
 * Read
 * Edit
 * View history
 More
 * Read
 * Edit
 * View history
 From Wikipedia, the free encyclopedia
 For other uses, see Simplex (disambiguation).
 The four simplexes which can be fully represented in 3D space.

 In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,

 * a 0-dimensional simplex is a point,
 * a 1-dimensional simplex is a line segment,
 * a 2-dimensional simplex is a triangle,
 * a 3-dimensional simplex is a tetrahedron, and
 * a 4-dimensional simplex is a 5-cell.

 Specifically, a k-simplex is a k-dimensional polytope which is the convex hull of its k + 1 vertices. More formally, suppose the k + 1 points are affinely independent, which means are linearly independent. Then, the simplex determined by them is the set of points

 This representation in terms of weighted vertices is known as the barycentric coordinate system.

 A regular simplex[1] is a simplex that is also a regular polytope. A regular k-simplex may be constructed from a regular (k − 1)-simplex by connecting a new vertex to all original vertices by the common edge length.

 The standard simplex or probability simplex[2] is the k - 1 dimensional simplex whose vertices are the k standard unit vectors, or

 In topology and combinatorics, it is common to "glue together" simplices to form a simplicial complex. The associated combinatorial structure is called an abstract simplicial complex, in which context the word "simplex" simply means any finite set of vertices.

 History [ edit ]

 The concept of a simplex was known to William Kingdon Clifford, who wrote about these shapes in 1886 but called them "prime confines". Henri Poincaré, writing about algebraic topology in 1900, called them "generalized tetrahedra". In 1902 Pieter Hendrik Schoute described the concept first with the Latin superlative simplicissimum ("simplest") and then with the same Latin adjective in the normal form simplex ("simple").[3]

 The regular simplex family is the first of three regular polytope families, labeled by Donald Coxeter as αn, the other two being the cross-polytope family, labeled as βn, and the hypercubes, labeled as γn. A fourth family, the tessellation of n-dimensional space by infinitely many hypercubes, he labeled as δn.[4]

 Elements [ edit ]

 The convex hull of any nonempty subset of the n + 1 points that define an n-simplex is called a face of the simplex. Faces are simplices themselves. In particular, the convex hull of a subset of size m + 1 (of the n + 1 defining points) is an m-simplex, called an m-face of the n-simplex. The 0-faces (i.e., the defining points themselves as sets of size 1) are called the vertices (singular: vertex), the 1-faces are called the edges, the (n − 1)-faces are called the facets, and the sole n-face is the whole n-simplex itself. In general, the number of m-faces is equal to the binomial coefficient .[5] Consequently, the number of m-faces of an n-simplex may be found in column (m + 1) of row (n + 1) of Pascal's triangle. A simplex A is a coface of a simplex B if B is a face of A. Face and facet can have different meanings when describing types of simplices in a simplicial complex; see simplical complex for more detail.

 The number of 1-faces (edges) of the n-simplex is the n-th triangle number, the number of 2-faces of the n-simplex is the (n − 1)th tetrahedron number, the number of 3-faces of the n-simplex is the (n − 2)th 5-cell number, and so on.

 n-Simplex elements[6]
 Schläfli 0- 1- 2- 3- 4- 5- 6- 7- 8- 9- 10- Sum 
 Δn Name Coxeter faces faces faces faces faces faces faces faces faces faces faces = 2n+1 − 1
 (vertices) (edges) (faces) (cells) 
 Δ0 0-simplex ( ) 1  1 
 (point)   
 Δ1 1-simplex { } = ( ) ∨ ( ) = 2 ⋅ ( ) 2 1  3 
 (line segment)  
 Δ2 2-simplex {3} = 3 ⋅ ( ) 3 3 1  7 
 (triangle)   
 Δ3 3-simplex {3,3} = 4 ⋅ ( ) 4 6 4 1 15 
 (tetrahedron)  
 Δ4 4-simplex {33} = 5 ⋅ ( ) 5 10 10 5 1 31 
 (5-cell)   
 Δ5 5-simplex {34} = 6 ⋅ ( ) 6 15 20 15 6 1 63 
 Δ6 6-simplex {35} = 7 ⋅ ( ) 7 21 35 35 21 7 1 127 
 Δ7 7-simplex {36} = 8 ⋅ ( ) 8 28 56 70 56 28 8 1 255 
 Δ8 8-simplex {37} = 9 ⋅ ( ) 9 36 84 126 126 84 36 9 1 511 
 Δ9 9-simplex {38} = 10 ⋅ ( ) 10 45 120 210 252 210 120 45 10 1 1023 
 Δ10 10-simplex {39} = 11 ⋅ ( ) 11 55 165 330 462 462 330 165 55 11 1 2047 
 

 In layman's terms, an n-simplex is a simple shape (a polygon) that requires n dimensions. Consider a line segment AB as a "shape" in a 1-dimensional space (the 1-dimensional space is the line in which the segment lies). One can place a new point C somewhere off the line. The new shape, triangle ABC, requires two dimensions; it cannot fit in the original 1-dimensional space. The triangle is the 2-simplex, a simple shape that requires two dimensions. Consider a triangle ABC, a shape in a 2-dimensional space (the plane in which the triangle resides). One can place a new point D somewhere off the plane. The new shape, tetrahedron ABCD, requires three dimensions; it cannot fit in the original 2-dimensional space. The tetrahedron is the 3-simplex, a simple shape that requires three dimensions. Consider tetrahedron ABCD, a shape in a 3-dimensional space (the 3-space in which the tetrahedron lies). One can place a new point E somewhere outside the 3-space. The new shape ABCDE, called a 5-cell, requires four dimensions and is called the 4-simplex; it cannot fit in the original 3-dimensional space. (It also cannot be visualized easily.) This idea can be generalized, that is, adding a single new point outside the currently occupied space, which requires going to the next higher dimension to hold the new shape. This idea can also be worked backward: the line segment we started with is a simple shape that requires a 1-dimensional space to hold it; the line segment is the 1-simplex. The line segment itself was formed by starting with a single point in 0-dimensional space (this initial point is the 0-simplex) and adding a second point, which required the increase to 1-dimensional space.

 More formally, an (n + 1)-simplex can be constructed as a join (∨ operator) of an n-simplex and a point, ( ). An (m + n + 1)-simplex can be constructed as a join of an m-simplex and an n-simplex. The two simplices are oriented to be completely normal from each other, with translation in a direction orthogonal to both of them. A 1-simplex is the join of two points: ( ) ∨ ( ) = 2 ⋅ ( ). A general 2-simplex (scalene triangle) is the join of three points: ( ) ∨ ( ) ∨ ( ). An isosceles triangle is the join of a 1-simplex and a point: { } ∨ ( ). An equilateral triangle is 3 ⋅ ( ) or {3}. A general 3-simplex is the join of 4 points: ( ) ∨ ( ) ∨ ( ) ∨ ( ). A 3-simplex with mirror symmetry can be expressed as the join of an edge and two points: { } ∨ ( ) ∨ ( ). A 3-simplex with triangular symmetry can be expressed as the join of an equilateral triangle and 1 point: 3.( )∨( ) or {3}∨( ). A regular tetrahedron is 4 ⋅ ( ) or {3,3} and so on.

 The numbers of faces in the above table are the same as in Pascal's triangle, without the left diagonal. 
 The total number of faces is always a power of two minus one. This figure (a projection of the tesseract) shows the centroids of the 15 faces of the tetrahedron.
 

 In some conventions,[7] the empty set is defined to be a (−1)-simplex. The definition of the simplex above still makes sense if n = −1. This convention is more common in applications to algebraic topology (such as simplicial homology) than to the study of polytopes.

 Symmetric graphs of regular simplices [ edit ]

 These Petrie polygons (skew orthogonal projections) show all the vertices of the regular simplex on a circle, and all vertex pairs connected by edges.

 
 1 2 3 4 5 
 
 6 7 8 9 10
 
 11 12 13 14 15
 
 16 17 18 19 20
 

 The standard simplex [ edit ]

 The standard 2-simplex in R3

 The standard n-simplex (or unit n-simplex) is the subset of Rn+1 given by

 The simplex Δn lies in the affine hyperplane obtained by removing the restriction ti ≥ 0 in the above definition.

 The n + 1 vertices of the standard n-simplex are the points ei ∈ Rn+1, where

 e0 = (1, 0, 0, ..., 0), e1 = (0, 1, 0, ..., 0), ⋮ en = (0, 0, 0, ..., 1).

 There is a canonical map from the standard n-simplex to an arbitrary n-simplex with vertices (v0, ..., vn) given by

 The coefficients ti are called the barycentric coordinates of a point in the n-simplex. Such a general simplex is often called an affine n-simplex, to emphasize that the canonical map is an affine transformation. It is also sometimes called an oriented affine n-simplex to emphasize that the canonical map may be orientation preserving or reversing.

 More generally, there is a canonical map from the standard -simplex (with n vertices) onto any polytope with n vertices, given by the same equation (modifying indexing):

 These are known as generalized barycentric coordinates, and express every polytope as the image of a simplex:

 A commonly used function from Rn to the interior of the standard -simplex is the softmax function, or normalized exponential function; this generalizes the standard logistic function.

 Examples [ edit ]

 * Δ0 is the point 1 in R1.
 * Δ1 is the line segment joining (1, 0) and (0, 1) in R2.
 * Δ2 is the equilateral triangle with vertices (1, 0, 0), (0, 1, 0) and (0, 0, 1) in R3.
 * Δ3 is the regular tetrahedron with vertices (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) in R4.
 * Δ4 is the regular 5-cell with vertices (1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0) and (0, 0, 0, 0, 1) in R5.

 Increasing coordinates [ edit ]

 An alternative coordinate system is given by taking the indefinite sum:

 This yields the alternative presentation by order, namely as nondecreasing n-tuples between 0 and 1:

 Geometrically, this is an n-dimensional subset of (maximal dimension, codimension 0) rather than of (codimension 1). The facets, which on the standard simplex correspond to one coordinate vanishing, here correspond to successive coordinates being equal, while the interior corresponds to the inequalities becoming strict (increasing sequences).

 A key distinction between these presentations is the behavior under permuting coordinates – the standard simplex is stabilized by permuting coordinates, while permuting elements of the "ordered simplex" do not leave it invariant, as permuting an ordered sequence generally makes it unordered. Indeed, the ordered simplex is a (closed) fundamental domain for the action of the symmetric group on the n-cube, meaning that the orbit of the ordered simplex under the n! elements of the symmetric group divides the n-cube into mostly disjoint simplices (disjoint except for boundaries), showing that this simplex has volume Alternatively, the volume can be computed by an iterated integral, whose successive integrands are

 A further property of this presentation is that it uses the order but not addition, and thus can be defined in any dimension over any ordered set, and for example can be used to define an infinite-dimensional simplex without issues of convergence of sums.

 Projection onto the standard simplex [ edit ]

 Especially in numerical applications of probability theory a projection onto the standard simplex is of interest. Given with possibly negative entries, the closest point on the simplex has coordinates

 where is chosen such that

 can be easily calculated from sorting .[8] The sorting approach takes complexity, which can be improved to complexity via median-finding algorithms.[9] Projecting onto the simplex is computationally similar to projecting onto the ball.

 Corner of cube [ edit ]

 Finally, a simple variant is to replace "summing to 1" with "summing to at most 1"; this raises the dimension by 1, so to simplify notation, the indexing changes:

 This yields an n-simplex as a corner of the n-cube, and is a standard orthogonal simplex. This is the simplex used in the simplex method, which is based at the origin, and locally models a vertex on a polytope with n facets.

 Cartesian coordinates for a regular n -dimensional simplex in Rn [ edit ]

 One way to write down a regular n-simplex in Rn is to choose two points to be the first two vertices, choose a third point to make an equilateral triangle, choose a fourth point to make a regular tetrahedron, and so on. Each step requires satisfying equations that ensure that each newly chosen vertex, together with the previously chosen vertices, forms a regular simplex. There are several sets of equations that can be written down and used for this purpose. These include the equality of all the distances between vertices; the equality of all the distances from vertices to the center of the simplex; the fact that the angle subtended through the new vertex by any two previously chosen vertices is ; and the fact that the angle subtended through the center of the simplex by any two vertices is .

 It is also possible to directly write down a particular regular n-simplex in Rn which can then be translated, rotated, and scaled as desired. One way to do this is as follows. Denote the basis vectors of Rn by e1 through en. Begin with the standard ( n − 1) -simplex which is the convex hull of the basis vectors. By adding an additional vertex, these become a face of a regular n-simplex. The additional vertex must lie on the line perpendicular to the barycenter of the standard simplex, so it has the form ( α / n , ..., α / n ) for some real number α. Since the squared distance between two basis vectors is 2, in order for the additional vertex to form a regular n-simplex, the squared distance between it and any of the basis vectors must also be 2. This yields a quadratic equation for α. Solving this equation shows that there are two choices for the additional vertex:

 Either of these, together with the standard basis vectors, yields a regular n-simplex.

 The above regular n-simplex is not centered on the origin. It can be translated to the origin by subtracting the mean of its vertices. By rescaling, it can be given unit side length. This results in the simplex whose vertices are:

 for , and

 Note that there are two sets of vertices described here. One set uses in each calculation. The other set uses in each calculation.

 This simplex is inscribed in a hypersphere of radius .

 A different rescaling produces a simplex that is inscribed in a unit hypersphere. When this is done, its vertices are

 where , and

 The side length of this simplex is .

 A highly symmetric way to construct a regular n-simplex is to use a representation of the cyclic group Zn+1 by orthogonal matrices. This is an n × n orthogonal matrix Q such that Qn+1 = I is the identity matrix, but no lower power of Q is. Applying powers of this matrix to an appropriate vector v will produce the vertices of a regular n-simplex. To carry this out, first observe that for any orthogonal matrix Q, there is a choice of basis in which Q is a block diagonal matrix

 where each Qi is orthogonal and either 2 × 2 or 1 × 1 . In order for Q to have order n + 1 , all of these matrices must have order dividing n + 1 . Therefore each Qi is either a 1 × 1 matrix whose only entry is 1 or, if n is odd, −1 ; or it is a 2 × 2 matrix of the form

 where each ωi is an integer between zero and n inclusive. A sufficient condition for the orbit of a point to be a regular simplex is that the matrices Qi form a basis for the non-trivial irreducible real representations of Zn+1, and the vector being rotated is not stabilized by any of them.

 In practical terms, for n even this means that every matrix Qi is 2 × 2 , there is an equality of sets

 and, for every Qi, the entries of v upon which Qi acts are not both zero. For example, when n = 4 , one possible matrix is

 Applying this to the vector (1, 0, 1, 0) results in the simplex whose vertices are

 each of which has distance √5 from the others. When n is odd, the condition means that exactly one of the diagonal blocks is 1 × 1 , equal to −1 , and acts upon a non-zero entry of v; while the remaining diagonal blocks, say Q1 , ..., Q(n − 1) / 2, are 2 × 2 , there is an equality of sets

 and each diagonal block acts upon a pair of entries of v which are not both zero. So, for example, when n = 3 , the matrix can be

 For the vector (1, 0, 1/ √ 2 ) , the resulting simplex has vertices

 each of which has distance 2 from the others.

 Geometric properties [ edit ]

 Volume [ edit ]

 The volume of an n-simplex in n-dimensional space with vertices (v0, ..., vn) is

 where each column of the n × n determinant is a vector that points from vertex v0 to another vertex vk.[10] This formula is particularly useful when is the origin.

 The expression

 employs a Gram determinant and works even when the n-simplex's vertices are in a Euclidean space with more than n dimensions, e.g., a triangle in .

 A more symmetric way to compute the volume of an n-simplex in is

 Another common way of computing the volume of the simplex is via the Cayley–Menger determinant, which works even when the n-simplex's vertices are in a Euclidean space with more than n dimensions.[11]

 Without the 1/n! it is the formula for the volume of an n-parallelotope. This can be understood as follows: Assume that P is an n-parallelotope constructed on a basis of . Given a permutation of , call a list of vertices a n-path if

 (so there are n! n-paths and does not depend on the permutation). The following assertions hold:

 If P is the unit n-hypercube, then the union of the n-simplexes formed by the convex hull of each n-path is P, and these simplexes are congruent and pairwise non-overlapping.[12] In particular, the volume of such a simplex is

 If P is a general parallelotope, the same assertions hold except that it is no longer true, in dimension > 2, that the simplexes need to be pairwise congruent; yet their volumes remain equal, because the n-parallelotope is the image of the unit n-hypercube by the linear isomorphism that sends the canonical basis of to . As previously, this implies that the volume of a simplex coming from a n-path is:

 Conversely, given an n-simplex of , it can be supposed that the vectors form a basis of . Considering the parallelotope constructed from and , one sees that the previous formula is valid for every simplex.

 Finally, the formula at the beginning of this section is obtained by observing that

 From this formula, it follows immediately that the volume under a standard n-simplex (i.e. between the origin and the simplex in Rn+1) is

 The volume of a regular n-simplex with unit side length is

 as can be seen by multiplying the previous formula by xn+1, to get the volume under the n-simplex as a function of its vertex distance x from the origin, differentiating with respect to x, at (where the n-simplex side length is 1), and normalizing by the length of the increment, , along the normal vector.

 Dihedral angles of the regular n-simplex [ edit ]

 Any two (n − 1)-dimensional faces of a regular n-dimensional simplex are themselves regular (n − 1)-dimensional simplices, and they have the same dihedral angle of cos−1(1/n).[13][14]

 This can be seen by noting that the center of the standard simplex is , and the centers of its faces are coordinate permutations of . Then, by symmetry, the vector pointing from to is perpendicular to the faces. So the vectors normal to the faces are permutations of , from which the dihedral angles are calculated.

 Simplices with an "orthogonal corner" [ edit ]

 An "orthogonal corner" means here that there is a vertex at which all adjacent edges are pairwise orthogonal. It immediately follows that all adjacent faces are pairwise orthogonal. Such simplices are generalizations of right triangles and for them there exists an n-dimensional version of the Pythagorean theorem:

 The sum of the squared (n − 1)-dimensional volumes of the facets adjacent to the orthogonal corner equals the squared (n − 1)-dimensional volume of the facet opposite of the orthogonal corner.

 where are facets being pairwise orthogonal to each other but not orthogonal to , which is the facet opposite the orthogonal corner.[15]

 For a 2-simplex the theorem is the Pythagorean theorem for triangles with a right angle and for a 3-simplex it is de Gua's theorem for a tetrahedron with an orthogonal corner.

 Relation to the ( n + 1)-hypercube [ edit ]

 The Hasse diagram of the face lattice of an n-simplex is isomorphic to the graph of the (n + 1)-hypercube's edges, with the hypercube's vertices mapping to each of the n-simplex's elements, including the entire simplex and the null polytope as the extreme points of the lattice (mapped to two opposite vertices on the hypercube). This fact may be used to efficiently enumerate the simplex's face lattice, since more general face lattice enumeration algorithms are more computationally expensive.

 The n-simplex is also the vertex figure of the (n + 1)-hypercube. It is also the facet of the (n + 1)-orthoplex.

 Topology [ edit ]

 Topologically, an n-simplex is equivalent to an n-ball. Every n-simplex is an n-dimensional manifold with corners.

 Probability [ edit ]

 Main article: Categorical distribution

 In probability theory, the points of the standard n-simplex in (n + 1)-space form the space of possible probability distributions on a finite set consisting of n + 1 possible outcomes. The correspondence is as follows: For each distribution described as an ordered (n + 1)-tuple of probabilities whose sum is (necessarily) 1, we associate the point of the simplex whose barycentric coordinates are precisely those probabilities. That is, the kth vertex of the simplex is assigned to have the kth probability of the (n + 1)-tuple as its barycentric coefficient. This correspondence is an affine homeomorphism.

 Compounds [ edit ]

 Since all simplices are self-dual, they can form a series of compounds;

 * Two triangles form a hexagram {6/2}.
 * Two tetrahedra form a compound of two tetrahedra or stella octangula.
 * Two 5-cells form a compound of two 5-cells in four dimensions.

 Algebraic topology [ edit ]

 In algebraic topology, simplices are used as building blocks to construct an interesting class of topological spaces called simplicial complexes. These spaces are built from simplices glued together in a combinatorial fashion. Simplicial complexes are used to define a certain kind of homology called simplicial homology.

 A finite set of k-simplexes embedded in an open subset of Rn is called an affine k-chain. The simplexes in a chain need not be unique; they may occur with multiplicity. Rather than using standard set notation to denote an affine chain, it is instead the standard practice to use plus signs to separate each member in the set. If some of the simplexes have the opposite orientation, these are prefixed by a minus sign. If some of the simplexes occur in the set more than once, these are prefixed with an integer count. Thus, an affine chain takes the symbolic form of a sum with integer coefficients.

 Note that each facet of an n-simplex is an affine (n − 1)-simplex, and thus the boundary of an n-simplex is an affine (n − 1)-chain. Thus, if we denote one positively oriented affine simplex as

 with the denoting the vertices, then the boundary of σ is the chain

 It follows from this expression, and the linearity of the boundary operator, that the boundary of the boundary of a simplex is zero:

 Likewise, the boundary of the boundary of a chain is zero: .

 More generally, a simplex (and a chain) can be embedded into a manifold by means of smooth, differentiable map . In this case, both the summation convention for denoting the set, and the boundary operation commute with the embedding. That is,

 where the are the integers denoting orientation and multiplicity. For the boundary operator , one has:

 where ρ is a chain. The boundary operation commutes with the mapping because, in the end, the chain is defined as a set and little more, and the set operation always commutes with the map operation (by definition of a map).

 A continuous map to a topological space X is frequently referred to as a singular n-simplex. (A map is generally called "singular" if it fails to have some desirable property such as continuity and, in this case, the term is meant to reflect to the fact that the continuous map need not be an embedding.)[16]

 Algebraic geometry [ edit ]

 Since classical algebraic geometry allows one to talk about polynomial equations but not inequalities, the algebraic standard n-simplex is commonly defined as the subset of affine (n + 1)-dimensional space, where all coordinates sum up to 1 (thus leaving out the inequality part). The algebraic description of this set is

 which equals the scheme-theoretic description with

 the ring of regular functions on the algebraic n-simplex (for any ring ).

 By using the same definitions as for the classical n-simplex, the n-simplices for different dimensions n assemble into one simplicial object, while the rings assemble into one cosimplicial object (in the category of schemes resp. rings, since the face and degeneracy maps are all polynomial).

 The algebraic n-simplices are used in higher K-theory and in the definition of higher Chow groups.

 Applications [ edit ]

 This section needs expansion. You can help by adding to it. ( December 2009 )
 
 * In statistics, simplices are sample spaces of compositional data and are also used in plotting quantities that sum to 1, such as proportions of subpopulations, as in a ternary plot.
 * In industrial statistics, simplices arise in problem formulation and in algorithmic solution. In the design of bread, the producer must combine yeast, flour, water, sugar, etc. In such mixtures, only the relative proportions of ingredients matters: For an optimal bread mixture, if the flour is doubled then the yeast should be doubled. Such mixture problem are often formulated with normalized constraints, so that the nonnegative components sum to one, in which case the feasible region forms a simplex. The quality of the bread mixtures can be estimated using response surface methodology, and then a local maximum can be computed using a nonlinear programming method, such as sequential quadratic programming.[17]
 * In operations research, linear programming problems can be solved by the simplex algorithm of George Dantzig.
 * In geometric design and computer graphics, many methods first perform simplicial triangulations of the domain and then fit interpolating polynomials to each simplex.[18]
 * In chemistry, the hydrides of most elements in the p-block can resemble a simplex if one is to connect each atom. Neon does not react with hydrogen and as such is a point, fluorine bonds with one hydrogen atom and forms a line segment, oxygen bonds with two hydrogen atoms in a bent fashion resembling a triangle, nitrogen reacts to form a tetrahedron, and carbon forms a structure resembling a Schlegel diagram of the 5-cell. This trend continues for the heavier analogues of each element, as well as if the hydrogen atom is replaced by a halogen atom.
 * In some approaches to quantum gravity, such as Regge calculus and causal dynamical triangulations, simplices are used as building blocks of discretizations of spacetime; that is, to build simplicial manifolds.

 See also [ edit ]

 * 3-sphere
 * Aitchison geometry
 * Causal dynamical triangulation
 * Complete graph
 * Delaunay triangulation
 * Distance geometry
 * Geometric primitive
 * Hill tetrahedron
 * Hypersimplex
 * List of regular polytopes
 * Metcalfe's law
 * Other regular n-polytopes
 + Cross-polytope
 + Hypercube
 + Tesseract
 * Polytope
 * Schläfli orthoscheme
 * Simplex algorithm—a method for solving optimization problems with inequalities.
 * Simplicial complex
 * Simplicial homology
 * Simplicial set
 * Spectrahedron
 * Ternary plot

 Notes [ edit ]

 1. ^ Elte, E.L. (2006) [1912]. "IV. five dimensional semiregular polytope". The Semiregular Polytopes of the Hyperspaces. Simon & Schuster. ISBN 978-1-4181-7968-7.
 2. ^ Boyd & Vandenberghe 2004
 3. ^ Miller, Jeff, "Simplex", Earliest Known Uses of Some of the Words of Mathematics , retrieved 2018-01-08
 4. ^ Coxeter 1973 , pp. 120–124, §7.2.
 5. ^ Coxeter 1973 , p. 120.
 6. ^ Sloane, N. J. A. (ed.). "Sequence A135278 (Pascal's triangle with its left-hand edge removed)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
 7. ^ Kozlov, Dimitry, Combinatorial Algebraic Topology , 2008, Springer-Verlag (Series: Algorithms and Computation in Mathematics)
 8. ^ Yunmei Chen; Xiaojing Ye (2011). "Projection Onto A Simplex". arXiv:1101.6081 [math.OC].
 9. ^ MacUlan, N.; De Paula, G. G. (1989). "A linear-time median-finding algorithm for projecting a vector on the simplex of n". Operations Research Letters. 8 (4): 219. doi:10.1016/0167-6377(89)90064-3.
 10. ^ A derivation of a very similar formula can be found in Stein, P. (1966). "A Note on the Volume of a Simplex". American Mathematical Monthly. 73 (3): 299–301. doi:10.2307/2315353. JSTOR 2315353.
 11. ^ Colins, Karen D. "Cayley-Menger Determinant". MathWorld.
 12. ^ Every n -path corresponding to a permutation is the image of the n -path by the affine isometry that sends to , and whose linear part matches to for all i . hence every two n -paths are isometric, and so is their convex hulls; this explains the congruence of the simplexes. To show the other assertions, it suffices to remark that the interior of the simplex determined by the n -path is the set of points , with and Hence the components of these points with respect to each corresponding permuted basis are strictly ordered in the decreasing order. That explains why the simplexes are non-overlapping. The fact that the union of the simplexes is the whole unit n -hypercube follows as well, replacing the strict inequalities above by " ". The same arguments are also valid for a general parallelotope, except the isometry between the simplexes.
 13. ^ Parks, Harold R.; Wills, Dean C. (October 2002). "An Elementary Calculation of the Dihedral Angle of the Regular n-Simplex". American Mathematical Monthly. 109 (8): 756–8. doi:10.2307/3072403. JSTOR 3072403.
 14. ^ Wills, Harold R.; Parks, Dean C. (June 2009). Connections between combinatorics of permutations and algorithms and geometry (PhD). Oregon State University. hdl:1957/11929.
 15. ^ Donchian, P. S.; Coxeter, H. S. M. (July 1935). "1142. An n-dimensional extension of Pythagoras' Theorem". The Mathematical Gazette. 19 (234): 206. doi:10.2307/3605876. JSTOR 3605876. S2CID 125391795.
 16. ^ Lee, John M. (2006). Introduction to Topological Manifolds. Springer. pp. 292–3. ISBN 978-0-387-22727-6.
 17. ^ Cornell, John (2002). Experiments with Mixtures: Designs, Models, and the Analysis of Mixture Data (third ed.). Wiley. ISBN 0-471-07916-2.
 18. ^ Vondran, Gary L. (April 1998). "Radial and Pruned Tetrahedral Interpolation Techniques" (PDF) . HP Technical Report. HPL-98-95: 1–32.

 References [ edit ]

 * Rudin, Walter (1976). Principles of Mathematical Analysis (3rd ed.). McGraw-Hill. ISBN 0-07-054235-X. (See chapter 10 for a simple review of topological properties.)
 * Tanenbaum, Andrew S. (2003). "§2.5.3". Computer Networks (4th ed.). Prentice Hall. ISBN 0-13-066102-3.
 * Devroye, Luc (1986). Non-Uniform Random Variate Generation. ISBN 0-387-96305-7. Archived from the original on 2009-05-05.
 * Coxeter, H.S.M. (1973). Regular Polytopes (3rd ed.). Dover. ISBN 0-486-61480-8.
 + pp. 120–121, §7.2. see illustration 7-2A
 + p. 296, Table I (iii): Regular Polytopes, three regular polytopes in n dimensions (n ≥ 5)
 * Weisstein, Eric W. "Simplex". MathWorld.
 * Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-1-107-39400-1. As PDF


 * v 
 * t 
 * e 
 Dimension 
 * Vector space 
 * Euclidean space 
 * Affine space 
 Dimensional spaces * Projective space 
 * Free module 
 * Manifold 
 * Algebraic variety 
 * Spacetime 
 * Krull 
 * Lebesgue covering 
 * Inductive 
 Other dimensions * Hausdorff 
 * Minkowski 
 * Fractal 
 * Degrees of freedom
 * Hyperplane 
 * Hypersurface 
 * Hypercube 
 * Hyperrectangle 
 Polytopes and shapes * Demihypercube 
 * Hypersphere 
 * Cross-polytope 
 * Simplex 
 * Hyperpyramid 
 * Zero 
 * One 
 * Two 
 * Three 
 Dimensions by number * Four 
 * Five 
 * Six 
 * Seven 
 * Eight 
 * n-dimensions 
 See also * Hyperspace 
 * Codimension 
 Category 
 
 * v  
 * t  
 * e  
 Fundamental convex regular and uniform polytopes in dimensions 2–10 
 Family  An Bn I2 (p) / Dn E6 / E7 / E8 / F4 / G2 Hn 
 Regular polygon  Triangle Square p-gon Hexagon Pentagon 
 Uniform polyhedron  Tetrahedron Octahedron • Cube Demicube Dodecahedron • Icosahedron
 Uniform polychoron  Pentachoron 16-cell • Tesseract Demitesseract 24-cell 120-cell • 600-cell 
 Uniform 5-polytope  5-simplex 5-orthoplex • 5-cube 5-demicube 
 Uniform 6-polytope  6-simplex 6-orthoplex • 6-cube 6-demicube 122 • 221 
 Uniform 7-polytope  7-simplex 7-orthoplex • 7-cube 7-demicube 132 • 231 • 321 
 Uniform 8-polytope  8-simplex 8-orthoplex • 8-cube 8-demicube 142 • 241 • 421 
 Uniform 9-polytope  9-simplex 9-orthoplex • 9-cube 9-demicube 
 Uniform 10-polytope  10-simplex 10-orthoplex • 10-cube 10-demicube 
 Uniform n-polytope  n-simplex n-orthoplex • n-cube n-demicube 1k2 • 2k1 • k21 n-pentagonal polytope 
 Topics: Polytope families • Regular polytope • List of regular polytopes and compounds
 
 Retrieved from "https://en.wikipedia.org/w/index.php?title=Simplex&oldid=1137814654"
 Categories:
 * Polytopes
 * Topology
 * Multi-dimensional geometry
 Hidden categories:
 * CS1: long volume value
 * Articles with short description
 * Short description is different from Wikidata
 * Articles to be expanded from December 2009
 * All articles to be expanded
 * Articles using small message boxes
 * This page was last edited on 6 February 2023, at 16:15 (UTC) .
 * Text is available under the Creative Commons Attribution-ShareAlike License 3.0; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
 * Privacy policy
 * About Wikipedia
 * Disclaimers
 * Contact Wikipedia
 * Mobile view
 * Developers
 * Statistics
 * Cookie statement
 * 
 * 
The four simplexes which can be fully represented in 3D space.  
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,
 a 0-dimensional simplex is a point,
a 1-dimensional simplex is a line segment,
a 2-dimensional simplex is a triangle,
a 3-dimensional simplex is a tetrahedron, and
a 4-dimensional simplex is a 5-cell. 
Specifically, a  k-simplex is a k-dimensional polytope which is the convex hull of its k + 1 vertices. More formally, suppose the k + 1 points are affinely independent, which means are linearly independent.
Then, the simplex determined by them is the set of points
   
This representation in terms of weighted vertices is known as the barycentric coordinate system.
 A regular simplex  [1]  is a simplex that is also a regular polytope. A regular k-simplex may be constructed from a regular (k − 1)-simplex by connecting a new vertex to all original vertices by the common edge length.
 The standard simplex or probability simplex  [2]  is the k - 1 dimensional simplex whose vertices are the k standard unit vectors, or
   
In topology and combinatorics, it is common to "glue together" simplices to form a simplicial complex. The associated combinatorial structure is called an abstract simplicial complex, in which context the word "simplex" simply means any finite set of vertices.
History[edit]
The concept of a simplex was known to William Kingdon Clifford, who wrote about these shapes in 1886 but called them "prime confines". 
Henri Poincaré, writing about algebraic topology in 1900, called them "generalized tetrahedra".
In 1902 Pieter Hendrik Schoute described the concept first with the Latin superlative simplicissimum ("simplest") and then with the same Latin adjective in the normal form simplex ("simple"). [3] 
 The regular simplex family is the first of three regular polytope families, labeled by Donald Coxeter as αn , the other two being the cross-polytope family, labeled as βn , and the hypercubes, labeled as γn . A fourth family, the tessellation of n-dimensional space by infinitely many hypercubes, he labeled as δn . [4] 
Elements[edit]
The convex hull of any nonempty subset of the n + 1 points that define an n-simplex is called a face of the simplex. Faces are simplices themselves. In particular, the convex hull of a subset of size m + 1 (of the n + 1 defining points) is an m-simplex, called an  m-face of the n-simplex. The 0-faces (i.e., the defining points themselves as sets of size 1) are called the vertices (singular: vertex), the 1-faces are called the edges, the (n − 1)-faces are called the facets, and the sole n-face is the whole n-simplex itself. In general, the number of m-faces is equal to the binomial coefficient . [5]  Consequently, the number of m-faces of an n-simplex may be found in column (m + 1) of row (n + 1) of Pascal's triangle. A simplex A is a coface of a simplex B if B is a face of A. Face and facet can have different meanings when describing types of simplices in a simplicial complex; see simplical complex for more detail.
 The number of 1-faces (edges) of the n-simplex is the n-th triangle number, the number of 2-faces of the n-simplex is the (n − 1)th tetrahedron number, the number of 3-faces of the n-simplex is the (n − 2)th 5-cell number, and so on.
 n-Simplex elements [6] 
 
Δ n 
Name
 Schläfli  Coxeter
0-faces (vertices)
1-faces (edges)
2-faces (faces)
3-faces (cells)
4-faces  
5-faces  
6-faces  
7-faces  
8-faces  
9-faces  
10-faces  
 Sum = 2 n+1 − 1
 
Δ0
0-simplex (point)
( )
1
 
 
 
 
 
 
 
 
 
 
 1
 
Δ1
1-simplex (line segment)
{ } = ( ) ∨ ( ) = 2 ⋅ ( )
2
1
 
 
 
 
 
 
 
 
 
 3
 
Δ2
2-simplex (triangle)
{3} = 3 ⋅ ( )
3
3
1
 
 
 
 
 
 
 
 
 7
 
Δ3
3-simplex (tetrahedron)
{3,3} = 4 ⋅ ( )
4
6
4
1
 
 
 
 
 
 
 
 15
 
Δ4
4-simplex (5-cell)
{33} = 5 ⋅ ( )
5
10
10
5
1
 
 
 
 
 
 
 31
 
Δ5
 5-simplex 
{34} = 6 ⋅ ( )
6
15
20
15
6
1
 
 
 
 
 
 63
 
Δ6
  6-simplex 
{35} = 7 ⋅ ( )
7
21
35
35
21
7
1
 
 
 
 
 127
 
Δ7
  7-simplex 
{36} = 8 ⋅ ( )
8
28
56
70
56
28
8
1
 
 
 
 255
 
Δ8
 8-simplex 
{37} = 9 ⋅ ( )
9
36
84
126
126
84
36
9
1
 
 
 511
 
Δ9
 9-simplex
{38} = 10 ⋅ ( )
10
45
120
210
252
210
120
45
10
1
 
 1023
 
Δ10
 10-simplex 
{39} = 11 ⋅ ( )
11
55
165
330
462
462
330
165
55
11
1
 2047
   
In layman's terms, an n-simplex is a simple shape (a polygon) that requires n dimensions. Consider a line segment AB as a "shape" in a 1-dimensional space (the 1-dimensional space is the line in which the segment lies). One can place a new point C somewhere off the line. The new shape, triangle ABC, requires two dimensions; it cannot fit in the original 1-dimensional space. The triangle is the 2-simplex, a simple shape that requires two dimensions. Consider a triangle ABC, a shape in a 2-dimensional space (the plane in which the triangle resides). One can place a new point D somewhere off the plane. The new shape, tetrahedron ABCD, requires three dimensions; it cannot fit in the original 2-dimensional space. The tetrahedron is the 3-simplex, a simple shape that requires three dimensions. Consider tetrahedron ABCD, a shape in a 3-dimensional space (the 3-space in which the tetrahedron lies). One can place a new point E somewhere outside the 3-space. The new shape ABCDE, called a 5-cell, requires four dimensions and is called the 4-simplex; it cannot fit in the original 3-dimensional space. (It also cannot be visualized easily.) This idea can be generalized, that is, adding a single new point outside the currently occupied space, which requires going to the next higher dimension to hold the new shape. This idea can also be worked backward: the line segment we started with is a simple shape that requires a 1-dimensional space to hold it; the line segment is the 1-simplex. The line segment itself was formed by starting with a single point in 0-dimensional space (this initial point is the 0-simplex) and adding a second point, which required the increase to 1-dimensional space. 
 More formally, an (n + 1)-simplex can be constructed as a join (∨ operator) of an n-simplex and a point, ( ). An (m + n + 1)-simplex can be constructed as a join of an m-simplex and an n-simplex. The two simplices are oriented to be completely normal from each other, with translation in a direction orthogonal to both of them. A 1-simplex is the join of two points: ( ) ∨ ( ) = 2 ⋅ ( ). A general 2-simplex (scalene triangle) is the join of three points: ( ) ∨ ( ) ∨ ( ). An isosceles triangle is the join of a 1-simplex and a point: { } ∨ ( ). An equilateral triangle is 3 ⋅ ( ) or {3}. A general 3-simplex is the join of 4 points: ( ) ∨ ( ) ∨ ( ) ∨ ( ). A 3-simplex with mirror symmetry can be expressed as the join of an edge and two points: { } ∨ ( ) ∨ ( ). A 3-simplex with triangular symmetry can be expressed as the join of an equilateral triangle and 1 point: 3.( )∨( ) or {3}∨( ). A regular tetrahedron is 4 ⋅ ( ) or {3,3} and so on.
 
       The numbers of faces in the above table are the same as in Pascal's triangle, without the left diagonal.  
 
       The total number of faces is always a power of two minus one. This figure (a projection of the tesseract) shows the centroids of the 15 faces of the tetrahedron.  
   
In some conventions, [7]  the empty set is defined to be a (−1)-simplex. The definition of the simplex above still makes sense if n = −1. This convention is more common in applications to algebraic topology (such as simplicial homology) than to the study of polytopes.
Symmetric graphs of regular simplices[edit]
These Petrie polygons (skew orthogonal projections) show all the vertices of the regular simplex on a circle, and all vertex pairs connected by edges.
 
    1
    2
    3
    4
    5
 
    6
    7
    8
    9
    10
 
    11
    12
    13
    14
    15
 
    16
    17
    18
    19
    20
   
The standard simplex[edit]
      The standard 2-simplex in R 3   
The standard n-simplex (or unit n-simplex) is the subset of R  n+1 given by
   
The simplex Δ n  lies in the affine hyperplane obtained by removing the restriction t  i  ≥ 0 in the above definition.
 The n + 1 vertices of the standard n-simplex are the points e  i  ∈ R  n+1, where
  e 0 = (1, 0, 0, ..., 0),
 e 1 = (0, 1, 0, ..., 0),
⋮
 e  n  = (0, 0, 0, ..., 1). 
There is a canonical map from the standard n-simplex to an arbitrary n-simplex with vertices (v 0, ..., v  n ) given by
   
The coefficients t  i  are called the barycentric coordinates of a point in the n-simplex. Such a general simplex is often called an affine n-simplex, to emphasize that the canonical map is an affine transformation. It is also sometimes called an oriented affine n-simplex to emphasize that the canonical map may be orientation preserving or reversing.
 More generally, there is a canonical map from the standard -simplex (with n vertices) onto any polytope with n vertices, given by the same equation (modifying indexing):
   
These are known as generalized barycentric coordinates, and express every polytope as the image of a simplex: 
 A commonly used function from R  n  to the interior of the standard -simplex is the softmax function, or normalized exponential function; this generalizes the standard logistic function.
Examples[edit]
 Δ0 is the point 1 in R 1.
Δ1 is the line segment joining (1, 0) and (0, 1) in R 2.
Δ2 is the equilateral triangle with vertices (1, 0, 0), (0, 1, 0) and (0, 0, 1) in R 3.
Δ3 is the regular tetrahedron with vertices (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) in R 4.
Δ4 is the regular 5-cell with vertices (1, 0, 0, 0, 0), (0, 1, 0, 0, 0), (0, 0, 1, 0, 0), (0, 0, 0, 1, 0) and (0, 0, 0, 0, 1) in R 5. 
Increasing coordinates[edit]
An alternative coordinate system is given by taking the indefinite sum:
   
This yields the alternative presentation by order, namely as nondecreasing n-tuples between 0 and 1:
   
Geometrically, this is an n-dimensional subset of (maximal dimension, codimension 0) rather than of (codimension 1). The facets, which on the standard simplex correspond to one coordinate vanishing, here correspond to successive coordinates being equal, while the interior corresponds to the inequalities becoming strict (increasing sequences).
 A key distinction between these presentations is the behavior under permuting coordinates – the standard simplex is stabilized by permuting coordinates, while permuting elements of the "ordered simplex" do not leave it invariant, as permuting an ordered sequence generally makes it unordered. Indeed, the ordered simplex is a (closed) fundamental domain for the action of the symmetric group on the n-cube, meaning that the orbit of the ordered simplex under the n! elements of the symmetric group divides the n-cube into mostly disjoint simplices (disjoint except for boundaries), showing that this simplex has volume Alternatively, the volume can be computed by an iterated integral, whose successive integrands are 
 A further property of this presentation is that it uses the order but not addition, and thus can be defined in any dimension over any ordered set, and for example can be used to define an infinite-dimensional simplex without issues of convergence of sums.
Projection onto the standard simplex[edit]
Especially in numerical applications of probability theory a projection onto the standard simplex is of interest. Given with possibly negative entries, the closest point on the simplex has coordinates 
   
where is chosen such that 
  can be easily calculated from sorting . [8] 
The sorting approach takes complexity, which can be improved to complexity via median-finding algorithms. [9]  Projecting onto the simplex is computationally similar to projecting onto the ball.
Corner of cube[edit]
Finally, a simple variant is to replace "summing to 1" with "summing to at most 1"; this raises the dimension by 1, so to simplify notation, the indexing changes:
   
This yields an n-simplex as a corner of the n-cube, and is a standard orthogonal simplex. This is the simplex used in the simplex method, which is based at the origin, and locally models a vertex on a polytope with n facets.
Cartesian coordinates for a regular n-dimensional simplex in R  n [edit]
One way to write down a regular n-simplex in R  n  is to choose two points to be the first two vertices, choose a third point to make an equilateral triangle, choose a fourth point to make a regular tetrahedron, and so on. Each step requires satisfying equations that ensure that each newly chosen vertex, together with the previously chosen vertices, forms a regular simplex. There are several sets of equations that can be written down and used for this purpose. These include the equality of all the distances between vertices; the equality of all the distances from vertices to the center of the simplex; the fact that the angle subtended through the new vertex by any two previously chosen vertices is ; and the fact that the angle subtended through the center of the simplex by any two vertices is .
 It is also possible to directly write down a particular regular n-simplex in R  n  which can then be translated, rotated, and scaled as desired. One way to do this is as follows. Denote the basis vectors of R  n  by e 1 through e  n . Begin with the standard (n − 1)-simplex which is the convex hull of the basis vectors. By adding an additional vertex, these become a face of a regular n-simplex. The additional vertex must lie on the line perpendicular to the barycenter of the standard simplex, so it has the form (α/n, ..., α/n) for some real number α. Since the squared distance between two basis vectors is 2, in order for the additional vertex to form a regular n-simplex, the squared distance between it and any of the basis vectors must also be 2. This yields a quadratic equation for α. Solving this equation shows that there are two choices for the additional vertex:
   
Either of these, together with the standard basis vectors, yields a regular n-simplex.
 The above regular n-simplex is not centered on the origin. It can be translated to the origin by subtracting the mean of its vertices. By rescaling, it can be given unit side length. This results in the simplex whose vertices are:
   
for , and
   
Note that there are two sets of vertices described here. One set uses in each calculation. The other set uses in each calculation.
 This simplex is inscribed in a hypersphere of radius .
 A different rescaling produces a simplex that is inscribed in a unit hypersphere. When this is done, its vertices are
   
where , and
   
The side length of this simplex is .
 A highly symmetric way to construct a regular n-simplex is to use a representation of the cyclic group Z  n+1 by orthogonal matrices. This is an n × n orthogonal matrix Q such that Q  n+1 = I is the identity matrix, but no lower power of Q is. Applying powers of this matrix to an appropriate vector v will produce the vertices of a regular n-simplex. To carry this out, first observe that for any orthogonal matrix Q, there is a choice of basis in which Q is a block diagonal matrix
   
where each Q  i  is orthogonal and either 2 × 2 or 1 × 1. In order for Q to have order n + 1, all of these matrices must have order dividing n + 1. Therefore each Q  i  is either a 1 × 1 matrix whose only entry is 1 or, if n is odd, −1; or it is a 2 × 2 matrix of the form
   
where each ω  i  is an integer between zero and n inclusive. A sufficient condition for the orbit of a point to be a regular simplex is that the matrices Q  i  form a basis for the non-trivial irreducible real representations of Z  n+1, and the vector being rotated is not stabilized by any of them.
 In practical terms, for n even this means that every matrix Q  i  is 2 × 2, there is an equality of sets
   
and, for every Q  i , the entries of v upon which Q  i  acts are not both zero. For example, when n = 4, one possible matrix is
   
Applying this to the vector (1, 0, 1, 0) results in the simplex whose vertices are
   
each of which has distance √5 from the others.
When n is odd, the condition means that exactly one of the diagonal blocks is 1 × 1, equal to −1, and acts upon a non-zero entry of v; while the remaining diagonal blocks, say Q 1, ..., Q (n − 1) / 2, are 2 × 2, there is an equality of sets
   
and each diagonal block acts upon a pair of entries of v which are not both zero. So, for example, when n = 3, the matrix can be
   
For the vector (1, 0, 1/√2), the resulting simplex has vertices
   
each of which has distance 2 from the others.
Geometric properties[edit]
Volume[edit]
The volume of an n-simplex in n-dimensional space with vertices (v 0, ..., v  n ) is
   
where each column of the n × n determinant is a vector that points from vertex v 0 to another vertex v  k . [10]  This formula is particularly useful when is the origin.
 The expression
   
employs a Gram determinant and works even when the n-simplex's vertices are in a Euclidean space with more than n dimensions, e.g., a triangle in . 
 A more symmetric way to compute the volume of an n-simplex in is
   
Another common way of computing the volume of the simplex is via the Cayley–Menger determinant, which works even when the n-simplex's vertices are in a Euclidean space with more than n dimensions. [11] 
 Without the 1/n! it is the formula for the volume of an n-parallelotope. 
This can be understood as follows: Assume that P is an n-parallelotope constructed on a basis of .
Given a permutation of , call a list of vertices a n-path if 
   
(so there are n! n-paths and does not depend on the permutation). The following assertions hold:
 If P is the unit n-hypercube, then the union of the n-simplexes formed by the convex hull of each n-path is P, and these simplexes are congruent and pairwise non-overlapping. [12]  In particular, the volume of such a simplex is
   
If P is a general parallelotope, the same assertions hold except that it is no longer true, in dimension &gt; 2, that the simplexes need to be pairwise congruent; yet their volumes remain equal, because the n-parallelotope is the image of the unit n-hypercube by the linear isomorphism that sends the canonical basis of to . As previously, this implies that the volume of a simplex coming from a n-path is:
   
Conversely, given an n-simplex of , it can be supposed that the vectors form a basis of . Considering the parallelotope constructed from and , one sees that the previous formula is valid for every simplex.
 Finally, the formula at the beginning of this section is obtained by observing that 
   
From this formula, it follows immediately that the volume under a standard n-simplex (i.e. between the origin and the simplex in R  n+1) is
   
The volume of a regular n-simplex with unit side length is
   
as can be seen by multiplying the previous formula by x  n+1, to get the volume under the n-simplex as a function of its vertex distance x from the origin, differentiating with respect to x, at   (where the n-simplex side length is 1), and normalizing by the length of the increment, , along the normal vector.
Dihedral angles of the regular n-simplex[edit]
Any two (n − 1)-dimensional faces of a regular n-dimensional simplex are themselves regular (n − 1)-dimensional simplices, and they have the same dihedral angle of cos−1(1/n). [13]   [14]  
 This can be seen by noting that the center of the standard simplex is , and the centers of its faces are coordinate permutations of . Then, by symmetry, the vector pointing from to is perpendicular to the faces. So the vectors normal to the faces are permutations of , from which the dihedral angles are calculated.
Simplices with an "orthogonal corner"[edit]
An "orthogonal corner" means here that there is a vertex at which all adjacent edges are pairwise orthogonal. It immediately follows that all adjacent faces are pairwise orthogonal. Such simplices are generalizations of right triangles and for them there exists an n-dimensional version of the Pythagorean theorem:
 The sum of the squared (n − 1)-dimensional volumes of the facets adjacent to the orthogonal corner equals the squared (n − 1)-dimensional volume of the facet opposite of the orthogonal corner.
   
where are facets being pairwise orthogonal to each other but not orthogonal to , which is the facet opposite the orthogonal corner. [15] 
 For a 2-simplex the theorem is the Pythagorean theorem for triangles with a right angle and for a 3-simplex it is de Gua's theorem for a tetrahedron 
with an orthogonal corner.
Relation to the (n + 1)-hypercube[edit]
The Hasse diagram of the face lattice of an n-simplex is isomorphic to the graph of the (n + 1)-hypercube's edges, with the hypercube's vertices mapping to each of the n-simplex's elements, including the entire simplex and the null polytope as the extreme points of the lattice (mapped to two opposite vertices on the hypercube). This fact may be used to efficiently enumerate the simplex's face lattice, since more general face lattice enumeration algorithms are more computationally expensive.
 The n-simplex is also the vertex figure of the (n + 1)-hypercube. It is also the facet of the (n + 1)-orthoplex.
Topology[edit]
 Topologically, an n-simplex is equivalent to an  n-ball. Every n-simplex is an n-dimensional manifold with corners.
Probability[edit]
In probability theory, the points of the standard n-simplex in (n + 1)-space form the space of possible probability distributions on a finite set consisting of n + 1 possible outcomes. The correspondence is as follows: For each distribution described as an ordered (n + 1)-tuple of probabilities whose sum is (necessarily) 1, we associate the point of the simplex whose barycentric coordinates are precisely those probabilities. That is, the kth vertex of the simplex is assigned to have the kth probability of the (n + 1)-tuple as its barycentric coefficient. This correspondence is an affine homeomorphism.
Compounds[edit]
Since all simplices are self-dual, they can form a series of compounds;
 Two triangles form a hexagram {6/2}.
Two tetrahedra form a compound of two tetrahedra or stella octangula.
Two 5-cells form a compound of two 5-cells in four dimensions. 
Algebraic topology[edit]
In algebraic topology, simplices are used as building blocks to construct an interesting class of topological spaces called simplicial complexes. These spaces are built from simplices glued together in a combinatorial fashion. Simplicial complexes are used to define a certain kind of homology called simplicial homology.
 A finite set of k-simplexes embedded in an open subset of R  n  is called an affine k-chain. The simplexes in a chain need not be unique; they may occur with multiplicity. Rather than using standard set notation to denote an affine chain, it is instead the standard practice to use plus signs to separate each member in the set. If some of the simplexes have the opposite orientation, these are prefixed by a minus sign. If some of the simplexes occur in the set more than once, these are prefixed with an integer count. Thus, an affine chain takes the symbolic form of a sum with integer coefficients.
 Note that each facet of an n-simplex is an affine (n − 1)-simplex, and thus the boundary of an n-simplex is an affine (n − 1)-chain. Thus, if we denote one positively oriented affine simplex as
   
with the denoting the vertices, then the boundary of σ is the chain
   
It follows from this expression, and the linearity of the boundary operator, that the boundary of the boundary of a simplex is zero:
   
Likewise, the boundary of the boundary of a chain is zero: .
 More generally, a simplex (and a chain) can be embedded into a manifold by means of smooth, differentiable map . In this case, both the summation convention for denoting the set, and the boundary operation commute with the embedding. That is,
   
where the are the integers denoting orientation and multiplicity. For the boundary operator , one has:
   
where ρ is a chain. The boundary operation commutes with the mapping because, in the end, the chain is defined as a set and little more, and the set operation always commutes with the map operation (by definition of a map).
 A continuous map to a topological space X is frequently referred to as a singular n-simplex. (A map is generally called "singular" if it fails to have some desirable property such as continuity and, in this case, the term is meant to reflect to the fact that the continuous map need not be an embedding.) [16] 
Algebraic geometry[edit]
Since classical algebraic geometry allows one to talk about polynomial equations but not inequalities, the algebraic standard n-simplex is commonly defined as the subset of affine (n + 1)-dimensional space, where all coordinates sum up to 1 (thus leaving out the inequality part). The algebraic description of this set is
    
which equals the scheme-theoretic description with
    
the ring of regular functions on the algebraic n-simplex (for any ring ).
 By using the same definitions as for the classical n-simplex, the n-simplices for different dimensions n assemble into one simplicial object, while the rings assemble into one cosimplicial object (in the category of schemes resp. rings, since the face and degeneracy maps are all polynomial).
 The algebraic n-simplices are used in higher K-theory and in the definition of higher Chow groups.
Applications[edit]
        This section needs expansion. You can help by adding to it. (December 2009)     
 In statistics, simplices are sample spaces of compositional data and are also used in plotting quantities that sum to 1, such as proportions of subpopulations, as in a ternary plot.
In industrial statistics, simplices arise in problem formulation and in algorithmic solution. In the design of bread, the producer must combine yeast, flour, water, sugar, etc. In such mixtures, only the relative proportions of ingredients matters: For an optimal bread mixture, if the flour is doubled then the yeast should be doubled. Such mixture problem are often formulated with normalized constraints, so that the nonnegative components sum to one, in which case the feasible region forms a simplex. The quality of the bread mixtures can be estimated using response surface methodology, and then a local maximum can be computed using a nonlinear programming method, such as sequential quadratic programming. [17]  
In operations research, linear programming problems can be solved by the simplex algorithm of George Dantzig.
In geometric design and computer graphics, many methods first perform simplicial triangulations of the domain and then fit interpolating polynomials to each simplex. [18]  
In chemistry, the hydrides of most elements in the p-block can resemble a simplex if one is to connect each atom. Neon does not react with hydrogen and as such is a point, fluorine bonds with one hydrogen atom and forms a line segment, oxygen bonds with two hydrogen atoms in a bent fashion resembling a triangle, nitrogen reacts to form a tetrahedron, and carbon forms a structure resembling a Schlegel diagram of the 5-cell. This trend continues for the heavier analogues of each element, as well as if the hydrogen atom is replaced by a halogen atom.
In some approaches to quantum gravity, such as Regge calculus and causal dynamical triangulations, simplices are used as building blocks of discretizations of spacetime; that is, to build simplicial manifolds. 
See also[edit]
  3-sphere 
 Aitchison geometry 
 Causal dynamical triangulation 
 Complete graph 
 Delaunay triangulation 
 Distance geometry 
 Geometric primitive 
 Hill tetrahedron 
 Hypersimplex 
 List of regular polytopes 
 Metcalfe's law 
Other regular n-polytopes
  Cross-polytope 
 Hypercube 
 Tesseract   
 Polytope 
 Schläfli orthoscheme 
 Simplex algorithm—a method for solving optimization problems with inequalities.
 Simplicial complex 
 Simplicial homology 
 Simplicial set 
 Spectrahedron 
 Ternary plot  
Notes[edit]
  ^   Elte, E.L. (2006) [1912]. "IV. five dimensional semiregular polytope". The Semiregular Polytopes of the Hyperspaces. Simon &amp; Schuster. ISBN  978-1-4181-7968-7 .
  ^  Boyd &amp; Vandenberghe 2004
  ^  Miller, Jeff, "Simplex", Earliest Known Uses of Some of the Words of Mathematics, retrieved 2018-01-08
  ^  Coxeter 1973, pp. 120–124, §7.2.
  ^  Coxeter 1973, p. 120.
  ^   Sloane, N. J. A. (ed.). "Sequence A135278 (Pascal's triangle with its left-hand edge removed)". The On-Line Encyclopedia of Integer Sequences . OEIS Foundation.
  ^  Kozlov, Dimitry, Combinatorial Algebraic Topology, 2008, Springer-Verlag (Series: Algorithms and Computation in Mathematics)
  ^  Yunmei Chen; Xiaojing Ye (2011). "Projection Onto A Simplex". arXiv:1101.6081 [math.OC].
  ^  MacUlan, N.; De Paula, G. G. (1989). "A linear-time median-finding algorithm for projecting a vector on the simplex of n". Operations Research Letters. 8 (4): 219. doi:10.1016/0167-6377(89)90064-3.
  ^  A derivation of a very similar formula can be found in Stein, P. (1966). "A Note on the Volume of a Simplex". American Mathematical Monthly. 73 (3): 299–301. doi:10.2307/2315353. JSTOR 2315353.
  ^  Colins, Karen D. "Cayley-Menger Determinant".  MathWorld .
  ^  Every n-path corresponding to a permutation is the image of the n-path by the affine isometry that sends to , and whose linear part matches to for all i. hence every two n-paths are isometric, and so is their convex hulls; this explains the congruence of the simplexes. To show the other assertions, it suffices to remark that the interior of the simplex determined by the n-path is the set of points , with and Hence the components of these points with respect to each corresponding permuted basis are strictly ordered in the decreasing order. That explains why the simplexes are non-overlapping. The fact that the union of the simplexes is the whole unit n-hypercube follows as well, replacing the strict inequalities above by "". The same arguments are also valid for a general parallelotope, except the isometry between the simplexes.
  ^   Parks, Harold R.; Wills, Dean C. (October 2002). "An Elementary Calculation of the Dihedral Angle of the Regular n-Simplex". American Mathematical Monthly. 109 (8): 756–8. doi:10.2307/3072403. JSTOR 3072403.
  ^  Wills, Harold R.; Parks, Dean C. (June 2009).  Connections between combinatorics of permutations and algorithms and geometry  (PhD). Oregon State University. hdl:1957/11929.
  ^  Donchian, P. S.; Coxeter, H. S. M. (July 1935). "1142. An n-dimensional extension of Pythagoras' Theorem". The Mathematical Gazette. 19 (234): 206. doi:10.2307/3605876. JSTOR 3605876. S2CID 125391795.
  ^  Lee, John M. (2006).  Introduction to Topological Manifolds . Springer. pp. 292–3. ISBN  978-0-387-22727-6 .
  ^  
Cornell, John (2002). Experiments with Mixtures: Designs, Models, and the Analysis of Mixture Data (third ed.). Wiley. ISBN  0-471-07916-2 .
  ^  Vondran, Gary L. (April 1998). "Radial and Pruned Tetrahedral Interpolation Techniques" (PDF). HP Technical Report. HPL-98-95: 1–32.
 
References[edit]
   Rudin, Walter (1976). Principles of Mathematical Analysis (3rd ed.). McGraw-Hill. ISBN  0-07-054235-X . (See chapter 10 for a simple review of topological properties.) 
  Tanenbaum, Andrew S. (2003). "§2.5.3". Computer Networks (4th ed.). Prentice Hall. ISBN  0-13-066102-3 . 
 Devroye, Luc (1986).  Non-Uniform Random Variate Generation . ISBN  0-387-96305-7 . Archived from the original on 2009-05-05. 
  Coxeter, H.S.M. (1973).  Regular Polytopes  (3rd ed.). Dover. ISBN  0-486-61480-8 .
 pp. 120–121, §7.2. see illustration 7-2A 
p. 296, Table I (iii): Regular Polytopes, three regular polytopes in n dimensions (n ≥ 5)  
  Weisstein, Eric W. "Simplex".  MathWorld . 
  Boyd, Stephen; Vandenberghe, Lieven (2004).  Convex Optimization . Cambridge University Press. ISBN  978-1-107-39400-1 . As PDF  
 
     v     t     e      Fundamental convex regular and uniform polytopes in dimensions 2–10 
 
 Family
  A  n  
  B  n  
 I 2(p) /  D  n  
  E 6  /  E 7  /  E 8  /  F 4  /  G 2 
 Hn 
 
 Regular polygon
 Triangle
 Square
 p-gon
 Hexagon
 Pentagon
 
 Uniform polyhedron
 Tetrahedron
 Octahedron • Cube
 Demicube
 Dodecahedron • Icosahedron
 
 Uniform polychoron
 Pentachoron
 16-cell • Tesseract
 Demitesseract
 24-cell
 120-cell • 600-cell
 
 Uniform 5-polytope
 5-simplex
 5-orthoplex • 5-cube
 5-demicube
 
 Uniform 6-polytope
 6-simplex
 6-orthoplex • 6-cube
 6-demicube
 122  • 221 
 
 Uniform 7-polytope
 7-simplex
 7-orthoplex • 7-cube
 7-demicube
 132  • 231  • 321 
 
 Uniform 8-polytope
 8-simplex
 8-orthoplex • 8-cube
 8-demicube
 142  • 241  • 421 
 
 Uniform 9-polytope
 9-simplex
 9-orthoplex • 9-cube
 9-demicube
 
 Uniform 10-polytope
 10-simplex
 10-orthoplex • 10-cube
 10-demicube
 
Uniform n-polytope
 n-simplex
 n-orthoplex • n-cube
 n-demicube
 1k2  • 2k1  • k21 
 n-pentagonal polytope
 
Topics: Polytope families • Regular polytope • List of regular polytopes and compounds
Simplex - Wikipedia
https://en.wikipedia.org/wiki/Simplex