Método simplex

+1

No comments posted yet

Comments

Slide 1

Programación lineal: Método Simplex Por Lic. Gabriel Leandro, MBA www.auladeeconomia.com

Slide 2

Ejemplo 1

Slide 3

Ejemplo: Un sastre elabora dos tipos de trajes para hombre, blazer y ejecutivos. Se cuenta con dos procesos: corte y costura. Hacer un traje tipo blazer requiere 1 hora de corte y 1 hora de costura, mientras que uno de tipo ejecutivo requiere 1 hora de corte y 2 de costura. El sastre trabaja un total de 4 horas al día en corte y en el proceso de costura 6 horas. Las ganancias por la venta de un traje tipo blazer es $2 por unidad y $3 por cada traje tipo ejecutivo vendido. Calcular cuántos trajes de cada tipo hay que hacer para maximizar las ganancias.

Slide 4

Paso 1. Definir variables de decisión Un sastre elabora dos tipos de trajes para hombre, blazer y ejecutivos. Se cuenta con dos procesos: corte y costura. Hacer un traje tipo blazer requiere 1 hora de corte y 1 hora de costura, mientras que uno de tipo ejecutivo requiere 1 hora de corte y 2 de costura. El sastre trabaja un total de 4 horas al día en corte y en el proceso de costura 6 horas. Las ganancias por la venta de un traje tipo blazer es $2 por unidad y $3 por cada traje tipo ejecutivo vendido. Calcular cuántos trajes de cada tipo hay que hacer para maximizar las ganancias. X1 = Número de trajes tipo blazer X2 = Número de trajes tipo ejecutivo

Slide 5

Paso 2. Plantear la información en el formato: Recurso Variables de decisión X1 X2 … Xn Disponibilidad o limitante del recurso Función objetivo

Slide 6

Paso 2. Plantear la información en el formato Un sastre elabora dos tipos de trajes para hombre, blazer y ejecutivos. Se cuenta con dos procesos: corte y costura. Hacer un traje tipo blazer requiere 1 hora de corte y 1 hora de costura, mientras que uno de tipo ejecutivo requiere 1 hora de corte y 2 de costura. El sastre trabaja un total de 4 horas al día en corte y en el proceso de costura 6 horas. Las ganancias por la venta de un traje tipo blazer es $2 por unidad y $3 por cada traje tipo ejecutivo vendido. Calcular cuántos trajes de cada tipo hay que hacer para maximizar las ganancias. Recurso X1 X2 Disponibilidad Corte 1 1 4 Costura 1 2 6 F.O.: Ganancia 2 3

Slide 7

Paso 3. Definir función objetivo Recurso X1 X2 Disponibilidad Corte 1 1 4 Costura 1 2 6 F.O.: Ganancia 2 3 Maximizar Z = 2 X1 + 3 X2

Slide 8

Paso 4. Definir restricciones Recurso X1 X2 Disponibilidad Corte 1 1 4 Costura 1 2 6 F.O.: Ganancia 2 3 Maximizar Z = 2 X1 + 3 X2 Sujeto a X1 + X2  4 X1 + 2X2  6 X1, X2  0

Slide 9

Paso 5. Transformar restricciones y función objetivo Agregar variables de holgura, exceso y artificiales según corresponda Tipo de restricción Agregar En las restricciones En la función objetivo  … + Sn = … Z = … + 0Sn  … - Sn + An = … Z = … + 0Sn - MAn = … + An = … Z = … + MAn

Slide 10

Paso 5. Transformar restricciones y función objetivo Agregar variables de holgura, exceso y artificiales según corresponda Tipo de restricción Agregar En las restricciones En la función objetivo  … + Sn = … Z = … + 0Sn  … - Sn + An = … Z = … + 0Sn - MAn = … + An = … Z = … + MAn X1 + X2 + S1 = 4 X1 + 2X2 + S2 = 6 Z - 2 X1 - 3 X2 + 0S1 + 0S2 = 0

Slide 11

Paso 6. Elaborar cuadro de “coeficientes separados” Este paso se identifica como la iteración 0 Variables básicas Z Variables decisión Variables holgura Variables artificiales Valor Razón Sn o An según el caso Z

Slide 12

Paso 6. Elaborar cuadro de “coeficientes separados” Este paso se identifica como la iteración 0 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1

Slide 13

Paso 7. Identificar columna pivote Columna con el valor más negativo en fila Z Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1

Slide 14

Paso 8. Identificar fila pivote Se calcula columna razón = columna Valor / columna pivote Se elige el menor y no se considera el cero, infinito y fila Z Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1 4 / 1 = 4 4 6 / 2 = 3 3

Slide 15

Paso 9. Identificar número pivote Intersección entre fila y columna pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1 4 3

Slide 16

Paso 10. Sustituir la variable saliente por la entrante Y calcular números de variable entrante dividiendo cada uno de los números de la variable saliente entre el número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 Z S2 X2 Se divide entre número pivote = 2 0 1/2 0 3 1 1/2

Slide 17

Paso 11. Convertir en 0 los número de columna pivote Coeficiente anterior  coeficiente de variable entrante / número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 Z S2 X2 0 1/2 0 3 1 1/2 R1 – R2 / 2 0 1/2 1 1 0 -1/2 0 – 0 / 2 = 0 1 – 1 / 2 = 1/2 1 – 2 / 2 = 0 1 – 0 / 2 = 1 0 – 1 / 2 = -1/2 4 – 6 / 2 = 1

Slide 18

Paso 11. Convertir en 0 los número de columna pivote Coeficiente anterior  coeficiente de variable entrante / número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 4 Z 1 -2 0 0 1 -3 0 0 S2 0 1 0 6 2 1 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 1 1 Z 0 -1/2 S2 X2 0 1/2 0 3 1 1/2 R3 – R2 * -3 / 2 1 -1/2 0 0 3/2 1 – 0 * -3 / 2 = 1 -2 – 1 * -3 / 2 = -1/2 -3 – 2 * -3 / 2 = 0 0 – 0 * -3 / 2 = 0 0 – 1 * -3 / 2 = 3/2 0 – 6 * -3 / 2 = 9 9

Slide 19

Paso 12. Si hay signos negativos en fila Z, no es óptima Se repiten pasos 7 a 11 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 1 1 Z 1 -1/2 S2 X2 0 1/2 0 3 1 1/2 1 -1/2 0 0 3/2 9 Se tienen números negativos, hay que volver a repetir los pasos 7 a 11.

Slide 20

Paso 7. Identificar columna pivote Columna con el valor más negativo en fila Z Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 1 1 Z 1 -1/2 0 9 0 0 -1/2 3/2 X2 0 1/2 0 3 1 1/2

Slide 21

Paso 8. Identificar fila pivote Se calcula columna razón = columna Valor / columna pivote Se elige el menor y no se considera el cero, infinito y fila Z Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 1 1 Z 1 -1/2 0 9 0 0 -1/2 3/2 X2 0 1/2 0 3 1 1/2 1 / (1/2) = 2 2 3 / (1/2) = 6 6

Slide 22

Paso 9. Identificar número pivote Intersección entre fila y columna pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 1 1 Z 1 -1/2 0 9 0 0 -1/2 3/2 X2 0 1/2 0 3 1 1/2 2 6

Slide 23

Paso 10. Sustituir la variable saliente por la entrante Y calcular números de variable entrante dividiendo cada uno de los números de la variable saliente entre el número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 1 1 Z 1 -1/2 0 9 0 0 -1/2 3/2 X2 0 1/2 0 3 1 1/2 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 Z X2 X1 Se divide entre número pivote = 1/2 0 1 2 2 0 -1 0 / (1/2) = 0 (1/2) / (1/2) = 1 0 / (1/2) = 0 1 / (1/2) = 2 (-1/2) / (1/2) = -1 1 / (1/2) = 2

Slide 24

Paso 11. Convertir en 0 los número de columna pivote Coeficiente anterior  coeficiente de variable entrante / número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 2 1 Z 1 -1/2 0 9 0 0 -1/2 3/2 X2 0 1/2 0 3 1 1/2 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón X1 Z S2 X2 0 0 -1 2 1 1 R2 – R1 0 1 2 2 0 -1 0 – 0 = 0 (1/2) – (1/2) = 0 1 – 0 = 1 0 – 1 = -1 (1/2) – (-1/2) = 1 3 – 1 = 2

Slide 25

Paso 11. Convertir en 0 los número de columna pivote Coeficiente anterior  coeficiente de variable entrante / número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1/2 2 1 Z 1 -1/2 0 9 0 0 -1/2 3/2 S2 0 1/2 0 3 1 1/2 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón X1 0 1 2 2 Z 0 -1 S2 X1 0 0 -1 2 1 1 R3 + R1 1 0 1 0 1 1 + 0 = 1 (-1/2) + (1/2) = 0 0 + 0 = 0 0 + 1 = 1 (3/2) + (-1/2) = 1 9 + 1 = 10 10

Slide 26

Paso 12. Si hay signos negativos en fila Z, no es óptima Se repiten pasos 7 a 11 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón X1 0 1 2 2 Z 0 -1 S2 X2 0 0 -1 2 1 1 1 0 1 0 1 10 Se tienen números negativos, hay que volver a repetir los pasos 7 a 11.

Slide 27

Paso 13. Si no hay signos negativos en fila Z, es óptima La solución se puede observar en la columna Valor Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón X1 0 1 2 2 Z 0 -1 S2 X2 0 0 -1 2 1 1 1 0 1 0 1 10 X1 = 2 X2 = 2 Z = 10

Slide 28

Notas: Nota 1: Cuando se tiene una restricción del tipo “” esta se transformar en una restricción del tipo “” multiplicándola por -1. Nota 2: Cuando el problema es de minimización se multiplica la función objetivo por -1 para transformarla a su equivalente de maximización. Y la respuesta de Z final nuevamente se multiplica por -1 para convertir los resultados en valores equivalentes al problema original. Nota 3: Si se tienen restricciones del tipo “”, se debe utilizar variables artificiales para transformarlas a igualdades, las cuales tienen como valor M, que representa un número muy grande en relación con los datos del problema (generalmente se trabaja con una M igual a 1000). Nota 4: Este material se basa en la guía elaborada por el Ing. Héctor Guerra Patiño y modificada por el Ing. José Félix Amado González.

Slide 29

Ejemplo 2

Slide 30

Ejemplo: Una fábrica de muebles elabora dos tipos de sillones, tradicional y moderno. La fábrica cuenta con dos procesos: carpintería y tapicería. Hacer un sillón tipo tradicional requiere 1 hora de carpintería y 2 de tapicería, mientras que uno de tipo moderno requiere 3 horas de carpintería y 1 de tapicería. El personal de tapicería trabaja un total de 80 horas a la semana y el de carpintería 90 horas. Las ganancias por las ventas de un sillón tradicional son $60 por unidad y $30 por cada sillón moderno. Calcular cuántos sillones de cada tipo hay que hacer para maximizar las ganancias.

Slide 31

Paso 1. Definir variables de decisión Una fábrica de muebles elabora dos tipos de sillones, tradicional y moderno. La fábrica cuenta con dos procesos: carpintería y tapicería. Hacer un sillón tipo tradicional requiere 1 hora de carpintería y 2 de tapicería, mientras que uno de tipo moderno requiere 3 horas de carpintería y 1 de tapicería. El personal de tapicería trabaja un total de 80 horas a la semana y el de carpintería 90 horas. Las ganancias por las ventas de un sillón tradicional son $60 por unidad y $30 por cada sillón moderno. Calcular cuántos sillones de cada tipo hay que hacer para maximizar las ganancias. X1 = Número de sillones tipo tradicional X2 = Número de sillones tipo moderno

Slide 32

Paso 2. Plantear la información en el formato: Recurso Variables de decisión X1 X2 … Xn Disponibilidad o limitante del recurso Función objetivo

Slide 33

Paso 2. Plantear la información en el formato Una fábrica de muebles elabora dos tipos de sillones, tradicional y moderno. La fábrica cuenta con dos procesos: carpintería y tapicería. Hacer un sillón tipo tradicional requiere 1 hora de carpintería y 2 de tapicería, mientras que uno de tipo moderno requiere 3 horas de carpintería y 1 de tapicería. El personal de tapicería trabaja un total de 80 horas a la semana y el de carpintería 90 horas. Las ganancias por las ventas de un sillón tradicional son $60 por unidad y $30 por cada sillón moderno. Calcular cuántos sillones de cada tipo hay que hacer para maximizar las ganancias. Recurso X1 X2 Disponibilidad Carpintería 1 3 90 Tapicería 2 1 80 F.O.: Ganancia 60 30

Slide 34

Paso 3. Definir función objetivo Recurso X1 X2 Disponibilidad Carpintería 1 3 90 Tapicería 2 1 80 F.O.: Ganancia 60 30 Maximizar Z = 60 X1 + 30 X2

Slide 35

Paso 4. Definir restricciones Recurso X1 X2 Disponibilidad Carpintería 1 3 90 Tapicería 2 1 80 F.O.: Ganancia 60 30 Maximizar Z = 60 X1 + 30 X2 Sujeto a X1 + 3 X2  90 2X1 + X2  80 X1, X2  0

Slide 36

Paso 5. Transformar restricciones y función objetivo Agregar variables de holgura, exceso y artificiales según corresponda Tipo de restricción Agregar En las restricciones En la función objetivo  … + Sn = … Z = … + 0Sn  … - Sn + An = … Z = … + 0Sn - MAn = … + An = … Z = … + MAn

Slide 37

Paso 5. Transformar restricciones y función objetivo Agregar variables de holgura, exceso y artificiales según corresponda Tipo de restricción Agregar En las restricciones En la función objetivo  … + Sn = … Z = … + 0Sn  … - Sn + An = … Z = … + 0Sn - MAn = … + An = … Z = … + MAn X1 + 3 X2 + S1 = 90 2X1 + X2 + S2 = 80 Z - 60 X1 - 30 X2 + 0S1 + 0S2 = 0

Slide 38

Paso 6. Elaborar cuadro de “coeficientes separados” Este paso se identifica como la iteración 0 Variables básicas Z Variables decisión Variables holgura Variables artificiales Valor Razón Sn o An según el caso Z

Slide 39

Paso 6. Elaborar cuadro de “coeficientes separados” Este paso se identifica como la iteración 0 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1

Slide 40

Paso 7. Identificar columna pivote Columna con el valor más negativo en fila Z Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1

Slide 41

Paso 8. Identificar fila pivote Se calcula columna razón = columna Valor / columna pivote Se elige el menor y no se considera el cero, infinito y fila Z Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1 90 / 1 = 90 90 80 / 2 = 40 40

Slide 42

Paso 9. Identificar número pivote Intersección entre fila y columna pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1 90 40

Slide 43

Paso 10. Sustituir la variable saliente por la entrante Y calcular números de variable entrante dividiendo cada uno de los números de la variable saliente entre el número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 Z S2 X1 Se divide entre número pivote = 2 0 1 0 40 1/2 1/2

Slide 44

Paso 11. Convertir en 0 los número de columna pivote Coeficiente anterior  coeficiente de variable entrante / número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 Z S2 X1 0 1 0 40 1/2 1/2 R1 – R2 / 2 0 0 1 50 5/2 -1/2 0 – 0 / 2 = 0 1 – 2 / 2 = 0 3 – 1 / 2 = 5/2 1 – 0 / 2 = 1 0 – 1 / 2 = -1/2 90 – 80 / 2 = 50

Slide 45

Paso 11. Convertir en 0 los número de columna pivote Coeficiente anterior  coeficiente de variable entrante / número pivote Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 1 1 90 Z 1 -60 0 0 3 -30 0 0 S2 0 2 0 80 1 1 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 0 1 50 Z 5/2 -1/2 S2 X1 0 1 0 40 1/2 1/2 R3 – R2 * -60 / 2 1 0 0 0 30 1 – 0 * -60 / 2 = 1 -60 – 2 * -60 / 2 = 0 -30 – 1 * -60 / 2 = 0 0 – 0 * -60 / 2 = 0 0 – 1 * -60 / 2 = -1/2 0 – 80 * -60 / 2 = -2400 2400

Slide 46

Paso 12. Si hay signos negativos en fila Z, no es óptima Se repiten pasos 7 a 11 Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 0 1 50 Z 5/2 -1/2 S2 X1 0 1 0 40 1/2 1/2 1 0 0 0 30 2400 No se tienen números negativos

Slide 47

Paso 13. Si no hay signos negativos en fila Z, es óptima La solución se puede observar en la columna Valor Var. Bás. Z Var. Dec. X1 X2 Var. Holg. S1 S2 Valor Razón S1 0 0 1 50 Z 5/2 -1/2 S2 X1 0 1 0 40 1/2 1/2 1 0 0 0 30 2400 X1 = 40 X2 = 0 Z = 2400

Slide 48

¡Muchas gracias!

Summary: Resolución de problemas de programación lineal mediante el método simplex.

Tags: programacion lineal metodo simplex métodos cuantitativos investigación de operaciones

URL:
More by this User
Most Viewed