Archivo de la etiqueta: equivalencias

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

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 Superior I: Condicionales y dobles condicionales

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

Hemos hablado en las últimas entradas de tres conectores muy importantes: la negación, la conjunción y la disyunción. Sin embargo, como recordarás en la introducción al tema, mencionamos más de tres conectores. Ha llegado el momento en que veamos a los dos conectores restantes: la implicación y la doble implicación.

Pensar en consecuencias

Para introducir mejor la implicación, pensemos en qué significa la palabra sin algún contexto matemático. ¿Qué se te viene a la mente cuando oyes la palabra «implicación»? Quizá se te venga a la mente «consecuencia», que a su vez significa cosas o acciones que derivan otras más.

Un ejemplo es el siguiente: ¿qué implicación tiene que se acabe la pila de un celular? Pues en principio se apaga el teléfono. Entonces podríamos decir «Si se acaba la pila del celular entonces se apagará». Otro ejemplo: ¿qué consecuencias tiene llegar tarde a una cita médica? Pues muy probablemente se cancelará. Esto mismo lo podemos decir así: «Si llego tarde a una cita médica entonces la cancelarán». Un último ejemplo sería el siguiente: «Si sube el nivel de dióxido de carbono en la atmósfera entonces los polos se derretirán».

Todas estas oraciones son ejemplos de condicionales, y para entender su estructura, volvamos al primer ejemplo. Pensemos en las proposiciones
\begin{align*}
P &= \text{El celular se queda sin pila.}\\
Q &= \text{El celular se apaga.}
\end{align*}

Podemos reescribir la oración «Si se acaba la pila del celular entonces se apagará» como «Si pasa $P$ entonces pasa $Q$». Observa que siempre que pase $P$, entonces pasará $Q$. Esto lo escribiremos como $P \Rightarrow Q$ y se lee «$P$ implica $Q$». Lo que estamos diciendo con esta oración es que si el valor de verdad de $P$ es verdadero entonces el valor de verdad de $Q$ es verdadero.

Observa que si al celular no se le acaba la pila, entonces no tendría porqué apagarse, entonces si $P$ es falso, $Q$ puede ser falso y no hay problema. También puede pasar que apagues el celular, pero no necesariamente sea porque se le acabó la pila, entonces si $P$ es falso, $Q$ también puede ser verdadero y no hay algún problema con ello. El único problema sería decir que se le acabó la pila al celular y sigue prendido, eso sería algo que no puede suceder, porque sabemos que «Si se acaba la pila del celular entonces se apagará».

Todo esto lo resumimos en la tabla de verdad de la siguiente sección.

Tabla de verdad de la implicación

$P$$Q$$P \Rightarrow Q$
$0$$0$$1$ 
$0$$1$$1$ 
$1$$0$ $0$
$1$$1$ $1$

Quizá sigas teniendo dificultades para entender porqué si $P$ es falso, $Q$ puede tener cualquier valor y seguir haciendo la expresión verdadera. Para ello, piensa en lo siguiente: lo que dice la implicación es que siempre que pase la primera condición $P$, también llamada hipótesis, ocurrirá $Q$, también conocida como tesis. Puede ser que se cumpla $Q$ y no se cumpla $P$, pero eso no contradice lo que dice la implicación, o puede que igual no se cumpla ni $Q$ ni $P$. Lo único que nos dice la implicación es que siempre que se cumpla $P$ va a tener como consecuencia que se cumpla $Q$. Entonces el único caso en donde desobedecemos a la implicación (donde es falsa), es cuando pasa $P$ y no pasa $Q$, que corresponde al penúltimo renglón de la tabla de verdad.

Condiciones suficientes y necesarias

El siguiente y último conector que vamos a ver es la doble implicación. A diferencia de la implicación, asumimos que para que una proposición sea verdadera, es necesaria que la otra también y viceversa. Para esto, refiramos a la doble implicación como una equivalencia lógica $P \Leftrightarrow Q = (P \Rightarrow Q) \land (Q \Rightarrow P)$. En otras palabras decimos que hay una doble implicación entre $P$ y $Q$ si $P$ implica $Q$ y además $Q$ implica $P$.

Además de este nombre, algunas formas de referirse a la doble implicación que encontrarás serán:

  • «$P$ es equivalente a $Q$»
  • «Una condición necesaria y suficiente para $Q$ es $P$»
  • «$P$ si y sólo si $Q$»

Esta última se utiliza mucho en enunciados matemáticos como proposiciones y teoremas.

Tabla de verdad de la doble implicación

$P$$Q$$P \Rightarrow Q$$Q \Rightarrow P$$(P \Rightarrow Q) \land (Q \Rightarrow P)$$P\Leftrightarrow Q$
$0$$0$ $1$$1$$1$  $1$ 
$0$$1$$1$ $0$ $0$ $0$ 
$1$$0$  $0$$1$ $0$ $0$
$1$$1$  $1$$1$ $1$   $1$

Nota que la doble implicación es verdad cuando los valores de $P$ y $Q$ son ambos verdaderos o ambos falsos. Esto quiere decir que en este caso si alguno es verdadero, entonces los dos son verdaderos, mientras que si uno es falso, los dos lo serán.

La implicación en términos de otros conectores

El hecho de que hayamos aprendido los primeros tres conectores (negación, conjunción y disyunción) antes que estos no es coincidencia. Resulta que la implicación y la doble implicación se «pueden construir» a partir de los primeros tres. Con esto nos referimos a que la implicación es equivalente a una expresión hecha únicamente por los anteriores.

Para ello, primero recuerda cómo construimos la implicación. La única forma en que la implicación $P \Rightarrow Q$ sea falsa es que $P$ sea verdadero y $Q$ falso. Entonces si $P$ es falso, no importa qué valor tome $Q$. De esta forma, cada vez que $\neg P$ sea verdad, la implicación también será verdadera. Pero si $P$ es verdadero, entonces $Q$ debe serlo también. Eso lo podemos expresar como $\neg P \lor Q$ que quiere decir «$P$ no pasa o $Q$ es verdadero» y coincide con lo que acabamos de decir. Para convencerte de eso, revisa con cuidado la siguiente tabla.

$P$$Q$$\neg P$ $\neg P \lor Q$$P \Rightarrow Q$
$0$$0$ $1$$1$  $1$ 
$0$$1$$1$  $1$ $1$ 
$1$$0$  $0$ $0$ $0$
$1$$1$  $0$ $1$   $1$

Entonces $\neg P \lor Q = P \Rightarrow Q$. Entonces cada vez que digamos que «Una cosa implica la otra», podemos pensarlo como «La negación de la primera cosa o la otra». Siempre es útil regresar a ejemplos concretos. Piensa cuidadosamente por qué es lo mismo decir «si llueve el piso se moja» y decir «no llueve o el piso está seco».

La contrapositiva de una implicación

Una propiedad que más adelante nos servirá sobre la implicación es el hecho de que en ocasiones es más sencillo trabajar con las negaciones de las proposiciones que con las proposiciones normales. No te preocupes si no entiendes a qué nos referimos con esto, más adelante lo veremos con más calma.

Un ejemplo de esto es verificar la siguiente proposición: «Si un número al cuadrado es par, entonces el número es par». A primera vista no es tan fácil verificar directamente esta proposición que es de la forma $P \Rightarrow Q$. Resulta que la forma en que se comprueba esto es con una equivalencia de la implicación. Para llegar a esta equivalencia, como primer paso, notaremos que podemos poner a la implicación en términos de la negación. Para esto, vamos a usar el resultado anterior para encontrar lo que buscamos.

Recordemos que $\neg P \lor Q = P \Rightarrow Q$, y la conjunción es conmutativa, es decir $\neg P \lor Q = Q \lor \neg P$.

¿Podemos ver esto de otra forma?

Pues resulta que sí. Veamos a $Q$ como la negación de la negación de $Q$, dicho de otra forma, $Q = \neg \neg Q$. Esto último nos ayuda a ver la equivalencia de otra forma: $Q \lor \neg P =\neg \neg Q \lor \neg P$. El siguiente paso es pensar a $\neg Q$ como un término por sí mismo y a $\neg P$ como otro término. Dicho de otra forma agrupemos términos para ver la equivalencia de manera distinta: $$Q \lor \neg P =\neg (\neg Q) \lor (\neg P).$$ Ahora, pensemos a $\neg Q$ como una proposición y a $\neg P$ como otra. La expresión está diciendo «La negación de $\neg Q$ una cosa o $\neg P$» ¿Suena familiar? Esto justamente es la equivalencia de la implicación. Dicho de otra manera, fíjate que tenemos una equivalencia:

$$Q \lor \neg P =\neg (\neg Q) \lor (\neg P) = \neg Q \Rightarrow \neg P.$$

Es decir,

$$P \Rightarrow Q = \neg Q \Rightarrow \neg P.$$

Cuando tenemos una implicación de la forma $P\Rightarrow Q$, a la proposición equivalente $\neg Q \Rightarrow \neq P$ le llamamos la contrapositiva.

Regresando al ejemplo inicial de esta sección, la proposición «Si un número al cuadrado es par, entonces el número es par» podemos pensarla como «Si un número es impar entonces su cuadrado es impar», lo cual es mucho más fácil de verificar. En entradas posteriores retomaremos esta forma de pensar. Por lo mientras es suficiente que entiendas que la implicación es equivalente a su contrapositiva.

El caso en donde todo es verdadero

Antes de terminar esta entrada, introduciremos un concepto que resultará útil cuando llegue el momento de estudiar inferencias. Para ello, observa la tabla de verdad de la proposición $((Q \Rightarrow P) \land Q) \Rightarrow P$:

$P$$Q$$Q \Rightarrow P$$Q \Rightarrow P \land Q$$(Q \Rightarrow P \land Q) \Rightarrow P$
$0$$0$ 1 01 
$0$$1$ 0 0 1
$1$$0$ 1 0 1
$1$$1$ 11  1

¿Notas algo peculiar? Toda la columna de nuestra regla de inferencia es verdadera. Esto quiere decir que no importa qué valores tomen nuestras premisas, siempre es verdadera la expresión. A esto en matemáticas le llamamos una tautología.

Sucede algo que une aún más los conceptos de tautología y doble condicional. ¿Recuerdas que las proposiciones $\neg(P \land Q) = \neg P \lor \neg Q$ son equivalentes? Pues veamos ahora sus tablas de verdad:

$P$$Q$$P \land Q$$\neg (P \land Q)$$\neg P$$\neg Q$$\neg P \lor \neg Q$$\neg (P \land Q)\Leftrightarrow (\neg P \lor \neg Q)$
$0$$0$ 01 1111 
$0$$1$ 01 101 1
$1$$0$ 01 011 1
$1$$1$ 10000 1

Hemos agregado una última columna, la correspondiente a $\neg (P \land Q))\Leftrightarrow (\neg P \lor \neg Q)$. ¡Es una tautología! Esto sucede siempre: dos proposiciones o expresiones $P, Q$ son equivalentes siempre que $P \Leftrightarrow Q$ sea una tautología.

Más adelante…

Recuerda el ejemplo que mencionamos anteriormente «Un número al cuadrado es par si el número es par», no especificamos de qué número se trataba, sin embargo hay una infinidad de números los cuales podemos tomar como ejemplo para verificar la propiedad. Entonces podemos decir «$1^2$ es par si $1$ es par» o «$38^2$ es par si $38$ es par», o en general podemos decir «$x^2$ es par si $x$ es par». ¿Pero quién es $x$? ¿Qué valores puede tomar? En la siguiente entrada veremos algo conocido como cuantificadores. Estos ampliarán el poder de las proposiciones introduciendo variables dentro de las proposiciones. Con ello, se puede cambiar el objeto al que se refiere una proposición y, dependiendo de esto, su valor de verdad.

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 la teoría vista.

  1. Escribe las siguientes frases en lógica proposicional:
    • Si hoy es lunes, entonces mañana será viernes.
    • El caos implica el orden.
    • Para que crezcan las plantas, tienes que regarlas.
    • Hoy es lunes si mañana es martes y mañana es martes si hoy es lunes.
    • Hoy es lunes si y sólo si mañana es martes.
  2. Verifica que siempre «Una cosa siempre se implica a sí misma», es decir, verifica que si $P$ es una proposición, entonces $P \Rightarrow P$ siempre es verdadera.
  3. Haz la tabla de verdad de la implicación $P\Rightarrow Q$ y de su contrapositiva $\neg Q \Rightarrow \neg P$ para convencerte de que en verdad son equivalentes.
  4. ¿Cómo verificarías que  $P \Leftrightarrow Q = (\neg Q \lor P)\land(\neg P \lor Q)$? Recuerda que la doble implicación $P \Leftrightarrow Q$ es equivalente a $(P \Rightarrow Q) \land (Q \Rightarrow P)$.
  5. Verifica que la doble condicional es conmutativa, es decir $P \Leftrightarrow Q = Q \Leftrightarrow P $. ¿La condicional es conmutativa?

Entradas relacionadas

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»