![]() |
Created by Sandra Lilia Castillo Flores
over 9 years ago
|
|
Problema puro de programación con enteros
Problema combinado de programación con enteros
PE binaria o PE 0 - 1
Relajación del PL de la PE
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.
Problema de la mochila
Cargo fijo
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
Solución de PE con LINDO
Precios sombra y costos reducidos en un PE de LINDO
Después de END lo que se escribe por cada variable x 0 - 1
Si w pudiera asumir los valores 0,1,2,. . . , después de END se escribe
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
Capítulo 9.3
Si al resolver la relajación del PL de un PE puro se obtiene una solución con todas las variables enteras entonces . . .
Nombre que recibe el valor óptimo de z para la relajación del PL
Ejemplo 1:
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?
CONCEPTOS DE:
1) Árbol
2) Nodo
3) Arco
Regla LIFO
Solución Probable
Aspectos claves del método de ramificación y acotamiento para PE puros
1) Las tres situaciones que dan como resultado un subproblema que ya está terminado
2) Situaciones en las que se deja de considerar un subproblema
relación de dependencia
Método de corte
¿Cómo se genera el plano cortante?
Enumeración Implícita
Restricción Inclusiva
(al menos una de las dos se cumple)
Restricción si . . . entonces
Formulación para una restricción si . . . entonces