Investigación de Operaciones (INI391)
Capítulo 6 de Hillier y Lieberman
Realizado por Adrianna Zapata (1085599)
Teoría de la dualidad y análisis de Sensibilidad
Type in the name of the book you have read.
Papel de la teoría de la Dualidad en el Análisis de Sensibilidad
Introducción de una nueva variable
La inclusión de otra actividad equivale a introducir en el modelo una nueva variable, con los coeficientes apropiados en las restricciones funcionales y en la función objetivo. El único cambio que resulta en el problema dual es la introducción de una nueva restricción
Las variables de decisión del modelo suelen representar los niveles de las distintas actividades en consideración. En algunas situaciones, se seleccionan algunas de ellas
de entre un grupo grande de actividades posibles en el que las restantes no fueron elegidas debido a que parecían ser menos atractivas.
Cambios en los coeficientes de una variable no básica
Como la variable en cuestión es no básica (su valor es cero), el cambio en sus coefi cientes no puede afectar la factibilidad de la solución, por lo cual, la pregunta que queda abierta en este caso es si todavía es óptima.
Suponga que los cambios que se hacen en el modelo original ocurren en los coefi cientes de una variable que era no básica en la solución óptima original. ¿Cuál es el efecto de estos cambios sobre esta solución? ¿Todavía es factible? ¿Todavía es óptima?
Interpretación económica
Type the main events of the book, classifying them in: events from the beginning, events from the middle, and events from the end of the book.
Describe the story visually. Add a representative picture for each of them.
Interpretación del Método Simplex
La meta del símplex es encontrar la manera de usar los recursos disponibles en la forma más redituable. Para alcanzarla, debe llegar a una solución BF que satisfaga todos los requisitos sobre el uso provechoso de los recursos (las restricciones del problema dual).
Sin embargo, los asociados con las variables no básicas pueden o no ser satisfecho.
Estos requisitos comprenden la condición de optimalidad del algoritmo. Para cualquier solución BF dada, los requisitos (restricciones duales) asociados con las variables básicas se satisfacen de manera automática (con la igualdad).
La interpretación del problema dual proporciona también una interpretación económica de lo que
hace el método símplex en el problema dual.
Type the main events from the middle.
Add a representative picture for each of them.
Interpretación del Problema Dual
Los valores de yi (o los valores de yi* en la solución óptima) no son otra cosa que los precios sombra.
En terminología económica, un recurso de este tipo es un “bien gratuito”; el precio de los bienes que tienen una sobredisponibilidad debe ser igual a cero por la ley de la oferta y la demanda. Este hecho justifica la interpretación de la función objetivo para el problema dual como la minimización del valor de los recursos consumidos, en lugar de los asignados
Type the main events from the beginning.
Add a representative picture for each of them.
Relaciones Prima-Dual
In contrast to the main idea, the theme is the message, lesson or moral of the book.
Some tips to find out the theme of the book easier:
- Try to find it while you are reading. It may be stated or implied.
- Think about how the characters reacted to obstacles.
- Think about the important decisions that the characters made.
- Think about the characters growing or changing throughout the book.
Soluciones básicas complementarias
Propiedad de holgura complementaria:
La razón por la que se usa el nombre de holgura complementaria para esta última propiedad
es que enuncia (en parte) que para cada par de variables asociadas, si una de ellas tiene holgura en su restricción de no negatividad (una variable básica > 0), entonces la otra no debe tener holgura (variable no básica =0)
Propiedad de las soluciones básicas complementarias:
Cada solución básica del problema primal tiene una solución básica complementaria para el problema dual, donde los valores respectivos de la función objetivo (Z y W ) son iguales
Una idea clave aquí es que la solución del dual que se lee en el renglón 0 también debe ser una solución básica. Esto se debe a que cada una de las m variables básicas del problema primal necesitan tener coeficiente igual a cero en el renglón 0
Como el problema dual es un problema de programación lineal, también tiene soluciones en los vértices.
Aún más, al emplear la forma de igualdades del problema, estas soluciones se pueden expresar como soluciones básicas
Adaptación a otras formas del Primal
Método común-extraño raro
Señala que la forma de una restricción funcional o de la restricción sobre una variable del problema dual debe ser común, extraña o rara, lo que depende de que la forma del elemento correspondiente en el problema sea común, extraña o rara.
Una consecuencia de la propiedad de simetría es que todas las afirmaciones que se hicieron antes sobre las relaciones del problema dual con el problema primal también se cumplen en sentido inverso.
Otra consecuencia es que no importa a cuál de los problemas se le dé el nombre de primal y a cuál el de dual. En la práctica, se puede encontrar un problema de programación lineal que se ajuste a nuestra forma estándar y al que se le dé el nombre de problema dual
Para cualquier problema primal y su
problema dual, todas las relaciones entre ellos deben ser simétricas.
Take notes while you read the book. Write here your favorite quotes from the book.
Esencia del análisis de sensibilidad
Take notes while you read the book. Type here the resources, books, or websites that the author mentioned and you want to check out later.
Sin embargo, en problemas más grandes como los que se encuentran en la práctica, el análisis
de sensibilidad requeriría de un esfuerzo computacional exorbitante si fuera necesario volver a aplicar el método símplex desde el principio para investigar cada cambio en el valor de un parámetro
Para problemas pequeños, la verificación del efecto de una variedad de cambios en los valores de los parámetros es directa con sólo aplicar de nuevo el método símplex para ver si cambia la solución óptima.
Un objetivo fundamental del análisis de sensibilidad es identificar los parámetros
sensibles
Es importante llevar a cabo un análisis de sensibilidad, para investigar el efecto que tendría sobre la solución óptima que proporciona el método símplex el hecho de que los parámetros tomen otros valores posibles
Aplicaciones
Su uso en la interpretación económica del problema dual y la visión que se obtiene para el análisis del problema primal.
La evaluación de una solución propuesta para el problema primal.
Puede resolverse el problema dual directamente con el método símplex, a fin de identificar una solución óptima para el problema primal.
The main idea is what the book is mostly about.
Some tips to find out the main idea of a book easier:
- Read the title.
- Look for the text features.
- Figure out if you are reading a fiction or a non fiction book.
- Think about some examples that support this idea.
Teorema de la Dualidad
Las siguientes son las únicas relaciones posibles entre los problemas primal y dual
Si un problema no tiene soluciones factibles, entonces el otro problema no tiene soluciones factibles o bien la función objetivo es no acotada.
Si uno de los problemas tiene soluciones factibles y una función objetivo no acotada, (es decir, no tiene solución óptima), entonces el otro problema no tiene soluciones
factibles.
Si un problema tiene soluciones factibles y una función objetivo acotada (y, por ende,
una solución óptima), entonces ocurre lo mismo con el otro problema, de manera que se aplican tanto la propiedad de dualidad débil como la fuerte.
Relaciones prima-dual
Type the names of the book characters. Start with the main character.
Draw arrows to represent the relationship between them and if it is possible write on them what they represent for each other (if they are relatives, friends, lovers, enemies etc.)
Propiedad de Simetría
En consecuencia, todas las propiedades anteriores se cumplen sin que importe a cuál de los dos problemas se le llame problema primal.
En el caso de cualquier problema primal y su problema dual,
las relaciones entre ellos deben ser simétricas debido a que el dual de este problema dual
es este problema primal.
Character name
Characteristics
Propiedad de soluciones complementarias óptimas
Al final de cada iteración, el método símplex identifica de manera simultánea una solución óptima x* para el problema primal y una solución óptima complementaria y* para el problema dual (que se encuentra en el renglón 0 como los coeficientes de las variables de holgura), donde cx* = y*b
Propiedad de Soluciones Complementarias
Si x no es óptima para el problema primal, entonces y no es factible para el problema
dua
En cada iteración, el método símplex identifica de manera simultánea una solución FEV, x, para el problema primal y una solución complementaria, y, para el problema dual (que se encuentra en el renglón 0, como los coeficientes de las variables de holgura), donde
cx = yb.
Propiedad de dualidad fuerte
Estas dos propiedades implican que cx < yb para soluciones factibles si una o ambas son no
óptimas para sus problemas respectivos, mientras que la igualdad se cumple cuando ambas son óptimas.
Si x* es una solución óptima para el problema primal y y* es una solución óptima para el problema dual, entonces cx*=y*b
Propiedad de dualidad debil
Si x es una solución factible para el problema primal y y es una solución factible para el problema dual, entonces cx ≤ yb.
What are the characteristics that best describe the character? Type them here.
Origen del problema dual
What is the reason why the author wrote the book?
La teoría de la dualidad se basa de manera directa en la idea fundamental
Esencia de la Teoría de la Dualidad
Who is the author of the book? Type in his/her name.
Parámetros
Los coeficientes de una variable de las restricciones funcionales del problema primal son los coeficientes de una restricción funcional del problema dual.
Los lados derechos de las restricciones funcionales del problema primal son los coeficientes de la función objetivo del problema dual.
Los coeficientes de la función objetivo del problema primal son los lados derechos de las restricciones funcionales del problema dual.
En los problemas primal en la forma de maximización, los problemas dual están en la forma de minimización.
