Archivo del Autor: Aldo Romero

Investigación de Operaciones: Soluciones básicas, factibles y no degeneradas (10)

Por Aldo Romero

Introducción

Ya hablamos de qué es la forma canónica y la forma estándar de un problema lineal. Como platicamos, esto nos permitirá llevar los problemas que nos interesan a ciertas formas especiales a las que podremos aplicarles algunos métodos más adelante. Lo que haremos ahora es comenzar a pensar en qué quiere decir resolver un problema lineal. Para ello, recordaremos de distintos tipos de soluciones que los problemas lineales pueden tener.

Tipos de soluciones y región de factibilidad

En esta sección recordaremos los conceptos de soluciones factibles, soluciones básicas factibles (degeneradas y no degeneradas) y de región de factibilidad.

Supongamos que tenemos un problema de programación lineal en su forma canónica:

$\begin{aligned} M a x z & = c \cdot x \\ s . a . \\ A x & \leq b \\ x & \geq 0, \end{aligned}$

donde usamos la misma notación que en la entrada anterior, pero donde tomaremos $l$ variables de decisión. En particular, $x, c$ son vectores en $R^{n}$ , $b$ es un vector en $R^{m}$ y $A$ es una matriz de entradas reales de $m \times n$ . Recuerda que en la expresión anterior entendemos $0$ como el vector en $R^{n}$ con entradas todas iguales a cero.

Este problema también tiene una forma estándar, en donde transformamos las desigualdades en igualdades introduciendo variables de sobra y de holgura.
$\begin{aligned} M a x z & = c \cdot x \\ s . a . \\ A^{'} x^{'} & = b \\ x^{'} & \geq 0, \end{aligned}$

en donde en hemos agregado $n - m$ variables de holgura al vector $x$ , para obtener un vector $x^{'}$ en $R^{n}$ , así como $n - m$ columnas a $A$ para volverla una matriz en de $m \times n$ , para agregar los coeficientes de las variables de holgura que hacen que se de la igualdad.

Como recordatorio, tenemos las siguientes definiciones para los tipos de soluciones del problema lineal.

Definición. Una solución factible al problema lineal en forma canónica dado anteriormente es un vector columna $x = (\begin{matrix} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{matrix})$ que satisface las restricciones $A x \leq b$ y $x \geq 0$ . Esto se corresponde con una solución $x^{'}$ al problema en forma estándar que satisface $A^{'} x^{'} = b$ y $x^{'} \geq 0$ .

Definición. La región de factibilidad del problema lineal en forma canónica es el conjunto de todas las soluciones factibles.

De entre las soluciones factibles, hay algunas que son un poco más sencillas, en el sentido de que varias de sus entradas son iguales a cero pensadas como soluciones del problema en forma estándar. En las siguientes definiciones suponemos que el rango de la matriz $A^{'}$ es exactamente igual a $m$ .

Definición. Una solución básica factible es una solución factible $x$ correspondiente a una solución $x^{'}$ del problema en forma estándar con no más de $m$ componentes positivas. En otras palabras, $x^{'}$ tiene al menos $n - m$ entradas iguales a cero.

Definición. Una solución básica factible no degenerada es una solución factible $x$ correspondiente a una solución $x^{'}$ del problema en forma estándar con exactamente $m$ componentes positivas. En otras palabras, $x^{'}$ tiene exactamente $n - m$ entradas iguales a cero.

Definición. Una solución básica factible degenerada es una solución factible $x$ correspondiente a uan solución $x^{'}$ del problema en forma estándar con menos de $m$ componentes positivas. En otras palabras, $x^{'}$ tiene más de $n - m$ entradas iguales a cero.

La importancia de las soluciones básicas factibles y no degeneradas es que cumplen las siguientes:

Se puede mostrar que si un problema de programación lineal tiene óptimo, entonces dicho óptimo se alcanza para alguna solución básica factible y no degenerada.
Las soluciones básicas factibles y no degeneradas se pueden encontrar resolviendo sistemas de ecuaciones.
Geométricamente, las soluciones básicas factibles y no degeneradas están en vértices de la región de factibilidad.

A continuación explicaremos algunos de estos puntos con un ejemplo detallado, que te ayudará a entender la intuición detrás de estas definiciones y de su importancia.

Ejemplos de región de factibilidad y tipos de solución

Consideremos el siguiente problema de programación lineal:

$\begin{aligned} M a x . z & = 2 x_{1} + 3 x_{2} \\ s . a . \\ \begin{array}{c} 2 x_{1} & + x_{2} & \leq & 4 \\ x_{1} & + 2 x_{2} & \leq & 5 \end{array} \\ x_{1}, x_{2} \geq 0. \end{aligned}$

Antes de comenzar a estudiar la región de factibilidad, debemos verificar que está en forma canónica. En efecto, todo está en orden: el problema es de maximización, las desigualdades son $\leq$ y a las variables de decisión se les pide ser no negativas.

La región de factibilidad es el conjunto de todos los $(x_{1}, x_{2})$ (en el plano $R^{2}$ ) que cumplen las restricciones del problema, es decir, $2 x_{1} + x_{2} \leq 4$ , $x_{1} + 2 x_{2} \leq 5$ , $x_{1} \geq 0$ y $x_{2} \geq 0$ . Para entender esto mejor, lo podemos pensar en cuatro regiones:

Región 1: La región $x_{1} \geq 0$ , que queda a la derecha del eje $y$ .

Región 2: La región $x_{2} \geq 0$ , que queda arriba del eje $x$ .

Región 3: La región $2 x_{1} + x_{2} \leq 4$ , que queda debajo de la recta $2 x_{1} + x_{2} = 4$ .

Región 4: La región $x_{1} + 2 x_{2} \leq 5$ , que queda por debajo de la recta $x_{1} + 2 x_{2} = 5$ .

Como queremos que $(x_{1}, x_{2})$ satisfaga todas las restricciones simultáneamente, necesitamos que esté en la intersección de todas las regiones. Así, la región de factibilidad es en la que se intersectan todas estas regiones que acabamos de dibujar. Al sobreponerlas, obtenemos la región encerrada en la siguiente figura:

Si gustas, puedes también explorar el interactivo de GeoGebra en donde se han coloreado los complementos de las regiones para más claridad. Puedes usar el cursor para mover la figura y las herramientas de lupa para hacer acercamientos y alejamientos.

La intuición que debemos tener ahora es que el máximo de la función objetivo $2 x_{1} + 3 x_{2}$ se tiene que alcanzar en alguno de los vértices del cuadrilátero que es la región factible. A grandes rasgos, estos vértices serán las soluciones básicas factibles y no degeneradas. Veamos dónde el álgebra nos dice esto.

Para ello, pensemos al problema en su forma estándar, tomando variables de holgura $s_{1}$ y $s_{2}$ . Las restricciones que tienen las cuatro variables en conjunto son las siguientes.

$\begin{aligned} 2 x_{1} + x_{2} + s_{1} & = 4 \\ x_{1} + 2 x_{2} + s_{2} & = 5 \\ x_{1}, x_{2}, s_{1}, s_{2} & \geq 0. \end{aligned}$

La matriz $A^{'}$ es $(\begin{matrix} 2 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \end{matrix})$ , que puedes verificar que tiene rango $2$ . Las soluciones básicas y no degeneradas corresponden a tener en ese sistema de ecuaciones exactamente $m = 2$ variables positivas, de manera que necesitamos hacer exactamente $n - m = 4 - 2 = 2$ de estas variables iguales a cero. Al hacer esto, podemos resolver para las $m = 2$ variables restantes. Por ejemplo, si establecemos $x_{1} = 0$ y $x_{2} = 0$ , las ecuaciones se convierten en

$\begin{array}{r} s_{1} = 4 \\ s_{2} = 5 \\ x_{1}, x_{2}, s_{1}, s_{2} \geq 0, \end{array}$

que tiene solución única $(x_{1}, x_{2}, s_{1}, s_{2}) = (0, 0, 4, 5)$ . Así, la solución básica del problema en forma canónica es $(x_{1}, x_{2}) = (0, 0)$ . Hay que recordar dar la solución básica ya sólo para las variables originales, es decir, las del problema en forma canónica.

Esta solución corresponde al punto $C$ del interactivo de GeoGebra. Se puede determinar otra solución básica fijando $s_{1} = 0$ y $s_{2} = 0$ , donde el sistema sería ahora

$\begin{array}{r} 2 x_{1} + x_{2} = 4 \\ x_{1} + 2 x_{2} = 5 \\ x_{1}, x_{2}, s_{1}, s_{2} \geq 0, \end{array}$

y tras resolver las dos ecuaciones, la solución básica que se obtiene es $(x_{1}, x_{2}) = (1, 2)$ , que es el punto $A$ del interactivo de GeoGebra.

Podemos seguir haciendo esto. Si consideramos todas las posibilidades en las que dos variables son cero y resolvemos las ecuaciones resultantes, eso nos dará puntos $(x_{1}, x_{2})$ en el plano. La solución óptima es la solución básica factible (punto de esquina) con el mejor valor objetivo.

En este ejemplo tenemos $(\binom{4}{2}) = \frac{4!}{2! 2!} = 6$ formas de volver dos de las $n$ variables iguales a cero. Ya para las variables $x_{1}$ y $x_{2}$ , los puntos que obtenemos son los puntos $A$ , $B$ , $C$ , $D$ que son vértices de la región de factibilidad. Los puntos $E$ y $F$ del interactivo también son puntos básicos y no degenerados (son las otras dos intersecciones de las rectas que dibujamos), pero como no satisfacen la condición de factibilidad del problema, entonces no los podemos considerar y por lo tanto no son candidatos a dar el valor óptimo.

La siguiente tabla muestra todas las soluciones básicas y no básicas de este ejemplo:

Variables no básicas (cero)	Variables básicas	Solución para $(x_{1}, x_{2})$	Punto de esquina asociado	¿Factible?	Valor objetivo z
$(x_{1}, s_{1})$	$(s_{1}, s_{2})$	$(0, 0)$	C	Sí	0
$(x_{1}, s_{1})$	$(x_{2}, s_{2})$	$(0, 4)$	E	No	___
$(x_{1}, s_{2})$	$(x_{2}, s_{1})$	$(0, 2.5)$	D	Sí	7.5
$(x_{2}, s_{1})$	$(x_{1}, s_{2})$	$(2, 0)$	B	Sí	4
$(x_{2}, s_{2})$	$(x_{1}, s_{1})$	$(5, 0)$	F	No	___
$(s_{1}, s_{2})$	$(x_{1}, x_{2})$	$(1, 2)$	A	Sí	8 (óptimo)

Más adelante…

Notemos que a medida que el tamaño del problema se incrementa, enumerar todos los puntos esquina se volverá una tarea que tomaría mucho tiempo. Por ejemplo, si tuviéramos $20$ variables (ya con las de holgura) y $10$ restricciones, es necesario resolver considerar $(\binom{20}{10}) = 184756$ formas de crear ecuaciones de $10 \times 10$ , y resolver cada una de ellas. Aunque esto es finito, son demasiadas operaciones. Y este en la práctica incluso es un ejemplo pequeño, ya que en la vida real hay problemas lineales que pueden incluir miles de variables y restricciones.

Por ello, se vuelve cruciar encontrar un método que atenúe esta carga computacional en forma drástica, que permita investigar sólo un subconjunto de todas las posibles soluciones factibles básicas no degeneradas (vértices de la región de factibilidad), pero que garantice encontrar el óptimo. Una idea intuitiva que debería servir es comenzar en un vértice y «avanzar en una dirección que mejore la función objetivo». Esto precisamente es la intuición detrás del método simplex, que repasaremos a continuación.

Tarea moral

Considera el siguiente problema lineal en su forma canónica:

$\begin{aligned} M a x z & = 2 x_{1} + 3 x_{2} \\ s . a . \\ \begin{array}{c} x_{1} & + 3 x_{2} & \leq & 6 \\ 3 x_{1} & + 2 x_{2} & \leq & 6 \end{array} \\ x_{1}, x_{2} \geq 0. \end{aligned}$

Sigue los pasos descritos arriba para encontrar todas sus soluciones básicas factibles y no degeneradas. Usa ello para encontrar el óptimo del problema.

Actualiza las restricciones en el interactivo de GeoGebra que se compartió en la entrada para visualizar este problema y confirmar tus cuentas del ejercicio anterior. Para ello, deberás ir al apartado «Álgebra» del interactivo y modificar los objetos $a$ y $b$ .
Considera un problema de optimización lineal en dos variables $x$ y $y$ , en forma canónica y con $m$ restricciones (desigualdades), además de las restricciones $x \geq 0$ y $y \geq 0$ . Explica por qué la región de factibilidad siempre es un polígono con a lo más $m + 2$ lados, y por qué entonces basta evaluar la función objetivo en a lo más $m + 2$ puntos para encontrar su máximo.
¿Cómo se vería la región de factibilidad de un problema de optimización lineal de maximización que no tenga máximo? Explica todas las posibilidades y da ejemplos.
Intenta usar las ideas de esta entrada para resolver los problemas de optimización lineal clásicos que hemos descrito en entradas anteriores.

Entradas relacionadas

Ir a Investigación de Operaciones
Entrada anterior del curso: Forma canónica y forma estándar de un problema lineal
Entrada siguiente del curso:

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:

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

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

$\begin{aligned} M a x z & = c_{1} x_{1} + \dots + c_{n} x_{n} \\ s . a . \\ \begin{array}{c} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} \leq b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} \leq b_{2} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} \leq b_{n} \end{array} \\ x_{1} \geq 0, x_{2} \geq 0, \dots, x_{n} \geq 0. \end{aligned}$

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

$\begin{aligned} M a x z & = c \cdot x \\ s . a . \\ A x & \leq b \\ x & \geq 0, \end{aligned}$

en donde:

$c = (c_{1}, \dots, c_{n}) \in R^{n}$ es el vector de costos (vector renglón)
$x = (x_{1}, \dots, x_{n}) \in R^{n}$ es el vector de variables de decisión (vector columna),
$A = [a_{i j}]$ es la matriz de restricciones, que es una matriz de $m \times n$ y
$b = (b_{1}, \dots, b_{m}) \in R^{m}$ es el vector de constantes que acotan las combinaciones lineales de variables.
Entendemos $0$ como el vector en $R^{n}$ que consiste de puras entradas iguales a cero.

Todo problema de programación lineal puede ser expresado en forma canónica; es decir, puede definirse un problema en forma canónica equivalente a él, en el sentido de que la solución de uno nos permite encontrar la solución del otro de manera sencilla. En efecto:

Si el problema es de minimización, puede considerarse en vez de $z$ la función $z^{'} = - z$ y en el problema equivalente se busca maximizar $z^{'}$ .
Si una restricción es del tipo $\geq$ puede ser mutiplicada por -1 para obtener una del tipo $\leq$ .
Una ecuación puede ser substituida por una desigualdad del tipo $\leq$ y otra del tipo $\geq$ . Luego, la del tipo $\geq$ puede ser substituida por una del tipo $\leq$ como en el punto anterior.
Para una variable $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}^{*}$ tales que $x_{i}^{'} - x_{i}^{*} = x_{i}$ . Para cualquier $x_{i}$ dado podemos construir dichas variables, y viceversa, para $x_{i}^{'}$ y $x_{i}^{*}$ se puede construir $x_{i}$ .

Ejemplo de pasar un problema a forma canónica

Transformaremos el siguiente problema a su forma canónica.
$\begin{aligned} M i n z & = x_{1} - 3 x_{2} + 7 x_{3} \\ s . a . \\ \begin{array}{c} 3 x_{1} & + x_{2} & + 3 x_{3} & \leq 40 \\ x_{1} & + 9 x_{2} & - 7 x_{3} & \geq 50 \\ 5 x_{1} & + 3 x_{2} & = 20 \\ 5 x_{2} & + 8 x_{3} & \leq 80 \end{array} \\ x_{1}, x_{2} \geq 0, x_{3} l i b r e . \end{aligned}$

Primeramente se definen las variables no negativas $x_{3}^{'}$ y $x_{3}^{*}$ , tales que $x_{3}^{'} - x_{3}^{*} = x_{3}$ , con objeto de satisfacer el punto (3) de la definición. Para satisfacer el punto (1) se considera la función:
$\begin{aligned} z^{'} & = - z \\ = - x_{1} + 3 x_{2} - 7 x_{3} \\ = - x_{1} + 3 x_{2} - 7 x_{3}^{'} + 7 x_{3}^{*} \end{aligned}$

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}^{*}$ ); la segunda desigualdad se multiplica por $- 1$ para obtener una del tipo $\leq$ : $x_{1} + 9 x_{2} - 7 x_{3} \geq 50 \Leftrightarrow - x_{1} - 9 x_{2} + 7 x_{3} \leq - 50.$

Substituyendo las nuevas variables se obtiene: $- x_{1} - 9 x_{2} + 7 x_{3}^{'} - 7 x_{3}^{*} \leq - 50.$

Para la tercera desigualdad se tiene lo siguiente:

$\begin{aligned} 5 x_{1} + 3 x_{2} & = 20 \\ \Leftrightarrow \\ 5 x_{1} + 3 x_{2} \leq 20 & y 5 x_{1} + 3 x_{2} \geq 20 \\ \Leftrightarrow \\ 5 x_{1} + 3 x_{2} \leq 20 & y - 5 x_{1} - 3 x_{2} \leq - 20. \end{aligned}$

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

$\begin{aligned} M a x z^{'} & = - x_{1} + 3 x_{2} - 7 x_{3}^{'} + 7 x_{3}^{*} \\ s . a . \\ \begin{array}{c} 3 x_{1} & + x_{2} & + 3 x_{3}^{'} & - 3 x_{3}^{*} & \leq & 40 \\ - x_{1} & - 9 x_{2} & + 7 x_{3}^{'} & - 7 x_{3}^{*} & \leq & - 50 \\ 5 x_{1} & + 3 x_{2} & \leq & 20 \\ - 5 x_{1} & - 3 x_{2} & \leq & - 20 \\ 5 x_{2} & + 8 x_{3}^{'} & - 8 x_{3}^{*} & \leq & 80 \end{array} \\ x_{1}, x_{2}, x_{3}^{'}, x_{3}^{*} \geq 0. \end{aligned}$

Forma estándar de un problema lineal

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

Todas las restricciones son ecuaciones.
Todas las variables son no negativas.
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{aligned} M a x (o M i n) z & = c_{1} x_{1} + \dots + c_{n} x_{n} \\ s . a . \\ \begin{array}{c} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} = b_{2} \\ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + \dots + a_{m n} x_{n} = b_{n} \\ x_{1} \geq 0, x_{2} \geq 0, \dots, x_{n} \geq 0. \end{array} \end{aligned}$

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

$\begin{aligned} M a x (o M i n) z & = c x \\ s . a . \\ A x & = b \\ x & \geq 0 \end{aligned}$

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

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

Ejemplo de pasar un problema a forma estándar

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

$\begin{aligned} M i n z & = x_{1} - 3 x_{2} + 7 x_{3} \\ s . a . \\ \begin{array}{c} 3 x_{1} & + x_{2} & + 3 x_{3} & \leq 40 \\ x_{1} & + 9 x_{2} & - 7 x_{3} & \geq 50 \\ 5 x_{1} & + 3 x_{2} & = 20 \\ 5 x_{2} & + 8 x_{3} & \leq 80 \end{array} \\ x_{1}, x_{2} \geq 0, x_{3} l i b r e . \end{aligned}$

Vamos a expresarlo ahora en forma estándar. Como lo hicimos anteriormente, hacemos la sustitución $x = x_{3}^{'} - x_{3}^{*}$ 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 finalmente, 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{aligned} M i n z & = x_{1} - 3 x_{2} + 7 x_{3}^{'} - 7 x_{3}^{*} \\ s . a . \\ \begin{array}{c} 3 x_{1} & + x_{2} & + 3 x_{3}^{'} & - 3 x_{3}^{*} & + x_{4} & = & 40 \\ x_{1} & + 9 x_{2} & - 7 x_{3}^{'} & + 7 x_{3}^{*} & - x_{5} & = & 50 \\ 5 x_{1} & + 3 x_{2} & = & 20 \\ 5 x_{2} & + 8 x_{3}^{'} & - 8 x_{3}^{*} & + x_{6} & = & 80 \end{array} \\ x_{1}, x_{2}, x_{3}^{'}, x_{3}^{*}, x_{4}, x_{5}, x_{6} \geq 0. \end{aligned}$

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

¿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?
Transforma el siguiente problema de programación lineal a su forma canónica y a su forma estándar:
$\begin{aligned} M a x z & = - 2 x_{1} + 3 x_{2} - 2 x_{3} \\ s . a . \\ \begin{array}{c} 4 x_{1} & - x_{2} & - 5 x_{3} & = & 10 \\ 2 x_{1} & + 3 x_{2} & + 2 x_{3} & \geq & 12 \end{array} \\ x_{1} \geq 0, x_{2}, x_{3} i r r e s t r i c t a s . \end{aligned}$
Revisa nuevamente las entradas anteriores y encuentra las formas canónicas y formas estándar de los problemas que hemos planteado hasta ahora.
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}, \dots, x_{n}$ que optimiza el problema original está asociada a una solución de su forma estándar (o canónica) y viceversa.
Imagina que tenemos un sistema de ecuaciones de la forma $A x = B$ con $A$ matriz en $M_{m, n} (R)$ y $b$ vector en $R^{m}$ . Queremos encontrar de todas las posibles soluciones al sistema aquella que minimiza la suma de las entradas de $x$ . Plantea esto como un problema lineal y transfórmalo a su forma canónica y a su forma estándar.

Entradas relacionadas

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

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.

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	0	1	2
Demanda en miles de copias del mes en curso	80	60	40
Productividad disponible del mes en curso	110	50	30

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:

$M i n 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:

$M i n z = 26000 x_{1} + 24000 x_{2} + 22000 x_{3} - 800000$

Restricciones del problema de producción e inventario

Primero, vayamos con las restricciones de oferta:

$\begin{array}{r} x_{1} \leq 110 \\ x_{2} \leq 50 \\ x_{3} \leq 30 \end{array}$

Después, vayamos con las restricciones de demanda:

$\begin{array}{r} x_{1} \geq 80 \\ x_{2} + (x_{1} - 80) \geq 60 \\ x_{3} + (x_{1} + x_{2} - 140) \geq 40 \end{array}$

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{aligned} M i n 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{aligned}$

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

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.
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?
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}, \dots, d_{n}$ por cada periodo.
2. Se tengan capacidades de producción $o_{1}, o_{2}, \dots, o_{n}$ unidades en cada periodo.
3. Se tengan costos $P$ y $A$ , de producir y almacenar una unidad de producto respectivamente.
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	0	1
Demanda en miles de copias del mes en curso	80	60
Productividad disponible del mes en curso	110	50

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:

$M i n z = 24000 x_{1} + 22000 x_{2} - 440000$

Las restricciones de oferta y de demanda serían:

$\begin{aligned} x_{1} & \leq 110 \\ x_{2} & \leq 50 \\ x_{1} & \geq 80 \\ x 2 + (x_{1} - 80) & \geq 60 \end{aligned}$

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

$\begin{aligned} M i n z & = 24000 x_{1} + 22000 x_{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{aligned}$

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}, \dots, d_{n}$ ) y oferta de productos ( $o_{1}, \dots, 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, \dots, n}$

Función objetivo:

$M i n z = P (x_{1} + \dots + x_{n}) + A [(x_{1} - d_{1}) + (x_{1} + x_{2} - d_{1} - d_{2}) + \dots + (\sum_{i = 1}^{n} x_{i} - \sum_{i = 1}^{n} d_{i})]$

Y por último, las restricciones serían:

$\begin{aligned} x_{1} & \leq o_{1} \\ x_{2} & \leq o_{2} \\ ⋮ \\ x_{n} & \leq o_{n} \\ x_{1} & \geq d_{1} \\ x_{1} + x_{2} - d_{1} & \geq d_{2} \\ ⋮ \end{aligned}$

$(\sum_{i = 1}^{n} x_{i} - \sum_{i = 1}^{n - 1} d_{i}) \geq \sum_{i = 1}^{n} d_{i}$

$x_{i} \geq 0, i \in {1, \dots, 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

Ir a Investigación de Operaciones
Entrada anterior del curso: El problema del transporte
Entrada siguiente del curso: El problema de la ruta más corta

Investigación de Operaciones: El problema del transporte (6)

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.

Origen	A	B	C
Oferta en unidades	200	350	470

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.

Destino	X	Y
Demanda en unidades	300	500

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.

	A	B	C
X	35	40	42
Y	44	37	45

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_{A X}$ 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_{i j}$ = 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 $35 x_{A X}$ , 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 $35 x_{A X} + 44 x_{A Y}$ . 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:

$M i n z = 35 x_{A X} + 44 x_{A Y} + 40 x_{B X} + 37 x_{B Y} + 42 x_{C X} + 45 x_{C Y} .$

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_{A X} + x_{A Y} \leq 200$ . De manera similar, con el almacén $B$ obtenemos que $x_{B X} + x_{B Y} \leq 350$ y con el almacén $C$ obtenemos que $x_{C X} + x_{C Y} \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_{A X} + x_{B X} + x_{C X} \geq 300$ y para la tienda $Y$ se tiene que cumplir $x_{A Y} + x_{B Y} + x_{C Y} \geq 500$ .

Entonces, juntando todas las restricciones, tenemos:

$\begin{array}{r} x_{A X} + x_{A Y} \leq 200 \\ x_{B X} + x_{B Y} \leq 350 \\ x_{C X} + x_{C Y} \leq 470 \\ x_{A X} + x_{B X} + x_{C X} \geq 300 \\ x_{A Y} + x_{B Y} + x_{C Y} \geq 500 \\ x_{i j} \in N, i \in {A, B, C}, j \in {X, Y} \end{array}$

Resumen de formulación del problema del transporte

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

$\begin{aligned} M i n z = 35 x_{A X} + 44 x_{A Y} + 40 x_{B X} & + 37 x_{B Y} + 42 x_{C X} + 45 x_{C Y} \\ s . a . \\ x_{A X} + x_{A Y} & \leq 200 \\ x_{B X} + x_{B Y} & \leq 350 \\ x_{C X} + x_{C Y} & \leq 470 \\ x_{A X} + x_{B X} + x_{C X} & \geq 300 \\ x_{A Y} + x_{B Y} + x_{C Y} & \geq 500 \\ x_{i j} \in N, i \in {A, B, C}, j \in {X, Y} \end{aligned}$

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, \dots, m$ ) y $d_{j}$ la demanda del destino $j$ en unidades del producto ( $j = 1, \dots, n$ ). Para cada origen $i$ y cada destino $j$ tiene cierto costo enviar una unidad de producto. Sea $c_{i j}$ el costo unitario de transporte del producto del origen $i$ al destino $j$ ( $i = 1, \dots, m; j = 1, \dots, n$ ).

Lo que buscamos es determinar para cada origen $i$ y cada destino $j$ cuántas unidades $x_{i j}$ 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}^{n} x_{i j} \leq o_{i},$

para cada $i = 1, \dots, 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_{i j} \geq d_{j},$

para cada $j = 1, \dots, 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{aligned} M i n z & = \sum_{i = 1}^{m} \sum_{j = 1}^{n} c_{i j} x_{i j} \\ s . a . \\ \sum_{j = 1}^{n} x_{i j} & \leq o_{i}, i = 1, \dots, m (1) \\ \sum_{i = 1}^{m} x_{i j} & \geq d_{j}, j = 1, \dots, n (2) \\ x_{i j} & \geq 0; i = 1, \dots, m; j = 1, \dots, n, \end{aligned}$

donde $x_{i j}$ es el número de unidades del producto a transportar del origen $i$ al destino $j$ , para cada $i = 1, \dots, m$ y cada $j = 1, \dots, 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

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.
¿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.
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?
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	$70k	100k
China	$60k	$70k	$75k	$80k	300k
Estados Unidos	$80k	$90k	$95k	$100k	350k
Disponibilidad	250k	220k	180k	150k	——

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.

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_{i j} < 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_{i j}$ = miles de televisores del tamaño $i$ que van a ser exportados al país $j$ , $i \in {1 (43″), 2 (50″), 3 (55″), 4 (65″)}$ , $j \in {1 (Japón), 2 (China), 3 (Estados Unidos)}$

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

$\begin{aligned} M i n z = & 50 x_{11} + 60 x_{12} + 80 x 13 + 60 x_{21} + 70 x_{22} + 90 x_{23} \\ + & 65 x_{31} + 75 x_{32} + 95 x_{33} + 70 x_{41} + 80 x_{42} + 100 x_{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_{i j} \in N \end{aligned}$

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, \dots, m}$

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

El planteamiento general sería el siguiente:

$\begin{aligned} M i n z & = \sum_{i = 1}^{m} c_{i} x_{i} \\ s . a . \\ x_{i} & \leq o_{i}, i \in {1, \dots, m} \\ \sum_{i = 1}^{m} x_{i} & \geq d \\ x_{i} & \geq 0 i \in {1, \dots, m} \end{aligned}$

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

Ir a Investigación de Operaciones
Entrada anterior del curso: El problema de la mochila
Entrada siguiente del curso: El problema de producción e inventario

Investigación de Operaciones: El problema de la ruta más corta (8)

Por Aldo Romero

Deja un comentario

Introducción

Veamos un último ejemplo de los problemas que podremos resolver con la teoría que desarrollaremos más adelante. Se conoce como el problema de la ruta más corta, y la idea es muy sencilla. Se tiene una red de localizaciones en un mapa. Hay algunos tramos que conectan localizaciones. Atravesar cada uno de ellos tiene cierto costo (asociado por ejemplo, con la distancia). Si nos dan un origen y un destino, ¿cómo podremos determinar el camino a seguir que nos lleve del origen al destino con el menor costo posible? Comencemos con un ejemplo concreto.

Ejemplo del problema de la ruta más corta

Supongamos que un empleado sale de trabajar a cierta hora de la noche y para regresar a su casa evalúa las posibles rutas a tomar en una aplicación móvil. La aplicación le indica algunas calles y avenidas que lo llevan de su trabajo (1) a su casa (7). Los vértices de en medio (2, 3, 4, 5 y 6) representan los cruces de calles por los que se transita en estas posibles rutas. También le indica cual es el tiempo que le tomará ir por cada calle o avenida en minutos, tomando en cuenta no solo la distancia, sino también el tráfico y los accidentes que se presentan. El empleado busca la ruta más rápida para poder llegar a su casa a descansar.

Una representación gráfica del problema presentado

Aunque parezca que este problema es muy geométrico, en realidad también se puede plantear en términos algebraicos, como veremos a continuación.

Variables de decisión del problema de la ruta más corta

En otros problemas hemos tenido variables de decisión que nos dicen cuánto producir, cuánto transportar, cuánto comer, etc. En esta caso, nuestras variables de decisión no representarán una cantidad, sino simplemente una decisión de «sí» o «no». Lo que haremos es establecer una variable $x_{i j}$ por cada uno de los posibles tramos del destino $i$ al $j$ , y será una variable binaria que indique la decisión de recorrer o no tal tramo. Si sí lo recorremos tendrá valor $1$ y si no, tendrá valor $0$ .

Por ejemplo si tomamos la ruta {1,2,3,7}, tendremos $x_{12} = x_{23} = x_{37} = 1$ , lo cual nos indicará que sí se recorren los tramos $(1, 2)$ , $(2, 3)$ , y $(3, 7)$ . Por otro lado, tomaremos $x_{i j} = 0$ para los demás tramos, que nos indicará que no se recorren.

Explícitamente, en nuestro ejemplo tomaremos variables $x_{i j}$ con $i < j$ , y tales que $(i, j)$ esté en el conjunto $A$ de todas las parejas $i < j$ para las cuales haya un tramo entre $i$ y $j$ (en cualquier dirección). La interpretación que les daremos será la siguiente:

$x_{i j} = {\begin{cases} 1 si se recorre el tramo (i, j) \\ 0 si no . \end{cases}$

Restricciones del problema de la ruta más corta

Ya establecidas las variables de decisión, lo que debemos hacer ahora es dar restricciones que hagan que los tramos elegidos definan una ruta.

Pensemos en qué sucede desde el trabajo. De ahí es donde debemos empezar. Solamente debemos tomar un tramo desde el trabajo, pues si pasamos por el trabajo más de una vez, en realidad nos podemos ahorrar esa vuelta que dimos de más para llegar más rápido a casa . Esto significa o que $x_{12} = 1$ , o que $x_{14} = 1$ , y sólo una de estas dos igualdades se cumple. Ya que las variables sólo serán $0$ ó $1$ , otra manera de escribir esto mismo es pedir que $x_{12} + x_{14} = 1.$

Del mismo modo, debemos garantizar que se llegue a casa por un solo tramo, que se puede escribir como $x_{37} + x_{57} + x_{67} = 1,$ o bien $- x_{37} - x_{57} - x_{67} = - 1.$

Para el resto de las zonas, debemos tomar en cuenta que si se entra a una, también se debe salir. Y si no se entra tampoco se sale. Veamos qué pasa, por ejemplo, con el cruce 2:

Si se entra entonces $x_{12} = 1$ . Deberá cumplirse entonces que $x_{23} = 1$ o $x_{26} = 1$ y sólo una de éstas.
Si no se entra entonces $x_{12} = 0$ . Deberá cumplirse entonces: $x_{23} = x_{26} = 0$ .

Podemos reescribir ambos casos anteriores de manera simplificada con la igualdad $x_{12} = x_{23} + x_{26},$ que también se puede escribir como $x_{23} + x_{26} - x_{12} = 0.$

Cada uno de los cruces $3, 4, 5, 6$ nos dan restricciones similares.

Función objetivo del problema de la ruta más corta

Finalmente, debemos determinar cuánto nos costará recorrer una ruta una vez fijas las variables de decisión. Esto es sencillo. Si el tramo de $i$ a $j$ tiene un costo de $c_{i j}$ , entonces recorrerlo nos costará $x_{i j} c_{i j}$ . En nuestro problema, la función objetivo quedaría como sigue:

$\begin{aligned} z & = 30 x_{12} + 20 x_{14} + 20 x_{23} + 8 x_{26} \\ + 10 x_{36} + 50 x_{37} + 20 x_{45} + 10 x_{56} \\ + 50 x_{57} + 30 x_{67} . \end{aligned}$

Resumen de formulación del problema de la ruta más corta

Así, el problema de ruta más corta que vimos como ejemplo queda descrito como sigue.
$\begin{aligned} z & = 30 x_{12} + 20 x_{14} + 20 x_{23} + 8 x_{26} \\ + 10 x_{36} + 50 x_{37} + 20 x_{45} + 10 x_{56} \\ + 50 x_{57} + 30 x_{67} . \end{aligned}$
$\begin{aligned} s . a . \\ x_{12} + x_{14} & = 1 \\ - x_{12} + x_{23} + x_{26} & = 0 \\ - x_{14} + x_{45} & = 0 \\ - x_{23} + x_{36} + x_{37} & = 0 \\ - x_{45} + x_{56} + x_{57} & = 0 \\ - x_{26} - x_{36} - x_{56} + x_{67} & = 0 \\ - x_{37} - x_{57} - x_{67} & = - 1 \\ x_{i j} = 0, 1 \forall (i, j) & \in A . \end{aligned}$

Este problema podría plantearse en general, bajo algunas condiciones sobre el tipo de mapas en los que se puede resolver. Este es un modelo lineal entero binario que tiene la propiedad de que puede ser resuelto eficientemente con algoritmos de programación lineal

Otro ejemplo de ruta más corta

La idea anterior puede servir no sólo para resolver problemas en donde nos interesen las distancias geográficas. En otros problemas, nos interesa llegar «rápidamente» a una meta que tenemos, pero quizás con una noción un poco distinta de «rapidez». Esto puede querer decir llegar a un objetivo de negocio en pocos días. Hay casos en los que también podremos plantear esta situación como un problema de ruta más corta. Considera el siguiente ejemplo.

Una compañía que renta automóviles está desarrollando una política de reemplazo para su flotilla de automóviles en un horizonte de planeación de 4 años. Al inicio de cada año, un automóvil se reemplaza o se conserva en operación durante un año más. Un automóvil debe estar en servicio de 1 a 3 años. La siguiente tabla proporciona el costo de reemplazo como una función del año en que se adquiere un automóvil y los años en operación.

Equipo adquirido al inicio del año	Costo de reemplazo ($) para años dados en operación
Equipo adquirido al inicio del año	1	2	3
1	4000	5400	9800
2	4300	6200	8700
3	4800	7100	______
4	4900	______	______

El problema puede formularse como una red en la que los nodos 1 a 5 representan el inicio de los años 1 a 5. Los arcos a partir del nodo 1 (año 1) pueden llegar a los nodos 2, 3 y 4 porque un automóvil puede estar en operación de 1 a 3 años. Los arcos a partir de los demás nodos pueden interpretarse del mismo modo. La longitud de cada arco es igual al costo de reemplazo. La solución del problema es equivalente a determinar la ruta más corta entre los nodos 1 y 5.

El problema puede ser representado con la siguiente red:

Más adelante…

Con esto terminamos los últimos planteamientos de problemas ejemplo de programación lineal. Por un lado, estos nos servirán como motivación para saber el tipo de problemas que podemos resolver. Por otro lado, nos irán guíando para el desarrollo de distintas técnicas de solución.

Ya que conocemos el tipo de problemas que podremos resolver, platicaremos ahora un poco de la teoría general que respaldará nuestros métodos. En la siguiente entrada introduciremos algunos aspectos teóricos de los problemas de programación lineal.

Tarea moral

Intenta resolver el ejemplo de la ruta más corta que pusimos como ejemplo usando técnicas elementales y una división en casos. ¿Cuál sería la ruta más corta? ¿Por qué crees que sea importante tener métodos generales si este ejemplo se puede resolver de manera muy sencilla con unos pocos casos?
Formula el segundo ejemplo del problema de la ruta más corta como un problema de programación lineal. ¿Qué interpretación tendría encontrar la ruta más corta?
Pedro va en auto diariamente a la facultad. Pedro siempre toma la misma ruta para llegar a la facultad. Por desgracia, en ocasiones hay algunos asaltos sobre la ruta, y a Pedro le gustaría disminuir lo más posible la probabilidad de que esto suceda. Pedro ha decidido por lo tanto elegir una ruta que minimice la probabilidad de ser asaltado.
La red presentada a continuación muestra las posibles rutas de su casa a la facultad y la probabilidad asociada de no ser asaltado en cada segmento.

La probabilidad de no ser asaltado en la ruta es el producto de las probabilidades de sus segmentos. Por ejemplo, la probabilidad de no ser asaltado en la ruta $1 \to 3 \to 5 \to 7$ es $.9 \times .3 \times .25 = .0675$ . El objetivo de Pedro es seleccionar la ruta que minimice la probabilidad de ser asaltado.
¿Puedes pensar en una manera de formular este problema como un modelo de la ruta más corta? Como sugerencia, trata de usar la función logaritmo.

Una vez planteado el problema anterior, intenta resolverlo con herramientas básicas y algunos casos.
Intenta plantear por tu cuenta una versión general del segundo problema que vimos en esta entrada. ¿Qué sucedería si tenemos más periodos en los que se puede renovar la flotilla? ¿Cómo se vería el problema?

Entradas relacionadas

Ir a Investigación de Operaciones
Entrada anterior del curso: El problema de producción e inventario
Entrada siguiente del curso: Forma canónica y forma estándar de un problema lineal