• Author / Uploaded
• hanterox

• Categories
• Programación lineal
• Algoritmos
• Matemáticas
• Ciencia
• Es / Ciencias de la Computación

Citation preview

UNIVERSIDAD NACIONAL DE ANCASH “SANTIAGO ANTÚNEZ DE MAYOLO” FACULTAD DE CIENCIAS ECONÓMICAS, ADMINISTRATIVAS Y CONTABLES MÉTODOS CUANTITATIVOS PARA LA TOMA DE DECISIONES

GUÍA PARA PRÁCTICA

Lic. Adm. RICARDO TOLEDO QUIÑONES

HUARAZ – PERÚ - ABRIL - 2 003

Universidad Nacional “Santiago Antúnez de Mayolo” Facultad de Ciencias Económicas, Administrativas y Contables

PROGRAMACIÓN LINEAL 1.

CONCEPTO

Es una técnica matemática que permite asignar recursos limitados tales como dinero, personal, materiales, equipos, espacio, tiempo, etc. Un problema de Programación Lineal (PL), es un problema de optimización, para lo cual se efectúa lo siguiente: a) b) c)

Se trata de maximizar (ejemplo beneficios) o minimizar (ejemplo costos) una función lineal de variables de decisión. La función que se pretende maximizar o minimizar se llama función objetivo. Los valores de las variables de decisión tienen que satisfacer un conjunto de restricciones. Cada restricción tiene que ser una ecuación lineal (relacionada con el signo = ) o una desigualdad lineal (relacionada con el signo =). Hay una restricción de signo para cada variable. Para cualquier variable Xn la restricción de signo especifica que Xn tiene que ser no negativo Xn >= 0 o que Xn puede ser una variable sin restricción de signo. Para los casos a estudiar sólo se utilizará la restricción de no negatividad.

La programación lineal se ha usado para resolver problemas de optimización en industrias tan diversas como la banca, la educación la silvicultura, la agricultura, el petróleo el transporte, etc. En una Encuesta en los EE.UU., se estableció que el 85% de las Empresas utilizaron ésta técnica. Su uso para optimizar la mezcla de gasolinas en la Texaco, le significó un ahorro de más de 30 millones de dólares anuales, en el diseño de las rondas de los oficiales de policía de San Francisco se logró un ahorro de 11 millones de dólares anuales, el remplazo de equipo en Phillips Petroleum le significó un ahorro de 90 mil dólares anuales. 2.

METODOS DE RESOLUCION DE PROBLEMAS DE PROGRAMACION LINEAL

a)

Método gráfico.- Utilizado cuando el modelo sólo contiene dos variables de decisión. Algoritmo Simplex.- Utilizado cuando el problema tiene muchas variables. El algoritmo de resolución fue desarrollado por George Dantzig en 1947. Algoritmo es un conjunto de procedimientos que, cuando se siguen en forma ordenada, proporcionan una solución óptima a un problema. Algoritmo Karmarkar.- Utilizado cuando el problema tiene muchas variables. Ha sido desarrollado en los años 80 y paulatinamente está cobrando importancia. Si se desea comparar el Algoritmo Simplex y Algoritmo Karmarkar se ha demostrado que para problemas grandes, el método Karmarkar puede ser hasta 50 veces más rápido que el algoritmo simplex, su importancia radica en que actualmente los diseños de los problemas exigen un elevado número de variables, el Military Airlift Command ha utilizado el método de Karmarkar para determinar cuántas veces hay que volar diferentes rutas y con qué avión, el modelo tenía 150 000 variables y 12 000 restricciones y se resolvió en una hora con una computadora. Con una estructura similar, con 36 000 variables y 10 000

b)

c)

Elaboración: Ricardo Toledo Q.

Universidad Nacional “Santiago Antúnez de Mayolo” Facultad de Ciencias Económicas, Administrativas y Contables

d)

restricciones, se resolvió mediante el método simplex, en 4 horas con una computadora. Computadora.- Existen diversos programas de computadora como son el Lindo, LPT1, Tora, etc. En las hojas de Cálculo como el Qpro y el Excel se posee una alta eficacia para resolverlos.

3.

PLANTEAMIENTO DE PROBLEMAS

Para resolver un problema de PL el orden más conveniente para plantear el problema es seguir el orden siguiente: a)b)c)d)e)f)-

Sintetizar los datos del problema en un Cuadro. Definir verbalmente lo que se desea alcanzar. Definir las Variables (incógnitas). Definir la Función Objetivo (lo que se desea alcanzar, un MAX o un MIN). Plantear las Restricciones (limitaciones a los recursos). Integrar todo el planteamiento del problema.

El formato del Cuadro de síntesis del problema es generalmente: FILAS: ENTRADAS TALES COMO MATERIAS PRIMAS, PLANTAS DE FABRICACION, ETC Y UTILIDAD O COSTO. COLUMNAS: SALIDAS TALES COMO ARTICULO I, ARTICULO II, PRODUCTO A Y PRODUCTO B. En algunos casos se invierte, llegando a ser la filas las columnas y las columnas las filas, por una situación de comodidad de manejo de la información. ENTRADAS

SALIDAS PRODUCT. I PRODUCT.II

DISPONIBILID,

RECURSO I RECURSO II UTIL. O COSTO PROBLEMAS 1)

Un fabricante produce bicicletas y motonetas, las cuales deben procesarse a través de dos Centrales de producción mecánica. La Central 1 tiene un máximo de 120 horas disponibles, y la Central 2 tiene un máximo de 180 horas disponibles. La manufactura de una bicicleta requiere 6 horas en la Central 1 y 3 horas en la Central 2; la fabricación de una motoneta requiere 4 horas en la Central 1 y 10 horas en la Central 2. Si la utilidad por bicicleta en unidades monetarias es $ 45 (dólares por ejemplo), y por motoneta es de $ 55, determinar el número de bicicletas y de motonetas que se deberían fabricar para obtener la máxima utilidad. Respuesta: 10 Bicicletas y 15 Motonetas, con una Utilidad Máxima de $ 1 275.

2)

Suponiendo que se cuenta con dos alimentos: pan y queso; cada uno de

Elaboración: Ricardo Toledo Q.

Universidad Nacional “Santiago Antúnez de Mayolo” Facultad de Ciencias Económicas, Administrativas y Contables

ellos contiene calorías y proteínas en diversas proporciones. Un kilogramo de pan contiene 2 000 calorías y 50 gramos de proteínas, y un kilogramo de queso contiene 4 000 calorías y 200 gramos de proteínas. Suponiendo que una dieta normal requiere cuando menos 6 000 calorías y 200 gramos de proteínas diariamente. Por tanto, si el kilogramo de pan cuesta $ 6 y $ 21 el queso. ¿Qué cantidades de pan y queso se debe comprar para satisfacer los requisitos de la dieta normal, gastando la menor cantidad de dinero? Respuesta: 2 Kg de Pan y 1/2 Kg de Queso, con un gasto mínimo de $ 22,50 3)

Un fabricante de juguetes que está preparando un programa de producción para dos nuevos artículos A y B, requiere utilizar en su fabricación las Máquinas X, Y y un tiempo adicional para su acabado final. Cada Juguete A requiere 2 horas de uso de la Máquina X, 1 de Y y 1 para su acabado final. El juguete B requiere 1 hora de X, 1 de Y y 3 horas para su acabado. Las horas disponibles de los empleados, por semana son: máquina X, 70 horas; máquina Y, 40 horas y para el terminado 90 horas. Si las utilidades del juguete A son $ 4 y de B $ 6. ¿Cuántas unidades de cada uno deben fabricarse por semana con el objeto de maximizar las utilidades? ¿Cuál sería la utilidad máxima? Respuesta: Juguete A = 15 Unidades; Juguete B = 25 Unidades; (MAX) U = 210. 4)

Una compañía minera extrae dos tipos de minerales A y B de dos minas. La cantidad de mineral que se puede extraer por tonelada procesada de la mina I es 100 kilos de A y 200 de B; de la mina II 200 kilos de A y 50 de B. El costo por tonelada en la mina I es de $ 50 y en la II de $ 60. Si la compañía debe fabricar cuanto menos 3000 kilos de A y 2 500 de B. ¿Cuántas toneladas de cada mina se deben procesar para minimizar los costos? ¿Cuál es el costo mínimo?. Respuesta: Mina I : 10 Toneladas; Mina II: 10 Toneladas; (MIN) C = 1 100. 5)

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

ARTICULO

MADERA A

MESA SILLA ESCRITORIO LIBRERO

HORAS HOMBRE

B

5 1 9 12

2 3 4 1

3 2 5 10

DEMANDA ESTIMADA (*)

UTILIDAD POR UNIDAD ($) 12 5 15 10

(*) Información debe ser completada por Estudiante. Respuesta: Nº Mesas= 130; Nº Sillas= 130; Nº Escritorios = 30; Nº Libreros = 0; Máxima Utilidad = $ 2 660.

Elaboración: Ricardo Toledo Q.

Universidad Nacional “Santiago Antúnez de Mayolo” Facultad de Ciencias Económicas, Administrativas y Contables

PROBLEMAS PROPUESTOS 1)

El Cuadro siguiente muestra el número de libras de cada uno de los dos ingredientes en una unidad de cada uno de los dos compuestos químicos. a)- ¿Cuántas unidades X1 y X2 de los dos compuestos deberán producirse?. (ULLMANN: Pág. 69) b)- Que sucedería si se requiriera un tercer material C, cuya obtención está restringida por 6X1 + 5X2 ≤ 150.

INGREDIENTE 1 INGREDIENTE 2 UTILIDAD ($/POR UNIDAD) 2)

COMPUESTO 1 8 2

COMPUESTO 2 4 6

3

4

DISPONIBILIDAD 160 60

Un fabricante de camisas está tratando de decidir cuántas camisas debe producir durante el mes próximo. Pueden hacerse siete estilos. Los estilos varían en las horas de mano de obra que requieren, en la utilidad y en las ventas potenciales que el departamento de comercialización estima. Los datos se dan en seguida. ESTILO 1 2 3 4 5 6 7

HORAS HOMBRE 0,50 1,00 0,25 1,50 0,70 0,90 1,20

VENTAS MAXIMAS 3 000 1 000 5 000 2 000 1 500 1 500 1 600

UTILIDAD POR UNIDAD 1,00 2,00 1,00 1,50 1,10 1,20 1,20

Se dispone de un total de 7 500 horas de mano de obra, se solicita maximizar la utilidad total. RESPUESTA: Estilo 1 = 3 000, estilo 2 = 1 000, estilo 3 = 5 000, estilo 4 = 0, estilo 5 = 1 500, estilo 6 = 1 500 y estilo 7 = 1 125. Utilidad Máxima 14 875 UM. *******

Elaboración: Ricardo Toledo Q.