aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--aoc/n3.lyx2
-rw-r--r--graf/n.lyx42
-rw-r--r--graf/n4.lyx6
-rw-r--r--graf/n5.lyx2106
-rw-r--r--graf/n6.lyx2099
-rw-r--r--graf/n7.lyx1822
6 files changed, 6075 insertions, 2 deletions
diff --git a/aoc/n3.lyx b/aoc/n3.lyx
index b76f960..dbde7a7 100644
--- a/aoc/n3.lyx
+++ b/aoc/n3.lyx
@@ -2220,7 +2220,7 @@ edge-cube routing
.
\end_layout
-\begin_layout Section
+\begin_layout Subsection
Estrategia de conmutación
\end_layout
diff --git a/graf/n.lyx b/graf/n.lyx
index 1c55080..c09c5e1 100644
--- a/graf/n.lyx
+++ b/graf/n.lyx
@@ -257,5 +257,47 @@ filename "n4.lyx"
\end_layout
+\begin_layout Chapter
+Coloración de grafos
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n5.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Chapter
+Programación lineal entera
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n6.lyx"
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Chapter
+Resolución de problemas de programación lineal entera
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "n7.lyx"
+
+\end_inset
+
+
+\end_layout
+
\end_body
\end_document
diff --git a/graf/n4.lyx b/graf/n4.lyx
index ec6340b..6674531 100644
--- a/graf/n4.lyx
+++ b/graf/n4.lyx
@@ -1927,7 +1927,11 @@ problema del viajero
\series bold
del viajante
\series default
- en una red
+ (
+\series bold
+de comercio
+\series default
+) en una red
\begin_inset Formula $(V,E,\ell)$
\end_inset
diff --git a/graf/n5.lyx b/graf/n5.lyx
new file mode 100644
index 0000000..4ae5cf7
--- /dev/null
+++ b/graf/n5.lyx
@@ -0,0 +1,2106 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\usepackage{amssymb}
+\end_preamble
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Dado un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ y un conjunto
+\begin_inset Formula $S$
+\end_inset
+
+ de
+\series bold
+colores
+\series default
+, llamamos
+\series bold
+coloración
+\series default
+ (
+\series bold
+propia por vértices
+\series default
+) de
+\begin_inset Formula $G$
+\end_inset
+
+ a una función
+\begin_inset Formula $f:V\to S$
+\end_inset
+
+ con
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ para
+\begin_inset Formula $(u,v)\in E$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $|S|=k$
+\end_inset
+
+,
+\begin_inset Formula $f$
+\end_inset
+
+ es una
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-coloración
+\series default
+, y
+\begin_inset Formula $G$
+\end_inset
+
+ es
+\series bold
+
+\begin_inset Formula $k$
+\end_inset
+
+-coloreable
+\series default
+ si admite una
+\begin_inset Formula $k$
+\end_inset
+
+-coloración.
+ Una
+\begin_inset Formula $k$
+\end_inset
+
+-coloración
+\begin_inset Formula $f$
+\end_inset
+
+ induce una partición de
+\begin_inset Formula $V$
+\end_inset
+
+ en subconjuntos independientes, dados por
+\begin_inset Formula $f^{-1}(c)$
+\end_inset
+
+ para
+\begin_inset Formula $c\in S$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+número cromático
+\series default
+ de un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+, es el menor
+\begin_inset Formula $k$
+\end_inset
+
+ tal que
+\begin_inset Formula $G$
+\end_inset
+
+ es
+\begin_inset Formula $k$
+\end_inset
+
+-coloreable, el mínimo número de conjuntos independientes en que se puede
+ particionar
+\begin_inset Formula $V$
+\end_inset
+
+.
+ Ejemplos: Dado un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\chi(K_{n})=n$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+En adelante
+\begin_inset Formula $f$
+\end_inset
+
+ será una coloración.
+ Entonces, en este caso,
+\begin_inset Formula $f(i)\neq f(j)$
+\end_inset
+
+ para
+\begin_inset Formula $i\neq j$
+\end_inset
+
+, luego
+\begin_inset Formula $f$
+\end_inset
+
+ es inyectiva y su imagen tiene cardinal
+\begin_inset Formula $|V|=n$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\chi(G)=0$
+\end_inset
+
+ si y sólo si
+\begin_inset Formula $G$
+\end_inset
+
+ es vacío.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si
+\begin_inset Formula $\chi(G)=0$
+\end_inset
+
+, en particular existe
+\begin_inset Formula $f:V\to\emptyset$
+\end_inset
+
+ y
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+,
+\begin_inset Formula $E=\emptyset$
+\end_inset
+
+ y
+\begin_inset Formula $f:V\to\emptyset$
+\end_inset
+
+ es una 0-coloración.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\chi(G)=1$
+\end_inset
+
+ si y sólo si
+\begin_inset Formula $G$
+\end_inset
+
+ es no vacío y sin ejes.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Si existiera
+\begin_inset Formula $(u,v)\in E$
+\end_inset
+
+ sería
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ y por tanto
+\begin_inset Formula $|f(V)|\geq2\#$
+\end_inset
+
+, y si fuera
+\begin_inset Formula $V=\emptyset$
+\end_inset
+
+ sería
+\begin_inset Formula $|f(V)|=0\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Claramente
+\begin_inset Formula $|f(V)|\geq1$
+\end_inset
+
+, pero podemos tomar todos los nodos del mismo color.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $\chi(G)=2$
+\end_inset
+
+ si y sólo si
+\begin_inset Formula $G$
+\end_inset
+
+ es bipartito con algún eje.
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+La partición
+\begin_inset Formula $\{f^{-1}(0),f^{-1}(1)\}$
+\end_inset
+
+ de
+\begin_inset Formula $V$
+\end_inset
+
+ cumple que eje une dos vértices en el mismo conjunto y por tanto todos
+ unen un vértice de uno con uno del otro.
+ Hay algún eje porque si no lo hubiera sería
+\begin_inset Formula $\chi(G)=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea
+\begin_inset Formula $(A,B)$
+\end_inset
+
+ la partición, definimos
+\begin_inset Formula $f(v):=0$
+\end_inset
+
+ para
+\begin_inset Formula $v\in A$
+\end_inset
+
+ y
+\begin_inset Formula $f(v):=1$
+\end_inset
+
+ para
+\begin_inset Formula $v\in B$
+\end_inset
+
+.
+ Entonces
+\begin_inset Formula $f$
+\end_inset
+
+ es una 2-coloración de
+\begin_inset Formula $G$
+\end_inset
+
+, y como hay algún eje,
+\begin_inset Formula $\chi(G)>1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Todo árbol no trivial es bipartito.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Se tiene
+\begin_inset Formula $|V|\geq2$
+\end_inset
+
+ y, sea
+\begin_inset Formula $n(v)$
+\end_inset
+
+ el nivel de un
+\begin_inset Formula $v\in V$
+\end_inset
+
+,
+\begin_inset Formula $f:V\to\{0,1\}$
+\end_inset
+
+ dada por
+\begin_inset Formula $f(v):=[n(v)]_{2}$
+\end_inset
+
+ es una coloración de
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Como
+\begin_inset Formula $G$
+\end_inset
+
+ tiene ejes,
+\begin_inset Formula $\chi(G)>1$
+\end_inset
+
+ y
+\begin_inset Formula $\chi(G)=2$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Sea
+\begin_inset Formula $C_{n}$
+\end_inset
+
+ el anillo o
+\series bold
+ciclo
+\series default
+ de tamaño
+\begin_inset Formula $n$
+\end_inset
+
+,
+\begin_inset Formula
+\[
+\chi(C_{n})=\begin{cases}
+2, & n\text{ par};\\
+3, & n\text{ impar}.
+\end{cases}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Como
+\begin_inset Formula $C_{n}:=(V:=\{0,\dots,n-1\},\{\{i,[i+1]_{n}\}\}_{i\in V})$
+\end_inset
+
+ tiene ejes,
+\begin_inset Formula $\chi(C_{n})\geq2$
+\end_inset
+
+.
+ Para
+\begin_inset Formula $n$
+\end_inset
+
+ par, tomamos
+\begin_inset Formula $f(i)=[i]_{2}$
+\end_inset
+
+.
+ Para
+\begin_inset Formula $n$
+\end_inset
+
+ impar, si
+\begin_inset Formula $C_{n}$
+\end_inset
+
+ fuera bipartito, sea
+\begin_inset Formula $V_{0}$
+\end_inset
+
+ el elemento que contiene al 0 y
+\begin_inset Formula $V_{1}$
+\end_inset
+
+ el que contiene al 1, necesariamente
+\begin_inset Formula $V_{0}\neq V_{1}$
+\end_inset
+
+ y, por inducción, el que contiene a
+\begin_inset Formula $i$
+\end_inset
+
+ es
+\begin_inset Formula $V_{[i]_{2}}$
+\end_inset
+
+, pero entonces
+\begin_inset Formula $0,n-1\in V_{0}\#$
+\end_inset
+
+, con lo que
+\begin_inset Formula $C_{n}$
+\end_inset
+
+ no es bipartito y
+\begin_inset Formula $\chi(C_{n})>2$
+\end_inset
+
+, y tomamos
+\begin_inset Formula $f(i):=[i]_{2}$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,n-1\}$
+\end_inset
+
+ y
+\begin_inset Formula $f(0):=2$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $H$
+\end_inset
+
+ es un subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\chi(H)\leq\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Si
+\begin_inset Formula $f$
+\end_inset
+
+ es una
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G$
+\end_inset
+
+, también es una
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $H$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $K_{q}$
+\end_inset
+
+ es subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)\geq q$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Formula $q=\chi(K_{q})\leq\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $v\in V$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G-v)\in\{\chi(G),\chi(G)-1\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Sean
+\begin_inset Formula $k:=\chi(G-v)$
+\end_inset
+
+ y
+\begin_inset Formula $f:V\to\{1,\dots,k\}$
+\end_inset
+
+ una
+\begin_inset Formula $k$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G-v$
+\end_inset
+
+,
+\begin_inset Formula $k\leq\chi(G)$
+\end_inset
+
+, y como
+\begin_inset Formula $g:V\to\{1,\dots,k+1\}$
+\end_inset
+
+ dada por
+\begin_inset Formula $g(i):=f(i)$
+\end_inset
+
+ para
+\begin_inset Formula $i\neq v$
+\end_inset
+
+ y
+\begin_inset Formula $g(v):=k+1$
+\end_inset
+
+ es una
+\begin_inset Formula $(k+1)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)\leq k+1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $e\in E$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G-e)\in\{\chi(G),\chi(G)-1\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Sea
+\begin_inset Formula $e=:(u,v)$
+\end_inset
+
+, como
+\begin_inset Formula $G-v$
+\end_inset
+
+ es un subgrafo de
+\begin_inset Formula $G-e$
+\end_inset
+
+,
+\begin_inset Formula $\chi(G)-1\leq\chi(G-v)\leq\chi(G-e)\leq\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+El coloreado de grafos se puede aplicar a problemas que traten de distribuir
+ productos con ciertas relaciones de incompatibilidad, como en el coloreado
+ de mapas, los sudokus.
+ la asignación de frecuencias en torres de telecomunicaciones, la organización
+ de horarios o la distribución de productos peligrosos en un almacén.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Grafo $G=(V=
+\backslash
+{1,
+\backslash
+dots,n
+\backslash
+},E)$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Coloración $f$ de $G$ que intenta usar pocos colores.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lPara{$i
+\backslash
+gets1$
+\backslash
+KwA $n$}{$f_i
+\backslash
+gets
+\backslash
+min(
+\backslash
+mathbb N
+\backslash
+setminus
+\backslash
+{f_j
+\backslash
+}_{j
+\backslash
+in N(i),j<i})$}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:color"
+
+\end_inset
+
+Algoritmo heurístico para coloreado de grafos.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Podemos colorear un grafo con el algoritmo
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:color"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+, aunque este no garantiza una coloración óptima.
+ Todo grafo
+\begin_inset Formula $G$
+\end_inset
+
+ cumple
+\begin_inset Formula $\chi(G)\leq\Delta_{G}+1$
+\end_inset
+
+, pues el algoritmo siempre elige el menor color de todos salvo un conjunto
+ de tamaño máximo
+\begin_inset Formula $\Delta_{G}$
+\end_inset
+
+.
+ Así, parece preferible al aplicar el algoritmo ordenar los nodos en orden
+ decreciente de sus grados.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de Brooks:
+\series default
+ Si un grafo conexo
+\begin_inset Formula $G$
+\end_inset
+
+ no es completo ni un ciclo de longitud impar, entonces
+\begin_inset Formula $\chi(G)\leq\Delta_{G}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Grafos críticos
+\end_layout
+
+\begin_layout Standard
+Un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ es
+\series bold
+crítico
+\series default
+ o
+\series bold
+
+\begin_inset Formula $\chi(G)$
+\end_inset
+
+-crítico
+\series default
+ si todo subgrafo estricto
+\begin_inset Formula $H$
+\end_inset
+
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ cumple
+\begin_inset Formula $\chi(H)<\chi(G)$
+\end_inset
+
+,
+\series bold
+crítico por ejes
+\series default
+ si para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+ es
+\begin_inset Formula $\chi(G-e)<\chi(G)$
+\end_inset
+
+ y
+\series bold
+crítico por vértices
+\series default
+ si para todo
+\begin_inset Formula $v\in V$
+\end_inset
+
+ es
+\begin_inset Formula $\chi(G-v)<\chi(G)$
+\end_inset
+
+.
+
+\end_layout
+
+\begin_layout Standard
+Entonces:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico si y sólo si es crítico por ejes y por vértices.
+\end_layout
+
+\begin_layout Enumerate
+Si
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico por ejes y no tiene nodos aislados, es crítico por vértices.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Para
+\begin_inset Formula $v\in V$
+\end_inset
+
+,
+\begin_inset Formula $v$
+\end_inset
+
+ es adyacente a algún
+\begin_inset Formula $e\in E$
+\end_inset
+
+ y
+\begin_inset Formula $G-v$
+\end_inset
+
+ es un subgrafo de
+\begin_inset Formula $G-e$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico por ejes si y sólo si
+\begin_inset Formula $\chi(G-e)=\chi(G)-1$
+\end_inset
+
+ para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+\begin_inset Formula $\chi(G-e)\in\{\chi(G),\chi(G)-1\}$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+Si
+\begin_inset Formula $|V|\geq2$
+\end_inset
+
+,
+\begin_inset Formula $G$
+\end_inset
+
+ tiene un subgrafo crítico
+\begin_inset Formula $H$
+\end_inset
+
+ tal que
+\begin_inset Formula $\chi(G)=\chi(H)$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Si todos los vértices de
+\begin_inset Formula $G$
+\end_inset
+
+ son aislados,
+\begin_inset Formula $\chi(G)=1$
+\end_inset
+
+ y tomamos un subgrafo unipuntual, que es crítico.
+ En otro caso, sea
+\begin_inset Formula $G_{0}$
+\end_inset
+
+ el subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+ generado por sus vértices no aislados, claramente
+\begin_inset Formula $G_{0}$
+\end_inset
+
+ tiene orden al menos 2 y
+\begin_inset Formula $\chi(G_{0})=\chi(G)$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $G_{0}$
+\end_inset
+
+ es crítico, tomamos
+\begin_inset Formula $G_{0}$
+\end_inset
+
+, y de lo contrario existe
+\begin_inset Formula $e_{1}\in E$
+\end_inset
+
+ con
+\begin_inset Formula $\chi(H_{0}:=G_{0}-e_{1})=\chi(G_{0})$
+\end_inset
+
+.
+ Si todos los vértices de
+\begin_inset Formula $H_{0}$
+\end_inset
+
+ son aislados,
+\begin_inset Formula $\chi(H_{0})=\chi(G)=1$
+\end_inset
+
+ y tomamos un subgrafo unipuntual, y de lo contrario llamamos
+\begin_inset Formula $G_{1}$
+\end_inset
+
+ al subgrafo de
+\begin_inset Formula $H_{0}$
+\end_inset
+
+ generado por sus vértices no aislados y repetimos.
+ Como
+\begin_inset Formula $E$
+\end_inset
+
+ es finito, en algún momento se llega a un subgrafo crítico.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+Como
+\series bold
+teorema
+\series default
+, si
+\begin_inset Formula $G$
+\end_inset
+
+ es crítico,
+\begin_inset Formula $\chi(G)\leq\delta_{G}+1$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Sea
+\begin_inset Formula $k:=\chi(G)$
+\end_inset
+
+ y supongamos
+\begin_inset Formula $k>\delta_{G}+1$
+\end_inset
+
+, con lo que
+\begin_inset Formula $\delta_{G}\leq k-2$
+\end_inset
+
+.
+ Sea
+\begin_inset Formula $v\in V$
+\end_inset
+
+ con
+\begin_inset Formula $o(v)=\delta_{G}$
+\end_inset
+
+, debe ser
+\begin_inset Formula $\chi(G-v)=\chi(G)-1$
+\end_inset
+
+, pero en una coloración de
+\begin_inset Formula $G-v$
+\end_inset
+
+, como
+\begin_inset Formula $v$
+\end_inset
+
+ es de menor grado, se usan a lo sumo
+\begin_inset Formula $\delta_{G}\leq k-2$
+\end_inset
+
+ colores para los vértices adyacentes a
+\begin_inset Formula $v$
+\end_inset
+
+ en
+\begin_inset Formula $G$
+\end_inset
+
+, luego hay un color que no se ha utilizado y, pintando
+\begin_inset Formula $v$
+\end_inset
+
+ de ese color, tenemos una
+\begin_inset Formula $(k-1)$
+\end_inset
+
+-coloración de
+\begin_inset Formula $G\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Polinomio cromático
+\end_layout
+
+\begin_layout Standard
+Dados un grafo
+\begin_inset Formula $G$
+\end_inset
+
+ y
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+, llamamos
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ al número de
+\begin_inset Formula $k$
+\end_inset
+
+-coloraciones de
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Así:
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $p(G,k)=0$
+\end_inset
+
+ para todo
+\begin_inset Formula $k<\chi(G)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $p(K_{n},k)=k(k-1)\cdots(k-n+1)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Sea
+\begin_inset Formula $P_{n}$
+\end_inset
+
+ la malla unidimensional o
+\series bold
+cadena
+\series default
+ de
+\begin_inset Formula $n$
+\end_inset
+
+ nodos,
+\begin_inset Formula $p(P_{n},k)=k(k-1)^{n-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Si
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+,
+\begin_inset Formula $u,v\in E$
+\end_inset
+
+ y
+\begin_inset Formula $e:=(u,v)$
+\end_inset
+
+, llamamos
+\begin_inset Formula $G+e:=(V,E\cup\{e\})$
+\end_inset
+
+, y si
+\begin_inset Formula $e\in E$
+\end_inset
+
+ llamamos
+\series bold
+grafo contraído
+\series default
+ a
+\begin_inset Formula
+\[
+G\circ e:=((V\setminus\{u,v\})\amalg\{*\},E_{V\setminus\{u,v\}}\cup(\{(*,i)\}_{(u,i)\in E}\cup\{(*,i)\}_{(v,i)\in E})\setminus\{u,v\}).
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de reducción:
+\series default
+ Sean
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ un grafo y
+\begin_inset Formula $e\notin E^{\complement}$
+\end_inset
+
+, entonces
+\begin_inset Formula $p(G;k)=p(G+e;k)+p(G\circ e;k)$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Sea
+\begin_inset Formula $(u,v):=e$
+\end_inset
+
+, las coloraciones
+\begin_inset Formula $f$
+\end_inset
+
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ con
+\begin_inset Formula $f(u)=f(v)$
+\end_inset
+
+ son precisamente las de
+\begin_inset Formula $G\circ e$
+\end_inset
+
+ haciendo
+\begin_inset Formula $f(*):=f(u)=f(v)$
+\end_inset
+
+, y las coloraciones
+\begin_inset Formula $f$
+\end_inset
+
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ con
+\begin_inset Formula $f(u)\neq f(v)$
+\end_inset
+
+ son precisamente las de
+\begin_inset Formula $G+e$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Así, dados un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ y un
+\begin_inset Formula $e\in E$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)=p(G-e;k)-p(G\circ e;k)$
+\end_inset
+
+, pues
+\begin_inset Formula $G=(G-e)+e$
+\end_inset
+
+ y
+\begin_inset Formula $G\circ e=(G-e)\circ e$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Newpage pagebreak
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+polinomio cromático
+\series default
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ es
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ respecto a
+\begin_inset Formula $k$
+\end_inset
+
+, y si
+\begin_inset Formula $G$
+\end_inset
+
+ tiene grado
+\begin_inset Formula $n\geq1$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ es un polinomio de grado
+\begin_inset Formula $n$
+\end_inset
+
+ en que el coeficiente de grado
+\begin_inset Formula $n$
+\end_inset
+
+ es 1, el término independiente es 0 y los coeficientes de los términos
+ intermedios son enteros y se alternan en signo.
+
+\series bold
+Demostración:
+\series default
+ Sean
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+,
+\begin_inset Formula $n=|V|$
+\end_inset
+
+ y
+\begin_inset Formula $m=|E|$
+\end_inset
+
+, y hacemos inducción sobre
+\begin_inset Formula $(n,m)$
+\end_inset
+
+ (el orden lexicográfico es un buen orden en
+\begin_inset Formula $\mathbb{N}^{*}\times\mathbb{N}$
+\end_inset
+
+).
+ Para
+\begin_inset Formula $m=0$
+\end_inset
+
+, todos los puntos son aislados y
+\begin_inset Formula $p(G;k)=k^{n}$
+\end_inset
+
+, y para
+\begin_inset Formula $n=1$
+\end_inset
+
+ es
+\begin_inset Formula $m=0$
+\end_inset
+
+.
+ Sean ahora
+\begin_inset Formula $n>1$
+\end_inset
+
+ y
+\begin_inset Formula $m>0$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)=p(G-e;k)-p(G\circ e;k)$
+\end_inset
+
+, pero
+\begin_inset Formula $G-e$
+\end_inset
+
+ tiene un eje menos y
+\begin_inset Formula $G\circ e$
+\end_inset
+
+ tiene un nodo menos, luego ambos cumplen la hipótesis y como
+\begin_inset Formula $p(G-e;k)$
+\end_inset
+
+ tiene orden
+\begin_inset Formula $n$
+\end_inset
+
+ y
+\begin_inset Formula $p(G\circ e;k)$
+\end_inset
+
+ tiene orden
+\begin_inset Formula $n-1$
+\end_inset
+
+,
+\begin_inset Formula $p(G;k)$
+\end_inset
+
+ cumple la hipótesis.
+\end_layout
+
+\begin_layout Section
+Planaridad
+\end_layout
+
+\begin_layout Standard
+Un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ es
+\series bold
+planar
+\series default
+ si existen
+\begin_inset Formula $f:V\to\mathbb{R}^{2}$
+\end_inset
+
+ inyectiva y
+\begin_inset Formula $g:E\to[0,1]\to\mathbb{R}^{2}$
+\end_inset
+
+ tales que, para
+\begin_inset Formula $e:=(u,v)\in E$
+\end_inset
+
+,
+\begin_inset Formula $g(e)$
+\end_inset
+
+ es una curva regular simple que une
+\begin_inset Formula $f(u)$
+\end_inset
+
+ y
+\begin_inset Formula $f(v)$
+\end_inset
+
+, no pasa por ningún vértice en
+\begin_inset Formula $(0,1)$
+\end_inset
+
+ y no corta a
+\begin_inset Formula $g(e')$
+\end_inset
+
+ para ningún otro
+\begin_inset Formula $e'\in E$
+\end_inset
+
+ en
+\begin_inset Formula $(0,1)$
+\end_inset
+
+.
+ En tal caso
+\begin_inset Formula $(V,E,f,g)$
+\end_inset
+
+ es un
+\series bold
+grafo plano
+\series default
+ o
+\series bold
+grafo embutido
+\series default
+, con imagen
+\begin_inset Formula $f(V)\cup\bigcup_{e\in E}g(e)([0,1])$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Una
+\series bold
+estrella
+\series default
+ es un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+ donde existe un
+\begin_inset Formula $v\in V$
+\end_inset
+
+ con
+\begin_inset Formula $v\in e$
+\end_inset
+
+ para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+.
+ Toda estrella es planar.
+ En efecto, sea
+\begin_inset Formula $G=(\{v_{0},\dots,v_{n}\},E)$
+\end_inset
+
+ la estrella y
+\begin_inset Formula $v_{0}\in e$
+\end_inset
+
+ para todo
+\begin_inset Formula $e\in E$
+\end_inset
+
+, llamamos
+\begin_inset Formula $f(v_{0}):=0$
+\end_inset
+
+,
+\begin_inset Formula $f(v_{i}):=(\cos i/n,\sin i/n)$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,n\}$
+\end_inset
+
+ y
+\begin_inset Formula $g(v_{0},v_{i})(t):=tv_{i}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Sea
+\begin_inset Formula $(V,E,f,g)$
+\end_inset
+
+ un grafo plano con imagen
+\begin_inset Formula $I$
+\end_inset
+
+, llamamos
+\series bold
+caras
+\series default
+ a las componentes conexas de
+\begin_inset Formula $\mathbb{R}^{2}\setminus I$
+\end_inset
+
+ y
+\series bold
+cara externa
+\series default
+ a la no acotada, que es única por ser
+\begin_inset Formula $I$
+\end_inset
+
+ compacto y por tanto acotado.
+
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+contorno
+\series default
+ de una cara es la imagen de un subgrafo de
+\begin_inset Formula $G$
+\end_inset
+
+, que existe, cuya imagen con las mismas
+\begin_inset Formula $f$
+\end_inset
+
+ y
+\begin_inset Formula $g$
+\end_inset
+
+ es la frontera de la cara.
+ Los ejes y vértices de dicho subgrafo son
+\series bold
+incidentes
+\series default
+ a la cara.
+ Un puente es incidente a una sola cara, y un eje no de corte es incidente
+ a 2 caras.
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+grado
+\series default
+ de una cara
+\begin_inset Formula $F$
+\end_inset
+
+,
+\begin_inset Formula $d(F)$
+\end_inset
+
+, es el número de ejes incidentes a ella, contando los puentes dos veces.
+ Así, si
+\begin_inset Formula $F$
+\end_inset
+
+ es el conjunto de caras del grafo,
+\begin_inset Formula $\sum_{f\in F}d(f)=2|E|$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $|V|\geq3$
+\end_inset
+
+,
+\begin_inset Formula $d(f)\geq3$
+\end_inset
+
+ para todo
+\begin_inset Formula $f\in F$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Identidad de Euler:
+\series default
+ Si
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo plano conexo con
+\begin_inset Formula $n$
+\end_inset
+
+ vértices,
+\begin_inset Formula $m$
+\end_inset
+
+ ejes y
+\begin_inset Formula $c$
+\end_inset
+
+ caras,
+\begin_inset Formula $n-m+c=2$
+\end_inset
+
+, y en particular todos los grafos planos de un mismo grafo planar conexo
+ tienen el mismo número de caras.
+
+\series bold
+Demostración:
+\series default
+ Si
+\begin_inset Formula $c=1$
+\end_inset
+
+,
+\begin_inset Formula $G$
+\end_inset
+
+ no tiene ciclos y, al ser conexo, es un árbol, luego
+\begin_inset Formula $m=n-1$
+\end_inset
+
+ y
+\begin_inset Formula $n-m+c=2$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $c\geq2$
+\end_inset
+
+, supuesto esto probado para
+\begin_inset Formula $c-1$
+\end_inset
+
+ caras, sean
+\begin_inset Formula $C$
+\end_inset
+
+ un ciclo de
+\begin_inset Formula $G$
+\end_inset
+
+ y
+\begin_inset Formula $e$
+\end_inset
+
+ un eje de
+\begin_inset Formula $C$
+\end_inset
+
+,
+\begin_inset Formula $e$
+\end_inset
+
+ no es un puente, luego es incidente a 2 caras y se puede ver que
+\begin_inset Formula $G-e$
+\end_inset
+
+ tiene
+\begin_inset Formula $c-1$
+\end_inset
+
+ caras y es conexo, de modo que por hipótesis
+\begin_inset Formula $n-(m-1)+(c-1)=2$
+\end_inset
+
+ y
+\begin_inset Formula $n-m+c=2$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+En un grafo plano con al menos 3 nodos, toda cara tiene al menos 3 ejes
+ incidentes.
+ Entonces, si
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo planar conexo con
+\begin_inset Formula $n\geq3$
+\end_inset
+
+ vértices y
+\begin_inset Formula $m$
+\end_inset
+
+ nodos,
+\begin_inset Formula $m\leq3n-6$
+\end_inset
+
+, y si además
+\begin_inset Formula $G$
+\end_inset
+
+ no contiene a
+\begin_inset Formula $K_{3}$
+\end_inset
+
+,
+\begin_inset Formula $m\leq2n-4$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Sean
+\begin_inset Formula $F$
+\end_inset
+
+ el conjunto de las caras de un grafo plano arbitrario de
+\begin_inset Formula $G$
+\end_inset
+
+ y
+\begin_inset Formula $c:=|F|$
+\end_inset
+
+, como toda
+\begin_inset Formula $f\in F$
+\end_inset
+
+ cumple
+\begin_inset Formula $d(f)\geq3$
+\end_inset
+
+,
+\begin_inset Formula $3c\leq\sum_{f\in F}d(f)=2m$
+\end_inset
+
+, y como
+\begin_inset Formula $c=2-n+m$
+\end_inset
+
+, tenemos
+\begin_inset Formula $6-3n+3m\leq2m$
+\end_inset
+
+ y
+\begin_inset Formula $m\leq3n-6$
+\end_inset
+
+.
+ Si una cara
+\begin_inset Formula $f$
+\end_inset
+
+ cumple
+\begin_inset Formula $d(f)=3$
+\end_inset
+
+, se puede ver que el único grafo con 3 ejes contando doblemente los puentes
+ es
+\begin_inset Formula $K_{3}$
+\end_inset
+
+, por lo que si
+\begin_inset Formula $G$
+\end_inset
+
+ no contiene a
+\begin_inset Formula $K_{3}$
+\end_inset
+
+,
+\begin_inset Formula $d(f)\geq4$
+\end_inset
+
+,
+\begin_inset Formula $4c=8-4n+4m\leq2m$
+\end_inset
+
+ y
+\begin_inset Formula $2m\leq4n-8$
+\end_inset
+
+, por lo que
+\begin_inset Formula $m\leq2n-4$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Por ejemplo, el
+\series bold
+grafo de Petersen
+\series default
+,
+\begin_inset Formula $(\{a_{i},b_{i}\}_{i=0}^{4},\{(a_{i},b_{i}),(a_{i},a_{[i+1]_{5}}),(b_{i},b_{[i+2]_{5}})\}_{i=0}^{4})$
+\end_inset
+
+, no es un grafo planar, pues tiene 5 nodos y 15 ejes, y
+\begin_inset Formula $15>9=3\cdot5-6$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Sea
+\begin_inset Formula $F$
+\end_inset
+
+ una cara de un grafo plano con
+\begin_inset Formula $d(F)\geq4$
+\end_inset
+
+, el grafo tiene dos vértices no adyacentes en
+\begin_inset Formula $F$
+\end_inset
+
+.
+ Entonces, si
+\begin_inset Formula $G$
+\end_inset
+
+ es un grafo planar maximal con al menos 3 nodos, toda cara
+\begin_inset Formula $F$
+\end_inset
+
+ de todo grafo plano de
+\begin_inset Formula $G$
+\end_inset
+
+ cumple
+\begin_inset Formula $d(F)=3$
+\end_inset
+
+.
+ Como
+\series bold
+teorema
+\series default
+, todo grafo planar maximal con
+\begin_inset Formula $n$
+\end_inset
+
+ nodos tiene exactamente
+\begin_inset Formula $3n-6$
+\end_inset
+
+ ejes.
+\end_layout
+
+\begin_layout Standard
+Dado un grafo
+\begin_inset Formula $G=(V,E)$
+\end_inset
+
+, una
+\series bold
+subdivisión de un eje
+\series default
+
+\begin_inset Formula $e=(u,v)\in E$
+\end_inset
+
+ es el grafo
+\begin_inset Formula $(V\amalg\{*\},E\setminus e\cup(u,*)\cup(*,v))$
+\end_inset
+
+, y una
+\series bold
+subdivisión
+\series default
+ de
+\begin_inset Formula $G$
+\end_inset
+
+ es el resultado de realizar subdivisiones sucesivas sobre
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de Kuratowski:
+\series default
+ Un grafo es planar si y sólo si no contiene como subgrafo ninguna subdivisión
+ de
+\begin_inset Formula $K_{5}$
+\end_inset
+
+ ni de
+\begin_inset Formula $K_{3,3}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de los 4 colores:
+\series default
+ Todo grafo planar es 4-coloreable.
+\end_layout
+
+\end_body
+\end_document
diff --git a/graf/n6.lyx b/graf/n6.lyx
new file mode 100644
index 0000000..e296d0b
--- /dev/null
+++ b/graf/n6.lyx
@@ -0,0 +1,2099 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\usepackage{amssymb}
+\end_preamble
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+Un
+\series bold
+modelo
+\series default
+ o
+\series bold
+problema de programación lineal entera
+\series default
+ es un modelo de programación u optimización lineal al que se le añade la
+ restricción de que algunas o todas las variables deben ser enteras.
+ El modelo general es
+\begin_inset Formula
+\begin{align*}
+ & \max & \sum_{i=1}^{n}c_{i}x_{i}\\
+ & & \sum_{i=1}^{n}a_{ij}x_{i} & \leq b_{j}, & & \forall j\in\{1,\dots,m\},\\
+ & & x_{i} & \geq0, & & \forall i\in\{1,\dots,n\},\\
+ & & x_{i} & \in\mathbb{Z}, & & \forall i\in I\subseteq\{1,\dots,n\}.
+\end{align*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+El problema es
+\series bold
+entero puro
+\series default
+ si
+\begin_inset Formula $I=\{1,\dots,n\}$
+\end_inset
+
+ y
+\series bold
+entero mixto
+\series default
+ en otro caso.
+ Como en la programación lineal, se pueden hacer transformaciones como cambiar
+ el sentido de optimización del problema, el sentido de una restricción
+ o el signo de una variable; convertir una restricción de igualdad en dos
+ de desigualdad, o transformar una variable no restringida en dos variables
+ positivas.
+\end_layout
+
+\begin_layout Standard
+Llamamos
+\series bold
+relajación lineal
+\series default
+ de un problema de programación lineal entera al resultado de eliminar de
+ este las
+\series bold
+restricciones de integridad
+\series default
+, las de la forma
+\begin_inset Formula $x_{i}\in\mathbb{Z}$
+\end_inset
+
+.
+ El valor óptimo de la relajación lineal es mejor o igual al del problema
+ entero.
+\end_layout
+
+\begin_layout Standard
+Si
+\begin_inset Formula $x\in\mathbb{R}^{m}$
+\end_inset
+
+ e
+\begin_inset Formula $y\in\mathbb{R}^{n}$
+\end_inset
+
+, llamamos
+\begin_inset Formula $[x,y]:=(x_{1},\dots,x_{m},y_{1},\dots,y_{n})\in\mathbb{R}^{n+m}$
+\end_inset
+
+; si
+\begin_inset Formula $A\in{\cal M}_{n\times p}(\mathbb{R})$
+\end_inset
+
+ y
+\begin_inset Formula $B\in{\cal M}_{n\times q}(\mathbb{R})$
+\end_inset
+
+, llamamos
+\begin_inset Formula $[A,B]:=(c_{ij})\in{\cal M}_{n\times(p+q)}(\mathbb{R})$
+\end_inset
+
+ dada por
+\begin_inset Formula $c_{ij}:=a_{ij}$
+\end_inset
+
+ para
+\begin_inset Formula $j\leq p$
+\end_inset
+
+ y
+\begin_inset Formula $c_{ij}:=b_{i(j-p)}$
+\end_inset
+
+ para
+\begin_inset Formula $j>p$
+\end_inset
+
+, y escribimos
+\begin_inset Formula $[x_{1},\dots,x_{n}]:=[x_{1},[x_{2},\dots,x_{n}]]$
+\end_inset
+
+ para
+\begin_inset Formula $n>2$
+\end_inset
+
+ y
+\begin_inset Formula $[x_{1}]:=x_{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Como
+\series bold
+teorema
+\series default
+, sean
+\begin_inset Formula $A\in{\cal M}_{n\times p}(\mathbb{Q})$
+\end_inset
+
+,
+\begin_inset Formula $G\in{\cal M}_{n\times q}(\mathbb{Q})$
+\end_inset
+
+,
+\begin_inset Formula $b\in\mathbb{Q}^{n}$
+\end_inset
+
+,
+\begin_inset Formula $P:=\{[x,y]\in\mathbb{R}^{p+q}:Ax+Gy\leq b\}$
+\end_inset
+
+ y
+\begin_inset Formula $S:=\{[x,y]\in P:x\in\mathbb{Z}^{p}\}$
+\end_inset
+
+, existen
+\begin_inset Formula $A'\in{\cal M}_{n\times p}(\mathbb{Q})$
+\end_inset
+
+,
+\begin_inset Formula $G'\in{\cal M}_{n\times q}(\mathbb{Q})$
+\end_inset
+
+ y
+\begin_inset Formula $b'\in\mathbb{Q}^{n}$
+\end_inset
+
+ tales que
+\begin_inset Formula $\text{ec}S=\{[x,y]:A'x+G'y\leq b'\}$
+\end_inset
+
+.
+ Si algunos coeficientes son irracionales, la envoltura convexa del conjunto
+ factible puede no ser un poliedro.
+
+\series bold
+Demostración:
+\series default
+ Sean
+\begin_inset Formula $S:=\{(x,y)\in\mathbb{Z}^{2}:y\leq\sqrt{2}x,x\geq0,y\geq0\}$
+\end_inset
+
+ y
+\begin_inset Formula $C:=\{(x,y):y<\sqrt{2}x,x\geq0,y\geq0\}\cup\{0\}$
+\end_inset
+
+.
+ Como para
+\begin_inset Formula $x\in\mathbb{Z}$
+\end_inset
+
+ es
+\begin_inset Formula $\sqrt{2}x\notin\mathbb{Z}$
+\end_inset
+
+,
+\begin_inset Formula $S\subseteq C$
+\end_inset
+
+.
+ Sean
+\begin_inset Formula $a,b\in C$
+\end_inset
+
+,
+\begin_inset Formula $t\in[0,1]$
+\end_inset
+
+ y
+\begin_inset Formula $p:=(1-t)a+tb$
+\end_inset
+
+, si uno de
+\begin_inset Formula $a$
+\end_inset
+
+ o
+\begin_inset Formula $b$
+\end_inset
+
+ es 0, por ejemplo
+\begin_inset Formula $a$
+\end_inset
+
+, entonces
+\begin_inset Formula $p=(tb_{1},tb_{2})$
+\end_inset
+
+, que es 0 si
+\begin_inset Formula $t=0$
+\end_inset
+
+ y en otro caso cumple las otras condiciones, y en otro caso
+\begin_inset Formula $p$
+\end_inset
+
+
+\begin_inset Quotes cld
+\end_inset
+
+hereda
+\begin_inset Quotes crd
+\end_inset
+
+ las otras condiciones de
+\begin_inset Formula $a$
+\end_inset
+
+ y
+\begin_inset Formula $b$
+\end_inset
+
+.
+ Por tanto
+\begin_inset Formula $C$
+\end_inset
+
+ es conexo y
+\begin_inset Formula $\text{ec}S\subseteq C$
+\end_inset
+
+.
+ Además,
+\begin_inset Formula $0\in S$
+\end_inset
+
+ y para
+\begin_inset Formula $(x,y)\in C\setminus\{0\}$
+\end_inset
+
+, como
+\begin_inset Formula $x>0$
+\end_inset
+
+,
+\begin_inset Formula $\frac{y}{x}<\sqrt{2}$
+\end_inset
+
+ y existen
+\begin_inset Formula $p,q\in\mathbb{Z}$
+\end_inset
+
+ con
+\begin_inset Formula $\frac{p}{q}\in[\frac{y}{x},\sqrt{2})$
+\end_inset
+
+, luego
+\begin_inset Formula $(q,p)\in S$
+\end_inset
+
+ y, como
+\begin_inset Formula $(q,0)\in S$
+\end_inset
+
+ y
+\begin_inset Formula $p>q\frac{y}{x}$
+\end_inset
+
+,
+\begin_inset Formula $(q,q\frac{y}{x})\in\text{ec}S$
+\end_inset
+
+ y
+\begin_inset Formula $(q\frac{x}{q},q\frac{y}{x}\frac{x}{q})=(x,y)\in\text{ec}S$
+\end_inset
+
+, luego
+\begin_inset Formula $C\subseteq\text{ec}S$
+\end_inset
+
+.
+ Así,
+\begin_inset Formula $C=\text{ec}S$
+\end_inset
+
+, pero
+\begin_inset Formula $C$
+\end_inset
+
+ no es un poliedro.
+\end_layout
+
+\begin_layout Standard
+Sean
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{Q})$
+\end_inset
+
+,
+\begin_inset Formula $b\in\mathbb{Q}^{m}$
+\end_inset
+
+ y
+\begin_inset Formula $P:=\{x\in\mathbb{R}^{n}:Ax\leq b\}$
+\end_inset
+
+, si
+\begin_inset Formula $P_{I}:=\text{ec}(P\cap\mathbb{Z}^{n})\neq\emptyset$
+\end_inset
+
+, para
+\begin_inset Formula $c\in\mathbb{R}^{n}$
+\end_inset
+
+,
+\begin_inset Formula $\{c\cdot x\}_{x\in P_{I}}$
+\end_inset
+
+ está acotado superiormente si y sólo si lo está
+\begin_inset Formula $\{c\cdot x\}_{x\in P}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Matrices totalmente unimodulares
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+sremember{OL}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Sean
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{R})$
+\end_inset
+
+ de rango
+\begin_inset Formula $m$
+\end_inset
+
+ (por tanto
+\begin_inset Formula $m\leq n$
+\end_inset
+
+),
+\begin_inset Formula $b\in\mathbb{R}^{m}$
+\end_inset
+
+ y
+\begin_inset Formula $c\in\mathbb{R}^{n}$
+\end_inset
+
+.
+ [...] Llamamos
+\begin_inset Formula $A_{1},\dots,A_{n}$
+\end_inset
+
+ a las columnas de
+\begin_inset Formula $A$
+\end_inset
+
+ [...].
+\end_layout
+
+\begin_layout Standard
+Dado
+\begin_inset Formula $S\subseteq\{1,\dots,n\}$
+\end_inset
+
+, la submatriz
+\begin_inset Formula $B\in{\cal M}_{m}(\mathbb{R})$
+\end_inset
+
+ formada por las columnas de
+\begin_inset Formula $A$
+\end_inset
+
+ con índice en
+\begin_inset Formula $S$
+\end_inset
+
+ es
+\series bold
+básica
+\series default
+ si es de rango máximo.
+ Entonces, de las variables
+\begin_inset Formula $x_{1},\dots,x_{n}$
+\end_inset
+
+, [...]
+\begin_inset Formula $x_{k}$
+\end_inset
+
+ es una
+\series bold
+variable básica
+\series default
+ [...] si
+\begin_inset Formula $k\in S$
+\end_inset
+
+ [...] ([...]
+\begin_inset Formula $N$
+\end_inset
+
+ es la submatriz formada por las columnas de
+\begin_inset Formula $A$
+\end_inset
+
+ con índice no en
+\begin_inset Formula $S$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Standard
+[...] Si
+\begin_inset Formula $S=\{s_{1},\dots,s_{m}\}$
+\end_inset
+
+ y
+\begin_inset Formula $\{1,\dots,n\}\setminus S=\{t_{1},\dots,t_{n-m}\}$
+\end_inset
+
+ con
+\begin_inset Formula $s_{1}<\dots<s_{m}$
+\end_inset
+
+ y
+\begin_inset Formula $t_{1}<\dots<t_{n-m}$
+\end_inset
+
+, llamamos
+\begin_inset Formula $x_{B}:=(x_{s_{1}},\dots,x_{s_{m}})$
+\end_inset
+
+,
+\begin_inset Formula $x_{N}:=(x_{t_{1}},\dots,x_{t_{n-m}})$
+\end_inset
+
+,
+\begin_inset Formula $\mathbf{b}(x_{1},\dots,x_{m})=\sum_{k}e_{s_{k}}x_{k}$
+\end_inset
+
+ y
+\begin_inset Formula $\mathbf{n}(x_{1},\dots,x_{n-m}):=\sum_{k}e_{t_{k}}x_{k}$
+\end_inset
+
+,
+\begin_inset Formula $\mathbf{b}\in{\cal M}_{n\times m}(\mathbb{R})$
+\end_inset
+
+,
+\begin_inset Formula $\mathbf{n}\in{\cal M}_{n\times(n-m)}(\mathbb{R})$
+\end_inset
+
+.
+ [...]
+\end_layout
+
+\begin_layout Standard
+Llamamos
+\series bold
+solución básica
+\series default
+ a [...]
+\begin_inset Formula $x\in\{Ax=b\}$
+\end_inset
+
+ con
+\begin_inset Formula $x_{N}=0$
+\end_inset
+
+ y, por tanto, [...]
+\begin_inset Formula $x_{B}=B^{-1}b$
+\end_inset
+
+, y [...] es
+\series bold
+factible
+\series default
+ si
+\begin_inset Formula $x\geq0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dado
+\begin_inset Formula $F:=\{Ax=b,x\geq0\}$
+\end_inset
+
+,
+\begin_inset Formula $x\in F$
+\end_inset
+
+ es un punto extremo si y sólo si es una solución básica factible.
+ Además, si
+\begin_inset Formula $F\neq\emptyset$
+\end_inset
+
+, existe al menos un punto extremo.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+eremember
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{R})$
+\end_inset
+
+ es
+\series bold
+unimodular
+\series default
+ si tiene rango máximo, todos sus coeficientes son enteros y el determinante
+ de cualquier submatriz cuadrada de tamaño máximo es 1, 0 o
+\begin_inset Formula $-1$
+\end_inset
+
+, y es
+\series bold
+totalmente unimodular
+\series default
+ si el determinante de cualquier submatriz cuadrada es 1, 0 o
+\begin_inset Formula $-1$
+\end_inset
+
+, de modo que todas sus entradas son 1, 0
+\begin_inset Formula $-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un poliedro
+\begin_inset Formula $P\subseteq\mathbb{R}$
+\end_inset
+
+ es
+\series bold
+entero
+\series default
+ si todos sus puntos extremos están en
+\begin_inset Formula $\mathbb{Z}^{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Lema de Veinott-Dantzig:
+\series default
+ Si
+\begin_inset Formula $m<n$
+\end_inset
+
+,
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{Z})$
+\end_inset
+
+ de rango
+\begin_inset Formula $m$
+\end_inset
+
+ es unimodular si y sólo si para cada
+\begin_inset Formula $b\in\mathbb{Z}^{m}$
+\end_inset
+
+,
+\begin_inset Formula $Q:=\{x\in\mathbb{R}^{n}:Ax=b,x\geq0\}$
+\end_inset
+
+ es entero.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea
+\begin_inset Formula $x$
+\end_inset
+
+ un punto extremo de
+\begin_inset Formula $Q$
+\end_inset
+
+,
+\begin_inset Formula $x$
+\end_inset
+
+ es una solución básica factible y tiene forma
+\begin_inset Formula $x=:\mathbf{b}B^{-1}b$
+\end_inset
+
+ para cierta submatriz
+\begin_inset Formula $B\in{\cal M}_{m}(\mathbb{Z})$
+\end_inset
+
+ no singular de
+\begin_inset Formula $A$
+\end_inset
+
+.
+ La adjunta de
+\begin_inset Formula $B$
+\end_inset
+
+ también tiene coeficientes enteros, y como
+\begin_inset Formula $|B|\in\{\pm1\}$
+\end_inset
+
+,
+\begin_inset Formula $B^{-1}=\frac{1}{|B|}\text{adj}B\in{\cal M}_{m}(\mathbb{Z})$
+\end_inset
+
+ y
+\begin_inset Formula $x\in\mathbb{Z}^{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sea
+\begin_inset Formula $B\in{\cal M}_{m}(\mathbb{Z})$
+\end_inset
+
+ una submatriz no singular de
+\begin_inset Formula $A$
+\end_inset
+
+ y queremos ver que
+\begin_inset Formula $|B|\in\{\pm1\}$
+\end_inset
+
+.
+ Para
+\begin_inset Formula $i\in\{1,\dots,n\}$
+\end_inset
+
+, sean
+\begin_inset Formula $y\in\mathbb{Z}^{m}$
+\end_inset
+
+ tal que
+\begin_inset Formula $z:=y+(B^{-1})_{i}\geq0$
+\end_inset
+
+ y
+\begin_inset Formula $b:=Bz=By+e_{i}$
+\end_inset
+
+,
+\begin_inset Formula $b\in\mathbb{Z}^{m}$
+\end_inset
+
+ al tener
+\begin_inset Formula $B$
+\end_inset
+
+,
+\begin_inset Formula $y$
+\end_inset
+
+ y
+\begin_inset Formula $e_{i}$
+\end_inset
+
+ todos los coeficientes enteros, luego
+\begin_inset Formula $Q:=\{Ax=b,x\geq0\}$
+\end_inset
+
+ es entero y
+\begin_inset Formula $x:=\mathbf{b}z=\mathbf{b}B^{-1}b$
+\end_inset
+
+ es una solución básica factible de
+\begin_inset Formula $\{Ax=b,x\geq0\}$
+\end_inset
+
+ y por tanto un punto extremo de
+\begin_inset Formula $Q$
+\end_inset
+
+, de modo que
+\begin_inset Formula $x=\mathbf{b}(y+(B^{-1})_{i})\in\mathbb{Z}^{m}$
+\end_inset
+
+,
+\begin_inset Formula $(B^{-1})_{i}\in\mathbb{Z}^{m}$
+\end_inset
+
+ y, como
+\begin_inset Formula $i$
+\end_inset
+
+ es arbitrario,
+\begin_inset Formula $B^{-1}\in\mathbb{Z}^{m}$
+\end_inset
+
+.
+ Ahora bien, como
+\begin_inset Formula $B$
+\end_inset
+
+ y
+\begin_inset Formula $B^{-1}$
+\end_inset
+
+ son enteras y
+\begin_inset Formula $|B||B^{-1}|=1$
+\end_inset
+
+,
+\begin_inset Formula $|B|\in\{1,-1\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+begin{samepage}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Teorema de Hoffman-Kruskal:
+\series default
+
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{Z})$
+\end_inset
+
+ con
+\begin_inset Formula $m\leq n$
+\end_inset
+
+ es totalmente unimodular si y sólo si para
+\begin_inset Formula $b\in\mathbb{Z}^{m}$
+\end_inset
+
+, el poliedro
+\begin_inset Formula $\{x\in\mathbb{R}^{n}:Ax\leq b,x\geq0\}$
+\end_inset
+
+ es entero.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\implies]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Dada una submatriz
+\begin_inset Formula $B\in{\cal M}_{m}$
+\end_inset
+
+ de
+\begin_inset Formula $[A,I]$
+\end_inset
+
+ no singular, si
+\begin_inset Formula $B$
+\end_inset
+
+ es submatriz de
+\begin_inset Formula $A$
+\end_inset
+
+, claramente
+\begin_inset Formula $|B|\in\{\pm1\}$
+\end_inset
+
+, y en otro caso, desarrollando por columnas,
+\begin_inset Formula $|B|=|B'|$
+\end_inset
+
+ para alguna submatriz
+\begin_inset Formula $B'$
+\end_inset
+
+ de
+\begin_inset Formula $B$
+\end_inset
+
+ y de
+\begin_inset Formula $A$
+\end_inset
+
+, por lo que
+\begin_inset Formula $|B|\in\{\pm1\}$
+\end_inset
+
+.
+ Entonces
+\begin_inset Formula $[I,A]$
+\end_inset
+
+ es unimodular, con lo que
+\begin_inset Formula $Q:=\{[x,y]\in\mathbb{R}^{n+m}:Ax+Iy=b,[x,y]\geq0\}$
+\end_inset
+
+ es entero.
+ Sea ahora
+\begin_inset Formula $[x,y]\in Q$
+\end_inset
+
+ (
+\begin_inset Formula $x\in\mathbb{R}^{n}$
+\end_inset
+
+), claramente
+\begin_inset Formula $y=b-Ax$
+\end_inset
+
+, por lo que la proyección de
+\begin_inset Formula $Q$
+\end_inset
+
+ en
+\begin_inset Formula $\mathbb{R}^{n}\times0_{\mathbb{R}^{m}}$
+\end_inset
+
+ es
+\begin_inset Formula $P:=\{x\in\mathbb{R}^{n}:b=b,x\geq0,b-Ax\geq0\}=\{Ax\leq b,x\geq0\}$
+\end_inset
+
+.
+ Así, dado un punto extremo
+\begin_inset Formula $x\in P$
+\end_inset
+
+,
+\begin_inset Formula $[x,b-Ax]\in Q$
+\end_inset
+
+ es un punto extremo, pues si no lo fuera existirían
+\begin_inset Formula $U:=[u,b-Au],V:=[v,b-Av]\in Q$
+\end_inset
+
+ distintos y
+\begin_inset Formula $t\in(0,1)$
+\end_inset
+
+ con
+\begin_inset Formula $(1-t)U+tV=[x,b-Ax]$
+\end_inset
+
+ y
+\begin_inset Formula $(1-t)u+tv=x$
+\end_inset
+
+, y como
+\begin_inset Formula $u,v\in P$
+\end_inset
+
+,
+\begin_inset Formula $x$
+\end_inset
+
+ no sería punto extremo.
+ Entonces
+\begin_inset Formula $[x,b-Ax]\in\mathbb{Z}^{n+m}$
+\end_inset
+
+ y
+\begin_inset Formula $x\in\mathbb{Z}^{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Argument item:1
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\impliedby]$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+Sean
+\begin_inset Formula $b\in\mathbb{Z}^{m}$
+\end_inset
+
+,
+\begin_inset Formula $P:=\{x:Ax\leq b,x\geq0\}$
+\end_inset
+
+,
+\begin_inset Formula $Q:=\{[x,y]:Ax+y=b,[x,y]\geq0\}$
+\end_inset
+
+ y
+\begin_inset Formula $[x,y]\in Q$
+\end_inset
+
+, claramente
+\begin_inset Formula $y=b-Ax$
+\end_inset
+
+, y si
+\begin_inset Formula $[x,y]$
+\end_inset
+
+ es punto extremo de
+\begin_inset Formula $Q$
+\end_inset
+
+,
+\begin_inset Formula $x$
+\end_inset
+
+ lo es de
+\begin_inset Formula $P$
+\end_inset
+
+, pues si no lo fuera habrían
+\begin_inset Formula $u,v\in P$
+\end_inset
+
+ distintos y
+\begin_inset Formula $t\in(0,1)$
+\end_inset
+
+ con
+\begin_inset Formula $(1-t)u+tv=x$
+\end_inset
+
+, pero
+\begin_inset Formula $[u,b-Au],[v,b-Av]\in Q$
+\end_inset
+
+ y por tanto
+\begin_inset Formula $[x,y]$
+\end_inset
+
+ no sería punto extremo de
+\begin_inset Formula $Q$
+\end_inset
+
+.
+ Así, como
+\begin_inset Formula $P$
+\end_inset
+
+ es entero,
+\begin_inset Formula $Q$
+\end_inset
+
+ también, luego
+\begin_inset Formula $[A,I]$
+\end_inset
+
+ es unimodular.
+ Sea entonces
+\begin_inset Formula $B$
+\end_inset
+
+ una submatriz cuadrada de
+\begin_inset Formula $A$
+\end_inset
+
+, añadiendo a
+\begin_inset Formula $B$
+\end_inset
+
+ las filas de
+\begin_inset Formula $A$
+\end_inset
+
+ que no se han tomado para
+\begin_inset Formula $B$
+\end_inset
+
+ y las columnas de
+\begin_inset Formula $I$
+\end_inset
+
+ que valen 1 en esas filas, obtenemos una submatriz
+\begin_inset Formula $B'$
+\end_inset
+
+ de
+\begin_inset Formula $[I,A]$
+\end_inset
+
+ de tamaño
+\begin_inset Formula $m$
+\end_inset
+
+ y, desarrollando por columnas de
+\begin_inset Formula $I$
+\end_inset
+
+, tenemos que
+\begin_inset Formula $|B'|=|B|$
+\end_inset
+
+, pero por ser
+\begin_inset Formula $[I,A]$
+\end_inset
+
+ unimodular,
+\begin_inset Formula $|B|=|B'|\in\{1,0,-1\}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+end{samepage}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Caracterizaciones de matrices unimodulares
+\end_layout
+
+\begin_layout Standard
+Como
+\series bold
+teorema
+\series default
+, una matriz
+\begin_inset Formula $A$
+\end_inset
+
+ es totalmente unimodular si y sólo si lo es
+\begin_inset Formula $A^{t}$
+\end_inset
+
+, si y sólo si lo es
+\begin_inset Formula $[A,I]$
+\end_inset
+
+, si y solo si lo es el resultado de añadir o quitar de
+\begin_inset Formula $A$
+\end_inset
+
+ una fila o columna igual a
+\begin_inset Formula $e_{i}$
+\end_inset
+
+ para algún
+\begin_inset Formula $i$
+\end_inset
+
+, si y sólo si lo es el resultado de multiplicar una fila o columna de
+\begin_inset Formula $A$
+\end_inset
+
+ por
+\begin_inset Formula $-1$
+\end_inset
+
+, si y sólo si lo es el resultado de intercambiar dos filas o columnas de
+
+\begin_inset Formula $A$
+\end_inset
+
+, si y sólo si lo es el resultado de duplicar una columna o fila de
+\begin_inset Formula $A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{R})$
+\end_inset
+
+ es
+\series bold
+euleriana
+\series default
+ si en cada fila o columna la suma de los elementos es par.
+ Como
+\series bold
+teorema
+\series default
+,
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\{1,0,-1\})$
+\end_inset
+
+ es totalmente unimodular si y sólo si la suma de los elementos de cada
+ submatriz cuadrada euleriana de
+\begin_inset Formula $A$
+\end_inset
+
+ es múltiplo de 4, si y sólo si para cada
+\begin_inset Formula $F\subseteq\{1,\dots,m\}$
+\end_inset
+
+ existe
+\begin_inset Formula $F_{1}\subseteq F$
+\end_inset
+
+ tal que, si
+\begin_inset Formula $F_{2}:=F\setminus F_{1}$
+\end_inset
+
+, para
+\begin_inset Formula $j\in\{1,\dots,n\}$
+\end_inset
+
+ es
+\begin_inset Formula
+\[
+\left|\sum_{i\in F_{1}}a_{ij}-\sum_{i\in F_{2}}a_{ij}\right|\leq1.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Como
+\series bold
+teorema
+\series default
+, si
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\{1,0,-1\})$
+\end_inset
+
+, ninguna columna de
+\begin_inset Formula $A$
+\end_inset
+
+ tiene más de dos elementos no nulos y existe una partición
+\begin_inset Formula $\{F_{1},F_{2}\}$
+\end_inset
+
+ de
+\begin_inset Formula $\{1,\dots,m\}$
+\end_inset
+
+ con elementos no necesariamente vacíos tal que, para
+\begin_inset Formula $i\in\{1,\dots,n\}$
+\end_inset
+
+ y
+\begin_inset Formula $j,k\in\{1,\dots,m\}$
+\end_inset
+
+,
+\begin_inset Formula $j$
+\end_inset
+
+ y
+\begin_inset Formula $k$
+\end_inset
+
+ están en el mismo conjunto de la partición si y sólo si
+\begin_inset Formula $a_{ji}$
+\end_inset
+
+ y
+\begin_inset Formula $a_{ki}$
+\end_inset
+
+ tienen el mismo signo, entonces
+\begin_inset Formula $A$
+\end_inset
+
+ es totalmente unimodular.
+ En particular
+\begin_inset Formula $A$
+\end_inset
+
+ es totalmente unimodular si en cada columna tiene a lo sumo un coeficiente
+
+\begin_inset Formula $+1$
+\end_inset
+
+ y otro
+\begin_inset Formula $-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Una
+\series bold
+matriz de intervalo
+\series default
+ es una matriz
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\{0,1\})$
+\end_inset
+
+ tal que para
+\begin_inset Formula $j\in\{1,\dots,n\}$
+\end_inset
+
+ e
+\begin_inset Formula $i,k\in\{1,\dots,m\}$
+\end_inset
+
+ con
+\begin_inset Formula $i<k$
+\end_inset
+
+, si
+\begin_inset Formula $a_{ij}=a_{kj}=1$
+\end_inset
+
+, entonces
+\begin_inset Formula $a_{hj}=1$
+\end_inset
+
+ para todo
+\begin_inset Formula $i\leq h\leq k$
+\end_inset
+
+.
+ Toda matriz de intervalo es totalmente unimodular.
+\end_layout
+
+\begin_layout Section
+Modelos clásicos
+\end_layout
+
+\begin_layout Standard
+Un
+\series bold
+problema de asignación
+\series default
+ consiste en asignar
+\begin_inset Formula $n$
+\end_inset
+
+ tareas a
+\begin_inset Formula $n$
+\end_inset
+
+ operarios, una tarea por operario, minimizando el tiempo total dada una
+ matriz
+\begin_inset Formula $T\in{\cal M}_{n}(\mathbb{R}^{\geq0})$
+\end_inset
+
+ en la que
+\begin_inset Formula $t_{ij}$
+\end_inset
+
+ es el tiempo que tarda el operario
+\begin_inset Formula $i$
+\end_inset
+
+ en realizar la tarea
+\begin_inset Formula $j$
+\end_inset
+
+.
+ Si llamamos
+\begin_inset Formula
+\[
+x_{ij}:=\begin{cases}
+1, & \text{el operario }i\text{ es asignado a la tarea }j;\\
+0, & \text{en otro caso}
+\end{cases}
+\]
+
+\end_inset
+
+para
+\begin_inset Formula $i,j\in\{1,\dots,n\}$
+\end_inset
+
+, podemos formular el problema como
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & {\textstyle \sum_{ij}}t_{ij}x_{ij}\\
+ & & {\textstyle \sum_{j}}x_{ij} & \leq1, & & \forall i\\
+ & & {\textstyle \sum_{i}}x_{ij} & \geq1, & & \forall j\\
+ & & x_{ij} & \in\{0,1\}, & & \forall i,j
+\end{alignat*}
+
+\end_inset
+
+Si las tareas se pueden hacer a la vez, lo que queremos minimizar es
+\begin_inset Formula $\max_{i}\sum_{j}t_{ij}x_{ij}$
+\end_inset
+
+, para lo que cambiamos la formulación a
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & z\\
+ & & {\textstyle \sum_{j}}x_{ij} & \leq1, & & \forall i\\
+ & & {\textstyle \sum_{i}}x_{ij} & \geq1, & & \forall j\\
+ & & z-{\textstyle \sum_{j}}t_{ij}x_{ij} & \geq0, & & \forall i\\
+ & & x_{ij} & \in\{0,1\}, & & \forall i,j
+\end{alignat*}
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Sean ahora
+\begin_inset Formula $R:=(V:=\{1,\dots,n\},E,\omega)$
+\end_inset
+
+ una red y
+\begin_inset Formula $s,t\in V$
+\end_inset
+
+ distintos, y queremos encontrar un paseo de coste mínimo de
+\begin_inset Formula $s$
+\end_inset
+
+ a
+\begin_inset Formula $t$
+\end_inset
+
+, lo que definiendo las variables
+\begin_inset Formula
+\[
+x_{ij}:=\begin{cases}
+1, & j\text{ aparece a continuación de }i\text{ en el camino};\\
+0, & \text{en otro caso},
+\end{cases}
+\]
+
+\end_inset
+
+para
+\begin_inset Formula $(i,j)\in V\times V$
+\end_inset
+
+ con
+\begin_inset Formula $\{i,j\}\in E$
+\end_inset
+
+, podemos formular como
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & {\textstyle \sum_{ij}}d_{ij}x_{ij}\\
+ & & {\textstyle \sum_{(s,j)\in E}}x_{sj} & =1,\\
+ & & {\textstyle \sum_{(j,t)\in E}}x_{jt} & =1, & & \forall j\\
+ & & {\textstyle \sum_{(i,v)\in E}}x_{iv}-{\textstyle \sum_{(v,j)\in E}x_{vj}} & =0, & & \forall v\neq s,t\\
+ & & x_{ij} & \in\{0,1\}, & & \forall i,j
+\end{alignat*}
+
+\end_inset
+
+Entonces el camino empieza en
+\begin_inset Formula $s$
+\end_inset
+
+, sigue en el único
+\begin_inset Formula $i$
+\end_inset
+
+ con
+\begin_inset Formula $x_{si}=1$
+\end_inset
+
+, luego en el único
+\begin_inset Formula $j$
+\end_inset
+
+ con
+\begin_inset Formula $x_{ij}=1$
+\end_inset
+
+, y así hasta llegar a
+\begin_inset Formula $t$
+\end_inset
+
+.
+ La unicidad sabemos que se da si
+\begin_inset Formula $\omega(e)\geq0$
+\end_inset
+
+ para todo
+\begin_inset Formula $e$
+\end_inset
+
+; de lo contrario tenemos que añadir
+\begin_inset Formula $\sum_{(i,v)\in E}x_{iv}\leq1,\forall v\neq s,t$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Para obtener el árbol generador minimal de
+\begin_inset Formula $R$
+\end_inset
+
+,
+\begin_inset Formula $T=(V,E_{T})$
+\end_inset
+
+, llamamos
+\begin_inset Formula $x_{ij}:=\chi_{E_{T}}(i,j)$
+\end_inset
+
+ para
+\begin_inset Formula $(i,j)\in E$
+\end_inset
+
+, y formulamos el problema como
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & {\textstyle \sum_{ij}}c_{ij}x_{ij}\\
+ & & {\textstyle \sum_{(i,j)\in E}x_{ij}} & =|V|-1\\
+ & & {\textstyle \sum_{(i,j)\in E_{S}}x_{ij}} & \leq|S|-1, & & \forall S\subsetneq V:|S|\geq3\\
+ & & x_{ij} & \in\{0,1\}, & & \forall i,j
+\end{alignat*}
+
+\end_inset
+
+En efecto, la primera condición nos asegura que
+\begin_inset Formula $T$
+\end_inset
+
+ tenga
+\begin_inset Formula $|V|-1$
+\end_inset
+
+ ejes y la segunda que no tenga ciclos salvo, quizá, uno con todos los vértices
+ de
+\begin_inset Formula $V$
+\end_inset
+
+, lo que la primera condición ya descarta, y esto caracteriza un árbol.
+ La relajación lineal de este problema da una solución entera.
+\end_layout
+
+\begin_layout Standard
+Otra posible formulación, con las mismas variables resulta de cambiar la
+ segunda condición por
+\begin_inset Formula $\sum_{(i,j)\in[S,V\setminus S]}x_{ij}\geq1,\forall S\subsetneq V:S\neq\emptyset$
+\end_inset
+
+, pues esto nos da la conexión y, junto con la primera condición, caracteriza
+ al árbol.
+ La relajación lineal no tiene por qué dar una solución entera.
+\end_layout
+
+\begin_layout Standard
+Para el problema del viajante de comercio sobre una red completa
+\begin_inset Formula $R:=(V:=\{0,\dots,n-1\},E:=\{\{i,j\}\}_{i,j\in V,i\neq j},d)$
+\end_inset
+
+, existen varias formulaciones:
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Formulación de Dantzig-Fulkerson-Johnson:
+\series default
+ Sea
+\begin_inset Formula
+\[
+x_{ij}:=\left\{ \begin{aligned}1, & \text{el ciclo tiene }i\text{ y a continuación }j;\\
+0, & \text{en otro caso}
+\end{aligned}
+\right.
+\]
+
+\end_inset
+
+para
+\begin_inset Formula $(i,j)\in V\times V$
+\end_inset
+
+ con
+\begin_inset Formula $\{i,j\}\in E$
+\end_inset
+
+, el problema es
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & {\textstyle \sum}_{ij}d_{ij}x_{ij}\\
+ & & {\textstyle \sum_{(i,j)\in E}}x_{ij} & =1, & & \forall i\\
+ & & {\textstyle \sum}_{(k,i)\in E}x_{ki} & =1, & & \forall i\\
+ & & x_{ij} & \in\{0,1\}, & & \forall i,j
+\end{alignat*}
+
+\end_inset
+
+Para obtener el camino, tomamos un nodo inicial
+\begin_inset Formula $i_{0}$
+\end_inset
+
+, luego el único
+\begin_inset Formula $i_{1}$
+\end_inset
+
+ con
+\begin_inset Formula $x_{i_{0}i_{1}}=1$
+\end_inset
+
+, y luego repetimos hasta volver a
+\begin_inset Formula $i_{0}$
+\end_inset
+
+.
+ El ciclo resultante puede no ser hamiltoniano porque esta formulación permite
+ subciclos estrictos, ciclos que no contienen a todos los nodos.
+ Para evitar esto, podemos añadir la restricción
+\begin_inset Formula $\sum_{e\in E_{s}}x_{e}\leq|S|-1,\forall S\subsetneq V:|S|\geq2$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Si ahora las variables son
+\begin_inset Formula
+\[
+x_{ij}:=\begin{cases}
+1, & (i,j)\text{ está en el ciclo};\\
+0, & \text{en otro caso}
+\end{cases}
+\]
+
+\end_inset
+
+para
+\begin_inset Formula $(i,j)\in E$
+\end_inset
+
+, otra formulación es
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & {\textstyle \sum}_{e}d_{e}x_{e}\\
+ & & {\textstyle \sum_{e\in N(v)}}x_{e} & =2, & & \forall v\\
+ & & {\textstyle \sum}_{e\in E_{S}}x_{e} & \leq|S|-1, & & \forall S\subsetneq V:|S|\geq3\\
+ & & x_{ij} & \in\{0,1\}, & & \forall i,j
+\end{alignat*}
+
+\end_inset
+
+El ciclo se obtendría tomando un nodo inicial
+\begin_inset Formula $i_{0}$
+\end_inset
+
+, luego un
+\begin_inset Formula $i_{1}$
+\end_inset
+
+ con
+\begin_inset Formula $x_{i_{0}i_{1}}=1$
+\end_inset
+
+, luego un
+\begin_inset Formula $i_{2}\neq i_{0}$
+\end_inset
+
+ con
+\begin_inset Formula $x_{i_{1}i_{2}}=1$
+\end_inset
+
+, etc.
+ En estas formulaciones el número de restricciones crece exponencialmente
+ con el número de vértices.
+\end_layout
+
+\begin_layout Enumerate
+
+\series bold
+Formulación de Miller-Tucker-Zemlin:
+\series default
+ Las variables se definen como en la primera formulación con variables adicional
+es
+\begin_inset Formula $u_{1},\dots,u_{n}$
+\end_inset
+
+.
+ Llamando
+\begin_inset Formula $n:=|V|$
+\end_inset
+
+:
+\begin_inset Formula
+\begin{alignat*}{3}
+ & \min & {\textstyle \sum}_{ij}d_{ij}x_{ij}\\
+ & & {\textstyle \sum_{(i,j)\in E}}x_{ij} & =1 & & \forall i\\
+ & & {\textstyle \sum_{(k,i)\in E}}x_{ki} & =1 & & \forall i\\
+ & & u_{i}-u_{j}+nx_{ij} & \leq n-1 & & \forall i,j\in\{1,\dots,n-1\}:(i,j)\in E\\
+ & & x_{ij} & \in\{0,1\} & & \forall i,j\\
+ & & u_{i} & \in\mathbb{R}^{>0} & & \forall i
+\end{alignat*}
+
+\end_inset
+
+Esto evita los ciclos que no contengan a 0, por lo que todos los nodos están
+ en el mismo ciclo.
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Sea
+\begin_inset Formula $x$
+\end_inset
+
+ una solución factible, si
+\begin_inset Formula $x$
+\end_inset
+
+ tuviera un ciclo que no contuviera al 0, como
+\begin_inset Formula $1\,2\cdots k1$
+\end_inset
+
+, entonces
+\begin_inset Formula $u_{i}-u_{i+1}+n\leq n-1$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,k-1\}$
+\end_inset
+
+ y
+\begin_inset Formula $u_{k}-u_{1}+n\leq n-1$
+\end_inset
+
+, y sumando todo queda
+\begin_inset Formula $kn\leq kn-1\#$
+\end_inset
+
+.
+ Recíprocamente, sea
+\begin_inset Formula $x$
+\end_inset
+
+ la representación por variables de un ciclo hamiltoniano, llamamos
+\begin_inset Formula $u_{i}:=t$
+\end_inset
+
+ si
+\begin_inset Formula $i$
+\end_inset
+
+ es el
+\begin_inset Formula $t$
+\end_inset
+
+-ésimo vértice visitado en el ciclo después del 0.
+ Entonces, para
+\begin_inset Formula $(i,j)\in E$
+\end_inset
+
+ con
+\begin_inset Formula $i,j\neq0$
+\end_inset
+
+, si
+\begin_inset Formula $x_{ij}=0$
+\end_inset
+
+,
+\begin_inset Formula $u_{i}-u_{j}<u_{i}\leq n-1$
+\end_inset
+
+, y si
+\begin_inset Formula $x_{ij}=1$
+\end_inset
+
+,
+\begin_inset Formula $u_{j}=u_{i}+1$
+\end_inset
+
+,
+\begin_inset Formula $u_{i}-u_{j}=-1$
+\end_inset
+
+ y
+\begin_inset Formula $u_{i}-u_{j}+n=n-1$
+\end_inset
+
+, y en ambos casos la tercera condición se cumple.
+\end_layout
+
+\end_deeper
+\begin_layout Section
+Situaciones generales
+\end_layout
+
+\begin_layout Standard
+Si tenemos
+\begin_inset Formula $m$
+\end_inset
+
+ restricciones
+\begin_inset Formula $g_{i}(x_{1},\dots,x_{n})\leq0$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,m\}$
+\end_inset
+
+ de las que queremos que se verifiquen al menos
+\begin_inset Formula $k<m$
+\end_inset
+
+, tomamos
+\begin_inset Formula $M$
+\end_inset
+
+ lo suficientemente grande, añadimos las variables
+\begin_inset Formula $y_{1},\dots,y_{m}\in\{0,1\}$
+\end_inset
+
+ y añadimos las restricciones
+\begin_inset Formula $g_{i}(x_{1},\dots,x_{n})\leq M(1-y_{i})$
+\end_inset
+
+ para
+\begin_inset Formula $i\in\{1,\dots,m\}$
+\end_inset
+
+ y
+\begin_inset Formula $\sum_{i=1}^{m}y_{i}\geq k$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dadas dos variables
+\begin_inset Formula $x_{1},x_{2}\in\mathbb{Z}$
+\end_inset
+
+, para definir una variable
+\begin_inset Formula $y:=[x_{1}>x_{2}]$
+\end_inset
+
+ (
+\begin_inset Formula $y=1$
+\end_inset
+
+ si
+\begin_inset Formula $x_{1}>x_{2}$
+\end_inset
+
+ e
+\begin_inset Formula $y=0$
+\end_inset
+
+ en otro caso), tomamos
+\begin_inset Formula $M$
+\end_inset
+
+ lo suficientemente grande y añadimos
+\begin_inset Formula $x_{1}-x_{2}-My\leq0$
+\end_inset
+
+,
+\begin_inset Formula $x_{2}-x_{1}+(1+M)y\leq M$
+\end_inset
+
+ e
+\begin_inset Formula $y\in\{0,1\}$
+\end_inset
+
+.
+ De esta forma, si
+\begin_inset Formula $x_{1}>x_{2}$
+\end_inset
+
+, con
+\begin_inset Formula $y=1$
+\end_inset
+
+ tenemos
+\begin_inset Formula $x_{1}-x_{2}-M\leq0$
+\end_inset
+
+ y
+\begin_inset Formula $x_{2}-x_{1}+(1+M)\leq-1+1+M=M$
+\end_inset
+
+ pero con
+\begin_inset Formula $y=0$
+\end_inset
+
+ tenemos
+\begin_inset Formula $x_{1}-x_{2}>0\#$
+\end_inset
+
+, y si
+\begin_inset Formula $x_{1}\le x_{2}$
+\end_inset
+
+, con
+\begin_inset Formula $y=0$
+\end_inset
+
+ tenemos
+\begin_inset Formula $x_{1}-x_{2}\leq0$
+\end_inset
+
+ y
+\begin_inset Formula $x_{2}-x_{1}\leq M$
+\end_inset
+
+ pero con
+\begin_inset Formula $y=1$
+\end_inset
+
+ tenemos
+\begin_inset Formula $x_{2}-x_{1}+1+M\geq1+M>M\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dadas dos variables reales
+\begin_inset Formula $x_{1}$
+\end_inset
+
+ y
+\begin_inset Formula $x_{2}$
+\end_inset
+
+, para definir
+\begin_inset Formula $z\geq\min\{x_{1},x_{2}\}$
+\end_inset
+
+, hacemos que se cumpla una de
+\begin_inset Formula $z\geq x_{1}$
+\end_inset
+
+ y
+\begin_inset Formula $z\geq x_{2}$
+\end_inset
+
+, y para definir
+\begin_inset Formula $z\leq\max\{x_{1},x_{2}\}$
+\end_inset
+
+, hacemos que se cumpla una de
+\begin_inset Formula $z\leq x_{1}$
+\end_inset
+
+ y
+\begin_inset Formula $z\leq x_{2}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Si
+\begin_inset Formula $x_{1},x_{2}\in\{0,1\}$
+\end_inset
+
+, para definir
+\begin_inset Formula $y:=\min\{x_{1},x_{2}\}$
+\end_inset
+
+ añadimos
+\begin_inset Formula $y\leq x_{1}$
+\end_inset
+
+,
+\begin_inset Formula $y\leq x_{2}$
+\end_inset
+
+,
+\begin_inset Formula $y\geq x_{1}+x_{2}-1$
+\end_inset
+
+ e
+\begin_inset Formula $y\in\{0,1\}$
+\end_inset
+
+, y para definir
+\begin_inset Formula $y:=\max\{x_{1},x_{2}\}$
+\end_inset
+
+ añadimos
+\begin_inset Formula $y\geq x_{1}$
+\end_inset
+
+,
+\begin_inset Formula $y\geq x_{2}$
+\end_inset
+
+,
+\begin_inset Formula $y\leq x_{1}+x_{2}$
+\end_inset
+
+ e
+\begin_inset Formula $y\in\{0,1\}$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document
diff --git a/graf/n7.lyx b/graf/n7.lyx
new file mode 100644
index 0000000..af1f41a
--- /dev/null
+++ b/graf/n7.lyx
@@ -0,0 +1,1822 @@
+#LyX 2.3 created this file. For more info see http://www.lyx.org/
+\lyxformat 544
+\begin_document
+\begin_header
+\save_transient_properties true
+\origin unavailable
+\textclass book
+\begin_preamble
+\usepackage{amssymb}
+\usepackage{amstext}
+\input{../defs}
+\end_preamble
+\use_default_options true
+\begin_modules
+algorithm2e
+\end_modules
+\maintain_unincluded_children false
+\language spanish
+\language_package default
+\inputencoding auto
+\fontencoding global
+\font_roman "default" "default"
+\font_sans "default" "default"
+\font_typewriter "default" "default"
+\font_math "auto" "auto"
+\font_default_family default
+\use_non_tex_fonts false
+\font_sc false
+\font_osf false
+\font_sf_scale 100 100
+\font_tt_scale 100 100
+\use_microtype false
+\use_dash_ligatures true
+\graphics default
+\default_output_format default
+\output_sync 0
+\bibtex_command default
+\index_command default
+\paperfontsize default
+\spacing single
+\use_hyperref false
+\papersize default
+\use_geometry false
+\use_package amsmath 1
+\use_package amssymb 1
+\use_package cancel 1
+\use_package esint 1
+\use_package mathdots 1
+\use_package mathtools 1
+\use_package mhchem 1
+\use_package stackrel 1
+\use_package stmaryrd 1
+\use_package undertilde 1
+\cite_engine basic
+\cite_engine_type default
+\biblio_style plain
+\use_bibtopic false
+\use_indices false
+\paperorientation portrait
+\suppress_date false
+\justification true
+\use_refstyle 1
+\use_minted 0
+\index Index
+\shortcut idx
+\color #008000
+\end_index
+\secnumdepth 3
+\tocdepth 3
+\paragraph_separation indent
+\paragraph_indentation default
+\is_math_indent 0
+\math_numbering_side default
+\quotes_style french
+\dynamic_quotes 0
+\papercolumns 1
+\papersides 1
+\paperpagestyle default
+\tracking_changes false
+\output_changes false
+\html_math_output 0
+\html_css_as_file 0
+\html_be_strict false
+\end_header
+
+\begin_body
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Problema $
+\backslash
+min
+\backslash
+{c
+\backslash
+cdot x
+\backslash
+}_{Ax=b,x
+\backslash
+geq0}$ dado por $m,n
+\backslash
+in{
+\backslash
+mathbb N}^*$ con $m<n$, $A
+\backslash
+in{
+\backslash
+cal M}_{m
+\backslash
+times n}(
+\backslash
+mathbb R)$, $b
+\backslash
+in{
+\backslash
+mathbb R}^m$ con $b
+\backslash
+geq0$ y $c
+\backslash
+in{
+\backslash
+mathbb R}^n$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Dirección de ilimitación $d
+\backslash
+in{
+\backslash
+mathbb R}^n$, conjunto $C
+\backslash
+subseteq{
+\backslash
+mathbb R}^n$ de puntos óptimos o $
+\backslash
+emptyset$ si el problema es infactible.
+ Puede no terminar.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetKw{Salir}{salir}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetKwBlock{Repetir}{repetir}{siempre}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetKwProg{Funcion}{función}{}{fin}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetKwFunction{params}{params}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetKwFunction{interpretar}{interpretar}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Funcion{
+\backslash
+params{$
+\backslash
+sigma$}}{
+\end_layout
+
+\begin_layout Plain Layout
+
+ $T
+\backslash
+gets[A_{
+\backslash
+sigma(1)},
+\backslash
+dots,A_{
+\backslash
+sigma(m)}]^{-1}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Devolver $(T,
+\backslash
+mathbf{b}Tb)$%
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+tcp*{{
+\backslash
+rm Para la notación,
+\end_layout
+
+\begin_layout Plain Layout
+
+ $B=[A_{
+\backslash
+sigma(1)},
+\backslash
+dots,A_{
+\backslash
+sigma(m)}]$.}}
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Funcion{
+\backslash
+interpretar{$
+\backslash
+sigma,Y,x,q$}}{
+\end_layout
+
+\begin_layout Plain Layout
+
+ $S
+\backslash
+gets
+\backslash
+{x
+\backslash
+}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ $D
+\backslash
+gets
+\backslash
+{0
+\backslash
+}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Para{$k:N$ con $q_k=0$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{$Y_k
+\backslash
+leq0$}{$D
+\backslash
+gets D
+\backslash
+cup
+\backslash
+{e_k-
+\backslash
+mathbf{b}Y_k
+\backslash
+}$}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lEnOtroCaso{$S
+\backslash
+gets S
+\backslash
+cup
+\backslash
+{
+\end_layout
+
+\begin_layout Plain Layout
+
+ x +
+\backslash
+min_{r
+\backslash
+in
+\backslash
+{1,
+\backslash
+dots,m
+\backslash
+},y_{rk}>0}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+frac{x_{
+\backslash
+sigma(r)}}{y_{kr}}
+\end_layout
+
+\begin_layout Plain Layout
+
+ (e_k-
+\backslash
+mathbf{b}Y_k)
+\backslash
+}$}
+\end_layout
+
+\begin_layout Plain Layout
+
+ }
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Devolver $
+\backslash
+{x +
+\backslash
+lambda u
+\backslash
+}_{x
+\backslash
+in
+\backslash
+text{cc}S, u
+\backslash
+in D,
+\backslash
+lambda
+\backslash
+geq0}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+subseteq {
+\backslash
+mathbb R}^n$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+ParaCada{subsecuencia $
+\backslash
+sigma:
+\backslash
+{1,
+\backslash
+dots,m
+\backslash
+}
+\backslash
+to
+\backslash
+{1,
+\backslash
+dots,n
+\backslash
+}$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SSi{$A_{
+\backslash
+sigma(1)},
+\backslash
+dots,A_{
+\backslash
+sigma(m)}$ son linealmente independientes}{
+\end_layout
+
+\begin_layout Plain Layout
+
+ $(T,x)
+\backslash
+gets
+\backslash
+text{
+\backslash
+params{
+\backslash
+ensuremath{
+\backslash
+sigma}}}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{$x
+\backslash
+geq0$}{
+\backslash
+Salir}
+\end_layout
+
+\begin_layout Plain Layout
+
+ }
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{no se ha obtenido $x
+\backslash
+geq0$}{
+\backslash
+Devolver $
+\backslash
+emptyset$}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Repetir{
+\end_layout
+
+\begin_layout Plain Layout
+
+ $Y
+\backslash
+gets TA$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ $q
+\backslash
+gets c_B^tY-c$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ Tomar $k:N$ con $q_k$ máximo
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+uSSi{$q_k
+\backslash
+leq0$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Devolver
+\backslash
+interpretar{$
+\backslash
+sigma,Y,x,q$}
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ }
+\backslash
+uEnOtroCasoSi{$Y_k
+\backslash
+leq0$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Devolver $e_k-
+\backslash
+mathbf{b}Y_k
+\backslash
+in {
+\backslash
+mathbb R}^n$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ }
+\backslash
+EnOtroCaso{
+\end_layout
+
+\begin_layout Plain Layout
+
+ Tomar $r
+\backslash
+in
+\backslash
+{1,
+\backslash
+dots,m
+\backslash
+}$ con $y_{rk}>0$ y
+\end_layout
+
+\begin_layout Plain Layout
+
+ $
+\backslash
+frac{x_{
+\backslash
+sigma(r)}}{y_{rk}}$ mínimo
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ {
+\backslash
+bf Pivotar:} $
+\backslash
+sigma(r)
+\backslash
+gets k$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ $(T,x)
+\backslash
+gets
+\backslash
+text{
+\backslash
+params{
+\backslash
+ensuremath{
+\backslash
+sigma}}}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ }
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:simplex"
+
+\end_inset
+
+Algoritmo del símplex para minimizar.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+sremember{OL}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+
+\series bold
+Algoritmo del símplex
+\series default
+ [...] para minimizar es el Algoritmo
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:simplex"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+ Si quisiéramos maximizar, [...] minimizaríamos
+\begin_inset Formula $q_{k}$
+\end_inset
+
+ [...] y [...] haríamos las comparaciones opuestas [con los
+\begin_inset Formula $q_{k}$
+\end_inset
+
+].
+ [...] Se suele hacer con una
+\series bold
+tabla del símplex
+\series default
+ como la siguiente:
+\begin_inset Formula
+\[
+\begin{array}{c|c|ccc|c}
+| & | & & & & |\\
+c_{B} & \sigma & & Y & & x_{B}\\
+| & | & & & & |\\
+\hline & & - & q & - & z
+\end{array}
+\]
+
+\end_inset
+
+En esta,
+\begin_inset Formula $z$
+\end_inset
+
+ es el coste total.
+ [...] Para pasar de la tabla del símplex de una iteración a la de la [...] siguiente,
+ basta conseguir una matriz identidad en las columnas correspondientes a
+ la base haciendo operaciones por filas en la submatriz
+\begin_inset Formula $\left(\begin{array}{c|c}
+Y & x_{B}\end{array}\right)$
+\end_inset
+
+, asegurándose de que
+\begin_inset Formula $x\geq0$
+\end_inset
+
+, y calcular
+\begin_inset Formula $q$
+\end_inset
+
+ y
+\begin_inset Formula $z$
+\end_inset
+
+.
+ [...] Si
+\begin_inset Formula $\sigma(i)=k$
+\end_inset
+
+, en vez de
+\begin_inset Formula $k$
+\end_inset
+
+ escribimos
+\begin_inset Formula $x_{k}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Un punto extremo
+\begin_inset Formula $x$
+\end_inset
+
+ asociado a una base
+\begin_inset Formula $B$
+\end_inset
+
+ es
+\series bold
+degenerado
+\series default
+ si existe
+\begin_inset Formula $i:B$
+\end_inset
+
+ con
+\begin_inset Formula $x_{i}=0$
+\end_inset
+
+; entonces [...] se pivotará este elemento, se tendrá
+\begin_inset Formula $\frac{x_{i}}{y_{\sigma^{-1}(i)k}}=0$
+\end_inset
+
+ y
+\begin_inset Formula $x$
+\end_inset
+
+ valdrá lo mismo en la siguiente iteración.
+ También se puede dar
+\series bold
+ciclaje
+\series default
+, consistente en ir cambiando de base de forma cíclica.
+ [...] Se puede evitar usando la
+\series bold
+regla de Bland:
+\series default
+ [...] [Si
+\begin_inset Formula $k$
+\end_inset
+
+ obtenido cumple
+\begin_inset Formula $q_{k}>0$
+\end_inset
+
+,] se establece
+\begin_inset Formula $k$
+\end_inset
+
+ al menor índice con
+\begin_inset Formula $q_{k}>0$
+\end_inset
+
+, y si hay varios
+\begin_inset Formula $r$
+\end_inset
+
+ que minimizan
+\begin_inset Formula $\frac{x_{\sigma(r)}}{y_{rk}}$
+\end_inset
+
+, se elige el de menor
+\begin_inset Formula $\sigma(r)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+[...] Sean
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{R})$
+\end_inset
+
+ de rango
+\begin_inset Formula $m$
+\end_inset
+
+,
+\begin_inset Formula $b\in\mathbb{R}^{m}$
+\end_inset
+
+,
+\begin_inset Formula $c\in\mathbb{R}^{n}$
+\end_inset
+
+,
+\begin_inset Formula $F:=\{x:Ax=b,x\geq0\}$
+\end_inset
+
+ y
+\begin_inset Formula $P:=\{c\cdot x\}_{x\in F}$
+\end_inset
+
+.
+ Para encontrar una base inicial para el símplex, por cada
+\begin_inset Formula $k\in\{1,\dots,m\}$
+\end_inset
+
+ tal que
+\begin_inset Formula $e_{k}$
+\end_inset
+
+ no es una columna de
+\begin_inset Formula $A$
+\end_inset
+
+, añadimos una columna al final de
+\begin_inset Formula $A$
+\end_inset
+
+ con valor
+\begin_inset Formula $e_{k}$
+\end_inset
+
+.
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+eremember
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+sremember{OL}
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Si [...]
+\begin_inset Formula $T\in{\cal M}_{m\times p}(\mathbb{R})$
+\end_inset
+
+ es la matriz formada por las columnas añadidas, escribimos
+\begin_inset Formula $F^{*}:=\{[x,x^{*}]\in\mathbb{R}^{n+p}:Ax+Tx^{*}=b,[x,x^{*}]\geq0\}$
+\end_inset
+
+ y vemos que
+\begin_inset Formula $x\in F\iff[x,0_{\mathbb{R}^{p}}]\in F^{*}$
+\end_inset
+
+.
+ Los elementos de
+\begin_inset Formula $x^{*}$
+\end_inset
+
+ son las
+\series bold
+variables artificiales
+\series default
+, y
+\begin_inset Formula $x^{*}$
+\end_inset
+
+ es el
+\series bold
+vector de variables artificiales
+\series default
+.
+\end_layout
+
+\begin_layout Standard
+[...] [
+\series bold
+Método de las dos fases:
+\series default
+] La primera fase consiste en hallar
+\begin_inset Formula $\min\{\sum_{i}x_{i}^{*}:Ax+Tx^{*}=b,[x,x^{*}]\geq0\}$
+\end_inset
+
+.
+ Si el resultado es distinto de 0, [...] el problema no es factible.
+ Para la segunda fase:
+\end_layout
+
+\begin_layout Enumerate
+Si la tabla del símplex al final de la primera fase no incluye variables
+ artificiales básicas, tenemos una base de
+\begin_inset Formula $A$
+\end_inset
+
+, [...] eliminar las variables artificiales y maximizar o minimizar
+\begin_inset Formula $P$
+\end_inset
+
+ [...].
+\end_layout
+
+\begin_layout Enumerate
+Si hay variables artificiales básicas, [...] eliminar las filas con variables
+ artificiales y estaríamos en el primer caso.
+\end_layout
+
+\begin_layout Standard
+[
+\series bold
+Método de penalización:
+\series default
+] Sea
+\begin_inset Formula $M>0$
+\end_inset
+
+ lo suficientemente grande, definimos
+\begin_inset Formula $P_{M}:=\{c\cdot x+M\sum_{i}x_{i}^{*}\}_{[x,x^{*}]\in F^{*}}$
+\end_inset
+
+ si estamos minimizando o
+\begin_inset Formula $P_{-M}:=\{c\cdot x-M\sum_{i}x_{i}^{*}\}_{[x,x^{*}]\in F^{*}}$
+\end_inset
+
+ [si maximizamos].
+ [...] Así:
+\end_layout
+
+\begin_layout Itemize
+Si hay soluciones óptimas
+\begin_inset Formula $[x,x^{*}]$
+\end_inset
+
+, las soluciones con
+\begin_inset Formula $x^{*}=0$
+\end_inset
+
+ son soluciones del problema original.
+ Si no hay [...] de este tipo, el problema no es factible.
+\end_layout
+
+\begin_layout Itemize
+Si hay dirección de ilimitación
+\begin_inset Formula $[d,d^{*}]$
+\end_inset
+
+, sea
+\begin_inset Formula $[x,x^{*}]$
+\end_inset
+
+ la solución básica asociada a la tabla del símplex:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+Si
+\begin_inset Formula $x^{*}=0$
+\end_inset
+
+, d es dirección de ilimitación del problema [...].
+ [...]
+\end_layout
+
+\begin_layout Itemize
+Si
+\begin_inset Formula $x^{*}\neq0$
+\end_inset
+
+, en general no podemos decir nada.
+\end_layout
+
+\end_deeper
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+¿Debería incluir el método revisado y el método para variables acotadas?
+ ¿Y el problema dual?
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+eremember
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Float algorithm
+wide false
+sideways false
+status open
+
+\begin_layout Plain Layout
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+Entrada{Problema $
+\backslash
+min
+\backslash
+{c
+\backslash
+cdot x
+\backslash
+}_{Ax=b,x
+\backslash
+geq0}$.}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Salida{Como en el algoritmo
+\backslash
+ref{alg:simplex}}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+SetKwFunction{interpretar}{interpretar}
+\end_layout
+
+\begin_layout Plain Layout
+
+Encontrar una subsecuencia $
+\backslash
+sigma:
+\backslash
+{1,
+\backslash
+dots,m
+\backslash
+}
+\backslash
+to
+\backslash
+{1,
+\backslash
+dots,m
+\backslash
+}$ tal que $B:=[A_{
+\backslash
+sigma(1)},
+\backslash
+dots,A_{
+\backslash
+sigma(m)}]$ es dual factible (si no la hay, este algoritmo no es aplicable)
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+$(T,x)
+\backslash
+gets
+\backslash
+text{
+\backslash
+params{
+\backslash
+ensuremath{
+\backslash
+sigma}}}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Mientras{$x<0$}{
+\end_layout
+
+\begin_layout Plain Layout
+
+ $Y
+\backslash
+gets TA$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ Tomar $r$ con $x_{
+\backslash
+sigma(r)}<0$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{$
+\backslash
+forall j:N,y_{rj}
+\backslash
+geq0$}{
+\backslash
+Devolver $
+\backslash
+emptyset$}
+\end_layout
+
+\begin_layout Plain Layout
+
+ $q
+\backslash
+gets c_B^tY-c$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ Tomar $k$ con $y_{rk}<0$ y $
+\backslash
+frac{q_k}{y_{rk}}$ mínimo
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+lSSi{$q_k
+\backslash
+leq0$}{
+\backslash
+Devolver
+\backslash
+interpretar{$
+\backslash
+sigma,Y,x,q,k$}}
+\end_layout
+
+\begin_layout Plain Layout
+
+ $
+\backslash
+sigma(
+\backslash
+sigma^{-1}(r))
+\backslash
+gets k$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+ $(T,x)
+\backslash
+gets
+\backslash
+text{
+\backslash
+params{
+\backslash
+ensuremath{
+\backslash
+sigma}}}$
+\backslash
+;
+\end_layout
+
+\begin_layout Plain Layout
+
+}
+\end_layout
+
+\begin_layout Plain Layout
+
+
+\backslash
+Devolver
+\backslash
+interpretar{$
+\backslash
+sigma,Y,x,q$}
+\backslash
+;
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Plain Layout
+\begin_inset Caption Standard
+
+\begin_layout Plain Layout
+\begin_inset CommandInset label
+LatexCommand label
+name "alg:simplex-dual"
+
+\end_inset
+
+Algoritmo dual del símplex para minimizar.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Dado un problema de programación lineal
+\begin_inset Formula $\min_{Ax=b,x\geq0}\{c\cdot x\}$
+\end_inset
+
+, una matriz básica
+\begin_inset Formula $B$
+\end_inset
+
+ es
+\series bold
+dual factible
+\series default
+ si
+\begin_inset Formula $(c_{B}B^{-1}A-c)_{N}\leq0$
+\end_inset
+
+.
+ El
+\series bold
+algoritmo dual del símplex
+\series default
+ es el algoritmo
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "alg:simplex-dual"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Supongamos que tenemos una tabla de símplex óptima con parámetros
+\begin_inset Formula $Y,x,q,\sigma$
+\end_inset
+
+ y queremos añadir al problema una restricción
+\begin_inset Formula $\sum_{j=1}^{n}\alpha_{j}x_{j}\leq\beta$
+\end_inset
+
+.
+ Si
+\begin_inset Formula $\alpha_{j}=0$
+\end_inset
+
+ para todo
+\begin_inset Formula $j:B$
+\end_inset
+
+, podemos añadir la restricción directamente a la tabla añadiendo lo siguiente,
+ donde
+\begin_inset Formula $t:=\beta-\sum_{j=1}^{n}\alpha_{j}x_{j}$
+\end_inset
+
+ y
+\begin_inset Formula $x^{*}$
+\end_inset
+
+ es el valor óptimo de
+\begin_inset Formula $x$
+\end_inset
+
+ calculado antes:
+\begin_inset Formula
+\[
+\begin{array}{c|c|ccc|c|c}
+| & | & & & & | & |\\
+c_{B} & \sigma & & Y & & 0 & x^{*}\\
+| & | & & & & | & |\\
+\hline 0 & x_{n+1} & - & \alpha & - & 1 & t\\
+\hline & & - & q & - & 0 & z
+\end{array}
+\]
+
+\end_inset
+
+Queda una base dual factible de la que sacar la solución con el algoritmo
+ dual.
+ Si la restricción tiene variables básicas, tenemos que cambiarlas por sus
+ expresión respecto a las no básicas con la fórmula
+\begin_inset Formula $x_{\sigma(i)}=x_{\sigma(i)}^{*}-\sum_{j:N}y_{ij}x_{j}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Section
+Ramificación y acotación
+\end_layout
+
+\begin_layout Standard
+La
+\series bold
+ramificación y acotación
+\series default
+ (
+\emph on
+\lang english
+branch and bound
+\emph default
+\lang spanish
+) es un algoritmo para resolver problemas de programación lineal entera.
+ Primero resolvemos el problema relajado para obtener una solución
+\begin_inset Formula $(x_{1}^{*},\dots,x_{n}^{*})$
+\end_inset
+
+.
+ Si en ella todas las variables que debían ser enteras lo son, la solución
+ es óptima, y si existe
+\begin_inset Formula $k$
+\end_inset
+
+ tal que
+\begin_inset Formula $x_{k}^{*}$
+\end_inset
+
+ debería ser entera pero es fraccionaria, creamos dos subproblemas introduciendo
+ las restricciones
+\begin_inset Formula $x_{k}\leq\lfloor x_{k}^{*}\rfloor$
+\end_inset
+
+ en uno y
+\begin_inset Formula $x_{k}\geq\lceil x_{k}^{*}\rceil$
+\end_inset
+
+ en el otro.
+ Como
+\begin_inset Formula $x_{k}$
+\end_inset
+
+ es básica, se puede introducir la nueva restricción fácilmente en la tabla
+ del símplex óptima obteniendo una tabla con base dual factible.
+\end_layout
+
+\begin_layout Standard
+Esto nos da un árbol de subproblemas cuyas hojas son problemas infactibles
+ o cuya solución es solución del problema entero, y que hemos de explorar.
+ La
+\series bold
+solución incumbente
+\series default
+ es la mejor solución del problema entero encontrada hasta ahora, y su valor
+ es el
+\series bold
+valor incumbente
+\series default
+.
+ Podemos podar los nodos con valor óptimo del problema relajado menor o
+ igual que el valor incumbente, pues los valores de sus hijos no van a ser
+ mejores.
+ Como optimización, en vez de añadir una restricción
+\begin_inset Formula $x_{k}\leq0$
+\end_inset
+
+, podemos eliminar
+\begin_inset Formula $x_{k}$
+\end_inset
+
+ del subproblema.
+\end_layout
+
+\begin_layout Standard
+Aunque esto no es
+\begin_inset Quotes cld
+\end_inset
+
+estándar
+\begin_inset Quotes crd
+\end_inset
+
+, si todos los coeficientes de la función objetivo son enteros y todos los
+ no nulos van con una variable entera, todas las soluciones tendrán valor
+ entero y, si un nodo tiene un valor mejor que el incumbente pero con una
+ diferencia menor que 1, podemos podarlo, pues no va a producir una solución
+ mejor del problema entero.
+\end_layout
+
+\begin_layout Standard
+La mayoría de los programas de optimización recorren el árbol de subproblemas
+ con
+\emph on
+\lang english
+backtracking
+\emph default
+\lang spanish
+, lo que suele dar soluciones factibles antes que la búsqueda en anchura.
+ También se puede usar búsqueda primero el mejor, por ejemplo.
+\end_layout
+
+\begin_layout Standard
+Cuando hay varias variables por las que se puede ramificar, una elección
+ adecuada puede acelerar la resolución del problema.
+ Algunas heurísticas son elegir la variable con mayor valor fraccionario,
+ la de valor fraccionario más cercano a
+\begin_inset Formula $\frac{1}{2}$
+\end_inset
+
+ o la que más influye en la función objetivo.
+\end_layout
+
+\begin_layout Section
+Hiperplanos de corte
+\end_layout
+
+\begin_layout Standard
+Un
+\series bold
+hiperplano de corte
+\series default
+ o
+\series bold
+desigualdad válida
+\series default
+ de un problema lineal entero es una desigualdad que cumplen todos sus puntos
+ factibles.
+ Se puede usar para mejorar las cotas en los nodos del árbol de ramificación.
+ Llamamos
+\begin_inset Formula $[[x]]:=x-\lfloor x\rfloor\in[0,1)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dados un problema entero puro
+\begin_inset Formula $\min_{Ax=b,x\in\mathbb{N}^{n}}\{c\cdot x\}$
+\end_inset
+
+ con tabla del símplex óptima para la relajación lineal con coeficientes
+
+\begin_inset Formula $(\sigma,Y,x^{*},q)$
+\end_inset
+
+ y
+\begin_inset Formula $k$
+\end_inset
+
+ tal que
+\begin_inset Formula $x_{k':=\sigma(k)}^{*}\notin\mathbb{Z}$
+\end_inset
+
+, entonces
+\begin_inset Formula
+\[
+-\sum_{j:N}[[y_{kj}]]x_{j}\leq-[[x_{k'}^{*}]]
+\]
+
+\end_inset
+
+es una desigualdad válida del problema entero que
+\begin_inset Formula $x^{*}$
+\end_inset
+
+ no satisface.
+
+\series bold
+Demostración:
+\series default
+ Por la fórmula usada antes para añadir una restricción con variables básicas,
+ para
+\begin_inset Formula $x\in P$
+\end_inset
+
+,
+\begin_inset Formula $x_{k'}+\sum_{j:N}y_{kj}x_{j}=x_{k'}^{*}$
+\end_inset
+
+, luego
+\begin_inset Formula $x_{k'}+\sum_{j:N}([y_{kj}]+[[y_{kj}]])x_{j}=[x_{k'}^{*}]+[[x_{k'}^{*}]]$
+\end_inset
+
+ y
+\begin_inset Formula $x_{k'}+\sum_{j:N}[y_{kj}]x_{j}-[x_{k'}^{*}]=-\sum_{j:N}[[y_{kj}]]x_{j}+[[x_{k'}^{*}]]\overset{[[y_{kj}]]\in[0,1),x_{j}\geq0}{\leq}[[x_{k'}^{*}]]<1$
+\end_inset
+
+, y como la parte izquierda de la igualdad es entera, la derecha también
+ y por tanto
+\begin_inset Formula $-\sum_{j:N}[[y_{kj}]]x_{j}+[[x_{k'}^{*}]]\leq0$
+\end_inset
+
+.
+ Despejando para
+\begin_inset Formula $x^{*}$
+\end_inset
+
+ quedaría
+\begin_inset Formula $0\leq-[[x_{k'}^{*}]]$
+\end_inset
+
+, pero
+\begin_inset Formula $[[x_{k'}^{*}]]\in(0,1)$
+\end_inset
+
+ porque
+\begin_inset Formula $x_{k'}^{*}\notin\mathbb{Z}\#$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dados un problema entero puro
+\begin_inset Formula $\min_{Ax=b,x\geq0,\forall i\in I,x_{i}\in\mathbb{Z}}\{c\cdot x\}$
+\end_inset
+
+ con tabla del símplex óptima para la relajación lineal con coeficientes
+
+\begin_inset Formula $(\sigma,Y,x^{*},q)$
+\end_inset
+
+ y
+\begin_inset Formula $k\in I$
+\end_inset
+
+ tal que
+\begin_inset Formula $k':=\sigma(k)\in I$
+\end_inset
+
+ y
+\begin_inset Formula $x_{k':=\sigma(k)}^{*}\notin\mathbb{Z}$
+\end_inset
+
+, entonces
+\begin_inset Formula
+\[
+\sum_{j\in N^{-}}\frac{[[x_{k'}^{*}]]}{1-[[x_{k'}^{*}]]}y_{kj}x_{j}-\sum_{j\in N^{+}}y_{kj}x_{j}\leq-[[x_{k'}^{*}]]
+\]
+
+\end_inset
+
+es una desigualdad válida del problema entero no satisfecha por
+\begin_inset Formula $x^{*}$
+\end_inset
+
+.
+
+\series bold
+Demostración:
+\series default
+ Para
+\begin_inset Formula $x$
+\end_inset
+
+ factible, como
+\begin_inset Formula $x_{k'}+\sum_{j:N}y_{kj}x_{j}=x_{k'}^{*}=[x_{k'}^{*}]+[[x_{k'}^{*}]]$
+\end_inset
+
+, entonces
+\begin_inset Formula $x_{k'}-[x_{k'}^{*}]=-\sum_{j:N}y_{kj}x_{j}+[[x_{k'}^{*}]]$
+\end_inset
+
+.
+ Así, si
+\begin_inset Formula $x_{k'}\leq[x_{k'}^{*}]$
+\end_inset
+
+,
+\begin_inset Formula $-\sum_{j:N}y_{kj}x_{j}+[[x_{k'}^{*}]]\leq0$
+\end_inset
+
+ y
+\begin_inset Formula $-\sum_{j\in N^{+}}y_{kj}x_{j}-\sum_{j\in N^{-}}y_{kj}x_{j}\leq-[[x_{k'}^{*}]]$
+\end_inset
+
+, pero
+\begin_inset Formula $\sum_{j\in N^{-}}y_{kj}x_{j}\geq0$
+\end_inset
+
+, luego
+\begin_inset Formula $-\sum_{j\in N^{+}}y_{kj}x_{j}\leq-[[x_{k'}^{*}]]$
+\end_inset
+
+ y además
+\begin_inset Formula $\sum_{j\in N^{-}}\frac{[[x_{k'}^{*}]]}{1-[[x_{k'}^{*}]]}y_{kj}x_{j}\leq0$
+\end_inset
+
+, de donde se obtiene la desigualdad.
+ Por otro lado, si
+\begin_inset Formula $x_{k'}>[x_{k'}^{*}]$
+\end_inset
+
+, entonces
+\begin_inset Formula $x_{k'}\geq[x_{k'}^{*}]+1$
+\end_inset
+
+, de modo que
+\begin_inset Formula $-\sum_{j:N}y_{kj}x_{j}+[[x_{k'}^{*}]]\geq1$
+\end_inset
+
+ y
+\begin_inset Formula $-\sum_{j\in N^{+}}y_{kj}x_{j}-\sum_{j\in N^{-}}y_{kj}x_{j}\geq1-[[x_{k'}^{*}]]$
+\end_inset
+
+.
+ Con esto, como
+\begin_inset Formula $-\sum_{j\in N^{+}}y_{kj}x_{j}\leq0$
+\end_inset
+
+, se tiene
+\begin_inset Formula $-\sum_{j\in N^{-}}y_{kj}x_{j}\geq1-[[x_{k'}^{*}]]$
+\end_inset
+
+ y, multiplicando por
+\begin_inset Formula $-\frac{[[x_{k'}^{*}]]}{1-[[x_{k'}^{*}]]}$
+\end_inset
+
+,
+\begin_inset Formula $\sum_{j\in N^{-}}\frac{[[x_{k'}^{*}]]}{1-[[x_{k'}^{*}]]}y_{kj}x_{j}\leq-[[x_{k'}^{*}]]$
+\end_inset
+
+, de donde se obtiene la desigualdad usando
+\begin_inset Formula $-\sum_{j\in N^{+}}y_{kj}x_{j}\leq0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+El
+\series bold
+método de los hiperplanos de corte de Gomory
+\series default
+ consiste en hallar sucesivamente un hiperplano de corte de una de las dos
+ formas anteriores, según si el problema es entero puro o mixto, añadirlo
+ al problema y re-optimizar (con el método dual del símplex) hasta llegar
+ a una solución entera.
+ Si hay varios índices
+\begin_inset Formula $k$
+\end_inset
+
+ candidatos, se elige el que tiene
+\begin_inset Formula $[[(x_{B}^{*})_{k}]]$
+\end_inset
+
+ más cercano a
+\begin_inset Formula $\frac{1}{2}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Si los coeficientes de
+\begin_inset Formula $A$
+\end_inset
+
+ y
+\begin_inset Formula $b$
+\end_inset
+
+ no son enteros sino racionales, se pueden multiplicar restricciones o variables
+ apropiadamente para convertirlos en enteros antes de empezar.
+ Lo de que
+\begin_inset Formula $A$
+\end_inset
+
+ y
+\begin_inset Formula $b$
+\end_inset
+
+ sean enteros se usa para que, al añadir las variables de holgura de las
+ desigualdades, estas sean enteras.
+\end_layout
+
+\begin_layout Section
+Desigualdades de Chvátal-Gomory
+\end_layout
+
+\begin_layout Standard
+Dado un problema entero puro con conjunto factible
+\begin_inset Formula $P:=\{Ax\leq b,x\in\mathbb{N}^{n}\}$
+\end_inset
+
+, donde
+\begin_inset Formula $A\in{\cal M}_{m\times n}(\mathbb{R})$
+\end_inset
+
+, para
+\begin_inset Formula $u\in\mathbb{R}^{m}$
+\end_inset
+
+ con
+\begin_inset Formula $u\geq0$
+\end_inset
+
+,
+\begin_inset Formula $\lfloor u^{\intercal}A\rfloor x\leq\lfloor u\cdot b\rfloor$
+\end_inset
+
+ es una desigualdad válida del problema.
+ Las desigualdades de esta forma se llaman
+\series bold
+desigualdades de Chvátal-Gomory
+\series default
+, y toda desigualdad válida de
+\begin_inset Formula $P$
+\end_inset
+
+ se puede obtener utilizando el procedimiento de obtener y añadir una desigualda
+d de este tipo al problema un número finito de veces.
+\end_layout
+
+\end_body
+\end_document
generated by cgit v1.2.3 (git 2.46.0) at 2025-10-27 12:52:38 +0000