Upload
sandri-guerrero
View
156
Download
1
Embed Size (px)
Citation preview
Tema 1. Programación Lineal
Modelos matemáticos para resolver problemas en los que hay que asignar ciertos recursos,
limitados por restricciones de tipo lineal, de tal manera que la asignación cumpla de modo
óptimo un objetivo predeterminado. Este reparto de recursos conllevará una adecuada
planificación de las actividadescorrespondientes
Desarrollo histórico de la PL
Trabajos aislados (PL no sistematizada):Fourier, de la Vallé Poussin, etc
JohnJohn VonVon NeumannNeumann (1903-1957): Desarrolla en los años 1920’s la Teoría de juegos, de gran importancia en la futura PL y con enormes implicaciones en la Economía
WassilyWassily LeontiefLeontief (1906-1999): Analiza la economía norteamericana mediante el uso de restricciones lineales. Nobel de Economía en 1973
LeonidLeonid KantorovichKantorovich (1912-1986): Desarrolla el primer modelo de PL aplicado a la industria de la madera en la URSS. Nobel de Economía en 1975 GeorgeGeorge StiglerStigler (1911-1991): Estudia en 1945 el llamado problema de la dieta y lo resuelve de forma heurística. Nobelde Economía en 1982
GeorgeGeorge B. B. DantzigDantzig (1914-2005): Miembro del proyecto SCOOP (ScientificComputation of Optimum Program) de la USAF durante los años de posguerra. Identifica los problemas mediante desigualdades lineales e inicia la búsqueda de un método algorítmico de búsqueda de la solución óptima. SCOOP desarrolla el modelo básico de PL y diseña el mecanismo deresolución (Método Simplex, 1947).
Primeras aplicaciones:Operaciones militares (“programas”), modelos económicos y teoría de juegos
Revolución informática:Primer problema resuelto manualmente: 1948, “problema de la dieta” de Stigler 120 días de trabajo (solución óptima sólo 24 cts más barata que la heurística de Stigler)Primer problema resuelto por computadora: 1952 (computadora SEAC)
Actualmente:“Programa” = plan para planificar y controlar las estrategias de inversión, la producción, la distribución, la comercialización, etc, de las actividades o productos que constituyen el objeto de interés de una empresa.Aplicaciones: Medio Ambiente, Sociología, Educación, Administración Pública, Industria, Informática, Economía, Logística, Telecomunicaciones, etc
MODELO:Programa lineal: Modelo o problema de maximización o
minimización de una función lineal, sujeta a restricciones lineales, con variables reales positivas.
nn xcxcxcmin +++ K2211
s.a.
mnmnmm
nn
nn
bxaxaxa
bxaxaxabxaxaxa
≥+++
≥+++≥+++
K
MM
K
K
2211
22222121
11212111
0,,, 21 ≥nxxx K
Función objetivo
Restricciones funcionales
Restricciones de no negatividad
Suposiciones: Proporcionalidad, aditividad y divisibilidad. Valores de los coeficientes aij, cj y bi conocidos
PASOS:•Identificar las variables de decisión (x1,...,xn)•Expresar las restricciones en términos de las variables•Expresar la función objetivo en términos de las variables
0 ..
≥≥
=
xbxAas
xczmin t
r
rr
rrRegión Factible =
( ){ }0,:R,, 1 ≥≥∈= xbxAxx nn
rrrK
SOLUCIÓN: Buscar entre todos los puntos de la región factible aquel o aquellos que minimicen la función objetivo
Nota: Las regiones factibles siempre son convexas (se puede ir en línea recta desde un punto a otro de la región sin salir de la misma)
Ejemplo: Una empresa láctea plantea la producción de dos nuevas bebidas. Producir un litro del primer tipo de bebida cuesta 2$, mientras que un litro del segundo tipo de bebida cuesta 5$. Para realizar el lanzamiento comercial se necesitan más de 6000000 litros de bebida, aunque del segundo tipo no podrán producirse (por limitaciones técnicas) más de 5000000. Además, se desea producir más cantidad de bebida del segundo tipo que del primero. ¿Cuántos litros habrá que producir de cada tipo de bebida para que el coste de producción sea mínimo?
Variables de decisión: xi = millones de litros producidos del tipo i de bebida
función objetivo: z = 2x1+5x2 (z =coste total de producción)
restricciones: x1 + x2 > 6
x2 < 5
x1 - x2 < 0
x1 , x2 > 0
0 1 2 3 4 50
1
2
3
4
5Y
X
: 1.0 X + 1.0 Y = 6.0
: 0.0 X + 1.0 Y = 5.0
: 1.0 X - 1.0 Y = 0.0
Payoff: 2.0 X + 5.0 Y = 17.0
: 1.0X + 1.0Y >= 6.0: 0.0X + 1.0Y <= 5.0: 1.0X - 1.0Y <= 0.0
Región factible
Función objetivo
0 1 2 3 4 50
1
2
3
4
5Y
X
Payoff: 2.0 X + 5.0 Y = 21.0
Optimal Decisions(X,Y): ( 3.0, 3.0): 1.0X + 1.0Y >= 6.0: 0.0X + 1.0Y <= 5.0: 1.0X - 1.0Y <= 0.0
RESOLUCIÓN GRÁFICA:
Solución óptima
SOLUCIONES ALTERNATIVAS:
0 1 2 30
1
2
3Y
X
: 2.0 X + 7.0 Y = 21.0
: 7.0 X + 2.0 Y = 21.0
Payoff: 4.0 X + 14.0 Y = 42.0
Optimal Decisions(X,Y): ( 2.3, 2.3) ( 0.0, 3.0): 2.0X + 7.0Y <= 21.0: 7.0X + 2.0Y <= 21.0
0 10 20 30 40 50 600
10
20
30
40
50
60
70
80
: 1.0 X - 1.0 Y = 10.0
: 2.0 X - 1.0 Y = 40.0Payoff: 2.0 X + 1.0 Y = 80.0
Optimal Decisions(X,Y): (210.0, 210.0): 1.0X - 1.0Y <= 10.0: 2.0X - 1.0Y <= 40.0
SOLUCION NO ACOTADA:
MÉTODO SIMPLEX (G.Dantzig, 1949)
Resultados en los que se basa:
• El problema tiene solución óptima si la región factible es no vacía y acotada.
• Existe un número finito de puntos extremos.• Si existe solución óptima, entonces existe al menos un
punto extremo óptimo.• Si el valor de la función objetivo en un punto extremo es
mejor que en los puntos extremos adyacentes, entonces es también mejor que en el resto de los puntos extremos.
MÉTODO: Desplazarse de un punto extremo a otro adyacente siempre que mejore la función objetivo.
IDENTIFICACIÓN DE LOS PUNTOS EXTREMOS:
SOLUCIONES BÁSICAS de un sistema de m ecuaciones lineales con n variables (n > m):
Se obtienen haciendo n-m variables igual a 0, y el resto (m) son la solución del sistema m x m que resulta.
Variables > 0 : BÁSICAS (en general > 0)
Variables = 0: NO BÁSICAS
Si las variables básicas son positivas, entonces SOLUCIÓN BÁSICA FACTIBLE.
Nota: Puede haber variables básicas iguales a 0, en cuyo caso la SBF se dice que es “degenerada”
PUNTOS EXTREMOS = SOLUCIONES BÁSICAS FACTIBLES
MÉTODO: Para pasar de un punto extremo (S.B.F.) a otro, una variable básica (>0) pasará a ser no básica (=0), mientras que otra variable no
básica cambiará a básica.
Forma estándar
0, 42 52 323- 632 s.a.
34max
21
21
2
21
21
21
≥≤+≤≤+≤++=
xxxxxxxxx
xxz
0,,,,, 42
52 323- 632 s.a.
34max
432121
421
32
221
121
21
≥=++=+=++=++
+=
ssssxxsxxsxsxxsxxxxz
S.B.F. : 6-4=2 variables no básicas (=0) y
4 variables básicas
n=6 variables
m=4 ecuaciones
0 1 20
1
2X2
X1
: 2.0 X1 + 3.0
: -3.0 X1 + 2.0 X2 = 3.0: 0.0 X1 + 2.0
: 2.0 X1 + 1.0 X2 = 4.0
Payoff: 4.0 X1 + 3.0 X2 = 5.4
: 2.0X1 + 3.0X2 <= 6.0: -3.0X1 + 2.0X2 <= 3.0: 0.0X1 + 2.0X2 <= 5.0: 2.0X1 + 1.0X2 <= 4.0
C
C: s1= s4= 0
E
E: x1= s2= 0
A
A: x1= x2= 0
B
B: x2= s4= 0
D
D: s1= s2= 0
Búsqueda de una S.B.F. inicial para empezar el algoritmo:
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
⎟⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
⋅
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛−
4536
100012010020001023000132
4
3
2
1
2
1
ssssxx
⎟⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
=
⎟⎟⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜⎜⎜
⎝
⎛
453600
4
3
2
1
2
1
ssssxx
A
En A, z = 0. Hay que comprobar si z mejora (aumenta) al desplazarse a las S.B.F. adyacentes (B ó E)
¿Cómo saber si desplazarse a B ó a E para que z aumente?
Formato de tabla:Básicas x1 x2 s1 s2 s3 s4 Solución
z -4 -3 0 0 0 0 0
s1 2 3 1 0 0 0 6s2 -3 2 0 1 0 0 3s3 0 2 0 0 1 0 5s4 2 1 0 0 0 1 4
S.B.F. inicio
Valores de zy variables básicas
S.B.F. = A
La variable con coeficiente “más negativo” en z será la que más aumente la f.o.
Maximizar
(minimizar⟩ coeficiente “más positivo”)
si aumenta x1 , z tendrá un mayor aumento
x1 entra en la base (deja de ser 0). Nos movemos al punto B.
¿cómo saber cuánto tiene que aumentar x1 para llegar a B y qué variable sale de la base (pasa a ser 0)?
bajo x1 Solución
2 6
-3 3
0 5
2 4
s1 6/2=3
s4 4/2=2
En el punto B, x1= 2 y s4= 0, con lo que las variables no básicas serían x2 y s4, este máximo aumento en la variable que entra en la base (x1) lo indica el menor cociente
La variable que sale de la base (que pasa a valer 0) es aquella que tenga el menor cociente entre la columna solución y la columna bajo la variable que entra, cuando este último valor es positivo.
En este caso, entra en la base la variable x1 y sale de la base la variable s4, es decir, estamos en el punto B.
Para saber cuánto vale ahora la función objetivo y cómo se han modificado las otras variables, es necesario expresar los valores de la tabla en función de la nueva variable básica x1.
Esta operación se realiza pivotando (Gauss-Jordan) sobre el elemento que está en la fila de la variable que sale y la columna de la variable que entra (en el ejemplo, el 2)
Básicas x1 x2 s1 s2 s3 s4 Soluciónz -4 -3 0 0 0 0 0 s1 2 3 1 0 0 0 6 s2 -3 2 0 1 0 0 3 s3 0 2 0 0 1 0 5 s4 2 1 0 0 0 1 4
2
pivote
Paso 1: dividir la fila de la variable que sale entre el pivoteBásicas x1 x2 s1 s2 s3 s4 Solución
z -4 -3 0 0 0 0 0 s1 2 3 1 0 0 0 6 s2 -3 2 0 1 0 0 3 s3 0 2 0 0 1 0 5 x1 1 1/2 0 0 0 1/2 2
Como x1 entra en la base y s4 sale, se intercambian
Paso 2: hacer ceros por en la columna de la variable que entra, por encima y por debajo del pivote
•Nueva fila z = Anterior fila z + 4 · fila del pivote
•Nueva fila s1= Anterior fila s1 -2 ·fila del pivote
•Nueva fila s2 = Anterior fila s2 + 3 · fila del pivote
•Nueva fila s3 = Anterior fila s3 (no hay cambios, ya había un 0)
Básicas x1 x2 s1 s2 s3 s4 Soluciónz 0 -1 0 0 0 2 8 s1 0 2 1 0 0 -1 2 s2 0 7/2 0 1 0 3/2 9 s3 0 2 0 0 1 0 5 x1 1 1/2 0 0 0 1/2 2
NUEVA TABLA:
Básicas x1 x2 s1 s2 s3 s4 Soluciónz 0 -1 0 0 0 2 8 s1 0 2 1 0 0 -1 2 s2 0 7/2 0 1 0 3/2 9 s3 0 2 0 0 1 0 5 x1 1 1/2 0 0 0 1/2 2
-12
2ª Iteración: Entra x2 y sale s1. Tras pivotar sobre el 2:
Básicas x1 x2 s1 s2 s3 s4 Soluciónz 0 0 1/2 0 0 3/2 9 x2 0 1 1/2 0 0 -1/2 1 s2 0 0 -7/4 1 0 13/4 11/2 s3 0 0 -1 0 1 1 3 x1 1 0 -1/4 0 0 3/4 3/2
Esta nueva tabla nos indica que estamos en C (s1= s4=0). La solución es óptima, porque todos los coeficientes en z son positivos. Por lo tanto:
x1* = 3/2 , x2
* = 1, (s1* = 0 , s2
* = 11/2 , s3* = 3 , s4
* = 0) y z*=9
El problema de la S.B.F. inicial
Si el programa lineal tiene todas sus restricciones del tipo < , entonces las variables de holgura proporcionan una S.B.F. inicialSi en alguna restricción no hay variable de holgura, entonces seintroduce una variable artificial, que formará la base inicial.
En la solución final, las variables artificiales deberían ser cero, pues, de lo contrario, significaría que el problema no tiene solución.
Se utilizará el Método de penalización.
Método simplex revisado
Es una variante del método simplex que reduce la complejidad computacional con vistas a una implementación óptima.
ANÁLISIS DE SENSIBILIDAD
Consiste en comprobar cómo se modifica el problema ante los cambios que sufran sus coeficientes. Estudiaremos los cambios en los recursos (lado derecho) y en la función objetivo
PRECIO SOMBRA DE UN RECURSO:
Es el aumento que se produce en la función objetivo por cada unidad que aumente el lado derecho asociado a ese recurso.
Por tanto, también puede ser interpretado como el precio máximo a pagar por disponer de una unidad adicional de dicho recuso.
Atención: La interpretación del precio sombra solamente es válida dentro de un rango de valores para el lado derecho del recuso, pues puede ocurrir que si se aumenta o disminuye mucho esta cantidad, la restricción sea redundante o cambien las variables básicas.
0 1 2 3 4 5 6 70
1
2
3
4
5
6
7
8
9X2
X1
: 1.0 X1 + 1.0 X2 = 5.0
: 1.0 X1 - 3.0 X2 = 0.0
: 10.0 X1 + 15.0 X2 = 150.0
: 20.0 X1 + 10.0 X2 = 160.0
: 30.0 X1 + 10.0 X2 = 135.0
Payoff: 5000.0 X1 + 4000.0 X2 = 50500.0
Optimal Decisions(X1,X2): ( 4.5, 7.0): 1.0X1 + 1.0X2 >= 5.0: 1.0X1 - 3.0X2 <= 0.0: 10.0X1 + 15.0X2 <= 150.0: 20.0X1 + 10.0X2 <= 160.0: 30.0X1 + 10.0X2 >= 135.0
Veamos lo que ocurre al incrementar el L.D. de la cuarta restricción en una unidad. Actualmente el valor óptimo de la f.o. es 50500
0 1 2 3 4 5 6 70
1
2
3
4
5
6
7
8
9X2
X1
: 1.0 X1 + 1.0 X2 = 5.0
: 1.0 X1 - 3.0 X2 = 0.0
: 10.0 X1 + 15.0 X2 = 150.0
: 20.0 X1 + 10.0 X2 = 161.0
: 30.0 X1 + 10.0 X2 = 135.0
Payoff: 5000.0 X1 + 4000.0 X2 = 50675.0
Optimal Decisions(X1,X2): ( 4.6, 7.0): 1.0X1 + 1.0X2 >= 5.0: 1.0X1 - 3.0X2 <= 0.0: 10.0X1 + 15.0X2 <= 150.0: 20.0X1 + 10.0X2 <= 161.0: 30.0X1 + 10.0X2 >= 135.0
El valor de la f.o. ha aumentado a 50675, por lo tanto el precio sombra de este cuarto recurso es de 175. Como las variables básicas siguen siendo las mismas y la restricción nueva no es redundante, la interpretación es válida.
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9X2
X1
: 1.0 X1 + 1.0 X2 = 5.0
: 1.0 X1 - 3.0 X2 = 0.0
: 10.0 X1 + 15.0 X2 = 150.0
: 20.0 X1 + 10.0 X2 = 245.0
: 30.0 X1 + 10.0 X2 = 135.0
Payoff: 5000.0 X1 + 4000.0 X2 = 63333.3
Optimal Decisions(X1,X2): (10.0, 3.3): 1.0X1 + 1.0X2 >= 5.0: 1.0X1 - 3.0X2 <= 0.0: 10.0X1 + 15.0X2 <= 150.0: 20.0X1 + 10.0X2 <= 245.0: 30.0X1 + 10.0X2 >= 135.0
Al pasar el L.D. a 245 la restricción es redundante, y aunque se aumente más el L.D. no se mejora el valor de la f.o.
0 1 2 3 4 5 6 70
1
2
3
4
5
6
7
8
9X2
X1
: 1.0 X1 + 1.0 X2 = 5.0
: 1.0 X1 - 3.0 X2 = 0.0
: 10.0 X1 + 15.0 X2 = 150.0
: 20.0 X1 + 10.0 X2 = 160.0
: 30.0 X1 + 10.0 X2 = 135.0
Payoff: 10000.0 X1 + 4000.0 X2 = 77714.2
Optimal Decisions(X1,X2): ( 6.9, 2.3): 1.0X1 + 1.0X2 >= 5.0: 1.0X1 - 3.0X2 <= 0.0: 10.0X1 + 15.0X2 <= 150.0: 20.0X1 + 10.0X2 <= 160.0: 30.0X1 + 10.0X2 >= 135.0
Cambios en los coeficientes de la función objetivo: Al modificar estos coeficientes, cambia la pendiente de la recta que encuentra el óptimo, por lo que puede modificarse la solución óptima, como en el caso que se muestra, donde el coeficiente de x1 pasa de 5000 a 10000