Upload
ssapolo
View
193
Download
0
Embed Size (px)
Citation preview
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 1/19
Juan José Bravo B., M.Sc.
Solución de Modelos de Programación Lineal
El Metodo Simplex
Ju an Jo séBravo B, M.Sc. ©
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 2/19
Juan José Bravo B., M.Sc.
EL MÉTODO SIMPLEX
Es un método genérico de solución de problemas lineales,desarrollado por George Dantzig en 1947.
Como tal, el método simplex es un procedimientoalgebraico, pero puede entenderse más fácilmente comoun método geométrico.
Antes de explicar los aspectos geométricos del Simplex,veremos el tratamiento que debe hacerse a cualquier
modelo de PL antes de aplicar el Método Simplex sobre élpara solucionarlo.
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 3/19
Juan José Bravo B., M.Sc.
Conversión de modelos de PL a laForma Estándar
Todo modelo de PL, para efectos de resolverse con el Método Simplex, debellevarse a una Forma Estándar con las siguientes características:
1. El lado derecho de las ecuaciones debe ser no-negativo
2. Todas las restricciones deben convertirse a Ecuaciones
3. Todas las variables deben ser no-negativas
EJEMPLO: Maximizar Z = 2x1 + 3x2 + x3
Sujeto a: x1 + x2 + x3 = 10
-2x1 + 3x2 + 2x3 ≤ -5
7x1 - 4x2 + 5x3 ≤ 6
x1 + 4x2 + 3x3 ≥ 8
x1 no restringida, x2 ≤ 0, x3 ≥0
/1
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 4/19
Juan José Bravo B., M.Sc.
Conversión de modelos de PL a laForma Estándar
/2
Maximizar Z = 2x1 + 3x2 + x3
Sujeto a: x1 + x2 + x3 = 10
-2x1 + 3x2 + 2x3 ≤ -5
7x1 - 4x2 + 5x3 ≤ 6
x1 + 4x2 + 3x3 ≥ 8
x1 no restringida, x2 ≤ 0, x3 ≥0
Maximizar Z = 2x1 + 3x2 + x3
Sujeto a: x1 + x2 + x3 = 10
2x1 - 3x2 - 2x3 ≥ 5
7x1 - 4x2 + 5x3 ≤ 6
x1 + 4x2 + 3x3 ≥ 8
x1 no restringida, x2 ≤ 0, x3 ≥0
Maximizar Z = 2x1 + 3x2 + x3
Sujeto a: x1 + x2 + x3 = 10
2x1 - 3x2 - 2x3 – S1 = 5
7x1 - 4x2 + 5x3 + S2 = 6
x1 + 4x2 + 3x3 – S3 = 8
x1 no restringida, x2 ≤ 0, x3 ≥0, S1≥0,S2≥0, S3≥0
1
2
Maximizar Z = 2x1 – 3x’ 2 + x3
Sujeto a: x1 – x’ 2 + x3 = 10
2x1 + 3x’ 2 - 2x3 – S1 = 5
7x1 + 4x’ 2 + 5x3 + S2 = 6
x1 - 4x’ 2 + 3x3 – S3 = 8
x1
no restringida, x’ 2 ≥ 0, x
3 ≥ 0, S
1≥0,
S2≥0, S3≥0
3a
x2=-x’ 2
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 5/19
Juan José Bravo B., M.Sc.
Conversión de modelos de PL a laForma Estándar
/3
3b
Maximizar Z = 2x1 – 3x’ 2 + x3
Sujeto a: x1 – x’ 2 + x3 = 10
2x1 + 3x’ 2 - 2x3 – S1 = 5
7x1 + 4x’ 2 + 5x3 + S2 = 6
x1 - 4x’ 2 + 3x3 – S3 = 8
x1 no restringida, x’ 2 ≥ 0, x3 ≥ 0, S1≥0,S2≥0, S3≥0
x1= x’ 1 - x’’ 1
Maximizar Z = 2x’ 1 – 2x’’ 1 - 3x’ 2 + x3
Sujeto a: x’ 1 – x’’ 1 – x’ 2 + x3 = 10
2x’ 1 – 2x’’ 1 + 3x’ 2 - 2x3 – S1 = 5
7x’ 1 – 7x’’ 1 + 4x’ 2 + 5x3 + S2 = 6
x’ 1 – x’’ 1 - 4x’ 2 + 3x3 – S3 = 8
x’ 1≥ 0, x’’ 1 ≥ 0, x’ 2 ≥ 0, x3 ≥ 0, S1≥0, S2≥0,S3≥0
Forma Estándar donde:
S1 y S3 Variables de Exceso
S2 Variable de Holgura
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 6/19
Juan José Bravo B., M.Sc.
Soluciones Básicas EJEMPLO: Minimizar Z = -3x1 - 5x2
Sujeto a: x1 ≤ 4
2x2 ≤ 12
3x1 + 2x2 ≤ 18
x1 , x2 ≥ 0
Minimizar Z = -3x1 - 5x2
Sujeto a: x1 + S1 = 4
2x2 + S2 = 12
3x1 + 2x2 + S3 = 18
x1 , x2 , S1, S2, S3 ≥ 0
Forma
Estándar
El Método Simplex observa elconjunto de ecuaciones resultantesen la forma estándar, y dado quehayan “m” ecuaciones y ” n” incognitas (en este caso m = 3 y n= 5) le corresponde hacer (n-m)variables iguales a “cero” parapoder tener solucionesconsistentes. Las soluciones que
logra de esta manera se llamanSoluciones Básicas.
x1 x2 s1 s2 s3
0 0 4 12 18
0 6 4 0 6
0 9 4 -9 0
4 6 0 0 -6
2 6 2 0 0
4 3 0 6 0
6 0 -2 12 0
4 0 0 12 6
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 7/19
Juan José Bravo B., M.Sc.
Soluciones Básicas Factibles (SBF)
x1 x2 s1 s2 s3
P1 0 0 4 12 18 Fact
P2 0 6 4 0 6 Fact
P3 0 9 4 -9 0 NO
P4 4 6 0 0 -6 NO
P5 2 6 2 0 0 Fact
P6 4 3 0 6 0 Fact
P7 6 0 -2 12 0 NO
P8 4 0 0 12 6 Fact
Los puntos resaltados con verde representanSoluciones Básicas Factibles ya que cumplen contodas las restricciones. Los demás puntos violanrestricciones de no-negatividad. El MétodoSimplex únicamente considera para su análisis las
SBF.
Las SBF son los vérticesde la Región Factible ypor tanto allí estará el óptimo.
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 8/19
Juan José Bravo B., M.Sc.
P1
P5P2
P6
P8
Búsqueda Geométrica del Optimo
Punto
Factibles
Puntos
Adyacentes
Valor Z en
el Punto
Valor Z en los Adyacentes
P1 P2 y P8 Z = 0 P2 (Z = -30) y P8 (Z = -12)
P2 P1 y P5 Z = -30 P1 (Z = 0) y P5 (Z = -36)
P5 P2 y P6 Z = -36 P2 (Z = -30) y P6 (Z = -27)
P6 P5 y P8 Z = - 27 P5 (Z = -36) y P8 (Z = -12)
P8 P1 y P6 Z = -12 P1 (Z = 0) y P6 (Z = -27)
El Método Simplex inicia explorando uno de los puntos, usualmente el origen(en este caso P1), y saltará a un punto adyacente sólo si éste salto mejora elvalor de Z.
Si estando en un punto se determina que ninguno de los adyacentes a él mejorael valor de Z, entonces se ha encontrado el óptimo.
En este caso el óptimo es el punto P5 , y se encuentra en 3 iteraciones (P1
P2 P5).
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 9/19
Juan José Bravo B., M.Sc.
Simplex Tabular Minimizar Z = -3x1 - 5x2
Sujeto a: x1 + S1 = 42x2 + S2 = 12
3x1 + 2x2 + S3 = 18
x1 , x2 , S1, S2, S3 ≥ 0
Tabla 1
El Método Simplex inicia en el punto P1,
que corresponde a la Tabla 1.
x1 x2 s1 s2 s3
P1 0 0 4 12 18
Variables
Básicas
Coeficientes en la
Función Objetivo
(Cj)
x1 x2 S1 S2 S3 Solución
(R.H.S.)
S1 0 1 0 1 0 0 4
S2 0 0 2 0 1 0 12
S3 0 3 2 0 0 1 18
Zj - Cj 3 5 0 0 0 0
VariablesNo Básicas VariablesBásicas
Coeficientes delas restricciones Valor Objetivo
/1
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 10/19
Juan José Bravo B., M.Sc.
Simplex Tabular /2
Ya obtenida la Tabla 1, el Método
Simplex se pregunta: ¿La Tabla1 es óptima? (es decir, ¿elpunto P1 es óptimo?).
Para ello observamos el
renglón (Zj – Cj), que dasólo informacion de las Variables No Basicas
Para Minimización• Si un valor del renglón (Zj – Cj) es positivo,indica que al darle valores a la variable no basicarespectiva, mejora la funcion objetivo.
• Si un valor del renglón (Zj – Cj) es negativo,
indica que al darle valores a la variable no basicarespectiva empeora la funcion objetivo.
•Si un valor del renglón (Zj – Cj) es cero, indicaque al darle valores a la variable no basicarespectiva, no hay cambio en la funcion objetivo.
Si todos los valores delrenglón (Zj – Cj) ≤ 0 entonces la Tabla esóptima
Debe ingresar a lasolución la Variable NoBasica que tenga elmayor valor positivo enel renglón (Zj – Cj)
ó
Criterio de Parada
Criterio de Entrada
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 11/19
Juan José Bravo B., M.Sc.
Tabla 1
VariablesBásicas
Coeficientes en laFunción Objetivo
(Cj)
x1 x2 S1 S2 S3 Solución(R.H.S.)
RazónMínima
(θ)
S1 0 1 0 1 0 0 4 -
S2 0 0 2 0 1 0 12 12/2 = 6
S3 0 3 2 0 0 1 18 18/2 = 9Zj - Cj 3 5 0 0 0 0
Simplex Tabular /3
Para darle valores a lavariable X2 (es decir,
volver básica a X2), debesalir de la solución actualuna de las variablesbásicas (es decir, una deellas deberá volverse nobasica ó “cero”).
Para saber cualvariable básica
actual sale, elCriterio de Salida es con base en laRazón Mínima(θ)
Columna entrante
Se calcula dividiendo elelemento de la columna
R.H.S con el elementode la columna entrante,siempre que elelemento de esta últimacolumna sea positivo.
sale S2
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 12/19
Juan José Bravo B., M.Sc.
Tabla 1Variables
Básicas
Coeficientes en la
Función Objetivo (Cj)
x1 x2 S1 S2 S3 Solución
(R.H.S.)
S1 0 1 0 1 0 0 4S2 0 0 2 0 1 0 12
S3 0 3 2 0 0 1 18
Zj - Cj 3 5 0 0 0 0
Simplex Tabular /4
Tabla 2
VariablesBásicas
Coeficientes en laFunción Objetivo (Cj)
x1 X2 S1 S2 S3 Solución(R.H.S.)
S1 0 1 0 1 0 0 4
x2 -5 0 1 0 1/2 0 6
S3 0 3 0 0 -1 1 6
Zj - Cj 3 0 0 -5/2 0 -30
000053
1810023
1201020
400101
000053
1810023
602/1010
400101
3002/5003
611003
602/1010
400101
r2 / 2 r4 -5r2
r3 -2r2
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 13/19
Juan José Bravo B., M.Sc.
Simplex Tabular /5Tabla 2Variables
Básicas
Coeficientes en la
Función Objetivo (Cj)
x1 X2 S1 S2 S3 Solución
(R.H.S.)Razón
θ
S1 0 1 0 1 0 0 4 4/1 =4
x2 -5 0 1 0 1/2 0 6 -
S3 0 3 0 0 -1 1 6 6/3 =2
Zj - Cj 3 0 0 -5/2 0 -30
Tabla 3Variables
Básicas
Coeficientes en la
Función Objetivo (Cj)
x1 X2 S1 S2 S3 Solución
(R.H.S.)
S1 0 0 0 1 1/3 -1/3 2
x2 -5 0 1 0 1/2 0 6
x1 -3 1 0 0 -1/3 1-3 2
Zj - Cj 0 0 0 -3/2 -1 -36
x1 x2 s1 s2 s3
P2 0 6 4 0 6 Fact
x1 x2 s1 s2 s3
P5 2 6 2 0 0 Fact
TablaOPTIMA
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 14/19
Juan José Bravo B., M.Sc.
El Simplex y las Variables Artificiales Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 34x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
Minimizar Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 3
4x1 + 3x2 – S2 = 6
x1 + 2x2 + S3 = 4
x1 , x2,S2, S3 ≥ 0
Estandarizacion
Tradicional
Como n=4 y m=3, el Simplexhace n-m variables “cero” (eneste caso una) para crear unsistema de ecuaciones
consistente que arroje unaSolucion Inicial Inmediata yFactible .
¿Puede Lograrlo con esteejemplo?
En general, las restricciones de “= “ yde “≥” generan problemas al Simplex almomento de construir la tabla inicialque arranca el procedimiento. Encambio cuando las restricciones son de “≤” no existen estos inconvenientes y
el metodo puede iniciar sin problemascon las variables de holgura.
El Simplex soluciona estos
inconvenientes de arranque creando Variables Artificiales.
/1
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 15/19
Juan José Bravo B., M.Sc.
El Simplex y las Variables Artificiales /2
Min Z = 4x1 + x2
Sujeto a: 3x1 + x2 = 34x1 + 3x2 ≥ 6
x1 + 2x2 ≤ 4
x1 , x2 ≥ 0
Min Z = 4x1 + x2
Sujeto a:3x1 + x2 = 3
4x1 + 3x2 – S2 = 6
x1 + 2x2 + S3 = 4
x1 , x2,S2, S3 ≥ 0
Min Z = 4x1 + x2 + MR 1+ MR 2
Sujeto a:3x1 + x2 + R 1 = 3
4x1 + 3x2 – S2 + R 2 = 6
x1 + 2x2 + S3 = 4
x1 , x2, S2, S3, R1, R2 ≥ 0
Aquí n = 6 y m = 3,siendo (n-m) = 3. Es decir,al hacer 3 variables iguales
a “cero” sale una SolucionInicial InmediataFactible. [Puede observarque estas 3 variables nobásicas iniciales deben serx1, x2, s2].
La Tabla Simplex Inicial se construye teniendoen cuenta que en el renglón (Zj – Cj) lasvariables básicas tienen necesariamente valoresde “cero”.
Tenga en cuenta que en la Tabla 1:
- Variables No Básicas: x1, x2, s2
- Variables Básicas: R 1, R 2, S3
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 16/19
Juan José Bravo B., M.Sc.
Min Z = 4x1 + x2 + MR 1+ MR 2
Sujeto a:3x1 + x2 + R 1 = 3
4x1 + 3x2 – S2 + R 2 = 6
x1 + 2x2 + S3 = 4
x1 , x2, S2, S3, R1, R2 ≥ 0
De la primera y segunda restricción:
R1 = 3 - 3x1 - x2
R2 = 6 - 4x1 - 3x2 + S2
Transformación necesaria en la FunciónObjetivo:
Min Z = 4x1 + x2 + M(3 - 3x1
- x2
) +M(6 - 4x1 - 3x2 + S2)
Min Z = (4 - 7M) x1 - (4M - 1)x2 + MS2 + 9M
Tabla 1Variables
Básicas
Coeficientes en la
Función Objetivo(Cj)
x1 x2 S2 S3 R1 R2 Solución
(R.H.S.)
R1 0 3 1 0 0 1 0 3
R2 0 4 3 -1 0 0 1 6
S3 0 1 2 0 1 0 0 4
Zj - Cj - (4-7M) (4M -1) -M 0 0 0 9M
El Simplex y las Variables Artificiales /3
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 17/19
Juan José Bravo B., M.Sc.
Tabla 1Variables
Básicas
Coeficientes en la
Función Objetivo(Cj)
x1 x2 S2 S3 R1 R2 Solución
(R.H.S.)
R1 0 3 1 0 0 1 0 3
R2 0 4 3 -1 0 0 1 6
S3 0 1 2 0 1 0 0 4
Zj - Cj - (4-7M) (4M -1) -M 0 0 0 9M
El Simplex y las Variables Artificiales /4
Tabla 4Variables
Básicas
Coeficientes en la
Función Objetivo
(Cj)
X1 x2 S2 S3 R1 R2 Solución
(R.H.S.)
X1 4 1 0 0 -1/5 2/5 0 2/5X2 1 0 1 0 3/5 -1/5 0 9/5
S2 0 0 0 1 1 1 -1 1
Zj - Cj 0 0 0 -1/5 7/5-M -M 17/5
Tabla OPTIMA
NOTA: Las variables artificiales siempre deben ser al final No Básicas, o tener valor de
“cero”, ya que solo fueron creadas para arrancar el procedimiento.
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 18/19
Juan José Bravo B., M.Sc.
El Método Simplex _ CASOS ESPECIALES
Problema demúltiples soluciones
Maximice Z = (5/2)X1 + X2 Sujeto a: 3X1 + 5X2 ≤ 15
5X1 + 2X2 ≤ 10Xj > 0 ; j = 1, 2
Tabla Final OPTIMAVariables
Básicas
Coeficientes en la
Función Objetivo (Cj)
x1 X2 S1 S2 Solución
(R.H.S.)
S1 0 0 3.8 1 -0.6 9
X1 5/2 1 0.4 0 0.2 2
Zj - Cj 0 0 0 0.5 5
Entonces aquí la variable que entra es la que variable no-básica que tenga el valor(Zj - Cj) más negativo. Observe la variable No Básica x2 con un valor de “0”. Siesta variable entra, la funcion objetivo permanece inmodificable.
Observe que una TablaOptima de MAXIMIZACION
tiene todos los valores delrenglón (Zj – Cj) ≥ 0. Esdecir, el criterio funciona a lainversa de la Minimizacion.
Puede encontrarse otra solucióncon el mismo valor de Z! Múltiples Soluciones
7/16/2019 2. Metodo Simplex
http://slidepdf.com/reader/full/2-metodo-simplex-563385709e46f 19/19
Juan José Bravo B., M.Sc.
Problema de solución infinita (ó No Acotada)Minimice Z = - X1 + X2
Sujeto a: - X1 + X2 ≤ 0
- 0,5X1 + X2 ≤ 1Xj > 0 ; j = 1, 2
Problema sin soluciónCuando en la Tabla Final existe como solución una Variable Artificial convalor mayor que cero.
Tabla InicialVariables
Básicas
Coeficientes en la
Función Objetivo (Cj)
x1 X2 S1 S2 Solución
(R.H.S.)
S1 0 -1 1 1 0 0
S2 5/2 -0.5 1 0 1 1
Zj - Cj 1 -1 0 0 0
Entra x1 pero: ¿Cuálvariable sale?