Note

Following a national ballot, the union, UCU, that represents staff in the higher education sector has called a strike on three days in late November, and also "action short of a strike" during a period that starts on Wednesday, 23 November. During this period, colleagues are invited to take various actions, including abstaining from voluntary activities. I view the maintenance of Spivey's Corner as an activity I undertake voluntarily and not part of any contract of employment, and I cannot guarantee that it will remain accessible during the period of the dispute. In addition, some materials on the site may pertain to lectures that are cancelled by myself or others as part of the strike, and we are asked not to make them available online. Further details of the reasons for the strike and how it affects teaching in Oxford are on a brief FAQ page.

How the Simplex Algorithm works

From Spivey's Corner
Jump to navigation Jump to search

[math]\displaystyle{ }[/math]Let's consider a simple linear programming problem.

Maximize \(2x+y\) subject to

\(x, y \geq 0\),
\(x-y\leq 3\),
\(x+y\leq 7\),
\(3y-x\leq 9\).

[Figure 1]

The feasible region is always a convex polygon/polyhedron/polytope.

We turn the constraints int equations by introducing slack variables \(s\), \(t\), \(u\):

Maximise \(P = 2x+y\) subject to

\(x, y, s, t, u \geq 0\),
\(x-y+s = 3\),
\(x+y+t = 7\),
\(-x+3y+u = 9\).

[Figure 2]

Each point of the feasible region now has five non-negative coordinates \((x, y, s, t, y)\), each measuring its perpendicular distance from an axis or a constraint line. For the point shown, \((x, y, s, t, u) = (2, 2, 3, 3, 5)\).

[Figure 3]

Unless the problem is degenerate, the optimum is reached at one vertex of the feasible region. We can find it geometrically by plotting lines of constant \(P\) and sliding down until the line hits the feasible region.

To use the simplex algorithm, we write the definition of \(P\) and the constraint equations in tabular form.

\(x\) \(y\) \(s\) \(t\) \(u\)
\(P\) −2 −1 0 0 0 0
\(s\) 1 −1 1 0 0 3
\(t\) 1 1 0 1 0 7
\(u\) −1 3 0 0 1 9

We can start at any vertex, but let's start at the origin. At any vertex of the feasible region, two variables are zero: in this case, \(x\) and \(y\). The others will be non-zero in a way that satisfies the constraint equations.

In the algorithm, we move from vertex to vertex along the edges of the feasible region, always increasing the objective function. If we move right from the origin, increasing \(x\), that will increase \(P\) by 2 units for each unit increase in \(x\).