Algoritmo De Plano Cortante
Páginas: 4 (889 palabras)
Publicado: 7 de junio de 2012
Algoritmo de Plano Cortante
Se inicia con la solución oprima del programa lineal continuo. Al espacio de soluciones se agregar restricciones especiales, llamadas cortes en una forma que produzcaun punto extremo entero.
Ejemplo.
Se tiene la siguiente programación lineal entero:
[pic]
El algoritmo de plano de corte modificara el espacio de soluciones agregando cortes que producen unpunto extremo entero óptimo. En el siguiente ejemplo se parte del optimo del programa lineal continuo, z = 66 1/2 , x1 = 4 1/2 , x2 = 3 ½. A continuación se agrega el corte I, que produce lasolución lineal optima continua z = 62, x1 = 4 ½, x2 =3. A continuación se agrega el corte II, que junto con el corte I y las restricciones originales.
[pic]
llega al optimo del programa lineal z = 58,x1 = 4, x2 = 4. La ultima solución es entera. Que era lo que se uscaba.
Los cortes agregados no eliminan alguno de los puntos enteros factibles originales, pero deben pasar por lo menos un puntoentero, factible o no factible. Estos son los requisitos bascis de cualquier corte.
Solo es por accidente que un problema con 2 variables necesitara de exactamente 2 cortes para llegar a la soluciónentera optima.
Se utiliza el mismo ejemplo para indicar como se determinan los cortes y se implementan algebraicamente.
[pic]
La solución optima es z = 66 1/2 , x1 = 4 1/2 , x2 = 3 ½, x3 = 0,x4 = 0. El corte se establece suponiendo que todas las variables son enteras.
Tambien Z es entero.
La información del cuadro optimo se puede presentar en forma explicita como siguiente:
[pic]Una ecuación de restricción se puede usar como renglón de fuente para generar un corte, siempre que su lado derecho sea fraccionario. También se ve que se puede usar la ecuación de Z como renglón defuente, por que en este ejemplo Z es entera. Demostraremos como se genera un corte a partir de estos renglones de fuente, comenzando con la ecuación de Z.
Primero se sacan todos los coeficientes...
Se inicia con la solución oprima del programa lineal continuo. Al espacio de soluciones se agregar restricciones especiales, llamadas cortes en una forma que produzcaun punto extremo entero.
Ejemplo.
Se tiene la siguiente programación lineal entero:
[pic]
El algoritmo de plano de corte modificara el espacio de soluciones agregando cortes que producen unpunto extremo entero óptimo. En el siguiente ejemplo se parte del optimo del programa lineal continuo, z = 66 1/2 , x1 = 4 1/2 , x2 = 3 ½. A continuación se agrega el corte I, que produce lasolución lineal optima continua z = 62, x1 = 4 ½, x2 =3. A continuación se agrega el corte II, que junto con el corte I y las restricciones originales.
[pic]
llega al optimo del programa lineal z = 58,x1 = 4, x2 = 4. La ultima solución es entera. Que era lo que se uscaba.
Los cortes agregados no eliminan alguno de los puntos enteros factibles originales, pero deben pasar por lo menos un puntoentero, factible o no factible. Estos son los requisitos bascis de cualquier corte.
Solo es por accidente que un problema con 2 variables necesitara de exactamente 2 cortes para llegar a la soluciónentera optima.
Se utiliza el mismo ejemplo para indicar como se determinan los cortes y se implementan algebraicamente.
[pic]
La solución optima es z = 66 1/2 , x1 = 4 1/2 , x2 = 3 ½, x3 = 0,x4 = 0. El corte se establece suponiendo que todas las variables son enteras.
Tambien Z es entero.
La información del cuadro optimo se puede presentar en forma explicita como siguiente:
[pic]Una ecuación de restricción se puede usar como renglón de fuente para generar un corte, siempre que su lado derecho sea fraccionario. También se ve que se puede usar la ecuación de Z como renglón defuente, por que en este ejemplo Z es entera. Demostraremos como se genera un corte a partir de estos renglones de fuente, comenzando con la ecuación de Z.
Primero se sacan todos los coeficientes...
Leer documento completo
Regístrate para leer el documento completo.