Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Programación lineal – Entera (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

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)

Monografias.com

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.

Monografias.com

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.

Monografias.com

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

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

Monografias.com

Ramificar y Podar (cont.)
5. Terminar: quedarse con la mejor solución factible obtenida una vez examinadas todas las ramificaciones.

Monografias.com

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

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter