M todo SIMPLEX ltimo
Páginas: 5 (1057 palabras)
Publicado: 9 de mayo de 2015
METODOS DE LA PROGRAMACION LINEAL
1
1.3 EL MÉTODO SIMPLEX
GEORGE DANTSIG- 1947
Este método llega a la solución optima por medio de iteraciones
(pasos sucesivos). Y utiliza los conceptos básicos del algebra
matricial. Este algoritmo pasa de una solución básica factible a
otro mejorando siempre la solución previa hasta llegar a la
optima.
2
Un algoritmo.- Es un conjunto de
reglas o unprocedimiento sistemático
para obtener la solución a un problema.
3
Max z = 3X1 + 4X2
Sujeto a :
2.5X1 + X2 ≤ 20
3X1 + 3X2 ≤ 30
X1 + 2X2 ≤ 16
X1 , X2 ≥ 0
4
1.- LA TABLA SIMPLEX INICIAL
1.1 Se convierten las desigualdades en ecuaciones
(holgura y excedentes)
1.2 Se expresan las ecuaciones de restricciones en
forma matricial
1.3 Se prepara una tabla simplex inicial compuesta por:
-La matriz decoeficientes de las ecuaciones
-El vector columna de constantes
-Una fila de indicadores que son las negativas de los
coeficientes de la función objetivo
5
La primera solución básica factible se puede
leer de la tabla simplex inicial al hacer x1=0 y
x2=0, s1=36, s2=40, s3=28 la función objetivo
tiene un valor de cero.
6
2.- EL ELEMENTO PIVOTE Y CAMBIO DE BASE
Para incrementar el valor de lafunción objetivo se examina una nueva
solución básica. Para hacer esto se debe introducir una nueva variable a la
base y se tiene que excluir una de las variables que se encontraba en la
base. A este proceso se llama CÁMBIO DE BASE
El indicador negativo con el valor absoluto mayor determina la variable
para entrar a la base entonces X1 se incluye en la base y se convierte en la
columna pivote.
La variable que se debe eliminar se determina mediante la razón de
desplazamiento menor, dividiendo los elementos de la columna de
constantes por los de la columna del pivote: (S3).
7
3.- PIVOTEANDO
Pivoteando es el proceso de resolver las m ecuaciones en
función de las m variables que se encuentran en la base. El
pivoteado implica convertir a 1 el elemento pivote y todos los
demás elementosde la columna pivote a cero.
Para ello se realiza lo siguiente:
Multiplicar la fila pivote por la reciproca del elemento pivote
(1/6)
Después de reducir el elemento pivote a 1 se limpia la
columna pivote. En este caso se resta 5 veces la fila 1 de la fila 2,
2 veces la fila 1 de la fila 3 y se suma 5 veces la fila 1 a la fila 4.
Esto da la segunda tabla.
8
Max z = 3X1 + 4X2
Sujeto a :
2.5X1 +X2 ≤ 20
3X1 + 3X2 ≤ 30
X1 + 2X2 ≤ 16
X1 , X2 ≥ 0
9
LA TABLA SIMPLEX INICIAL
Se convierten las desigualdades en ecuaciones (holgura y excedentes)
Se expresan las ecuaciones de restricciones en forma matricial
Se prepara una tabla simplex inicial compuesta por:
-La matriz de coeficientes de las ecuaciones
-El vector columna de constantes
-Una fila de indicadores que son las negativas de loscoeficientes de la función
objetivo
10
EL ELEMENTO PIVOTE Y CAMBIO DE BASE
El indicador negativo con el valor absoluto mayor determina la variable
para entrar a la base entonces X2 se incluye en la base y se convierte en la
columna pivote.
La variable que se debe eliminar se determina mediante la razón de
desplazamiento menor, dividiendo los elementos de la columna de
constantes por los dela columna del pivote: (S3).
11
PIVOTEANDO
El pivoteado implica convertir a 1 el elemento pivote y todos los demás
elementos de la columna pivote a cero.
Multiplicar la fila pivote por la reciproca del elemento pivote (1/2)
Después de reducir el elemento pivote a 1 se limpia la columna pivote. En
este caso se resta 1 veces la fila 3 de la fila 1, 3 veces la fila 3 de la fila 2 y se
suma 4veces la fila 3 a la fila 4
12
13
Optimización
La función objetivo se maximiza cuando no hay
indicadores negativos en la ultima fila. El
pivoteado continua puesto que -1 es el único
indicador negativo
14
15
Tabla final
X1
X2
S1
S2
S3
CONSTANTES
0
0
1
-4/3
3/2
4
1
0
0
2/3
-1
4
0
1
0
-1/3
0
6
0
0
0
2/3
1
36
16
Max z = 30X1 + 24X2+60x3
Sujeto a :
6X1+3X2+5x3 ≤...
1
1.3 EL MÉTODO SIMPLEX
GEORGE DANTSIG- 1947
Este método llega a la solución optima por medio de iteraciones
(pasos sucesivos). Y utiliza los conceptos básicos del algebra
matricial. Este algoritmo pasa de una solución básica factible a
otro mejorando siempre la solución previa hasta llegar a la
optima.
2
Un algoritmo.- Es un conjunto de
reglas o unprocedimiento sistemático
para obtener la solución a un problema.
3
Max z = 3X1 + 4X2
Sujeto a :
2.5X1 + X2 ≤ 20
3X1 + 3X2 ≤ 30
X1 + 2X2 ≤ 16
X1 , X2 ≥ 0
4
1.- LA TABLA SIMPLEX INICIAL
1.1 Se convierten las desigualdades en ecuaciones
(holgura y excedentes)
1.2 Se expresan las ecuaciones de restricciones en
forma matricial
1.3 Se prepara una tabla simplex inicial compuesta por:
-La matriz decoeficientes de las ecuaciones
-El vector columna de constantes
-Una fila de indicadores que son las negativas de los
coeficientes de la función objetivo
5
La primera solución básica factible se puede
leer de la tabla simplex inicial al hacer x1=0 y
x2=0, s1=36, s2=40, s3=28 la función objetivo
tiene un valor de cero.
6
2.- EL ELEMENTO PIVOTE Y CAMBIO DE BASE
Para incrementar el valor de lafunción objetivo se examina una nueva
solución básica. Para hacer esto se debe introducir una nueva variable a la
base y se tiene que excluir una de las variables que se encontraba en la
base. A este proceso se llama CÁMBIO DE BASE
El indicador negativo con el valor absoluto mayor determina la variable
para entrar a la base entonces X1 se incluye en la base y se convierte en la
columna pivote.
La variable que se debe eliminar se determina mediante la razón de
desplazamiento menor, dividiendo los elementos de la columna de
constantes por los de la columna del pivote: (S3).
7
3.- PIVOTEANDO
Pivoteando es el proceso de resolver las m ecuaciones en
función de las m variables que se encuentran en la base. El
pivoteado implica convertir a 1 el elemento pivote y todos los
demás elementosde la columna pivote a cero.
Para ello se realiza lo siguiente:
Multiplicar la fila pivote por la reciproca del elemento pivote
(1/6)
Después de reducir el elemento pivote a 1 se limpia la
columna pivote. En este caso se resta 5 veces la fila 1 de la fila 2,
2 veces la fila 1 de la fila 3 y se suma 5 veces la fila 1 a la fila 4.
Esto da la segunda tabla.
8
Max z = 3X1 + 4X2
Sujeto a :
2.5X1 +X2 ≤ 20
3X1 + 3X2 ≤ 30
X1 + 2X2 ≤ 16
X1 , X2 ≥ 0
9
LA TABLA SIMPLEX INICIAL
Se convierten las desigualdades en ecuaciones (holgura y excedentes)
Se expresan las ecuaciones de restricciones en forma matricial
Se prepara una tabla simplex inicial compuesta por:
-La matriz de coeficientes de las ecuaciones
-El vector columna de constantes
-Una fila de indicadores que son las negativas de loscoeficientes de la función
objetivo
10
EL ELEMENTO PIVOTE Y CAMBIO DE BASE
El indicador negativo con el valor absoluto mayor determina la variable
para entrar a la base entonces X2 se incluye en la base y se convierte en la
columna pivote.
La variable que se debe eliminar se determina mediante la razón de
desplazamiento menor, dividiendo los elementos de la columna de
constantes por los dela columna del pivote: (S3).
11
PIVOTEANDO
El pivoteado implica convertir a 1 el elemento pivote y todos los demás
elementos de la columna pivote a cero.
Multiplicar la fila pivote por la reciproca del elemento pivote (1/2)
Después de reducir el elemento pivote a 1 se limpia la columna pivote. En
este caso se resta 1 veces la fila 3 de la fila 1, 3 veces la fila 3 de la fila 2 y se
suma 4veces la fila 3 a la fila 4
12
13
Optimización
La función objetivo se maximiza cuando no hay
indicadores negativos en la ultima fila. El
pivoteado continua puesto que -1 es el único
indicador negativo
14
15
Tabla final
X1
X2
S1
S2
S3
CONSTANTES
0
0
1
-4/3
3/2
4
1
0
0
2/3
-1
4
0
1
0
-1/3
0
6
0
0
0
2/3
1
36
16
Max z = 30X1 + 24X2+60x3
Sujeto a :
6X1+3X2+5x3 ≤...
Leer documento completo
Regístrate para leer el documento completo.