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 recordar forma estándar y forma canónica de un problema lineal; y como pasar de un formato a otro.

Forma canónica de un problema lineal

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

1. Las variables de decisión son todas no negativas ($x_i \geq 0$).
2. El problema es de maximización ($Max \quad z = c_1x_1+\ldots+c_nx_n$).
3. Las restricciones del problema son todas del tipo $\leq$ ($a_{i1}x_1+ \ldots + a_{in}x_n \leq b_i$).

Tenemos entonces que un problema en forma canónica se ve de la siguiente manera:

\begin{align*}
Max \quad z &= c_1x_1+\ldots+c_nx_n\\
s.a.&\\
&\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\end{matrix}\\
& x_1\geq 0, x_2\geq 0, \ldots, x_n\geq 0.
\end{align*}

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

\begin{align*}
Max \quad z &= cx^t\\
s.a.&\\
Ax^t &\leq b^t\\
x &\geq \bar 0,\\
\end{align*}

en donde:

• $c=(c_1,\ldots,c_n)\in \mathbb R^n$ es el vector de costos
• $x = (x_1,\ldots,x_n)\in \mathbb R^n$ es el vector de variables de decisión,
• $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,
• Entendemos $\bar{0}$ como el vector en $\mathbb{R}^n$ cuyas entradas son todas cero.

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 el sentido de que la solución de uno nos permite encontrar la solución del otro de manera sencilla. 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 que es negativa ($x_i\leq 0$) puede sustituirse por $x_i’ = -x_i$, resultando $x_i’ \geq 0$. Claramente hay una relación directa entre 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»$ tales que $x_i’-x_i» = x_i$. Para cualquier $x_i$ dado podemos construir dichas variables, y viceversa, para $x_i’$ y $x_i»$ se puede construir $x_i$.

Ejemplo 1 de pasar un problema a forma canónica

Transformemos el siguiente problema a su forma canónica:
\begin{align*}
Min \quad z &= 3x_1-x_2\\
s.a&\\
&\begin{matrix}2x_1&+x_2& \leq 50\\
-x_1&+3x_2& \geq 20\end{matrix}\\
& x_1, x_2\geq 0\\
\end{align*}

Primero observemos que la tercera condición ya se cumple, ya que tanto $x_1$ como $x_2$ son no negativas.

Ahora, la primera condición nos dice que el problema tiene que ser de maximización y en este momento es de minimización. Para transformar nuestro problema a uno de maximización solo tenemos que invertir el signo de la función objetivo, ya que el minimizar la primera función ($z$) es equivalente a maximizar la función negativa ($-z$).

$$Max \quad z = -3x_1 + x_2$$

Y por último verifiquemos que se cumpla la segunda condición. La primera restricción claramente es del tipo $\leq$, pero la segunda restricción no es del tipo $\leq$ sino que es del tipo $\geq$. A esta restricción se le puede multiplicar por -1 de ambos lados y se convierte en una restricción del tipo $\leq$.

\begin{matrix}2x_1&+x_2& \leq 50\\
x_1&-3x_2& \leq -20\end{matrix}

Entonces nuestro problema ya cumple las 3 condiciones y podemos decir que está en forma canónica:

\begin{align*}
Max \quad z &= -3x_1 + x_2\\
&s.a\\
&\begin{matrix}2x_1&+x_2& \leq& 50\\
x_1&-3x_2& \leq& -20\end{matrix}\\
& x_1, x_2\geq 0\\
\end{align*}

Ejemplo 2 de pasar un problema a forma canónica

Transformemos el siguiente problema a su forma canónica.

\begin{align*}
Max \quad z &= 2x_1 + 5x_2 -3x_3\\
&s.a\\
&\begin{matrix}-x_1&+2x_2&-4x_3 =& -9\\
3x_1&+x_2&-5x_3 \geq& 10\\
4x_1&-6x_2&+7x_3 \geq& 2\\
\end{matrix}\\
& x_1, x_2\geq 0, \quad x_3 \quad SRS\\
\end{align*}

Primero observemos que la tercera condición se cumple para $x_1$ y $x_2$ pero $x_3$ está sin restricción de signo, por lo que vamos a definir $x_3′ \geq 0$ y $x_3″ \geq 0$ tales que $x_3 = x_3′- x_3″$.

Ahora, observemos que el problema ya es de maximización. Lo único que haremos es sustituir la variable $x_3$ que acabamos de re definir:

$$Max \quad z = 2x_1 + 5x_2 – 3x_3′ + 3x_3″$$

Y por último, para cumplir la segunda restricción tenemos que hacer a todas nuestras restricciones del tipo $\leq$.

Para la primera restricción, primero sustituimos la variable $x_3$ por la re definición que le dimos:

$$-x_1 + 2x_2 – 4x_3′ + 4x_3″ = -9$$

Y dado que es una igualdad, podemos sustituir la por dos desigualdades. Estas son:

\begin{matrix}-x_1&+2x_2&-4x_3’& + 4x_3″& \leq -9\\
-x_1&+2x_2& -4x_3’& +4x_3″& \geq -9\end{matrix}

La primera de estas dos nuevas restricciones ya es del tipo $\leq$, pero la segunda es del tipo $\geq$, por lo que lo único que hay que hacer es invertir el signo de esta desigualdad para que sea como queremos:

Para la segunda y tercera restricción del problema original, primero sustituimos a variable $x_3$ por como la re definimos:

\begin{matrix}3x_1&+x_2&-5x_3’& + 5x_3″& \geq 10\\
4x_1&-6x_2& +7x_3’& -7x_3″& \geq 2\end{matrix}

Y luego transformamos estas restricciones en restricciones del tipo \leq como lo hicimos en el ejemplo pasado.

\begin{matrix}-3x_1&-x_2&+5x_3’& -5x_3″& \leq -10\\
-4x_1&+6x_2& -7x_3’& +7x_3″& \leq -2\end{matrix}

Y así, todo junto el problema quedaría planteado de la siguiente manera:

\begin{align*}
Max \quad z = 2x_1 + 5x_2 – 3x_3′ + 3x_3″\\
\begin{matrix}-x_1&+2x_2&-4x_3’& + 4x_3″& \leq -9\\
-x_1&+2x_2& -4x_3’& +4x_3″& \geq -9\\
3x_1&-x_2&+5x_3’& -5x_3″& \leq -10\\
-4x_1&+6x_2& -7x_3’& +7x_3″& \leq -2\end{matrix}\\
x_1, x_2, x_3′, x_3″ \geq 0\\
\end{align*}

Y así este segundo problema quedaría en su forma canónica.

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.&\\
&\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}\\
\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 (o variable de sobra).

Ejemplo de pasar un problema a forma estándar

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

\begin{align*}
Min \quad z &= 3x_1-x_2\\
s.a&\\
&\begin{matrix}2x_1&+x_2& \leq 50\\
-x_1&+3x_2& \geq 20 \end{matrix}\\
& x_1, x_2\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.\\
   &\begin{matrix}4x_1 &-x_2 &- 5x_3 &=& 10\\
   2x_1 &+ 3x_2 &+ 2x_3 &\geq &12\end{matrix}\\
   & 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

• Ir a Investigación de Operaciones
• Entrada anterior del curso: El problema de la ruta más corta
• Entrada siguiente del curso: Soluciones básicas, factibles y no degeneradas