Principio de Optimización (Simplex) En un problema de maximización, conviene incrementar la participación de una actividad en el plan en tanto el Ingreso Marginal sea mayor que el Costo Marginal que se incurra. Se llega a una solución óptima siguiendo un mecanismo iterativo, en la que cada solución mejora sobre la previa a partir de incluír actividades que aportan más que lo que “cuestan”. Se llega a una solución óptima cuando no hay sustituciones factibles que permitan lograr un resultado mayor. Para todas las actividades incluídas en el óptimo se cumple el principio: Ingreso Marginal = Costo Marginal
Costo de Sustitución (Costo Reducido) Indica la diferencia entre el Ingreso Marginal y el Costo Marginal para cada actividad. En una solución óptima, las actividades incluídas en el plan cumplen con la condición Ingreso Marginal = Costo Marginal, por lo que el Costo de Sustitución de las mismas es igual a 0. Las actividades no incluídas en el plan tienen un Costo Marginal mayor que su Ingreso Marginal. El Costo de Sustitución indica la magnitud de esta diferencia.
Solución óptima Una solución es óptima para una situación determinada en relación a precios relativos, funciones de producción, disponibilidad de recursos y restricciones empresariales especificadas. Cualquier alteración en los supuestos empleados va a tener un impacto cierto en el resultado obtenido y eventualmente en el nivel o composición de las actividades incluídas en la solución.
Información obtenida Resultado (óptimo) Dimensión de cada actividad en la solución Costo de Sustitución de las actividades Uso de cada recurso Costo de Oportunidad de cada recurso Rango de precios dentro del cual no se modifica la dimensión de las actividades en la solución (ceteris paribus) Rango dentro del cual se mantiene el Costo de Oportunidad de cada recurso (ceteris paribus)
Soluciones degeneradas Cuando en la solución hay menos variables con valores positivos que cantidad de restricciones, la solución es degenerada. En general la degeneración no es un problema, pero a veces puede ocurrir que haya soluciones óptimas alternativas que no son fáciles de identificar. Costos de sustitución igual a 0 o costos de oportunidad igual a 0 son indicadores de soluciones degeneradas.
Soluciones fallidas Solución no factible Posibles causas: error en la formulación (p.ej. una desigualdad con signo equivocado), o problema con restricciones incompatibles. Solución no limitada El modelo fue formulado de tal modo que la función objetivo puede aumentar (en un problema de maximización) o disminuír (en un problema de minimización) sin límites. Posibles causas: falta incluír alguna restricción esencial o se introdujo algún coeficiente con signo equivocado.
Problemas de Transporte Hay un conjunto de m puntos de origen desde los que se envía una mercadería. Cada punto de origen i tiene una capacidad máxima de abastecimiento. Hay un conjunto de n puntos de demanda hacia los que se destina mercadería. Cada punto de demanda j debe ser abastecido con un mínimo de mercadería. Cada unidad producida en un punto de origen i y enviada a un punto de demanda j incurre en un costo cij
Balanceo de un problema de transporte Si la oferta excede a la demanda, se puede balancear el problema creando un punto de demanda ficticia que absorba el exceso de oferta. Si la demanda excede a la oferta, para que el problema se vuelva factible se puede permitir no satisfacer parte de la demanda pagando una penalidad por unidad de demanda insatisfecha. Se agrega un punto de abastecimiento ficticio con una capacidad igual a la demanda insatisfecha, y una penalidad asociada a cada punto demanda.
Problemas de Asignación: son problemas balanceados de transporte en los cuales todas las ofertas y todas las demandas son iguales a 1. Problemas de Transbordo: son problemas de transporte en los que se agregan puntos de transbordo. Los puntos de transbordo son puntos que pueden tanto recibir mercadería de otros puntos como enviar mercadería a otros puntos.
Programación Entera / Mixta Los problemas de programación con enteros se formulan de la misma manera que los problemas de programación lineal, pero agregando la condición de que al menos alguna de las variables de decisión debe tomar valores enteros. Una variable de decisión binaria sólo puede tomar valores 0 o 1. Una variable entera puede tomar cualquier valor, en tanto éste sea entero.
Factores a considerar al incluír variables de decisión enteras en un problema. El procedimiento de resolución es bastante más trabajoso que el método Simplex. Se pierde la posibilidad de contar con información sobre el costo de oportunidad de los recursos y el costo de sustitución de las actividades.
Resolución de problemas enteros por el método de Ramificar y Podar En un problema con enteros existe un número finito de soluciones posibles (no todas son factibles) que pueden representarse mediante un diagrama de árbol. No hace falta enumerar todas las soluciones posibles si se pueden eliminar “ramas dominadas”. Una rama puede eliminarse si puede demostrarse que no contiene una solución factible que sea mejor que una ya obtenida.
Pasos en el método de Ramificar y Podar 1. Comenzar: resolver el problema como si fuera un problema ordinario de PL (relajación de enteros). La solución obtenida se toma como cota máxima y base para el procedimiento de búsqueda de una solución factible. 2. Ramificar: a partir de la solución de PL designar una variable como entera y seleccionar, a partir de los posibles valores enteros que pueda tomar, una rama para investigarla.
Ramificar y Podar (cont.) 3. Limitar: encontrar un límite para el problema definido por la rama seleccionada. El límite está dado por el valor de la mejor solución factible de enteros encontrada hasta el momento, y domina a todos los otros posibles resultados de una rama.
Ramificar y Podar (cont.) 4. Comparar: comparar la solución obtenida en la rama con el límite de referencia vigente. Si el valor de la solución es menor que el límite vigente, se elimina de consideración toda la nueva rama. Se continúa con las ramas que no hayan sido evaluadas aún. Si el valor de la solución es mejor que el límite vigente y si la solución es entera (factible), entonces se convierte en el nuevo límite de referencia. Se examinan las ramas que aún no se han considerado en relación al nuevo límite. Si el valor de la solución es mayor que el límite vigente, pero la solución no es entera (factible) deben explorarse las ramificaciones de nivel inferior en la misma rama.
Ramificar y Podar (cont.) 5. Terminar: quedarse con la mejor solución factible obtenida una vez examinadas todas las ramificaciones.
Problemas con Variables Binarias Estibaje: son problemas con una sola restricción de capacidad. Cargo Fijo: hay un costo asociado con desarrollar una actividad que no depende del nivel de la actividad. Cobertura: cada elemento de un conjunto debe ser “cubierto” por un elemento aceptable de otro conjunto. El objetivo del problema es minimizar el número de elementos del segundo conjunto requerido para cubrir todos los elementos del primer conjunto. Escala mínima de operación
| Página siguiente |