Clase II - Jaqueline Avila Rico

Vista previa del material en texto

Aplicación de Programación 
Matemática para la Optimización 
y el Diseño de Procesos y 
Sistemas
Programación Matemática
• ¿Qué es la programación matemática?
Es una potente técnica de modelado usada en el proceso de toma de decisiones. 
• Resolver un problema de este tipo implica: 
1.- Identificar las posibles decisiones que pueden tomarse; esto lleva a identificar 
las variables del problema. Normalmente, las variables son de carácter cuantitativo y 
se buscan los valores que optimizan el objetivo. Variables de decisión
2.- Determinar qué decisiones resultan admisibles; esto conduce a un conjunto 
de restricciones que se determinan teniendo presente la naturaleza del problema. 
Restricciones del problema.
3.- Calcular costo/beneficio asociado a cada decisión admisible; supone evaluar 
una función objetivo que asigna a cada conjunto posible de valores de las variables 
que determinan una decisión un valor de costo/beneficio. Función objetivo.
• El conjunto de todos estos elementos define el problema de optimización.
Programación Lineal (PL)
• PL trata exclusivamente con funciones 
objetivo y restricciones lineales.
• Es una de las áreas más importante de la 
matemática aplicada. Se utiliza en campos 
como ingeniería, economía, gestión y otras 
áreas de la ciencia.
Un problema de PL requiere identificar 4 componentes:
1. El conjunto de datos.
2. El conjunto de variables involucradas en el problema, 
junto con sus dominios respectivos de definición.
3. El conjunto de restricciones (lineales) que definen el 
conjunto de soluciones admisibles.
4. La función objetivo (lineal) que debe ser optimizada 
(minimizada o maximizada).
Programación Lineal (PL)
* PL Entera Estricta (PLEE) - o Entera Pura-.
Todas las variables deben tomar valores enteros.
PL Entera Estricta 0/1 (PPLEM 0/1).
Todas las variables deben tomar el valor 0 o 1.
* PL Entera-Mixta (PLEM)
Algunas variables no necesariamente deben tomar valores enteros.
(Variables enteras mezcladas con variables continuas)
PL Entera-Mixta 0/1 (PLEM 0/1).
Algunas variables pueden tomar cualquier valor (Variables binarias 
mezcladas con variables continuas).
Programación No Lineal (PNL)
• Problemas de programación lineal: restricciones 
y función a optimizar son lineales.
• En la vida real se tiene que enfrentar con cierta 
frecuencia a otro tipo de problemas que no son 
lineales. 
• En un problema de programación no lineal 
(PPNL) el conjunto de restricciones o la 
función objetivo, o ambos, son no lineales.
Introducción a Programación Lineal (PL)
• Formulación del problema.
• Problema de programación lineal en forma estándar.
– Transformación a la forma estándar
• Soluciones básicas.
• Sensibilidades.
• Dualidad.
– Obtención del dual a partir del primal en forma estándar
– Obtención del problema dual.
– Teoremas de dualidad.
• Ejercicios
Formulación del problema
Objeto de la Programación Lineal (PL)
• Optimizar (minimizar o maximizar) una función lineal de 
n variables sujeto a restricciones lineales de igualdad o 
desigualdad.
• Más formalmente…
un problema de PL consiste en encontrar el óptimo 
(máximo o mínimo) de una función lineal en un conjunto 
que puede expresarse como la intersección de un 
número finito de hiperplanos y semiespacios en Rn.
Def.1: Problema Programación Lineal (PPL)
m q p 1
que talespositivos enterosson my q, p, donde
m , . . . q, i bxa
1 - q , . . . p, i ,bxa
1 - p ., . . 2, 1, i ,bxa
a sujeto
xc f(x) Zmin) (omax 
i
1
jij
i
1
jij
i
1
jij
1
jj
≤≤≤
⎪
⎪
⎪
⎭
⎪
⎪
⎪
⎬
⎫
=≤⋅
=≥⋅
==⋅
⎭
⎬
⎫⋅==
∑
∑
∑
∑
=
=
=
=
n
j
n
j
n
j
n
j
función objetivo o función de coste (FO)
Posibles alternativas referentes a operadores que 
relacionan los dos términos de las restricciones 
(lineales)
Fu
nci
ón
 ob
jeti
vo 
y r
est
ric
cio
nes
 LIN
EA
LE
S
Def. 2. Solución factible (SF)
• Un punto x = (x1, x2, . . . , xn) que satisface 
todas las restricciones es una solución factible. 
• El conjunto de todas las soluciones factibles es 
la región de factibilidad.
Def. 3. Solución óptima (SO)
• Un punto factible xx tal que f(x) ≥ f(xx) para cualquier 
otro punto factible x es una solución óptima
(mínimo) del PPL.
• El objetivo de todo problema de optimización es 
encontrar un óptimo global. 
¡Las condiciones de optimalidad sólo garantizan, en 
general, óptimos locales (si existen)!. 
• Los problemas lineales tienen propiedades que 
garantizan el óptimo global.
Propiedades de problemas lineales
• Si región factible (RF) está acotada, el problema siempre 
tiene una solución (condición suficiente pero no necesaria 
para que exista una solución).
• El óptimo de un PPL es siempre un óptimo global.
• Si x y y son soluciones óptimas de un PPL, cualquier 
combinación (lineal) convexa de ellos también es SO. 
Combinaciones convexas de puntos con el mismo valor de 
FO presentan el mismo valor de FO.
• SO se alcanza siempre, al menos, en 1 punto extremo de RF.
Casos de soluciones de un PPL
• Soluciones posibles de un PPL:
– Única.
– Múltiple.
– No acotada.
– Infactible.
Solución Única
0 
1
0 
4 2 
3 
6 
2 
:a sujeto
3 ZMaximizar 
1
21
2
21
1
21
21
21
≤−
−≤−−
≤−
≤−
≤
≤+
≤+−
+=
x
xx
x
xx
x
xx
xx
xx
0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0 4.5 5.0
-8
-6
-4
-2
0
2
4
6
8
10
x2
x1
 Z=6
 Z=7
 Z=8
 Z=9
 Z=10
 Z=11
 Z=12
Curvas de nivel de FO
Cr
ec
im
ie
nt
o
de
 F
O
… más sobre “Solución Única”
0 
1 
0 
4 2 
3 
6 
2 
:a sujeto
3 ZMaximizar 
1
21
2
21
1
21
21
21
≤−
−≤−−
≤−
≤−
≤
≤+
≤+−
+=
x
xx
x
xx
x
xx
xx
xx
-1 0 1 2 3 4 5 6
0
2
4
6
x 2
x1
 C1
 C2
 C4
 C5
 C6
Región factible
Vértice → Punto extremo
A
B
CD
E
F
G
0 
1 
0 
4 2 
3 
6 
2
:a sujeto
3 ZMaximizar 
1
21
2
21
1
21
21
21
≤−
−≤−−
≤−
≤−
≤
≤+
≤+−
+=
x
xx
x
xx
x
xx
xx
xx
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
-2
-1
0
1
2
3
4
5
6
7
8
9
10
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
-2
-1
0
1
2
3
4
5
6
7
8
9
10
RF
SOSO
C7
C3
C6
C5
C4
C2
x2
x1
 C1
 C2
 C4
 C5
 C6
C1
P(3,3) SO
C3
C7
Z=12
… más sobre “Solución Única”
El punto P (3,3) es la intersección de dos rectas
Soluciones Múltiples
0
1
0
42
3
6
2
:a sujeto
 ZMaximizar 
3 ZMaximizar 
1
21
2
21
1
21
21
21
21
≤−
−≤−−
≤−
≤−
≤
≤+
≤+−
+=
+=
x
xx
x
xx
x
xx
xx
xx
xx
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
-2
-1
0
1
2
3
4
5
6
7
8
9
10
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
-2
-1
0
1
2
3
4
5
6
7
8
9
10
P(2,4)
P(3,3)
Z=6
RF
C7
C3
C6
C5
C4
C2
x2
x1
 C1
 C2
 C4
 C5
 C6
C1
P(3,3) Soluciones
Múltiples
C3
C7
Z=12
Curvas de nivel son paralelas a una restricción
Solución No Acotada
0 
1
0 
2
:a sujeto
3 ZMaximizar 
1
21
2
21
21
≤−
−≤−−
≤−
≤+−
+=
x
xx
x
xx
xx
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
-2
-1
0
1
2
3
4
5
6
7
8
9
10
-2 0 2 4 6 8 10
-2
0
2
4
6
8
10
x 2
x1
 C1
 C5
 C6
 C7
Solución no acotada
Región factible no acotada en la dirección del crecimineto de la FO 
Solución Infactible
0 
0 
1 
0 
4 2
3 
6 
2
:a sujeto
3 ZMaximizar 
21
1
21
2
21
1
21
21
21
≤+
≤−
−≤−−
≤−
≤−
≤
≤+
≤+−
+=
xx
x
xx
x
xx
x
xx
xx
xx
Restricción no compatible con las demás
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
0
5
10
-3 -2 -1 0 1 2 3 4 5 6 7 8 9 10
-2
-1
0
1
2
3
4
5
6
7
8
9
10
P(3,3)
C7
C3
C6
C5
C4
C2
x 2
x1
 C1
 C2
 C4
 C5
 C6
C1
Solución
Infactible
C3
C7
PPL en forma estándar
• Son necesarios tres elementos:
1. Un vector c є Rn
2. Un vector no negativo b є Rm
3. Una matriz A de dimensión m×n.
• Problema lineal en forma estándar:
Minimizar Z = cTx → Producto escalar
sujeto a: Ax = b
x ≥ 0
• PPL está en forma estándar si y sólo si:
1. Es de minimización.
2. Sólo incluye restricciones de igualdad (=).
3. El vector b es no negativo.
4. Las variables x son no negativas
m q p 1m , . . . q, i bxa
1 - q , . . . p, i ,bxa
1 - p ., . . 2, 1, i ,bxa
a sujeto
xc f(x) Zmin) (omax 
i
1
jij
i
1
jij
i
1
jij
1
jj
≤≤≤
=≤⋅
=≥⋅
==⋅
⋅==
∑
∑
∑
∑
=
=
=
=
n
j
n
j
n
j
n
j
min. Z = cTx
sujeto a:
Ax = b 
x ≥ 0
Forma general Forma estándar
Transformación a forma estándar
Mediante manipulaciones algebraicas se llega a la forma estándar:
1.- Variables no restringidas en signo (-∞ a +∞) se pueden expresar como diferencias de 
variables no negativas (≥ 0). 
Una variable no restringida en signo se puede expresar sus partes positiva y negativa.
Las partes positiva y negativa de la variable xi se definen como: 
xi+ = max {0, xi} 
xi- = max {0,−xi}
Se comprueba que: 
xi = xi+ − xi-, 
|x| = xi+ + xi-
y que ambas xi+ y xi- son no negativas.
Si hay r variables no restringidas en signo, se necesitan r variables adicionales.
EJEMPLO: 
xi = - 5
Las partes positiva y negativa de la variable xi = -5 se definen como: 
xi+ = max {0, xi} = max {0, -5} = 0
xi- = max {0, −xi} = max {0, -(-5)} = 5
Se comprueba que: 
xi = xi+ − xi- = 0 − 5 = -5 
|xi| = xi+ + xi- = 0 + 5 = 5 
Ambas, xi+ = 0 y xi- = 5, son no negativas.
2.- Restricciones de desigualdad pueden convertirse en restricciones 
equivalentes de igualdad introduciendo nuevas variables: 
variables de holgura:
Si ai1x1 + ai2x2 + · · · + ainxn ≤ bi
entonces existe una variable xn+1 ≥ 0 tal que
ai1x1 + ai2x2 + · · · + ainxn + xn+1 = bi
Si ai1x1 + ai2x2 + · · · + ainxn ≥ bi
entonces existe una variable xn+1 ≥ 0 tal que
ai1x1 + ai2x2 + · · · + ainxn - xn+1 = bi
… más sobre “Transformación a forma estándar”
3. Para las mismas restricciones, un problema de maximización es 
equivalente a uno de minimización cambiando el signo de FO: 
max Z = cT x
es equivalente a
min Z = −cT x
(Zmax = - Zmin)
4. Restricción con término independiente b no positivo se reemplaza 
por otra equivalente cuyo término independiente es no negativo.
Reemplazar:
x1 + x2 = -2
por
-x1 - x2 = 2
… más sobre “Transformación a forma estándar”
0 x,x
 3 x- x 3x
2 x x
:a sujeto
5x 3x - 2x Z
Maximizar 
21
321
21
321
≥
≥+
≤+
+=
0 x, x, x, x, x,x
 3 x- ) x- (x- x 3x
2 x x x
:a sujeto
) x- 5(x - 3x 2x- Z
Minimizar
765421
57621
421
7621
≥
=+
=++
+=
Forma dada Forma estándar
Ejemplo 1
Ejemplo 2
0 x
1- x x
1 x- x- x
1 x x x
:a sujeto
 x- 3x ZMaximizar 
1
31
321
321
31
≥
≥+
≤
=++
=
0 x
1- x x
1 x- x- x
1 x x x
:a sujeto
 x- 3x ZMaximizar 
1
31
321
321
31
≥
≥+
≤
=++
=
1 x- x- 31 ≤
… más sobre “Ejemplo 2”
0 x
1- x x
1 x- x- x
1 x x x
:a sujeto
 x- 3x ZMaximizar 
1
31
321
321
31
≥
≥+
≤
=++
=
1 x- x- 31 ≤
0 z ,z ,y ,y
z - y x
z - y x
3232
333
222
≥
=
=
-
33
-
22
3322
 x z , x z
 x y , x y
==
== ++
… más sobre “Ejemplo 2”
0 x
1- x x
1 x- x- x
1 x x x
:a sujeto
 x- 3x ZMaximizar 
1
31
321
321
31
≥
≥+
≤
=++
=
1 x- x- 31 ≤
0 z ,z ,y ,y
z - y x
z - y x
3232
333
222
≥
=
=
-
33
-
22
3322
 x z , x z
 x y , x y
==
== ++
0 z ,y ,z ,y , x
1 z y- x-
 1 z y- z y- x
1 z- y z- y x
a sujeto
z y - 3x ZMaximizar 
33221
331
33221
33221
331
≥
≤+
≤++
=++
+=
… más sobre “Ejemplo 2”
0 z ,y ,z ,y , x
1 z y- x-
 1 z y- z y- x
1 z- y z- y x
a sujeto
z y - 3x ZMaximizar 
33221
331
33221
33221
331
≥
≤+
≤++
=++
+=
0 u , u 
1 u z y- x-
1 u z y- z y- x
21
2331
133221
≥
=++
=+++
… más sobre “Ejemplo 2”
0 z ,y ,z ,y , x
1 z y- x-
 1 z y- z y- x
1 z- y z- y x
a sujeto
z y - 3x ZMaximizar 
33221
331
33221
33221
331
≥
≤+
≤++
=++
+= 331 z - y 3x- ZMinimizar +=
0 u , u 
1 u z y- x-
1 u z y- z y- x
21
2331
133221
≥
=++
=+++
… más sobre “Ejemplo 2”
* Variables de holgura (u1, u2) no intervienen en la solución de problema original 
(son variables auxiliares).
* Valor óptimo de la FO del problema original es el óptimo del problema en forma 
estándar cambiado de signo:
Zóptimo MAX = - Zóptimo MIN
0 u ,u , z ,y ,z ,y , x
1 u z y- x-
 1 u z y- z y- x
1 z- y z- y x
a sujeto
z - y 3x- ZMinimizar 
2133221
2331
133221
33221
331
≥
=++
=+++
=++
+=
( )*2*1*3*3*2*2*1 u ,u , z ,y ,z ,y ,x
Solución óptima
Forma estándar
0 x
1- x x
1 x- x- x
1 x x x
:a sujeto
 x- 3x ZMaximizar 
1
31
321
321
31
≥
≥+
≤
=++
=
*
3
*
3
*
3
*
2
*
2
*
2
z - y x
z - y x
=
=
( )*3*2*1 x, x,x
Solución óptima
Problema original
… más sobre “Ejemplo 2”
	xClase II_Parte I_270315 sin animación.pdf
	xClase II_Parte II_2703415 sin animacion.pdf