You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

177 lines
5.9 KiB

\documentclass{article}
\usepackage{bstr}
\fancyhead[L]{MA4701 - Optimización Combinatorial}
\fancyhead[R]{Primavera 2013}
\fancyfoot[C]{}
\title{Auxiliar 3}
\date{}
\begin{document}
\maketitle
\thispagestyle{fancy}
\section*{P1}
\subsection*{a)}
\begin{itemize}
\item[$\Rightarrow$] Sea $X$ realista\footnote{¡Viva Fernando VII!} y $\pi\in\Sigma_n$ tal que todo $i\in
X$ sea realiza a tiempo.
Definamos $i_t \colonequals $ el $t$-ésimo trabajo de $X$ que se completó.
Primero, $\pi(i_t)\geq t$ (pues se hicieron al menos $t-1$ tareas antes).
Por otro lado, $\pi(i_t) \leq D(i_t)$ (pues $X$ es realista).
Por lo tanto, $t\leq D(i_t) \Rightarrow \{i\in X|D(i)\leq t\} \subseteq
\{i_1,\dots,i_t\} \Rightarrow |\{i\in X|D(i)\leq t\}|\leq t$.
\item[$\Leftarrow$] Supongamos $|\{i\in X|D(i)\leq t\}|\leq t$. Realizamos
las tareas de $X$ de manera que su fecha límite es creciente. Por lo tanto,
completamos todas las tares de $X$ con límite $t$ o menor al día $t$. Es
decir, $\forall i\in X, \pi(i)\leq D(i)$. Luego, $X$ es realista.
\end{itemize}
\subsection*{b)}
Tenemos que
\[c(\pi) = \sum_{i:\pi(i)>D(i)} P(i) =
\sum_{i=1}^{n}P(i) - \sum_{i:\pi(i)\leq D(i)} P(i)\]
Luego,
\[\min_{\pi\in\Sigma_n} c(\pi) = \sum_{i=1}^{n} P(i)
- \max_{\pi\in\Sigma_n} \sum_{i:\pi(i)\leq D(i)} P(i)\]
Pero
\[\max_{\pi\in\Sigma_n} \sum_{i:\pi(i)\leq D(i)} P(i) =
\max_{\text{$X$ realista}}\sum_{i\in X} P(i)\]
\subsection*{c)}
Claramente, $\varnothing\in\I$, pues $\varnothing$ es realista.
Además, si $X\subseteq Y$, $Y$ realista, entonces existe $\pi$ tal que realiza a
tiempo todas las tareas de $Y$. Luego, $\pi$ realiza a tiempo todas las tareas
de $X$.
Sean $X,Y\in\I$, $|X|<|Y|$. \textbf{Pdq} $\exists e\in Y\setminus X$ tal que
$X+e\in\I$.
Sea $t^*$ el entero más grande tal que $|\{i\in Y| D(i)\leq t^*\}|\leq |\{i\in
X| D(i)\leq t^*\}|$. Tal entero existe y es menor que $n$, pues
\begin{align*}
|\{i\in Y| D(i)\leq 0\}| = 0 &\leq 0 |\{i\in X:D(i)\leq 0\}|\\
|\{i\in Y| D(i)\leq n\}| = |Y| &> |X| = |\{i\in X| D(i)\leq n\}|
\end{align*}
Escogemos $j$ en $Y\setminus X$ con fecha límite $t^*+1$. Hacemos $Z\colonequals
X\cup\{j\}$. Sea $t\in\{1,\dots,n\}$.
\begin{itemize}
\item Si $t\leq t^*$, entonces $|\{i\in Z| D(i)\leq t\}| = |\{i\in
X:D(i)\leq t\}| \leq t$.
\item Si $t > t^*$, entonces $|\{i\in Z| D(i)\leq t\}| = |\{i\in X| D(I)\leq
t\}| + 1 \leq |\{i\in Y: D(i)\leq t\}| \leq t$ pues $Y$ es realista.
\end{itemize}
Por lo tanto, $Z$ es realista.
\subsection*{d)}
\textsc{Programación Glotona}
\begin{algorithm}
\DontPrintSemicolon
Ordenamos $P$ decreciente \tcp*{$O(n\log n)$}
$j \gets 0$\;
\For{$i\in[n]$}
{
$X[j+1]\gets i$\;
\If{$X[1,\dots,j+1]$}
{
$j\gets j+1$\;
}
}
\Return{\text{la ``permutación canónica'' de $X[1,\dots,j]$}}\;
\end{algorithm}
Si chequear ``realismo'' es $O(n)$, entonces \textsc{Programación Glotona} es
$O(n^2)$.
\section*{P2}
\subsection*{a)}
\textbf{Pdq} $\mathcal{C}=\{X\subseteq E| X\not\in\I, X-e\in\I, \forall e\in X\}$ cumple los axiomas de circuito.
\begin{itemize}
\item[\textbf{C1}] $\varnothing\in\I\Rightarrow\varnothing\not\in C$
\begin{lema}
$Y\in\I \iff \forall X\subseteq Y,X\not\in\mathcal{C}$
\end{lema}
\begin{dem}
\begin{itemize}
\item[$\Rightarrow$] $Y\in\I \Rightarrow \forall X\subseteq Y,
X\in\I\Rightarrow X\not\in\mathcal{C}$
\item[$\Leftarrow$] Supongamos que $Y\not\in\I$. Como $Y\not\in\mathcal{C}$,
existe $e_1$ tal que $Y-e_1\not\in\I$. Como $Y-e_1\subseteq Y,
Y-e_1\not\in\mathcal{C}$, por lo que existe $e_2$ tal que $Y-e_1-e_2\not\in\I$,
$Y-e_1-e_2\subseteq Y$, $Y-e_1-e_2\not\in\mathcal{C}$.
Iterando el argumento $|Y|$ veces, $\varnothing\not\in\I$ $\contra$.
\end{itemize}
\end{dem}
\item[\textbf{C2}] Sea $X\subseteq Y$, $X,Y\in\mathcal{C}$. Si $X\subsetneq Y$,
existe $e\in Y\setminus X$. Como $Y\in\mathcal{C}$, $Y-e\in \I$, pero $\mathcal{C}\ni
X\subseteq Y-e\in\I$, lo que contradice el lema.
\item[\textbf{C3}] Sean $X,Y$ distintos, $e\in X\cap Y$. Supongamos que no
existe $Z\in\mathcal{C}$ con $X\subseteq(X\cup Y)-e$. Por lema,
$(X\cup Y)-e\in\I$ es independiente. Como $X,Y$ son distintos, de la
propiedad \textbf{C2}, $X\not\subseteq Y$ y $Y\not\subseteq Z$. Sea $f\in
Y\setminus X$. Como $Y\in\mathcal{C}$, $Y-f\in I$.
\[\{P\in\I| Y-f\subseteq P\subseteq X\cup Y\}\neq\varnothing\]
Sea $W$ maximal para la inclusión en tal conjunto. Notemos que $f\not\in W$,
pues si lo hiciera
\[\mathcal{C}\ni Y = \underbrace{Y-f}_{\subseteq W} + \underbrace{f}_{\in W} \subseteq
W\in\I\]
Sea $g\in X\setminus W$. Si no existe, $X\subseteq W$, pero $X\in\mathcal{C},
W\in\I$. Luego, $g\neq f$.
Por lo tanto,
\[|W|\leq |(X\cup Y)\setminus\{f,g\}| = |(X\cup Y)| - 2 < |X\cup Y| - 1 =
|X\cup Y -e|\]
Como $W, X\cup Y-e\in \I$, existe $h\in(X\cup Y)-e$ tal que $W+h\in I$, lo
que contradice la maximalidad de $W$.
\end{itemize}
\subsection*{b)}
Sea $\mathcal{C}$ familia que cumple los axiomas de circuito. Sea
$\I=\{X\subseteq E| \text{$X$ no tiene circuito}\}$.
\textbf{Pdq} $I$ es matroide.
\begin{itemize}
\item $\varnothing\not\supseteq C, \forall C\in\mathcal{C}$
\item $y\in\I \Rightarrow \not\exists C\in\mathcal{C}$ tq $C\subseteq Y$. Si
$X\subseteq Y$, tampoco contiene $C\in\mathcal{C}$.
\item Ahora, basta ver aumento débil. Sean $X,Y\in\I$ con $|Y\setminus X|
= 2, |X\setminus Y| = 1$.
\textbf{Pdq} $\exists y\in Y\setminus X$ tal que $X+y\in\I$.
Supongamos que no. Entonces, $X+y_1,X+y_2\not\in\I$ ($\{y_1,y_1\} =
Y\setminus X$). Es decir, $\exists C_1, C_2\in\mathcal{C}$ tales que
$C_1\subseteq X+y_1, C_2\subseteq X+y_2$. Como $C_1,C_2\not\subseteq X$,
entonces, $y_1\in C_1, y_2\in C_2$. Luego, $C_1\neq C_2$, pues $y_1\in
C_2, y_1\not\in\mathcal{C}_2$ y viceversa.
Como $C_1,C_1\not\subseteq Y$, entonces $x\in C_1\cap C_2$ ($\{x\}\in
X\setminus Y$). Por \textbf{C3}, existe $C_3$ tal que $C_3\subseteq
(C_1\cup C_2)-x\subseteq Y$, pero $Y\in\I$ $\contra$.
\end{itemize}
\end{document}