Algortimo de plano cortante

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Universidad José Antonio Páez

ALGORITMO DE PLANO DE CORTE

Huamanciza S, Paúl F – CI: 19455808
Rodríguez A, Alejandra J – CI: 20266857
Sección 308C1
Métodos cuantitativos

San Diego, 28 de Febrero de 2012
El algoritmo de plano de corte, es un modelo de programación lineal que se divide endos subclases, las cuales son:
* Gráfica
* Algebraica, y ésta, se divide en dos más, que son:
* Fraccional
* Mixta
Este algoritmo consiste en ir agregando restricciones (también llamadas cortes), de manera que va modificando el espacio de soluciones; así hasta hallar la solución óptima.

PASOS PARA RESOLVER DE FORMA GRÁFICA:
1. Se grafican lasrestricciones de la PL, y se observa cuál es el punto en que las mismas se cruzan (o se calculan algebraicamente mediante un sistema de ecuaciones)
2. Luego de obtenido el punto, se sustituye en la función objetivo (Z). Si el resultado que arroja es entero, se halló la solución óptima del modelo de PL. Si no es entero se continúa al siguiente paso:
3. Teniendo el punto de cruce de lasrestricciones anteriores, se redondean al menor número entero anterior, y se grafican en ambos ejes. Se toman los puntos de cruce de las nuevas rectas con las restricciones, y se sustituyen los nuevos valores en Z. Esto se hará sucesivamente hasta que Z sea un valor entero.
EJEMPLO: Maximizar z=7x1+20x2
Sujeto a: -x1+3x2≤6
7x1+x2≤35
x1,x2≥0 y enteros
SOLUCIÓN:
1. Se grafican ambasrestricciones. Se observa el punto de cruce de ambas.

2. Se sustituye el punto obtenido en Z -> z = 7(4,5)+10(3,5) -> z = 66.5. No es un entero, por lo tanto se prosigue al paso 3
3. Se redondea x2 al entero inferior inmediato, en este caso sería 3. Se grafica x2=3, y se toma el punto de corte de esta recta con la restricción 1.

Se sustituye el punto en z = 7(4,57)+10(3)-> z= 61,99. No es un entero y no cumple con que x1 lo sea, así que se prosigue
Se redondea x1 a su entero inferior inmediato, en este caso 4. Se grafica x1=4, y se toma el punto de corte de esta recta con x2. Se sustituyen los nuevos puntos en la función objetivo, z = 7(4)+10(3) -> z = 58. Ya que es entero, se grafica la función objetivo. En donde se intersecten las 3 rectas es elóptimo.

PASOS PARA RESOLVER DE FORMA FRACCIONAL:
1. Se estandariza y se resuelve el modelo de PL por método simplex primal. Si todas las variables tienen resultado entero, entonces se encontró una solución óptima del modelo. Si no es así, se prosigue con el paso 2.
2. Según el resultado obtenido, se elige alguna de las ecuaciones de la tabla, siempre y cuando no tengan resultadoentero. Sólo los fraccionarios, y depende de cuál tenga el mayor decimal. Si son iguales es arbitrario.
3. Se realiza el ‘corte’, que es la separación de las fracciones en sus ‘enteros y partes fraccionarias’. Luego de hacer esto se introduce una variable de holgura, para crear una nueva restricción y se crea la nueva ecuación bajo el siguiente criterio:

4. Se añade la nueva restricción alfinal de la tabla Simplex Primal óptima. Si todas las variables tienen resultados enteros, la solución es óptima (generalmente luego de aplicar Simplex Dual), sino se vuelve a realizar el paso 2 hasta que todas las soluciones lo sean.

EJEMPLO: Maximizar z=x1+2x2
Sujeto a: 4x1+3x2≤12
-x1+x2≤2
x1,x2≥0 y enteros

1. Estandarizando:
Maximizar: z=x1+2x2+0x3+0x4
Sujeto a: 4x1+3x2+x3=12-x1+x2+x4=2
x1,x2≥0 y enteros

* Entra x2
Tabla Simplex Primal:

Vb | x1 | x2 | x3 | x4 | Solución | Razón |
z | -1 | -2 | 0 | 0 | 0 | |
Sale x4
x3 | 4 | 3 | 1 | 0 | 12 | 12/3=4 |
x4 | -1 | 1 | 0 | 1 | 2 | Entra x1
2/1=2 |
Sale x3
z | -3 | 0 | 0 | 2 | 4 | |
x3 | 7 | 0 | 1 | -3 | 6 | |
x2 | -1 | 1 | 0 | 1 | 2 | |
z | 0 | 0 | 3/7 | 5/7 | 46/7 | |
x1 | 1 | 0 | 1/7 |...