6

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

  • 1
    Thanks for providing code. Can you make it so we can copy-paste-compile it? Makes it a lot easier for people to help, especially if they don't have to guess which class and packages you're using ;). – cfr Mar 24 '15 at 20:13
9

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:

enter image description here

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.
  • Waaw, that is indeed the figure I was looking for, but I'll need to investigate LuaLatex to apply these for other solutions. Thanks! – Jens Buysse Mar 26 '15 at 12:44
  • @Jens Buysse In fact, it is MetaPost coding much more than LuaLaTeX. See here for an introduction to MetaPost itself: staff.science.uva.nl/a.j.p.heck/Courses/mptut.pdf. One of LuaLaTeX's most prominent features is that it allows the inclusion of MetaPost programs thanks to the luamplib package. – Franck Pastor Mar 26 '15 at 13:36
6

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?

enter image description here

\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}
  • Well it's part of the solution, but what I wanted was indeed somehting like the answer of fpast, although I have never heard of LuaLatex. I'll have to look into that though. – Jens Buysse Mar 26 '15 at 12:43
  • It would be possible to edit the above LaTeX code to look like fpast's figure if you run into trouble with LuaLaTeX, though I don't expect that you will. – Christopher Mar 26 '15 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.