Tikz figure wit linear inequalities, surfaces and lables (ILP graphically)

Question

I'm creating slides to explain Integer Linear Programming (ILP). What I want to do is show how solve a two dimensional problem graphically.

E.g. I have the following problem:

Decision variables:
\begin{description}
    \item[$x_{1}$] 
    \item[$x_{2}$] 
\end{description}
Maximaize
\[ 3 x_{1} + 4 x_{2} \]
Restrictions
\begin{equation*}
    \begin{cases}
        2x_1 + 1x_2 \leq 120 \\
        1x_1 + 3x_2 \leq 180  \\
        1x_1 + 1x_2 \leq 80 \\
        x_1 \geq 0, x_2 \geq 0                          
    \end{cases}
\label{eq:restricties}
\end{equation*}

What I'm able to draw are the lines for the max. function and the restrictions but I'm not succeeding in the folling:

1. Fill the surface for the restrictions (the bigger then and smaller then's) (making intersections)
2. Show the labels for the inequalities. E.q. $2x_1 + 1x_2 \leq 120$ next to a line
3. Filling the surface for the solution space

Is there someone who can help me?

This is the code I have so far.

    \begin{tikzpicture}
\begin{axis}[
    domain=0:150,
    xmin=-10, xmax=150,
    ymin=-5, ymax=150,
    samples=400,
    axis y line=center,
    axis x line=middle,
]
    \addplot+[mark=none,blue] {120-x} node[pin=180:{$4x^2-5$}]{};
            \addplot+[mark=none,black] {(1/3)*(180-x)};
            \addplot+[mark=none,purple] {80-x};
            \addplot+[mark=none,red] {(1/8)*12*x}; 
            \addplot+[mark=none,green] {(1/4)*(290-3*x)};
            \addplot+[mark=none,style=dashed,green] {(1/4)*(100-3*x)};
            \addplot+[mark=none,style=dashed,green] {(1/4)*(350-3*x)};
\end{axis}
\end{tikzpicture}

Kind regards

Jens Buysse

Answer 1

For those who are interested, here is a MetaPost solution (inserted in a LuaLaTeX program), taking care of points 2 and point 3 of the OP (though I preferred equalities to label the lines, a personal choice). Point 1 seems to me too difficult to represent appropriately in only one figure. This program uses at some places MetaPost's ability to implicitly solve systems of linear equations. It indicates also the point solution and the optimal value on the graph. The coding itself can surely be improved, e.g. by introducing specific macros. I'll take care about that later!

\documentclass[border=2mm]{standalone}
\usepackage{luamplib}
  \mplibtextextlabel{enable}
\begin{document}
  \begin{mplibcode}

    u := .075cm; xmax := 140; ymax := 140; 
    path constraint[], objective, max_objective; pair loc[], loc_eqmax;

    beginfig(1);
      % 2x_1 + x_2 \le 120
      z11 = (0, 120);
      z12 = (60, 0);
      constraint1 = (z11 -- z12) scaled u; loc1 = u*.2[z11, z12];

      % x_1 + 3x_2 \le 180
      z21 = (0, 60);
      z22 = (120, 20);
      constraint2 = (z21 -- z22) scaled u; loc2 = u*.7[z21, z22];


      % x_1 + 1x_2 \leq 80 
      z31 = (0, 80);
      z32 = (80, 0);
      constraint3 = (z31 -- z32) scaled u; loc3 = u*.2[z31, z32];


      % x1 \geq 0
      constraint4 = origin -- (0, ymax*u); 

      % x2 \geq 0
      constraint5 = origin -- (xmax*u, 0); 

      fill buildcycle(constraint1, constraint3, constraint2, constraint4, constraint5) 
        withcolor .8white; 

      draw constraint1;
      draw thelabel.top("$2x_1 + x_2 = 120$", loc1) rotatedaround(loc1, angle(z12-z11));

      draw constraint2; 
      draw thelabel.top("$x_1 + 3x_2 = 180$", loc2) rotatedaround(loc2, angle(z22-z21));

      draw constraint3;
      draw thelabel.top("$x_1 + x_2 = 80$", loc3) rotatedaround(loc3, angle(z32-z31));

      drawarrow constraint4;
      label.lft("$x_1 = 0$", .5u*z21); label.lft("$x_2$", (0, u*ymax));

      label.bot("$x_2 = 0$", .5u*z12); label.bot("$x_1$", (xmax*u, 0));
      drawarrow constraint5;

      % max 3x_1 + 4x2
      3x01 + 4y01 = 0; x01 = -50;
      3x02 + 4y02 = 0; y02 = -60;
      objective = (z01 -- z02) scaled u;

      drawoptions(withcolor red);
      draw objective scaled .5 dashed evenly;
      draw thelabel.bot("$3x_1+4x_2 = 0$", origin) rotatedaround(origin, angle(z02-z01));

      % point solution z
      x + y = 80; x + 3y = 180;
      draw z*u withpen pencircle scaled 3;
      label.llft("$(" & decimal x & "," & decimal y & ")$", z*u); 

      % Maximum
      max_objective = objective shifted (z*u);
      draw max_objective;
      loc_eqmax = point .7 of max_objective;
      draw thelabel.top("$3x_1 + 4x_2 =" & decimal(3x+4y) & "$", loc_eqmax)
        rotatedaround(loc_eqmax, angle(loc_eqmax-z*u));

    endfig; 

  \end{mplibcode}
\end{document}

Output:

Edit Here is a version not included in a LuaLaTeX program, only MetaPost coding thus. In this one I've define a macro simplifying the handling of rotated labels:

vardef rotatedlabel@#(expr str, loc, angl) =
  draw thelabel@#(str, loc) rotatedaround(loc, angl)
enddef;

It turned out that the luamplib package could not handle the hash character (#) of this macro properly, so I reverted to standalone MetaPost for this occasion. (In the meantime, the maintainer of the luamplib package, Kim Dohyun, has fixed the problem, but the new version is not to be found in CTAN yet). The output is the same as above.

input latexmp; setupLaTeXMP(textextlabel=enable, mode=rerun);

vardef rotatedlabel@#(expr str, loc, angl) =
  draw thelabel@#(str, loc) rotatedaround(loc, angl)
enddef;

u := .075cm; xmax := 140; ymax := 140; 
path constraint[], objective, max_objective; pair loc[], loc_eqmax;

beginfig(1);

  % 2x_1 + x_2 \le 120
  z11 = (0, 120); z12 = (60, 0);
  constraint1 = (z11 -- z12) scaled u; loc1 = u*.2[z11, z12];

  % x_1 + 3x_2 \le 180
  z21 = (0, 60); z22 = (120, 20);
  constraint2 = (z21 -- z22) scaled u; loc2 = u*.7[z21, z22];

  % x_1 + 1x_2 \leq 80 
  z31 = (0, 80); z32 = (80, 0);
  constraint3 = (z31 -- z32) scaled u; loc3 = u*.2[z31, z32];

  % x1 \geq 0
  constraint4 = origin -- (0, ymax*u); 

  % x2 \geq 0
  constraint5 = origin -- (xmax*u, 0); 

  fill buildcycle(constraint1, constraint3, constraint2, constraint4, constraint5) 
    withcolor .8white; 

  draw constraint1;
  rotatedlabel.top("$2x_1 + x_2 = 120$", loc1, angle(z12-z11));

  draw constraint2; 
  rotatedlabel.top("$x_1 + 3x_2 = 180$", loc2, angle(z22-z21));

  draw constraint3;
  rotatedlabel.top("$x_1 + x_2 = 80$", loc3, angle(z32-z31));

  drawarrow constraint4;
  label.lft("$x_1 = 0$", .5u*z21); label.lft("$x_2$", (0, u*ymax));

  drawarrow constraint5;
  label.bot("$x_2 = 0$", .5u*z12); label.bot("$x_1$", (xmax*u, 0));

  % max 3x_1 + 4x2
  3x01 + 4y01 = 0; x01 = -50;
  3x02 + 4y02 = 0; y02 = -60;
  objective = (z01 -- z02) scaled u;
  drawoptions(withcolor red);
  draw objective scaled .5 dashed evenly;
  rotatedlabel.bot("$3x_1+4x_2 = 0$", origin, angle(z02-z01));

  % point solution z
  x + y = 80; x + 3y = 180;
  draw z*u withpen pencircle scaled 3;
  label.llft("$(" & decimal x & "," & decimal y & ")$", z*u); 

  % Maximum
  max_objective = objective shifted (z*u);
  draw max_objective;
  loc_eqmax = point .7 of max_objective;
  rotatedlabel.top("$3x_1 + 4x_2 =" & decimal(3x+4y) & "$", loc_eqmax, angle(loc_eqmax-z*u));

endfig; 
end.

Answer 2

Something like this? It's very messy to label each line, a legend would be a better idea but that's not what you requested. If you fill the restrictions you'll just end up with two coloured blocks. Is that what you want?

\documentclass{article}
\usepackage{pgfplots}
\usepackage{amsmath}

\pgfplotsset{compat=newest}
\usepgfplotslibrary{fillbetween}

\begin{document}
Decision variables:
\begin{description}
    \item[$x_{1}$] 
    \item[$x_{2}$]
\end{description}
Maximaize
\[ 3 x_{1} + 4 x_{2} \]
Restrictions
\begin{equation*}
    \begin{cases}
        2x_1 + 1x_2 \leq 120 \\
        1x_1 + 3x_2 \leq 180  \\
        1x_1 + 1x_2 \leq 80 \\
        x_1 \geq 0, x_2 \geq 0                          
    \end{cases}
\label{eq:restricties}
\end{equation*}

    \begin{tikzpicture}
\begin{axis}[
    domain=0:180,
    xmin=0, xmax=180,
    ymin=0, ymax=150,
    samples=200,
    axis y line=center,
    axis x line=middle,
]
%First line blue with a  label
       \addplot+[mark=none,blue] {120-x} node[pin=180:{$4x^2-5$}]{} node[pos=0](blue){};
       \node [right] at (blue) {\footnotesize{$2x_1 + 1x_2 \leq 120$}};      
%Second line black with a label       
          \addplot+[mark=none,black] {(1/3)*(180-x)}  node[pos=0.6](black){};
          \node [right] at (black) {\footnotesize{$ 1x_1 + 3x_2 \leq 180$}};
%Third line purple with a label                    
             \addplot+[mark=none,purple] {80-x} node[pos=0](purple){};
             \node [right] at (purple) {\footnotesize{$ 1x_1 + 1x_2 \leq 80$}};    
%Fourth line red with a label                     
                \addplot+[mark=none,red] {(1/8)*12*x} node[pos=0.02](red){}; 
                \node [right] at (red) {\footnotesize{red}};
%Fifth line green with a label            
                   \addplot+[mark=none,green] {(1/4)*(290-3*x)} node[pos=0.5](green){};
                   \node [right] at (green) {\footnotesize{Inequality}};
%Min and max lines with labels           
                      \addplot+[name path=A, mark=none,style=dashed,green] {(1/4)*(100-3*x)} node[pos=0](min){};
                      \node [right] at (min) {\footnotesize{$\min$}};
                         \addplot+[name path=B, mark=none,style=dashed,green] {(1/4)*(350-3*x)}node[pos=0](max){};
                         \node [right] at (max) {\footnotesize{$\max$}};
% Colouring between the two dashed green lines aka min and max       
            \addplot[green!20] fill between[of=A and B];
\end{axis}
\end{tikzpicture}

\end{document}