confidencialidad Archivos - Gestión de Operaciones

Problema de Arriendo de Buses para Transporte de Pasajeros en Programación Lineal

El siguiente problema de Programación Lineal consiste en determinar una política óptima de arriendo de buses para el transporte de pasajeros que minimice los costos asociados a su arriendo y satisfaga los requerimientos de transporte y otras condiciones adicionales que se deseen imponer.

El Centro de Alumnos de Ingeniería Industrial de una respetada universidad desea celebrar el día del alumno en la playa. Este paseo está planificado para 1.200 alumnos como mínimo. Una empresa de transporte ofrece 2 tipos de buses pero solo cuenta con 28 conductores. La tabla de abajo indica la capacidad y el costo de arriendo de cada tipo de bus:

Para mantener el equilibrio de su flota, la empresa de transporte impone la condición de que el número de buses tipo B arrendados no puede exceder el número de buses tipo A arrendados. Formule y resuelva un modelo de Programación Lineal que permita determinar cuántos buses de cada tipo hay que arrendar para el paseo de modo que resulte lo más económico para el Centro de Alumnos.

Variables de Decisión:

$x$ : Cantidad de Buses Tipo A arrendados
$y$ : Cantidad de Buses Tipo B arrendados

Función Objetivo:

Minimizar $80.000x+110.000y$

Restricciones:

Cantidad de Alumnos: $40x+60y\geq 1.200$
Cantidad de Conductores: $x+y\leq 28$
Condición de Flota: $x-y\geq 0$
No Negatividad: $x,y\geq 0$

El dominio de soluciones factibles del problema esta dado por el polígono ABC según se detalla a continuación (representación gráfica realizada con el software Geogebra). En particular la solución óptima corresponde al vértice A donde $x=12$ e $y=12$ , con valor óptimo $V(P)=80.000*12+110.000*12=2.280.000$ .

Notar que si bien el problema fue modelado como uno de Programación Lineal, dadas las características del problema sería deseable obtener una solución entera para las variables de decisión (dado que no es posible arrendar una fracción de buses y asumir por ejemplo que el costo del mismo es proporcional a la capacidad ocupada). No obstante en el ejemplo propuesto la solución óptima obtenida cumple de forma natural con las condiciones de integralidad, lo que indica que sus resultados son idénticos al problema de Programación Entera asociado (es decir, aquel al cual se le agregan de forma explícita las condiciones de enteros para las variables de decisión).

De forma complementaria al análisis anterior se pueden responder las siguientes preguntas correspondientes al análisis de sensibilidad o postoptimal:

1. Determine cuánto podría variar el costo de arriendo del Bus tipo A que conserve la solución óptima. Si C1 (costo arriendo del Bus tipo A) varía en el intervalo entre [73.333,3 , ∞[ se conserva la actual solución óptima.

2. Determine el impacto en el valor óptimo del problema si se elimina la condición que el número de buses tipo B arrendados no puede exceder el número de buses tipo A arrendados. El precio sombra de la restricción de condición de flota es 4.000. Luego si se elimina la condición de flota la solución óptima se alcanza en la mínima variación $(x,y)=(0,20)$ para una reducción permisible del lado derecho de dicha restricción en 20 unidades. Luego el nuevo valor óptimo es $V(P)=2.280.000+(-20-0)*4.000=2.200.000$ .

Cálculo del Intervalo de Variación del Lado Derecho que conserva la Base Óptima

Una vez concluidas las iteraciones del Método Simplex y en el caso de alcanzar una solución básica factible óptima, puede resultar de interés determinar un intervalo de variación para un parámetro del vector de los lados derechos de las restricciones que permita conservar la geometría del problema. Esto implica que se conservan las restricciones activas originales en el nuevo escenario (es decir, se mantiene la base óptima) que se genera a partir de la modificación (individual) de un parámetro o coeficiente del lado derecho. Para ilustrar el resultado anterior consideremos el siguiente modelo de Programación Lineal.

Luego de llevar a la forma estándar el modelo anterior agregando $x_{3}$ , $x_{4}$ y $x_{5}$ como las variables de holgura de las restricciones 1, 2 y 3, respectivamente, y aplicar las iteraciones necesarias del Método Simplex, se alcanza la siguiente tabla final (óptima):

La solución óptima es $x_{1}=15$ y $x_{2}=40$ con valor óptimo $V(P)=615$ . El valor de las variables de holgura en el óptimo $x_{3}$ , $x_{4}$ y $x_{5}$ es 0, 0 y 20, respectivamente. Luego se puede concluir que la solución óptima del problema se alcanza con las restricciones 1 y 2 activas (notar que sus respectivas holguras con variables no básicas en el óptimo) y la base actual esta conformada por las variables $x_{1}$ , $x_{2}$ y $x_{5}$ .

Sabemos adicionalmente que, por ejemplo, el costo reducido de la variable de holgura $x_{3}$ representa el precio sombra asociado a la primera restricción ( $\pi_{1}=1/2$ ). No obstante desconocemos en qué intervalo puede variar el parámetro del lado derecho de la restricción 1 (actualmente $b_{1}=180$ ) de modo que se conserve la base óptima y por tanto nos permita hacer un correcto uso de la información del precio sombra.

Para ello se propone la siguiente fórmula que permite encontrar el intervalo de variación para un lado derecho que conserva la base óptima:

Max {-bj/yij con yij>0} <= D <= Min {-bj/yij con yij<0}

Por ejemplo determinemos el intervalo para el parámetro $b_{1}$ :

En consecuencia $b_{1}$ puede disminuir en 30 unidades y aumentar en 15 unidades y se conserva la base óptima. Es decir, si $b_{1}\epsilon [150,195]$ se mantiene la base óptima.

El resultado anterior se puede corroborar gráficamente. La solución óptima se encuentra en el vértice C donde las restricciones 1 y 2 son activas (notar la curva de nivel que pasa por el vértice óptimo es la línea punteada de color azul). Si para el lado derecho de la restricción 1 consideramos $b_{1}=150$ se obtiene la línea de color verde y para $b_{1}=195$ la línea de color rojo. En estos casos si bien se modifica el dominio de soluciones factibles, la solución óptima conserva las actuales restricciones activas (y por ende cuando $b_{1}$ adopta un valor fuera de este intervalo cambia la geometría del problema o base óptima).

Esto es consistente con el Informe de Confidencialidad de Solver. En particular el reporte de restricciones donde se aprecia el aumento y reducción permisible que conserva la actual base óptima:

Por ejemplo, ¿cuál es el nuevo valor óptimo si el lado derecho de la restricción 1 ahora es $b_{1}=190$ ?. Como $b_{1}=190\epsilon[150,195]$ , entonces $V(P)=615+\Delta b_{1}\pi _{1}=615+(190-180)*(1/2)=620$ . ¿Cuál es la nueva solución óptima?. Como sabemos que se conservan las restricciones activas en el óptimo para la variación propuesta, la solución óptima del nuevo escenario se obtiene simplemente resolviendo el siguiente sistema de ecuaciones (notar que la restricción 1 y 2 se conservan activas):

De donde $x_{1}=20$ y $x_{2}=110/3$ , que al evaluar en la función objetivo se obtiene: $V(P)=9*(20)+12*(110/3)=620$ corroborando el resultado anterior. Dejamos al lector el desafío de aplicar los conceptos presentados en este articulo para encontrar un intervalo para $b_{2}$ y $b_{3}$ que conserve la base óptima.

Informe de Confidencialidad de Celdas de Variables y Restricciones de Solver

El siguiente problema tiene por objetivo mostrar la interpretación del Informe de Confidencialidad (o Informe de Sensibilidad) de Solver de Excel en los distintos escenarios que de éste se pueden considerar. Una empresa fabrica 3 productos (A, B y C) y desea planificar la producción semanal de cada uno de estos productos. Para ello dispone de 200 horas semanales en el departamento de corte, 350 horas semanales en el departamento de ensamblaje y 250 horas semanales en el departamento de terminado. Cada producto utiliza una determinada cantidad de horas en estos departamentos según lo muestran los parámetros en el lado izquierdo de las respectivas restricciones. Adicionalmente la empresa ha adquirido contratos con clientes que compran el producto B y C para producir al menos 50 y 30 unidades semanales, respectivamente. Finalmente según el departamento de ventas se ha estimado que la demanda máxima semanal para los productos A, B y C son 60, 120 y 80 unidades respectivamente.

Un modelo de Programación Lineal para la situación anterior es:

Luego de implementar en Solver de Excel el modelo anterior se obtiene el siguiente Informe de Confidencialidad (Informe de Sensibilidad):

1. ¿Cuánto estaría dispuesto a pagar para cancelar el contrato que obliga a producir al menos 30 unidades de C?

El Precio Sombra de la restricción de contrato del producto C es de -2 y su disminución permisible es de 30 unidades. Por tanto podemos utilizar el precio sombra para predecir el cambio en el valor óptimo ante la eliminación de este contrato (que sería equivalente a reemplazar $C\geq 30$ por $C\geq 0$ ). El valor óptimo en consecuencia aumentaría en -2*(0-30)=$60 que determina la máxima disposición a pagar para eliminar este contrato.

2. Suponga que se elimina el contrato que obliga producir al menos 50 unidades de B. ¿Cuál es el impacto en el impacto en el valor óptimo?

El Precio Sombra de la restricción de contrato del producto B es de -19 y su disminución permisible es de 10 unidades. Esto determina que reemplazar $B\geq 50$ por $B\geq 0$ no llevaría la producción de B a cero sino que sólo disminuiría a 40 unidades. Por tanto al eliminar este contrato el valor óptimo aumentaría en -19*(40-50)=$190 que determina la máxima disposición a pagar para eliminar este contrato.

3. Suponga que la empresa tiene $100 para invertir en capacidad. El costo de una hora extra de capacidad en los departamentos de Corte, Ensamblaje y Terminación es de $7, $5, y $6 respectivamente. ¿Cómo invertiría los fondos?. Asuma que sólo puede invertir en una de las 3 alternativas.

No tiene sentido destinar fondos adicionales para contratar horas extraordinarias en los departamentos de ensamblaje y terminado dado que en la actual solución óptima éstas restricciones no se encuentran activas y por tanto existen horas ociosas en dichos departamentos (70 y 80 horas semanales, respectivamente).

Por el contrario el departamento de corte se encuentra operando a máxima capacidad y dispone de un precio sombra de $9 que es mayor al costo de la hora extra de $7, por lo tanto conviene comprar capacidad adicional.

Con un presupuesto de $100 se pueden adquirir 14,2857 horas adicionales en el departamento de corte ($100/7) lo cual está dentro del aumento permisible para el precio sombra (23,3 horas) por tanto se destina la totalidad del presupuesto para dicho propósito.

4. ¿Cuál es el rango de variación para el coeficiente asociado a la variable B en la función objetivo que conserva la actual solución óptima?

Notar que la solución óptima actual es A=20, B=50, C=30. Adicionalmente el valor actual del parámetro en la función objetivo que pondera la variable B es 8, con un aumento permisible de 19 y una reducción permisible de 1E+30 (infinito). Es decir, el intervalo de variación para el parámetro que conserva la solución óptima es ]-1E+30,27]. La cota inferior del intervalo anterior cobra sentido al considerar la restricción de Contrato de B, que, independiente del beneficio (o pérdida) que reporte dicho producto al plan de producción, se debe fabricar de todos modos.

Cambio en un coeficiente de la Función Objetivo asociado a una Variable Básica

En el contexto del Análisis de Sensibilidad o Postoptimal en Programación Lineal y una vez alcanzada la tabla (tableau) final en la aplicación del método simplex, resulta de interés evaluar el impacto en la solución óptima del problema si cambia un coeficiente o parámetro en la función objetivo asociado a una variable básica. Se busca dar respuesta a este escenario sin la necesidad de reoptimizar, es decir, de resolver el problema original nuevamente.

Para conservar la solución óptima identificada inicialmente, se debe cumplir que el costo reducido de todas las variables debe ser mayor o igual a cero (recordar que el costo reducido de las variables básicas es cero por tanto dicha condición en la práctica se establece sobre las variables no básicas). Lo anterior se garantiza si el incremento es cualquiera en el siguiente intervalo:

Donde rj es el costo reducido de la respectiva variable no básica en la actual solución óptima y los coeficientes yij denotan las entradas en la tabla final del método simplex asociadas a la variable básica xi (cuyo costo cambia) y la respectiva variable no básica xj.

Para presentar el concepto anteriormente expuesto consideremos el siguiente problema de Programación Lineal:

Luego de llevar a la forma estándar, incorporando S1, S2 y S3 como las variables de holgura de las restricciones 1, 2 y 3 respectivamente y resolver el modelo lineal anterior a través del método simplex se alcanza la siguiente tabla óptima:

La solución básica factible óptima es Y1=40 e Y2=40 con valor óptimo V(P)=100. A continuación determinaremos un intervalo de variación para los coeficientes que ponderan a las variables Y1 e Y2 en la función objetivo de modo que conservar la actual solución óptima. En este sentido tanto Y1 como Y2 son variables básicas en el óptimo según se aprecia en la tabla anterior.

Luego el intervalo de variación para C1 (en adelante coeficiente asociado a la variable Y1 en la función objetivo de minimización) que mantiene la solución óptima original es:

Del cálculo anterior se obtiene que C1 (coeficiente que multiplica a la variable Y1 en la función objetivo de minimización) puede variar en el intervalo entre C1℮[-1-1/2, -1+1/4], es decir, C1℮[-3/2, -3/4] y se conserva la actual solución óptima. Si hacemos la equivalencia en la función objetivo de maximización original el intervalo corresponde a C1℮[3/4, 3/2], es decir, existe una reducción permisible de 1/4 y un aumento permisible de 1/2 para el valor actual del parámetro que mantiene la solución óptima inicial. De forma análoga se puede verificar que el intervalo de variación para C2 (en la función objetivo de maximización) corresponde a C2℮[1, 2], con un aumento y disminución permisible de 1/2 en cada caso.

Los resultados obtenidos son consistentes con los que provee el informe de confidencialidad o sensibilidad de Solver según se resume a continuación:

Una alternativa para corroborar los resultados anteriores de una forma intuitiva consiste en realizar una representación gráfica del problema anterior. La solución óptima se encuentra en el vértice C, donde la línea punteada de color rojo representa la curva de nivel que intersecta dicha solución. Por otra parte la línea punteada de color verde se obtiene al modificar C1 a 3/4 (reducción permisible de 1/4), lo cual conserva la solución óptima actual pero deja de ser única (en efecto se genera el caso de infinitas soluciones óptimas en el tramo entre los vértices B y C). Finalmente la línea color azul representa la curva de nivel que resulta de cambiar el coeficiente de C1 a 3/2 (aumento permisible de 1/2) que también conserva la solución actual y denota el caso de infinitas soluciones en el tramo CD).

Interpretación del Informe de Sensibilidad de Restricciones de Solver

Continuando con el Análisis de Sensibilidad (o Análisis Postoptimal) en la resolución de modelos de Programación Lineal, en este artículo analizaremos la interpretación del Informe de Sensibilidad (o Informe de Confidencialidad en algunas de las versiones de Office que datan del año 2010 a la fecha) de restricciones de Solver, comúnmente conocido como el análisis del Precio Sombra de cada una de las restricciones.

Por ejemplo, la versión de Solver disponible con Office 365 ofrece la siguiente interfaz para obtener el Informe de Sensibilidad (luego de alcanzar la solución óptima del problema en su escenario base).

En el caso de la versión de Solver compatible con Office 2007 y Office 2003, la interfaz es la siguiente:

De modo de ilustrar su correcta interpretación, a continuación consideraremos nuevamente nuestro ejemplo de Programación Lineal:

Con solución óptima X=14/5 Y=8/5 y valor óptimo V(P)=20,8. El Informe de Restricciones de Solver corresponde a:

Las filas del Informe de Restricciones corresponden a las restricciones 1 y 2, respectivamente.

En el caso de la restricción 1 el Precio Sombra es de 1,2 y el valor de la restricción (lado derecho) es igual a 12. Para dicho parámetro (lado derecho) se permite un aumento de de 9,33 y una disminución de 4, es decir, el lado derecho de la restricción 1 puede variar entre [8, 21,33] (12-4, 12+9,33) y el Precio Sombra de magnitud 1,2 seguirá siendo válido (es decir, se conserva la base óptima).

Esto significa que si, por ejemplo, el lado derecho de la restricción 1 aumenta en 1 unidad y el resto de los parámetros del modelo permanecen constantes, el nuevo valor óptimo será: V(P)=20,8+1*1,2=22.

Ahora bien, si por ejemplo, el lado derecho de la restricción 1 disminuye a 10 el nuevo valor óptimo será: V(P)=20,8-2*1,2=18,4.

Finalmente si la variación del lado derecho esta fuera del intervalo [8, 21,33] NO se puede utilizar el Precio Sombra para poder predecir cuál será el nuevo valor óptimo. Esto se debe a que la nueva solución óptima ya no se encontrará con las mismas restricciones activas, es decir, cambia la base óptima.

Al respecto recomendamos ver el tutorial sobre Cómo calcular gráficamente el Precio Sombra de una Restricción.

De forma análoga, para la restricción 2 el Precio Sombra es de 0,4 y este valor es válido si su lado derecho varía entre [9, 24] (16-7, 16+8). Por ejemplo, si el lado derecho de la restricción 2 aumenta en 3 unidades (y el resto de los parámetros permanece constante) el nuevo valor óptimo será: V(P)=20,8+3*0,4=22.