UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

FACULTAD DE ESTUDIOS SUPERIORES ACATLÁN

MATEMÁTICAS APLICADAS Y COMPUTACIÓN

“Conceptos y ejemplo del método simplex”

JIMÉNEZ CORONEL JOSÉ GAMALIEL

ACOSTA ARIZMENDI JÜRGUEN

PROFRA. GUADALUPE DEL CARMEN RODRÍGUEZ MORENO

Variable de holgura

Se usa para convertir en igualdad una desigualdad de tipo "≤".

La igualdad se obtiene al adicionar en el lado izquierdo de la desigualdad una variable no negativa, que representa el valor que le hace falta al lado izquierdo para ser igual al lado derecho.

Esta se conoce como variable de holgura, y en el caso particular en el que las restricciones de tipo ≤ se refieren al consumo máximo de un recurso, la variable adicionada cuantifica la cantidad sobrante de recurso (cantidad no utilizada) al poner en ejecución la solución óptima.

Ejemplo

Max z = X1 + 5X2 +2 X3                 Max z = X1 + 5X2 + 2X3

s.a                                                      s.a

X1 + X2 + X3 <= 10                         X1 + X2 + X3 + X4 = 10

2X1 + X2 + 7X3 <= 15                     2X1 + X2 +7 X3 + X5 = 15

5X1 + X2 + 3X3 <= 5                       5X1 + X2 + 3X3 + X6 = 5

Xi >= 0  i=1-3                                   Xi >= 0  i=1-6

Variables de holgura: X4, X5 y X6.

Variable de exceso

Se usa para convertir en igualdad una desigualdad del tipo "≥"

Se realiza al restar en el lado izquierdo de la desigualdad, una variable no negativa, que representa el valor en el cual el valor del lado izquierdo excede al derecho. A esta variable la llamaremos variable de exceso y en el caso particular en el que las restricciones de tipo ≥ se refieran al contenido mínimo de un ingrediente en una mezcla, la variable adicionada indica cuánto ingrediente en exceso sobre el mínimo exigido contendrá la mezcla.

Ejemplo

Min z = 3X1 + 6X2 – X3                  Min z = 3X1 + 6X2 – X3

s.a                                                      s.a

X1 + 6X2 – X3 >= 12                       X1 + 6X2 – X3 – X4 >= 12

2X1 + X2 – 7X3 >= 18                     2X1 + X2 –7 X3 – X5 >= 18

X1 + X2 – X3 >= 7                           X1 + X2 – X3 – X6 >= 7

Xi >= 0  i=1-3                                   Xi >= 0  i=1-6

Variables de exceso: X4, X5 y X6.

Variable no restringida

Una variable no restringida, o sea aquella que puede tomar toda clase de valores positivos, cero y negativos puede escribirse como la diferencia de dos variables no negativas.

Ejemplo

Sea X1 una variable no restringida, entonces

          X1 = X2 –X3

donde X2>=0, X3>=0. Nótese que si  X2>X3, eso implica que X1>0; si X2=X3, entonces X1=0; si X2<X3 se tiene que X1<0.

Variables básicas y no básicas

Se denominan variables básicas a las variables del vector xB formado por las m variables asociadas con la solución básica y variables no básicas a las n-m restantes variables que se han igualado a cero.

Ejemplo

Forma estándar del modelo

Max z = 3X1 + 2X2                    Solución de la primera iteración

s.a                                                 X1=0, X2=0, X3=6, X4=8, X5=1, X6=2

X1 + 2X2 + X3 = 6                      Variables básicas: X3, X4, X5, X6

2X1 + X2 + X4 = 8                       Variables no básicas: X1, X2

-X1 + X2 + X5 = 1

           X2 + X6 = 2

X1, X2 >=0

Variable de entrada y salida

Variable de entrada: Garantiza que la función objetivo mejora.

Variable de salida: Es aquella que tiene una razón mínima positiva entra la solución de la restricción (bi) y el coeficiente de la variable que entra (ai).

Ejemplo

Forma estándar del modelo

Max z = 3X1 + 2X2                    Solución de la primera iteración

s.a                                                 X1=0, X2=0, X3=6, X4=8, X5=1, X6=2, Z=0

X1 + 2X2 + X3 = 6                      Variables básicas: X3, X4, X5, X6

2X1 + X2 + X4 = 8                      Variables no básicas: X1, X2

-X1 + X2 + X5 = 1                       Solución de la segunda iteración                    

           X2 + X6 = 2                       X1=4, X2=0, X3=2, X4=0, X5=5, X6=2, Z=12

X1, X2 >=0                                   Variables básicas: X3, X1, X5, X6

                                                      Variables no básicas: X4, X2

                                                      Variable de entrada (se convierte en básica): X1

                                                      Variable de salida (se convierte en no básica): X4

Programación lineal

Se entiende por programación lineal aquel que optimiza:

                    Z = cX  ------------------------ (1)

sujeto a

                    AX <=, = ó >= b  -------------(2)

                    X >= 0    ------------------------(3)

Donde la función lineal (1) se llama función objetivo; las desigualdades (2) se llaman restricciones y a (3) se lo conoce como condición de no negatividad. La palabra optimizar puede significar maximizar o minimizar.

Ejemplo

Minimizar z = 6/16X1 + 8/16X2

s.a

100X1 + 200X2 >= 1000

400X1 + 250X2 >= 2000

200X1 + 200X2 >= 1500

X1, X2 >= 0

Forma canónica

La forma canónica de un problema de programación lineal es:

                         n

            max z= ∑ cjXj

                         j=1

s.a

           n

           ∑ aijXj  <= bi, para i=1,…, m

           j=1

               

                     Xj >= 0, para j=1,…, n

Ejemplo                                            

                                                    Forma canónica

Min z = 16X1 + X2                        Max z = -16X1 - X2

s.a                                                 s.a

X1 + 5X2 >= 100                         - X1 - 5X2 <= -100

4X1 - 2X2 >= 200                        - 4X1 + 2X2 <= -200

2X1 + X2 >= 150                          -2X1 - X2 <= -150

X1, X2 >= 0                                  X1, X2 >= 0

Forma estándar

La forma estándar de un problema de programación lineal es:

                         n

            max z= ∑ cjXj

                         j=1

s.a

           n

           ∑ aijXj  = bi, para i=1,…, m

           j=1

               

                     Xj >= 0, para j=1,…, n

Ejemplo

                                                          Forma estándar

Min z = 3X1 + 6X2 – X3                  Min z = 3X1 + 6X2 – X3

s.a                                                      s.a

X1 + 6X2 – X3 >= 12                       X1 + 6X2 – X3 – X4 >= 12

2X1 + X2 – 7X3 >= 18                     2X1 + X2 –7 X3 – X5 >= 18

X1 + X2 – X3 >= 7                           X1 + X2 – X3 – X6 >= 7

Xi >= 0  i=1-3                                   Xi >= 0  i=1-6

Solución básica

Es la solución de un sistema de ecuaciones mxn donde n-m variable se hacen cero y se resuelve el problema.

Ejemplo

Max z = 3X1 + 2X2                    Solución basica

s.a                                                 X1=10/3, X2=4/3, X3=0, X4=0, X5=3, X6=2/3, Z=38/3

X1 + 2X2 + X3 = 6                      Variables básicas: X2, X1, X5, X6

2X1 + X2 + X4 = 8                      Variables no básicas: X4, X3

-X1 + X2 + X5 = 1                      

           X2 + X6 = 2                      

 X1, X2 >=0                  

Solución múltiple

Cuando la función objetivo es paralela a una restricción que se satisface en el sentido de la igualdad a través de la solución óptima, la función objetivo tomará el mismo valor óptimo en más de un punto de la solución. Por esta razón reciben el nombre de Múltiples alternativas óptimas.

Ejemplo

Max z = 4X1 + 14X2

s.a

2X1 + 7X2 <= 21 ------------ (1)

7X1 + 2X2 <= 21 ------------ (2)

X1, X2 >= 0

Como la función objetivo es paralela a la restricción 1 entonces el problema tendrá una solución múltiple.

Ejemplo de solución de un problema de programación lineal por el método simplex 

En una pastelería se hacen dos tipos de tartas: Vienesa y Real. Cada tarta Vienesa necesita un cuarto de relleno por cada Kg. de bizcocho y produce un beneficio de 250 pesos, mientras que una tarta Real necesita medio Kg. de relleno por cada Kg. de bizcocho y produce 400 pesos de beneficio. En la pastelería se pueden hacer diariamente hasta 150 Kg. de bizcocho y 50 Kg. de relleno, aunque por problemas de maquinaria no pueden hacer mas de 125 tartas de cada tipo. ¿Cuántas tartas Vienesas y cuantas Reales deben vender al día para que sea máximo el beneficio?

X1= número de tartas vienesa a producir

X2= número de tartas real a producir


Función objetivo                              

Max z = 250X1 + 400X2         --------------- F.O.            
s. a

X1 + X2 <= 150                       --------------- (1)

0.250X1 + 0.500X2 <= 50       --------------- (2)

X1<=125                                  --------------- (3)

X2<=125                                  --------------- (4)

X1,X2 >=0

La función objetivo nos dice que tenemos que maximizar la ganancia de la pastelería para lo que debemos de saber cuantas tartas de cada tipo se tienen que producir.

Restricciones

1.- La restricción nos dice que la suma del total de tartas que se haga de cada tipo deben de sumar una cantidad <= a 150 kg de bizcocho.

2-. La restricción nos dice que la cantidad de tartas vienesa multiplicado por 0.250 kg de relleno mas la cantidad de tartas real multiplicado por 0.500 kg de relleno debe de ser <= a 50 kg de relleno.

3.- La restricción nos indica que el numero de tartas a producir tipo vienesa debe ser <= 125 tartas.

 4.- La restricción nos indica que el numero de tartas a producir tipo real debe ser <= 125 tartas.

Tenemos la condición de no negatividad de que el número de tartas de cada tipo debe ser >= 0.

Forma estándar del modelo

Max z = 250X1 + 400X2         
s. a

X1 + X2 + X3 = 150                       --------------- (1)

0.250X1 + 0.500X2 + X4 = 50       --------------- (2)

X1+ X5 =125                                  --------------- (3)

X2 + X6 =125                                  --------------- (4)

Xi >=0, i=1-6

Aplicación del método simplex

Tabla principal

z

x1

x2

x3

x4

x5

x6

Solución

Razón

zj-cj

1

-250

-400

0

0

0

0

0

x3

0

1

1

1

0

0

0

150

150

x4

0

0.25

0.5

0

1

0

0

50

100

x5

0

1

0

0

0

1

0

125

#¡DIV/0!

x6

0

0

1

0

0

0

1

125

125

1.-Encontramos que el renglón pivote es el que pertenece a x4 por medio de la razón.

2.-La columna pivote es la que pertenece a x2 ya que su valor en el zj-cj es el mas negativo

3.-Su elemento pivote será la intersección entre los 2 anteriores por lo que el pivote es .5

Ahora aplicamos Gauss Jordan para la primera iteración.

Iteración 1

z

x1

x2

x3

x4

x5

x6

Solución

zj-cj

1

-50

0

0

800

0

0

40000

Razón

x3

0

0.5

0

0

-2

0

0

50

100

x2

0

0.5

1

0

2

0

0

100

200

x5

0

1

0

0

0

1

0

125

125

x6

0

-0.5

0

0

-2

0

1

25

-50

En esta segunda tabla tenemos que:

1.-Encontramos que el renglón pivote es el que pertenece a x3 por medio de la razón.

2.-La columna pivote es la que pertenece a x1 ya que su valor en el zj-cj es el mas negativo

3.-Su elemento pivote será la intersección entre los 2 anteriores por lo que el pivote es .5

Ahora aplicamos Gauss Jordan para la segunda iteración.

Iteración 2

z

x1

x2

x3

x4

x5

x6

Solución

zj-cj

1

0

0

0

600

0

0

45000

x1

0

1

0

0

-4

0

0

100

x2

0

0

1

0

3

0

0

50

x5

0

0

0

0

1

1

0

25

x6

0

0

0

0

-1

0

1

75

En la segunda iteración encontramos que el renglón del zj-cj contiene todos sus valores positivos y como el problema es de maximización, eso quiere decir que llegamos a la solución optima.

Por lo tanto la solución es:

Dada la solución del modelo, esto nos dice que se tienen que producir 100 tartas vienesa y 50 tartas real al dia para obtener una utilidad máxima de $45000 pesos.

Por otra parte dado que 2 de las variables de holgura son variables básicas esto nos dice que el número de tartas que se produjeron es el suficiente para obtener la utilidad máxima más no el máximo número de tartas que se preveía se podrían hacer. Esto quiere decir que de 125 tartas vienesa que se podían fabricar solo se produjeron 100 y tienen un sobrante de 25 tartas ya que se acabaron los demás recursos y de 125 tartas reales solo se produjeron 50 teniendo un sobrante de 72 tartas por el mismo caso.