UNIDAD 4. PROGRAMACIÓN LINEAL.
4.1 La formulación del modelo LP.
4.2 Modelo LP del problema.
4.3 Condiciones especiales en modelos LP.
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. Implementación en SCILAB®.
La formulación del modelo LP.
La programación lineal (LP) es uno de los métodos más
ampliamente usado para optimización.
El término lo introdujo George Dantzing en 1947, para
describir problemas donde tanto función objetivo y
restricciones tiene carácter lineal.
La programación lineal, no se refiere a programación de
códigos en un lenguaje determinado.
La formulación del modelo LP.
• Organización de trabajadores de acuerdo a un
organigrama para maximizar la producción.
• Seleccionar que productos se deben manufacturar
teniendo en cuenta los recursos existentes para
maximizar las ganancias.
• Encontrar patrones de distribución para plantas pata
minimizar los costos, dentro unos recursos limitados.
Modelo LP del problema.
Cuando se formula un problema de LP, implica lidiar con
muchas variables, ecuaciones e inecuaciones.
La solución no solo debe cumplir con las restricciones,
además debe encontrar el optimo de la función objetivo.
Los software especializados como GAMS, pueden tratar
con miles de variables y restricciones.
La formulación del modelo LP.
El modelo de programación lineal (LP) es extensamente
utilizado en casi todas las áreas del conocimiento.
La relación lineal entre variables le confiere la
particularidad de ser un modelo fácil de generar y simple
de resolver y analizar.
Esto permite automatizar el proceso de generación del
modelo, por lo que es posible generar grandes modelos
LP.
La formulación del modelo LP.
Publicaciones recientes han reportado trabajo con
modelos LP de más de cien mil variables.
Para casos de 2 variables, puede emplearse el método
gráfico.
La formulación del modelo LP.
Estructura de un problema de optimización.
Se buscará maximizar o minimizar una función llamada
objetivo cuyas variables deber estar regidas, además, por
cierto número de restricciones que pueden ser de igualdad
o desigualdad.
Optimizar f(x) ---> Función Objetivo
Sujeto a :
Hk(x) = 0 k= 1,2,..,n Restricciones de igualdad.
Gk(x) > b k= 1,2,..,n Restricciones de desigualdad.
XL < x < X U Restricciones de intervalo
La formulación del modelo LP.
Región factible:
Conjunto de valores de las variables independientes que
satisfacen simultáneamente las restricciones de igualdad y
de desigualdad.
Así por ejemplo, las condiciones de igualdad solo se
satisfacen en una curva, en el caso de que se traten de
solamente dos variables y, obviamente, pueda
representarse en el plano.
La formulación del modelo LP.
Para el mismo caso una condición de desigualdad, separa
al plano en 2 zonas, una de valores factibles y la otra de
valores no factibles.
La formulación del modelo LP.
La formulación del modelo LP.
Considere el siguiente problema de Optimización:
Maximizar :
Sujeto a :
La formulación del modelo LP.
El problema de programación lineal en dos dimensione.
Se puede interpretar de manera más esquemática con un
gráfico.
Denotando zonas “factibles”, es decir, donde las ecuaciones
e inecuaciones limitan un conjunto solución.
La formulación del modelo LP.
Ejemplo ( 2 dimensiones)
La empresa “Heat Exchangers” , fabrica y vende dos modelos de intercambiadores
de calor: “Hot rod” y el ”Hydro-thing”. Su propietario y gerente, Dirck Diggler,
necesita decidir cuanto de cada tipo producir durante el ciclo siguiente de
producción. La carcaza y las bombas, las compra prefabricadas, a las cuales le
adiciona la tubería, para confeccionar dichos intercambiadores. Dirck instala el
mismo tipo de bombas a ambos intercambiadores. Su disposición de las mismas es
de 200 en cada ciclo. Ambos intercambiadores tienen diferentes requerimientos de
material y mano de obra. Así, cada “Hot rod” requiere 9 horas de mano de obra y
12 pies de tubería, mientras que cada ”Hydro-thing” requiere 6 horas de mano de
obra y 16 pies de tubería. Dirck, espera disponer de 1566 horas de mano de obra y
2880 pies de tubería en cada ciclo de producción. Cada “Hot rod” provee de una
ganancia de 350$ mientras que cada ”Hydro-thing” vendido reporta 300$. Su
propietario confía en vender toda su producción. La pregunta es, ¿Cuántos “Hot
rod” y cuántos ”Hydro-thing” producir para maximizar las ganancias en cada ciclo?
Ejemplo ( 2 dimensiones)
Los pasos generales de la metodología de resolución de un modelo
LP, son:
1. Comprender el problema,
En este caso implica, determinar el número a producir de cada tipo de
intercambiador para obtener la máxima ganancia, disponiendo de 200
bombas, 1566 horas de mano de obra y 2880 pies de tubería.
Ejemplo ( 2 dimensiones)
2. Identificar las variables de decisión.
Así, en este ejemplo, X1 será la cantidad de “Hot rod” y X2 la
cantidad de ”Hydro-thing” a producir.
3. Formular la función objetivo como combinación lineal de las
variables de decisión. Esta función expresa la relación
matemática entre las variables que debe ser maximizada o
Minimizada. En nuestro ejemplo: por cada “Hot rod” vendido
(X1), ingresan 350 $ y por cada ”Hydro-thing” (X2),
en cambio, 300 $. La ganancia total será:
G ( X 1 , X 2 )=350∗X 1+300∗X 2
Ejemplo ( 2 dimensiones)
4. Las restricciones como combinación lineal de la variables de
decisión.
Estos son valores que restringen las variables en el problema a resolver.
En este ejemplo: tenemos tres restricciones.
La primera en que el número de bombas disponibles es de 200, valor
que no puede superarse. Esto se expresaría:
1∗X 1+1∗X 2 ⩽200
Ejemplo ( 2 dimensiones)
La segunda restricción es el número de horas disponibles: 1566.
Cada baño requiere un numero diferente de horas, y juntas no deben
superar el límite permitido:
9∗X 1 +1∗6X 2 ⩽1565
La tercera y última restricción es sobre los pies de tuberías disponibles.
La cantidad total requerida deberá ser menor o igual que 2880:
12∗X 1+1∗16X 2 ⩽2880
Ejemplo ( 2 dimensiones)
La segunda restricción es el número de horas disponibles: 1566.
Cada baño requiere un numero diferente de horas, y juntas no deben
superar el límite permitido:
9∗X 1 +1∗6X 2 ⩽1565
La tercera y última restricción es sobre los pies de tuberías disponibles.
La cantidad total requerida deberá ser menor o igual que 2880:
12∗X 1+1∗16X 2 ⩽2880
Ejemplo ( 2 dimensiones)
5. Identificar los límites superiores e inferiores de las variables.
En este ejemplo, se asume que ni X1 ni X2 deben ser negativos o
ceros, lo que se expresa en forma matemática, como:
X1 ≥ 0
X2 ≥ 0
Ejemplo ( 2 dimensiones)
El modelo entonces, queda planteado de esta
manera:
Ejemplo ( 2 dimensiones)
Resolución del problema por el método gráfico.
Cada restricción representada
(Hydro-thing)
por una desigualdad, divide al
espacio en dos zonas: una
factible y la otra, no.
Las igualdades, solo se cumplen
en una recta. Una vez
introducidas todas las
restricciones quedará una zona
(Hot-Rod) en la que las variables asumen
todas las restricciones.
Ejemplo ( 2 dimensiones)
En algún punto de la zona coloreada, las variables,
maximizan la función objetivo.
Para seguir
(Hydro-thing)
Supongamos un valor
para la función objetivo
(por ejemplo 35000 $) y
grafiquemos su línea.
Supongamos ahora
una ganancia de 52500
$ y grafiquemos este
(Hot-Rod)
nuevo objetivo.
Ejemplo ( 2 dimensiones)
Graficando la
(Hydro-thing)
nueva linea recta:
52.000=350∗X 1 +300∗X 2
Toda la recta esta
conforma por
puntos solución
factibles.
(Hot-Rod)
Ejemplo ( 2 dimensiones)
Vemos que la nueva solución
es paralela a la anterior. Para
(Hydro-thing)
hallar la óptima, se debe trazar
una paralela que pase por el
punto más alejado de la zona
factible.
El punto óptimo se encuentra
para X1 = 122 y X2 = 78. Esto
significa que deberán
producirse 122 Hot-Rod y 78
Hydro-thing para que la
ganancia sea máxima, esto es:
350 $ * 122 + 300 $ * 78 =
66100 $
(Hot-Rod)
Ejemplo ( 2 dimensiones)
Cualquier otro punto que caiga en la zona factible, dará una
menor ganancia, mientras que no puede haber otro punto de
mayor ganancia y a la vez cumpla las restricciones del problema.
De hecho, la solución óptima, siempre caerá sobre uno de los
vértices generados por las rectas que representan las
restricciones. En nuestro caso son cinco los vértices:
Ejemplo ( 2 dimensiones)
Vemos que si la curva de nivel
representativa del objetivo fuera
paralela algunas de las restricciones
todos los puntos de intersección
serían igualmente factibles e
igualmente óptimos. Esto no es una
dificultad, de hecho en casos de
programación y optimización de
múltiples objetivos, esto es muy
deseable.
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
Una planta procesadora de gasolina recibe cada semana una cantidad
fija de materia prima para gasolina. Esta última se procesa en dos tipos
de gasolina, de calidad regular y premium. Estas clases de gasolina son
de alta demanda; es decir, se tiene garantizada su venta y se obtiene
diferentes utilidades para la compañía. Sin embargo, su producción
involucra varias restricciones; tiempo y almacenaje en sitio. Por ejemplo,
sólo una de las clases se puede producir a la vez, y las instalaciones
están abiertas solamente 80 horas por semana. Además, existe un
límite de almacenamiento para cada uno de los productos. Todos estos
factores se listan abajo (observe que una tonelada métrica, o ton, es
igual a 1.000 kg):
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
Producto
______________________
Recurso Regular Prémium Disponibilidad del recurso
_________________________________________________________
Materia Prima 7 m3/ton 11 m3/ton 77 m3/semana
Tiempo de
producción 10 hr/ton 8 hr/ton 80 hr/semana
Almacenamiento 9 ton 6 ton
________________________________________________________________
Aprovechamiento 150/ ton 175/ ton
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
●
La solución, por el método gráfico; esta limitada a dos o
tres dimensiones.
●
Con la formulación adecuada, mostrará un espacio de
soluciones factibles.
●
Se comienza trazando las restricciones, reemplazando el
signo de desigualdad con uno de igualdad.
7
x 2=− x 1 +7
11
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
Después, se puede agregar la función objetivo a la gráfica. Para
hacer esto, se debe escoger un valor de Z.
Por ejemplo, para Z = 0 la función objetivo es ahora:
0=150x 1 +175x 2
150
x 2=− x1
175
Esta función representa una recta que pasa por el origen
( punteada ).
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
Ahora, puesto que estamos interesados en maximizar Z, se
puede aumentar a digamos 600, y la función objetivo es:
600 150
x 2= − x1
175 175
Así, incrementando el valor de la función objetivo, la línea se mueve
lejos del origen. Como la línea todavía está dentro del espacio de
solución, nuestro resultado es aún factible. Sin embargo, por la misma
razón, todavía hay espacio para mejorarlo. Por tanto, Z se puede seguir
aumentando hasta que un incremento adicional lleve la función objetivo
más allá de la región factible.
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
4.4 Resumen para la resolución gráfica de problemas de
programación lineal. ( Ejemplo 2 )
Además de determinar los valores óptimos, el procedimiento
gráfico proporciona conocimientos adicionales del problema.
Esto se puede apreciar al sustituir de nuevo las soluciones
en las ecuaciones restrictivas.
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®.
Para la implementación de un problema de Programación
Lineal, recordamos la definición:
minimizar f ( ⃗x )=c T x
Ax=b
Gx⩽h ,
x L⩽x⩽x L
Donde ⃗x es el vector que contiene las variables,
x=[ x 1 , x 2 , .... , x n ]T , c es el vector columna de los
coeficientes de la función de minimizar, A es la matriz de
los coeficientes de las restricciones de igualdad y G es a la
matriz de coeficientes de las restricciones de desigualdad.
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®. Función “karmarkar” ( SCILAB-v 5.5.2 )
Para referencia:
[Link]
Ejemplo 3 Ahora se le da formato de matriz al
minimizar −x 1 −x 2 problema para introducirlo en SCILAB
sujeto a x 1 −x 2 =0
[ ]
Matriz de los coeficientes
x 1 +x 2 +x 3=2 Aeq= 1 −1 0 de las restricciones de
1 1 1
x 1 , x 2 , x 3 ⩾0 igualdad.
Vector columna de los términos
[]
beq= 0
2 independientes de las restricciones de
igualdad.
[]
−1
Vector columna Coeficientes de
c= −1
0 la función objetivo.
[]
0.1
x0= 0.1 Punto de inicio para iteraciones
1.8
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®. Función “karmarkar” ( SCILAB-v 5.5.2 )
Y en SCILAB ??
minimizar −x 1 −x 2
sujeto a x 1 −x 2 =0
x 1 +x 2 +x 3=2
x 1 , x 2 , x 3 ⩾0
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®. Función “karmarkar” ( SCILAB-v 5.5.2 )
Ejemplo 4.
minimizar −20x 1 −24x 2
sujeto a 3x 1+6x2 ⩽60
4x 1+2x 2 +x 3⩽32
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®. Función “karmarkar” ( SCILAB-v 5.5.2 )
Estas son las secuencias de comandos para invocar
La función “karmarkar”
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®.
1 1
Ejemplo 5 Función Objetivo f ( x 1 , x 2 )= x 1+ x 2
4 3
Restricciones −5x1 −x 2 ⩽−5
−2x1−5x 2⩽−10
x 1 ⩾0, x 2 ⩾0
c= 1/ 4
1/3 [ ]
b= [ ]
−5
−10
A= [ −5 −1
−2 −5 ]
IMPLEMENTACIÓN DE PROBLEMAS DE LP, USANDO
SCILAB®.
1 1
Ejemplo 5 Función Objetivo f ( x 1 , x 2 )= x 1+ x 2
4 3
Restricciones −5x1 −x 2 ⩽−5
−2x1−5x 2⩽−10
x 1 ⩾0, x 2 ⩾0