Introduction to Algorithms (CLRS)ΒΆ

This page includes several visualizations for linear programs used in the third edition of Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.

Chapter 29 of Cormen, Leiserson, Rivest, and Stein uses the following LP to motivate fundamental LP concepts and introduce the graphical method for solving 2-dimensional LPs. See Equations (29.11-29.15).

\[\begin{split}\begin{align*} \text{maximize} \quad & x_1+x_2\\ \text{subject to} \quad & 4x_1-x_2 \leq 8 \\ & 2x_1+x_2 \leq 10 \\ & 5x_1 -2x_2 \geq -2 \\ & x_1, x_2 \geq 0 \end{align*}\end{split}\]

Note that we have rewritten the third constraint as \(-5x_1+2x_2\leq 2\) when defining the LP in gilp below

from gilp import examples
from gilp.visualize import simplex_visual

simplex_visual(examples.CLRS_INTEGER_2D_LP).show()