• Author / Uploaded
• mauro

• Categories
• Conceptos matemáticos
• Física y matemáticas
• Matemática
• Matemática aplicada
• Algoritmos

Citation preview

Método simplex casos especiales

Método Simplex Para realizar un problema de programación lineal, con cambio de variable, debido a que se encuentran con variables que no tienen restricciones de signo (o variables irrestrictas) se pueden transformar en un problema lineal el cual se requiere que todas las variables sean negativas.

Método Simplex En estos casos se empiezan por definir nuevas variables por cada variables irrestricta o ≤ 0, ≥ a un numero negativo o ≤ a un numero negativo. Estos casos se muestran a continuación:

Caso 1

Caso 2

Caso 3

Caso 4

Caso 5

Xn≤0

Xn≥0

Xn = SRS

Xn ≥ -m

Xn ≤ -m

Xn = X`n-X``n

Xn = X`n- m

Xn = -m-X`n

Xn=-X`n

Ejemplos de esas variables, son las que cuantifican efectivo en caja, temperaturas, niveles de inventario, y otras.

Método Simplex Min Z  3x1  2 x2

S/A  x1  x2  1...............(1)  7 x1  9 x2  63.........( 2) x1  3, x2  0 Como existe una variable mayor a -3, tenemos que realizar una cambio de variable, esto quiere decir que estamos en el caso 3, la cual queda

x1  3  x1  x`1 3

Método Simplex Si reemplazamos X1, en la función objetivo y en las restricciones tenemos: Min Z  3(x`1 -3)  2 x2

S/A  ( x`1 3)  x2  1  7( x`1 3)  9 x2  63 x`1  0, x2  0

Método Simplex Al ordenar nuestra función restricciones, nos queda Min Z  3x`1 -9  2 x2

objetivo

y

Min Z` 3x`1 2 x2

S/A

S/A

 x`1 3  x2  1

x`1  x2  2

 7 x`1 21  9 x2  63 x`1  0, x2  0

Con Z` Z  9

nuestras

 7 x`1 9 x2  42 x`1  0, x2  0 Recordar que por cada signo del tipo ≤ se agregan variables de holgura. Y por cada signo del tipo ≥ se resta una variables de exceso sumado con una variable artificial.

Método Simplex Forma Estandar, incorporando las variables de holguras Min Z`3x`1 2 x2  0

x`1  x2  x3  2  7 x`1 9 x2  x4  42 x`1 , x2 , x3 , x4  0

Forma Artificial, incorporando las variables artificiales. Min Z` 3x1  2 x2  Mx5

x`1  x2  x3  x5  2  7 x`1 9 x2  x4  42 x`1 , x2 , x3 , x4 , x5  0

X3=V. Exceso X4= V. holgura X5= V. Artificial Recordar que por cada variable artificial que incorporamos en las restricciones se suma (minimización) un Mai a la función objetivo. Para el caso de Maximización por cada variables artificial se resta un Mai.

Método Simplex Luego, debemos hacer desaparecer la variable artificial de nuestra función objetivo, despejando X5 de la restricción 1

x5  2  x`1  x2  x3 Min Z` 3x`1 2 x2  M (2  x`1  x2  x3 ) Min Z` 3x`1 2 x2  2 M  x`1 M  x2 M  x3 M Min Z`3x`1 2 x2  2 M  x`1 M  x2 M  x3 M  0 Min Z`3x`1  x`1 M  2 x2  x2 M  x3 M  2 M Min Z`(3  M ) x`1 (2  M ) x2  x3 M  2 M Min Z` ( M  3) x`1  ( M  2) x2  x3 M  2 M

Método Simplex X`1

X2

X3

X4

X5

Sol.

Z

(M-3)

(M-2)

-M

0

0

2M

X5

1

1

-1

0

1

2

X4

-7

9

0

1

0

42

Entra a la base X2 Sale de la base X5 Elemento pivote 1

Método Simplex X`1

X2

X3

X4

X5

Sol.

Z

-1

0

-2

0

-M+2

4

X5

1

1

-1

0

1

2

X4

16

0

9

1

-9

24

Como en Z son todos positivos (en caso minimización), estamos en el optimo, donde: Z=4 X2=2 X4=24

Método Simplex Ejercicios para taller: Min Z  2x1  x2

S/A  2 x1  3 x2  6  4 x1  5 x2  20 5 x1  3 x2  15 x1 : srs, x2  0

Método Simplex Un panadero tiene 30 onzas de harina y 5 paquetes de levadura. Para hornear una hogaza de pan necesita 5 onzas de harina y 1 paquete de levadura. Cada hogaza de pan se puede vender en 30 centavos. El panadero podría comprar mas harina a 4 centavos por onza o vender el sobrante de harina al mismo precio. Plantee y resuelva un PL para ayudar al panadero a maximizar la utilidad (ingresos – costos)

Método Simplex X1:Cantidad de hogazas de pan horneadas X2: Cantidad de onzas en que se incrementa el suministro de harina por las transacciones en efectivo.

Max Z  30x1  4 x2

S/A 5 x1  30  x2 ........ Re st.harina x1  5................... Re st.Levadura x1  0, x2 : srs