Método Simplex Otros Modelos

PARTE 3

MÉTODO SIMPLEX

OTRAS FORMAS

1. ROMPIMIENTO DE EMPATES
1. SOLUCIONES ÓPTIMAS MÚLTIPLES
2. RESTRICCIONES IGUAL ( =)
1. ARTIFICIALES Y GRAN M
3. MINIMIZAR
1. MAXIMIZACIÓN EQUIVALENTE
4. RESTRICCIONES MAYOR O IGUAL (≥ )

1. ARTIFICIALES, SUPERÁVIT Y GRAN M

MÉTODO SIMPLEX EN otras formas

Consideraciones

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

Consideraciones

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

1. Empate de la variable básica entrante2. Empate de la variable básica saliente 3. No hay variable básica que sale 4. Soluciones óptimas múltiples

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

1. Empate de la variable básica entrante Z = 3X1 + 3X2 Ecuación (0): Z - 3X1- 3X2 = 0X1 y X2 tienen el valor negativo más grande, ¿Cuál escoger?** Cualquiera de las 2, tarde o temprano se llegará a la solución óptima. No hay manera de saber con cual de las 2 se llegará más rápido al final

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

2. Empate de la variable básica saliente (DEGENERACIÓN) Sucede cuando la prueba del cociente mínimo da dos resultados iguales (2 números iguales como mínimos). La que no se escogiera como variable saliente también tomaría el valor de cero (a pesar de ser variable básica) y se denominaría “variable degenerada”.Lo que podría suceder es que se crearan “ciclos” sin que Z cambie. No hay que preocuparse, es muy raro, seleccionar cualquier variable como variable básica saliente.

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

3. No hay variable básica que sale: Z no acotada Sucede cuando ninguna variable califica como variable básica que sale. En la forma tabular sería el caso que todos los coeficientes de la columna pivote (excluyendo el renglón 0) son negativos o cero y por lo tanto no podemos seguir el paso 2 que se inicia escogiendo los coeficientes mayores que cero El método simplex no podría continuar y se asumiría que se cometió un error: • Modelo mal formulado • Faltan restricciones • Errores en los cálculos

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

4. Soluciones Óptimas Múltiples Al encontrar una solución óptima siempre verificar si existe en el renglón (0) una variable no básica que tenga un valor de cero (0). Si esto sucede, se puede encontrar por lo menos otra solución óptima mediante iteraciones adicionales (cada vez se elige una variable no básica con coeficiente cero como variable básica entrante) Modificando la Función Objetivo del problema de la Puertas Globales Z = 3X1 + 2X2 se tendría:

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

FUNCIÓN OBJETIVOMaximizar Z = 3X1 + 2X2 Sujeto a las siguientes RESTRICCIONES (funcionales y de no negatividad) : X1 ≤ 4 2X2 ≤ 12 3X1 + 2X2 ≤ 18 X1 ≥ 0 X2 ≥ 0 VARIABLES DE DECISIÓN: X1 y X2 En la segunda y tercera iteración (esta sería una iteración adicional) tendríamos:

Soluciones Óptimas Múltiples

ROMPIMIENTO DE EMPATES EN EL MÉTODO SIMPLEX

4. Soluciones Óptimas Múltiples ** Lo más común es encontrar 2 soluciones óptimas, pero este es CASO ESPECIAL Y HAY MUCHAS MÁS: Hemos encontrado las 2 soluciones BF óptimas: (4,3,0,6,0) y (2,6,2,0,0). La combinación de estas soluciones nos proporcionan todas las demás soluciones que hay: ( X1,X2,X3,X4,X5) = w1 = (4,3,0,6,0) + w2 (2,6,2,0,0)w1 + w2 = 1 w1 ≥ 0 w2 ≥ 0 Ejemplo: 0.5 (4,3,0,6,0) + 0.5 (2,6,2,0,0) = (3,4.5,1,3,0) Esto se da porque los sumandos de la función objetivo coinciden exactamente con los sumandos de la tercera restricción funcional (misma pendiente).

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

FORMA ESTÁNDAR:

• Maximizar Z

• Restricciones Funcionales ≤

• Lados derechos positivos

• Restricciones de no negatividad

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

FORMAS NO ESTÁNDAR:

• Restricciones en forma de igualdad
• Minimización
• Otras:
• Restricciones funcionales ≥
• Lados derechos negativos
• Sin solución

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

SE HARÁN AJUSTES SOLO EN EL PASO INICIAL Y DESPUÉS YA SE PUEDE CONTINUAR CON EL MÉTODO SIMPLEX COMO LO HEMOS VISTO. SE USARÁ LA “TÉCNICA DE LAS VARIABLES ARTIFICIALES”

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

Se introduce una variable ficticia (variable artificial) en cada restricción que lo requiera. Esta variable en realidad tiene un valor de cero ya que es ficticia Esto se hace con el fin de que sea la variable básica inicial de esa ecuación La función objetivo se modifica para que imponga una penalización muy grande en el caso de que adquieran valores mayores a cero, Por lo que con las iteraciones las variables artificiales se vuelven cero hasta que quedan FUERA DE LA SOLUCIÓN Y YA SE RESUELVE ELPROBLEMA REAL

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

Maximizar Z = 3X1 + 5X2 sujeta a : X1 ≤ 4 2X2≤ 12 3X1 + 2X2 = 18 y X1 ≥ 0 X2 ≥0

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

LA FORMA AUMENTADA ES: (0) Z - 3X1 - 5X2 = 0(1) X1 + X3 = 4(2) 2X2 + X4 = 12(3) 3X1 + 2X2= 18(sin variable de holgura porque ya está desde el enunciado en forma de igualdad)En la ecuación (3) no hay variable de holgura por lo que no se puede incluir como variable básica inicial, lo cual dejaría a esta ecuación fuera del problema (X1 y X2 son no básicas).

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

Ya habiendo hecho los ajustes al paso inicial se puede encontrar la solución óptima aplicando el MÉTODO SIMPLEX al problema artificial.La solución BF inicial es la siguiente:Variables no básicas (las de decisión): X1 = 0 X2 = 0Variables básicas (holgura y artificial) : X3 = 4 X4 = 12 X5 = 18

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

PASOS PARA LA RESTRICCIÓN DE IGUALDAD:

1. VARIABLE ARTIFICIAL

(3) 3X1 + 2X2 + X5 = 18

1. X5 = variable artificial no negativa (como si fuera variable de holgura)

b. PENALIZACIÓN ENORME al hecho de tener X5 > 0 (porque en realidad debe de ser igual a cero). Esto implica cambiar la función objetivo a: Z = 3X1 + 5X2 – M X5 donde M es un número simbólico positivo muy grande

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

Z = 3X1 + 5X2 – M X5 donde M es un número simbólico positivo muy grandeMétodo de la gran M = obliga a X5 a llegar a cero en la solución óptima, con lo cual, el término – M X5 también se vuelve cero ypor lo tanto tendremos ya la Función Objetivo original*** CUANDO ES MAXIMIZACIÓN SE USA – M EN LAFUNCIÓN OBJETIVO, CUANDO ES MINIMIZACIÓN SEUSA + M EN LA FUNCIÓN OBJETIVO

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

El sistema de ecuaciones a resolver es: (0) Z - 3X1 - 5X2 + M = 0 Pasar términos a la izq(1) X1 + X3 = 4(2) 2X2 + X4 = 12(3) 3X1 + 2X2 + X5 = 18NOTAR QUE EN (0) HAY UNA VARIABLE BÁSICA, X5 POR LO QUE ANTES HAY QUE APLICAR ELIMINACIÓN GAUSSIANA PARA QUE QUEDEN SOLO LAS NO BÁSICAS

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. Restricciones en forma de igualdad

Resolviendo se llega a la solución BF óptima: (X1 ,X2,X3,X4, X5 )= (2,6,2,0,0)Z - 3X1 - 5X2 + MX5 = 0Z = 3X1 + 5X2 - MX5 despeje Z = 3 (2) + 5 (6) – M (0) = 36 sustituìmos

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

2. Minimización

Cualquier problema de minimización se puede convertir en un problema de maximización equivalente y así ya se puede aplicar el método simplex.

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

2. Minimización

El concepto se entiende mejor con un ejemplo sencillo: Si Z puede tomar valores entre 2 y 5 y queremos minimizar Z, el resultado es 2 Esto equivale a maximizar – Z y los valores que podría tomar estarían entre -2 y – 5, siendo el resultado – 2 (que es mayor a -5)Por lo que :

• Minimización: Z = 2 es lo mismo que
• Maximización: - Z = -2

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

2. Minimización

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

1. I. Restricciones en forma de igualdad
2. II. Minimización
3. III. Otras:
4. ❖ Restricciones funcionales ≥
5. ❖ Lados derechos negativos
6. ❖ Sin solución

MÉTODO SIMPLEX EN FORMA TABULAR

❖ RESTRICCIONES FUNCIONALES ≥ 2X1 - 3X2 ≥ 4Es equivalente a: 2X1 - 3X2 - X3 + X4 = 4X3 = variable de superávit para restar el exceso que se da por el signo >. Se resta porque es el proceso inversode la variable de holgura (cuando hay un faltante por el signo < y se suma)X4 = variable artificial que se usa para los casos de igualdades (como se explicó antes) y que permite incluir a X3 como no básica (=0) para que se cumpla que todas las variables sean ≥ 0. De lo contrario, con X1 y X2 =0, X3 sería -4 (no permitido)

MÉTODO SIMPLEX EN FORMA TABULAR

❖ RESTRICCIONES FUNCIONALES ≥ VARIABLES BÁSICAS Y NO BÁSICAS Si el modelo completo fuera: Función Objetivo Maximizar Z = 3X1 + 6X2 Única restricción funcional 2X1 - 3X2 ≥ 4Variables de no negatividad X1 y X2 ≥ 0La forma aumentada equivalente sería: Z – 3X1 – 6X2 + MX4 = 0 2X1 - 3X2 - X3 + X4 = 4

VARIABLES BÁSICAS Y NO BÁSICAS

AL INICIAR EL MÉTODO TABULAR BÁSICAS: ARTIFICIALES Y HOLGURA NO BÁSICAS: DECISIÓN Y SUPERÁVIT PASO PREVIO A PRIMERA TABLA ELIMINAR DE LA FUNCIÓN OBJETIVO LAS ARTIFICIALES POR SER BÁSICAS (IRÁN ACOMPAÑADAS POR LA “M”)

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

LADOS DERECHOS NEGATIVOS - 2X1 + 3X2 ≤ - 4 es equivalente a 2X1 - 3X2 ≥ 4Se cambian los signos y el sentido de la desigualdad

ADAPTACIÓN A OTRAS FORMAS DEL MODELO

SIN SOLUCIÓNSi en la tabla final (con la prueba de optimalidad ya superada), hay una o más variables de superávit o artificiales como variables básicas y que tengan un valor mayor a cero, el problema no tiene solución, habrán dos restricciones funcionales excluyentes (contradictorias), no habrá un área factible. SE DEBE REVISAR LA FORMULACIÓN DEL PROBLEMA DE PROGRAMACIÓN LINEAL.

Tarea : OTRAS FORMAS DEL MODELO/MÉTODO TABULAR

SUPREMA, S.A. fabrica y vende tres productos, sus costos unitarios son de $8, $12 y $16 respectivamente. Se trabajan 51 semanas al año, tipo de cambio Q7.80/$.Los productos usan dos tipos de materia prima con los siguientes requerimientos para c/u:Producto 1: 4 unidades de la materia prima A y 12 unidades de materia prima B Producto 2: 8 unidades de la materia prima A y 12 unidades de materia prima B Producto 3: 12 unidades de la materia prima A y 20 unidades de materia prima B

Tarea : OTRAS FORMAS DEL MODELO/MÉTODO TABULAR

De la materia prima A se dispone exactamente de 40 unidades por semana. De la materia prima B se dispone como mínimo de 80 unidades por semana.a) Modelo completo de Programación Lineal solo con variables de decisión ** INDISPENSABLE SIMPLIFICAR ANTES DE INICIAR b) Ecuaciones finales completas que se usarán para elaborar la primera tabla c) Primera VBE, primera VBS, primera solución básica factible completa anual en Qd) Encuentre todas las soluciones óptimas completas anuales en Quetzales e) ¿Cómo se plantearía el caso si se concreta un contrato de vender a un distribuidor como mínimo 24 unidades del producto 2 por semana?INCLUIR CARÁTULA, PROCEDIMIENTO Y HOJA DE RESPUESTAS

Feliz noche