Archivo de la etiqueta: matriz

Investigación de Operaciones: Forma canónica y forma estándar de un problema lineal

Por Aldo Romero

Deja un comentario

Introducción

En las entradas anteriores hemos dado ejemplos de varios problemas de aplicación que pueden ser planteados mediante un problema de programación lineal. Una vez que llegamos a un modelo, se pueden tener restricciones de los tipos $\leq$, $=$ y $\geq$. Además, puede haber restricciones de signo sobre las variables. Puede que se les pida ser no positivas, no negativas o irrestrictas (no restringidas) en signo. Lo que haremos ahora es ver cómo podemos llegar a un cierto formato (forma estándar o forma canónica).

Forma canónica de un problema lineal

A continuación introducimos el primer formato que nos facilitará el trabajo.

Definición. Se dice que un problema de programación lineal está en forma canónica si cumple simultáneamente las siguientes tres propiedades:

  1. El problema es de maximización.
  2. Las restricciones del problema son todas del tipo $\leq$ (menor o igual).
  3. Las variables de decisión son no negativas.

Así, tenemos entonces que un problema en forma canónica se ve como sigue:

\begin{align*}
Max \quad z &= c_1x_1+\ldots+c_nx_n\\
s.a.&\\
&\left\{\begin{matrix} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n \leq b_1\\
a_{21}x_1+a_{22}x_2+\ldots + a_{2n}x_n \leq b_2\\
\vdots \\
a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n\leq b_n. \\
x_1\geq 0, x_2\geq 0, \ldots, x_n\geq 0.\end{matrix}\right.
\end{align*}

En términos matriciales, esto podemos reescribirlo de manera mucho más compacta como sigue:

\begin{align*}
Max \quad z &= c\cdot x\\
s.a.&\\
Ax &\leq b\\
x &\geq 0,\\
\end{align*}

en donde:

  • $c=(c_1,\ldots,c_n)\in \mathbb R^n$ es el vector de costos (vector renglón)
  • $x = (x_1,\ldots,x_n)\in \mathbb R^n$ es el vector de variables de decisión (vector columna),
  • $A=[a_{ij}]$ es la matriz de restricciones, que es una matriz de $m \times n$ y
  • $b=(b_1,\ldots,b_m) \in \mathbb R^m$ es el vector de constantes que acotan las combinaciones lineales de variables.

Todo problema de programación lineal puede ser expresado en forma canónica; es decir, puede definirse un problema en forma canónica equivalente a él. En efecto:

  • Si el problema es de minimización, puede considerarse en vez de $z$ la función $z’ = -z$ y en el problema equivalente se busca maximizar $z’$.
  • Si una restricción es del tipo $\geq$ puede ser mutiplicada por -1 para obtener una del tipo $\leq$.
  • Una ecuación puede ser substituida por una desigualdad del tipo $\leq$ y otra del tipo $\geq$. Luego, la del tipo $\geq$ puede ser substituida por una del tipo $\leq$ como en el punto anterior.
  • Para una variable $x_i\leq 0$ puede definirse $x_i’ = -x_i$, resultando $x_i’ \geq 0$. Claramente hay una biyección entre elegir el valor de $x_i$ y $x_i’$.
  • Para una $x_i$ no restringida pueden ser definidas dos variables no negativas $x_i’$ y $x_i^\ast$ tales que $x_i’-x_i^\ast = x_i$. Para cualquier $x_i$ dado podemos construir dichas variables, y viceversa, para $x_i’$ y $x_i^\ast$ se puede construir $x_i$.

Ejemplo de pasar un problema a forma canónica

Transformaremos el siguiente modelo a su forma canónica
\begin{align*}
Min \quad z &= x_1-3x_2+7x_3\\
&s.a.\\
3x_1+&x_2+3x_3 &\leq 40\\
x_1+&9x_2-7x_3 &\geq 50\\
5x_1+&3x_2 &= 20\\
&5x_2 + 8x_3 &\leq 80\\
x_1, x_2 &\geq 0, \quad x_3 \quad libre.\\
\end{align*}

Primeramente se definen las variables no negativas $x_3’$ y $x_3^{\ast}$, tales que $x’_3-x_3^{\ast} = x_3$, con objeto de satisfacer el punto (3) de la definición. Para satisfacer el punto (1) se considera la función:
\begin{align*}
z’ &= -z \\&= -x_1+3x_2-7x_3\\&=-x_1+3 x_2-7 x’_3+7x_3^{\ast}
\end{align*}

y se busca maximiza ésta (equivalente a minimizar $z$). Finalmente se realizan cambios en las restricciones para satisfacer el punto (2). La primera y cuarta desigualdad cumplen con la definición por lo que no se modifican (más allá de la sustitución de $x_3$ por $x’_3-x_3^{\ast}$); la segunda desigualdad se multiplica por $-1$ para obtener una del tipo $\leq$: $$ x_1 + 9x_2 – 7x_3 \geq 50 \quad \Leftrightarrow \quad -x_1 – 9x_2 + 7x_3 \leq -50.$$

Substituyendo las nuevas variables se obtiene: $$-x_1-9x_2+7x’_3-7x_3^{\ast}\leq -50.$$

Para la tercera desigualdad se tiene lo siguiente:

\begin{align*}
5x_1+3x_2 &= 20\\
&\Leftrightarrow\\
5x_1 + 3x_2 \leq 20 \quad& y \quad 5x_1 + 3x_2 \geq 20\\
&\Leftrightarrow\\
5x_1 + 3x_2 \leq 20 \quad& y \quad -5x_1 – 3x_2 \leq -20.\\
\end{align*}

Finalmente el problema queda expresado en forma canónica como:

\begin{align*}
Max \quad z’ &= -x_1+3x_2-7x’_3+7x_3^{\ast}\\
&s.a.\\
3x_1+&x_2+3x’_3-3x_3^{\ast} &\leq 40\\
-x_1-&9x_2+7x’_3-7x_3^{\ast} &\leq -50\\
5x_1+&3x_2 &\leq 20\\
-5x_1-&3x_2 &\leq -20\\
&5x_2+8x’_3-8x_3^{\ast} &\leq 80\\
x_1, x_2&, x’_3, x_3^{\ast} \geq 0.\\
\end{align*}

Forma estándar de un problema lineal

Definición. Se dice que un problema de programación lineal está en forma estándar si

  1. Todas las restricciones son ecuaciones.
  2. Todas las variables son no negativas.
  3. La función objetivo puede pedirse que se optimice maximizándola, o minimizándola.

De esta manera, un problema en forma estándar se ve como sigue:

\begin{align*}
Max\, (\text{o } Min) \quad z &= c_1x_1+\ldots+c_nx_n\\
s.a.&\\
&\left\{\begin{matrix} a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1\\
a_{21}x_1+a_{22}x_2+\ldots + a_{2n}x_n = b_2\\
\vdots \\
a_{m1}x_1+a_{m2}x_2+\ldots+a_{mn}x_n= b_n\\
x_1\geq 0, x_2\geq 0, \ldots, x_n\geq 0.
\end{matrix}\right.\\
\end{align*}

En notación matricial, el problema en forma canónica queda expresado de la siguiente manera:

\begin{align*}
Max\, (\text{o } Min) \quad z &= cx\\
&s.a.\\
Ax &= b\\
x &\geq 0\\
\end{align*}

en donde $c, x, A$ y $b \geq 0$ son como se mencionó antes.

Así como cualquier problema de programación lineal puede ser expresado en forma canónica, también cualquier problema de programación lineal puede expresarse en forma estándar. Una restricción del tipo $\leq$ ($\geq$) puede ser transformada en una ecuación sumando (o restando) una variable no negativa que recibe el nombre de variable de holgura.

Ejemplo de pasar un problema a forma estándar

Retomemos el problema ejemplo anterior, antes de expresarlo en forma canónica.

\begin{align*}
Min \quad z &= x_1-3x_2+7x_3\\
&s.a.\\
3x_1+&x_2+3x_3 &\leq 40\\
x_1+&9x_2-7x_3 &\geq 50\\
5x_1+&3x_2 &= 20\\
&5x_2 + 8x_3 &\leq 80\\
x_1, x_2 &\geq 0, \quad x_3 \quad libre.\\
\end{align*}

Vamos a expresarlo ahora en forma estándar. Como lo hicimos anteriormente, hacemos la sustitución $x=x’_3-x_3^\ast$ para que la variable libre se convierta en dos con restricciones de ser no negativas.

Para satisfacer (1) se introducen las variables de holgura, $x_4$, $x_5$ y $x_6$ que pediremos que sean no negativas. A la primera desigualdad le sumamos $x_4$. A la quinta le sumamos $x_6$. Y finalment, a la segunda le restamos $x_5$. Esto transforma las desigualdades en igualdades. De esta manera, el problema queda expresado de la siguiente manera:

\begin{align*}
Min \quad z &= x_1 – 3x_2+7x’_3-7x_3^\ast\\
&s.a.\\
3x_1 + &x_2 + 3x’_3 – 3x_3^\ast + x_4 &= 40\\
x_1 + &9x_2 – 7x’_3 + 7x_3^\ast – x_5 &= 50\\
5x_1 + &3x_2 &= 20\\
&5x_2 + 8x’_3 – 8x_3^\ast + x_6 &= 80\\
x_1,&x_2,x’_3,x_3^\ast,x_4,x_5,x_6 \geq 0.\\
\end{align*}

Más adelante…

Las formas que estudiamos en esta entrada nos ayudarán posteriormente para plantear soluciones para problemas de programación lineal.

Mientras tanto, en la siguiente entrada hablaremos de algunos otros conceptos relativos a la teoría de problemas lineales y posibles propiedades que puede tener una asignación de variables. Diremos qué es una solución básica, una solución factible y un punto extremo para un problema lineal.

Tarea moral

  1. ¿Cuál sería la forma estándar del problema de maximizar $x+y$ sujeto a $x-y\leq 8$ y $y\leq 0$? ¿Y su forma canónica?
  2. Transforma el siguiente problema de programación lineal a su forma canónica y a su forma estándar:
    \begin{align*}
    Max \quad z &= -2x_1 + 3x_2 – 2x_3\\
    &s.a.\\
    4x_1 – &x_2 – 5x_3 &= 10\\
    2x_1 + &3x_2 + 2x_3 &\geq 12\\
    x_1 &\geq 0, \quad x_2, x_3 \quad irrestrictas\\
    \end{align*}
  3. Revisa nuevamente las entradas anteriores y encuentra las formas canónicas y formas estándar de los problemas que hemos planteado hasta ahora.
  4. La forma estándar (o bien la forma canónica) de un programa lineal «es equivalente» al problema original. Justifica esta afirmación formalmente. Es decir, explica por qué una solución $x_1,\ldots,x_n$ que optimiza el problema original está asociada a una solución de su forma estándar (o canónica) y viceversa.
  5. Imagina que tenemos un sistema de ecuaciones de la forma $Ax=B$ con $A$ matriz en $M_{m,n}(\mathbb{R})$ y $b$ vector en $\mathbb{R}^m$. Queremos encontrar de todas las posibles soluciones al sistema aquella que minimiza la suma de las entradas de $x$. Plantea esto como un problema lineal y transfórmalo a su forma canónica y a su forma estándar.

Entradas relacionadas

Álgebra Lineal II: Adjunta de una transformación lineal

Por Ayax Calderón

5 respuestas

Introducción

En esta tercera unidad estudiaremos algunos aspectos geométricos de transformaciones lineales. Para ello, lo primero que haremos será introducir la noción de la adjunta de una transformación lineal. Esto nos permitirá más adelante poder hablar de varias transformaciones especiales: normales, simétricas, antisimétricas, ortogonales. De entrada, las definiciones para cada uno de estos conceptos parecerán simplemente un juego algebraico. Sin embargo, poco a poco descubriremos que pidiendo a las transformaciones lineales cierta propiedad con respecto a su adjunta, podemos recuperar muchas propiedades geométricas bonitas que satisfacen.

Un ejemplo de esto serán las transformaciones ortogonales. Estas serán las transformaciones que, a grandes rasgos, no cambian la norma. Daremos un teorema de clasificación para este tipo de transformaciones: veremos que sólo son reflexiones o rotaciones en ciertos ejes. Después estudiaremos las transformaciones simétricas y veremos un resultado fantástico: el teorema espectral. Este teorema nos garantizará que toda transformación simétrica en $\mathbb{R}$ puede ser diagonalizada, y de hecho a través de una transformación ortogonal.

El párrafo anterior nos dice que las transformaciones ortogonales y las simétricas serán «fáciles de entender» en algún sentido. Esto parece limitado a unas familias muy particulares de transformaciones. Sin embargo, cerraremos la unidad con un teorema muy importante: el teorema de descomposición polar. Gracias a él lograremos entender lo que hace cualquier transformación lineal. Tenemos un camino muy interesante por recorrer. Comencemos entonces con la idea de la adjunta de una transformación lineal.

La adjunta de una transformación lineal

Sea $V$ un espacio euclidiano y producto interior $\langle \cdot, \cdot \rangle$. Tomemos una transformación lineal $T:V \to V$. Para cada $y\in V$, la transformación $x\mapsto \langle T(x),y\rangle$ es una forma lineal. Del teorema de representación de Riesz se sigue que existe un único vector $T^*(y)\in V$ tal que
$$\langle T(x),y\rangle=\langle T^*(y),x\rangle =\langle x, T^*(y)\rangle \hspace{2mm} \forall x\in V.$$

Esta asignación de este vector $T^\ast$ es lineal, ya que al vector $ry_1+y_2$ para $r$ escalar y $y_1,y_2$ en $V$ se le asigna la forma lineal $x\mapsto \langle T(x),ry_1+y_2\rangle=r\langle(T(x),y_1\rangle + \langle (T(x),y_2)$, que se puede verificar que le corresponde en la representación de Riesz el vector $rT^\ast(y_1)+T^\ast(y_2)$.

De esta manera, podemos correctamente enunciar la siguiente definición.

Definición. Sea $V$ un espacio euclidiano y producto interior $\langle \cdot, \cdot \rangle$. Sea $T:V\to V$ una transformación lineal. Definimos a la adjunta de $T$, como la única transformación lineal $T^\ast:V\to V$ que cumple la siguiente condición para todos $x,y$ en $V$:

$$\langle T(x),y\rangle =\langle x, T^*(y)\rangle$$

Notemos que para cualesquiera $x,y\in V$ tenemos que
$$\langle y,T(x)\rangle=\langle T(x),y\rangle=\langle x,T^* (y)\rangle=\langle T^*(y),x\rangle =\langle y, (T^*)^*(x)\rangle.$$

Restando el último término del primero, se sigue que $T(x)-(T^*)^*(x)=0$, de manera que $$(T^*)^*=T,$$ por lo cual simplemente escribiremos $$T^{**}=T.$$

Por lo tanto, la asignación $T\mapsto T^*$ es una transformación auto-inversa sobre $V$.

La matriz de la transformación adjunta

Tenemos que $T^{**}=T$. Esto debería recordarnos a la transposición de matrices. En efecto, en cierto sentido podemos pensar a la transformación $T^\ast$ algo así como la transpuesta de la transformación (por lo menos en el caso real, para espacios sobre $\mathbb{C}$ será algo ligeramente distinto).

La siguiente proposición nos ayudará a reforzar esta intuición.

Proposición. Sea $V$ un espacio euclidiano y producto interior $\langle \cdot, \cdot \rangle$ y $T:V\to V$ una transformación lineal. Sea $\mathcal{B}=(e_1,\dots, e_n)$ una base otronormal de $V$. Se tiene que $$\text{Mat}_{\mathcal{B}}(T^\ast)={}^t\text{Mat}_{\mathcal{B}}(T).$$

En palabras, bajo una base ortonormal, la adjunta de una transformación tiene como matriz a la transpuesta de la transformación original.

Solución. Sea $A=\text{Mat}_{\mathcal{B}}(T)$ y $B=[B_{ij}]$ la matriz asociada a $T^*$ con respecto a $\mathcal{B}$. Para cada $i\in\{1,\ldots,n\}$ se tiene
$$T^*(e_i)=\displaystyle\sum_{k=1}^n b_{ki}e_k.$$

En vista de que $$T(e_i)=\displaystyle\sum _{k=1}^n a_{ki}e_k$$ y de que la base $\mathcal{B}$ es ortonormal, se tiene que $$\langle T(e_i),e_j\rangle=\displaystyle\sum_{k=1}^n a_{ki}\langle e_k,e_j\rangle=a_{ji}$$ y
$$\langle e_i,T^*(e_j)\rangle=\displaystyle\sum_{k=1}^n b_{kj}\langle e_i,e_k \rangle = b_{ij}.$$

Como, por definición de transformación adjunta, se tiene que
$$\langle T(e_i),e_j\rangle =\langle e_i, T^*(e_j)\rangle,$$ entonces $b_{ij}=a_{ji}$ para cada $i,j$ en $\{1,\ldots, n\}$, que precisamente significa que $B= {}^tA$.

$\square$

Ejemplos de encontrar una adjunción

La proposición de la sección anterior nos da una manera práctica de encontrar la adjunción para transformaciones lineales.

Ejemplo. Encontraremos la transformación adjunta a la transformación lineal $T:\mathbb{R}^2\to \mathbb{R}^2$ dada por $T((x,y))=(y-x,y+2x)$. Por la proposición de la sección anterior, basta expresar a $T$ en una base ortonormal y transponer. Usemos la base canónica de $\mathbb{R}^2$. En esta base, la matriz que representa a $T$ es $\begin{pmatrix} -1 & 1 \\ 2 & 1 \end{pmatrix}$. Por ello, la matriz que representa a $T^\ast$ es la transpuesta, es decir $\begin{pmatrix} -1 & 2 \\ 1 & 1 \end{pmatrix}$. De este modo, concluimos que $T^\ast((x,y)) = (-x+2y,x+y)$.

Podemos verificar que en efecto esta transformación satisface la definición de adjunción. Por un lado,

$$\langle T((a,b)), (c,d) \rangle = (b-a,b+2a)\cdot (c,d)= bc-ac+bd+2ad,$$

y por otro

$$ \langle (a,b), T((c,d)) \rangle = (a,b) \cdot (-c+2d,c+d) = -ac +2ad + bc +bd.$$

Ambas expresiones en efecto son iguales.

$\triangle$

Problema. Demuestra que una transformación lineal $T$ en un espacio euclideano de dimensión finita y la adjunta $T^\ast$ de $T$ tienen el mismo determinante.

Solución. El determinante de una transformación es igual al determinante de cualquiera de las matrices que la represente. Así, si $A$ es la forma matricial de $T$ bajo una base ortonormal, se tiene que $\det(A)=\det(T)$. Por la proposición de la sección anterior, $^tA$ es la forma matricial de $T^\ast$ en esa misma base, de modo que $\det({}^tA)=\det(T^\ast)$. Pero una matriz y su transpuesta tienen el mismo determinante, de modo que $$\det(T^\ast)=\det({}^tA)=\det(A)=\det(T).$$

$\square$

Más adelante…

La noción de transformación adjunta es nuestra primera noción fundamental para poder definir más adelante transformaciones que cumplen propiedades geométricas especiales. Con ella, en la siguiente entrada hablaremos de transformaciones simétricas, antisimétricas y normales.

Toma en cuenta que las definiciones que hemos dado hasta ahora son para espacios euclideanos, es decir, para el caso real. Cuando hablamos de espacios hermitianos, es decir, del caso complejo, los resultados cambian un poco. La transformación adjunta se define igual. Pero, por ejemplo, si la matriz que representa a una transformación es $A$, entonces la que representará a su adjunta no será la transpuesta, sino más bien la transpuesta conjugada.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más a profundidad la teoría vista.

  1. Encuentra la transformación adjunta para las siguientes tranformaciones lineales:
    • $T:\mathbb{R}^2\to \mathbb{R}^2 $ dada por $T(x,y)=(2y-x,2x+y)$.
    • $T:\mathbb{R}^3\to \mathbb{R}^3$ dada por $T(x,y,z)=(x+y+z,y+z,z)$.
    • $T:\mathbb{R}^n \to \mathbb{R}^n$ tal que para la base canónica $e_1,\ldots,e_n$ cumple que $T(e_i)=e_{i+1}$ para $i=1,\ldots,n-1$ y $T(e_n)=0$.
  2. Considera el espacio vectorial $M_n(\mathbb{R})$. En este espacio, la operación transponer es una transformación lineal. ¿Cuál es su tranformación adjunta?
  3. Completa los detalles de que $T^\ast$ es en efecto una transformación lineal.
  4. Demuestra que si $T$ es una transformación lineal sobre un espacio euclidiano y $\lambda$ es un eigenvalor de $T$, entonces $\lambda$ también es un eigenvalor de $T^\ast$. De manera más general, demuestra que $T$ y $T^\ast$ tienen el mismo polinomio característico.
  5. Sea $V$ un espacio euclidiano y $T:V\to V$. ¿Es cierto que para todo polinomio $p$ se cumple que $p(T)^\ast=p(T^\ast)$?

Entradas relacionadas