Método Símplex

I

OBJETIVOS

Conocer los principales conceptos asociados al Método Símplex. Conocer y aplicar el Método Símplex para la solución de problemas de

maximización y minimización. Identificar los casos especiales mediante el método Simplex.

II

TEMAS A TRATAR

Conceptos generales. Método Símplex. Uso del LINDO, winQsb, PomQm y Excel.

III

MARCO TEORICO

MÉTODO SIMPLEXUsar la teoría aprendida en las clases teóricas. Hay que recordar que es un método que se basa en iteraciones. Debemos tener en cuenta los siguientes conceptos:

a) Variable de holguraEs la variable que representa el resto de un recurso que no ha sido utilizado, se le usa para que las restricciones de tipo se conviertan en igualdades (ecuaciones), el cual es uno de los requisitos para poder trabajar el Método Símplex.

b) Variable de superávitEs la variable que representa el exceso mínimo sobre el requerimiento mínimo de un recurso, se le usa para que las restricciones de tipo >= se conviertan en

Sesión

3

igualdades (ecuaciones), el cual es uno de los requisitos para poder trabajar el Método Símplex.

c) Reglas de estandarización

Reglas de aumentoTipo Variables

Restricción agregadas<= +Si Variable de holgura>= -Si +Ai Variable de exceso + Variable artificial = +Ai Variable artificial

Reglas de aumento en la F.O.Variable Función Objetivo

Agregada Max Min +Si 0Si 0Si -Si 0Si 0Si +Ai -MAi +MAi Donde M es un valor muy grande

d) Reglas de decisión para la columna y fila pivot

1ra Decisión (Columna Pivot) 2da Decisión (Fila Pivot)FO FO

Max Min Max MinEl valor Zj más

negativo (*) El valor Zj menos

negativo (**)El < +

(*): Elegir el valor Zj más negativo de las columnas correspondientes a las variables de decisión, de no haber ninguna, elegir la más negativa de las columnas correspondientes a las variables de holgura o exceso.(**): Elegir el valor Zj menos negativo de las columnas correspondientes a las variables de decisión, de no haber ninguna, elegir la menos negativa de las columnas correspondientes a las variables de holgura o exceso.

e) Reglas de decisión para ver si se llegó a la tabla final (Solución óptima).

FOMax Min

Todos los valores Zj>=0

Todos los valores Zj<=0

EJEMPLOTomando el problema de la Compañía que produce pinturas (Sesión 1), hallaremos su solución vía Método Símplex:Función objetivo: max Z = 5X1 + 4X2

Restricciones:6X1 + 4X2 24

X1 + 2X2 6X2 – X1 1

X2 2

Convertir las desigualdades en igualdades:

6X1 + 4X2 + S1 = 24X1 + 2X2 + S2 = 6– X1 + X2 + S3 = 1X2 + S4 = 2

La nueva función objetivo es:max Z = 5X1 + 4X2 + 0S1 + 0S2 + 0S3 + 0S4

Iteraciones:Tabla inicial: Se elige la columna pivote, la que tenga el valor más negativo en Z.

X1 X2 S1 S2 S3 S4 SoluciónS1 6 4 1 0 0 0 24S2 1 2 0 1 0 0 6S3 -1 1 0 0 1 0 1S4 0 1 0 0 0 1 2Z -5 -4 0 0 0 0 0

Luego se busca el pivote, con la siguiente relación:min [ 24/6, 6/1, 1/-1, 2/0 ] = 24/6

Nota: Solamente de deben considerar valores positivos y mayores a cero.

La variable que entra en la base (pasa a ser parte de la solución) es X1 y la que sale es S1

Modificar fila del pivote (convertir pivote en uno):

S1 6 4 1 0 0 0 24 6

S1 1 2/3 1/6 0 0 0 4

Pasar a cero toda la columna del pivote:

X1 X2 S1 S2 S3 S4 SoluciónX1 1 2/3 1/6 0 0 0 4 (5), (-1), (1)S2 0 4/3 -1/6 1 0 0 2S3 0 5/3 1/6 0 1 0 5S4 0 1 0 0 0 1 2Z 0 -2/3 5/6 0 0 0 20

La variable que entra en la base es X2 y la que sale es S2:min [ 6, 3/2, 3, 2 ] = 3/2

Modificar fila del pivote:

S2 0 4/3 -1/6 1 0 0 2 4/3

S2 0 1 -1/8 3/4 0 0 3/2

Pasar a cero toda la columna del pivote:

X1 X2 S1 S2 S3 S4 SoluciónX1 1 0 ¼ -1/2 0 0 3X2 0 1 -1/8 ¾ 0 0 3/2 (2/3), (-2/3), (-5/3), (-1)S3 0 0 3/8 -5/4 1 0 5/2S4 0 0 1/8 -3/4 0 1 ½Z 0 0 ¾ 1/2 0 0 21

Como ya no existen valores negativos en Z, entonces tenemos la solución final.Entonces tenemos la siguiente INFORMACIÓN PARA LA TOMA DE DECISIONES:

a) Valor de las variables de decisión:X1=3X2=3/2=1.5

b) Valor de la función objetivo:Z=21

c) Holguras o excedentes:S1=0S2=0S3=5/2=2.5S4=1/2=0.5

d) Costos reducidos de los coeficientes de la función objetivo: (estos valores se encuentran en la fila Z)De X1=0De X2=0

e) Precios Duales de los lados derechos: (estos valores se encuentran en la fila Z)De S1=3/4=0.75De S2=1/2=0.50De S3=0De S4=0

GRAFICAMENTE

Reporte del Software WINQSB:

Obtención de la Iteración Final mediante el Software WINQSB (utilizar la opción del menú Solve and Analyze/Solve and Display Steps):

En el reporte y en la Iteración final emitidos por el software WinQsb se observa toda la información para la toma de decisiones mostrada anteriormente.

IV

(La práctica tiene una duración de 02 horas) ACTIVIDADES

1.- Una empresa de producción de muebles dispone de dos diferentes tipos de madera; tiene 1500 pies tabla del tipo A y 1000 del tipo B, también dispone de 800 horas-hombre para efectuar el trabajo. La demanda semanal que ha estimado es la siguiente: cuando menos 40 mesas, 130 sillas, 30 escritorios y no más de 10 libreros. Las cantidades de madera Ay B, las horas-hombre que requiere la elaboración de cada unidad de artículo y las utilidades unitarias, están indicadas en el siguiente cuadro:

Madera Horas Demanda UtilidadesArtículo A B Hombre Estimada por unidadMesa 5 2 3 no menos de 40 $ 12Silla 1 3 2 no menos de 130 5Escritorio 9 4 5 no menos de 30 15Librero 12 1 10 no más de 10 10Disponibilidad semanal 1500 1000 800

MODELO MATEMÁTCIO:Variables:Xi: Número de unidades a producir semanalmente del artículo ii=1,2,3,4 (1: Mesas, 2: Sillas, 3: Escritorios, 4: Libreros)

Max 12x1+5x2+15x3+10x4St5x1+x2+9x3+12x4<=1500 Pies de Madera A2x1+3x2+4x3+x4<=1000 Pies de Madera B3x1+2x2+5x3+10x4<=800 horas hombreX1>=40 demanda mínima de mesasX2>=130 demanda mínima de sillasX3>=30 demanda mínima de escritoriosX4<=10 demanda máxima de librerosXi>=0

a) Resuelva el modelo matemático mediante el METODO SIMPLEX y muestre la primera y la última Iteración (Utilice el Excel).

b) Tomando la tabla de la iteración final, indique la siguiente información para la toma de decisiones:b.1 El valor de las variables de decisión (Cuánto producir semanalmente de cada artículo).b.2 El valor de la función objetivo (Utilidad semanal de la empresa).b.3 Las holguras o excedentes de los lados derechos.b.4 Los costos reducidos de los coeficientes de la función objetivo.b.5 Los Precios Duales de los lados derechos.

c) Utilizando el software WinQsb, resuelva el modelo matemático y compare la información de la salida del reporte con la obtenida en el punto b). Emita sus comentarios.

d) Utilizando el software PomQm, resuelva el modelo matemático y compare la información de los reportes con la obtenida en el punto b). Emita sus comentarios.

2. Dado el siguiente modelo matemático de programación lineal:

Minimizar: BAZ 85 Costo de la dieta en base a los alimentos A y B.

Sujeto a las restricciones de requerimientos mínimos de vitaminas.

40104 BA vitamina W 50510 BA vitamina X 4977 BA vitamina Y 0,0 BA

Utilizando el Excel, obtenga la Tabla Final mediante el MÉTODO SIMPLEX y resalte lo siguiente:a) El valor de las variables de decisión (Cuánto consumir de cada alimento).b) El Valor de la Función objetivo (Costo de la dieta).c) Los precios duales de los lados derechos.d) Los costos reducidos de los coeficientes de la función objetivo.e) El estado de los recursos (lados derechos).

3.- Dado los siguientes modelos matemáticos, aplique el METODO SIMPLEX y obtenga las TABLAS DE LA ITERACIÓN FINAL (Utilice el Excel). Emita sus comentarios.

4.- Un fabricante de gasolina para aviación vende dos clases de combustibles: A y B. El combustible A tiene 25% de gasolina de grado 1, 25% de gasolina de grado 2 y 50% de grado 3. El combustible B tiene 50% de gasolina de grado 2 y 50% de grado 3. Disponible para producción hay 500 gal./hr. De grado 1 y 200 gal./hr. de los grados 2 y 3. Los costos son de 30 ctvs. ($0.30) por galón de grado 1, $0.60 por galón de 2 y $0.50 por galón de grado 3. La clase A puede venderse a $0.75 por galón, mientras que la clase B alcanza $0.90/galón. ¿Qué cantidad debe producirse de cada combustible para maximizar la utilidad?. (Shamblin)