GEO Tutoriales, Autor en Gestión de Operaciones

Criterios para la Rapidez de Convergencia del Método Simplex

En un artículo previo respecto a Cómo resolver un modelo de Programación Lineal con el Método Simplex de 2 Fases, se consideró en una iteración intermedia (es decir, en un tableau que representa una solución básica factible no óptima) la entrada a la base de una variable no básica que no era aquella con el costo reducido más negativo. Dicha situación por cierto no tuvo incidencia respecto a alcanzar los resultados del modelo en cuanto a su solución óptima y valor óptimo, no obstante, dicha situación afecto la rapidez de convergencia del Método Simplex.

Entendemos por rapidez de convergencia en este caso, el número de iteraciones necesarias en la aplicación del Método Simplex para, comenzando en una solución básica factible inicial llegar a una solución básica factible óptima.

Se debe destacar que si bien es frecuente que en la bibliografía básica asociada a cursos de Investigación de Operaciones se considere como criterio privilegiar la entrada a la base de aquella variable no básica con el costo reducido más negativo esto NO garantiza un menor número de iteraciones en el Método Simplex.

Ejemplo Criterio Costo Reducido Más Negativo en el Método Simplex

Como forma de corroborar lo anterior retomaremos el modelo de Programación Lineal que fue presentado en el artículo mencionado anteriormente:

La resolución del problema anterior se aborda a través del Método Simplex de 2 Fases, incorporando $X_{4}$ y $X_{5}$ como variables de exceso y $X_{6}$ y $X_{7}$ como variables auxiliares, de las restricciones 1 y 2, respectivamente. Esto da origen al siguiente problema de la Fase 1.

Luego de algunas iteraciones del Método Simplex se alcanza la siguiente tabla:

A continuación podríamos seleccionar como variable que ingresa a la base tanto a $X_{1}$ , $X_{2}$ o $X_{4}$ , al tener cada una de estas variables no básicas un costo reducido negativo.

Luego, y según lo descrito anteriormente, podemos privilegiar la entrada a la base de la variable $X_{2}$ que tiene el costo reducido más negativo. En consecuencia el mínimo cuociente se calcula en la columna de la variable $X_{2}$ , siendo éste: $Min\begin{Bmatrix}\frac{1/4}{1/4};\frac{1}{3/2}\end{Bmatrix}=2/3$ , por tanto $X_{1}$ deja la base. Se actualiza la tabla con esta nueva información obteniendo lo siguiente que representa el fin de la Fase I:

Eliminamos las columnas de las variables auxiliares $X_{6}$ y $X_{7}$ y adicionalmente actualizamos el vector de costos reducidos considerando la función objetivo original.

Luego llevamos a cero los costos reducidos de las variables $X_{3}$ y $X_{2}$ :

Ahora entra la variable $X_{1}$ a la base. El criterio de factibilidad o mínimo cuociente determina que $Min\begin{Bmatrix}\frac{1/12}{1/3};\frac{2/3}{2/3}\end{Bmatrix}=1/4$ la variable $X_{3}$ deja la base. Se actualiza la tabla:

Que corresponde a la tabla final de la Fase II donde $X_{1}=1/4$ , $X_{2}=1/2$ y $X_{3}=0$ y que por cierto demuestra la equivalencia en los resultados obtenidos cuando en la tabla intermedia de la Fase I se ingresa a la base a la variable $X_{1}$ . Cabe destacar que una forma alternativa de resolver el problema anterior que evita la aplicación de las 2 Fases del Método Simplex es a través del Método Simplex Dual.

Ejemplo Criterio Costo Reducido Negativo en el Método Simplex

Consideremos el siguiente problema de Programación Lineal:

El lector puede corroborar que luego de llevar a la forma estándar el problema anterior, pasando a minimización la función objetivo y agregando como variables de holgura las variables $x_{3}$ y $x_{4}$ se dispone de una solución básica factible inicial en el origen (vértice A de la siguiente gráfica).

Si se privilegia la entrada a la base de aquella variable no básica con el costo reducido más negativo se debería seleccionar inicialmente la variable $x_{2}$ la cual permite concluir con las iteraciones del Método Simplex y alcanzar la solución óptima al cabo de 3 iteraciones (vértice D). Por el contrario si inicialmente se ingresa a la base la variable $x_{1}$ se alcanza la solución óptima al cabo de 1 iteración. Se recomienda al lector verificar estos resultados.

Este sencillo ejemplo demuestra que NO necesariamente garantiza una mayor rapidez de convergencia del Método Simplex el considerar como criterio de entrada a la base aquella variable no básica con el costo reducido más negativo.

Cambio de Variables como alternativa al Método Simplex de 2 Fases

Una empresa que fabrica tres artículos A, B y C, desea encontrar un Plan de Producción semanal que le permita maximizar sus beneficios netos totales. Los productos son procesados en tres máquinas siendo la producción mínima semanal de 100, 60 y 60 unidades respectivamente. El beneficio neto por unidad vendida de estos artículos son 2, 2 y 4 mil pesos para los artículos A, B y C, respectivamente. Las horas que se necesitan por unidad y máquina son:

Siendo el número de horas disponibles de cada máquina 240, 400 y 360 respectivamente. Formule un modelo de Programación Lineal para abordar el problema propuesto. Resuelva a través del Método Simplex dicho modelo, indicando cuántas unidades de A, B y C se deben fabricar semanalmente y el beneficio final de este plan.

Variables de Decisión: Se debe definir cuántas unidades de cada uno de los 3 productos se fabricarán durante el período de evaluación.

Función Objetivo: Consiste en maximizar el beneficio neto asociado al plan de producción.

Restricciones: Se debe garantizar que se fabrique los mínimos semanales exigidos para cada producto como también que se respete la disponibilidad de horas máquinas.

El problema anterior se puede resolver por el Método Simplex de 2 Fases agregando variables de exceso y auxiliares para cada una de las restricciones que establecen los mínimos semanales de producción. Además se debe agregar variables de holguras para cada una de las restricciones de disponibilidad de horas máquinas. En consecuencia el problema de la Fase 1 tendría 3 variables auxiliares (cuya sumatoria se minimiza en la función objetivo) lo cual genera una instancia de resolución al menos tediosa para este problema (en caso se ser abordada manualmente).

Una alternativa más eficiente de resolución se alcanza al imponer un cambio de variables, lo que permite simplificar las restricciones de mínimos de producción semanal. Sea $X=A-100\geq 0$ , $Y=B-60\geq 0$ y $Z=C-60\geq 0$ . Luego $A=X+100$ , $B=Y+60$ y $C=Z+60$ , obteniendo la siguiente instancia de modelamiento equivalente:

A continuación llevamos a la forma estándar el modelo anterior, transformando la función objetivo a minimización y agregando $s_{1},s_{2},s_{3}$ como variables de holgura de las restricciones 1, 2 y 3, respectivamente:

Lo que da origen a la siguiente tabla inicial del Método Simplex:

A continuación incorporamos a la base a la variable Z considerando el criterio que favorece la rapidez de convergencia del algoritmo. Luego calculamos el criterio de factibilidad o mínimo cuociente en la columna de la variable Z: $Min\begin{Bmatrix}\frac{60}{2}; \frac{180}{1}; \frac{40}{1}\end{Bmatrix}=30$ , lo que determina que la variable $s_{1}$ deja la base. Se actualiza la tabla realizando una iteración del Método Simplex:

Se procede a incorporar a la variable $X$ a la base y $s_{3}$ abandona la base dado que $Min\begin{Bmatrix}\frac{150}{1}; \frac{10}{2}\end{Bmatrix}=5$ . Se realiza una iteración adicional que permite alcanzar la siguiente solución básica factible óptima:

La solución óptima es $X=5$ , $Y=0$ y $Z=30$ que al remplazar en las variables originales permite obtener $A=X+100=5+100=105$ , $B=Y+60=0+60=60$ y $C=Z+60=30+60=90$ . Notar que el valor óptimo es $V(P)=130+560=690$ luego de sumar el valor de la constante 560 al valor obtenido para la función objetivo del problema auxiliar. Se propone al lector corroborar los resultados anterior a través de la aplicación del Método Simplex de 2 Fases que por cierto permite alcanzar idénticos resultados pero con una mayor esfuerzo en la resolución.

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.

Clasificación de los Costos de la Calidad

«Haga el producto correcto, correctamente, la primera vez». Probablemente en alguna oportunidad ha escuchado dicha aseveración que deja de manifiesto que en la gestión de empresas es vital conocer los costos asociados a la calidad y su influencia en la competitividad. Su importancia radica en que nos permite analizar la manera cómo se llevan a cabo las actividades, planificar las actividades relacionadas con la calidad y los recursos disponibles, controlar las actividades desarrolladas y compararlas con aquellas planificadas y detectar y eliminar aquellas condiciones poco favorables.

Costos de la Calidad

En este contexto usualmente se considera la siguiente clasificación de los costos de la calidad en 4 dimensiones:

Prevención
Evaluación
Fallas Internas (cliente interno)
Fallas Externas (cliente externo)

1. Costos de Prevención: El objetivo es mantener los costos de fallas (internas y externas) y evaluación al mínimo. Algunos ejemplos son:

Revisión de nuevos productos y procesos
Planeación de la calidad (Plan global y difusión)
Capacitación focalizada
Control de Procesos
Planificación de la inspección
Selección y evaluación de proveedores
Auditorías de calidad (Evaluación del Plan global)

2. Costos de Evaluación: Se incurre en ellos debido a la inspección y comprobación de las especificaciones de calidad. Por ejemplo:

Inspección y prueba de entrada (al recibir)
Inspección y prueba en proceso
Inspección final
Auditoría de la calidad del producto
Pruebas especiales (ejemplo: ensayos destructivos)
Mantención del equipamiento de inspección

3. Costos de Fallas Internas: Son aquellos detectados antes de que el producto llegue a manos del cliente externo. Entre ellos destaca:

Desechos
Reelaboración
Reinspección
Análisis de defectos
Pérdidas de proceso evitables
Degradación (Rebajas)

4. Costos de Fallas Externas: Se incurre en ellos aún si el cliente no los percibe. Típicamente se ven traducidos en:

Garantías efectivas
Reclamos-devoluciones
Descuentos por razones de calidad
Conciliación de quejas
Retiradas de productos
Concesiones
Otros (generalmente mezclas de los anteriores)

Es importante detectar los problemas asociados a la mala calidad lo antes posible y en especial evitar que estos lleguen al cliente. Cuando se incurren en costos de fallas externas, el impacto de éstos puede ser insospechado. Tal es el caso de la situación que debió enfrentar la marca de automóviles Toyota, la cual debió emitir una orden de retirada en todo el mundo de 6,4 millones de vehículos, de 27 modelos diferentes, por cinco problemas distintos. Lo anterior no sólo se traduce en una pérdida monetaria millonaria por el concepto de reemplazo de componentes, sino también el impacto en la reputación de la marca y su posicionamiento, un aspecto que por cierto es más complejo de estimar cuantitativamente pero no obstante podría superar fácilmente aquellos costos visibles asociados a los problemas de calidad.