– Un problema de Programación Lineal se presenta en entornos económicos en el que hay que gestionar una serie de recursos para realizar una determinada actividad, utilizando para ello un criterio de tipo económico. (Gp:) 1. Definición – En un problema de Programación Lineal existen diferentes soluciones y un criterio para discriminar entre ellas con el objetivo de encontrar la mejor. A este proceso de búsqueda se le denomina Optimización. Optimizar significa poco más que mejorar; en el contexto científico la optimización es el proceso de tratar de encontrar la mejor solución posible para un determinado problema. Los problemas de Programación Lineal pueden considerarse o denominarse como problemas de optimización, si bien, esta denominación recoge un rango más amplio de problemas.
(Gp:) 1. Definición – De forma más precisa, estos problemas se trata de calcular el valor de unas variables que están sujetas a una serie de restricciones y para las que una determinada función objetivo alcanza su valor máximo o mínimo. – El criterio o función objetivo en un problema PL va referido a la minimización de los costes de la actividad, o a la maximización de beneficios. – Los problemas de Programación Lineal se expresan mediante un conjunto de relaciones matemáticas que se conoce como modelo. – El esfuerzo se centra tanto en la construcción del modelo como en la resolución del mismo.
Un problema de Programación Lineal está formado por tres componentes principales: Un conjunto de variables: Referidas a la actividad que se desarrolla en el sistema que se quiere optimizar. Notación: x1, x2, x3, …. Un conjunto de restricciones: Expresan la relación entre el consumo de recursos y las limitaciones de los mismos, así como toda clase de características que hay que imponer en el problema y que están asociadas a la actividad que se realiza en el sistema. Ejemplo: x1+ x2 ? 3 Una función objetivo: Criterio que se desea optimizar Ejemplo: Maximizar x1 + 3×2 (Gp:) 1. Definición
Los problemas de optimización dependen fundamentalmente para su resolución del tipo de variables que forman parte del mismo y del carácter lineal o no lineal de las restricciones. Problemas Lineales (Función Objetivo y Restricciones lineales) No Lineales (Función Objetivo y/o restricciones no lineales) Continuos (Vbles. continuas) Enteros (vbles. enteras) [Entera mixta (vbles. enteras y continuas)] PROGRAMACIÓN LINEAL [CONTINUA] PROGRAMACIÓN ENTERA (Gp:) 1. Definición
(Gp:) 1. Definición
(Gp:) 2. Un primer ejemplo Un fabricante de mantequilla desea optimizar la producción diaria de su factoría. Fabrica dos tipos de mantequilla (Estándar y Media Sal). Un Kilo de mantequilla Estándar proporciona un beneficio de 10 € y uno de MediaSal de 15 €. Para la producción de mantequillas se usan tres procesos, pasterización, centrifugado, y batido. La capacidad de pasterización es de 6horas/día, de centrifugado es de 3horas/día y de batido es de 3.5horas/día. Los tiempos(en minutos) de proceso por cada kilo de mantequilla se recogen en la siguiente tabla:
Identificación de componentes Variables asociadas a la actividad: Cantidad de mantequilla Estándar a producir por día: x1 Cantidad de mantequilla Media Sal a producir por día: x2 Objetivo: Maximizar el beneficio (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.1. Construcción del modelo Restricciones: – Limitación de las horas de pasterización – Limitación de las horas de centrifugado – Limitación de las horas de batido Recursos: – Tiempo de pasterización – Tiempo de centrifugado – Tiempo de batido
Semántica de la restricción: Consumo ? Capacidad 1 Kg Estándar consume 3 minutos de pasterización 2 Kg Estándar consumen 6 minutos(3?2) de pasterización ….. x1 Kgs Estándar consumen 3?x1minutos de pasterización Idéntico análisis para Kgs de Media Sal: 8?x2 Consumo Total = 3?x1 + 8?x2 minutos Capacidad = 6 horas = 360 minutos Restricción completa: 3?x1 + 8?x2 ? 360 (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.1. Construcción del modelo Restricciones: Expresión matemática – Limitación de las horas de pasterización (Gp:) Misma Unidad – Análisis equivalente para el resto de restricciones
Objetivo: Maximizar los beneficios: 1 Kg Estándar ? Beneficio = 10 2 Kg Estándar ? Beneficio = 10?2 = 20 …………. x1 Kg Estándar ? Beneficio = 10?x1 Idéntico análisis para Media Sal: 15?x2 Beneficio Total = 10 * x1 + 15 * x2 Función Objetivo: Expresión matemática (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.1. Construcción del modelo Expresión: Max 10?x1 + 15?x2
Modelo: x1 : Kilos de mantequilla Estándar x2 : Kilos de mantequilla Media Sal Función Objetivo: Rest. Recurso pasterización: Rest. Recurso centrifugado: Rest. Recurso batido: Signo de las variables: (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.1. Construcción del modelo Variables: ? Expresiones Lineales ? Variables continuas Modelo lineal Programación lineal continua
20 30 40 50 60 70 80 90 100 110 120 130 140 150 10 10 20 30 40 50 60 70 80 90 100 x1 x2 (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.2. La geometría del modelo Representación de una restricción: Es un semiespacio del espacio de ?2 El semiespacio se define por la recta que expresa la restricción con signo de igualdad SEMIESPACIO NO ADMISIBLE SEMIESPACIO ADMISIBLE
20 30 40 50 60 70 80 90 100 110 120 130 140 150 10 10 20 30 40 50 60 70 80 90 100 x1 x2 R2 R1 R3 Región de admisibilidad convexa (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.2. La geometría del modelo
(R1) (R3) 20 30 40 50 60 70 10 10 20 30 40 50 x1 x2 (R2) z=0 z=100 Dirección de máxima mejora (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.2. La geometría del modelo
20 30 40 50 60 70 10 10 20 30 40 50 x1 x2 Óptimo ? Punto interior (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.2. La geometría del modelo Siguiendo la dirección de máxima mejora desde cualquier punto interior podré ir a otro punto con mejor valor de la F.O. Por tanto, el Óptimo debe estar en la frontera de la región.
?: Ángulo agudo = Mejora ?: Ángulo obtuso = Empeoramiento Óptimo ? Vértice (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.2. La geometría del modelo Óptimo ? Punto interior de una arista*
Vértice óptimo (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.2. La geometría del modelo
(Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 50 (Gp:) 60 (Gp:) 70 (Gp:) 10 (Gp:) 10 (Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 50 (Gp:) x1 (Gp:) x2 Variables de holgura V1 V2 V3 V4 V5 (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo m = Número de restricciones n = Número de variables
Características generales de un vértice (Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 50 (Gp:) 60 (Gp:) 70 (Gp:) 10 (Gp:) 10 (Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 50 (Gp:) x1 (Gp:) x2 (Gp:) V1 (Gp:) V2 (Gp:) V3 (Gp:) V4 (Gp:) V5 (Gp:) x1?; x2=0 (Gp:) x2? x1=0 El número de variables (?0) es igual a m ? ? Vbles BÁSICAS El número de variables = 0 es igual a (n-m) ? ? Vbles NO BÁSICAS Se intercambian una a una desde un vértice a otro adyacente V1 (x1=0; x2=0; h1>0;h2>0;h3>0) V2 (x1=0; x2>0; h1=0;h2>0;h3>0) V3 (x1>0; x2>0; h1=0;h2>0;h3=0) V4 (x1>0; x2>0; h1>0;h2=0;h3=0) V5 (x1>0; x2=0; h1>0;h2=0;h3>0) (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo Variables: n=5 Restricciones: m=3
Vértice V1: x1=x2=0 (n-m) h1>0; h2>0;h3>0 (m) Restricciones: h1=360 h2=180 h3=210 (x1 x2 h1 h2 h3) (0 0 360 180 210) Valor de la F.O. en V1 = 0 + 0 = 0 Dos cuestiones: Cómo me desplazo hacia un vértice adyacente? Cómo averiguo si un vértice es el óptimo? Variables: n=5 Restricciones: m=3 (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo
Cómo me desplazo hacia un vértice adyacente? EJEMPLO: V1 ? V2 Me desplazo por la arista hasta topar con el siguiente vértice x2? hasta que alguna de las variables que son >0 en V1 se haga = 0 Durante el desplazamiento la otra variable que es = 0 en V1 permanece a 0 en toda la arista Paso 1. Calcular el vértice destino Paso 2. Preparar las restricciones para un desplazamiento posterior Paso 1: Calcular el vértice destino (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo
(x1 x2 h1 h2 h3) = (0 45 0 90 30) Vértice V2 Valor de la F.O. En V2 = 10×1 + 15×2 = = 0 + 675 = 675 (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo
Paso 2. Preparar las restricciones para un nuevo desplazamiento: Hay que realizar transformaciones lineales en las restricciones hasta conseguir la matriz identidad en las columnas de las variables básicas del vértice en el que me encuentro. Parto de las expresiones de las restricciones del vértice anterior V1 V1 ? V2 (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo
Para responder a esta pregunta tengo que expresar la F.O.en función de las variables que valen 0 en el vértice. Coste relativo = Índice que me indica si el incremento de esa variable produce mejora en la F.O. Si Índice > 0 ? Mejoro si me desplazo por esa arista Si Índice < 0 ? Empeoro x1? ?Mejoro con tasa 35/8 h1? ?Empeoro con tasa 15/8 Si en el vértice al que llego los índices de la expresión de la F.O. en ese vértice son todos negativos (en un problema de maximizar), dicho vértice es el óptimo del problema El vértice al que he llegado es óptimo? (Gp:) 2. Un primer ejemplo (Gp:) 2. Un primer ejemplo (Gp:) 2.3. El álgebra del modelo
(Gp:) 3. Ejercicios Para los sistemas productivos que aparecen a continuación: Obtenga el modelo matemático del problema Represente gráficamente las restricciones Identifique geométricamente el vértice óptimo Realice el recorrido algebraico por los vértices hasta alcanzar el vértice óptimo
(Gp:) 3. Ejercicios Un artesano alfarero desea optimizar la producción diaria de su taller de alfarería. Fabrica dos tipos de ánforas (Anforas1 y Anforas2). Para ello utiliza un proceso de producción simple. Emplea dos tipos de arcilla (arcilla A y arcilla B) que mezcla en las proporciones adecuadas, les da forma durante un cierto tiempo y las pone a secar en el horno que posee hasta el día siguiente. El alfarero vende posteriormente las ánforas1 a 100u.m. Y las ánforas2 a 250u.m. El horno posee una capacidad para 144 ánforas. Diariamente, dispone de 300 Kg de arcilla A y 16 Kg de arcilla B, y 15 horas de trabajo (él y su hijo). Las proporciones de arcilla A y B y el tiempo que necesita cada ánfora se recogen en la siguiente tabla: Ejercicio 1
(Gp:) 3. Ejercicios Un fabricante de baldosas desea optimizar la producción semanal de su factoría. Fabrica dos tipos de baldosas (Estándar y Lujo). Una baldosa Estándar proporciona un beneficio de 10 € y una Lujo de 15 €. Para la producción de baldosas se usan tres procesos, apomozado, pulido y abrillantado. La capacidad de apomazado es de 200horas/semana, de pulido es de 80horas/semana y la de abrillantado de 60horas/semana. Además, cada baldosa Estándar emplea 25mg de una sustancia para su limpieza por 10 de la baldosa Lujo. Se disponen de 1,2Kg por semana de esa sustancia. Los tiempos de pulido y abrillantado(en horas) por cada unidad se recogen en la siguiente tabla: Ejercicio 2