Archivo de la etiqueta: optimización

Cálculo Diferencial e Integral III: Multiplicadores de Lagrange

Por Alejandro Antonio Estrada Franco

Deja un comentario

Introducción

En la entrada anterior buscábamos optimizar un campo escalar $f$. Retomaremos este problema, pero ahora agregando restricciones al dominio de $f$. Para ello hablaremos del método de los multiplicadores de Lagrange, el cual nos permitirá dar una solución bajo ciertas condiciones de diferenciabilidad.

Esto en general es lo mejor que podremos hacer. En realidad, los problemas de este estilo son muy difíciles y no tienen una solución absoluta. Si no tenemos las condiciones del teorema de Lagrange, es posible que se tengan que hacer cosas mucho más compliadas para obtener óptimos exactos, o bien que se tengan que hacer aproximaciones numéricas.

En la demostración del teorema de los multiplicadores de Lagrange usaremos el teorema de la función implícita, lo cual es evidencia adicional de lo importante y versátil que es este resultado.

Un ejemplo para motivar la teoría

Imagina que tenemos la función $f(x,y)=x^2+y^2$ y queremos encontrar su mínimo. Esto es muy fácil. El mínimo se da cuando $x=y=0$, pues en cualquier otro valor tenemos un número positivo. Pero, ¿Qué pasaría si además queremos que los pares $(x,y)$ que usamos satisfagan también otra condición?, por ejemplo, que cumplan $$2x^2+3y^2=10$$

En este caso, la respuesta ya no es obvia. Podríamos intentar encontrar el mínimo por inspección, pero suena que será difícil. Podríamos intentar usar la teoría de la entrada anterior, pero esa teoría no nos dice nada de qué hacer con nuestra condición.

La teoría que desarrollaremos a continuación nos permitirá respondernos preguntas de este estilo. En este ejemplo en concreto, puedes pensar que la solución se obtendrá de la siguiente manera: La ecuación $2x^2+3y^2=10$ nos dibuja una elipse en el plano, como se ve en la figura 1 imagen 3. Las curvas de nivel de la superficie dibujada por la gráfica de la función $f$ corresponden a circunferencias concéntricas, cuyo centro es el origen. Al ir tomando circunferencias cada vez mas grandes en el plano comenzando con el punto $(0,0)$ nos quedaremos con la primera que toque a la elipse, de hecho la tocará en dos puntos, digamos $(x_1 ,y_1)$ y $(x_2 ,y_2)$, donde $f(x_1 ,y_1)=f(x_2 ,y_2)$ sería el mínimo buscado, es decir el mínimo que sobre la superficie $f(x,y)$ cumple con la ecuación $2x^2+3y^2=10$.

Figura 1; Imagen 1-Superior izquierda. Tenemos la gráfica de la ecuación $f(x,y)=x^2 + y^2$. Imagen 2- Inferior izquierda. Planos que intersecan a la superficie $f(x,y)$, nos dan las curvas de niver que son circunferencias concéntricas. Imagen 3- Derecha. En azul la elipse dibujada por la ecuación $2x^2 + 3y^2 =10$, y las curvas de nivel que se acercan a ella conforme cortamos mas arriba.

Pero como ahí se da una tangencia, entonces suena que justo en ese punto $(x,y)$ hay una recta simultáneamente tangente a la curva de nivel y a la elipse. Esto nos da una relación entre gradientes. El teorema de multiplicadores de Lagrange detecta y enuncia esta relación entre gradientes con precisión y formalidad, incluso cuando tenemos más de una condición. A estas condiciones también las llamamos restricciones, y están dadas por ecuaciones.

Enunciado del teorema de multiplicadores de Lagrange

A continuación enunciamos el teorema.

Teorema (multiplicadores de Lagrange). Sea $f:S\subseteq \mathbb{R}^{n}\rightarrow \mathbb{R}$ es un campo escalar de clase $C^{1}$. Para $m<n$, tomamos $g_{1},\dots ,g_{m}:S\in \subset \mathbb{R}^{n}\rightarrow \mathbb{R}$ campos escalares de clase $C^{1}$ en $S$. Consideremos el conjunto $S^\ast$ donde todos los $g_i$ se anulan, es decir:

$$S^\ast=\{ \bar{x}\in S|g_{1}(\bar{x})=g_2(\bar{x})=\ldots=g_m(\bar{x})=0\}.$$

Tomemos un $\bar{x}_0$ en $S^\ast$ para el cual

  1. $f$ tiene un extremo local en $\bar{x}_0$ para los puntos de $S^\ast$ y
  2. $\triangledown g_{1}(\bar{x}_{0}),\dots ,\triangledown g_{m}(\bar{x}_{0})$ son linealmente independientes.

Entonces existen $\lambda _{1},\dots ,\lambda _{m}\in \mathbb{R}$, a los que llamamos multiplicadores de Lagrange tales que:

\[ \triangledown f(\bar{x}_{0})=\lambda _{1}\triangledown g_{1}(\bar{x}_{0})+\dots +\lambda _{m}\triangledown g_{m}(\bar{x}_{0}).\]

Si lo meditas un poco, al tomar $m=1$ obtenemos una situación como la del ejemplo motivador. En este caso, la conclusión es que $\triangledown f(\bar{x}_0)=\lambda \triangledown g(\bar{x}_0)$, que justo nos dice que en $\bar{x}_0$, las gráficas de los campos escalares $f$ y $g$ tienen una tangente en común.

Demostración del teorema de multiplicadores de Lagrange

Demostración. La demostración del teorema de multiplicadores de Lagrange usa varios argumentos de álgebra lineal. Esto tiene sentido, pues a final de cuentas, lo que queremos hacer es poner un gradiente ($\triangledown f(\bar{x}_0)$) como combinación lineal de otros gradientes ($\triangledown g_1(\bar{x}_0),\ldots, \triangledown g_m(\bar{x}_0)$). A grandes rasgos, lo que haremos es:

  • Definir un espacio $W$.
  • Mostrar que $\triangledown g_1(\bar{x}_0),\ldots, \triangledown g_m(\bar{x}_0)$ generan al espacio ortogonal $W^\bot$.
  • Mostrar que $\triangledown f(\bar{x}_0)$ es ortogonal a todo vector de $W$, por lo cual estará en $W^\bot$ y así por el inciso anterior será combinación lineal de $\triangledown g_1(\bar{x}_0),\ldots, \triangledown g_m(\bar{x}_0)$.

Para construir el espacio $W$ del que hablamos, usaremos el teorema de la función implícita y la regla de la cadena. Empecemos este argumento. Consideremos la siguiente matriz:

\[ \begin{equation} \begin{pmatrix} \frac{\partial g_{1}}{\partial x_{1}}(\bar{x}_{0}) & \dots & \frac{\partial g_{1}}{\partial x_{m}}(\bar{x}_{0}) & \frac{\partial g_{1}}{\partial x_{m+1}}(\bar{x}_{0}) & \dots & \frac{\partial g_{1}}{\partial x_{n}}(\bar{x}_{0}) \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ \frac{\partial g_{m}}{\partial x_{1}}(\bar{x}_{0}) & \dots & \frac{\partial g_{m}}{\partial x_{m}}(\bar{x}_{0}) & \frac{\partial g_{m}}{\partial x_{m+1}}(\bar{x}_{0}) & \dots & \frac{\partial g_{1}}{\partial x_{n}}(\bar{x}_{0}) \end{pmatrix}. \end{equation}\]

Dado que los vectores $\triangledown g_1(\bar{x}_0),\ldots, \triangledown g_m(\bar{x}_0)$ son linealmente independientes, el rango por renglones de esta matriz es $m$, de modo que su rango por columnas también es $m$ (tarea moral). Sin perder generalidad (quizás tras hacer una permutación de columnas, que permuta las entradas), tenemos que las primeras $m$ columnas son linealmente independientes. Así, la matriz

\[ \begin{pmatrix} \frac{\partial g_{1}}{\partial x_{1}}(\bar{x}_{0}) & \dots & \frac{\partial g_{1}}{\partial x_{m}}(\bar{x}_{0}) \\ \vdots & \ddots & \vdots \\ \frac{\partial g_{m}}{\partial x_{1}}(\bar{x}_{0}) & \dots & \frac{\partial g_{m}}{\partial x_{m}}(\bar{x}_{0}) \end{pmatrix}\]

es invertible. Hagamos $l=n-m$ y reetiquetemos las variables coordenadas $x_1,\ldots,x_m$ como $v_1,\ldots,v_m$, y las variables coordenadas $x_{m+1},\ldots,x_n$ como $u_1,\ldots, u_l$. Escribiremos $\bar{x}_0=(\bar{v}_0,\bar{u}_0)$ para referirnos al punto al que hacen referencia las hipótesis. Esto nos permite pensar $\mathbb{R}^{n}=\mathbb{R}^{m}\times \mathbb{R}^{l}$ y nos deja en el contexto del teorema de la función implícita. Como la matriz anterior es invertible, existen $U\subseteq \mathbb{R}^l$ y $V\subseteq \mathbb{R}^m$ para los cuales $\bar{u}_0\in U$, $\bar{v}_0\in V$ y hay una única función $h=(h_1,\ldots,h_m):U\to V$ de clase $C^1$ tal que para $\bar{u}\in U$ y $\bar{v}\in V$ se cumple que $g(\bar{v},\bar{u})=0$ si y sólo si $\bar{v}=h(\bar{u})$.

Definamos ahora la función $H:U\subseteq \mathbb{R}^{l}\rightarrow \mathbb{R}^{m}\times \mathbb{R}^{l}$ como $H(\bar{u})=(h(\bar{u}),\bar{u})$, la cual es de clase $C^{1}$ en $U$.

Por cómo construimos $h$, sucede que $(h(\bar{u}),\bar{u})\in S^{*}$ para toda $\bar{u}\in U$. Por definición, esto quiere decir que para toda $i=1,\ldots,m$ tenemos que $$(g_{i}\circ H)(\bar{u})=0$$ para toda $\bar{u}\in U$. Esto quiere decir que $g_i\circ H$ es una función constante y por lo tanto su derivada en $\bar{u}_0$ es la transformación $0$. Pero otra forma de obtener la derivada es mediante la regla de la cadena como sigue:

\begin{align*} D(g_{i}\circ H)(\bar{u}_{0})&=Dg_{i}(H(\bar{u}_{0}))DH(\bar{u}_{0})\\ &=Dg_{i}(\bar{v}_{0},\bar{u}_{0})DH(\bar{u}_{0}).\end{align*}

En términos matriciales, tenemos entonces que el siguiente producto matricial es igual al vector $(0,\ldots,0)$ de $l$ entradas (evitamos poner $(\bar{v}_0,\bar{u}_0)$ para simplificar la notación):

\[ \begin{equation}\begin{pmatrix} \frac{\partial g_{i}}{\partial v_{1}}& \dots & \frac{\partial g_{i}}{\partial v_{m}} & \frac{\partial g_{i}}{\partial u_{1}} & \dots & \frac{\partial g_{i}}{\partial u_{l}} \end{pmatrix}\begin{pmatrix} \frac{\partial h_{1}}{\partial u_{1}} & \dots & \frac{\partial h_{1}}{\partial u_{l}} \\ \vdots & \ddots & \vdots \\ \frac{\partial h_{m}}{\partial u_{1}} & \dots & \frac{\partial h_{m}}{\partial u_{l}} \\ 1 & \dots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \dots & 1 \end{pmatrix}\end{equation},\]

para cada $i=1,\ldots, m$. Nos gustaría escribir esta conclusión de manera un poco más sencilla, para lo cual introducimos los siguientes vectores para cada $j=1,\ldots, l$:

\[ \bar{w}_{j}=\left( \left( \frac{\partial h_{1}}{\partial u_{j}}(\bar{u}_{0}),\dots ,\frac{\partial h_{m}}{\partial u_{j}}(\bar{u}_{0}) \right), \hat{e}_{j}\right).\]

Cada uno de estos lo pensamos como vector en $\mathbb{R}^m\times \mathbb{R}^l$. Además, son $l$ vectores linealmente independientes, pues sus entradas $\hat{e}_j$ son linealmente independientes. El espacio vectorial $W$ que generan es entonces un subespacio de $\mathbb{R}^m\times \mathbb{R}^l$, con $\dim(W)=l$.

De la ecuación $(2)$ tenemos que $\triangledown g_{i}(\bar{v}_{0},\bar{u}_{0})\cdot \bar{w}_{j}=0$ para todo $i=1,\dots ,m$, y $j=1,\dots ,l$. Se sigue que $\triangledown g_{i}(\bar{v}_{0},\bar{u}_{0})\in W^{\perp}$, donde $W^{\perp}$ es el complemento ortogonal de $W$ en $\mathbb{R}^{m}\times \mathbb{R}^{l}$. Pero además, por propiedades de espacios ortogonales tenemos que

\begin{align*}
\dim(W^{\perp})&=\dim(\mathbb{R}^{m}\times \mathbb{R}^{l})-dim(W)\\
&=m+l-l\\
&=m.
\end{align*}

Así $\dim(W^{\perp})=m$, además el conjunto $\left\{ \triangledown g_{i}(\bar{v}_{0},\bar{u}_{0}) \right\}_{i=1}^{m}$ es linealmente independiente con $m$ elementos, por tanto este conjunto es una base para $W^{\perp}$. Nuestra demostración estará terminada si logramos demostrar que $\triangledown f(\bar{v}_0,\bar{u}_0)$ también está en $W^\perp$, es decir, que es ortogonal a todo elemento de $W$.

Pensemos qué pasa al componer $f$ con $H$ en el punto $\bar{u}_0$. Afirmamos que $\bar{u}_0$ es un extremo local de $f\circ H$. En efecto, $(f\circ H)(\bar{u}_0)=f(g(\bar{u}_0),\bar{u}_0)=(\bar{v}_0,\bar{u}_0)$. Si, por ejemplo $(\bar{v}_0,\bar{u}_0)$ diera un máximo, entonces los valores $f(\bar{v},\bar{u})$ para $(\bar{v},\bar{u})$ dentro de cierta bola $B_\delta(\bar{v}_0,\bar{u}_0)$ serían menores a $f(\bar{v}_0,\bar{u}_0)$. Pero entonces los valores cercanos $\bar{u}$ a $\bar{u}_0$ cumplen $(f\circ H)(\bar{u})=f(h(\bar{u}),\bar{u})$, con $(\bar{u},h(\bar{u}))$ en $S^\ast$ y por lo tanto menor a $f(\bar{v}_0,\bar{u}_0)$ (para mínimos es análogo).

Resumiendo lo anterior, $\bar{u}_{0}$ es extremo local de $f\circ H$. Aplicando lo que aprendimos en la entrada anterior, la derivada de $f\circ H$ debe anularse en $\bar{u}_0$. Pero por regla de la cadena, dicha derivada es

\begin{align*}\triangledown (f\circ H)(\bar{u}_{0})&=D(f\circ H)(\bar{u}_{0})\\ &=Df(H(\bar{u}_{0}))DH(\bar{u}_{0})\\ &=Df(h(\bar{u}_{0}),\bar{u}_{0})DH(\bar{u}_{0})\\
&=Df(\bar{v}_0,\bar{u}_{0})DH(\bar{u}_{0})
\end{align*}

Viéndolo como multiplicación de matrices, el siguiente producto es el vector $(0,0,\ldots,0)$ de $l$ entradas:

\[ \begin{pmatrix} \frac{\partial f}{\partial v_{1}} & \dots & \frac{\partial f}{\partial v_{m}} & \frac{\partial f}{\partial u_{1}} & \dots & \frac{\partial f}{\partial u_{l}} \end{pmatrix}\begin{pmatrix} \frac{\partial h_{1}}{\partial u_{1}} & \dots & \frac{\partial h_{1}}{\partial u_{l}} \\ \vdots & \ddots & \vdots \\ \frac{\partial h_{m}}{\partial u_{1}} & \dots & \frac{\partial h_{m}}{\partial u_{l}} \\ 1 & \dots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \dots & 1 \end{pmatrix}=0 \]

De donde concluimos $\triangledown f(\bar{v}_{0},\bar{u}_{0})\cdot \bar{w}_{j}=0$ para cada $j=1,\dots l$. Esto precisamente nos dice que $\triangledown f(\bar{v}_{0},\bar{u}_{0})\in W^{\perp}$. Esto es justo lo que queríamos, pues habíamos demostrado que $\left\{ \triangledown g_{i}(\bar{v}_{0},\bar{u}_{0}) \right\}_{i=1}^{m}$ es una base de $W^{\perp}$. Por ello podemos expresar a $\triangledown f(\bar{v}_{0},\bar{u}_{0})$ como combinación lineal de esta base, es decir, existen $\lambda _{1},\dots ,\lambda _{m}$ escalares tales que:

\[ \triangledown f(\bar{v}_{0},\bar{u}_{0})=\lambda _{1}\triangledown g_{1}(\bar{v}_{0},\bar{u}_{0})+\dots +\lambda _{m}\triangledown g_{m}(\bar{v}_{0},\bar{u}_{0}). \]

$\square$

¡Qué bonita demostración! Usamos el teorema de la función implícita, la regla de la cadena (dos veces), nuestros resultados para valores extremos de la entrada anterior, y un análisis cuidadoso de ciertos espacios vectoriales.

Ejemplos del método de multiplicadores de Lagrange

Veamos algunos problemas que podemos resolver con esta nueva herramienta.

Ejemplo. Determinaremos los puntos extremos de $f(x,y)=x+2y$ bajo la condición $x^{2}+y^{2}=5$. Para poner todo en términos de nuestro teorema, definimos $g(x,y)=x^{2}+y^{2}-5$. Por el teorema de multiplicadores de Lagrange, en los puntos extremos debe existir una $\lambda$ tal que $\triangledown f(x,y)=\lambda \triangledown g(x,y)$. Calculando las parciales correspondientes, debemos tener entonces

\[ \left( 1,2 \right)=\lambda \left( 2x,2y \right).\]

Adicionalmente, recordemos que se debe satisfaces $g(x,y)=0$. Llegamos entonces al sistema de ecuaciones

\[ \left \{\begin{matrix} 1-2x\lambda=0 \\ 2-2y\lambda =0 \\ x^{2}+y^{2}-5=0 \end{matrix}\right. \]

Al despejar $x$ y $y$ en ambas ecuaciones tenemos:

\[ \begin{matrix} x=\frac{1}{2\lambda} \\ y=\frac{1}{\lambda} \\ x^{2}+y^{2}-5=0 \end{matrix}.\]

Poniendo los valores de $x$ y $y$ en la tercera ecuación, llegamos a $\left( \frac{1}{2\lambda}\right)^{2}+\left( \frac{1}{\lambda}\right)^{2}-5=0$, de donde al resolver tenemos las soluciones $\lambda _{1}=\frac{1}{2}$ y $\lambda _{2}=-\frac{1}{2}$.

Al sustituir en las ecuaciones de nuestro sistema, obtenemos como puntos críticos a $(x,y)=(-1,-2)$ y $(x,y)=(1,2)$.

Si intentamos calcular el hessiano de $f$, esto no nos dirá nada (no tendremos eigenvalores sólo positivos, ni sólo negativos). Pero esto ignora las restricciones que nos dieron. Podemos hacer una figura para entender si estos puntos son máximos o mínimos. En la Figura $1$ tenemos la gráfica de $f$, intersectada con la superfice dada por $g$. Nos damos cuenta que hay un punto máximo y uno mínimo. Al evaluar, obtenemos $f(1,2)=5$ y $f(-1,-2)=-5$. Esto nos dice que el máximo en la superficie se alcanza en $(1,2)$ y el mínimo en $(-1,-2)$.

Figura 2: Ilustración del Ejemplo 1 la función $g(x,y)=x^{2}+y^{2}-5$ esta dibujada en azul esta impone restricción a la función $f$ que dibuja un plano en el espacio.

$\triangle$

Ejemplo. Veamos cómo minimizar la expresión $$f(x,y,z)=x^{2}+y^{2}+z^{2}$$ sujetos a la condición $x+y+z=1$. Una vez más, proponemos $g(x,y,z)=x+y+z-1$ para tener la situación del teorema de multiplicadores de Lagrange. Debe pasar que $\lambda$ $\triangledown f(x,y,z)=\lambda \triangledown g(x,y,z)$. El gradiente de $g(x,y,z)$ es de puros ceros unos, así que tenemos el sistema de ecuaciones:

\[ \left \{\begin{matrix} 2x=\lambda \\ 2y=\lambda \\ 2z=\lambda \\ x+y+z-1=0 \end{matrix}\right.\]

De las primeras tres ecuaciones tenemos $2x=2y=2z$ de donde $x=y=z$. Sustituyendo en la tercera ecuación, $3x-1=0$, es decir $x=y=z=\frac{1}{3}$. Ya que sólo tenemos una solución, ésta es el mínimo del conjunto de soluciones. En la figura 3 tenemos la ilustración de la solución de este problema, la esfera centrada en el origen de radio $\frac{1}{3}$ toca al plano $x+y+z=1$ en el punto $\left( \frac{1}{3},\frac{1}{3},\frac{1}{3}\right)$

$\triangle$

Figura 3: En azul claro el plano $x+y+z=1$, inflamos esferas centradas en el origen; desde la de radio cero vamos aumentando el radio hasta tener el radio correspondiente para el cual la esfera toque tangentemente al plano.

Más adelante…

Con esta entrada cerramos el curso de Cálculo Diferencial e Integral III. ¡¡Felicidades!! Esperamos que todas estas notas te hayan sido de ayuda para estudiar, repasar o impartir la materia. Quedamos al pendiente de cualquier duda, observación o sugerencia en la sección de comentarios de las entradas.

Tarea moral

  1. Determina los extremos de la función $f(x,y)=xy+14$ bajo la restricción $x^{2}+y^{2}=18$
  2. El plano $x+y+2z=2$ interseca al paraboloide $z=x^{2}+y^{2}$ en una elipse $\mathbb{E}$. Determina el punto de la elipse con el valor mayor en el eje $z$, y el punto con el valor mínimo en el mismo eje. Sugerencia: $f(x,y,z)=x+y+2z-2$, y $g(x,y,z)=x^{2}+y^{2}-z$
  3. Determinar el máximo valor de $f(x,y,z)=x^{2}+36xy-4y^{2}-18x+8y$ bajo la restricción $3x+4y=32$
  4. Determinar los puntos extremos de la función $f(x,y,z)=x^{2}+y^{2}+z^{2}$ bajo la restricción $xyz=4$
  5. Demuestra que en una matriz $M$ su rango por columnas es igual a su rango por renglones. Sugerencia. Usa el teorema de reducción gaussiana. También, puedes revisar la entrada que tenemos sobre rango de matrices.

Entradas relacionadas

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

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.

Abundan las aplicaciones de la programación lineal para planificar la producción y para controlar inventarios. El siguiente es solo una de múltiples aplicaciones que se les puede dar a este tipo de problemas.

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 empresa productora de videojuegos indie acaba de finalizar su último gran lanzamiento y está lista para producirlo en masa en su formato físico. La siguiente tabla indica la demanda de los primeros 3 meses de lanzamiento.

Meses transcurridos a
partir del lanzamiento		012
Demanda en miles de copias
del mes en curso		806040
Productividad disponible del
mes en curso		1105030

Como el primer mes de lanzamiento es el más importante, la empresa decide que se pueden producir hasta 110 mil copias ese mes, y gradualmente va a reducir su productividad a 50 mil copias el segundo mes y 30 mil el tercer mes; esto con la finalidad de enfocar más tiempo y recursos en otras producciones.

La empresa productora y las tiendas donde se venden tiene un contrato que establece en particular dos cosas:

  • Las tiendas tienen que tener en stock la cantidad de copias demandas cada mes, y esta cantidad de copias será las que la empresa productora entregó este mes junto con las que sobraron el mes pasado
    • Si se entregan más copias que las demandadas por la tienda, se cobrará un costo de almacenamiento de \$2000 al mes por cada mil copias que están siendo almacenadas en tienda fuera de la demanda establecida.

El costo de producción de cada mil copias es de \$20000. Se desea determinar el plan de producción e inventario que satisfaga el contrato con estas tiendas a fin de minimizar los costos.

Variables de decisión

De manera intuitiva, vamos a hacer nuestras variables de decisión las miles de copias que se van a producir el mes en curso desde el lanzamiento del juego.

$x_i$ = miles de copias a producir en el mes $i$ desde el lanzamiento del juego. $(i \in \{1, 2, 3\})$.

Función objetivo

Como se mencionó, el plan de producción tiene que minimizar los costos para la empresa, tanto los gastos de producción de sus videojuegos como el almacenamiento de estos.

El costo de producción es simplemente el número de copias producidas por cada mes, multiplicado por el costo de fabricación de cada copia ($\$20$). Esto es: $20(x_1 + x_2 + x_3)$.

Y luego consideramos el costo de almacenamiento de las copias que no fueron demandadas por la empresa en ese mes. Entonces, para el primer mes, $x_1 – 80$ son las miles de copias que la empresa tiene que cubrir en gastos de almacenamiento. Para el segundo mes, las copias demandadas al momento son las acumuladas del primer y segundo mes ($140000$) y los juegos producidos son solamente $x_1 + x_2$. Entonces, los miles de juegos por los que hay que cubrir el costo de almacenamiento son $x_1 + x_2 – 140$. Y para el tercer mes, las copias demandadas son las acumuladas de los primeros 3 meses ($180000$) y los juegos producidos serán $x_1 + x_2 + x_3$ en miles de copias, y así, los costos de almacenamiento para el tercer mes serán $x_1 + x_2 + x_3 – 180$.

Entonces, el número de miles de copias por las que hay que cubrir costos de almacenamiento para estos 3 meses será: $(x_1 – 80) + (x_1 + x_2 – 140) + (x_1 + x_2 + x_3 -180)$. Y esta cantidad la multiplicamos por el costo de almacenamiento mensual por millar de copias (\$2000).

Entonces, juntando las expresiones, el costo total que hay que minimizar sería:

$$Min \quad z = 20000(x_1 + x_2 + x_3) + 2000[(x_1 – 80) + (x_1 + x_2 – 140) + (x_1 + x_2 + x_3 – 180)]$$

O si lo queremos poner de la forma más resumida posible, esto es:

$$Min \quad z = 26000x_1 + 24000x_2 + 22000x_3 – 800000$$

Restricciones del problema de producción e inventario

Primero, vayamos con las restricciones de oferta:

\begin{align*}
x_1 \leq 110\\
x_2 \leq 50\\
x_3 \leq 30\\
\end{align*}

Después, vayamos con las restricciones de demanda:

\begin{align*}
x_1 \geq 80\\
x_2 + (x_1 – 80) \geq 60\\
x_3 + (x_1 + x_2 – 140) \geq 40\\
\end{align*}

Recordemos que la razón de la última restricción es para que la empresa productora no se quede ninguna copia más de las demandadas para que no haya cuota por almacenamiento en las tiendas para el cuarto mes.

Y naturalmente nuestras variables de decisión son no negativas ya que hablamos de la cantidad de unidades que tenemos de un producto.

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

En resumen, nuestro problema de programación lineal quedaría planteado así:

\begin{align*}
Min \quad z = 20000(x_1 + x_2 + x_3) &+ 2000[(x_1 – 80) + (x_1 + x_2 – 140) + (x_1 + x_2 + x_3 – 180)]\\
&s.a\\
x_1 &\leq 110\\
x_2 &\leq 50\\
x_3 &\leq 30\\
x_1 &\geq 80\\
x_2 + (x_1 – 80) &\geq 60\\
x_3 + (x_1 + x_2 – 140) &\geq 40\\
x_i &\geq 0, i \in \{1, 2, 3\}\\
\end{align*}

Más adelante…

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

  1. El problema se vuelve mucho más sencillo si únicamente hay dos periodos. Plantea un problema que refleje esta situación en el caso particular de la entrada y resuélvelo. Es decir, determina en esos dos periodos (el primer y segundo mes) cuál es la cantidad correcta de unidades a producir por mes, para minimizar el costo total.
  2. Cambia el planteamiento dado en la entrada por uno en el que el costo de almacenaje en las tiendas sea de \$0. En ese caso, ¿cuál sería el plan de producción e inventario óptimo?
  3. 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 n periodos con demanda de unidades$d_1, d_2, \ldots, d_n$ por cada periodo.
    2. Se tengan capacidades de producción $o_1, o_2, \ldots, o_n$ unidades en cada periodo.
    3. Se tengan costos $P$ y $A$, de producir y almacenar una unidad de producto respectivamente.
  4. En un problema general de producción e inventario. ¿Por qué podría ser mala idea producir mucho más de lo necesario en las temporadas en las que se puede? Intenta justificar intuitivamente, y luego encuentra algunos casos particulares del problema que apoyen tus argumentos.

Respuestas

1.- Si eliminamos un mes del problema, tendríamos la siguiente tabla de productividad y demanda:

Meses transcurridos a
partir del lanzamiento		01
Demanda en miles de copias
del mes en curso		8060
Productividad disponible del
mes en curso		11050

Tenemos las mismas variables de decisión: $x_i$ = miles de copias a producir el mes $i$ desde el lanzamiento del juego. $i \in \{1, 2\}$

Para la función objetivo, el costo de producción de las copias va a ser: $20000(x_1 + x_2)$. Los gastos de almacenamiento del primer y segundo mes serán: $2000[(x_1 – 80) + (x_1 + x_2 – 140)]$.

Entonces la función objetivo queda de la siguiente manera:

$$Min \quad z = 24000x_1 + 22000x_2 – 440000$$

Las restricciones de oferta y de demanda serían:

\begin{align*}
x_1 &\leq 110\\
x_2 &\leq 50\\
x_1 &\geq 80\\
x2 + (x_1 – 80) &\geq 60\\
\end{align*}

Entonces, el problema con dos periodos de tiempo quedaría planteado de la siguiente manera:

\begin{align*}
Min \quad z &= 24000x_1 + 22000x_2 – 440000\\
&s.a\\
x_1 &\leq 110\\
x_2 &\leq 50\\
x_1 &\geq 80\\
x_2 + (x_1 – 80) &\geq 60\\
x_i &\geq 0, i \in \{1, 2\}\\
\end{align*}

Ahora, una posible solución a este problema sea satisfacer la demanda del primer mes, con tal de que sobren solamente la menor cantidad de copias que al sumarlas con la producción del segundo mes, nos cumplan también la demanda exacta de ese mes. Es decir, producir en el primer mes 90000 copias, almacenar 10000 que sobrarían en tienda y producir hasta el límite de producción el segundo mes que son 50000 copias y juntos con las 10000 que había almacenadas, se cumplirá la demanda que tenemos para el segundo periodo que son 60000 copias. De esta manera no se incurre en gastos innecesarios de almacenamiento, ya que para el tercer mes no hay copias por almacenar que nos generen ese gasto.

2.- Si no hubiera costo por almacenamiento tenemos varias soluciones que podrían ser óptimas, pero en realidad lo sería cualquiera donde se cumplan los valores de demanda al mínimo, es decir, que se produzcan las unidades que nos piden por los tres meses y ni una más.

3.- Sea una empresa tiene que producir un producto y este producto se vende en n periodos de tiempo, con su respectiva demanda ($d_1, \ldots, d_n$) y oferta de productos ($o_1, \ldots, o_n$) en cada uno de ellos.

Se tiene un costo $P$ de fabricación por producto y un costo A de almacenamiento por producto de un periodo a otro.

Se quiere determinar el plan de producción e inventario que satisfaga la demanda y minimice los costos.

Variables de decisión: $x_i$ = número de unidades a producir en el periodo $i$. $i \in \{1, \ldots, n\}$

Función objetivo:

$$Min \quad z = P(x_1 + \ldots + x_n) + A[(x_1-d_1) + (x_1 + x_2 – d_1 – d_2) + \ldots + (\sum_{i=1}^n{x_i} – \sum_{i=1}^n{d_i})]$$

Y por último, las restricciones serían:

\begin{align*}
x_1 &\leq o_1\\
x_2 &\leq o_2\\
&\vdots\\
x_n &\leq o_n\\
x_1 &\geq d_1\\
x_1 + x_2 – d_1 &\geq d_2\\
\vdots\\
\end{align*}

$$(\sum_{i=1}^n{x_i} – \sum_{i=1}^{n-1}{d_i}) \geq \sum_{i=1}^n{d_i}$$

$$x_i \geq 0,\quad i \in \{1, \ldots, n\}$$

4.- Dependería del problema pero en general como se intenta minimizar los costos, esto también sería minimizar los costos que conlleva el almacenaje de productos y si se producen muchos cada periodo, esto incurrirá en el aumento de los gastos mencionados y no será lo optimo para el objetivo que tenemos.

Entradas relacionadas

Investigación de Operaciones: El problema del transporte

Por Aldo Romero

Deja un comentario

Introducción

En esta entrada abordaremos otro de los problemas conocidos que se pueden plantear en términos de programación lineal: el problema del transporte. A grandes rasgos, el problema del transporte habla de cómo surtir a diferentes destinos de un cierto producto que parte de diferentes orígenes con disponibilidad limitada.

Siendo un poco más concretos, cada origen tiene una cierta cantidad de unidades de producto. Cada destino requiere de una cierta cantidad de unidades de producto. Además, para cada pareja origen-destino se tiene un costo de transporte unitario. El objetivo es determinar cuál es la manera más económica de cumplir con todos los requisitos de oferta y demanda.

Ejemplo del problema del transporte

Supongamos que una compañía que produce electrónicos tiene tres almacenes $A$, $B$ y $C$. La cantidad de computadoras portátiles disponibles en cada uno de los almacenes se encuentra registrada en la siguiente tabla.

OrigenABC
Oferta en unidades200350470

Pensemos que hay dos tiendas de electrónicos $X$ y $Y$ que desean vender computadoras portátiles de dicha compañía. La cantidad de computadoras portátiles que necesita cada tienda está dada en la siguiente tabla.

DestinoXY
Demanda en
unidades		300500

Además de esto sabemos que transportar cada una de las computadoras portátiles tiene un costo que depende del almacén origen y de la tienda destino. El costo unitario de transporte está dado por la siguiente tabla.

ABC
X354042
Y443745

Así, por ejemplo, transportar una computadora portátil del almacén $B$ a la tienda $Y$ tiene un costo de \$37.

Queremos determinar cuántas computadoras portátiles se tienen que enviar de cada origen a cada destino de manera que no se exceda la cantidad disponible en cada origen, a cada tienda llegue la cantidad de computadoras que se deben enviar y se minimice el costo total de envío.

Variables de decisión

Lo que tenemos que decidir en nuestro problema es cuántas computadoras portátiles se envían de cada origen a cada destino. Por ejemplo, debemos decidir cuánto vale una variable $x_{AX}$ que nos dice cuántas computadoras portátiles enviar del almacén $A$ a la tienda $X$. Así, las variables se definen de la siguiente manera:

$x_{ij}$ = número de computadoras a transportar del almacén $i$ al destino $j$. $i \in \{A, B, C\}, j \in \{X, Y\}$.

En este ejemplo en concreto, la cantidad de unidades debe ser un número entero (no podemos enviar $1/2$ de computadora portátil de un almacén a una tienda).

Función objetivo

Debemos de establecer cuál es la función objetivo que queremos optimizar. Notemos que el costo total que involucrarán las computadoras portátiles enviadas del almacén $A$ a la tienda $X$ es $35x_{AX}$, pues de acuerdo a la tabla de costos de transporte, hay un costo de \$35 para enviar cada computadora portátil. Todas las computadoras que salgan del almacén $A$ tendrán entonces un costo de $35x_{AX}+44x_{AY}$. Si calculamos de manera similar el costo de las computadoras que se salen de los almacenes $B$ y $C$ obtenemos el total. Entonces la función objetivo será la siguiente expresión:

$$Min \quad z = 35x_{AX}+44x_{AY}+40x_{BX}+37x_{BY}+42x_{CX}+45x_{CY}.$$

Restricciones

Hay dos tipos de restricciones que debemos cuidar:

  • Que ninguno de los almacenes exceda la cantidad de computadoras portátiles que tiene disponible.
  • Que cada tienda reciba el número de computadoras portátiles que requiere.

En el caso de la primera restricción, lo que estamos haciendo es limitar a las sumas que involucren a un mismo almacén. Por ejemplo, para no exceder las $200$ unidades que se tienen disponibles en el almacén $A$, se debe cumplir que $x_{AX}+x_{AY}\leq 200$. De manera similar, con el almacén $B$ obtenemos que $x_{BX}+x_{BY}\leq 350$ y con el almacén $C$ obtenemos que $x_{CX}+x_{CY}\leq 470$.

En el caso de la segunda restricción, ahora la desigualdad es opuesta: es una condición que requiere que las computadoras portátiles que lleguen a cada tienda sean al menos un valor dado. Entonces, para la tienda $X$ se tiene que cumplir $x_{AX}+x_{BX}+x_{CX}\geq 300$ y para la tienda $Y$ se tiene que cumplir $x_{AY}+x_{BY}+x_{CY}\geq 500$.

Entonces, juntando todas las restricciones, tenemos:

\begin{align*}
x_{AX}+x_{AY} \leq 200\\
x_{BX}+x_{BY} \leq 350\\
x_{CX}+x_{CY} \leq 470\\
x_{AX}+x_{BX}+x_{CX} \geq 300\\
x_{AY}+x_{BY}+x_{CY} \geq 500\\
x_{ij} \in \mathbb N, i \in \{A, B, C\}, j \in \{X, Y\}\\
\end{align*}

Resumen de formulación del problema del transporte

En resumen, el ejemplo de problema de transporte queda resumido en el siguiente PPL.

\begin{align*}
Min \quad z = 35x_{AX}+44x_{AY}+40x_{BX}&+37x_{BY}+42x_{CX}+45x_{CY}&\\
s.a.&\\
x_{AX}+x_{AY}&\leq 200\\
x_{BX}+x_{BY}&\leq 350\\
x_{CX}+x_{CY}&\leq 470\\
x_{AX}+x_{BX}+x_{CX}&\geq 300\\
x_{AY}+x_{BY}+x_{CY}&\geq 500\\
x_{ij} \in \mathbb N, i \in \{A, B, C\}, j \in \{X, Y\}\\
\end{align*}

Formulación general del problema del transporte

De manera general, en el problema del transporte se requieren transportar ciertas unidades de un producto desde $m$ centros de oferta (también llamados orígenes), a $n$ centros de demanda, (también denominados destinos). Cada centro de oferta tiene una cierta cantidad de unidades disponibles, y cada centro de demanda tiene una cierta cantidad de unidades que desea recibir.

Llamemos $o_i$ a la oferta del origen $i$ en unidades del producto ($i=1, \ldots , m$) y $d_j$ la demanda del destino $j$ en unidades del producto ($j=1, \ldots, n$). Para cada origen $i$ y cada destino $j$ tiene cierto costo enviar una unidad de producto. Sea $c_{ij}$ el costo unitario de transporte del producto del origen $i$ al destino $j$ ($i = 1, \ldots , m;j=1, \ldots , n$).

Lo que buscamos es determinar para cada origen $i$ y cada destino $j$ cuántas unidades $x_{ij}$ se deben transportar de tal modo que no se exceda la producción de cada origen, se satisfaga la demanda en cada destino y se incurra en el mínimo costo de transporte.

Como lo hemos hecho en entradas anteriores, las condiciones anteriores pueden ser planteadas en términos lineales. Para no exceder la oferta del origen $i$, se debe cumplir que

$$\sum_{j=1}^nx_{ij} \leq o_i,$$

para cada $i=1,\ldots,m$. A estas desigualdades les llamamos las restricciones de oferta.

Para cumplir con la demanda en el destino $j$ se debe cumplir que

$$\sum_{i=1}^{m}x_{ij} \geq d_j,$$

para cada $j=1,\ldots,n$. A estas desigualdades les llamamos las restricciones de demanda.

Agregando las condiciones de positividad y estableciendo que queremos minimizar el costo total, obtenemos el problema planteado de la siguiente manera:

\begin{align*}
Min \quad z &= \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}\\
s.a.&\\
\sum_{j=1}^nx_{ij} &\leq o_i, \quad i=1, \ldots , m \quad \quad (1)\\
\sum_{i=1}^{m}x_{ij} &\geq d_j, \quad j=1, \ldots , n \quad \quad (2)\\
x_{ij} &\geq 0; \quad i=1, \ldots , m; j=1, \ldots , n,\\
\end{align*}

donde $x_{ij}$ es el número de unidades del producto a transportar del origen $i$ al destino $j$, para cada $i=1, \ldots , m$ y cada $j = 1, \ldots , n$.

Las desigualdades en (1) se llaman restricciones de oferta y en (2) restricciones de demanda.

Más adelante…

Con este problema contamos ya con tres ejemplos de situaciones que se pueden plantear en términos de programación lineal: el problema de la dieta, el problema de la mochila y el problema del transporte. A continuación veremos dos más: el problema de producción e inventario, y el problema de la ruta más corta.

Tarea

  1. Encuentra por lo menos una manera de realizar las asignaciones de variables en el problema de los almacenes de computadoras portátiles y las tiendas. No importa que el costo total que encuentres no sea óptimo, pero sí se deben cumplir las restricciones de oferta y de demanda.
  2. ¿Qué sucede en el problema del transporte si la cantidad total de demanda excede a la cantidad total de oferta? Plantea esta posibilidad en términos de los parámetros $o_i$ y $d_j$ de oferta y demanda, respectivamente.
  3. Imagina que en el ejemplo que planteamos de computadoras portátiles, almacenes y tiendas sucede que el precio de transportar una computadora portátil es de \$30 sin importar el almacén origen o la tienda destino. En este caso, ¿cuál sería una manera óptima de realizar los envíos, y tal que se cumplan las restricciones de oferta y demanda?
  4. Se presenta la siguiente situación:

Una empresa coreana fabrica y luego distribuye sus pantallas a diferentes vendedores. En este momentos tienen pantallas de 4 diferentes tamaños: 43″, 50″, 55″ y 65″. Los países a donde distribuyen sus productos son Japón, China y Estados Unidos. En la siguiente tabla se muestra el costo de exportación en miles de dólares por cada 1000 televisores de cada modelo.

43″50″55″65″Demanda este año
Japón\$50k\$60k\$65k\$70k100k
China\$60k\$70k\$75k\$80k300k
Estados Unidos\$80k\$90k\$95k\$100k350k
Disponibilidad250k220k180k150k——

También se señaló en la tabla anterior cual es la demanda de cada país para este año y las pantallas que fueron fabricadas este año por cada modelo.

Plantea este problema como un problema del transporte como se hizo anteriormente.

  1. Un posible caso particular del problema del transporte sucede cuando hay muchos orígenes y únicamente un destino. Plantea esta posibilidad de manera general. En este caso, ¿cuál sería una buena estrategia para decidir cuáles orígenes deben enviar unidades del producto al destino?

Respuestas

1.- (Respuesta a criterio del lector)

2.- Si la demanda supera a la oferta, por lo menos uno de los destinos del problema va a cumplir que $\sum_{i=1}^{m}x_{ij} < d_j$, por lo que no cumplirá una de las restricciones de nuestro problema y el problema ya no será factible.

3.- En este caso, sería indistinto de donde elijamos enviar nuestras computadoras con tal de que se satisfaga la demanda, y solamente se parará de enviar computadoras cuando se satisfaga esta demanda de 800 computadoras, que en cualquier caso nos dará un costo total de envío de $24000.

4.- Nuestra variable de decisión va a ser la siguiente: $x_{ij}$ = miles de televisores del tamaño $i$ que van a ser exportados al país $j$, $i \in \{1 (\textrm{43″}), 2 (\textrm{50″}), 3 (\textrm{55″}), 4 (\textrm{65″})\}$, $j \in \{1 (\textrm{Japón}), 2 (\textrm{China}), 3 (\textrm{Estados Unidos})\}$

Si seguimos los pasos como lo hemos venido haciendo, el problema debería quedar planteado de la siguiente manera:

\begin{align*}
Min \quad z = &50x_{11} + 60 x_{12} + 80x{13} + 60 x_{21} + 70 x_{22} + 90x_{23}\\
+ &65x_{31} + 75x_{32} + 95x_{33} + 70x_{41} + 80x_{42} + 100x_{43}\\
&s.a\\
&x_{11} + x_{21} + x_{31} + x_{41} \geq 100\\
&x_{12} + x_{22} + x_{32} + x_{42} \geq 300\\
&x_{13} + x_{23} + x_{33} + x_{43} \geq 350\\
&x_{11} + x_{12} + x_{13} \leq 250\\
&x_{21} + x_{22} + x_{23} \leq 220\\
&x_{31} + x_{32} + x_{33} \leq 180\\
&x_{41} + x_{42} + x_{43} \leq 150\\
&x_{ij} \in \mathbb{N}\\
\end{align*}

5.- Como solamente habría un destino, la variable de decisión sería la siguiente:
$x_i$ = unidades de producto que vamos a enviar del origen $i$ a nuestro destino, $i \in \{1, \ldots, m\}$

Sea $d$ la demanda de nuestro único destino.

El planteamiento general sería el siguiente:

\begin{align*}
Min \quad z &= \sum_{i=1}^{m} c_{i}x_{i}\\
s.a.&\\
x_i &\leq o_i, \quad i \in \{1, \ldots , m\}\\
\sum_{i=1}^{m}x_i &\geq d\\
x_i &\geq 0 \quad i \in \{1, \ldots , m\}\\
\end{align*}

Una buena estrategia para resolver el problema simplemente sería ir agotando las unidades que nos puede proporcionar cada origen empezando por los que nos dan el menor costo de transporte por unidad, y parar justo cuando se haya cumplido la demanda de este único destino.

Entradas relacionadas

Investigación de Operaciones: El problema de la mochila

Por Aldo Romero

Deja un comentario

Introducción

En la entrada anterior hablamos del problema de la dieta, en donde queríamos cumplir ciertas restricciones alimenticias creando un menú de bajo costo. En esta entrada veremos otro ejemplo conocido de PPL: el problema de la mochila. La idea general es que queremos transportar ciertos bienes mediante un contenedor que tiene cierta capacidad. Este contenedor puede ser algo tan sencillo como una mochila, o algo tan complicado como un tren. A continuación veremos un ejemplo intermedio.

Ejemplo del problema de la mochila

Cesar es un fabricante de botanas que vende 3 de sus productos a varios distribuidores dentro de su localidad. Cada caja de sus productos tiene un peso diferente y generan diferentes ganancias al ser vendidas. Esta información está reflejada en la siguiente tabla:

—Peso por caja
en kilogramos		Ganancia en pesos
por caja vendida
Producto 110150
Producto 212200
Producto 315300

Cesar tiene una camioneta que aguanta hasta 800 kilos de carga sin contar al conductor. Cesar quiere saber cuales son los productos que debe llevar con tal de maximizar sus ganancias.

Variables de decisión

Nuestra variable de decisión es bastante intuitiva.

$x_i$ = número de cajas del producto $i$ que Cesar va a llevar en su camioneta. $i \in \{1, 2, 3\}$

Función objetivo

Como el objetivo de Cesar es maximizar las ganancias, la función objetivo va a ser:

$$Max \quad z = 150x_1 + 200x_2 + 300x_3$$

Restricciones

En este problema, la única condición que nos dan es que el peso total de las cajas a llevar no exceda la capacidad de carga de la camioneta. Es decir:

\begin{align*}
10x_1 + 12x_2 + 15x_3 \leq 800\\
x_i \geq 0, i \in \{1, 2, 3\}\\
\end{align*}

Resumen

El PPL que obtenemos es en resumen:

\begin{align*}
Max \quad z= 150x_1&+ 200x_2 + 300x_3\\
s.a.&\\
10x_1&+12x_2+15x_3 \leq 800\\
x_i& \geq 0,i \in \{1, 2, 3\}\\
\end{align*}

Formulación general del problema de la mochila

Un modelo como el anterior recibe el nombre de problema de la mochila pues originalmente fue formulado del siguiente modo: un excursionista desea determinar la cantidad de latas de ciertos comestibles que llevará en su mochila. Las latas tienen cierto peso $p_i$, cierto valor $v_i$ para el excursionista y su mochila tiene capacidad $P$. Si hay $n$ alimentos disponibles y usamos como variables de decisión a $x_1,\ldots,x_n$, donde $x_i$ es el número de latas de alimento $i$ que el excursionista llevarán, entonces el problema de la mochila es:

\begin{align*}
Max \quad z &= \sum_{n}^{i=1} v_ix_i\\
s.a.&\\
\sum_{n}^{i=1} p_ix_i &\leq P\\
x_i &\geq 0, x_i \in \mathbb Z, i=1, \ldots, n.\\
\end{align*}

Este es un problema de programación lineal, pero más específicamente se le conoce como un problema de programación lineal entera (PPLE), o bien un modelo lineal entero, pues las variables $x_i$ están sujetas a tomar sólo valores en los números enteros. Sorpresivamente, aunque los problemas de programación entera parezcan «más fáciles» dado que sus posibilidades están más restringidas, esto no es así. Han sido objeto de mucho estudio pues agregar la condición de integralidad (que las variables sean enteras) crea complicaciones adicionales y hacen que los métodos generales no funcionen tan bien. Los problemas de programación lineal entera son difíciles incluso en términos de una noción computacional muy precisa del tiempo requerido para obtener la mejor solución.

Más adelante…

Aún tenemos algunos problemas conocidos por explorar. El siguiente que veremos es el problema del transporte, en donde queremos saber cómo distribuir productos a través distintas posibilidades de transporte para economizar costos.

En algunas entradas más también hablaremos de cómo llevar cualquier PPL a una forma estándar, que nos permitirá desarrollar la teoría general necesaria para resolverlo.

Tarea

  1. Imagina el siguiente escenario:
    Cesar ahora solo vende los productos 1 y 2. El producto 1 ahora pesa 8 kilogramos y el producto 2 ahora pesa 10 kilogramos, que el primero de ellos da una ganancia de \$120 y que el segundo da una ganancia de \$155. El vehículo que tenemos ahora es un coche que sólo puede cargar 392 kilogramos. ¿Cómo cargarías en este caso el coche para maximizar las ganancias? Plantea el PPLE e intenta resolver el problema con las herramientas con las que cuentes hasta ahora.
  2. Para entender un poco el problema binario de la mochila, considera el siguiente ejemplo. Se tienen 7 posibles artículos con pesos de 7, 10, 12, 4, 5, 9, 11 kilos y con valor de 23, 25, 28, 17, 19, 25, 26 respectivamente. Sólo podemos decidir si llevar o no llevar cada artículo, y el peso total que se cargará no puede exceder 40 kilos. ¿Cuáles artículos hay que llevar para maximizar el valor? Plantea el PPLE e intenta resolverlo con las herramientas con las que cuentes hasta ahora.
  3. Considera el problema ejemplo original de esta entrada de blog. ¿Qué pasaría con la respuesta del problema si ocurrieran los siguientes escenarios? ¿Las ganancias aumentarán o disminuirán?
    • Cesar compró una mejor camioneta, que ahora puede transportar 1.5 toneladas.
    • El producto 3 se volvió más caro y ahora Cesar solo gana 250 pesos por caja vendida.
    • El tipo de envoltura y material de la caja cambio, por lo que ahora los pesos de los productos son 12, 17, 25 kilos para los productos 1, 2 y 3 respectivamente.

Respuestas

1.- Podríamos calcular cual es el producto que nos da más ganancias por kilo con una simple división. El producto 1 nos da 120/8 = 15 pesos por kilo del producto y el producto 2 nos da 155/10 = 15.5 pesos por kilo. El producto 2 es el que más ganancias nos va a dar por lo que vamos a llenar el carro con la mayor cantidad de productos 1 que se pueda.
Lo máximo que podemos meter dentro del carro son 39 unidades del producto 2, teniendo una ganancia de 6045 pesos, pero nos sobrarían 2 kilos para llegar al límite de peso. Entonces vamos a tratar de considerar las opciones donde incluyamos algunas unidades del producto 1 y a ver si podemos mejoran las ganancias.
Si tomamos 38 unidades del producto 2, nos quedan 12 kilos de capacidad y solamente podemos solamente agregar una unidad del producto 1, teniendo en total una ganancia de 6010 pesos. Esta opción no mejora las ganancias.
Si tomamos 37 unidades del producto 2 nos quedan 22 kilos de capacidad y solamente podemos agregar dos unidades del producto 1, teniendo una ganancia de 5975 pesos. Esta opción tampoco mejora las ganancias.
Ahora, si tomamos 36 unidades del producto 2, nos quedan 32 kilos de capacidad y ahora podemos agregar 4 unidades del producto 1, teniendo ahora una ganancia de 6060 pesos. En este caso SI conseguimos una mejora en nuestras ganancias.
Y si somos observadores, nos daremos cuenta que si seguimos agregando unidades del producto 1, ahora las ganancias solo van a ir disminuyendo, por lo que nos quedaremos con esta última solución para nuestro problema.

2.- La variable de decisión sería como el visto en esta entrada, con la siguiente variante: $x_i$ = 1 si el articulo i se va a llevar o 0 si el articulo i no se va a llevar.

La función objetivo simplemente va a ser la que maximice el valor total de los artículos a llevar:

$$Max z = 23x_1 + 25x_2 + 28x_3 + 17x_4 + 19x_5 + 25x_6 + 26x_7$$

Y la única restricción es:

$$7x_1 + 10x_2 + 12x_3 + 4x_4 + 5x_5 + 9x_6 + 11x_7 \leq 40$$

Entonces, el problema planteado sería:

\begin{align*}
Max z = &23x_1 + 25x_2 + 28x_3 + 17x_4 + 19x_5 + 25x_6 + 26x_7\\
&s.a\\
&7x_1 + 10x_2 + 12x_3 + 4x_4 + 5x_5 + 9x_6 + 11x_7 \leq 40\\
&x_i \geq 0, i \in {1, \ldots, 7}\\
\end{align*}

Y el modo de resolverlo es muy similar al anterior, solo hay que considerar los cocientes de los artículos que dan más valor por cada kilo que pesan, tomar los mejores y si sobra capacidad de peso, probar combinaciones de tal manera que el se elimine esa capacidad restante y evaluar si el valor sube en efecto o hasta baja.

3.- $\bullet$ La solución va a ser similar a el problema 1, se va a llenar la camioneta con el producto que ofrezca la mayor ganancia/kilo (el producto 3) y si sobra capacidad de carga se va a intentar introducir algunos los productos de menor peso, hasta encontrar la solución que nos de las mayores ganancias. La diferencia solo va a ser en el número de unidades que van a entrar en la camioneta y por tanto, la solución aunque sea análoga, va a ser diferente.

$\bullet$ Como la ganancia del producto de mayor ganancia/kilo cambió, ahora hay que comparar este nuevo valor con el de los otros productos y nos daremos cuenta que ahora tendremos la misma ganancia/kilo entre este producto y el producto número 2, entonces lo que se intentará es llenar la camioneta entre estos dos productos de tal manera que no quede capacidad de carga sobrante.

$\bullet$ Hay que calcular la nueva ganancia/kilo de cada producto y resulta ahora que al cambiar los pesos de las cajas, el producto 1 es el que mayor ganancia/kilo tiene, entonces vamos a tratar de incluir la mayor cantidad de unidades de este producto que sea posible y si sobra capacidad tratar de combinar con algunas unidades de los otros productos con tal de tener la ganancia más grande.

Entradas relacionadas