2413072
Description
Flashcards by Sandra Lilia Castillo Flores, updated more than 1 year ago
|
Created by Sandra Lilia Castillo Flores
over 9 years ago
|
|
| Question | Answer |
| Problema puro de programación con enteros | todas las variables tiene que ser enteros |
| Problema combinado de programación con enteros | sólo algunas de las variables son enteros |
| PE binaria o PE 0 - 1 | todas las variables tienen que ser iguales a 0 ó 1 |
| Relajación del PL de la PE | PL obtenido cuando se omiten todos los enteros o las restricciones 0-1 en las variables |
| La región factible para cualquier PE debe estar contenida en la región factible para la relajación del PL correspondiente | |
| Aún cuando la región factible para un PE es un subconjunto de la región factible para la relajación del PL del PE, el PE es mucho más difícil de resolver que la relajación del PL del PE. | No existe un algoritmo como el simplex para que un PE comience desde una solución factible. |
| Problema de la mochila | Cualquier PE que sólo tenga una restricción |
| Cargo fijo | Cuando los costos no dependen de la cantidad, es un costo que se evalúa cada vez que la actividad se emprende a un nivel no cero |
| Ejemplo de planteamiento de restricciones: De cuatro inversiones a lo más se puede invertir en dos | |
| Si se invierte en la inversión 2 entonces también debe invertir en la 1 | |
| Si se invierte en la 2 no se puede invertir en la 4 | |
| ¿Dónde está el error en este planteamiento? Si yi representan los costos fijos por la maquinaria | Los valores de yi que maximizan serán siempre iguales a cero y no puede ser que no se pague por la maquinaria por lo que el PL está incompleto |
| Solución de PE con LINDO | Se puede utilizar LINDO para PE puros o mezclados |
| Precios sombra y costos reducidos en un PE de LINDO | se refieren a subproblemas que se generan durante la solución ramificada y acotada no al PE |
| Después de END lo que se escribe por cada variable x 0 - 1 | INTE x Para un PE en el cual "x " y "y" son variables 1-0 se escribe después de END INTE x INTE y |
| Si w pudiera asumir los valores 0,1,2,. . . , después de END se escribe | GIN w |
| Comando para señalar a LINDO que las primeras n variables que aparecen en la formulación podrían asumir cualquier valor entero no negativo | INT n |
| Capítulo 9.3 | Método de ramificación y acotamiento para resolver problemas de programación pura con enteros |
| Si al resolver la relajación del PL de un PE puro se obtiene una solución con todas las variables enteras entonces . . . | la solución óptima para la relajación del PL es también solución óptima del PE |
| Nombre que recibe el valor óptimo de z para la relajación del PL | Límite o acotamiento superior |
| Ejemplo 1: | Planteamiento |
| b. Ejemplo 1 Se elige en forma arbitraria una variable que es fraccionaria en la solución óptima; si se elige x1 ¿entre qué valores debe estar x1 para la PE? | x1<=3 o x1>=4 |
| CONCEPTOS DE: 1) Árbol 2) Nodo 3) Arco | 1) Representación de todos los subproblemas 2) Cada subproblema 3) Cada línea que une dos nodos |
| Regla LIFO | se resuelve el subproblema recién creado: last in fisrt out que corresponde a último en entrar primero en salir. |
| Solución Probable | Solución que se obtiene al resolver un subproblema en el cual todas las variables tienen valores enteros |
| Aspectos claves del método de ramificación y acotamiento para PE puros | Branch and Bound |
| 1) Las tres situaciones que dan como resultado un subproblema que ya está terminado | 1) el subproblema no es factible 2) el subproblema da una solución óptima en la cual todas las variables tienen valores enteros 3) el valor óptimo de z no excede el LB (acotamiento inferior, lower bound) actual |
| 2) Situaciones en las que se deja de considerar un subproblema | 1) El subproblema es no factible 2) El LB (que representa el valor de z de la mejor solución probable hasta ese momento) es por lo menos igual al valor de z para el subproblema. |
| relación de dependencia | cuando deben de estar presentes dos variables |
| Método de corte | Método que genera restricciones adicionales que son planos cortantes |
| ¿Cómo se genera el plano cortante? | A partir de la tabla óptima de la relajación lineal del modelo |
| Enumeración Implícita | Se usa para resolver problema PE 0 - 1 |
| Restricción Inclusiva (al menos una de las dos se cumple) | |
| Restricción si . . . entonces | Si una restricción f(x1, x2,…,xn) >0 se satisface entonces la restricción g(x1, x2, …,xn) >=0 se debe satisfacer en tanto que sino se satisface la primera entonces la segunda se podría satisfacer o no. |
| Formulación para una restricción si . . . entonces |
Want to create your own Flashcards for free with GoConqr? Learn more.