Archivo de la categoría: Matemáticas

Posts de matemáticas, la ciencia más cercana a las artes.

Álgebra Moderna I: Subgrupo Conjugado, Subgrupo Normal y Conmutatividad Parcial

Por Cecilia del Carmen Villatoro Ramos

Deja un comentario

Introducción

Hace algunas entradas, comenzamos dando una motivación usando a los enteros. En esta, nos encontramos de nuevo con la necesidad de retomarlos para darle introducción al tema principal de la entrada. Sabemos que $(\z, +)$ es un grupo, de ahí podemos tomar los subgrupos de las clases módulo $n$. Supongamos que tenemos las clases de equivalencia módulo $a$ y módulo $b$ respectivamente, $a,b\in \z$. Éstas se definen de esta manera:
\begin{align*}
\bar{a} = a + \z, \quad \bar{b} = b + \z.
\end{align*}

Si queremos sumar dos clases de equivalencia, usamos la suma usual en $\z$. Digamos
\begin{align*}
\bar{a} + \bar{b} = \overline{a+b}.
\end{align*}

Aunque lo escribamos así, en realidad lo que estamos haciendo, es definir la suma $+_n$ en $\z_n$ usando $+_\z$ que es la suma del grupo $(\z,+)$. Entonces lo anterior quedaría:
\begin{align*}
\bar{a} +_n \bar{b} = \overline{a+_\z b}.
\end{align*}

El caso es que $+_n$ es una operación bien definida y $(\z_n,+_n)$ es un grupo.

Otra manera de escribirlo sería:
\begin{align*}
(a+\z) +_n (b+\z) = (a+_\z b) + \z.
\end{align*}
Donde, en este caso $+$ es notación.

Entonces, ahora nos preguntamos, ¿cómo podemos generalizar esta propiedad?

Tomemos $G$ un grupo y $H$ un subgrupo y consideremos dos clases laterales izquierdas de $H$, digamos $aH$ y $bH$, lo que queremos es
\begin{align*}
aH \cdot_H bH = ab H.
\end{align*}

Donde $\cdot_H$ es el nuevo producto que queremos definir y $ab$ se hace con el producto en $G$.

Lo siguiente que queremos probar es si ese producto ($\cdot_H$) está bien definido. Para ello tenemos que tomar otro representante de las clases, para simplificarlo, tomemos sólo una $\tilde{a}H = aH$.

Entonces, queremos que $abH = \tilde{a}bH$, esto sucedería sólo de la siguiente manera,
\begin{align*}
abH = \tilde{a}b H \Leftrightarrow\;& (ab)^{-1} \tilde{a}b\in H\\
\Leftrightarrow\;& b^{-1}a^{-1}\tilde{a}b\in H.
\end{align*}

Entonces, ¿cómo sabemos que $b^{-1}a^{-1}\tilde{a}b\in H$? De por sí, sabemos que $a^{-1}\tilde{a} \in H$, pues $\tilde{a}H= aH$. Entonces, todo se reduce a que necesitamos que al conjugar elementos de $H$ sigamos obteniendo elementos en $H$.

Así que en esta entrada buscaremos definir un producto entre dos clases izquierdas usando el producto en $G$.

El grupo normal

Primero necesitamos definir formalmente qué es un conjugado en nuestro contexto.

Definición. Sea $G$ un grupo, $H$ subgrupo de $G$, $b,c \in G$. Decimos que $b$ es conjugado de $c$ si $b = aca^{-1}$ para alguna $a\in G$.

Dado $a\in G$ el conjugado de $H$ por el elemento $a$ es
$$aHa^{-1} = \{aha^{-1}|h\in H\}.$$

Observación. $aHa^{-1}$ es un subgrupo de $G$, para toda $a \in G$.

La demostración de esta observación te queda de tarea moral.

Definición. Sea $G$ un grupo, $N$ subgrupo de $G$. Decimos que $N$ es normal en $G$ si $ana^{-1} \in N$ para toda $a\in G$, $n\in N$.

Notación. $N\unlhd G$.

Ahora, veamos una proposición. Recordemos que en una entrada pasada vimos que las clases laterales izquierdas no siempre coinciden con las clases laterales derechas y dimos algunos ejemplos. La siguiente proposición nos dirá que con subgrupos normales, la igualdad de clases derechas e izquierdas siempre se da.

Proposición. Sea $G$ un grupo, $N$ subgrupo de $G$. Las siguientes condiciones son equivalentes:

  1. $N\unlhd G$.
  2. $a N a^{-1} = N$ para todo $a\in G$.
  3. Toda clase laterial izquierda de $N$ en $G$ es una clase lateral derecha de $N$ en G.

Demostración. Sea $G$ un grupo, $N \leq G$.

$|1) \Rightarrow 2)]$ Supongamos que $N \unlhd G$. Sea $a\in G$.

P.D. $aNa^{-1} = N$.
Probaremos esto por doble contención.

$\subseteq]$ Como $N\unlhd G$, $ana^{-1} \in N$ para toda $n\in N$. Entonces el conjunto $aNa^{-1} = \{ana^{-1}|n\in N\}$ está contenido en $N$.

$\supseteq]$ Sea $n\in N$, como $N\unlhd G$, $a^{-1}na = a^{-1}n(a^{-1})^{-1} \in N$. Entonces $n = a(a^{-1}n a)a^{-1} \in a N a^{-1}$.

Por lo tanto $aNa^{-1} = N$.

$|2) \Rightarrow 3)]$ Supongamos que para todo $a \in G$, entonces $aNa^{-1} = N$. Sea $a\in G$.

P.D. $aN = Na$.
De nuevo, probaremos esto por doble contención.

$\subseteq]$ Tomemos $an \in aN$ con $n\in N$, como $ana^{-1} \in aNa^{-1}$ y $ aNa^{-1}= N$ por hipótesis. Entonces $an = (ana^{-1}) a \in Na$.

$\supseteq]$ Tomemos $na \in Na$ con $n\in N$, como $a^{-1}na \in a^{-1}Na$ y $a^{-1}Na = N$ por hipótesis. Entonces $na = a(a^{-1}na) \in aN$.

Por lo tanto $aN = Na$.

$|3)\Rightarrow 1)]$ Supongamos que para todo $a\in G$, existe $b\in G$ tal que $aN = Nb$. Sea $a \in G$ y $n \in N$.

P.D. $ana^{-1} \in N$.

Por hipótesis $aN = Nb$ para alguna $b\in G$. Pero $a \in aN = Nb$, entonces $Na = Nb$.

Así $an\in aN = Na$ y entonces $an = \tilde{n}a$ para alguna $\tilde{n}\in N$. Entonces

\begin{align*}
ana^{-1} = (an)a^{-1} = (\tilde{n}a)a^{-1} = \tilde{n} \in N
\end{align*}
Por lo tanto $N \unlhd G$.

Así 1), 2) y 3) son equivalentes.

$\blacksquare$

Observación. (Conmutatividad parcial)
Si $N\unlhd G$, dados $n\in N$ y $a\in G$. Si $an = \tilde{n}a$ para alguna $\tilde{n}\in N$, también $na = a \bar{n}$ para alguna $\bar{n} \in N$.

Ejemplos

  1. $A_n \unlhd S_n$ ya que si $\beta \in A_n$ y $\alpha\in S_n$.
    \begin{align*}
    sgn(\alpha\beta\alpha^{-1}) &= sgn\alpha \; sgn\beta \:sgn \,\alpha^{-1}\\
    & = sgn\alpha \;(+1) \;sgn \alpha \\
    & = +1
    \end{align*}
    Por lo tanto $\alpha\beta\alpha^{-1}\in A_n$.
  2. Consideremos
    \begin{align*}
    Q &= \{\pm 1, \pm i, \pm j, \pm k\}\\
    H &= \{\pm 1, \pm i\}
    \end{align*}
    Las clases laterales izquierdas de $H$ en $Q$ son: $H$ y $jH$.
    Las clases laterales derechas de $H$ en $Q$ son: $H$ y $Hj$.
    Además $jH = \{\mp j, \mp k\} = Hj$. Por lo tanto $H \unlhd Q$.
  3. Consideremos $D_{2(4)}$ las simetrías del cuadrado. Sea $a$ la rotación $\frac{\pi}{2}$, $b$ la reflexión on respecto al eje $x$.
    Sea $H = \{e, b\}$.
    Si tomamos la transformación $aba^{-1}$ podemos desarrollarla algebráicamente y visualmente. Primero lo haremos de manera algebráica y la visual la podrás encontrar en una imagen más abajo.
    Así, como vimos cuando trabajamos con el grupo diédrico:
    $aba^{-1} = aab = a^2b \not\in H$
    reflexión con respecto al eje $y$.
    Por lo tanto $H \not\unlhd D_{2(4)}$.
Representación gráfica de la transformación $aba^{-1}$.

Tarea moral

  1. Sean $W = \left< (1\;2)(3\;4)\right>$, $V = \{(1), (1\;2)(3\;4),(1\;3)(2\;4),(1\;4)(2\;3)\}\leq S_4$. Verifica si $W$ es normal en $V$, si $V$ es normal en $S_4$ y si $W$ es normal en $S_4$ ¿qué puedes concluir con ello?
  2. Sea $G$ un grupo, $H$ y $N$ subgrupos de $G$ con $N$ normal en $G$, prueba o da un contraejemplo:
    1. $N\cap H$ es normal en $H$.
    2. $N\cap H$ es normal en $G$.
  3. Demuestra o da un contraejemplo: Si $G$ es un grupo tal que cada subgrupo de él es normal, entonces $G$ es abeliano.
  4. Sea $G$ un grupo finito con un único subgrupo $H$ de orden $|H|$. ¿Podemos concluir que $H$ es normal en $G$?

Más adelante…

Como ya es costumbre, después de dar las definiciones y de practicarlas un poco con ejemplos, toca profundizar y hablar más sobre las proposiciones y teoremas que involucran los subgrupos normales. En la siguiente entrada veremos esto.

Entradas relacionadas

Álgebra Moderna I: Caracterización de grupos cíclicos

Por Cecilia del Carmen Villatoro Ramos

Deja un comentario

Introducción

Gracias al teorema de Lagrange sabemos que el orden de todo subgrupo divide al del grupo que lo contiene, pero no sabemos si para cada divisor del orden del grupo, existe un subgrupo de ese tamaño. El siguiente teorema nos da una respuesta cuando hablamos de grupos cíclicos finitos.

Para grupos cíclicos, existe un único subgrupo de orden que divide al tamaño del grupo. Eso es lo primero que veremos en esta entrada. Después, demostraremos un resultado de teoría de números, usando teoría de conjuntos para llegar a una caracterización de los grupos cíclicos.

Todo divisor tiene un subgrupo de ese orden

Teorema. Sea $G$ un grupo finito cíclico de orden $n$. Para cada $d \in \z^+$ divisor de $n$ existe un único subgrupo de $G$ de orden $d$.

Demostración.
Sea $G$ un grupo finito cíclico de orden $n$ y sea $a \in G$ tal que $G = \left< a \right>$.

Sea $d\in \z^+$ con $d|n$.

P.D. Existe un subgrupo de $G$ de orden $d$.
Como $d|n$, entonces $n = dk$ con $k \in \z$.

Sabemos por un ejercicio que
\begin{align*}
o(a^k) = \frac{n}{(n,k)} = \frac{n}{k} = d.
\end{align*}

Así $|\left< a^k \right>| = o(a^k) = d$.

P.D. Que no hay otro subgrupo de orden $d$.
Sea $H\leq G$ con $|H|=d$. Como $G$ es cíclico, $H$ también es cíclico y, por ende, $H = \left< a^m \right>$ para alguna $m \in \z$, entonces

\begin{align*}
&e = (a^m)^{|H|} = (a^m)^d = a^{md}.
\end{align*}
Como $ a^{md} = e$, podríamos pensar que $o(a) = md$, sin embargo eso no es siempre cierto, lo que si es cierto es que $n|md$. Entonces, existe $q\in\z$ tal que
\begin{align*}
&md = nq\\
\Rightarrow \;& md = dkq &\text{Sustituyendo } n = dk\\
\Rightarrow \; &m=kq.
\end{align*}

Así $a^m = a^{kq} = (a^k)^q \in \left< a^k \right>$, entonces $H = \left< a^m\right> \leq \left< a^k\right> $. Pero $| \left< a^m\right>| = |\left< a^k\right>| = d$, por lo tanto $ \left< a^m\right> = \left< a^k\right>$.

$\blacksquare$

Demostrando resultados de teoría de números usando teoría de grupos

Para llegar a una caracterización de los grupos cíclicos, primero vamos a hacer unas pequeñas definiciones con la forma de anotaciones.

Notación. Sea $C$ grupo cíclico, entonces llamamos al conjunto de generadores del grupo cíclico $C$ como
$$\text{gen } C =\{a\in C | \left< a\right> = C\}.$$

Recordatorio. Dado $d \in \z^+$

$$\varphi(d) = \#\{m \in \{1,2,\dots,d\} | (m,d) = 1\}.$$
Es decir, $\varphi(d)$ es la cantidad de primos relativos con $d$. En este caso, $\varphi$ es la phi de Euler.

Ahora, veamos un resultado que se refiere más a asuntos de teoría de números. Pero esta vez lo demostraremos usando teoría de conjuntos.

Teorema. Sea $n\in \z^+$. Entonces $n = \displaystyle \sum_{\substack{d|n \\ 1\leq d \leq n}} \varphi(d)$.

Demostración.
Sea $G$ un grupo cíclico de orden $n$.

Para cada $d|n$, tenemos que $1\leq d\leq n$ existe un único subgrupo de $G$ de orden $d$, digamos $C_d$.

P.D. $\displaystyle G = \bigcup_{\substack{d|n \\ 1\leq d \leq n}} \text{gen } C_d$.

Lo probaremos por doble contención.

$\subseteq]$ Sea $a\in G$.

Sabemos que $\left< a \right>$ es un subgrupo de $G$ de orden $o(a)$, entonces $\left< a \right> = C\,o(a)$ y además $a \in \text{gen }C\, o(a)$. Así $\displaystyle a \in \bigcup_{\substack{d|n \\ 1\leq d \leq n}} \text{gen } C_d.$

$\supseteq]$ Por construcción, se da que $\text{gen } C_d \subseteq G$ para cada $d|n$, $1 \leq d \leq n$.

P.D. Ahora veamos que la unión es disjunta.

Sean $d, d’ \in \{1,\dots, n\}$ divisores de $n$. Sea $a \in \text{gen } C_d \cap \text{gen } C_{d’}$.

Entonces
\begin{align*}
C_d &= \left< a \right> = C_{d’}\\
\Rightarrow \;d &= |C_d| = |C_{d’}| = d’\\
&\therefore d = d’.
\end{align*}

Así tenemos una unión disjunta,

\begin{align*}
|G| &= \left|\bigcup_{\substack{d|n \\ 1\leq d \leq n}} \text{gen } C_d \right| \\
& = \sum_{\substack{d|n \\ 1\leq d \leq n}} \#\text{gen } C_d &\text{Definición de gen }C.
\end{align*}

Luego, en un ejercicio ya probaste que si $C_d = \left<a\right>$, entonces $C_d = \left<a^k\right>$ si y sólo si $(k,d) = 1$. Por lo que tenemos tantos generadores como primos relativos haya con $d$. Así,
\begin{align*}
\sum_{\substack{d|n \\ 1\leq d \leq n}} \#\text{gen } C_d = \sum_{\substack{d|n \\ 1\leq d \leq n}} \varphi(d).
\end{align*}

Por último, como $|G| = n$, se sigue que
\begin{align*}
\sum_{\substack{d|n \\ 1\leq d \leq n}} \varphi(d) = n.
\end{align*}

$\blacksquare$

Ahora sí, la caracterización que todos esperábamos

Después de los resultados anteriores ya estamos listos para dar el siguiente teorema.

Teorema. Sea $G$ un grupo finito de orden $n$. $G$ en cíclico si y sólo si para cada $d \in \z^+$ divisor de $n$, $G$ tiene a lo más un subgrupo cíclico de orden $d$.

A pesar de que el enunciado dice que $G$ tiene a lo más un subgrupo cíclico, al final resulta que existe un único. La redacción es adrede para que la demostración del regreso no sea trivial.

Demostración.
Sea $G$ un grupo finito de orden $n$.

$|\Rightarrow]$ Si $G$ un cíclico, para cada $d \in \z^+$ divisor de $n$, $G$ tiene exactamente un sibgrupo cíclico de orden $d$.

$[\Leftarrow|$ Supongamos que para toda $d \in \z^+$ divisor de $n$, $G$ tiene a lo más un subgrupo cíclico de orden $d$, si existe lo denotaremos por $C_d$, si no existe definimos $C_d = \emptyset$ y definimos también $\text{gen } C_d = \emptyset$ en ese caso.

De nuevo, tenemos una unión disjunta. Demostrar la igualdad es análogo al teorema anterior.
\begin{align*}
G = \bigcup_{\substack{d|n\\1\leq d\leq n}} \text{gen }C_d.
\end{align*}

Entonces, usando el teorema anterior,

\begin{align*}
n = |G| = \sum_{\substack{d|n\\1\leq d \leq n}} \#\text{gen } C_d \leq \sum_{\substack{d|n\\1\leq d \leq n}} \varphi(d) = n
\end{align*}

Donde el teorema anterior se usa en la última igualdad.

Así, para toda $d|n$, con $1\leq d\leq n$ se tienen que $\#\text{gen } C_d = \varphi(d)$ de donde $\text{gen } C_d \neq \emptyset$.

Por lo tanto, para toda $d|n$ con $1\leq d \leq n$, $G$ tiene exactamente un subgrupo cíclico de orden $d$. En particular $G$ tiene exactamente un subgrupo cíclico de orden $n$ que debe ser $G$ mismo.

$\therefore G$ es cíclico. $\blacksquare$

Consecuencias

Corolario 1. Sea $G$ un grupo finito de orden $n$. Si para toda $d\in \z^+$ divisor de $n$ hay a lo más $d$ soluciones de $x^d = e$ en $G$, entonces $G$ es cíclico.

Demostración.
Sea $G$ un grupo finito, $|G| = n$, tal que $\forall d \ n \z^+$ que $d|n$, existen a lo más $d$ soluciones de $x^d = e$ en $G$.

P.D. $G$ es cíclico.

Supongamos por contradicción que para alguna $d\in\z^+$ que $d|n$ existen $C,C’$ con $C\neq C’$ subgrupos cíclicos de $G$ de orden $d$.

Por un lado, si $a\in C$, $e = a^{|C|} = a^d$. Por otro lado, si $a\in C’$, $e = a^{|C’|} = a^d$. Entonces para toda $a\in C\cup C’$, $a$ es solución de $x^d = e$.

Pero como $C \neq C’$, entonces $\#C\cup C’ > |C| = d$, entonces habría más de $d$ soluciones de $x^d=e$ en $G$. Esto es una contradicción.

Así, para toda $d\in\z^+$ tal que $d\in\n$ existe a lo más un subgrupo cíclico de orden $d$.

Por el teorema anterior, $G$ es cíclico.

$\blacksquare$

En realidad, nos interesa el corolario 1, para probar el corolario 2.

Corolario 2. Para todo campo finito $K$, el grupo multiplicativo $K^* = K\setminus\{0\}$ con la multiplicación del campo, es cíclico.

Demostración.
Sea $d\in \z^+$ tal que $d\big||K^*|$.

Ahora, nos fijamos en el polinomio $f(x) = x^d -1$ que tiene a lo más $d$ raíces en $K^*$. Porque las soluciones a esa ecuación son las $x^d = 1$, además, $1$ es el neutro multiplicativo de $K$.
Por lo tanto, por el corolario 1, $K^*$ es cíclico.

$\blacksquare$

Tarea moral

  1. Dada $d\in \z^+$ definimos
    \begin{align*}
    \phi(d) = \#\{m\in \{1,2,\dots,d\}\, | \, (m,d) = 1\}.
    \end{align*}
    Donde $(m,d)$ es máximo común divisor.
    Encuentra $\displaystyle \sum_{\substack{ d|n \\ 1\leq d \leq n}} \phi(d) $ para $n \in \{5,8,9,12\}$.
  2. Considera el conjunto
    \begin{align*}
    K = \left\{ \begin{pmatrix}
    a & b \\ b & a+b
    \end{pmatrix} \, \Big| a,b\in\z_2
    \right\}
    \end{align*}
    con las operaciones usuales. Prueba que $K$ es un campo con cuatro elementos y verifica que $K^*$ es cíclico.

Más adelante…

Con esta entrada concluimos por el momento con temas relacionados al orden de un grupo y de un subgrupo. En la próxima entrada comenzaremos una nueva tarea: encontrar una multiplicación apropiada entre dos clases laterales, para ello, regresaremos a estudiar un poco a los enteros.

Entradas relacionadas

Investigación de Operaciones: El problema de producción e inventario

Por Aldo Romero

Deja un comentario

Introducción

Ya hemos visto algunos ejemplos en los que se plantea un problema de programación lineal a partir de un contexto específico. Hemos visto el problema de la dieta, el problema de la mochila y el problema del transporte. Hay algunos problemas que parecen un poco más complicados y que no es tan evidente desde el inicio que se pueden plantear como problemas de programación lineal. En esta ocasión veremos uno de ellos: el problema de producción e inventario.

A grandes rasgos, el problema consiste en modelar una fábrica que necesita tener lista cierta cantidad de inventario de un producto en determinados momentos del año. La fábrica puede producir cierta cantidad de producto que depende de la temporada del año. Quizás haya temporadas en las que puede producir más de lo que necesita, pero si hace eso incurrirá en costos de almacenaje. ¿Cómo puede distribuir su producción, almacenaje y despacho la fábrica para minimizar el costo y cumplir con su compromiso de inventario? Veamos a continuación que esta situación se puede plantear en términos de un problema de programación lineal.

Ejemplo del problema de producción e inventario

Una fábrica de alimento para gatos tiene un contrato para entregar las siguientes cantidades de alimento al final de cada uno de los trimestres indicados.

Trimestre1234
Demanda en
toneladas		100150480350

Debido a la estacionalidad de los ingredientes involucrados en la producción de alimento para gato, la fábrica tiene una capacidad de producción trimestral de 150 toneladas en los semestres 1 y 3; y de 260 toneladas en los trimestres 2 y 4.

El costo de producción de cada tonelada de alimento para gato es de \$50,000. Por otro lado, es posible almacenar el producto de un trimestre a otro incurriendo en un costo de \$8,000 por unidad. También se tiene la opción, con objeto de cumplir el contrato, de comprar a un competidor alimento para gato a \$52,000 la tonelada.

Se desea determinar un plan de producción, inventario y compra que satisfaga el contrato a costo mínimo.

Variables de decisión del problema de producción e inventario

Lo que se puede decidir en este problema es cuánto alimento producir en cada semestre, y cuánto alimento comprar a un competidor en cada semestre. De esta manera, planteamos las variables de decisión como sigue:

  • $x_i$ = cantidad de alimento de gato (en toneladas) a producir en el trimestre $i$ , $i=1, \ldots ,4.$
  • $y_i$ = cantidad de alimento de gato (en toneladas) a comprar al competidor en el trimestre $i$, $i=1, \ldots , 4.$

Restricciones del problema de producción e inventario

Una primera cosa a observar es que el alimento de gato que sobre de un periodo a otro puede ser usado para cubrir la demanda del segundo periodo, claro, con la desventaja de que esto incurrirá en un costo. ¿Cómo podemos determinar la cantidad de alimento que sobra? Por ejemplo, el alimento que sobra del primer al segundo periodo sería $x_1+y_1-100$, pues a lo producido y comprado habrá que quitar lo que sí se vendió. De manera similar podemos calcular otros sobrantes.

Con esto en mente, vamos a plantear primero las restricciones de demanda. Lo que requerimos es que todo el alimento sobrante, producido y comprado de cada periodo sea suficiente para cubrir la demanda. De esta manera, tenemos las siguientes restricciones.

\begin{align}
x_1 + y_1 &\geq 100\\
x_2 + y_2 + (x_1 + y_1 – 100) &\geq 150\\
x_3 + y_3 + (x_2 + y_2 + (x_1 + y_1 – 100) – 150) &\geq 480\\
x_4 + y_4 + (x_3 + y_3 + (x_2 + y_2 + (x_1 + y_1 – 100) – 150) – 480) &\geq 350.\\
\end{align}

Si bien estas desigualdades reflejan correctamente lo requerido, las condiciones anteriores son un poco complicadas de escribir. Por esta razón, vamos a introducir algunas variables auxiliares. Estas serán variables que no se deciden sino que están totalmente determinadas por lo que se produce y compra al competidor. De cualquier forma, es útil introducirlas en el modelo, y para dejar claro que dependen de las variables $x_i$, tendremos que establecer algunas restricciones dadas por igualdades. Hagamos esto. Definamos las siguientes variables.

  • $w_i$ = cantidad de fertilizante (en toneladas) en inventario al final del trimestre $i$, $i=1, \ldots , 4.$

Como comentamos arriba, estas variables dependen de las variables $x_i$ y $y_i$; de hecho, por ejemplo: $$w_1 = x_1 + y_1 – 100.$$

Si reescribimos esta restricción obtenemos

$$x_1 + y_1 – w_1 = 100.$$

Análogamente:

\begin{align*}
x_2 + y_2 + w_1 – w_2 = 150\\
x_3 + y_3 + w_2 – w_3 = 480\\
x_4 + y_4 + w_3 – w_4 = 350.\\
\end{align*}

Tenemos una gran ventaja de usar estas restricciones. Es exactamente lo mismo «que se cubra la demanda en cada periodo» a que «lo que nos sobre en cada periodo sea $\geq 0$». Intenta convencerte de esto intuitivamente y luego verifica esto algebraicamente. Por ejemplo, nota que la primera condición de demanda ($x_1+y_1\geq 100$) es exactamente lo mismo que pedir $w_1=0$, y lo mismo para las demás. De esta manera, las restricciones (1),(2),(3) y (4) pueden cambiarse por pedir que cada $w_i\geq 0$.

Con esto terminamos con las restricciones de demanda. Tenemos otras restricciones dadas por la cantidad de toneladas de alimento que se pueden producir cada mes. Estas quedan expresadas en las siguientes desigualdades:

\begin{align*}
x_i \leq 150, i = 1,3\\
x_i \leq 260, i = 2,4.\\
\end{align*}

Finalmente, hay condiciones de no negatividad. Ya dijimos que $w_i\geq 0$ para $i=1,2,3,4$. Además de esto, claramente necesitamos

\begin{align*}
x_i, y_i,\geq 0 \quad i=1, \ldots , 4.
\end{align*}

Función objetivo del problema de producción e inventario

En cada periodo tenemos ciertas toneladas que se producen, ciertas que se compran y ciertas que se obtuvieron por almacenar de periodos anteriores. Cada una de ellas incurre en un costo.

Como cada tonelada producida cuesta \$50,000, el total de gasto por toneladas de alimento de gato producidas es de $50000(x_1+x_2+x_3+x_4)$. Como cada tonelada comprada a un competidos cuesta \$52,000, el total de gasto por toneladas de alimento de gato adquiridas a un competidor es de $52000(y_1+y_2+y_3+y_4)$. De manera similar, el costo incurrido por almacenar sobrantes es de $8000(w_1+w_2+w_3+w_4)$. Si juntamos todo en notación suma obtenemos que el costo total a minimizar es el siguiente:

\begin{align*}
z = 50000\sum_{i=1}^4 x_i + 52000\sum_{i=1}^4y_i + 8000\sum_{i=1}^4w_i.
\end{align*}

Resumen de formulación del problema de producción e inventario

En resumen, el PPL que obtenemos es:

\begin{align*}
Min \quad z &= 50000\sum_{i=1}^4 x_i + 52000\sum_{i=1}^4y_i + 8000\sum_{i=1}^4w_i.
&\\
s.a.&\\
x_1&+y_1-w_1 &= 100\\
x_2&+y_2+w_1-w_2 &= 150\\
x_3&+y_3+w_2-w_3 &= 480\\
x_4&+y_4+w_3-w_4 &= 350\\
&x_i \leq 150, i =1,3, \quad x_i \leq 260, i = 2,4\\
x_i, &y_i,w_i \geq 0, i=1, 2, 3, 4.\\
\end{align*}

Más adelante…

En este problema introducimos las variables $w_i$, y ese es uno de los trucos para ampliar el tipo de situaciones que se pueden atender con problemas de programación lineal. La siguiente entrada muestra nuestro último ejemplo introductorio: el problema de la ruta más corta. Como veremos, en este problema también es necesario aprovechar la situación del problema de manera creativa para poder llevarlo a un contexto lineal.

Tarea moral

  1. El problema se vuelve mucho más sencillo si únicamente hay un periodo, pues en ese caso no sobra inventario de un periodo a otro. Plantea un problema que refleje esta situación en el caso particular de la entrada y resuélvelo. Es decir, determina en ese (único periodo) cuál es la cantidad correcta de unidades a producir y cuál es la cantidad correcta de unidades a comprar al competidor, para optimizar el costo total.
  2. Cambia el planteamiento dado en la entrada por uno en el que el costo de almacenaje es de \$0. En ese caso, ¿cuál sería el plan de producción, inventario y compra óptimo?
  3. Estudia el planteamiento dado en la entrada y realiza cambios ya sea en las variables o restricciones para reflejar las siguientes situaciones:
    1. No hay ningún competidor al que se le pueda comprar producto para ayudar a cumplir la demanda.
    2. Hay un competidor, pero sólo permite comprarle 100 toneladas por periodo.
  4. En esta entrada dimos la formulación de un caso particular del problema de producción e inventario. Sin embargo, ya tienes todas las herramientas para plantear el problema de manera general. Realiza una formulación general en la que:
    1. Se tengan periodos $p_1, p_2, \ldots, p_n$ con requisitos de contrato $r_1, r_2, \ldots, r_n$ unidades a cubrir.
    2. Se tengan capacidades de producción $c_1, c_2, \ldots, c_n$ unidades en cada periodo.
    3. Se tengan costos $P$, $C$ y $A$ de producir, comprar al competidor y almacenar una unidad de producto, respectivamente.
  5. En un problema general de producción e inventario. ¿Por qué podría ser mala idea producir todo lo que se necesita vender? ¿Por qué podría ser mala idea producir mucho más de lo necesario en las temporadas en las que se puede? ¿Por qué podría ser mala idea cubrir toda la demanda con unidades compradas al competidor? Intenta justificar intuitivamente, y luego encuentra algunos casos particulares del problema que apoyen tus argumentos.

Entradas relacionadas

Teoría de los Conjuntos I: Conjuntos finitos (parte II)

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

En esta entrada daremos continuación al tema de conjuntos finitos. Probaremos más resultados que se satisfacen para los conjuntos finitos y veremos cuál es la cardinalidad del conjunto potencia dada un conjunto finito.

Propiedades de los conjuntos finitos

Teorema: Sean $A$ y $B$ conjuntos tales que $B$ es finito. Si $A\subseteq B$, entonces $A$ es finito. Más aún, $|A|\leq |B|$.

Demostración: (Por inducción sobre $|B|$).

Base de inducción: Supongamos que $|B|=0$. Entonces $B=\emptyset$, por lo que $A=\emptyset$ y así, $A$ es finito y $0=|A|\leq |B|=0$.

Hipótesis de inducción: Supongamos que para $|B|=n$ se cumple que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.

Paso inductivo: Sea $B$ un conjunto finito, tal que $|B|=n+1$, veamos que si $A\subseteq B$, entonces $A$ es finito y $|A|\leq |B|$.

Sea $A\subseteq B$ arbritario.

Si $A=B$, entonces $A$ es finito y $|A|\leq |B|$.

Si $A\not=B$, entonces existe $x\in B\setminus A$. Luego, $A\subseteq B\setminus\set{x}$ y como $|B\setminus \set{x}|=n$, tenemos por hipótesis de inducción que $A$ es finito y $|A|\leq |B\setminus \set{x}|=n$. Luego entonces, $A$ es finito y $|A|\leq |B|$.

$\square$

Cardinalidad del conjunto potencia

Teorema: Si $X$ es finito, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$.

Nota: $2^{n}=\underbrace{2\cdot 2\cdots 2}_{n-veces}$

Demostración: (Por inducción sobre $|X|$)

Base de inducción: Si $|X|=0$, entonces $X=\emptyset$ y así, $\mathcal{P}(X)=\set{\emptyset}$, por lo que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}=2^0=1$.

Hipótesis de inducción: Supongamos que si $X$ es finito tal que $|X|=n$, entonces $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|= 2^{|X|}$.

Paso inductivo: Sea $X$ un conjunto finito tal que $|X|=n+1$. Supongamos que $X=\set{X_1,X_2, \dots, X_n, X_{n+1}}$. Luego, consideremos $X’=X\setminus \set{X_1}$, entonces $|X’|=n$ y así, $|\mathcal{P}(X’)|=2^{|X’|}$. Veamos que $\mathcal{P}(X)$ es finito y $|\mathcal{P}(X)|=2^{|X|}$, para ello veamos primero que $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Procederemos por doble contención.

$\subseteq$) Sea $Y\in \mathcal{P}(X)$, entonces $Y\subseteq X$. Si $X_1\in Y$, entonces $Y\in \set{Z\in \mathcal{P}(X): X_1\in Z}$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Si $X_1\notin Y$, entonces $Y\subseteq X\setminus \set{X_1}=X’$, por lo que $Y\in \mathcal{P}(X’)$ y por lo tanto, $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Concluimos que $\mathcal{P}(X)\subseteq \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

$\supseteq$) Sea $Y\in \mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X): X_1\in Z}$.

Caso 1: Si $Y\in \mathcal{P}(X’)$, entonces $Y\subseteq X’$ y como $X’\subseteq X$, entonces $Y\subseteq X$ y así, $Y\in \mathcal{P}(X)$.

Caso 2: Si $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$, entonces $Y\in \mathcal{P}(X)$.

Por lo tanto, $\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}\subseteq \mathcal{P}(X)$.

Así, $\mathcal{P}(X)=\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X):X_1\in Z}$.

Luego, por hipótesis de inducción tenemos que $\mathcal{P}(X’)$ es finito y $|\mathcal{P}(X’)|=2^n$.

Además, $\set{Z\in \mathcal{P}(X)}$ es finito, más aún, $|\set{Z\in \mathcal{P}(X):X_1\in Z}|=|\mathcal{P}(X’)|$. Para probar este último hecho estableceremos una biyección entre $\mathcal{P}(X’)$ y $\set{Z\in \mathcal{P}(X):X_1\in Z}$.

Consideremos $f:\mathcal{P}(X’)\to \set{Z\in \mathcal{P}(X):X_1\in Z}$ dada por $f(Y)=Y\cup \set{X_1}$. Veamos que $f$ es biyectiva.

Inyectividad: Sean $A,B\in \mathcal{P}(X’)$ tales que $f(A)=f(B)$, esto es $A\cup \set{X_1}=B\cup \set{X_1}$. Luego, $A$ y $\set{X_1}$ son ajenos pues $A\subseteq X’=X\setminus \set{X_1}$; asimismo, $B$ y $\set{X_1}$ son ajenos pues $B\subseteq X’=X\setminus \set{X_1}$. De este modo, debe ocurrir que $A=B$. Por lo tanto, $f$ es inyectiva.

Sobreyectividad: Sea $Y\in \set{Z\in \mathcal{P}(X):X_1\in Z}$. Entonces $Y\subseteq X$ y $X_1\in Y$.

Veamos que existe $W\subseteq X\setminus \set{X_1}$ tal que $f(W)=Y$. Consideremos $W=Y\setminus \set{X_1}$, tenemos que $f(W)=(Y\setminus \set{X_1})\cup \set{X_1}=Y$. Por lo tanto, $f$ es sobreyectiva.

Así, $f$ es biyectiva y $|\set{Z\in \mathcal{P}(X): X_1\in Z}|=2^n$.

Por lo tanto, $|\mathcal{P}(X)|=|\mathcal{P}(X’)\cup \set{Z\in \mathcal{P}(X)}|= 2^n+2^n=2(2^n)= 2^{n+1}$. Lo que concluye nuestra prueba.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección:

  • Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
  • Si $A$ y $B$ son conjuntos finitos y ajenos, muestra que $A\cup B$ es finito y $|A\cup B|=|A|+|B|$.
  • Demuestra que si $A\subseteq B$ y $B$ es finito, entonces $|B|=|B\setminus A|+|A|$.
  • Demuestra que si $A$ y $B$ son cualesquiera conjuntos finitos, entonces $|A\cup B|+|A\cap B|=|A|+|B|$.

Más adelante

En la siguiente sección abordaremos a los conjuntos infinitos, esto nos acercara a preguntarnos sobre la cardinalidad de dichos conjuntos.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Conjuntos finitos

Siguiente entrada: Conjuntos infinitos

Teoría de los Conjuntos I: Conjuntos finitos

Por Gabriela Hernández Aguilar

Deja un comentario

Introducción

Ahora que sabemos el concepto de equipotencia, en esta sección veremos a los conjuntos finitos, los cuales podremos contar según el número natural al que sean equipotentes. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.

Concepto

Definición: Sea $X$ un conjunto. Decimos que $X$ es un conjunto finito si y sólo si existe $n\in \mathbb{N}$ tal que $X\sim n$.

Ejemplo:

El conjunto $\emptyset$ es finito, pues existe una biyección entre el conjunto $\emptyset$ y $0$; a saber, la función vacía.

$\square$

Ejemplo:

El conjunto $A=\set{2,4,6,8, 10}$ es finito pues $f:A\to 5=\set{0,1,2,3,4}$ definida por medio de $f=\set{(2,0), (4,1), (6,2), (8,3), (10, 4)}$ es una función biyectiva.

$\square$

Es conveniente añadir la siguiente notación para conjuntos finitos, pues hará más fluida la escritura.

Definición: Sea $X$ un conjunto finito y $n\in\mathbb{N}$ tal que $X\sim n$. Definimos el cardinal de $X$ como el número natural al cual $X$ es equipotente, y lo denotaremos por medio del símbolo $|X|$; esto es, $|X|:=n$.

Lema: Si $X$ es finito y $y\notin X$, entonces $X\cup\set{y}$ es finito y $|X\cup \set{y}|= |X|+1$.

Demostración:

Sea $X$ finito tal que $|X|=n$, entonces existe $f:n\to X$ tal que $f$ es biyectiva.

Definimos $f’:s(n)\to X\cup \set{y}$ como

$f'(x)= \left\{ \begin{array}{lcc}
             f(x) &   si  & x \in n \\
             \\ y&  si & x=n \\
             \end{array}
   \right.$

Tenemos que $f$ es biyectiva.

En efecto, primero veamos que $f$ es inyectiva. Sean $x_1, x_2\in s(n)$ tales que $f'(x_1)=f'(x_2)$.

Caso 1: Si $x_1\in n$ y $x_2\in n$, entonces $f(x_1)=f'(x_1)=f'(x_2)=f(x_2)$. Como $f$ es inyectiva, entonces $x_1=x_2$.

Caso 2: Si $x_1= n$ y $x_2= n$, entonces $x_1=x_2$.

No ocurre que $x_1\in n$ y $x_2=n$ pues $f'(x_1)=f(x_1)\in X$ y $f'(x_2)=y\notin X$. De manera análoga, no ocurre que $x_1=n$ y $x_2\in n$.

Por lo tanto, $f’$ es inyectiva.

Veamos ahora que $f’$ es sobreyectiva.

Sea $w\in X\cup \set{y}$. Veamos que existe $x\in s(n)$ tal que $f'(x)=w$.

Caso 1: Si $w\in X$, entonces existe $x\in n$ tal que $f(x)=w$, pues $f:n\to X$ es una función sobreyectiva, así que existe $x\in s(n)$ tal que $f'(x)=f(x)=w$.

Caso 2: Si $w=y$, entonces tomamos al elemento $n\in s(n)$ y se tiene que $f'(n)=w$.

De los casos 1 y 2, concluimos que $f’$ es sobreyectiva.

Por lo tanto, $f’$ es biyectiva y así $X\cup\set{y}$ es finito; más aún, $X\cup\set{y}\sim s(n)$, es decir, $|X\cup \set{y}|=s(n)=n+1=|X|+1$.

$\square$

Teorema: Sean $X$ y $Y$ conjuntos finitos, entonces $X\cup Y$ es finito. Más aún, $|X\cup Y|\leq |X|+|Y|$.

Demostración: (Por inducción sobre $|Y|$.

Base de inducción: Si $|Y|=0$, entonces $Y=\emptyset$, así $X\cup Y=X\cup \emptyset=X$ y por lo tanto, $|X\cup Y|=|X|=|X|+0=|X|+|\emptyset|$.

Hipótesis de inducción: Ahora supongamos que si $X$ y $Y$ son finitos tales que $|X|=m$ y $|Y|=n$, entonces $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$.

Paso inductivo: Veamos que si $|Y|=n+1$, entonces $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$. Si para todo $y\in Y$, $y\in X$, entonces $Y\subseteq X$, por lo que $X\cup Y=X$ y, por tanto, $X\cup Y$ es finito; además, como $n\leq n+t$ para cualesquiera naturales $n$ y $t$, entonces $|X\cup Y|=|X|\leq |X|+|Y|$.

Supongamos ahora que existe $y\in Y\setminus X$. Luego, sea $Y’=Y\setminus \set{y}$. Tenemos que $|Y’|=n$ por lo que, por hipótesis de inducción, se tiene que $X\cup Y’$ es finito y $|X\cup Y’|\leq |X|+|Y’|$.

Luego, dado que $y\notin Y’$ y $y\notin X$, entonces, $y\notin X\cup Y’$, y así por el lema anterior, tenemos que $(X\cup Y’)\cup\set{y}$ es finito y

\begin{align*}
|(X\cup Y’)\cup \set{y}|&=|X\cup Y’|+1\\
&\leq |X|+|Y’|+1\\
&=|X|+n+1=|X|+|Y|.
\end{align*}

Por lo tanto, $X\cup Y$ es finito y $|X\cup Y|\leq |X|+|Y|$, siempre que $X$ y $Y$ son conjuntos finitos.

$\square$

Teorema: Si $\mathcal{F}$ es finito y para cualquier $X\in \mathcal{F}$, $X$ es finito. Entonces $\bigcup\mathcal{F}$ es finito.

Demostración: (Por inducción sobre la cardinalidad de $\mathcal{F}$).

Base de inducción: Si $|\mathcal{F}|=0$, entonces $\mathcal{F}=\emptyset$. Así, se cumple por vacuidad, que si cualquier $X\in \mathcal{F}$ es finito, entonces $\bigcup \mathcal{F}$ es finito. Más aún, $\bigcup \mathcal{F}=\emptyset$ y $|\bigcup \mathcal{F}|=0$.

Hipótesis de inducción: Supongamos que si $|\mathcal{F}|=n$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, se cumple que $\bigcup\mathcal{F}$ es finito.

Paso inductivo: Veamos que si $|\mathcal{F}|=n+1$ y para cualquier $X\in \mathcal{F}$, $X$ es finito, entonces $\bigcup\mathcal{F}$ es finito.

Sea $X\in\mathcal{F}$ y definamos $\mathcal{F’}:=\mathcal{F}\setminus X$. Tenemos que cualquier elemento de $\mathcal{F’}$ es finito y que $|\mathcal{F}’|=n$, por lo que por hipótesis de inducción se cumple que $\bigcup\mathcal{F’}$ es finito.

Ahora, por el lema, tenemos que $\bigcup\mathcal{F}’\cup X$ es finito.

Afirmación: $\bigcup\mathcal{F}=\bigcup\mathcal{F}’\cup X$.

Demostración de la afirmación:

Sea $x\in\bigcup \mathcal{F}$, entonces existe $Y\in \mathcal{F}$ tal que $x\in Y$.

Caso 1: Si $Y=X$, entonces $x\in X$ y por lo tanto, $x\in \bigcup\mathcal{F}’\cup X$.

Caso 2: Si $Y\not=X$, entonces $Y\in \mathcal{F}’$ y así, $x\in \bigcup\mathcal{F}’$, lo cual implica que $\bigcup\mathcal{F}\subseteq \bigcup\mathcal{F}’\cup X$.

Ahora, como $\mathcal{F’}\subseteq\mathcal{F}$ y $X\in\mathcal{F}$, entonces $\bigcup\mathcal{F’}\cup X\subseteq\mathcal{F}$.

Así, $\bigcup \mathcal{F}=\bigcup\mathcal{F}’\cup X$. Por lo tanto, $\bigcup\mathcal{F}$ es finito. Lo que concluye nuestra prueba.

$\square$

,

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección.

  • Sea $X$ un conjunto finito y $x\in X$. Si $|X|=n+1$, demuestra que $X\setminus\set{x}$ es finito y que $|X\setminus\set{x}|=n$.
  • Prueba que si $X$ y $Y$ son conjuntos finitos, entonces $X\cap Y$ también es finito.
  • Si $A$ y $B$ son conjuntos finitos, prueba que $A\setminus B$ también es finito.

Más adelante

En la siguiente entrada continuaremos con el contenido de esta sección, probaremos más propiedades sobre los conjuntos finitos y a su vez hablaremos acerca de la cardinalidad del conjunto potencia.

Enlaces

Entrada anterior: Teoría de los Conjuntos I: Equipotencia

Siguiente entrada: Conjuntos finitos (parte II)