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

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 (7)

Por Aldo Romero

Deja un comentario

Introducción

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

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

Ejemplo del problema de producción e inventario

Una 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 5 meses de lanzamiento.

Meses transcurridos a
partir del lanzamiento		01234
Demanda en miles de copias
del mes en curso		8065503010
Productividad disponible del
mes en curso		11560402010

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

El costo de producción de cada copia es de \$20. El costo de almacenamiento en las tiendas donde distribuyen sus juegos es de \$2000 por cada mil copias almacenadas. 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 el número de copias que se van a producir el mes en curso desde su lanzamiento.

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

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 + x_4 + x_5)$$.

Restricciones del problema de producción e inventario

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

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

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

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

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

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

Si reescribimos esta restricción obtenemos

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

Análogamente:

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

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

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

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

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

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

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

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

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

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

En resumen, el PPL que obtenemos es:

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

Más adelante…

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

Tarea moral

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

Entradas relacionadas

Investigación de Operaciones (6): 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 moral

  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?

Entradas relacionadas

Investigación de Operaciones (5): 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 satisfacer 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\}\\

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.

Un caso particular de este modelo, también difícil de resolver, es el problema binario de la mochila en el cual las variables sólo pueden tomar los valores $0$ o $1$. Esto se traduce, en el caso de la excursión, simplemente a decidir si se incluye o no una lata de alimento $i$.

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 distrubuir 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 moral

  1. Para entender un poco las dificultades de los PPLE considera el siguiente ejemplo. Imagina que el saco de arroz pesa 5 kilogramos, que el saco de azucar pesa 3 kilogramos, que el primero de ellos da un ahorro de \$12 y que el segundo da un ahorro de \$10. El vehículo que tenemos ahora es un coche que sólo puede cargar 300 kilogramos. ¿Cómo cargarías en este caso el coche para maximizar el ahorro? 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 10 posibles artículos con peso $7,10,12,4,5,9,11$ y con valor correspondiente $23,25,28,17,19,25,26$. Sólo podemos decidir si llevar o no llevar cada artículo, y el peso total que se cargará no puede exceder $40$. ¿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 de la entrada. ¿Qué crees que pase con la respuesta del problema si pasan las siguientes cosas? ¿El ahorro óptimo aumentará o dismunuirá? Considera cada caso por separado, uno por uno.
    • El programa compró una mejor camioneta, que ahora puede transportar 2.5 toneladas.
    • El café se volvió más caro y ahora cada saco sólo ahorra 25 pesos al consumidor.
    • La fábrica de frijol ya cambió las presentaciones de sus productos y ahora sólo vende sacos de 30 kilos, que le dan un ahorro de 50 pesos al comprador.
    • Por una nueva política de salud, se quitó el azucar de los productos beneficiados por el programa social.
  4. ¿Notaste que en la entrada anterior no dimos la formulación general del problema de la dieta, sino sólo un ejemplo? Es tu turno de plantear una versión general. Regresa a la entrada anterior y plantea la versión general del problema de la dieta.

Entradas relacionadas