INSTITUTO TECNOLÓGICO DE NUEVO LEÓN Práctica # 2

Programación Lineal Objetivo: Comprender y aplicar los métodos gráfico y simplex de programación lineal para la optimización de recursos. Introducción: La programación lineal, salió a la luz durante la segunda guerra mundial. La aplicación principal que se le dio fue la optimización de los recursos o pertrechos de los países aliados y el logro de conquistar más objetivos militares. Al terminar la 2ª Guerra Mundial, Estados Unidos de América, aplicó estos modelos en la industria de ese país, y el resultado que arrojó fueron; más ganancias para ese sector y una mejor utilización de la materia prima. Por esta situación, estos modelos se han estado aplicando a diferentes tipos de problemas en la búsqueda de soluciones mejores. Correlación con temas del programa: La programación lineal, ayuda a la búsqueda de mejores soluciones de los problemas. Esta unidad se relaciona con los temas posteriores, en la ayuda de encontrar soluciones óptimas, y modelos alternativos de solución. Material y equipo necesario: Una calculadora y libreta para resolver los problemas, y practicar la metodología vista, en caso de utilizar algún software, imprimir o enviar de forma electrónica el resultado. Metodología: Elaborar el modelo matemático mediante la metodología revisada y encontrar la solución por el método gráfico, para después encontrar la solución por el método simplex tabular. Sugerencias didácticas: Realizar investigación documental y realizar una presentación grupal de los elementos que componen un modelo de programación lineal y aplicar estos modelos para mezcla de productos. Analizar problemas planteados; así como la información e identificar el modelo a utilizar para la solución de problemas con base en la función objetivo y las ecuaciones de restrictivas. Plantear y resolver problemas de programación lineal en algún software de propósito general como Excel, Solver, Winqsb, Tora, o cualquier otro del mismo rubro para encontrar la solución del método gráfico y el algoritmo simplex. Aplicar método simplex en problemas de optimización de recursos. Interpretar los resultados obtenidos mediante el Análisis de Sensibilidad.

Manual de Prácticas de Investigación de Operaciones

Página 8

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN Reporte del alumno: Entregar los problemas solicitados por el docente para la calificación de la competencia. Bibliografía preliminar: NVESTIGACION DE OPERACIONES (HAMDY TAHA) INVESTIGACION DE OPERACIONES (W. L. WINSTON) INVESTIGACION DE OPERACIONES (HILLER) METODOS CUANTITATIVOS PARA LOS NEGOCIOS (SWEENEY) METODOS CUANTITATIVOS PARA LOS NEGOCIOS (RENDER) INVESTIGACION DEOPERACIONES (EPPEN) ENFOQUES CUANTITATIVOS EN LA ADMINISTRACION (LEVIN)

Manual de Prácticas de Investigación de Operaciones

Página 9

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN TEORIA: I.- Responda las siguientes preguntas con F falso o V verdadero 1. El método gráfico resuelve problemas de 2 variables. 2. Los elementos de un modelo de programación lineal son; función objetivo, ecuaciones restrictivas, variables de decisión y recursos. 3. Las variables de decisión representan los elementos desconocidos del problema. 4. Los métodos de solución de la programación lineal proporcionan una solución pseudo-óptima 5. La función objetivo representa el mejor valor alcanzado para el problema. 6. El método simplex trabaja como una aplicación del método de Gauss Jordán 7. Las variables de holgura representan Recursos Adicionales 8. El valor de la función objetivo en la solución óptima del simplex representa el mejor valor del problema 9. Las variables básicas iniciales son las que dan la solución óptima final del problema 10. El modelo de programación lineal original, no se puede modificar nunca.

F F

V V

F

V

F

V

F

V

F

V

F F

V V

F

V

F

V

PRACTICA II.- Elaborar un mapa conceptual sobre los temas que conforman la Programación Lineal.

PRACTICA. III.- Resolver los problemas según se pida en cada sección. Sección a) Elabore el modelo de programación lineal a cada problema dado a continuación. 1.- Una compañía manufacturera produce 3 arts. (1,2,3), la gerencia desea conocer la cantidad que deben producir de c/u de ellos para maximizar las utilidades. La información complementaria muestra en las siguientes tablas: MAQUINA

PRODUCTO 1

PRODUCTO 2 PRODUCTO 3 TIEMPO DISP.

FRESADORA

9

3

5

500(HRS.-SEM.)

TORNO

5

4

0

350

“

RECTIFICADORA

3

0

2

150

“

Manual de Prácticas de Investigación de Operaciones

Página 10

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN El depto. de ventas a pronosticado que la demanda de cada uno de los productos 1 y 2 excederán a las 50 unidades por semana y el producto 3 será de al menos 20 unidades por semana. Las utilidades respectivas serán de $50, $20 y $25. Formule el modelo de PL para encontrar las variables de decisión y maximizar las ganancias. 2.- La compañía. ANCE produce una línea de artículos de peltre para el hogar, la cual consta de 4 productos. El sistema de manufactura se divide en cinco etapas; cortado, troquelado, esmaltado, acabado y empacado. La información relevante se muestra en las siguientes tablas. DEPTO.

PROD.1

PROD.2

PROD.3

PROD.4

CAP (hrs)

CORTADO

25

6

20

10

400

TROQUELADO

13

8

20

10

380

ESMALTADO

17

9

33

8

490

ACABADO

20

4

-

8

450

EMPACADO

50

13

50

20

400

Información sobre el producto PRODUCTO

PRECIO VENTA ($)

DEMANDA MENSUAL (UNID) MINIMA MAXIMA

1

100

500

5,000

2

300

750

6,000

3

160

650

8,000

4

250

0

3,500

Adicionalmente se sabe que en el siguiente mes solo se dispondrá de 1,200 m2 de lámina que consumen los productos 1 y 2, y el producto 1 requiere de 0.50 m2 por unidad y el producto 2 requiere por unidad 0.80 m2. Formule el modelo de PL para maximizar las ganancias. 3.- Una compañía de pañales para bebe, tiene 3 plantas de producción las cuales pueden fabricar un producto en 3 tamaños diferentes; chico, mediano y grande, dando una ganancia de $ 300, $360 y $ 420 respectivamente. Cada planta (1, 2 y 3) tienen capacidad de producción y de mano de obra para elaborar 450, 900 y 750 unidades respectivamente, sin importar el tamaño o la combinación de tamaños de que se trate. Manual de Prácticas de Investigación de Operaciones

Página 11

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN La cantidad de espacio disponible en cada planta para almacenar material de proceso tiene una limitación, se cuenta solamente con 13,000, 12,000 y 5,000 pies cuadrados. Cada unidad que se produce requiere de 12 pies cuadrados para el tamaño chico, 15 para el mediano y 20 para el grande. Los pronósticos de mercado indican que si se dispone de los artículos se pueden vender 750, 1200 y 900 unidades de cada tamaño respectivamente. Será necesario ayudar al gerente de la compañía a implementar un programa de producción para obtener el máximo de utilidades. Formule el modelo de PL para maximizar las utilidades. 4- Una compañía productora de automóviles debe producir 1000 unidades del tipo familiar. La compañía tiene 4 fábricas a las que denomino f1a, f2b, f3c, y f4d. El sindicato de la rama automotriz exige que se produzcan por lo menos 400 unidades en la fábrica f3c. Se disponen de 3,300 horas de trabajo y 4,000 unidades de materia prima las cuales se distribuirán en las 4 plantas. Los costos en miles de dls. se distribuyen de la siguiente manera: $15 para la fábrica f1a, $10 para f2b, $9 para la f3c y $7 para f4d. Cada unidad del automóvil familiar requiere de 2 hrs de mano de obra en la planta f1a, 3 hrs de mano de obra en la planta f2b, 4 hrs en la planta f3c y 5 hrs. En la planta f4d de manera similar la distribución de la materia prima es de la siguiente manera; 3 unidades de materia prima en la planta f1a, 4 unidades en la planta f2b, 5 unidades en la planta f3c y 6 unidades en la planta f4d respectivamente. Formule el modelo de PL para encontrar los valores que minimicen los costos de producción. 5.- REEM produce una bebida sabor cítrico (ORANJ), la cual se obtiene de mezclar refresco y jugo de naranja. Cada onza de refresco de naranja contiene 5 onzas de azúcar y 1 mg. de vitamina C. Cada onza de jugo de naranja contiene 0.25 onzas de azúcar y 3 mg. de vitamina C. A REEM le cuesta $0.45 producir una onza de refresco de naranja y $0.65 una onza de jugo de naranja. El depto. de mercadotecnia ha decidido que cada botella de 10 onzas de “ORANJ” debe contener por lo menos 20mg. de vitamina C y a lo más 4 onzas de azúcar. Formular el modelo de PL para determinar cómo se puede satisfacer los requerimientos mínimos al menor costo. 6.- Un estudiante de preparatoria debe planear su gasto semanal para los almuerzos escolares, y procurar cumplir con los requisitos mínimos de alimentación recomendados, no menos de 1000 y no mas de 1200 calorías, no más de 450 carbohidratos, y a lo mas 800 kilo proteínas. Para esto en la siguiente tabla se presentan los alimentos que puede consumir, los costos así como también el contenido calórico de cada uno de ellos. Ayude a este joven a planear Manual de Prácticas de Investigación de Operaciones

Página 12

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN el desayuno con el menor costo posible. Formular el modelo de PL para minimizar el gasto. TABLA DE ALIMENTOS SUGERIDOS Y COSTO DE CADA UNO DE ELLOS ALIMENTO

HAMBURGUESA

CALORIAS CARBOHIDRATOS KILO PROTEINAS COSTO

300 250 600 $30

PAN DULCE 100 250 350 $10

LECHE 10 90 30 $5

FRUTAS Y YOGURT 100 110 60 $12

Sección b) Encuentre la solución gráfica a cada problema, marcando la solución óptima, el área factible de solución y el valor de las variables de decisión. 1.- MIN. C = 2 X 1 + 3 X 2 Sujeto a: ½X1 + ¼ X2 4 X1 + 3X2 20 X1 + X 2 = 10

2.- MAX Z = 2 X 1 + X 2 sujeta a : X1 + X2 5 X1 - 2X2 4 X1 ,X2

X1 , X2 0 3.-MIN C = 200 X 1 + 500 X 2 sujeta a

0.2 X 1 0.3 X 1 0.5 X 1

0.4 X 2 + 0.3 X 2 + 0.2 X 2 + 0.1 X 2

5,000 10,000 12,000 7,000

4.-MAX G = 20X1 + 15X2 suejto a: X1 100 X2 100 5 X1 + 35 X2 6000 20 X1 + 15 X2 2000 X1 ,X2

X1 , X2 0 5.-MAX G = 2 X 1 + 5 X 2 sujeta a: X1+ X2 15 2X1 - X2 10 X1 - 3X2 9

0

6.-MIN Z = 2X1 + 3 X2 sujeto a: 2X 1 + X 2 4 X1 - X2 -1 X1 ,X2

X1 ,X2

0

0

0

Manual de Prácticas de Investigación de Operaciones

Página 13

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN Sección c) Resuelva los siguientes problemas por el método simplex, encontrando el valor de la función objetivo, el valor de las variables de decisión y el valor de las variables de holgura. 1.- MAX U = 5 X 1 + X 2 + 3 X 3 sujeta a:

2.- MAX G = 2 X 1 + X 2 + 5 X 3 sujeta a:

2 X1 - X 2 + 3 X 3 X1 + X 2 + 4 X 3

X1 + 2 X 2 2 X1 + 2 X 2 + 2 X 3

4 4

8 10

X1 ,X2,X3 0 3.- MAX A = 6X 1 + 2X 2 + 8 X 3 sujeta a:

X1 ,X2,X3 0 4.- MAX Z = 5 X 1 + X 2 + 3 X 3 + X4 sujeta a:

2X1 + 4X3 4X1 + 4X 2 + X 3

X1 - X 2 + X 3 - X4 X1 + 2X 2 + X 3 +2X4 X1 + X 2 + X 3 + X4

X1 ,X2,X3

14 40

0 X 1, X 2 , X 3, X4

5.- MIN C = 3 X 1 + 2X2 + 4X3 Sujeto a 2 X 1 + X2 + 3X3 = 60 3X 1 + 3X2 + 5X3 120

0

6.-MIN. P = X 1 + X 2 + X 3 + X 4 sujeta a: X 1 - X 2 + X 3 - X 4 = 20 2 X 1 - 2 X 2 - X 3 + X 4 = 10 X1 ,X2,X3,X4

X1 ,X2,X3

18 24 20

0

0

Manual de Prácticas de Investigación de Operaciones

Página 14

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN EJERCICIO RESUELTO MODELACON DE PROGRAMACION LINEAL. El Sr. López es gerente de una empresa que produce para vender 2 artículos para la limpieza domestica. Dichos productos utilizan 2 tipos de materias primas, y 2 procesos para su manufactura. Los productos tienen un precio de venta de $10 para el limpiador de pisos, y $8 para las toallitas limpiadoras. En la tabla siguiente se dan los datos de utilización de la materia prima y el tiempo que se requiere en cada proceso de dichos artículos. a) Formule el modelo de programación lineal que maximice las ganancias, b) Resolver por el método gráfico y c) Resolver el problema por el método simplex. TABLA COMPLEMENTARIA DE INFORMACIÓN ARTÍCULO Limpiador de pisos Toallitas DISPONIBILIDAD

MATERIA PRIMA 1 4

MATERIA PRIMA 2 6

PROCESO 1

PROCESO 2

2

2

2 12

1 10

1 8

2 8

ELABORAR EL MODELO Identificar las incógnitas o variables de decisión. Están asociadas a las unidades monetarias del problema sobre las cuales se maximizara o minimizara según el caso. X1 = Cantidad a producir del limpiador de pisos X2 = Cantidad a producir de las toallitas limpiadoras Después se deberán distribuir los recursos conforme la información y necesidades del problema. a) MODELO MAX GANANCIAS = 10X1 + 8X2 Sujeto a: 4X1 + 2X2 ≤ 12 6X1 + 1X2 ≤ 10 2X1 + 1X2 ≤ 8 Manual de Prácticas de Investigación de Operaciones

Página 15

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN 2X1 + 2X2 ≤ 8

X1, X2 ≥ 0 (Condición de no negatividad) b) MÉTODO GRÁFICO Este método requiere de un eje coordenado XY, donde se dibujarán las rectas que representan a cada una de las ecuaciones del problema. Eje Y

4X1 + 2X2 ≤ 12

De cada una de las rectas buscar el área de solución.

6X1 + 1X2 ≤ 10 2X1 + 1X2 ≤ 8 2X1 + 2X2 ≤ 8

Eje x

El AFS es la intersección de TODAS las áreas del problema. Y es allí donde encontraremos la solución.

PUNTO ÓPTIMO (PO)

AREA DE (AFS)

Y lo más fácil es buscar si las coordenadas del (0,0) satisfacen la desigualdad. Con esto al sustituir en la ecuación, si satisface la desigualdad, el área de la ecuación es hacia el “0”. En caso de no satisfacer la ecuación es en contra del “0” (hacia la derecha de la gráfica)

FACTIBLE SOLUCIÓN

Manual de Prácticas de Investigación de Operaciones

El PO es el punto donde encontraremos la solución para todas las ecuaciones, incluyendo el valor máximo de la función objetivo.

Página 16

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN Valores: PO (1.33, 2.66) FUNCION OBJETIVO = 10X1 + 8X2 = 10(1.33) + 8(2.66)= 13.3 + 20.62 = 33.96

c) MÉTODO SIMPLEX Este método utiliza el principio de GAUSS-JORDAN para resolución de ecuaciones lineales, las que se incluyen en una tabla y se da inicio a las operaciones de renglón para la solución del problema. TABLA INICIAL

1ª ITERACIÓN: Dividir cada elemento de los recursos entre los elementos respectivos de la columna señalada como variable de entrada Variable

de

Variable de salida

Renglón pivote Manual de Prácticas de Investigación de Operaciones

Página 17

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN

SEGUNDA ITERACIÓN: De los elementos de la función objetivo, seleccionar el más negativo, sin incluir el valor de los recursos. Variable

de

Variable de salida

Renglón pivote

TERCERA ITERACIÓN: Si en el renglón de la función objetivo, ya no existen elementos negativos, el problema ha terminado, y se deberá desglosar la solución óptima de la tabla.

Elementos de la FO Manual de Prácticas de Investigación de Operaciones

Página 18

INSTITUTO TECNOLÓGICO DE NUEVO LEÓN VARIABLES DEL PROBLEMA: VARIABLE F.O X1 X2 S1 S2 S3 S4

VALOR 31.6 1.2 2.8 1.6 0 2.8 0

**NOTA: CUALQUIER VARIABLE QUE NO ESTE DENTRO DE LA COLUMNA DE VARIABLES BASICAS, SU VALOR ES CERO (0)

Manual de Prácticas de Investigación de Operaciones

Página 19