File:IntLinPgmRelax.pdf
Summary
| Description |
English: Integer linear program (red) and its relaxation (blue). Both are characterized by the inequation set . In this example, the function to be maximized is simply . The optimum is if only integer coordinates are allowed, but if real coordinates are allowed. |
| Date | |
| Source | Own work |
| Author | Jochen Burghardt |
| Other versions | File:IntLinPgmRelax.pdf * File:IntLinPgmRelax svg.svg |
LaTeX source code |
|---|
\documentclass[12pt]{article}
\usepackage{color}
\usepackage[paperwidth=170mm,paperheight=40mm,textwidth=170mm,textheight=40mm]{geometry}
\usepackage{amssymb}
\setlength{\unitlength}{1mm}
\setlength{\parindent}{0em}
\definecolor{fInt} {rgb}{0.99,0.00,0.00}% integer
\definecolor{fReal} {rgb}{0.00,0.00,0.99}% contraint
\definecolor{fMs} {rgb}{0.50,0.50,0.59}% measure
\begin{document}%
\begin{picture}(170,40)%
%\put(0,0){\makebox(0,0){$+$}}%
%\put(170,40){\makebox(0,0){$+$}}%
\thicklines%
% x axis
\put( 27,4){\vector(1,0){133}}%
\put(160,3){\makebox(0,0)[tr]{$\scriptstyle x$}}%
\textcolor{fMs}{\put( 40,3){\makebox(0,0)[t]{$\scriptstyle 1$}}}%
\textcolor{fMs}{\put( 50,3){\makebox(0,0)[t]{$\scriptstyle 2$}}}%
\textcolor{fMs}{\put( 60,3){\makebox(0,0)[t]{$\scriptstyle 3$}}}%
\textcolor{fMs}{\put( 70,3){\makebox(0,0)[t]{$\scriptstyle 4$}}}%
\textcolor{fMs}{\put( 80,3){\makebox(0,0)[t]{$\scriptstyle 5$}}}%
\textcolor{fMs}{\put( 90,3){\makebox(0,0)[t]{$\scriptstyle 6$}}}%
\textcolor{fMs}{\put(100,3){\makebox(0,0)[t]{$\scriptstyle 7$}}}%
\textcolor{fMs}{\put(110,3){\makebox(0,0)[t]{$\scriptstyle 8$}}}%
\textcolor{fMs}{\put(120,3){\makebox(0,0)[t]{$\scriptstyle 9$}}}%
\textcolor{fMs}{\put(130,3){\makebox(0,0)[t]{$\scriptstyle 10$}}}%
\textcolor{fMs}{\put(140,3){\makebox(0,0)[t]{$\scriptstyle 11$}}}%
\textcolor{fMs}{\put(150,3){\makebox(0,0)[t]{$\scriptstyle 12$}}}%
% y axis
\put(30, 1){\vector(0,1){38}}%
\put(29,39){\makebox(0,0)[tr]{$\scriptstyle y$}}%
\textcolor{fMs}{\put(29,14){\makebox(0,0)[r]{$\scriptstyle 1$}}}%
\textcolor{fMs}{\put(29,24){\makebox(0,0)[r]{$\scriptstyle 2$}}}%
\textcolor{fMs}{\put(29,34){\makebox(0,0)[r]{$\scriptstyle 3$}}}%
% int points
\textcolor{fMs}{\multiput(30, 4)(10,0){13}{\circle*{0.7}}}%
\textcolor{fMs}{\multiput(30,14)(10,0){13}{\circle*{0.7}}}%
\textcolor{fMs}{\multiput(30,24)(10,0){13}{\circle*{0.7}}}%
\textcolor{fMs}{\multiput(30,34)(10,0){13}{\circle*{0.7}}}%
% constraints
\textcolor{fReal}{\put(24,25){\line(6,-1){133}}}%
\textcolor{fReal}{\put(24, 6){\line(1, 0){133}}}%
\textcolor{fReal}{\put(23,25){\makebox(0,0)[tr]{$x \!+\! 6y \leqslant 12$}}}%
\textcolor{fReal}{\put(23, 7){\makebox(0,0)[br]{$1 \leqslant 5y$}}}%
% int feasible region
\textcolor{fInt}{\multiput(30,14)(10,0){7}{\circle*{0.9}}}%
\textcolor{fInt}{\multiput(30,24)(10,0){1}{\circle*{0.9}}}%
%
\thinlines%
% int optimum
\textcolor{fInt}{\put(90,29){\vector(0,-1){12}}}%
\textcolor{fInt}{\put(91,29){\makebox(0,0)[tl]{$x_{opt} = 6$}}}%
% real optimum
\textcolor{fReal}{\put(138,19){\vector(0,-1){11}}}%
\textcolor{fReal}{\put(139,19){\makebox(0,0)[tl]{$x_{opt} = 10.8$}}}%
\end{picture}%
\end{document}
|
Licensing
I, the copyright holder of this work, hereby publish it under the following license:
  |
This file is made available under the Creative Commons CC0 1.0 Universal Public Domain Dedication. |
| The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.
|