Clase 02 Invope
Páginas: 16 (3844 palabras)
Publicado: 4 de abril de 2015
30/08/2014
Investigación de
Operaciones I
Ing. Enrique M. Avendaño Delgado
eavendano@hotmail.com
Unidad 1
PROGRAMACION LINEAL
Ing. Enrique M. Avendaño Delgado
eavendano@hotmail.com
1
30/08/2014
El Método Simplex:
• El método Simplex es un procedimiento iterativo que permite ir
mejorando la solución a cada paso. El proceso concluye cuando no
es posible seguir mejorando más dicha solución.• Partiendo del valor de la función objetivo en un vértice cualquiera,
el método consiste en buscar sucesivamente otro vértice que
mejore al anterior. La búsqueda se hace siempre a través de los
lados del polígono (o de las aristas del poliedro, si el número de
variables es mayor). Cómo el número de vértices (y de aristas) es
finito, siempre se podrá encontrar la solución
Ing. Enrique AvendañoDelgado
Ejemplo de Simplex:
Vamos a resolver el siguiente problema:
Maximizar
Z = 5x1 + 4x2
Sujeto a:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2
x1 ≥ 0 , x 2 ≥ 0
Ing. Enrique Avendaño Delgado
2
30/08/2014
Se consideran los siguientes pasos:
1.
Convertir las desigualdades en igualdades:
Se introduce una variable de holgura por cada una de las
restricciones, este caso s1, s2, s3 paraconvertirlas en igualdades y
formar el sistema de ecuaciones estandar. Usando en simplex el
siguiente criterio:
Signo:
≤
Introducir
sn
Ing. Enrique Avendaño Delgado
FORMA ESTANDAR:
6x1 + 4x2 + s1 = 24
x1 + 2x2 + s2 = 6
-x1 + x2 + s3 = 1
x2 + s4 = 2
Ing. Enrique Avendaño Delgado
3
30/08/2014
2. Igualar la función objetivo a cero y despues agregar la variables de holgura del
sistemaanterior:
Z - 5 x1 - 4 x2 = 0
La funcion objetivo ocupa la primera fila del tablero,
Cuando minimizamos se toma el valor (+) positivo de Fo para
convertirlo en negativo y cuando maximizamos tomamos el valor
(-) negativo de Fo para convertirlo en positivo.
3. Escribir el tablero inicial simplex:
En las columnas aparecerán todas las variables del problema y, en las
filas, los coeficientes de lasigualdades obtenidas, una fila para cada restricción y la
primera fila con los coeficientes de la función objetivo:
Ing. Enrique Avendaño Delgado
Tablero Inicial:
Básica
Z
X1
X2
S1
S2
S3
S4
Solución
Z
1
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Ing. Enrique Avendaño Delgado
4
30/08/2014
4.Encontrar la variable de decisión que entra en la base y la variable de holgura
que sale de la base
A. Para escoger la variable de decisión que entra en la base, observamos la
primera fila, la cual muestra los coeficientes de la función objetivo y escogemos la
variable con el coeficiente más negativo (en valor absoluto).
En este caso, la variable x1 de coeficiente - 5.
Si existiesen dos o máscoeficientes iguales que cumplan la condición anterior,
entonces se elige cualquiera de ellos.
Si en la primera 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 primera fila no haya elementos negativos.
La columna de la variable que entra en la base sellama columna pivote (en
color azulado).
Ing. Enrique Avendaño Delgado
Tablero Inicial:
Básica
Z
X1
X2
S1
S2
S3
S4
Solución
Z
1
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Ing. Enrique Avendaño Delgado
5
30/08/2014
Tablero Inicial:
Se elije el + negativo
Básica
Z
X1
X2
S1
S2
S3
S4Solución
Z
1
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Ing. Enrique Avendaño Delgado
Tablero Inicial:
Se elije el + negativo
Básica
Z
X1
X2
S1
S2
S3
S4
Solución
Z
1
-5
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1...
Investigación de
Operaciones I
Ing. Enrique M. Avendaño Delgado
eavendano@hotmail.com
Unidad 1
PROGRAMACION LINEAL
Ing. Enrique M. Avendaño Delgado
eavendano@hotmail.com
1
30/08/2014
El Método Simplex:
• El método Simplex es un procedimiento iterativo que permite ir
mejorando la solución a cada paso. El proceso concluye cuando no
es posible seguir mejorando más dicha solución.• Partiendo del valor de la función objetivo en un vértice cualquiera,
el método consiste en buscar sucesivamente otro vértice que
mejore al anterior. La búsqueda se hace siempre a través de los
lados del polígono (o de las aristas del poliedro, si el número de
variables es mayor). Cómo el número de vértices (y de aristas) es
finito, siempre se podrá encontrar la solución
Ing. Enrique AvendañoDelgado
Ejemplo de Simplex:
Vamos a resolver el siguiente problema:
Maximizar
Z = 5x1 + 4x2
Sujeto a:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
-x1 + x2 ≤ 1
x2 ≤ 2
x1 ≥ 0 , x 2 ≥ 0
Ing. Enrique Avendaño Delgado
2
30/08/2014
Se consideran los siguientes pasos:
1.
Convertir las desigualdades en igualdades:
Se introduce una variable de holgura por cada una de las
restricciones, este caso s1, s2, s3 paraconvertirlas en igualdades y
formar el sistema de ecuaciones estandar. Usando en simplex el
siguiente criterio:
Signo:
≤
Introducir
sn
Ing. Enrique Avendaño Delgado
FORMA ESTANDAR:
6x1 + 4x2 + s1 = 24
x1 + 2x2 + s2 = 6
-x1 + x2 + s3 = 1
x2 + s4 = 2
Ing. Enrique Avendaño Delgado
3
30/08/2014
2. Igualar la función objetivo a cero y despues agregar la variables de holgura del
sistemaanterior:
Z - 5 x1 - 4 x2 = 0
La funcion objetivo ocupa la primera fila del tablero,
Cuando minimizamos se toma el valor (+) positivo de Fo para
convertirlo en negativo y cuando maximizamos tomamos el valor
(-) negativo de Fo para convertirlo en positivo.
3. Escribir el tablero inicial simplex:
En las columnas aparecerán todas las variables del problema y, en las
filas, los coeficientes de lasigualdades obtenidas, una fila para cada restricción y la
primera fila con los coeficientes de la función objetivo:
Ing. Enrique Avendaño Delgado
Tablero Inicial:
Básica
Z
X1
X2
S1
S2
S3
S4
Solución
Z
1
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Ing. Enrique Avendaño Delgado
4
30/08/2014
4.Encontrar la variable de decisión que entra en la base y la variable de holgura
que sale de la base
A. Para escoger la variable de decisión que entra en la base, observamos la
primera fila, la cual muestra los coeficientes de la función objetivo y escogemos la
variable con el coeficiente más negativo (en valor absoluto).
En este caso, la variable x1 de coeficiente - 5.
Si existiesen dos o máscoeficientes iguales que cumplan la condición anterior,
entonces se elige cualquiera de ellos.
Si en la primera 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 primera fila no haya elementos negativos.
La columna de la variable que entra en la base sellama columna pivote (en
color azulado).
Ing. Enrique Avendaño Delgado
Tablero Inicial:
Básica
Z
X1
X2
S1
S2
S3
S4
Solución
Z
1
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Ing. Enrique Avendaño Delgado
5
30/08/2014
Tablero Inicial:
Se elije el + negativo
Básica
Z
X1
X2
S1
S2
S3
S4Solución
Z
1
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1
0
0
0
1
2
Ing. Enrique Avendaño Delgado
Tablero Inicial:
Se elije el + negativo
Básica
Z
X1
X2
S1
S2
S3
S4
Solución
Z
1
-5
-5
-4
0
0
0
0
0
S1
0
6
4
1
0
0
0
24
S2
0
1
2
0
1
0
0
6
S3
0
-1
1
0
0
1
0
1
S4
0
0
1...
Leer documento completo
Regístrate para leer el documento completo.