INVESTIGACION DE OPERACIONES CLASE 06 Mail
Páginas: 8 (1938 palabras)
Publicado: 24 de noviembre de 2015
4/11/2015
Método Simplex
1
El Método Simplex
Restricciones (limitaciones del conjunto de soluciones)
s.a
Variables de
decisión
Coeficientes
Tecnológicos
a11x1+a12x2+..+a1nxn = b1
a21x1+a22x2+..+a2nxn = b2
Coeficientes
de Recursos
.................................................
am1x1+am2x2+..+ammxn = bm
Otras restricciones características del tipo de variables
x1,x2,...xn 0
Formato Estandar
• Max Z=3X1+5X2
•
•
•
•
s.a.
X14
2X2 12
3X1+2X2 18
X1
+ S1
= 4
2X2
+ S2
= 12
3X1 + 2X2
+S3 = 18
Z=3x1+5x2+0S1+0S2+0S3
Z-3X1-5X2-0S1-0S2-0S3=0
1
4/11/2015
Método
Práctico
El Método Simplex
Con miras a conocer la metodología que se aplica en el Método
SIMPLEX, vamos a resolver el siguiente problema:
Maximizar
Z= f(x,y)= 3x + 2y
sujeto a:
2x + y ≤ 18
2x + 3y ≤42
3x + y ≤ 24
X≥0,y≥0
5
El Método Simplex
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para
convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + h
= 18
2x + 3y
+s
= 42
3x + y
+ d = 24
6
2
4/11/2015
El Método Simplex
2. Igualar la función objetivo acero
- 3x - 2y = 0
7
El Método Simplex
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los
coeficientes de las igualdades obtenidas, una fila para cada restricción y la
última fila con los coeficientes de la función objetivo:
Tabla I . Iteración nº 1
Base
Variable de
decisión
Variable de holgura
x
y
h
3
0
h
2
1
d
3
1s
Z
2
-3
-2
s
d
1
0
1
0
0
0
0
0
Valores
solución
0
18
1
24
0
42
0
8
El Método Simplex
4. Encontrar la variable de decisión que entra en la
base y la variable de holgura que sale de la base
•Para escoger la variable de decisión que entra en la base, nos fijamos en la
última fila, la de los coeficientes de la función objetivo y escogemos la variable
con el coeficientenegativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente
- 3.
La columna de la variable que entra en la base se llama columna pivote (En
color azulado).
9
3
4/11/2015
El Método Simplex
4. Encontrar la variable de decisión que entra en la
base y la variable de holgura que sale de la base
IMPORTANTE:
Si existiesen dos o más coeficientes iguales que cumplan la condiciónanterior,
entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha
alcanzado la solución óptima.
Por tanto, lo que va a determinar el final del proceso de aplicación del método
del simplex, es que en la última fila no haya elementos negativos.
10
El Método Simplex
Columna Pivote
Base
h
s
d
Z
Tabla I . Iteración nº 1
Variablede
decisión
x
y
h
3
0
2
1
3
1
2
-3
Variable de holgura
-2
s
d
Valores
solución
1
0
0
18
0
0
1
24
0
1
0
0
Mayor Numero
Negativo de la fila Z
0
42
0
11
El Método Simplex
Para encontrar la variable de holgura que tiene que salir de la
base
•Se divide cada término de la última columna (valores solución)
por el término correspondiente de la columna pivote, siempre queestos últimos sean mayores que cero.
•En nuestro caso:
18/2 =9
42/2 =21 y
24/3 =8
12
4
4/11/2015
h 18/2 = 9
s 42/2 = 21
d 24/3 = 8
Tabla I . Iteración nº 1
Base
Variable de
decisión
x
y
h
3
0
h
2
1
d
3
1
s
Z
2
-3
Variable de holgura
-2
s
d
Valores
solución
1
0
0
18
0
0
1
24
0
1
0
0
0
42
0
13
El Método Simplex
Si hubiese algún elemento menor o igual que cerono se hace dicho cociente.
En el caso de que todos los elementos fuesen menores o iguales a cero,
entonces tendríamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor
cociente positivo,
8 es el menor
indica la fila de la variable de holgura que sale de la base,
Esta fila se llama fila pivote (En color azulado).
d.
Si...
Método Simplex
1
El Método Simplex
Restricciones (limitaciones del conjunto de soluciones)
s.a
Variables de
decisión
Coeficientes
Tecnológicos
a11x1+a12x2+..+a1nxn = b1
a21x1+a22x2+..+a2nxn = b2
Coeficientes
de Recursos
.................................................
am1x1+am2x2+..+ammxn = bm
Otras restricciones características del tipo de variables
x1,x2,...xn 0
Formato Estandar
• Max Z=3X1+5X2
•
•
•
•
s.a.
X14
2X2 12
3X1+2X2 18
X1
+ S1
= 4
2X2
+ S2
= 12
3X1 + 2X2
+S3 = 18
Z=3x1+5x2+0S1+0S2+0S3
Z-3X1-5X2-0S1-0S2-0S3=0
1
4/11/2015
Método
Práctico
El Método Simplex
Con miras a conocer la metodología que se aplica en el Método
SIMPLEX, vamos a resolver el siguiente problema:
Maximizar
Z= f(x,y)= 3x + 2y
sujeto a:
2x + y ≤ 18
2x + 3y ≤42
3x + y ≤ 24
X≥0,y≥0
5
El Método Simplex
Se consideran las siguientes fases:
1. Convertir las desigualdades en igualdades
Se introduce una variable de holgura por cada una de las restricciones, para
convertirlas en igualdades, resultando el sistema de ecuaciones lineales:
2x + y + h
= 18
2x + 3y
+s
= 42
3x + y
+ d = 24
6
2
4/11/2015
El Método Simplex
2. Igualar la función objetivo acero
- 3x - 2y = 0
7
El Método Simplex
3. Escribir la tabla inicial simplex
En las columnas aparecerán todas las variables del problema y, en las filas, los
coeficientes de las igualdades obtenidas, una fila para cada restricción y la
última fila con los coeficientes de la función objetivo:
Tabla I . Iteración nº 1
Base
Variable de
decisión
Variable de holgura
x
y
h
3
0
h
2
1
d
3
1s
Z
2
-3
-2
s
d
1
0
1
0
0
0
0
0
Valores
solución
0
18
1
24
0
42
0
8
El Método Simplex
4. Encontrar la variable de decisión que entra en la
base y la variable de holgura que sale de la base
•Para escoger la variable de decisión que entra en la base, nos fijamos en la
última fila, la de los coeficientes de la función objetivo y escogemos la variable
con el coeficientenegativo mayor (en valor absoluto).
En nuestro caso, la variable x de coeficiente
- 3.
La columna de la variable que entra en la base se llama columna pivote (En
color azulado).
9
3
4/11/2015
El Método Simplex
4. Encontrar la variable de decisión que entra en la
base y la variable de holgura que sale de la base
IMPORTANTE:
Si existiesen dos o más coeficientes iguales que cumplan la condiciónanterior,
entonces se elige uno cualquiera de ellos.
Si en la última fila no existiese ningún coeficiente negativo, significa que se ha
alcanzado la solución óptima.
Por tanto, lo que va a determinar el final del proceso de aplicación del método
del simplex, es que en la última fila no haya elementos negativos.
10
El Método Simplex
Columna Pivote
Base
h
s
d
Z
Tabla I . Iteración nº 1
Variablede
decisión
x
y
h
3
0
2
1
3
1
2
-3
Variable de holgura
-2
s
d
Valores
solución
1
0
0
18
0
0
1
24
0
1
0
0
Mayor Numero
Negativo de la fila Z
0
42
0
11
El Método Simplex
Para encontrar la variable de holgura que tiene que salir de la
base
•Se divide cada término de la última columna (valores solución)
por el término correspondiente de la columna pivote, siempre queestos últimos sean mayores que cero.
•En nuestro caso:
18/2 =9
42/2 =21 y
24/3 =8
12
4
4/11/2015
h 18/2 = 9
s 42/2 = 21
d 24/3 = 8
Tabla I . Iteración nº 1
Base
Variable de
decisión
x
y
h
3
0
h
2
1
d
3
1
s
Z
2
-3
Variable de holgura
-2
s
d
Valores
solución
1
0
0
18
0
0
1
24
0
1
0
0
0
42
0
13
El Método Simplex
Si hubiese algún elemento menor o igual que cerono se hace dicho cociente.
En el caso de que todos los elementos fuesen menores o iguales a cero,
entonces tendríamos una solución no acotada y no se puede seguir.
El término de la columna pivote que en la división anterior dé lugar al menor
cociente positivo,
8 es el menor
indica la fila de la variable de holgura que sale de la base,
Esta fila se llama fila pivote (En color azulado).
d.
Si...
Leer documento completo
Regístrate para leer el documento completo.