– 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