Ejercicios resueltos de los temas tratados en este blog.
Ejercicios resueltos Métodos Cuantitativos
domingo, 4 de mayo de 2014
Bibliografía
- HAMDY A. TAHA, Investigación de Operaciones. Ed. Prentice Hall. 6ª ed. México 1998.
- Hiller y Leiberman. Introducción a la Investigación de Operaciones. Ed Mc Graw-Hill. México, 1997.
- Eppen, G. D.; Gould, F.J.; Schmidt, C.P.; Moore, J.H. y Weatherford, L.R. Investigación de Operaciones en la Ciencia Administrativa. Ed. Pearson.
- Winston Wayne L. Investigación de Operaciones: Aplicaciones y Algoritmos. Grupo Editorial Iberoamericana. México, 1994.
Diagrama de Pareto
El diagrama de Pareto, también llamado curva cerrada o Distribución A-B-C, es una gráfica para organizar datos de forma que estos queden en orden descendente, de izquierda a derecha y separados por barras. Permite, pues, asignar un orden de prioridades.El diagrama permite mostrar gráficamente el principio de Pareto (pocos vitales,muchos triviales), es decir, que hay muchos problemas sin importancia frente a unos pocos muy importantes. Mediante la gráfica colocamos los "pocos que son vitales" a la izquierda y los "muchos triviales" a la derecha. El diagrama facilita el estudio de las fallas en las industrias o empresas comerciales, así como fenómenos sociales o naturales psicosomáticos.
Modelos de control de inventarios
Las empresas mantienen inventarios de materias primas y de productos terminados. Los inventarios de materias primas sirven como entradas al proceso de producción y los inventarios de productos terminados sirven para satisfacer la demanda de los clientes. Puesto que estos inventarios representan frecuentemente una considerable inversión, las decisiones con respecto a las cantidades de inventarios son importantes. Los modelos de inventario y la descripción matemática de los sistemas de inventario constituyen una base para estas decisiones. Mantener un inventario (existencia de bienes) para su venta o uso futuro es una práctica común en el mundo de los negocios. Las empresas de venta al menudeo, los mayoristas, los fabricantes y aún los bancos de sangre por lo general almacenan bienes o artículos. ¿Cómo decide una instalación de este tipo sobre su "política de inventarios", es decir, cuándo y cómo se reabastece? En una empresa pequeña, el administrador puede llevar un recuento de su inventario y tomar estas decisiones. Sin embargo, como esto puede no ser factible incluso en empresas chicas, muchas compañías han ahorrado grandes sumas de dinero al aplicar la "administración científica del inventario". Hay que tener en cuenta que tanto la distribución de los efectos como sus posibles causas no es un proceso lineal sino que el 20% de las causas totales hace que sean originados el 80% de los efectos. El principal uso que tiene el elaborar este tipo de diagrama es para poder establecer un orden de prioridades en la toma de decisiones dentro de una organización. Evaluar todas las fallas, saber si se pueden resolver o mejor evitarlas.
Método Vogel
Un método que por lo general supera los demás cuando se trata de encontrar un SFBI es el llamado método de Vogel. La
expresión sanción es una indicación del método que se aplica. Por cada renglón y columna de la tabla de transporte hay una
sanción conceptual, en términos de costo, debida al hecho de no elegir la casilla más baja disponible durante el proceso de
asignación.
Las sanciones calculadas son las diferencias en relación con cada renglón y columna, entre las rutas de transporte de costo
más bajo y de costo más bajo siguiente. Por lo tanto, las asignaciones se hacen primero a aquellas casillas donde las sanciones
son mayores, porque esto evita los incrementos más grandes del costo asociados por las rutas de transporte de bajo costo, en
un sentido absoluto, como la elección de las rutas de bajo costo que mejor eluden las sanciones relativas de costo asociadas
con la utilización de otras posibilidades alternativas.
Resumen del Método de Vogel
1. Encontrar las diferencias entre los costos mas pequeños en los renglones y las columnas
2. Determinar el renglón o columna con la diferencia de costos mínimos más grande, si hay dos o más iguales seleccionar
arbitrariamente
3. Asignar tanto como sea posible a la celda que tiene l costo más pequeño tratando de satisfacer la demanda en función
de la disponibilidad de la oferta e ir disminuyendo la oferta y la demanda correspondiente
4. Eliminar las columnas o los renglones saturados
5. Regresar al primer paso y repetir hasta que las columnas y renglones queden saturados; si al final solo queda un renglón
una columna, por el método de costo mínimo continuamos asignando a las celdas restantes hasta que todas queden
saturadas.
Renglones:
4-3 = 1
3-2 = 1
Columnas:
6-2 = 4 * Se escoge el que tenga una diferencia mayor
4-3 =1
5-3 = 2
X11 = 0 X21 = 6
X12 = 0 X22 = 4
X13 = 11 X23 = 3 Z=72
expresión sanción es una indicación del método que se aplica. Por cada renglón y columna de la tabla de transporte hay una
sanción conceptual, en términos de costo, debida al hecho de no elegir la casilla más baja disponible durante el proceso de
asignación.
Las sanciones calculadas son las diferencias en relación con cada renglón y columna, entre las rutas de transporte de costo
más bajo y de costo más bajo siguiente. Por lo tanto, las asignaciones se hacen primero a aquellas casillas donde las sanciones
son mayores, porque esto evita los incrementos más grandes del costo asociados por las rutas de transporte de bajo costo, en
un sentido absoluto, como la elección de las rutas de bajo costo que mejor eluden las sanciones relativas de costo asociadas
con la utilización de otras posibilidades alternativas.
Resumen del Método de Vogel
1. Encontrar las diferencias entre los costos mas pequeños en los renglones y las columnas
2. Determinar el renglón o columna con la diferencia de costos mínimos más grande, si hay dos o más iguales seleccionar
arbitrariamente
3. Asignar tanto como sea posible a la celda que tiene l costo más pequeño tratando de satisfacer la demanda en función
de la disponibilidad de la oferta e ir disminuyendo la oferta y la demanda correspondiente
4. Eliminar las columnas o los renglones saturados
5. Regresar al primer paso y repetir hasta que las columnas y renglones queden saturados; si al final solo queda un renglón
una columna, por el método de costo mínimo continuamos asignando a las celdas restantes hasta que todas queden
saturadas.
4-3 = 1
3-2 = 1
Columnas:
6-2 = 4 * Se escoge el que tenga una diferencia mayor
4-3 =1
5-3 = 2
X12 = 0 X22 = 4
X13 = 11 X23 = 3 Z=72
Esquina Noreste
Esta regla nos permite encontrar una solución factible inicial (SFBI), una vez que tengamos el problema de transporte "balanceado"
o equilibrado, es decir que el total de ofertas es igual al total de demandas.
Procedimiento:
Iniciar la asignación en el renglón 1 y columna 1 (esquina noroeste) y formar una base asignando cantidades, de forma tal
que se agoten las existencias y satisfaga la demanda. Así, entonces la asignación inicia en la casilla X11 (esquina noroeste) y
si la fábrica 1 (compañía, empresa, etc.) no agoto s oferta continuará en la casilla X12 y así sucesivamente.
En el caso de que el total de la oferta de la fabrica1 no haya sido suficiente para cubrir la demanda del mercado1, completar con la oferta2, que es
la casilla X21 y si no se agotó la oferta pasar a la casilla X22 y así continuar el proceso de asignación.
Z = 2*6+3*4+5*3=72
X11 = 0
X12 = 0
X13 = 11
X21 = 6
X22 = 4
X23 = 3
Z = 72
o equilibrado, es decir que el total de ofertas es igual al total de demandas.
Procedimiento:
Iniciar la asignación en el renglón 1 y columna 1 (esquina noroeste) y formar una base asignando cantidades, de forma tal
que se agoten las existencias y satisfaga la demanda. Así, entonces la asignación inicia en la casilla X11 (esquina noroeste) y
si la fábrica 1 (compañía, empresa, etc.) no agoto s oferta continuará en la casilla X12 y así sucesivamente.
En el caso de que el total de la oferta de la fabrica1 no haya sido suficiente para cubrir la demanda del mercado1, completar con la oferta2, que es
la casilla X21 y si no se agotó la oferta pasar a la casilla X22 y así continuar el proceso de asignación.
X11 = 0
X12 = 0
X13 = 11
X21 = 6
X22 = 4
X23 = 3
Z = 72
Modelos de Transporte
Dentro de la amplia gama de problemas de programación lineal se encuentran los problemas de transporte, los cuales poseen
características particulares. En este caso especifico de problemas, es necesario determinar la ruta más eficiente para
hacer llegar productos o materiales desde puntos alternativos de origen hasta diferentes puntos de destino, cumpliendo las
restricciones especificas de oferta y demanda y con base a la estructura de costos de las rutas de transporte.
Las diversas técnicas para abordar el problema de transporte requieren de una tabla de transporte, dicha tabla en su forma
estándar registra todos los elementos esenciales del problema de transporte que estamos solucionando: costos de transporte
y cantidades remitidas por todas las rutas posibles; puntos de origen y destino, cantidades de oferta y demanda; tal y como se
muestra a continuación.
En la tabla anterior la demanda (33) es igual a la oferta (33), lo cual significa que el problema está balanceado y ello facilita la
búsqueda de la solución.
Ferrocarriles Nacionales de México tiene disponibles en Zacapo, Michoacán 11 vagones y en Toluca 13 vagones.
Requiere de vagones: 6 en Monterrey, 4 En Tehuantepec y 14 en Jalapa, Veracruz. Los costos de transporte están basaos en
los distintos costos de procesos, tienen poca relación entre la distancia y aparecen relacionados en la siguiente tabla.
características particulares. En este caso especifico de problemas, es necesario determinar la ruta más eficiente para
hacer llegar productos o materiales desde puntos alternativos de origen hasta diferentes puntos de destino, cumpliendo las
restricciones especificas de oferta y demanda y con base a la estructura de costos de las rutas de transporte.
Las diversas técnicas para abordar el problema de transporte requieren de una tabla de transporte, dicha tabla en su forma
estándar registra todos los elementos esenciales del problema de transporte que estamos solucionando: costos de transporte
y cantidades remitidas por todas las rutas posibles; puntos de origen y destino, cantidades de oferta y demanda; tal y como se
muestra a continuación.
búsqueda de la solución.
Ferrocarriles Nacionales de México tiene disponibles en Zacapo, Michoacán 11 vagones y en Toluca 13 vagones.
Requiere de vagones: 6 en Monterrey, 4 En Tehuantepec y 14 en Jalapa, Veracruz. Los costos de transporte están basaos en
los distintos costos de procesos, tienen poca relación entre la distancia y aparecen relacionados en la siguiente tabla.
Flujo Máximo
El uso de modelos de redes en la toma de decisiones incluye los llamados problemas de flujo máximo. En algunos problemas
el planteamiento de la red es muy evidente, no obstante, en otros casos se requiere de imaginación para representar la red
apropiadamente. Una vez construida la red, el algoritmo adecuado debe ser aplicado para la toma de decisión.
Considere una red con un nodo de entrada (o fuente) y un nodo de salida (o antifuente).
El problema del flujo máximo pregunta:
¿Cuál es la cantidad máxima de vehículos, líquido, peatones o llamadas telefónicas que pueden entrar y salir del sistema en
un periodo determinado de tiempo?
En este tipo de problemas se intenta conducir un flujo por las ramas o arcos de la red en forma óptima, aunque dicho flujo
esta limitado por restricciones diversas tales como: condiciones de la carpeta asfáltica, diámetros de tuberías, etc. Al límite
máximo del flujo de una rama se le denominara capacidad de flujo.
1) Volver a la red no dirigida
Trayectoria de aumento: OBET
Capacidad residual: {7, 5, 6}=5
Trayectoria de aumento: OADT
Capacidad residual: {5, 3, 9}=3
Trayectoria de aumento: OBADT
Capacidad residual: {2,4,6}=2
Trayectoria de aumento: OCEBDT
Capacidad residual: {4, 4, 5, 2, 4}=2
Trayectoria de aumento: OCEDT
Capacidad residual: {2, 2, 1, 2}=1
Trayectoria de aumento: OABET
Capacidad residual: {2, 1, 2, 1}=1
La cortadura es para saber si se realizo bien el ejercicio, esta consiste en cortar arcos dirigidos y
sumar los valores:
Puesto que todos los valores son mayores de 14, el ejercicio es correcto.
el planteamiento de la red es muy evidente, no obstante, en otros casos se requiere de imaginación para representar la red
apropiadamente. Una vez construida la red, el algoritmo adecuado debe ser aplicado para la toma de decisión.
Considere una red con un nodo de entrada (o fuente) y un nodo de salida (o antifuente).
El problema del flujo máximo pregunta:
¿Cuál es la cantidad máxima de vehículos, líquido, peatones o llamadas telefónicas que pueden entrar y salir del sistema en
un periodo determinado de tiempo?
En este tipo de problemas se intenta conducir un flujo por las ramas o arcos de la red en forma óptima, aunque dicho flujo
esta limitado por restricciones diversas tales como: condiciones de la carpeta asfáltica, diámetros de tuberías, etc. Al límite
máximo del flujo de una rama se le denominara capacidad de flujo.
Capacidad residual: {7, 5, 6}=5
Trayectoria de aumento: OADT
Capacidad residual: {5, 3, 9}=3
Capacidad residual: {2,4,6}=2
Capacidad residual: {4, 4, 5, 2, 4}=2
Capacidad residual: {2, 2, 1, 2}=1
Capacidad residual: {2, 1, 2, 1}=1
sumar los valores:
PERT-Costo
Hemos visto como PERT/CPM se concentra en el factor tiempo del desarrollo de un proyecto y ofrece información que
puede utilizarse para programar y controlar actividades y del proyecto en total. No obstante, aunque el tiempo es una consideración
importante, existen muchas situaciones en las que el costo es casi tan importante como el tiempo. A continuación
veremos como PERT/costo puede ser utilizado, adicionalmente, para controlar los costos de un proyecto, puesto que su objetivo
es ofrecer información que sirva para mantener los costos del proyecto dentro de un presupuesto especificado y para un
mejor ejercicio de recursos adicionales.
Se traza la ruta crítica y se intensifican las actividades de la Rc.
Rc = 12 semanas
Ahora si con la intensificación se crearon rutas con mayor duración se vuelve a intensificar esas rutas, se
realizará por ciclos.
Ciclo 1:
Se intensifica la actividad (2,3) en $500.00
Ciclo 2:
Se escoge el menor de la subred
puede utilizarse para programar y controlar actividades y del proyecto en total. No obstante, aunque el tiempo es una consideración
importante, existen muchas situaciones en las que el costo es casi tan importante como el tiempo. A continuación
veremos como PERT/costo puede ser utilizado, adicionalmente, para controlar los costos de un proyecto, puesto que su objetivo
es ofrecer información que sirva para mantener los costos del proyecto dentro de un presupuesto especificado y para un
mejor ejercicio de recursos adicionales.
Rc = 12 semanas
realizará por ciclos.
Ciclo 1:
Se intensifica la actividad (2,3) en $500.00
Ciclo 2:
PERT-Probabilístico
Existen proyectos con actividades que tienen tiempos inciertos, es decir, se tienen solo estimaciones de tiempo por el
cual deben ser tratados como variables aleatorias con distribuciones de probabilidad asociadas.
Para incluir los tiempos inciertos de las actividades en el análisis de la red, es necesario obtener tres estimaciones de
tiempo para cada actividad. Las tres estimaciones son:
Tiempo optimista (a): Es el tiempo requerido para la actividad si todo marcha idealmente.
Tiempo más probable (m): Es el tiempo requerido para la actividad con más probabilidades bajo condiciones
estándar o normales.
Tiempo pesimista (b): Es el tiempo para la actividad cuando se afrontan demoras considerables
Las tres anteriores estimaciones de tiempo permiten al administrador un proyecto desarrollar una mejor apreciación del
tiempo con una mayor probabilidad para cada actividad, el cual se calculara con la formula:
¯D=te=(a+4m+b)/6
Por el tipo de distribución: (Beta)
Con tiempos inciertos en las actividades, puede utilizarse la medida estadística común conocida como varianza ara describir
la dispersión o variabilidad en los valores de tiempo de actividades, la cual estará determinada por la siguiente formula:
V=((b-a)/6)^2
Como podrá concluiré, en la medida en que existan diferencias grandes entre b y a se tendrá un elevado grado de incertidumbre
en el tiempo de actividad.
PERT probabilístico parte de dos suposiciones:
Que las actividades son estadísticamente independientes, lo cual permitirá sumar las varianzas para obtener la varianza
total del proyecto.
Que el tiempo determinación de un proyecto es una variable normalmente distribuida, lo cual permite usar la distribución
normal en el análisis.
NOTA: Aunque los números aparezcan en diferente orden, el a es el más pequeño, b es el más grande y m el
que tenga valor intermedio. También, si sólo aparece un número los tres valores son igual a ese número.
Se utilizaran las siguientes fórmulas:
cual deben ser tratados como variables aleatorias con distribuciones de probabilidad asociadas.
Para incluir los tiempos inciertos de las actividades en el análisis de la red, es necesario obtener tres estimaciones de
tiempo para cada actividad. Las tres estimaciones son:
Tiempo optimista (a): Es el tiempo requerido para la actividad si todo marcha idealmente.
Tiempo más probable (m): Es el tiempo requerido para la actividad con más probabilidades bajo condiciones
estándar o normales.
Tiempo pesimista (b): Es el tiempo para la actividad cuando se afrontan demoras considerables
Las tres anteriores estimaciones de tiempo permiten al administrador un proyecto desarrollar una mejor apreciación del
tiempo con una mayor probabilidad para cada actividad, el cual se calculara con la formula:
¯D=te=(a+4m+b)/6
Por el tipo de distribución: (Beta)
la dispersión o variabilidad en los valores de tiempo de actividades, la cual estará determinada por la siguiente formula:
V=((b-a)/6)^2
Como podrá concluiré, en la medida en que existan diferencias grandes entre b y a se tendrá un elevado grado de incertidumbre
en el tiempo de actividad.
PERT probabilístico parte de dos suposiciones:
Que las actividades son estadísticamente independientes, lo cual permitirá sumar las varianzas para obtener la varianza
total del proyecto.
Que el tiempo determinación de un proyecto es una variable normalmente distribuida, lo cual permite usar la distribución
normal en el análisis.
que tenga valor intermedio. También, si sólo aparece un número los tres valores son igual a ese número.
Se utilizaran las siguientes fórmulas:
Árbol Minimmal
En terminología de redes, este problema se refiere a utilizar las ramas o arcos de la red para llegar a todos los nodos de la
red, de manera que se minimiza la longitud total.
La aplicación de este tipo de problemas de optimización se ubica, sobre todo, en las redes de comunicación eléctrica, telefónica,
telegráfica, carretera, ferroviaria, aérea, marítima; etc. Donde los nodos representan puntos de consumo eléctrico,
teléfonos, aeropuertos; etc. Y los arcos podrían ser líneas de alta tensión, vías de ferrocarril, rutas aéreas; etc.
Si n = número de nodos, entonces la solución óptima debe incluir n-1 arcos.
El Algoritmo de Kruskal para resolver este problema es muy sencillo. Los pasos son los siguientes:
1. Comenzar en forma arbitraria en cualquier nodo y conectarlo con el nodo más próximo (menos distante).
2. Identificar el nodo no conectado que este más cerca de alguno de los nodos conectados. Deshacer los empates de
forma arbitraria. Agregar este nodo al conjunto de nodos conectados. Repetir este paso hasta que se hayan conectado
todos los nodos.
Se utiliza para transporte, las duraciones de ahora son distancias, las distancias pueden ir de ida o de regreso, por esta
razón ya no tienen dirección. El objetivo es conectar a todos los nodos con la mínima distancia.
red, de manera que se minimiza la longitud total.
La aplicación de este tipo de problemas de optimización se ubica, sobre todo, en las redes de comunicación eléctrica, telefónica,
telegráfica, carretera, ferroviaria, aérea, marítima; etc. Donde los nodos representan puntos de consumo eléctrico,
teléfonos, aeropuertos; etc. Y los arcos podrían ser líneas de alta tensión, vías de ferrocarril, rutas aéreas; etc.
Si n = número de nodos, entonces la solución óptima debe incluir n-1 arcos.
El Algoritmo de Kruskal para resolver este problema es muy sencillo. Los pasos son los siguientes:
1. Comenzar en forma arbitraria en cualquier nodo y conectarlo con el nodo más próximo (menos distante).
2. Identificar el nodo no conectado que este más cerca de alguno de los nodos conectados. Deshacer los empates de
forma arbitraria. Agregar este nodo al conjunto de nodos conectados. Repetir este paso hasta que se hayan conectado
todos los nodos.
Se utiliza para transporte, las duraciones de ahora son distancias, las distancias pueden ir de ida o de regreso, por esta
razón ya no tienen dirección. El objetivo es conectar a todos los nodos con la mínima distancia.
Estructura del PERT y CPM
Seis pasos comunes son:
PERT y CPM difieren en terminología, pero sus objetivos son los mismos, así como el análisis utilizado. La diferencia más importante es que PERT utiliza tres estimaciones de duración de tiempo para cada actividad, cada estimación tiene una probabilidad de ocurrencia asociado, la cual a su vez se utiliza para calcular valores esperados y desviación estándar para las duraciones de las actividades. CPM hace la suposición de que las duraciones de las actividades de las operaciones se conocen con certeza y por lo tanto sólo se da un factor de duración para cada actividad.
- 1. Definir el proyecto y todas sus tareas especificas
- 2. Desarrollar o establecer las relaciones entre las actividades, es decir, definir cuales actividades deben preceder y cuáles deben seguir a otras.
- 3. Graficar la red que conecta todas las actividades.
- 4. Asignar las estimaciones de tiempo y/o costo para cada actividad.
- 5. Calcular la trayectoria de mayor duración a través de la red; esta será la ruta crítica.
- 6. Utilizar la red para evaluar y controlar el proyecto
PERT y CPM difieren en terminología, pero sus objetivos son los mismos, así como el análisis utilizado. La diferencia más importante es que PERT utiliza tres estimaciones de duración de tiempo para cada actividad, cada estimación tiene una probabilidad de ocurrencia asociado, la cual a su vez se utiliza para calcular valores esperados y desviación estándar para las duraciones de las actividades. CPM hace la suposición de que las duraciones de las actividades de las operaciones se conocen con certeza y por lo tanto sólo se da un factor de duración para cada actividad.
PERT/CPM
Los grandes proyectos a menudo, resultan retos difíciles para los administradores. Los riesgos son altos, un retraso puede significar perdidas por miles de dólares o hasta millones. Los proyectos especiales usualmente desarrollan fuera del sistema normal de grandes proyectos involucra tres fases: planeación, programación y control.
Tiempo vs Costo Antecedente:
Gráfica de Gantt
Existen dos técnicas para la administración de proyectos: La técnica de evaluación y revisión del programa (PERT, por sus siglas en inglés) y el método de la ruta crítica para apoyar el trabajo de programación, seguimiento y control de proyectos grandes y complejos.
CPM llegó primero en 1957, como una herramienta desarrollada en la compañía Dupont para ayudar en la construcción y mantenimiento de las plantas químicas de la empresa PERT fue desarrollada un año después por U.S. Navy.
Tiempo vs Costo Antecedente:
Gráfica de Gantt
Existen dos técnicas para la administración de proyectos: La técnica de evaluación y revisión del programa (PERT, por sus siglas en inglés) y el método de la ruta crítica para apoyar el trabajo de programación, seguimiento y control de proyectos grandes y complejos.
CPM llegó primero en 1957, como una herramienta desarrollada en la compañía Dupont para ayudar en la construcción y mantenimiento de las plantas químicas de la empresa PERT fue desarrollada un año después por U.S. Navy.
Modelo de Redes
Existe un tipo particular de problemas en programación lineal a los que se denomina problemas de flujo de redes. Para ellos existen algunos modelos que permiten obtener una solución óptima, para la cual se desarrolla una interpretación gráfica del problema (denominada red), la cual consiste de un diagrama de nodos y arcos.
Por la forma o estructura matemática de los problemas es que se han podido desarrollar procedimientos (algoritmos) especializados de solución para resolverlos.
Existen:
Por la forma o estructura matemática de los problemas es que se han podido desarrollar procedimientos (algoritmos) especializados de solución para resolverlos.
Existen:
- 1. Gráficas de Gantt
- 2. CPM
- 3. PERT
Cambios que afectan la optimalidad
La solución actual dejará de ser óptima sólo si los coeficientes de la función objetivo z_i-c_j, violan la condición de optimalidad.
Dado el vector de los precios duales Y=C_B B^(-1), la definición.
z_i-c_j=YP_j-c_j
Nos dice que la optimalidad de la solución sólo se verá afectada cuando cambiamos los coeficientes objetivo c_j (y, por tanto, C_B) o el vector P_j de utilización de recursos por unidad.
Cambios en los coeficientes objetivo c_j. El efecto de hacer cambios en c_jsobre la optimalidad implica volver a calcular z_ic_ j, únicamente para las variables no básicas. La razón por la cual no necesitamos volver a calcular z_i-c_jpara las variables básicas es que siempre serán igual a cero, sin importar los cambios que se hagan en c_j.
El procedimiento del cálculo se resume como sigue:
Adición de una nueva actividad.
La adición de una nueva actividad en un modelo de PL es equivalente a añadir una nueva variable. Intuitivamente, la adición de una nueva actividad es deseable sólo si deja utilidades, es decir, si mejora el valor óptimo de la función objetivo. Esta condición se verifica calculando z_i-c_j=YP_j- c_j , para la nueva actividad, donde Y son los valores duales óptimos actuales y P_j y c_j representan el empleo de los recursos y la utilidad por unidad de la nueva utilidad. Si la z_i-c_j calculada no satisface la condición de optimalidad, entonces la nueva actividad no es deseable. De lo contrario la nueva actividad produce utilidades y debe incluirse en la solución básica.
Dado el vector de los precios duales Y=C_B B^(-1), la definición.
z_i-c_j=YP_j-c_j
Nos dice que la optimalidad de la solución sólo se verá afectada cuando cambiamos los coeficientes objetivo c_j (y, por tanto, C_B) o el vector P_j de utilización de recursos por unidad.
Cambios en los coeficientes objetivo c_j. El efecto de hacer cambios en c_jsobre la optimalidad implica volver a calcular z_ic_ j, únicamente para las variables no básicas. La razón por la cual no necesitamos volver a calcular z_i-c_jpara las variables básicas es que siempre serán igual a cero, sin importar los cambios que se hagan en c_j.
El procedimiento del cálculo se resume como sigue:
- Calcule el valor de los precios duales Y=C_B B^(-1)utilizando un nuevo vector C_Bsi se cambió.
- Calcule z_i-c_j=YP_j- c_j para todas las x, no básicas actuales.
- Si se satisface a condición de optimalidad, la solución actual seguirá siendo la misma pero a un nuevo valor óptimo de la función objetivo. (Sin embargo, si C_B pertenece inalterada el valor objetivo óptimo seguirá siendo el mismo.)
- Si no se satisface la condición de optimalidad, aplicamos el método simplex (primal) para recuperar optimalidad.
Resultarán dos casos:
Adición de una nueva actividad.
La adición de una nueva actividad en un modelo de PL es equivalente a añadir una nueva variable. Intuitivamente, la adición de una nueva actividad es deseable sólo si deja utilidades, es decir, si mejora el valor óptimo de la función objetivo. Esta condición se verifica calculando z_i-c_j=YP_j- c_j , para la nueva actividad, donde Y son los valores duales óptimos actuales y P_j y c_j representan el empleo de los recursos y la utilidad por unidad de la nueva utilidad. Si la z_i-c_j calculada no satisface la condición de optimalidad, entonces la nueva actividad no es deseable. De lo contrario la nueva actividad produce utilidades y debe incluirse en la solución básica.
Cambios que afectan la factibilidad
La factibilidad de la solución óptima actual puede resultar afectada únicamente (1) se cambia el lado derecho de las restricciones, b, o (2) si se añade una nueva restricción al modelo. En ambos casos la factibilidad ocurre cuando por lo menos uno de los elementos de B^(-1) b se vuelve negativo, es decir, si una o más de las variables básicas actuales se vuelven negativas.
Cambios discretos en el vector b del lado derecho. Se considera el caso en que se hacen cambios específicos discretos en uno o más de los elementos del vector b.
Rango factible de los elementos en b. Otra forma de ver el efecto de cambiar la disponibilidad de los recursos (es decir, el vector b del lado derecho), es determinar el rango para el cual sigue siendo factible la solución actual. Adición de nuevas restricciones. La adición de una nueva restricción a un modelo existente conducirá a uno de dos casos. La nueva restricción es redundante, lo que significa que se satisface por la solución óptima actual. La nueva restricción se viola, en cuyo caso debe utilizarse el método simplex dual para (tratar de) recuperar la factibilidad.
Cambios discretos en el vector b del lado derecho. Se considera el caso en que se hacen cambios específicos discretos en uno o más de los elementos del vector b.
Rango factible de los elementos en b. Otra forma de ver el efecto de cambiar la disponibilidad de los recursos (es decir, el vector b del lado derecho), es determinar el rango para el cual sigue siendo factible la solución actual. Adición de nuevas restricciones. La adición de una nueva restricción a un modelo existente conducirá a uno de dos casos. La nueva restricción es redundante, lo que significa que se satisface por la solución óptima actual. La nueva restricción se viola, en cuyo caso debe utilizarse el método simplex dual para (tratar de) recuperar la factibilidad.
Análisis de sensibilidad
El análisis de sensibilidad es el estudio de la forma en que se afecta la solución óptima al presentarse en los coeficientes de un programa lineal.
El análisis de sensibilidad se obtiene después de obtener la solución óptima (actual) de un modelo PL. La meta es determinar si los cambios en los coeficientes del modelo dejarán inalterada la solución actual y, de no ser así cómo obtener con eficiencia una nueva óptima (suponiendo que exista una). La principal razón de la importancia del análisis de sensibilidad para quienes toman las decisiones es que los problemas reales ocurren en un medio ambiente dinámico.
El nuevo problema puede diferir del original en uno o varios de los siguientes aspectos:
En general, los cambios en el modelo dan por resultado uno de cuatro casos.
En el caso 2, utilizaremos el método dual simplex para recuperar la factibilidad, en el caso 3 utilizaremos el método simplex (primal) para obtener la nueva óptima. En el caso 4, utilizamos los métodos primal y dual para obtener la nueva solución.
El análisis de sensibilidad se obtiene después de obtener la solución óptima (actual) de un modelo PL. La meta es determinar si los cambios en los coeficientes del modelo dejarán inalterada la solución actual y, de no ser así cómo obtener con eficiencia una nueva óptima (suponiendo que exista una). La principal razón de la importancia del análisis de sensibilidad para quienes toman las decisiones es que los problemas reales ocurren en un medio ambiente dinámico.
El nuevo problema puede diferir del original en uno o varios de los siguientes aspectos:
- Disponibilidad de recursos (Vector b)
- Los costos unitarios o utilidades (Vector c)
- Los coeficientes tecnológicos (Matriz a_ij)
En general, los cambios en el modelo dan por resultado uno de cuatro casos.
- La solución actual (básica) permanece inalterada.
- La solución actual se vuelve no factible.
- La solución actual se vuelve no óptima.
- La solución actual se vuelve no óptima así como no factible.
En el caso 2, utilizaremos el método dual simplex para recuperar la factibilidad, en el caso 3 utilizaremos el método simplex (primal) para obtener la nueva óptima. En el caso 4, utilizamos los métodos primal y dual para obtener la nueva solución.
Restricciones “≥” “=”
Paso 1: Multiplicar por (-1) para cambiar de signo.
Paso 2: Multiplicar por (-1) para cambiar el signo.
Paso 3:
Paso 4: Ahora se hace el dual
Razones para convertir de simplex a dual
1. Cálculos
2. Nexos con el análisis de sensibilidad
3. Interpretación económica
2. Nexos con el análisis de sensibilidad
3. Interpretación económica
¿Cómo convertir un problema primal a dual?
Un problema dual se formula de una problema primal de la siguiente forma:
Si el primal es un problema de maximización su dual será un problema de minimización y viceversa.
Los coeficientes de la función objetivo del problema primal se convierten en los coeficientes del vector de disponibilidad en el problema dual.
Los coeficientes del vector de disponibilidad el problema original se convierten en los coeficientes de la función objetivo (vector de costo o precio) en el problema dual.
Los coeficientes de las restricciones en el problema primal, será la matriz de los coeficientes tecnológicos en el dual.
Los signos de desigualdad del problema dual son contrarios a los del primal.
Cada restricción es un problema correspondiente a la variable en el otro problema.
Si el primal tiene m restricciones y n variables, el dual tendrá n restricciones y m variables. Así , las variables En del primal se convierte en nuevas variables Ym en el dual.
La siguiente tabla resume gráficamente esta información donde y_1,y_(2 ),….y y_m
Teoría de la dualidad
El método simplex además de resolver un problema de PL legando a una solución óptima nos ofrece más y mejores elementos para la toma de decisiones. La dualidad y el análisis de sensibilidad son potencialidades de este método.
El concepto de dualidad indica que para cada problema de PL hay una asociación y una relación muy importante con otro problema de programación lineal, llamado precisamente dual.
La relación entre el problema dual y su asociado, es decir el problema original llamado primal, presenta varias utilidades:
Aportar elementos que aumentan sustancialmente la compresión de la PL.
El análisis de dualidad es una herramienta útil en la solución de problemas PL, por ejemplo mas restricciones que variables.
El problema dual tiene interpretaciones e informaciones importantes que muestran que los análisis marginales están siempre involucrados al buscar la solución óptima aun problema de PL.
Método de la Gran M
Método Simplex
El método del simplex se utiliza, sobre todo para resolver problemas de programación lineal en los que intervienen tres o más variables. Fue desarrollado en el año 1947 por George Dantzig. Exceptuando las cosas más pequeñas y sencillas, su ejecución se lleva a cabo en las computadoras a través de programas desarrollados con ese propósito particular.
Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace a través e los lados de polígono (o de las aristas del poliedro, si el numero de variables es mayor). Como el numero de vértices (y de aristas es finito), siempre se pondrá encontrar la solución.
El algebra matricial y el proceso de eliminación de Gauss-Jordan para resolver un sistema de ecuaciones lineales constituye la base del método simplex.
El método simplex es un procedimiento algebraico, sin embargo, sus conceptos básicos sin de tipo geométrico, por lo cual a través de una grafica es posible comprender su fundamentación.
El comprender dichos procesos proporciona una base para saber como opera el método simplex y el porque es tan eficiente en la organización de recursos limitados.
La forma mas fácil para resolver un problema pequeño de programación lineal es, por lo tanto, el llamado sistema o forma de solución grafica. Cuando existen mas de dos variables, no es posible obtener la solución en una grafica de dos dimensiones, por lo tanto, se deben buscar formas más complejas, tal como la forma algebraicas del método simplex. Sin embargo, el método grafico es invaluable al ofrecer las bases del funcionamiento en los otros procedimientos.
Diagrama de método Simplex
Método Grafico
Nota: Igualaremos las ecuaciones y anularemos 3 ceros pero al final del problema recordar aumentarlos.
Suscribirse a:
Entradas (Atom)