Simplex

REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA EDUCACIÓN SUPERIOR
UNIVERSIDAD NACIONAL EXPERIMENTAL SUR DEL LAGO
UNESUR
CASIGUA EL CUBO ESTADO ZULIA









PROFESOR: INTEGRANTES:
DenisDebora Acero
María Gelvez C.I: V-18.721.366


Casigua El Cubo, Septiembre De 2012
Para Que Utilizamos El Método Simplex En El Caso De Maximización Y Minimización
EL MÉTODO SIMPLEX Es un método genérico de solución de problemas lineales, desarrollado por George Dantzig en 1947. Como tal, el método simplex es un procedimiento algebraico, pero puede entenderse más fácilmente como unmétodo geométrico. Antes de explicar los aspectos geométricos del Simplex, veremos el tratamiento que debe hacerse a cualquier modelo de PL antes de aplicar el Método Simplex sobre él para solucionarlo. Juan José Bravo B., M.Sc.
Conversión de modelos de PL a la /1 Forma Estándar Todo modelo de PL, para efectos de resolverse con el Método Simplex, debe llevarse a una Forma Estándar con lassiguientes características: 1. El lado derecho de las ecuaciones debe ser no-negativo 2. Todas las restricciones deben convertirse a Ecuaciones 3. Todas las variables deben ser no-negativas EJEMPLO: Maximizar Z = 2x1 + 3x2 + x3 Sujeto a: x1 + x2 + x3 = 10 -2x1 + 3x2 + 2x3 ≤ -5 7x1 - 4x2 + 5x3 ≤ 6 x1 + 4x2 + 3x3 ≥ 8 x1 no restringida, x2 ≤ 0, x3 ≥0 Juan José Bravo B., M.Sc.
Conversión de modelos de PL ala /2 Forma Estándar Maximizar Z = 2x1 + 3x2 + x3 Maximizar Z = 2x1 + 3x2 + x3 1 Sujeto a: x1 + x2 + x3 = 10 Sujeto a: x1 + x2 + x3 = 10 -2x1 + 3x2 + 2x3 ≤ -5 2x1 - 3x2 - 2x3 ≥ 5 7x1 - 4x2 + 5x3 ≤ 6 7x1 - 4x2 + 5x3 ≤ 6 x1 + 4x2 + 3x3 ≥ 8 x1 + 4x2 + 3x3 ≥ 8 x1 no restringida, x2 ≤ 0, x3 ≥0 x1 no restringida, x2 ≤ 0, x3 ≥0 2 Maximizar Z = 2x1 – 3x’2 + x3 Maximizar Z = 2x1 + 3x2 + x3 3a Sujeto a: x1– x’2 + x3 = 10 Sujeto a: x1 + x2 + x3 = 10 2x1 + 3x’2 - 2x3 – S1 = 5 2x1 - 3x2 - 2x3 – S1 = 5 7x1 + 4x’2 + 5x3 + S2 = 6 7x1 - 4x2 + 5x3 + S2 = 6 x2=-x’2 x1 - 4x’2 + 3x3 – S3 = 8 x1 + 4x2 + 3x3 – S3 = 8 x1 no restringida, x’2 ≥ 0, x3 ≥ 0, S1≥0, x1 no restringida, x2 ≤ 0, x3 ≥0, S1≥0, S2≥0, S3≥0 S2≥0, S3≥0 Juan José Bravo B., M.Sc.
Conversión de modelos de PL a la /3 Forma Estándar Maximizar Z =2x1 – 3x’2 + x3 Sujeto a: x1 – x’2 + x3 = 10 3b 2x1 + 3x’2 - 2x3 – S1 = 5 7x1 + 4x’2 + 5x3 + S2 = 6 x1= x’1 - x’’1 x1 - 4x’2 + 3x3 – S3 = 8 x1 no restringida, x’2 ≥ 0, x3 ≥ 0, S1≥0, S2≥0, S3≥0 Maximizar Z = 2x’1 – 2x’’1 - 3x’2 + x3 Sujeto a: x’1 – x’’1 – x’2 + x3 = 10 Forma Estándar donde: 2x’1 – 2x’’1 + 3x’2 - 2x3 – S1 = 5 S1 y S3  Variables de Exceso 7x’1 – 7x’’1 + 4x’2 + 5x3 + S2 = 6 S2 Variable de Holgura x’1 – x’’1 - 4x’2 + 3x3 – S3 = 8 x’1≥ 0, x’’1 ≥ 0, x’2 ≥ 0, x3 ≥ 0, S1≥0, S2≥0, S3≥0 Juan José Bravo B., M.Sc.
Soluciones Básicas EJEMPLO: Minimizar Z = -3x1 - 5x2 Minimizar Z = -3x1 - 5x2 Forma Sujeto a: x1 ≤ 4 Sujeto a: x1 + S1 = 4 Estándar 2x2 ≤ 12 2x2 + S2 = 12 3x1 + 2x2 ≤ 18 3x1 + 2x2 + S3 = 18 x1 , x2 ≥ 0 x1 , x2 , S1, S2, S3 ≥ 0 x1 x2 s1 s2 s3 0 0 4 12 18 El MétodoSimplex observa el conjunto de ecuaciones resultantes 0 6 4 0 6 en la forma estándar, y dado que 0 9 4 -9 0 hayan “m” ecuaciones y ”n” incognitas (en este caso m = 3 y n 4 6 0 0 -6 = 5) le corresponde hacer (n-m) 2 6 2 0 0 variables iguales a “cero” para 4 3 0 6 0 poder tener soluciones consistentes. Las soluciones que 6 0 -2 12 0 logra de esta manera se llaman 4 0 0 12 6 Soluciones Básicas. Juan JoséBravo B., M.Sc.
Soluciones Básicas Factibles (SBF) x1 x2 s1 s2 s3 P1 0 0 4 12 18 Fact P2 0 6 4 0 6 Fact P3 0 9 4 -9 0 NO P4 4 6 0 0 -6 NO P5 2 6 2 0 0 Fact P6 4 3 0 6 0 Fact P7 6 0 -2 12 0 NO P8 4 0 0 12 6 Fact Los puntos resaltados con verde representan Soluciones Básicas Factibles ya que cumplen con Las SBF son los vértices todas las restricciones. Los demás puntos violan de la Región...