[Math] Online view of a polyhedron defined by linear inequalities

linear programmingonline-resourcespolygonspolyhedrasimplex

I am studying the simplex algorithm which finds an optimal solution for a minimization or a maximization of a set of linear inequalities.

I know that such a set of inequalities defines a polyhedron. My question is this :is there an online tool that allows me to input linear inequalities with two or three variables and see the polyhedron defined by them? This would be the set of all points which satisfy all inequalities.

Best Answer

You can, with Sage. Specifically, Sage has a web-interface or online workspace that requires zero installation (although you may need to create an account).

Here's an example. If you type

p = Polyhedron(ieqs = [[0,0,0,2],[0,0,1,0,],[0,10,0,0],
                      [1,-1,0,0],[1,0,-1,0,],[1,0,0,-1]])
p.plot()

you will receive this picture:

somehow, a cube is born

(In Sage/Python, anything in a line after # will be a comment; that p.Hrepresentation() business was me trying to figure out what the inequalities were)).

I've really never used Sage for this, so this example is taken from this documentation about $V$- and $H$-representations of polytopes.

I was seriously confused by how [0, 0, 0, 2] counts as an inequality, but that's explained in this thematic tutorial on polytopes in Sage.

Apparently if a list $[d, a, b, c]$ is given when an inequality is expected, it's the inequality $(a, b, c) \cdot \vec x + d \ge 0$. It seems then that an inequality $ax + by + cz \ge d$ would be represented by the list [-d, a, b, c], and an inequality $ax + by + cz \le d$ by [d, -a, -b, -c] (I think).

At any rate, picking up Sage isn't too bad, but it does take some legwork, usually, to do anything that isn't immediately straightforward. It's been immensely helpful to me over the years, so it's worth a shot: it definitely can do what you want, if you have a bit of patience (and obviously some programming experience is a plus!).

If you do decide to give it a shot, I'd be more than happy to try to help out with things you're not sure about.

Related Question