Metodo Simplex
Páginas: 9 (2195 palabras)
Publicado: 26 de febrero de 2013
El m´todo SIMPLEX e
Prof. Victor Bernal.
UNEXPO
M´todos de optimizaci´n e o
Prof. Victor Bernal. (UNEXPO)
El m´todo SIMPLEX e
UNEXPO 2012
1 / 16
Soluci´n por el m´todo Simplex o e
Planteamiento del problema
Una compa˜´ fabrica un producto qu´ nıa ımico mezclando dos sustancias S1 y S2 en proporci´n 5:2, por peso. Las sustancias son elaboradas por tres o proveedoresutilizando dos tipos de materia prima, MP1 y MP2, y un combustible C. Los datos de producci´n est´n en la tabla que se da a o a continuaci´n. o Determinar, planteando el problema como uno de programaci´n lineal y o resolvi´ndolo mediante el m´todo Simplex, el tiempo que debe operar cada e e proceso para maximizar la cantidad de mezcla producida por la compa˜´ nıa.
Prof. Victor Bernal. (UNEXPO)El m´todo SIMPLEX e
UNEXPO 2012
2 / 16
Soluci´n por el m´todo Simplex o e
Los datos del problema
Proceso 1 2 3 Disponible
Req/Tiempo MP1 MP2 C 9 5 50 6 8 75 4 11 100 200 400 1850
Prod./Tiempo S1 S2 9 6 7 10 10 6
Prof. Victor Bernal. (UNEXPO)
El m´todo SIMPLEX e
UNEXPO 2012
3 / 16
Soluci´n por el m´todo Simplex o e
Variables de decisi´n y formulaci´n delproblema o o
Las variables de decisi´n se definen como xj , las unidades de tiempo que opera o cada proceso. Se define z como la cantidad de mezcla obtenida. La formulaci´n o algebraica tiene dos tipos de restricciones, uno por la condici´n de proporci´n 5:2 o o en la mezcla y otro por los requerimientos de materia prima y combustible. El planteamiento, en forma algebraica, se puede expresar como, maxSujeto a: z− 9x1 + 7x2 + 10x3 ≤0 5 6x1 + 10x2 + 6x3 z− ≤0 2 9x1 + 6x2 + 4x3 ≤ 200 5x1 + 8x2 + 11x3 ≤ 400 50x1 + 75x2 + 100x3 ≤ 1850 xj ≥ 0, j = 1, 2, 3
Prof. Victor Bernal. (UNEXPO) El m´todo SIMPLEX e UNEXPO 2012 4 / 16
z
Soluci´n por el m´todo Simplex o e
Conversi´n a la forma est´ndar o a
Para convertir la formulaci´n a la forma est´ndar, inicialmente se o a introducen cincovariables de holgura, x4 , . . . , x8 , una por cada desigualdad. De esta manera el sistema se puede escribir como, max Sujeto a: 5z −9x1 −7x2 −10x3 +x4 2z −6x1 −10x2 −6x3 +x5 9x1 +6x2 +4x3 +x6 5x1 +8x2 +11x3 +x7 50x1 +75x2 +100x3 +x8 xj ≥ 0, j = 1, 2, 3
Prof. Victor Bernal. (UNEXPO) El m´todo SIMPLEX e UNEXPO 2012 5 / 16
z
= 0 = 0 = 200 = 400 = 1850
Soluci´n por el m´todo Simplex o eConversi´n a la forma est´ndar o a
La presencia de z en las restricciones se evita despejando en la primera igualdad 9x1 + 7x2 + 10x3 − x4 z= 5 y reemplazando en la segunda. 2 9x1 + 7x2 + 10x3 − x4 5 − 6x1 − 10x2 − 6x3 + x5 = 0
Aunque se puede multiplicar por 5 en ambos lados de la segunda ecuaci´n o los coeficientes de x1 , . . . , x4 se escriben como fracciones para que x5 quede con coeficiente 1 ysea una variable b´sica. El valor inicial de z es 0 a y se lee en la esquina inferior derecha de la tabla. El problema de maximizaci´n se convierte a uno de minimizaci´n o o multiplicando por − 1 los coeficientes de z.
Prof. Victor Bernal. (UNEXPO) El m´todo SIMPLEX e UNEXPO 2012 6 / 16
Soluci´n por el m´todo Simplex o e
El m´todo Simplex e
Eliminando z de las restricciones la tablainicial del m´todo Simplex es, e VB x1 x2 x3 x4 x5 x6 x7 x8 x5 −12/5 −36/5 −2 −2/5 1 0 0 0 x6 9 6 4 0 0 1 0 0 5 8 11 0 0 0 1 0 x7 x8 50 75 100 0 0 0 0 1 −z −9/5 −7/5 −2 1/5 0 0 0 0 z b 0 0 0 200 0 400 0 1850 1 0
para mayor facilidad se convierten las fracciones a decimales, la tabla inicial queda como,
Prof. Victor Bernal. (UNEXPO)
El m´todo SIMPLEX e
UNEXPO 2012
7 / 16
Soluci´npor el m´todo Simplex o e
El M´todo Simplex e
V B x1 x2 x3 x4 x5 x6 x7 x8 x5 −2.4 −7.2 −2 −0.4 1 0 0 0 9 6 4 0 0 1 0 0 x6 x7 5 8 11 0 0 0 1 0 x8 50 75 100 0 0 0 0 1 −z −1.8 −1.4 −2 0.2 0 0 0 0 z b 0 0 0 200 0 400 0 1850 1 0
A esta tabla se agrega una ultima columna para almacenar los cocientes ´ de los t´rminos independientes y los coeficientes positivos de la variable e que entra en la...
Prof. Victor Bernal.
UNEXPO
M´todos de optimizaci´n e o
Prof. Victor Bernal. (UNEXPO)
El m´todo SIMPLEX e
UNEXPO 2012
1 / 16
Soluci´n por el m´todo Simplex o e
Planteamiento del problema
Una compa˜´ fabrica un producto qu´ nıa ımico mezclando dos sustancias S1 y S2 en proporci´n 5:2, por peso. Las sustancias son elaboradas por tres o proveedoresutilizando dos tipos de materia prima, MP1 y MP2, y un combustible C. Los datos de producci´n est´n en la tabla que se da a o a continuaci´n. o Determinar, planteando el problema como uno de programaci´n lineal y o resolvi´ndolo mediante el m´todo Simplex, el tiempo que debe operar cada e e proceso para maximizar la cantidad de mezcla producida por la compa˜´ nıa.
Prof. Victor Bernal. (UNEXPO)El m´todo SIMPLEX e
UNEXPO 2012
2 / 16
Soluci´n por el m´todo Simplex o e
Los datos del problema
Proceso 1 2 3 Disponible
Req/Tiempo MP1 MP2 C 9 5 50 6 8 75 4 11 100 200 400 1850
Prod./Tiempo S1 S2 9 6 7 10 10 6
Prof. Victor Bernal. (UNEXPO)
El m´todo SIMPLEX e
UNEXPO 2012
3 / 16
Soluci´n por el m´todo Simplex o e
Variables de decisi´n y formulaci´n delproblema o o
Las variables de decisi´n se definen como xj , las unidades de tiempo que opera o cada proceso. Se define z como la cantidad de mezcla obtenida. La formulaci´n o algebraica tiene dos tipos de restricciones, uno por la condici´n de proporci´n 5:2 o o en la mezcla y otro por los requerimientos de materia prima y combustible. El planteamiento, en forma algebraica, se puede expresar como, maxSujeto a: z− 9x1 + 7x2 + 10x3 ≤0 5 6x1 + 10x2 + 6x3 z− ≤0 2 9x1 + 6x2 + 4x3 ≤ 200 5x1 + 8x2 + 11x3 ≤ 400 50x1 + 75x2 + 100x3 ≤ 1850 xj ≥ 0, j = 1, 2, 3
Prof. Victor Bernal. (UNEXPO) El m´todo SIMPLEX e UNEXPO 2012 4 / 16
z
Soluci´n por el m´todo Simplex o e
Conversi´n a la forma est´ndar o a
Para convertir la formulaci´n a la forma est´ndar, inicialmente se o a introducen cincovariables de holgura, x4 , . . . , x8 , una por cada desigualdad. De esta manera el sistema se puede escribir como, max Sujeto a: 5z −9x1 −7x2 −10x3 +x4 2z −6x1 −10x2 −6x3 +x5 9x1 +6x2 +4x3 +x6 5x1 +8x2 +11x3 +x7 50x1 +75x2 +100x3 +x8 xj ≥ 0, j = 1, 2, 3
Prof. Victor Bernal. (UNEXPO) El m´todo SIMPLEX e UNEXPO 2012 5 / 16
z
= 0 = 0 = 200 = 400 = 1850
Soluci´n por el m´todo Simplex o eConversi´n a la forma est´ndar o a
La presencia de z en las restricciones se evita despejando en la primera igualdad 9x1 + 7x2 + 10x3 − x4 z= 5 y reemplazando en la segunda. 2 9x1 + 7x2 + 10x3 − x4 5 − 6x1 − 10x2 − 6x3 + x5 = 0
Aunque se puede multiplicar por 5 en ambos lados de la segunda ecuaci´n o los coeficientes de x1 , . . . , x4 se escriben como fracciones para que x5 quede con coeficiente 1 ysea una variable b´sica. El valor inicial de z es 0 a y se lee en la esquina inferior derecha de la tabla. El problema de maximizaci´n se convierte a uno de minimizaci´n o o multiplicando por − 1 los coeficientes de z.
Prof. Victor Bernal. (UNEXPO) El m´todo SIMPLEX e UNEXPO 2012 6 / 16
Soluci´n por el m´todo Simplex o e
El m´todo Simplex e
Eliminando z de las restricciones la tablainicial del m´todo Simplex es, e VB x1 x2 x3 x4 x5 x6 x7 x8 x5 −12/5 −36/5 −2 −2/5 1 0 0 0 x6 9 6 4 0 0 1 0 0 5 8 11 0 0 0 1 0 x7 x8 50 75 100 0 0 0 0 1 −z −9/5 −7/5 −2 1/5 0 0 0 0 z b 0 0 0 200 0 400 0 1850 1 0
para mayor facilidad se convierten las fracciones a decimales, la tabla inicial queda como,
Prof. Victor Bernal. (UNEXPO)
El m´todo SIMPLEX e
UNEXPO 2012
7 / 16
Soluci´npor el m´todo Simplex o e
El M´todo Simplex e
V B x1 x2 x3 x4 x5 x6 x7 x8 x5 −2.4 −7.2 −2 −0.4 1 0 0 0 9 6 4 0 0 1 0 0 x6 x7 5 8 11 0 0 0 1 0 x8 50 75 100 0 0 0 0 1 −z −1.8 −1.4 −2 0.2 0 0 0 0 z b 0 0 0 200 0 400 0 1850 1 0
A esta tabla se agrega una ultima columna para almacenar los cocientes ´ de los t´rminos independientes y los coeficientes positivos de la variable e que entra en la...
Leer documento completo
Regístrate para leer el documento completo.