Método gráfico simplex.
yo2112Práctica o problema20 de Julio de 2016
815 Palabras (4 Páginas)356 Visitas
Tabla de contenido
- Método simplex2
- Solución degenerada7
- Solución infactible 9
- Solución no acotada 10
- Bibliografía13
Método simplex
Cuando un problema de investigación de operaciones es muy complejo para resolverlo por el método gráfico es necesario contar con un método para poder dar solución al problema; el método simplex resulta ser la herramienta para tal fin, el método simplex es un método de programación lineal en el cual no se tiene restricciones en las variables. Este método mejora en cada iteración la solución. George Bernard Dantzig y el ruso Leonid Vitalievich Kantorovich fueron los creadores del método en el año de 1947 para resolver problemas con m restricciones y n variables. Al tratar de buscar las soluciones nos encontramos con algunos casos especiales que son:
- Solución múltiple
- Solución degenerada
- Solución infactible
- Solución no acotada
Solución múltiple
Este tipo de caso se presenta cuando se tienen múltiples soluciones óptimas y se debe a que la función objetivo es paralela a alguna de las restricciones que se satisface al sentido de la igualdad de la solución óptima.
Ejemplo 1:
[pic 1]
Sa:
[pic 2]
[pic 3]
[pic 4]
Reformulando
[pic 5]
[pic 6]
[pic 7]
[pic 8]
| 4 | 6(C.P) | 0 | 0 | 0 | Valor solución | |
X1 | X2 | S1 | S2 | S3 | |||
0S1 | 2 | 3 | 1 | 0 | 0 | 6 | 2 |
0S2 | 6 | 4 | 0 | 1 | 0 | 12 | 3 |
0S3(F.P) | -2 | 2 | 0 | 0 | 1 | 2 | 1 |
Zj | 0 | 0 | 0 | 0 | 0 |
| |
Cj –Zj | 4 | 6 | 0 | 0 | 0 |
|
El resultado de las iteraciones se registrara en las tablas de datos indicando el intercambio de variables cada vez que señala el reglón y la columna pivote.
Cálculos para la primera fila
[pic 9]
[pic 10]
[pic 11]
[pic 12]
[pic 13]
[pic 14]
[pic 15]
Para la segunda fila
[pic 16]
[pic 17]
[pic 18]
[pic 19]
[pic 20]
[pic 21]
| 4(C.P) | 6 | 0 | 0 | 0 | Valor solucion | |
X1 | X2 | S1 | S2 | S3 | |||
0S1 | 5 | 0 | 1 | 0 | -0,75 | 6 | 3 |
0S2 | 10 | 0 | 0 | 1 | -2 | 12 | 8 |
6X2 (F.P) | -1 | 1 | 0 | 0 | ½ | 2 | 1 |
Zj | -6 | 6 | 0 | 0 | 3 | 6 | |
Cj –Zj | 10 | 0 | 0 | 0 | -3 |
|
Para la primera fila
[pic 22]
[pic 23]
[pic 24]
[pic 25]
[pic 26]
Para la segunda fila
[pic 27]
[pic 28]
[pic 29]
[pic 30]
[pic 31]
Los resultados se registran a continuación:
| 4 | 6 | 0 | 0 | 0 | Valor solución |
X1 | X2 | S1 | S2 | S3 | ||
4X1 | 1 | 0 | 0,2 | 0 | -0,3 | 3/5 |
0S2 | 0 | 0 | -2 | 1 | 1 | 2 |
6X2 | 0 | 1 | 0,2 | 0 | 1/5 | 8/5 |
Zj | 4 | 6 | 2 | 0 | 0 | 12 |
Cj –Zj | 0 | 0 | -2 | 0 | 0 |
|
Tenemos que X1= 3/5, X2=8/5 ,
Zmax= 4*(3/5) + 6*(8/5) = 12
Como dos variables de holgura son cero (S1 y S3) se puede inferir que hay múltiples soluciones y por lo tanto podemos encontrar otra solución introduciendo la variable de holgura que tenga valor de cero a la base. En nuestro caso elegimos S3, ya que en el renglón Cj –Zj tiene un valor de cero hay que mencionar que S1 tiene valor tiene valor negativo.
Para el primer renglón
[pic 32]
[pic 33][pic 34]
[pic 35]
[pic 36]
[pic 37]
Para el tercer renglón
[pic 38]
[pic 39]
[pic 40]
[pic 41]
[pic 42]
Los resultados se registran en la siguiente tabla.
| 4 | 6 | 0 | 0 | 0 | Valor solución |
X1 | X2 | S1 | S2 | S3 | ||
4X1 | 1 | 0 | -0,4 | 0,3 | 0 | 6/5 |
0S2 | 0 | 0 | -2 | 1 | 1 | 2 |
6X2 | 0 | 1 | 0,6 | -0,2 | 0 | 6/5 |
Zj | 4 | 6 | 2 | 0 | 0 | 12 |
Cj –Zj | 0 | 0 | -2 | 0 | 0 |
|
La otra solución óptima es X1 = 6/5, X2 = 6/5
Zmax = 4*(6/5) + 6*(6/5) = 12
Solución degenerada
La solución degenerada es una situación en la cual tres restricciones pasan por un mismo punto. Esto se reconoce cuando se encuentra un empate entre las dos relaciones más pequeñas y por ende una de las variables en la mezcla de solución es cero. De la misma forma la aparición de un empate indica que en el problema existe una restricción redundante y dicho empate se puede romper de forma arbitraria.
...