METODOS DE LA PROGRAMACION LINEAL*

GEORGE DANTSIG- 1947

Este mtodo llega a la solucin optima por medio de iteraciones (pasos sucesivos). Y utiliza los conceptos bsicos del algebra matricial. Este algoritmo pasa de una solucin bsica factible a otro mejorando siempre la solucin previa hasta llegar a la optima.

1.3 EL MTODO SIMPLEX*

*Un algoritmo.- Es un conjunto de reglas o un procedimiento sistemtico para obtener la solucin a un problema.

Max z = 3X1 + 4X2 Sujeto a : 2.5X1 + X2 20 3X1 + 3X2 30 X1 + 2X2 16 X1 , X2 0 *

1.- LA TABLA SIMPLEX INICIAL1.1 Se convierten las desigualdades en ecuaciones (holgura y excedentes)1.2 Se expresan las ecuaciones de restricciones en forma matricial1.3 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 los coeficientes de la funcin objetivo

*

La primera solucin bsica factible se puede leer de la tabla simplex inicial al hacer x1=0 y x2=0, s1=36, s2=40, s3=28 la funcin objetivo tiene un valor de cero.*

2.- EL ELEMENTO PIVOTE Y CAMBIO DE BASE

Para incrementar el valor de la funcin objetivo se examina una nueva solucin bsica. 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 CMBIO DE BASEEl 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 razn de desplazamiento menor, dividiendo los elementos de la columna de constantes por los de la columna del pivote: (S3).

*

3.- PIVOTEANDO

Pivoteando es el proceso de resolver las m ecuaciones en funcin de las m variables que se encuentran en la base. El pivoteado implica convertir a 1 el elemento pivote y todos los dems elementos de la columna pivote a cero.Para ello se realiza lo siguiente:Multiplicar la fila pivote por la reciproca del elemento pivote (1/6)Despus 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.

*

Max z = 3X1 + 4X2 Sujeto a : 2.5X1 + X2 20 3X1 + 3X2 30 X1 + 2X2 16 X1 , X2 0 *

LA TABLA SIMPLEX INICIALSe convierten las desigualdades en ecuaciones (holgura y excedentes)Se expresan las ecuaciones de restricciones en forma matricialSe 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 los coeficientes de la funcin objetivo

*

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 razn de desplazamiento menor, dividiendo los elementos de la columna de constantes por los de la columna del pivote: (S3).

*

PIVOTEANDO

El pivoteado implica convertir a 1 el elemento pivote y todos los dems elementos de la columna pivote a cero.Multiplicar la fila pivote por la reciproca del elemento pivote (1/2)Despus 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 4 veces la fila 3 a la fila 4

*

*

OptimizacinLa funcin objetivo se maximiza cuando no hay indicadores negativos en la ultima fila. El pivoteado continua puesto que -1 es el nico indicador negativo*

*

Tabla final*

X1X2S1S2S3CONSTANTES001-4/33/241002/3-14010-1/3060002/3136

Max z = 30X1 + 24X2+60x3 Sujeto a : 6X1+3X2+5x3 30 2X1+2X2+10X3 50 X1,X2,X3 0 *

Revisar la tarea del ejercicio 2*

VALOR MARGINAL O PRECIO SOMBRAEl valor del indicador bajo cada variable floja en la tabla final expresa el valor marginal o precio sombra del insumo asociado a al variable, o sea, hasta que punto cambiara la funcin objetivo debido a un incremento de una unidad el insumo.*

Tabla final*

X1X2S1S2S3CONSTANTES10-1/100501-1/43/100300-116001/22/5034

As en el ejemplo los beneficios aumentaran en unidad o 0.50 centavos para un cambio de una unidad en el valor constante de la restriccin 1. En 2/5 o 0.40 centavos para un incremento de una unidad en el valor constante de la restriccin 2 y en cero para un aumento de una unidad en el valor constante de a restriccin 3

*

VERIFICACIN.Z=5(5)+3(3)=34S.A6(5)+2(3)+0=365(5)+5(3)+0=402(5)+4(3)+6=28

*Z= (36)+2/5(40)+0(28)=34

TEORIA DE LA DUALIDAD

Cada problema de maximizacin(minimizacin) en la programacin lineal tiene un problema correspondiente de minimizacin(maximizacin). El problema original se denomina primario y el correspondiente el dual.*EL DUAL

Ejemplo 1*

Reglas de transformacin para obtener el dualSe invierte la direccin de la optimizacin.Los signos de desigualdad de las restricciones se invierten.Las filas de la matriz de coeficientes de las restricciones en el primario se transponen en columnas para la matriz de coeficientes del dual.El vector columna de constantes del primario se transponen a vector fila de coeficientes para la funcin objetivo del dualLas variables de decisin del primario (Xj) se reemplazan con variables de decisin del dual (Zi)*

Ejemplo 2*

*George Bernard Dantzig fue un profesor, fsico y matemtico estadounidense, reconocido por desarrollar el mtodo simplex y es considerado como el "padre de la programacin lineal".*******