Apunte Optimización
Apunte Optimización
Apunte Optimización
INGENIERÍA
Jorge Amaya
22 de octubre de 2018
El presente texto contiene la mayor parte de los contenidos del curso de Optimización que
he dictado en la Escuela de Ingenierı́a de la Universidad de Chile durante los últimos años.
Inicialmente, tanto los énfasis como las motivaciones del curso estaban en los fundamentos
matemáticos de la Optimización y en el rigor de su desarrollo. Con el tiempo, el curso fue
interesando también a estudiantes de variadas especialidades, lo cual ha significado que el
número de estudiantes se ha multiplicado desde fines de los 90’s, llegando actualmente alre-
dedor 200 o 300 por semestre, en secciones paralelas. En esta evolución hemos debido adaptar
sus contenidos para hacerlo más cercano a los intereses de estudiantes de especialidades más
diversas, tales como Ingenierı́a Civil Eléctrica, de Minas o Biotecnologı́a. Es ası́ como se
reorientió el primer capı́tulo, destinado al análisis de las funciones y conjuntos convexos, a
los conceptos de poliedros y sus propiedades, de uso intensivo en la teorı́a de la Programa-
ción Lineal. Igualmente, se ha incorporado un capı́tulo sobre los problemas de flujos en redes,
particularmente los problemas de flujo de costo mı́nimo, flujo máximo, asignación y camino
más corto, de mucho interés para la formación de ingenieros.
La Programación no Lineal casi siempre se enseña de manera somera en las escuelas de
ingenierı́a, tanto por la supuesta complejidad de su tratamiento matemático y los conceptos
que usa, como por la dificultad de implementación de los algoritmos. Sin embargo cada
dı́a es más frecuente encontrar, en la práctica profesional y en la investigación, problemas
reales de optimización con componentes no lineales. Por una parte, la linearización de estos
componentes puede permitir su solución mediante el uso reiterado de la Programación Lineal,
aunque no siempre se alcanza buenas aproximaciones a la solución y, por otra, la resolución
directa por métodos de Programación no Lineal es a menudo muy costosa o ineficiente.
No se trata esta de una obra completamente original, sino más bien corresponde a un com-
pendio de materias ampliamente conocidas que hemos sistematizado para dar cuerpo a un
texto de estudio a nivel unversitario. Recientemente, hemos incorporado una larga lista de
problemas propuestos, los cuales permiten ilustar y practicar los conceptos y materias tra-
tadas en los capı́tulos fundamentales. Estos problemas propuestos son también herencia de
varios años de pruebas y exámenes, algunos muy conocidos en la literatura y otros producto
de nuestra invención.
Finalmente debo decir que este trabajo, que está en permanente evolución, se ha enriqueci-
do con la colaboración de mis profesores auxiliares y ayudantes, ası́ como por la constante
interpelación de los estudiantes. A todos ellos les agradezco su contribución constante con
que me alimentan clase a clase.
Jorge Amaya
jorge.amaya@cmm.uchile.cl
Octubre de 2018
Índice general
1. El Problema de Optimización 5
3. Caracterización de Optimalidad 50
3.1. Definición del Problema de Optimización . . . . . . . . . . . . . . . . . . . . 50
3.2. Condiciones de Optimalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2.1. Optimización sin restricciones . . . . . . . . . . . . . . . . . . . . . . 51
3.2.2. Optimización con restricciones . . . . . . . . . . . . . . . . . . . . . . 53
4. Programación Lineal 61
4.1. Introducción y Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2. Resolución de Problemas de Programación Lineal: Algoritmo Simplex . . . . 63
2
4.2.1. Fase II del algoritmo Simplex: mejorar solución en curso . . . . . . . 65
4.2.2. Fase I del algoritmo Simplex: obtener una solución inicial básica factible 72
4.3. Introducción a la Programación Lineal Entera . . . . . . . . . . . . . . . . . 76
4.3.1. Método de Ramificación y Acotamiento . . . . . . . . . . . . . . . . . 76
4.3.2. Técnicas básicas de modelamiento con variables enteras . . . . . . . . 81
3
7. Algoritmos para Programación no Lineal 127
7.1. Optimización sin Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.1.1. Método del gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.1.2. Caso cuadrático . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.1.3. Método de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.1.4. Método de paso (minimización unidimensional) . . . . . . . . . . . . 137
7.2. Optimización con Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.2.1. Método del gradiente proyectado . . . . . . . . . . . . . . . . . . . . 140
7.2.2. Método de direcciones admisibles . . . . . . . . . . . . . . . . . . . . 145
7.2.3. Método de penalización . . . . . . . . . . . . . . . . . . . . . . . . . 148
4
Capı́tulo 1
El Problema de Optimización
f (x̄) ≤ f (x) ∀x ∈ S,
5
Dependiendo de las caracterı́sticas particulares del problema, éste recibe nombres y tra-
tamientos especiales para su resolución. Dos casos de interés, son el de la programación
lineal (f y gi son funciones lineales afines ∀i) y la programación lineal entera (en que
además las variables sólo toman valores enteros). También trataremos la teorı́a y técnicas de
solución de un problema con funciones no lineales.
Un concepto esencial para entender cómo plantear y resolver un problema de optimización
es el de convexidad. Mostrar algo de la teorı́a básica del análisis convexo y su vinculación
con la teorı́a de optimización son los objetivos del siguiente capı́tulo.
6
Capı́tulo 2
a) b)
y
y x
x
1
Por convención, el conjunto vacı́o será considerado convexo
7
Ejemplo 2.1.1 Un espacio vectorial es un conjunto convexo (en particular, IRn lo es).
Demostración. Directo pues, por definición, un espacio vectorial es cerrado para la suma
y la ponderación por escalar.
Demostración. Sean x, y ∈ S, λ ∈ [0, 1]. Por definición del conjunto S, esto significa que
x1 + 2x2 − x3 = 2 e y1 + 2y2 − y3 = 2.
λx1 + (1 − λ)y1
Vemos que λx + (1 − λ)y = λx2 + (1 − λ)y2 pertenece a S, pues
λx3 + (1 − λ)y3
H = {x ∈ IRn /aT x = α}
H − = {x ∈ IRn /aT x ≤ α}
H + = {x ∈ IRn /aT x ≥ α}
Por ejemplo, en el caso H = {x ∈ IR3 /x1 + 2x2 − x3 = 2} se tiene que aT = (1, 2, −1) y
α = 2. Los dos semiespacios asociados son:
8
x3 -
H
x2
1
+
2 H
x1
-2
x, y ∈ S1 ⇒ λx + (1 − λ)y ∈ S1
9
y
x, y ∈ S2 ⇒ λx + (1 − λ)y ∈ S2 ,
puesto que S1 y S2 son convexos.
∑
k
Definición 2.1.3 Sean x1 , . . . , xk ∈ IRn , λ1 , . . . , λk ∈ IR+ tales que λi = 1. El vector
i=1
∑
k
x= λi xi se dice combinación convexa de los k vectores x1 , . . . , xk .
i=1
10
Definición 2.1.4 Sea S ⊆ IRn (no necesariamente convexo). Se define la envoltura con-
vexa de S, de la manera siguiente:
∑
k ∑
k
co(S) = { λi xi / k ∈ IN, x1 , . . . , xk ∈ S, λ1 , . . . , λk ∈ IR+ , λi = 1}.
i=1 i=1
S ⊆ co(S).
a) b)
y
y x
Figura 2.3: La envoltura convexa del conjunto de la figura a) coincide con él, por ser convexo. Para el
conjunto de la figura b), la lı́nea sólida delimita su envoltura convexa.
11
3
−1
7
6 6
5 5
4
4 3
3 2
1
2 0
Figura 2.4: La envoltura convexa del conjunto de puntos señalados queda determinada por un poliedro
cuyos vértices están dados por un subconjunto del conjunto de puntos.
∑
k ∑
m
x= νi xi , y = µ i yi
i=1 i=1
∑
k+m
zi ∈ S, αi ∈ [0, 1], ∀i = 1, . . . , k + m y αi = 1.
i=1
12
Luego por definición se tiene que λx + (1 − λ)y ∈ co(S), por lo tanto co(S) es convexo.
Proposición 2.1.3 El conjunto co(S) es ∩ el convexo más pequeño (en el sentido de la inclu-
sión) que contiene a S, es decir, co(S) = {C ⊆ IRn / C convexo, S ⊆ C}.
∩
Demostración. Sea x ∈ {C ⊆ IRn / C convexo, S ⊆ C}. Entonces x ∈ C, ∀C convexo,
tal que S ⊆ C. Luego x ∈ co(S), que es un convexo particular que contiene a S.
S1 + S2 = {x + y / x ∈ S1 , y ∈ S2 }
αS1 = {αx / x ∈ S1 }
13
donde I la matriz identidad en dimensión n.
A b
Llamando A′ = −A , b′ = −b , se obtiene un sistema de la forma
−I 0
P = {x ∈ IRn /A′ x ≤ b′ },
que es igual a P ′ . Luego, P ′ es un poliedro.
Observación 2.1.3 Es obvio que P ′ ={x ∈ IRn /Ax ≥ b} es un poliedro. En efecto: como
x∈ IRn es irrestricto, basta multiplicar el sistema de desigualdades por -1, y definir A′ =-A,
b′ =-b.
Como x̄ ∈ P̄, existe una sucesión {xk } en P tal que lı́m xk = x̄.
k→∞
14
Ejemplo 2.1.7 C = {x ∈ IR2 / − x1 + x2 ≤ 2, x1 + x2 ≥ 4, x2 ≤ 4, x1 ≥ 0, x2 ≥ 0}.
Matricialmente esto puede escribirse de la siguiente manera:
−1 1 2
−1 −1 ( ) −4
x1
0
1 x2 ≤ 4
−1 0 0
0 −1 0
4 (2,4)
(1,3)
C
2
(4,0)
4 x
15
Ejemplo 2.1.8 Veamos algunos casos de conjuntos convexos y sus puntos extremos.
a) Sea S=B(0,1), la bola unitaria en IRn . El conjunto de puntos extremos queda represen-
tado por {x ∈ IRn / ∥x∥ = 1}, que es la frontera de S.
16
y
(-2,4)
* _ _
y<=-1x+10
3 3
(1,3)
*
(0,2)
y>=-2x x<=1
*
*
(1,1)
y>=x
*
(0,0) x
x1 + x2 + x3 = 2
8x1 + 3x2 + x4 = 8
x1 , x2 , x3 , x4 ≥ 0
17
X2
8 /3
X1
1 2
Asignando valor nulo a dos variables cualesquiera podemos entonces resolver el sistema de
dos ecuaciones cada vez. Esto da las soluciones
0 0 0 2 1 2/5
0 2 8/3 0 0 8/5
, , , , .
2 0 −2/3 , 0 1 0
8 2 0 −8 0 0
Se observa que dos de ellas (la tercera y la cuarta) no satisfacen la condición de positividad,
luego no pertenecen a P ′ . Sin embargo las cuatro soluciones restantes determinan, en sus
dos primeras coordenadas, los puntos extremos de P:
( ) ( ) ( ) ( )
0 0 1 2/5
, , , .
0 2 0 8/5
18
descomponer, eventualmente reordenando sus columnas, en la forma A = [B, N ], donde
B ∈(Mm×m (IR)
) es invertible, N ∈ Mm×(n−m) (IR) corresponde a las columnas restantes y
−1
B b
x= , con B −1 b ≥ 0.
0
Demostración.( −1 )
B b
(⇐=) Sea x = ≥ 0. Se tiene que x ∈ P, pues
0
( −1 )
B b
Ax = [B, N ] = BB −1 b + N 0 = b.
0
Sean u, v ∈ P tales que x = λu + (1 − λ)v, para algún λ ∈]0, 1[, es decir
( ) ( ) ( )
B −1 b u1 v1
=λ + (1 − λ)
0 u2 v2
De allı́:
(1) λu1 + (1 − λ)v1 = B −1 b
(2) λu2 + (1 − λ)v2 = 0
De la misma manera se prueba que v = x, con lo que se concluye que x es punto extre-
mo.
19
Notemos A = [A1 , . . . , An ], donde Ai , i = 1, . . . , n, es la i-ésima columna de A. Luego,
∑ k
como Ax = b, se tiene que xi Ai = b.
i=1
20
de donde xB = B −1 b.
Ejemplo 2.1.9 Consideremos un poliedro en la forma canónica dado por las matrices
[ ] [ ]
2 1 0 −1 1
A= y b= .
0 0 −1 2 1
Calculemos sus puntos extremos. De acuerdo al corolario anterior, existen a lo sumo 6 puntos
extremos dado que hay 6 formas posibles de elegir la matriz B.
[ ]
2 1
(1) B = no es invertible.
0 0
[ ] ( )
2 0 −1 1/2
(2) B = es invertible, pero B b = no es un vector positivo.
0 −1 −1
[ ] ( )
2 −1 −1 3/4
(3) B= es invertible y el vector B b = tiene todas sus coodenadas
0 2 1/2
positivas.
[ ] ( )
1 0 1
(4) B= es invertible, pero B −1 b = no es un vector positivo.
0 −1 −1
[ ] ( )
1 −1 3/2
(5) B= es invertible y el vector B −1 b = tiene todas sus coodenadas
0 2 1/2
positivas.
[ ] ( )
0 −1 −1 −3
(6) B= es invertible, pero B b = no es un vector positivo.
−1 2 −1
Los casos (3) y (5) nos entregan puntos extremos para el poliedro en estudio, sólo falta ubicar
los valores resultantes en las posiciones correctas:
21
La matriz del caso (3) toma las columnas
primera
y cuarta de la matriz A, luego el
3
4
0
vector punto extremo correspondiente será
0 .
1
2
De acuerdo con esta definición, puede concluirse fácilmente que todo polı́topo es envoltura
convexa de sus puntos extremos. Es obvio, además, que todo polı́topo es un poliedro. Luego,
parece natural preguntarse si todo poliedro puede escribirse como combinación convexa de
sus puntos extremos. La respuesta es negativa, cuando el poliedro es no acotado. En el
Ejemplo 2.1.7 observamos que los( puntos
) ( del)poliedro
( )que no están en la superficie del
1 2 4
triángulo definido por los puntos , y , no pueden ser expresados como
3 4 0
combinación convexa de esos tres puntos extremos.
x2 ≥ |x1 | ⇐⇒ x2 ≥ x1 ≥ −x2 , x2 ≥ 0,
se tiene
S = {x ∈ IR2 / x1 − x2 ≤ 0, −x1 − x2 ≤ 0, x2 ≥ 0}
Como es posible ver en la Figura 2.8, el origen es el único punto extremo y ningún punto
del poliedro S puede expresarse como combinación convexa de sus puntos extremos. Luego,
para poliedros no acotados introduciremos un nuevo concepto, en la subsección siguiente.
22
d1 d2
Figura 2.8: El origen es el único punto extremo del poliedro de la figura y d1 , d2 son sus únicas
direcciones extremas.
Definición 2.1.9 Dos direcciones d1 y d2 se dirán iguales si d1 = αd2 para algún α > 0.
Se escribirá d1 = d2 , si no hay posible confusión.
Definición 2.1.10 Sea S un convexo cerrado y d ∈ IRn una dirección de S. Se dice que d
es dirección extrema si, dadas d1 y d2 , direcciones de S, tales que d = αd1 + βd2 para
algún α, β > 0, entonces se tiene que d = d1 = d2 .
23
Es decir, d no puede expresarse como combinación lineal positiva (estricta) de dos direcciones
distintas.
Ejemplo 2.1.11 En la Figura 2.8, d1 y d2 son direcciones extremas y toda otra dirección
se escribe como combinación lineal positiva de ellas.
Con lo que hemos hecho hasta aquı́, una pregunta interesante es: ¿existirá alguna caracteri-
zación de las direcciones extremas, equivalente a la obtenida para puntos extremos?
para algunos η1 , η2 ≥ 0.
24
por lo tanto d1 = d2 = d (en el sentido de la igualdad de direcciones), lo que muestra que d
es dirección extrema. De paso, se observa que η1 , η2 ̸= 0 puesto que d1 y d2 son direcciones.
Teorema 2.1.2 Sea un poliedro P = {x ∈ IRn /Ax = b, x ≥ 0}, donde A ∈ Mm×n (IR) es
de rango m y b ∈ IRm . Una dirección d¯ ∈ IRn es dirección extrema de P si y sólo si la matriz
A se puede descomponer, eventualmente reordenando sus columnas, en la forma ( A = [B, ) N ],
−1
−B a
donde B ∈ Mm×m (IR) es invertible y d¯ es un múltiplo positivo de d = j
con
ej
B −1 aj ≤ 0, donde aj ∈ N (es un vector columna de N ) y ej es el j-ésimo vector de la base
canónica de IRn−m .
Para concluir esta sección, enunciaremos, sin demostrar, un teorema de caracterización que
liga todo lo que hemos desarrollado en esta sección.
25
Teorema 2.1.3 Sea P = {x ∈ IRn /Ax = b, x ≥ 0}, donde A ∈ Mm×n (IR) es de rango m
y b ∈ IRn . Sean x1 , . . . , xk los puntos extremos y d1 , . . . , dl las direcciones extremas de P.
Entonces, x ∈ P si y sólo si puede ser escrito como la suma de una combinación convexa de
los puntos extremos y una combinación lineal positiva de las direcciones extremas, es decir,
∑
k ∑
l
x= λi xi + µj dj
i=1 j=1
∑
k
donde λi ≥ 0 ∀i = 1, . . . , k, λi = 1, µj ≥ 0, ∀j = 1, . . . , l.
i=1
Demostración.
(=⇒) Si P tiene una dirección d, entonces es no acotado puesto que dado x ∈ P se tiene que
x + λd ∈ P, ∀λ ≥ 0 y por lo tanto lı́m ∥x + λd∥ = ∞.
λ→∞
(⇐=) Supongamos que P es no acotado y que no posee direcciones. Entonces tampoco po-
seee direcciones extremas y, por el teorema anterior, todo punto x ∈ P puede escribirse de
∑k ∑
k
la forma x = λi xi , para algunos λi ≥ 0, i = 1, . . . , k, λi = 1.
i=1 i=1
Ejercicio 2.1.2 Sea S un convexo. Demuestre que x ∈ S es punto extremo si y sólo si S\{x}
es convexo.
26
2.1.4. Proyección sobre conjuntos convexos
Teorema 2.1.5 Sea S un conjunto convexo, cerrado, no vacı́o en IRn , y ∈ IRn , y ∈
/ S.
Entonces, existe un único x̄ ∈ S que minimiza la función
φy : S −→ IR
x 7−→ φy (x) = ∥y − x∥
Demostración.
Existencia: Sea γ = ı́nf{φy (x) / x ∈ S}. Existe una sucesión minimizante {xk }k∈IN ⊆ S tal
que
φy (xk ) → γ, k → ∞.
Usando la propiedad conocida como Ley del Paralelógramo,
para u = xk − y, v = xl − y, tenemos
Unicidad: Sea x̄¯ ∈ S, x̄¯ ̸= x̄, tal que φy (x̄¯) = γ. De manera análoga a la parte anterior,
se llega a ∥x̄ − x̄¯∥2 ≤ 2 ∥x̄ − y∥2 + 2 ∥x̄¯ − y∥2 − 4γ 2 , que es igual a cero, luego x̄ = x̄¯.
Observación 2.1.4 El teorema anterior es válido para la norma euclideana, pero si se usa
otra norma, entonces es posible que la proyección no quede bien definida al no haber unicidad.
En lo que sigue, salvo indicación expresa en contrario, siempre entenderemos que se usa la
norma euclideana.
27
i) Para y ∈ IRn , se define la distancia de y a S, por d(y, S) = mı́n{φy (x) / x ∈ S}.
*
y
d(y,S)
P (y) _
S x S
Observación 2.1.5 La notación arg mı́n se lee como ”el argumento que minimiza”. Clara-
mente, si y ∈ S se tiene que d(y, S) = 0 y PS (y) = y.
Observación 2.1.6 De aquı́ en adelante usaremos la notación ⟨u, v⟩ para el producto in-
terno habitual en IRn pero, como interpretamos los vectores de IRn como columnas, es equi-
valente escribir uT v.
⟨y − x̄, x − x̄⟩ ≤ 0, ∀x ∈ S
28
Demostración. Supongamos que para cierto x̄ ∈ IRn se tiene ⟨y − x̄, x − x̄⟩ ≤ 0, ∀x ∈ S.
Entonces
∥y − x∥2 = ∥y − x̄ − (x − x̄)∥2
= ∥y − x̄∥2 + ∥x − x̄∥2 − 2⟨y − x̄, x − x̄⟩
≥ ∥y − x̄∥2 + ∥x − x̄∥2
≥ ∥y − x̄∥2
Esto implica que ∥y − x̄∥ ≤ ∥y − x∥, ∀x ∈ S. Es decir φy (x̄) ≤ φy (x), ∀x ∈ S.
de donde
29
y
S _
x
pT y > α
pT x ≤ α, ∀x ∈ S.
H={z/p t z= α }
30
Sean p = y − x̄ ̸= 0 y α = ⟨p, x̄⟩. Tenemos que
⟨p, x − x̄⟩ ≤ 0 ∀x ∈ S
por lo tanto
⟨p, x⟩ ≤ ⟨p, x̄⟩ = α ∀x ∈ S (2.1)
Por otro lado
a) b)
ω
S
S ω
H2
H1
H3
Figura 2.12: Para la figura a), H1 y H2 son dos hiperplanos soportantes en el punto señalado.
Cuando definimos los poliedros, los caracterizamos como una intersección finita de semiespa-
cios. El siguiente teorema nos permitirá deducir una caracterización similar para un conjunto
convexo no vacı́o cualquiera.
31
Teorema 2.1.9 Sea S ⊆ IRn un conjunto convexo y sea x̄ un punto en la frontera de S.
Entonces S tiene un hiperplano soportante en x̄.
Demostración. Basta tomar los semiespacios generados por todos los hiperplanos sopor-
tantes del convexo, que contengan a S.
Teorema 2.1.10 (Farkas) Sea A ∈ Mm×n (IR), c ∈ IRn . Uno y sólo uno de los siguientes
sistemas tiene solución:
(1) Ax ≤ 0, cT x > 0
(2) AT y = c, y ≥ 0
Demostración. Supongamos que (2) tiene solución, es decir, que existe y ≥ 0 tal que
AT y = c.
Supongamos ahora que (2) no tiene solución. Sea S = {z ∈ IRn /z = AT y, y ≥ 0}, que
es un convexo, cerrado y no vacı́o.
32
Supongamos queAp tiene una coordenada estrictamente positiva, digamos (Ap)1 , y con-
1
0
sideremos y = λ .. , λ > 0. Entonces λ(Ap)1 ≤ α ∀λ > 0, lo que es una contradicción,
.
0
pues se puede elegir λ suficientemente grande de modo de violar la desigualdad, dado que
(Ap)1 > 0. Luego, Ap no tiene coordenadas positivas, es decir,
Ap ≤ 0 (2.4)
Ejercicio 2.1.5 Sea A ∈ Mm×n (IR), c ∈ IRn . Uno y sólo uno de los siguientes sistemas
tiene solución:
(1) Ax ≤ 0, x ≥ 0, cT x > 0
(2) AT u ≥ c, u ≥ 0
[ ]
e= A
Basta considerar la matriz A y aplicar el teorema de Farkas.
−I
pT x1 ≥ pT x2 ∀x1 ∈ S1 , x2 ∈ S2 .
S = {x/x = x2 − x1 , x1 ∈ S1 , x2 ∈ S2 } = S2 − S1 .
Se deduce del Ejercicio (2.1.1) que S es un convexo. Además, es claro que 0 ∈ / S (en efecto,
0 ∈ S implicarı́a que S1 ∩ S2 ̸= ∅). Luego, usando el Teorema 2.1.8, existe p ̸= 0 tal que
pT x ≤ 0 ∀x ∈ S
33
S2
S1
Figura 2.13: En el caso de la figura, el hiperplano separador de los dos conjuntos convexos es soportante
para la clausura de ambos.
Teorema 2.1.12 (Gordan) Sea A ∈ Mm×n (IR). Entonces uno y sólo uno de los siguientes
sistemas tiene solución:
(1) Ax < 0
(2) AT p = 0, p ≥ 0, p ̸= 0
Demostración. Supongamos primero que (1) tiene solución, es decir, que existe x ∈ IRn tal
que Ax < 0. Demostraremos que (2) no tiene solución. Si no, existirı́a p ∈ IRn , p ≥ 0, p ̸= 0
tal que AT p = 0.
Entonces, premultiplicando (1) por pT se obtiene que pT Ax < 0, lo que contradice que
AT p = 0.
Supongamos ahora que (1) no tiene solución. Demostraremos que (2) posee solución. Si
no, definamos
34
S1 ∩ S2 = ∅
S1 ̸= ∅, S2 ̸= ∅
S1 y S2 convexos
Entonces, por teorema anterior (separación de dos convexos), existe un hiperplano separador;
es decir existe p ̸= 0 tal que
p T z1 ≥ p T z2 ∀z1 ∈ S1 , z2 ∈ S2
Luego,
pT Ax1 ≥ pT z2 ∀x1 ∈ IRn , z2 ∈ S2 (2.5)
lo cual implica que
pT Ax1 ≥ sup {pT z2 }.
z2 <0
Probaremos que p ≥ 0. Si p tiene alguna coordenada negativa, entonces el supremo del lado
derecho de esta desigualdad es igual a +∞. Se deduce entonces que pT Ax1 = +∞, ∀x1 ∈ IRn ,
lo que es una contradicción. Ası́, p ≥ 0.
Luego, tomando lı́mite z2 →
0− en
(2.5), se tiene que pT Ax1 ≥ 0, ∀x1 ∈ IRn . Eligien-
do x1 = −AT p, se tiene que
AT p
= 0 lo que implica AT p = 0. Esto demuestra que (2)
tiene solución.
Esta definición se puede interpretar geométricamente, diciendo que la imagen por f del
segmento [x, y] queda por debajo de la recta que une (x, f (x)) e (y, f (y)) (ver Figura 2.14).
Es posible probar la siguiente proposición, que induce una definición equivalente de conve-
xidad de funciones.
35
f(y)
f(x)
x y
Figura 2.14: Función convexa: imagen del segmento [x, y] queda por debajo de la recta que une los
puntos (x, f (x)) e (y, f (y)).
Definición 2.2.2 Una función f, definida sobre un convexo S, se dice estrictamente con-
vexa si para todo x, y ∈ S, x ̸= y, 0 < λ < 1, se tiene
Ejemplo 2.2.1 .
i) Para todo α ∈ IRn , β ∈ IR, la función f : IRn → IR definida por f (x) = αT x + β (lineal
afı́n) es cóncava y convexa.
ii) La función f definida por
x si x ∈] − ∞, 0]
f (x) = 0 si x ∈]0, 1[
x si x ∈ [1, ∞[
(lineal por pedazos) no es convexa ni cóncava.
36
iii) La función f (x) = −x2 es estrictamente cóncava.
iv) La función {
x2 si x ∈] − ∞, 2]
f (x) =
4 si x ∈]2, ∞[
no es convexa ni cóncava.
i) ii)
iii) iv)
37
Sea entonces ε > 0. Dado que x̄ ∈ int(S) existe η > 0 tal que la bola de centro x̄ y ra-
dio η está incluida en S, es decir, B(x̄, η) ⊆ S.
1 ε
αi ≤ mı́n{ , } ∀i = 1, . . . , n.
n nK
38
Entonces,
∑
n ∑n
1
f (x) = f (x − x̄ + x̄) = f ( αi di + x̄) = f ( (nαi di + x̄))
i=1 i=1
n
∑n
1 1∑
n
≤ f (nαi di + x̄) = f [(1 − nαi )x̄ + nαi (x̄ + di )]
i=1
n n i=1
1∑
n
≤ [(1 − nαi )f (x̄) + nαi f (x̄ + di )]
n i=1
∑
n
= f (x̄) + αi [f (x̄ + di ) − f (x̄)]
i=1
∑
n ∑
n
f (x) − f (x̄) ≤ αi [f (x̄ + di ) − f (x̄)] ≤ K αi ≤ ε
i=1 i=1
1 1 1
[f (x̄) − f (x)] ≤ [f (y) − f (x̄)] ≤ ε.
2 2 2
Una función convexa podrı́a no ser continua en todo su dominio, sin embargo, el teorema
anterior dice que los puntos de discontinuidad se encuentran en la frontera, como muestra el
siguiente ejemplo.
{
x2 |x| < 1
Ejemplo 2.2.2 Sea S = {x/ |x| ≤ 1} y f : S → IR, definida por f (x) =
2 |x| = 1
La función f es convexa, continua en int (S) y los puntos de discontinuidad {−1, 1} están
en la frontera de S.
39
2.2.1. Conjuntos relevantes asociados a funciones convexas
Definición 2.2.4 Sea f : S ⊆ IRn −→ IR, con S ̸= ∅ un conjunto cualquiera. Para α ∈ IR
se definen los siguientes conjuntos (ver Figura 2.16)
epi(f)
α
N α f(x)=[x 1 ,x 2 ]
x1* *x2
Cα f(x)={x 1,x 2}
Figura 2.16: Conjunto de nivel, curva de nivel y epı́grafo de una función real f.
Teorema 2.2.2 Sea una función f : S ⊆ IRn −→ IR, con S convexo. Se tiene que
Demostración.
40
(i) Sea f convexa. Sean (x, α), (y, β) ∈ epi(f ), λ ∈ [0, 1]. Entonces, por convexidad
Sea ahora epi(f ) un conjunto convexo. Claramente se tiene que (x, f (x)), (y, f (y)) ∈ epi(f )
y, por lo tanto, para λ ∈ [0, 1] se tiene
Es decir,
(λx + (1 − λ)y, λf (x) + (1 − λ)f (y)) ∈ epi(f ),
de donde se concluye que f es convexa.
de donde λx + (1 − λ)y ∈ Nα (f ).
La recı́proca de (ii) no es cierta: para la función (iv) del Ejemplo 2.2.1, Nα (f ) es convexo
∀α ∈ IR, sin embargo la función no es convexa.
41
f (x̄ + λd) − f (x̄)
f ′ (x̄, d) = lı́m+ ∈ IR
¯
λ→0 λ
¯ = IR ∪ {−∞, +∞}.
donde IR
o (x − x̄)
donde lı́m = 0.
x→x̄ ∥x − x̄∥
implica
f (x̄ + λd) − f (x̄) o(λd)
= ∇f (x̄)T d + ∥d∥
λ ∥λd∥
Proposición 2.2.2 Sea f : S −→ IR, convexa. Sean x̄ ∈ S, y d ̸= 0 tales que existe η > 0
que cumple x̄ + λd ∈ S, para todo λ ∈ [0, η[. Entonces f ′ (x̄, d) existe.
42
implica
f (x̄ + λ1 d) − f (x̄) f (x̄ + λ2 d) − f (x̄)
≤
λ1 λ2
f (x̄ + λd) − f (x̄)
Ası́, la función φ(λ) = es monótona (no decreciente) y por lo tanto ı́nf φ(λ)
λ λ>0
existe (estamos en IR).¯
Pero ı́nf φ(λ) = lı́m+ φ(λ) = f ′ (x̄, d), luego la derivada direccional existe.
λ>0 λ→0
Demostración.
(⇒) Sea f convexa. Dados x, x̄ ∈ S se tiene que
que implica
f (x) ≥ f (x̄) + ∇f (x̄)T (x − x̄), ∀x̄, x ∈ S.
43
Multilplicando la primera desigualdad por λ, la segunda por (1 − λ) y sumando, se tiene
Es decir, f es convexa.
Observación 2.2.1 Es directo probar que f, satisfaciendo las hipótesis del teorema anterior,
es estrictamente convexa si y sólo si f (x) > f (x̄) + ∇f (x̄)T (x − x̄), ∀x, x̄ ∈ S, x ̸= x̄.
Definición 2.2.7 Sea S ⊆ IRn , no vacı́o. Una función f : S → IR se dice dos veces
diferenciable en x̄ si existe ∇f (x̄) ∈ IRn y H(x̄) ∈ Mn×n (IR) tal que
o (x − x̄)
donde → 0 si x → x̄
||x − x̄||2
44
∂ 2 f (x̄) ∂ 2 f (x̄) ∂ 2 f (x̄)
···
∂x21 ∂x1 ∂x2 ∂x1 ∂xn
.. .. 2
∂ f (x̄) ..
H (x̄) =
. . .
2 ∂xi ∂xj
∂ f (x̄) ∂ f (x̄)
2
··· ···
∂xn ∂x1 ∂x2n
Teorema 2.2.5 (Caracterización de convexidad para una función dos veces diferenciable)
Sea S ⊆ IRn un abierto, convexo, no vacı́o, y sea f : S → IR dos veces diferenciable en S.
Entonces f es convexa si y sólo si H (x) es semi-definida positiva ∀x ∈ S.
Demostración.
(⇒) Sea x̄ ∈ S. Queremos probar que ∀x ∈ IRn , xT H (x̄) x ≥ 0.
Además,
λ2 T
f (x̄ + λx) = f (x̄) + λ∇f (x̄)T x + x H (x̄) x + o (λx) , ∀x ∈ IRn
2
Restando las dos ecuaciones, se tiene que
λ2 T
0≥− x H (x̄) x − o (λx) ∀x ∈ IRn
2
de donde,
2
xT H (x̄) x + o (λx) ≥ 0 ∀x ∈ IRn .
λ2
Para x ̸= 0 (el caso x = 0 es directo), dividamos por ∥x∥2 y tomemos lı́mite cuando λ → 0+
para obtener que xT H (x̄) x ≥ 0 ∀x ∈ IRn , es decir, que H (x̄) es semi-definida positiva.
45
b = λx̄ + (1 − λ)x ∈ S, para algún λ ∈]0, 1[.
con x
( )
x1
Ejemplo 2.2.3 Sea f = −x21 − 5x22 + 2x1 x2 + 10x1 − 10x2 . Deseamos verificar si f
x2
es convexa, cóncava o ninguna de ellas.
Como ambos valores son negativos, H(x) es definida negativa. Luego, por el teorema ante-
rior, f es cóncava. Más aún, como lo demuestra el siguiente resultado, f es estrictamente
cóncava.
Corolario 2.2.2 Sea S ⊆ IRn un abierto, convexo, no vacı́o, y sea f : S → IR dos veces
diferenciable en S. Se tiene que,
46
(ii) si f es estrictamente convexa, entonces H(x) es semi-definida positiva en todo punto
de S.
Demostración.
(i) Análogamente a la segunda parte de la demostración del teorema anterior, de la igualdad
Hasta aquı́ hemos desarrollado caracterizaciones de convexidad que nos serán de mucha
utilidad, pero sólo para funciones diferenciables. Existe una forma sencilla de extender estas
caracterizaciones a funciones no diferenciables, mediante el concepto de subgradiente, que se
define a continuación.
47
Demostración. Sean ξ1 , ξ2 ∈ ∂f (x̄). Entonces por definición se tiene
Demostración. Notemos primero que ∇f (x̄) ∈ ∂f (x̄), pues f es convexa (Teorema 2.2.4).
Si ξ ∈ ∂f (x̄), entonces por definición f (x) ≥ f (x̄) + ξ t (x − x̄) , ∀x ∈ S.
Proposición 2.2.5 Sea S ⊆ IRn un convexo no vacı́o y f : S → IR. Si ∀x̄ ∈ int (S)
∃ξ ∈ IRn tal que
Demostración. Sean x1 , x2 ∈ int (S) , λ ∈ [0, 1]. Como S es convexo entonces int (S) es
convexo, luego x̄ = λx1 + (1 − λ) x2 ∈ int (S) y existe ξ ∈ IRn , tal que
48
En particular,
f (x1 ) ≥ f (x̄) + ξ t (x1 − x̄)
f (x2 ) ≥ f (x̄) + ξ t (x2 − x̄)
Pero x1 − x = (1 − λ) (x1 − x2 ) y x2 − x̄ = −λ (x1 − x2 ). Luego, multiplicando la primera
desigualdad por λ, la segunda por (1 − λ) y sumando, se tiene que
es decir, f es convexa.
49
Capı́tulo 3
Caracterización de Optimalidad
(P ) mı́n f (x)
x∈S
Con S ⊆ IRn , generalmente definido por ecuaciones no necesariamente lineales, que llamare-
mos región factible y f una función cualquiera. Ciertamente, si S es un poliedro y f es lineal
entonces se trata del caso de la Programación Lineal.
Definición 3.1.1 Un punto x∗ ∈ S se dirá mı́nimo local de f si existe ϵ > 0 que cumpla
f (x∗ ) ≤ f (x), ∀x ∈ S tal que ∥x∗ − x∥ < ϵ. Es decir, existe una vecindad de x∗ donde dicho
punto es mı́nimo.
Teorema 3.1.1 Sea f : S → IR, con S convexo no vacı́o, y sea x̄ una solución local del
problema (P ). Entonces,
50
(i) Si f es convexa, x̄ es mı́nimo global.
Demostración.
(i) Sea ε > 0 tal que f (x̄) ≤ f (x), ∀x ∈ Vε (x̄) = {x ∈ S / ||x̄ − x|| < ε} y supongamos que
x̄ no es óptimo global.
Es decir, existe y ∈ S tal que f (y) < f (x̄). Luego, para λ ∈]0, 1[,
(ii) Como f estrictamente convexa entonces f es convexa. Luego, por (i), x̄ es mı́nimo global.
Supongamos que no es único, esto es, que existe y ∈ S, con y ̸= x̄, tal que f (y) = f (x̄).
Entonces
1 1 1 1
f ( y + x̄) < f (y) + f (x̄) = f (x̄)
2 2 2 2
lo que implica que existe z ∈ S, z = 2 y + 2 x̄, distinto de x̄, tal que f (z) < f (x̄). Esto
1 1
(P ) mı́n f (x)
x ∈ IRn
En general supondremos que f es una función una o dos veces continuamente diferenciable.
51
Teorema 3.2.1 (Condiciones necesarias de optimalidad) Sea x∗ solución local de (P)
y supongamos f ∈ C 2 (S), donde S es un conjunto abierto que contiene a x∗ . Entonces,
a) ∇f (x∗ ) = 0 y
b) La matriz Hessiana H(x∗ ) es semidefinida positiva.
Demostración. Sea d ∈ IRn , no nulo dado y consideremos la función g(α) = f (x∗ + αd).
Es decir,
f (x∗ + αd) − f (x∗ )
0≤ .
α
Tomando lı́mite,
Ahora, por la regla de la cadena se tiene que g ′ (α) = ∇f (x∗ + αd)T d, lo que implica que
g ′ (0) = ∇f (x∗ )T d, por lo tanto
0 ≤ ∇f (x∗ )T d.
1
g(α) = g(0) + g ′ (0)α + g ′′ (0)α2 + o(α2 ),
2
o(t)
donde la función o(t) cumple lı́m = 0.
t→0 t
Considerando que g ′ (α) = ∇(x∗ + αd)T d y g ′′ (α) = dT H(x∗ + αd)d, la expresión an-
terior se escribe
α2 T
f (x∗ + αd) − f (x∗ ) = α∇f (x∗ )T d + d H(x∗ )d + o(α2 ),
2
52
por lo tanto, como ∇f (x∗ ) = 0 y f (x∗ + αd) − f (x∗ ) ≥ 0, para α > 0 suficientemente
pequeño, se tiene que
o(α2 )
0 ≤ dT H(x∗ )d +
α2
∗
Tomando α → 0 se obtiene que H(x ) es semidefinida positiva.
En relación a las condiciones suficientes, se puede fácilmente probar los siguientes teoremas,
para el caso de funciones convexas (las demostraciones quedan como ejercicio de cálculo).
Teorema 3.2.2 Sea f una función convexa y diferenciable sobre un conjunto convexo S,
abierto. Entonces ∇f (x∗ ) = 0 es una condición necesaria y suficiente para que x∗ ∈ S sea
un mı́nimo global de f sobre S.
a) ∇f (x∗ ) = 0.
b) La matriz H(x∗ ) es definida positiva.
Definición 3.2.1 Sea f : IRn → IR. Se dice que d ∈ IRn es dirección de descenso de f
en x̄ si ∇f (x̄)T d < 0.
53
Teorema 3.2.4 Sea f : IRn → IR diferenciable en x̄ ∈ S. Si x̄ es mı́nimo local del problema
(P ) mı́n f (x)
x∈S
entonces, A ∩ D = ∅.
d ∈ D =⇒ existe ε > 0 tal que f (x̄ + λd) < f (x̄), λ ∈ [0, ε[.
Luego f (x̄ + λd) < f (x̄), para todo λ ∈]0, mı́n{ε, η}[, lo que contradice la minimalidad
local de x̄.
Muy frecuentemente el conjunto factible S está descrito mediante una sistema de inecuacio-
nes, que denominaremos restricciones. Sean g1 , . . . , gm , funciones de IRn en IR, diferencia-
bles. Consideremos también el conjunto
que es un convexo cuando las funciones g1 , . . . , gm son convexas en IRn (dejamos al lector
la tarea de probar esta afirmación y encontrar un contraejemplo para la afirmación recı́proca).
(P ) mı́n f (x)
gi (x) ≤ 0 i = 1, . . . , m
Definición 3.2.3 Sea x̄ ∈ IRn . Si una restricción gi verifica gi (x̄) = 0 entonces se dice que
es activa en x̄. Además, I = {i / gi (x̄) = 0} denota el conjunto de ı́ndices de las restricciones
activas en x̄.
Sea ahora el conjunto G(x̄) = {d / ∇gi (x̄)T d < 0, ∀i ∈ I}, el cual denotaremos simplemente
por G.
54
Demostración. Basta probar que G ⊆ A y luego concluir usando el teorema anterior.
Sea d ∈ G y consideremos el caso i ∈ I. Entonces ∇gi (x̄)T d < 0, luego existe ηi > 0 tal
que
gi (x̄ + λd) < gi (x̄) λ ∈]0, ηi [.
Notar que el lado derecho de esta última desigualdad es nulo, entonces se tiene que
gi (x̄ + λd) < 0 λ ∈]0, η[,
para η = mı́n{ηj }.
j∈I
Tomemos ahora i ∈ / I. Como x̄ es factible, entonces cumple gi (x̄) < 0. De allı́, por con-
tinuidad, se deduce que existe εi > 0 tal que gi (x̄ + λd) < 0 λ ∈ [0, εi [.
∇f (x̄)T d < 0
∇gi (x̄)T d < 0 i ∈ I
Definiendo
∇f (x̄)T
..
.
A= T
∇gi (x̄)
..
. i∈I
55
podemos interpretar lo anterior como: no existe d ∈ IRn tal que Ad < 0. Entonces, por el
teorema de Gordan, existe p ̸= 0 tal que
AT p = 0
p ≥0
Notemos
µ0
..
.
p=
µi
..
. i∈I
entonces,
∑
µ0 ∇f (x̄) + µi ∇gi (x̄) = 0
i∈I
∑
m
∇f (x̄) + µi ∇gi (x̄) = 0
i=1
µi gi (x̄) = 0 i = 1, . . . , m
µi ≥ 0 i = 1, . . . , m,
56
lo que completa la demostración.
Ejemplo 3.2.1 Veremos aquı́ cuán importantes son las hipótesis del teorema anterior.
( ) El
1
siguiente es un problema clásico, que tiene como solución óptima el punto x∗ = .
0
(P ) mı́n −x1
−(1 − x1 )3 + x2 ≤ 0
−x2 ≤0
70
60
50
40
30
20
10
−10
−3 −2 −1 0 1 2 3
Como puede verse en la Figura (3.1), la versión del teorema de Karusch-Kuhn-Tucker (KKT)
no es aplicable en este caso, pues los gradientes de g1 y g2 no son linealmente independientes
en x∗ . En efecto,
( ) ( )
∗ 3(1 − x∗1 )2 0
∇g1 (x ) = =
1 1
( )
0
∇g2 (x∗ ) =
−1
( )
∗ −1
∇f (x ) = .
0
( ) ( ) ( ) ( )
−1 0 0 0
Se observa que no existen µ1 , µ2 ≥ 0 que satisfagan + µ1 + µ2 = .
0 1 −1 0
57
Interpretación geométrica del teorema de Karush-Kuhn-Tucker
_
cono de direcciones - f(x)
admisibles _
x
g2 _
g1 (x)
Bajo la hipótesis de independencia lineal de los gradientes de las restricciones activas, para
que x̄ sea un mı́nimo local, se necesita que el vector −∇f (x̄) forme un ángulo obtuso con
toda dirección admisible d, lo que equivale a decir que −∇f (x̄) debe ser combinación lineal
positiva de los vectores del conjunto {∇gi (x̄), ∀i ∈ I}.
Sean x̄ un punto factible. Supongamos que el conjunto {∇gi (x̄), ∇hj (x̄), i ∈ I, j = 1, . . . , l}
es linealmente independiente.
58
Entonces, si x̄ es solución de (P), existen µi ∈ IR, i = 1, . . . , m, νj ∈ IR, j = 1, . . . , l
tales que
∑
m ∑
l
∇f (x̄) + µi ∇gi (x̄) + νj ∇hj (x̄) = 0
i=1 j=1
µi gi (x̄) = 0 i = 1, . . . , m
µi ≥ 0 i = 1, . . . , m
Ejemplo 3.2.2 Una aplicación interesante de esta versión del teorema de KKT es el caso
de la programación lineal, que es el tema del próximo capı́tulo. Consideremos el problema
(P ) mı́n cT x
Ax = b
x ≥0
donde la matriz A ∈ Mm×n (IR) y los vectores c ∈ IRn , b ∈ IRm son los datos del problema.
Se puede escribir equivalentemente,
(P ) mı́n cT x
−x ≤ 0
Ax − b = 0
de manera que las funciones f , gi y hj del problema general están dadas por
f (x) = cT x
gi (x) = −xi
∑n
hj (x) = ajk xk − bj
k=1
59
∑
n ∑
m
c+ ui (−ei ) + vj (aj1 , . . . , ajn )T = 0
i=1 j=1
ui (−xi ) = 0 i = 1, . . . , n
ui ≥ 0 i = 1, . . . , n
AT y + u = c
uT x = 0
u≥0
Ax = b
AT y + u = c
uT x = 0
x, u ≥ 0
Este es un sistema difı́cil de resolver, dado que algunas variables deben ser positivas y además
deben satisfacer una ecuación no lineal (ortogonalidad de x y u). Más adelante, en el capı́tulo
sobre la dualidad en Programación Lineal, daremos otra interpretación de este sistema.
60
Capı́tulo 4
Programación Lineal
(P L) mı́n cT x
Ax = b
x ≥0
61
Observación 4.1.1 Se cumple:
Si P es acotado, entonces existe solución, pues se minimiza una función (lineal) con-
tinua sobre un conjunto compacto (el poliedro P es cerrado).
1) Forma de desigualdad:
máx cT x
Ax ≤b
2) Forma estándar o canónica:
mı́n cT x
Ax = b
x ≥0
Estas dos formas son equivalentes pues los poliedros {x/Ax = b, x ≥ 0} y {x/Ax ≤ b} son
equivalentes, en el sentido que se puede pasar de una forma a otra mediante cambios simples
en las variables y restricciones, como por ejemplo:
62
∑
n ∑
n
aij xj ≤ bj puede escribirse en la forma aij xj + xn+1 = bj ,
j=1 j=1
con xn+1 ≥ 0. Notar que en este caso el problema aumenta en una variable por cada
restricción de desigualdad convertida en igualdad.
Una variable irrestricta x puede ser reemplazada por dos variables no negativas x1 ≥ 0
y x2 ≥ 0, escribiendo x = x1 − x2
Maximizar cT x es equivalente a minimizar −cT x
máx c1 x1 + c2 x2
x1 − 3x2 ≥ 8
x1 ≥ 0
− mı́n −c1 x1 − c2 u+ c2 v
−x1 + 3u− 3v ≤ −8
x1 , u, v ≥ 0
− mı́n −c1 x1 − c2 u + c2 v
−x1 + 3u − 3v +y = −8
x1 , u, v, y ≥ 0
63
(i) (P) es no acotado.
Demostración. Supongamos que existe una dirección extrema d tal que cT d < 0. Entonces,
dado que el poliedro es no vacı́o, elijamos x0 ∈ P. Es evidente que x0 + αd ∈ P y que
cT (x0 + αd) −→ −∞, si α −→ ∞. Entonces (P ) es no acotado, lo que prueba (i).
∑
k ∑
l
x0 = λi xi + µj dj
i=1 j=1
∑
k
donde λi ∈ [0, 1], ∀i = 1, . . . , k y λi = 1, µj ≥ 0, ∀j = 1, . . . , l.
i=1
Entonces,
∑
k ∑
l
T T
c x0 = λi c xi + µj cT dj
i=1 j=1
∑
l
Dado que µj cT dj ≥ 0 entonces
j=1
∑
k
cT x 0 ≥ λi cT xi
i=1
∑
k
cT x0 ≥ λi cT xq = cT xq
i=1
64
Motivación: solución gráfica en R2
Vimos que para poder resolver un problema de programación lineal necesitamos sólo con-
siderar los vértices del poliedro P = {x ∈ IRn /Ax = b, x ≥ 0} como candidatos a solución
óptima del problema. Para un número grande de variables
( )(n) y restricciones (m) vimos
n
también que el número de vértices puede ser enorme, , por lo que una metodologı́a
m
más sistemática se hace necesaria.
A la búsqueda de una base factible se la llama Fase I del algoritmo Simplex (esto se verá más
adelante). El resto del procedimiento (que describiremos a continuación) se conoce como Fa-
se II.
65
Consideremos el problema
(P ) mı́n cT x
x∈P
con P = {x ∈ IRn /Ax = b, x ≥ 0}.
Definición 4.2.1 Las coordenadas del vector xB se denominan variables básicas y las del
vector xN son las variables no básicas. Análogamente, a la matriz invertible B se le llama
base y si se cumple que B −1 b ≥ 0 entonces se dice base factible.
El problema (P ) es equivalente a
mı́n cTB xB + cTN xN
BxB + N xN = b
xN ≥ 0
xB ≥ 0
o bien, reemplazando xB en la función objetivo,
mı́n cTB B −1 b + (cTN − cTB B −1 N )xN
xB + B −1 N xN = B −1 b
xN ≥ 0
xB ≥ 0
Notemos que la función objetivo original
z(x) = cTB xB + cTN xN
coincide con la función
ẑ(xN ) = cTB B −1 b + (cTN − cTB B −1 N )xN ,
para x ∈ P. Entonces, minimizar z(x) ( es equivalente
) a minimizar ẑ(xN ) y se obtiene trivial-
−1
B b
mente que el punto extremo x̄ = es óptimo cuando cTN − cTB B −1 N ≥ 0, puesto
0
que
z(x̄) = cTB x̄B + cTN x̄N = cTB B −1 b ≤ cTB B −1 b + (cTN − cTB B −1 N )xN ,
para todo xN ≥ 0.
66
Definición 4.2.2 La cantidad π T = cTB B −1 es un vector fila que se conoce como vector de
multiplicadores del Simplex. Esta terminologı́a proviene de la interpretación de las coor-
denadas de π como multiplicadores de Lagrange. Daremos más adelante una interpretación
económica de estos multiplicadores.
Definición 4.2.3 El vector fila c̄TN = cTN − cTB B −1 N se denomina vector de costos reduci-
dos.
A continuación examinaremos por separado, con la ayuda de un ejemplo, los tres casos
que pueden aparecer cuando estamos en presencia de un punto extremo y a partir de esto
generaremos la formulación general del Algoritmo Simplex.
[ ] [ ] ( ) x 1 ( ) 0
1 −1 5 −1 xB x2 cB 0
Elijamos B = , N= , =
x3 , cN = 3 ,
0 1 −8 4 xN
x4 1
donde:
xB : variables básicas o en la base (x1 , x2 en este caso),
xN : variables no-básicas o fuera de la base (x3 , x4 en este caso).
67
( ) 6 ( −1 )
xB 4 B b
Como cTN − π T N = (3, 1) ≥ 0, la solución =
0 = es óptima.
xN 0
0
Criterio de optimalidad: en un problema de minimización escrito en la forma canónica,
si las variables no básicas
( ) tienen
( asociado
) un vector de costos reducidos c̄TN = cTN − π T N ≥ 0,
xB B −1 b
entonces la solución = es óptima.
xN 0
0 c̄TN −π T b
I B N B −1 b
−1
↓
x1 x2 x3 x4 −z
0 0 -3 1 0 = −π T b
1 0 -3 3 6
0 1 -8 4 4
( )T
Tal como en el ejemplo anterior, x = 6 4 0 0 es una solución factible; pero no es
óptima, pues c̄3 = −3 < 0.
¿Conviene hacer crecer una variable no básica a un valor positivo? Es claro que sı́; con-
viene que la variable x3 tome un valor positivo.
x1 = −3x4 + 6 + 3x3
x2 = −4x4 + 4 + 8x3
68
Tomando x4 = 0 (fuera de la base), x3 puede crecer indefinidamente, disminuyendo el valor
de la función objetivo, sin violar las restricciones, dado que las variables x1 y x2 se mantienen
positivas. Este problema es no acotado.
Escribamos la tabla:
↓
x1 x2 x3 x4 −z
0 0 3 -1 0
1 0 -3 3 6
0 1 -8 4 4
x1 = −3x4 + 6
x2 = −4x4 + 4
x3 = 0 (fuera de la base)
b̄i 6 4
Como x1 ≥ 0 y x2 ≥ 0, entonces se lleva x4 al valor x4 = mı́n{ / āi4 > 0} = mı́n { , } = 1.
āi4 3 4
69
↓s
x1 x2 x3 x4 −z
0 0 3 -1 0
1 0 -3 3 6
0 1 -8 4 4 →r
āis ārj
āij ← āij − para i ̸= r
ārs
70
ārj
ārj ←
ārs
āis b̄r
b̄i ← b̄i − para i ̸= r
ārs
b̄r
b̄r ←
ārs
c̄s ārj
c̄j ← c̄j −
ārs
c̄s b̄r
−z̄ ← −z̄ −
ārs
Observación 4.2.1 Notar que esto corresponde precisamente al pivoteo de Gauss para la
resolución de sistemas de ecuaciones lineales.
Escribamos la tabla:
↓s ↓s
x1 x2 x3 x4 −z x1 x2 x3 x4 −z
-1 -3 0 0 0 (pivoteando) -10 0 0 3 6
1 1 1 0 3 4 0 1 -1 1 →r
-3 1 0 1 2 →r -3 1 0 1 2
x1 x2 x3 x4 −z
0 0 5/2 1/2 17/2
1 0 1/4 -1/4 1/4
0 1 3/4 1/4 11/4
71
( )T
∗ 1 11
De este cuadro final identificamos x = 0 0 como la solución óptima, luego el
4 4
valor óptimo es z ∗ = −17/2
Definición 4.2.4 Si una o más variables básicas son nulas, entonces la solución se dice
degenerada. En caso contrario, la llamaremos no-degenerada.
El problema es conocer una solución básica factible para comenzar el algoritmo. Este pro-
blema, que corresponde a investigar la factibilidad de (P ), puede plantearse mediante el
siguiente problema auxiliar:
72
∑
(Pa ) mı́n xai
i
Ax + xa = b
x, xa ≥ 0
Notemos que x ∈ IRn y xa ∈ IRm . Bajo el supuesto razonable b ≥ 0, una solución básica
factible evidente para este problema es x = 0 y xa = b, luego podemos usar la Fase II del
algoritmo simplex para resolverlo.
T
El problema (Pa ) se resuelve considerando B = I (xa en la base), N = A, cB = 1I y
cN = 0T . Ası́, para este problema el cuadro inicial es:
donde 1I es el vector que tiene todas sus coordenadas iguales a 1, de manera que 1I T b =
b1 + . . . + bm . Las variables xai son llamadas variables artificiales y el propósito del problema
(Pa ) es llevarlas a tomar valores nulos. Esto es posible, siempre que el problema original ten-
ga una solución factible. En tal caso, el método Simplex terminará con una solución básica
factible, donde xai = 0 ∀i = 1, . . . , m.
73
Escribamos el problema en su forma canónica:
(P ) − mı́n x1 −2x2
x1 +x2 −x3 = 1
x1 +x4 = 4
x1 −x2 = 0
xi ≥ 0 i = 1, 2, 3, 4
Luego, agregando las variables artificiales x5 , x6 , x7 (son tres, dado el número de restricciones
del problema (P ), tenemos:
↓
−3 0 1 −1 0 0 0 −5
1 1 −1 0 1 0 0 1 x1 = ( 0 0 0 0 1 4 0 )T
1 0 0 1 0 1 0 4
1 −1 0 0 0 0 1 0 ←
Primera iteración:
↓
0 −3 1 −1 0 0 3 −5
0 2 −1 0 1 0 −1 1 ← x2 = ( 0 0 0 0 1 4 0 )T
0 1 0 1 0 1 −1 4
1 −1 0 0 0 0 1 0
Segunda iteración:
↓
0 0 −1/2 −1 3/2 0 3/2 −7/2
0 1 −1/2 0 1/2 0 −1/2 1/2 x3 = ( 1
2
1
2
0 0 0 7
2
0 )T
0 0 1/2 1 −1/2 1 −1/2 7/2 ←
1 0 −1/2 0 1/2 0 1/2 1/2
1
las negrillas señalan las variables en la base para cada iteración.
74
Tercera iteración:
0 0 0 0 1 1 1 0
0 1 −1/2 0 1/2 0 −1/2 1/2 1 1 7
x4 = ( 0 0 0 0 )T
0 0 1/2 1 −1/2 1 −1/2 7/2 2 2 2
En la última iteración todas las variables artificiales salen de la base, los costos reduci-
dos asociados toman todos el valor 1 y z = 0.
Ya tenemos una solución básica factible. Ahora eliminamos las variables artificiales y re-
calculamos los costos reducidos y el valor objetivo para esta solución:
0 1 −1/2 0 1/2
0 0 1/2 1 7/2
1 0 −1/2 0 1/2
( )T
El vector de costos está dado por c T = 1 −2 0 0 , por lo tanto:
( )T ( )T ( ) ( )
cTB = c2 c4 c1 = −2 0 1 , cTN = c3 = 0
El orden en que se escribe el costo para las variables básicas depende del vector en la base
canónica que las mismas tienen asociado.
75
−1
( ) 1 0 1 −1
c̄TN = cTN − −2 0 1 0 1 1 0 = − 12
−1 0 1 0
| {z }
( 1 ) T
−2 1
2
− 12 columna no básica del cuadro
En tanto que:
( 1/2 )
1
−π b = −2 0 1
T
7/2 =
2
1/2
↓
0 0 −1/2 0 1/2
0 1 −1/2 0 1/2
0 0 1/2 1 7/2 →
1 0 −1/2 0 1/2
0 0 0 1 4
0 1 0 1 4
0 0 1 2 7
1 0 0 1 4
( )
con lo cual xT = 4 4 7 0 es solución óptima para el problema, y el valor de la función
objetivo es −(−π T b) = 4 (recordemos que hicimos el cambio máx z = − mı́n{−z}).
76
(P ) mı́n 51x1 +90x2
x1 +x2 ≥ 6
5x1 +9x2 ≥ 45
x1 , x2 ∈ IN
La relajación corresponde a cambiar el conjunto IN por IR+ , pero en el caso de variables 0-1,
la relajación corresponderı́a a imponer restricciones del tipo xi ∈ [0, 1].
Dado que los costos son enteros, se puede deducir una cota de (P ): z ∗ ≥ 453.
Acotamos una de las variables (x1 ), que toma valor no entero, en la forma x1 ≤ 2 o bien
x1 ≥ 3. Eso divide la región factible en dos subregiones que conforman una partición de la
región factible de (P ). Se resuelve por separado los dos subproblemas ası́ generados:
Dado que (P11 ) tiene solución entera, representa una solución factible para el problema ori-
ginal (P ). Entonces ese problema ya no dará origen a subproblemas, pues no hay variables
77
para subdividir, y establece una cota para la función objetivo: z ∗ ≤ 462.
Análogamente, el problema (P12 ) tiene una solución no entera, de modo que su valor óptimo
es una cota inferior del valor óptimo del problema (P ) original, es decir, z ∗ ≥ 453.
∗
para (P21 ): (x1 , x2 ) = ( 18
5
, 3), z21 = 453, 6;
∗
para (P22 ): (x1 , x2 ) = (3, 4), z22 = 513.
El subproblema (Pk ) entrega una solución entera. Dado que la región factible de (Pk )
está contenida en la región factible del problema (P ), entonces la solución del subpro-
blema es factible para (P ) y por lo tanto provee una cota superior del valor óptimo z ∗
buscado.
El subproblema (Pk ) tiene solución no entera y su valor óptimo es mayor que la menor
cota superior de z ∗ establecida por los subproblemas precedentes que han entregado
soluciones enteras.
78
Para la aplicación de estas reglas hay que tener en cuenta que:
Cada vez que se encuentra un subproblema con solución entera, se genera una cota
superior de z ∗ .
Cada vez que se encuentra un subproblema con solución no entera, se puede ramificar
y se dispone de una nueva cota inferior de z ∗ .
Estos dos hechos permiten establecer una sucesión decreciente de intervalos que contienen
el valor z ∗ y que pueden ser usados como criterio de detención, cuando no se busca necesa-
riamente la solución óptima de (P ), sino que solamente una buena aproximación de ella.
En nuestro ejemplo, la rama a partir de (P22 ) debe detenerse por dos razones: tiene so-
lución entera y también el valor z22 = 513 es mayor que la mejor cota z ∗ ≤ 462.
Contrariamente, se puede ramificar de nuevo a partir del problema (P21 ), según la varia-
ble x1 , que toma el valor 18/5 en dicho problema. Siguiendo este proceso se llega finalmente
a la solución del problema original:
Este método, si bien es convergente, puede ser muy ineficiente del punto de vista del inmenso
número de subproblemas que puede ser necesario resolver para llegar a la solución. En el
ejemplo aquı́ presentado, de sólo dos variables, ha sido necesario ”bajar” hasta el noveno
nivel del árbol y resolver 17 subproblemas para encontrar la solución. Mucha investigación
79
se ha llevado a cabo con el fin de mejorar la eficiencia de este método básico y actualmente
se dispone de muy buenas estrategias de solución para problemas muy grandes (varios miles
o eventualmente millones de variables) de Programación Lineal Mixta (con variables enteras
y continuas).
Como último comentario, se puede observar que si se hubiese aproximado la solución del
primer problema relajado (P0 ) al entero más cercano, se habrı́a propuesto la solución aproxi-
mada
que está bastante lejos de la solución exacta encontrada mediante el método. Ese es un
peligro que se corre cuando se resuelve el problema relajado y luego se aproximan los valores
de las variables al entero más cercano. Eventualmente este tipo de soluciones aproximadas
puede ser infactible. Más abajo se muestra el diagrama de subproblemas que se genera en el
ejemplo.
80
P0
x1 шϯ
x1 чϮ njшϰϱϯ
x=(9/4, 15/4)
njчϰϲϮ͕ƐŽů͘entera njшϰϱϯ
P22
P21 x1 шϰ
njчϱϭϯ͕ƐŽů͘entera
x1 чϯ
njшϰϱϰ
x2 шϯ
P31 x2 чϮ P32
P42
infactible njшϰϱϰ
P41
x1 чϱ x1 шϲ njчϰϳϰ͕ƐŽů͘entera
njшϰϱϲ
P52 x2 шϮ
P51 x2 чϭ
njшϰϱϲ P62
infactible P61
x1 чϳ x1 шϴ njчϰϴϲ͕ƐŽů͘entera
njшϰϱϴ
P72 x2 шϭ
P71 x2 чϬ
P82
njшϰϱϴ
infactible P81
njчϰϵϴ͕ƐŽů͘entera
njчϰϱϵ͕ƐŽů͘entera óptima x=(9, 0)
81
Para fijar ideas, supondremos que la actividad i corresponde a la instalación (construcción)
de una planta de producción de cierto producto, el cual es producido en cantidades enteras.
Notemos mediante xi la cantidad producida en esa planta. Analizaremos varios casos muy
tı́picos para los cuales es necesario escribir las ecuaciones (restricciones) correspondientes.
que significa que a lo más p actividades del conjunto pueden ser realizadas.
2. Las actividades i y j son incluyentes entre sı́, es decir, se debe construir ambas plantas
o ninguna, lo cual se expresa simplemente mediante
zi = zj
82
5. El costo total de instalación de las n plantas está dado por la expresión
∑
n
Ci zi ,
i=1
donde Ci representa el costo de la actividad i. Esta expresión puede ser usada como
parte de la función objetivo o para representar una restricción de presupuesto total de
construcción, del tipo
∑n
Ci zi ≤ K,
i=1
Los casos descritos son ilustrativos y muy frecuentes, pero por cierto existen numerosas e
inesperadas situaciones que podrı́an ser modeladas usando una lógica similar a la expuesta.
83
Capı́tulo 5
Ejemplo 5.0.1 Una fábrica produce tres artı́culos en cantidades x1 , x2 , x3 , los cuales utilizan
dos materias primas en su elaboración, digamos a y b.
El proceso de producción debe satisfacer lo siguiente:
1) Para producir una unidad del artı́culo 1 se necesitan 2 unidades del recurso a y 5 del
recurso b.
Para producir una unidad del artı́culo 2 se necesitan 3 unidades del recurso a y 2 del
recurso b.
Para producir una unidad del artı́culo 3 se necesita 1 unidad del recurso a y 1 del
recurso b.
El precio unitario de venta del producto 1 es $4, el del producto 2 es $1 y el del producto 3
es $5.
El problema del fabricante será el de maximizar sus utilidades (sus ingresos por venta, en
este ejemplo) sujeto a sus restricciones en la producción.
84
(P ) máx 4x1 +x2 +5x3
2x1 +3x2 +x3 ≤ 10
5x1 +2x2 +x3 ≤ 20
xi ≥ 0 i = 1, 2, 3
85
[ ]x ( )
2 3 1 1 10
x2 ≤
5 2 1 20
x3
x1 , x2 , x3 ≥ 0
(P ) máx cT x
Ax ≤ b
x ≥0
(D) mı́n bT y
AT y ≥ c
y ≥0
86
Demostración. Para demostrar este teorema tomaremos el problema:
(D) mı́n bT y
AT y ≥ c
y ≥0
e − máx
(D) (−b)T y
(−A)T y ≤ −c
y ≥0
− mı́n (−c)T x
(−A)x ≥ −b
x ≥0
(P ) máx cT x
Ax ≤ b
x ≥0
Una noción limpia de dualidad requiere que las variables de un problema pertenezcan a
un espacio cuya dimensión sea igual al número de restricciones del dual (por restricciones
entendemos las ecuaciones o inecuaciones lineales, sin incluir las condiciones de signo de
las variables).
87
El teorema siguiente muestra que la función objetivo del problema dual acota a la del primal
y viceversa.
(P ) máx cT x
Ax ≤ b
x ≥0
un problema primal y
(D) mı́n bT y
AT y ≥ c
y ≥0
88
Hint. Para resolver este ejercicio, se sugiere desdoblar la restricción de igualdad en el pro-
blema (P ), escribirla en forma ≥ y luego aplicar la definición de dualidad.
(P ) mı́n cT x
Ax = b
x ≥ 0
y
(D) máx bT y
AT y ≤ c
Entonces, para ze, valor mı́nimo de (P) y ω
e , valor máximo de (D), se tiene:
a) Si ze es finito, entonces ω
e también lo es y se cumple ze = ω
e
Demostración.
a) Dado que ze es finito, existe un x e (punto extremo o solución básica factible), que es
solución de (P ). Entonces
( −1 )existe ( también
) B, submatriz de A = [B, N ], tal que se
B b eB
x
puede escribir xe= = . Además, en el óptimo los costos reducidos de
0 eN
x
las variables no básicas son positivos, es decir para π = B −T cB se tiene
cTN − π T N ≥ 0
lo que implica
N T π ≤ cN .
e = bT π
Probaremos que π es solución básica factible óptima de (D), con lo cual, ω
será finito.
89
[
] ( ) ( )
BT −T cB c
T
A π= T B cB = T ≤ B =c
N N π cN
y π es óptimo para (D), pues
( )
T −T
( T T ) B −1 b
e = b π = b B cB = cB cN
ω T
e = ze
= cT x
0
por lo tanto, por el Teorema de Dualidad Débil, π es óptimo.
b) Análogo.
d) Análogo.
Primal
ze finito (P) no acotado (P) infactible
e finito
ω Sı́ No No
Dual
(D) no acotado No No Sı́
(D) infactible No Sı́ Sı́/No
Ejercicio 5.1.2 Indique un ejemplo de un par primal-dual, en que ambos problemas sean
infactibles.
90
Demostración: Por el Teorema de Dualidad Fuerte, si x∗ e y ∗ son óptimos respectivos de
(P ) y (D), entonces cT x∗ = bT y ∗ , de donde se tiene
Ax = b
AT y + u = c
uT x = 0
x, u ≥ 0
91
del lado derecho ∆b no provoca un cambio en la base óptima. (
Luego,)cuando
( b−1
es reemplazado
)
′
′ xB B b + B −1 ∆b
por b + ∆b, la nueva solución óptima se transforma en x = =
0 0
y el valor óptimo de la función objetivo se perturba en
∆z = cTB B −1 ∆b = π ∗T ∆b
Veamos ahora otra interpretación económica posible. Supongamos que estamos bajo compe-
tencia perfecta y un productor resuelve:
(P ) máx cT x
Ax ≤ b
x ≥ 0
es decir, desea maximizar las utilidades dadas por el vector de precios c, sujeto a las restric-
ciones de capacidad de su firma. En el óptimo las restricciones no necesariamente se cumplen
con igualdad, es decir podrı́an sobrar ciertas materias primas que se pueden vender en el
mercado en un cierto precio, dado por el vector λ ≥ 0. Entonces, lo que este productor
resuelve es:
máx cT x + λT (b − Ax)
x≥0
92
Si el vector (c − AT λ) tiene todas sus componentes negativas, dado que el vector x es
positivo, se tiene que el máximo es cero, y φ(λ) = λT b.
Si el vector (c − AT λ) tiene alguna coordenada positiva, entonces, por el mismo argu-
mento, el subproblema de maximización es no acotado, luego φ(λ) = ∞.
Entonces se tiene {
bT λ si (c − AT λ) ≤ 0, λ ≥ 0
φ(λ) =
∞ si no
que es la utilidad del productor, en función de λ. El mercado, ”que es cruel”, asigna al
productor el mı́nimo de utilidades, a través de la fijación de precios. Como conoce la situación
de costos e infraestructura (suponiendo información completa), entonces resuelve:
(D) mı́n bT λ
AT λ ≥ c
λ ≥ 0
93
pero el lado derecho del sistema b̄ no es positivo.
0 c̄TN −z̄
I N̄ b̄
N̄ = B −1 N , b̄ = B −1 b, Ā = [I, N̄ ]
cTN − π T N ≥ 0,
lo cual implica
B T π = cB
N T π ≤ cN
Es decir, AT π ≤ c, lo que indica que π es una solución factible del problema dual.
94
(2) Elegir cualquier r tal que b̄r < 0.
c̄s c̄j
= máx{ / ārj < 0}
ārs ārj
e ir a (4).
mı́n cT x
Ax = b
x ≥0
Puede suceder que nuestro problema sea muy complejo y no se desee resolver completamente
de nuevo parta analizar estos cambios, por ejemplo por problemas de tiempo de cómputo. Las
siguientes subsecciones examinan estos casos, sobre la base de ejemplos simples. El estudio
del comportamiento de la solución de un problema lineal, como función de ciertos parámetros
del problema, también se conoce como análisis de sensibilidad.
95
5.5.1. Variación en los coeficientes de la función objetivo
Consideremos el siguiente problema:
Una solución inicial es x0 = (0, 0, 0)T (notar que es un punto extremo del poliedro). El cuadro
Simplex inicial es:
4 0 0 0 8 4 14400
2 0 1 0 2 −1 400
0 1 0 0 −1 1 600
1 0 0 1 0 0 400
La base está compuesta por [x3 , x2 , x4 ] y el valor óptimo es -14400. ¿Qué sucede si nos in-
forman que el coeficiente c1 vale -30 en lugar de -20?
Examinemos los costos reducidos (los demás elementos del cuadro, es decir, B −1 N, B −1 b,
y cTB B −1 b no sufren alteraciones, dado que c1 no participa en ellos). Tenemos
que c̄5 = 8 y
( ) 2
c̄6 = 4 no se modifican, y c̄1 = c1 − cTB B −1 A1 = −30 − −12 −16 0 0 = −6.
1
96
Por esto, el cuadro final cambia a uno que no satisface optimalidad:
−6 0 0 0 8 4 14400
2 0 1 0 2 −1 400
0 1 0 0 −1 1 600
1 0 0 1 0 0 400
Por lo tanto se puede pivotear para mejorar la solución en curso, haciendo entrar x1 a la
base:
0 0 3 0 14 1 15600
1 0 12 0 1 − 12 200
0 1 0 0 −1 1 600
0 0 −2 1 0
1 1
2
200
y la nueva solución es:
200 200
x∗ = 600 xholg = 0
0 0
1
que es positivo cuando θ ≥ −4. Es decir, el rango para el coeficiente c1 con el que la base
óptima [x3 , x2 , x4 ] no cambie es c1 ≥ −24.
Veamos otro caso. Supongamos ahora que el coeficiente perturbado es c2 = −16 y pasa
a ser −16 + γ. El vector de costos queda:
−20
−16 + γ
−12
c=
0
0
0
Recordemos que las tres primeras componentes de este vector corresponden a los costos
estructurales y las últimas tres corresponden a las variables de holgura, y por lo tanto son
97
cero. Examinemos los costos reducidos:
Estos costos reducidos de las variables no básicas son positivos, es decir preservan la opti-
malidad, cuando:
−8 ≤ γ ≤ 4
o sea, la base [x2 , x3 , x4 ] no cambia si:
−24 ≤ c2 ≤ −12
T
En general, si el vector c cambia a e
c se debe evaluar ē
cN = e cTB B −1 N y decidir:
cTN − e
T
si ē cTB B −1 b = z ∗ .
cN ≥ 0, la base óptima no cambia y sólo hay que reevaluar e
T
si ē
cN 0, se itera con algoritmo Simplex.
Tomemos el mismo ejemplo y supongamos que el vector b cambia a eb. La base óptima para
b es [x3 , x2 , x4 ] entonces se tiene que:
0 0 1 0 2 −1
B = 1 1 0 y B −1 = 0 −1 1
1 2 0 1 0 0
Si B −1eb 0, la solución no es factible (primal), pero los costos reducidos no han sufrido
cambios, luego el cuadro final presenta una solución primal-infactible y dual-factible.
Entonces se debe iterar con el algoritmo Simplex-dual.
98
100
Veamoslo con un ejemplo: supongamos que eb = 1000 , por lo tanto:
1600
400
−1e
B b = 600 ≥ 0
100
De aquı́ se deduce que para que se cumpla la condición de optimalidad se debe tener:
Notemos que en este ejemplo los datos originales satisfacen estas condiciones.
99
mı́n −20x1 −16x2 −12x3 −10x4
x1 +x4 ≤ 400
2x1 +x2 +x3 ≤ 1000
2x1 +2x2 +x3 +x4 ≤ 1600
x 1 , x2 , x3 ≥ 0
Además:
0 2 −1 1 −1
−1
B A4 = 0 −1 1
0 = 1
1 0 0 1 1
Por lo tanto, basta agregar la columna correspondiente a la nueva variable en el cuadro final
original. Esta columna es:
c4 − cTB B −1 A4
−1
B A4
100
En este caso, la nueva variable tiene costo reducido −6 < 0, y por lo tanto puede entrar a la
base. Ası́, al iterar, el cuadro queda:
10 0 0 0 6 8 4 16800
3 0 1 0 1 2 −1 800
−1 1 0 0 −1 −1 1 200
1 0 0 1 1 0 0 400
La nueva variable permite disminuir el costo total desde -14400 a -16800 siendo la solución
final:
0
200
x∗ =
800
400
En el ejemplo, si nos interesara calcular para qué valores del nuevo costo c4 la variable
introducida es irrelevante en el óptimo (es decir, no pertenece a la base óptima), la condición
serı́a c̄4 = c4 − cTB B −1 A4 ≥ 0, lo que implica c4 ≥ cTB B −1 A4 = −4.
I B −1N B −1b
dT x ≤ d0
101
En que d ∈ IRn y d0 ∈ IR. Es decir, agregamos:
dT x + xn+1 = d0
Con xn+1 una variable de holgura. Ası́, el problema original se puede plantear como:
( )
( T ) x
mı́n c 0
xn+1
[ ]( ) ( )
A 0 x b
T =
d 1 xn+1 d0
x, xn+1 ≥ 0
102
( )
( ) b
cTB e −1
0 B = cTB B −1 b.
d0
I B −1 N 0 B −1 b
d0 = 800
( )
dT = 1, 1, 1, 0, 0, 0
Entonces,
( )
dTB = 1, 1, 0 [x3 , x2 , x4 ]
( )
dTN = 1, 0, 0 [x1 , x5 , x6 ]
103
( ) ( ) 2 2 −1 ( )
dTN − dTB B −1 N = 1, 0, 0 − 1, 1, 0 0 −1 1 = −1, −1, 0
1 0 0
( ) 400
d0 − dTB B −1 b = 800 − 1, 1, 0 600 = −200
400
4 0 0 0 8 4 14400
2 0 1 0 2 −1 400
0 1 0 0 −1 1 600
1 0 0 1 0 0 400
4 0 0 0 8 4 0 14400
2 0 1 0 2 −1 0 400
0 1 0 0 −1 1 0 600
1 0 0 1 0 0 0 400
−1 0 0 0 −1 0 1 −200
Al pivotear con Simplex-dual, la última variable sale de la base (entra la primera) generando
un nuevo cuadro óptimo y una nueva solución:
0 0 0 0 4 4 4 13600
0 0 1 0 0 −1 2 0
0 1 0 0 −1 1 0 600
0 0 0 1 −1 0 1 200
1 0 0 0 1 0 −1 200
( )T
de modo que x∗ = 200, 600, 0, 200, 0, 0, 0 y z ∗ = −13600.
Esta técnica para recalcular soluciones óptimas cuando se ha agregado una restricción, pue-
de ser muy útil en la resolución de problemas de Programación Lineal Entera mediante el
método de Ramificación y Acotamiento, explicado anteriormente.
104
Capı́tulo 6
Esta área de la Optimización es muy importante ya que existen muchos problemas de estruc-
tura particular que se pueden expresar mediante la noción de grafo o red. Muchos de estos
problemas ya estaban planteados y concitaban el interés de los matemáticos e ingenieros
antes de la aparición formal de la Programación Lineal.
a) Problema de asignación
b) Problema de transporte
Notemos que los arcos son dirigidos, es decir, el par (i, j) ∈ A es distinguible del par
(j, i) ∈ A, que representa un arco en el sentido contrario. En el grafo de la figura la cantidad
entre paréntesis (b) representa la oferta en cada nodo (si b > 0 el nodo ofrece la cantidad b,
105
(4, 2)
2 4 Destino
(-5)
(10, 6)
(15, 4)
Origen
(ь, 2)
1 (ь, 2)
(15, 1)
(20)
(8, 4)
(5, 3)
3 5 Destino
(4, 1)
(-15)
La primera restricción dice que lo que entrega el nodo i es igual a su oferta más lo que recibe,
dado que el término del lado izquierdo representa la diferencia entre el flujo saliente
y el flujo entrante al nodo. La segunda restricción, dice que el flujo sobre un arco debe
respetar entre las cotas del mismo (en muchos casos se usa lij = 0 y uij = ∞).
106
Notemos que cada arco aparece sólo en dos restricciones ya que un arco participa sola-
mente en dos nodos: en uno como arco entrante y en otro como arco saliente. Cabe destacar
que la matriz A resultante es de rango incompleto (igual a n − 1, en que n es la cardinalidad
de N ). En efecto, la suma de las filas es cero, es decir son linealmente dependientes. Como
haremos en lo que sigue el supuesto (esencial en todo este capı́tulo) que
∑
n
bi = 0,
i=1
es decir que la oferta iguala a la demanda, entonces el sistema de ecuaciones del problema
(F CM ) tiene una ecuación redundante. En todo caso, ese supuesto no hace perder genera-
lidad al tratamiento de los problemas que veremos más adelante.
Normalmente, las variables estructurales del problema son consideradas enteras, de manera
que el problema general de flujo de costo mı́nimo puede escribirse de la forma:
∑
(F CM ) mı́n cij xij
(i,j)∈A
Ax = b
lij ≤ xij ≤ uij ∀(i, j) ∈ A
xij ∈ IN ∀(i, j) ∈ A
Las filas 1 a 5 de este cuadro representan las restricciones de equilibrio y se observa que la
matriz A tiene las filas linealmente dependientes (suman cero). De hecho, en cada columna
hay solamente dos coeficientes no nulos, un 1 y un -1, dado que cada arco es emergente para
un nodo e incidente para otro.
107
En lo que sigue del capı́tulo describiremos los 4 problemas antes mencionados, para lue-
go entregar un método de resolución del problema de transporte y una forma de mejorar
soluciones factibles del problema más general (F CM ).
Cajeras Cajas
1 1
2
2
n n
Figura 6.2: Problema de asignación. Hay n×n arcos, que corresponden a las variables del problema.
108
Las variables en este caso son:
{
1 si al nodo (cajera) i le corresponde el nodo (caja) j
xij =
0 si no
xij ∈ {0, 1} i, j = 1, . . . , n
Los coeficientes cij representan los rendimientos de las cajeras en cada caja y la función
objetivo persigue maximizar el rendimiento total.
109
Origen Destino
a1 1 1 b1
a2 2
2 b2
ai i
j bi
an n m bm
Figura 6.3: Problema de transporte. Hay n×m arcos, que corresponden a las variables del problema.
xij ∈ IN i = 1, . . . n, j = 1, . . . m
En este problema se considera que existen todos los arcos entre nodos de origen y nodos de
destino. Las restricciones quedan definidas de esa forma ya que, para los nodos de origen,
las ecuaciones son del tipo (flujo saliente - flujo entrante = demanda):
∑ ∑
xij − xki = ai ,
j/(i,j)∈A k/(k,i)∈A
110
y, en este caso ∑
xki = 0.
k/(k,i)∈A
y ∑
xjk = 0.
k/(j,k)∈A
Podemos notar que el problema de asignación puede también ser interpretado como un caso
particular del problema de transporte.
máx x
∑ts ∑
s.a. xsj − xks − xts = 0 (balance en s)
j k
∑ ∑
xtj + xts − xkt = 0 (balance en t)
j k
∑ ∑
xij − xki =0 i ̸= s, t (balance entre nodos intermedios)
j k
donde A′ = A ∪ {(t, s)}. Todas las sumas se extienden sobre los arcos existentes y se debe
asignar capacidad uts = ∞ al arco artificial (t, s).
Si N denota el conjunto de todos los nodos (incluidos s y t), una forma más compacta
111
3
2 4
2 4
1
Origen Destino
1 6
4 5
8
2
3 5
Figura 6.4: Problema de flujo máximo. Sobre los arcos se indica la capacidad.
máx xts∑ ∑
s.a. xij − xki = 0 i ∈ N (balance en los nodos)
j/(i,j)∈A′ k/(k,i)∈A′
Se puede advertir que si existe un camino orientado desde s a t, cuyos arcos tienen capacidad
infinita, entonces el problema es no acotado.
La longitud del arco puede ser interpretada en términos de costo, tiempo, distancia, etc.
El problema se escribe
112
30
2 4
0
11
8 Destino
Origen
6
1
12
3
1 7
10
3 5
2
Figura 6.5: Problema de camino más corto. Sobre los arcos se indica la distancia.
∑
mı́n cij xij
∑
(i,j)∈A
s.a. xsj = 1 (nodo s ofrece una unidad)
j
∑
xkt = 1 (nodo t demanda una unidad)
k
∑ ∑
xij− xki = 0 i ̸= s, t (balance en nodos intermedios)
j k
Esta formulación se basa en que una unidad de producto viaja desde el nodo origen s al nodo
destino t, de manera que al minimizar el costo total se está definiendo un camino de costo
mı́nimo. El nodo origen es oferente y el nodo destino es demandante, siendo los restantes
nodos de oferta (demanda) nula.
113
6.2. Resolución del Problema de Transporte
La resolución del problema de transporte será aquı́ abordada usando el algoritmo Simplex,
adaptado a la estructura particular de este problema. Para esto, describiremos tres etapas
del algortimo, a saber:
Se puede probar que las bases de este problema son árboles, es decir subgrafos de una
estructura particular que definimos a continuación.
Es conexo, es decir, existe una secuencia de arcos entre dos nodos cualesquiera (sin
considerar la orientación de los arcos), y
No contiene ciclos, es decir, partiendo de un nodo no se puede volver a él por una
secuencia de arcos adyacentes (sin importar la orientación).
114
8 6 10 9
C = 9 12 13 7
14 9 16 5
Ofertas Demandas
35 1 1 45
2 20
50 2
3 30
40 3 4 30
115
Ofertas Demandas
35
35 1 1 45
10
2 20
20
50 2
20
3 30
10
40 3 30 4 30
20, 30 y 30. Al primer arco (1, 1) se asigna el flujo x11 = 35, que el máximo posible y corres-
ponde a la oferta del nodo-origen 1. Eso quiere decir que el nodo-origen 1 queda saturado,
en el sentido que ya entregó toda su oferta. El nodo-destino 1, que con esto tiene demanda
residual igual a 10, puede ser saturado desde el nodo-origen 2, el cual queda con oferta re-
sidual igual a 40. Esas 40 unidades pueden ser trasladadas al nodo-destino 2, con lo cual el
nodo-origen 2 queda saturado y el nodo-destino 2 tiene demanda residual cero. Este es un
caso especial, puesto que se asigna entonces flujo de valor cero al arco (3, 2). Repitiendo el
procedimiento, el nodo-origen 3 entrega 10 unidades al nodo-destino 3 y 30 al nodo-destino 4.
Notar que este procedimiento produce una solución factible que corresponde a una base,
pues el grafo ası́ generado es un árbol de 6 arcos (esto es 3+4-1). Además se puede generar
distintas bases factibles cambiando el orden de saturación. En el ejemplo se usó el orden
correlativo de los nodos de origen y destino, pero bastarı́a con reordenarlos para que este
procedimiento generara una base distinta.
Por otro lado, podemos calcular el costos asociado a esta solución, el cual resulta ser z = 1180.
116
Procedimiento de saturación a costo mı́nimo. Como hemos dicho, el orden de satura-
ción es irrelevante, de manera que podemos ir haciendo entrar los arcos a la base, de acuerdo
a los costos de estos, buscando producir una solución de bajo costo esperado. Entonces ahora
saturamos siguiendo en cada paso el costo mı́nimo, es decir, comenzamos saturando desde
el arco que posee el menor costo al de mayor costo. Este procedimiento también produce un
árbol o solución básica factible.
Ofertas Demandas
15
35 1 1 45
20
30
2 20
50 2
20
3 30
10
40 3 30 4 30
En el ejemplo, el arco de costo más bajo es el arco (3, 4), de manera que saturamos x34 = 30
y este valor de flujo se resta de los dos nodos involucrados, lo cual hace que la demanda
del nodo se anula y la oferta del nodo 1 se rebaja a 10. Como el nodo destino 4 satisface
su demanda, entonces es eliminado del proceso lo cual significa que se procede a eliminar
todos los arcos incidentes en él. De los restantes arcos, el de mı́nimo costo es (1, 2), y se debe
saturar entonces x12 = 20, quedando la oferta del nodo 1 en valor 15 y la demanda del nodo
2 en valor 0. Se procede a eliminar ahora del proceso al nodo destino 2.
Siguiendo de esta forma se llega a una base (árbol) que consta de los arcos (1, 1), (1, 2),
(2, 1), (2, 3), (3, 3) y (3, 4), cuyo valor de función objetivo es z = 1080. Notar que es algo
menor que el valor de la solución anterior, obtenida por el proceso de saturación simple, pero
esto no corresponde a una propiedad sino más bien a una simple casualidad.
117
6.2.2. Examinar si una solución básica factible es óptima
Notemos que si los datos ai , bj son enteros, entonces los flujos xij son enteros (de acuerdo a los
procedimientos que hemos descrito), pues se trata de diferencias de números enteros (dados
por las ofertas y demandas). Esto muestra que todos los puntos extremos del problema de
transporte tienen coordenadas enteras, en el caso de ofertas y demandas enteras. Por esta
razón, el problema de optimización lineal es del tipo canónico
mı́n cT x, s.a. Ax = d, x ≥ 0,
en el cual no se impone la condición de integridad de las variables de manera explı́cita. Notar
que el vector d está dado por una columna que concatena los vectores a = (ai ) y b = (bj ).
Las restricciones son de dos tipos: de oferta (n) y de demanda (m). Es decir, hay dos tipos
de variables duales, que llamaremos ui y vj , asociadas respectivamante a los nodos de origen
y de destino. Entonces el problema dual se puede escribir
∑
n ∑
m
(D) máx ai ui + b j vj
i=1 j=1
ui + vj ≤ cij i = 1, . . . , n, j = 1, . . . , m
dado que en cada columna de la matriz A hay solamente dos coeficientes iguales a 1 y los
restantes son nulos.
Supongamos entonces que tenemos una solución básica factible (una solución factible con
estructura de árbol, tal como la última, generada por la saturación a costo más bajo). Los
costos reducidos para las variables básicas están dados por
c̄TB = cTB − π T B = 0
en que π T = (uT , v T ) es el vector de variables duales. De allı́, dada la estructura de la matriz
B, se tiene
(α) c̄ij = cij − ui − vj = 0 para todo arco básico
118
un valor arbitrario y usar (α) para encontrar todas las restantes variables duales (eso es
posible, dado que el sistema recorre un árbol, en el cual en cada paso se puede despejar una
variable ui o vj ). En este ejemplo (puede ser cualquier variable y en cualquier valor real),
fijamos u1 = 0, lo que implica que v1 = 8 y los valores de las demás variables duales quedan
determinadas ası́:
c11=8
u1=0 1 1 v1=8
c12=6
c21=9
2 v2=6
u2=1 2 c23=13
3 v3=12
c33=16
Con estos valores es posible determinar los costos reducidos de los arcos no básicos, usando
lass ecuaciones (β), de manera de decidir si alguno puede entrar a la base (costo reducido
negativo). Esto es,
c̄13 = −2
c̄14 = 8
c̄22 = 5
c̄24 = 5
c̄31 = 2
c̄32 = −1
Es sabido que si c̄ij ≥ 0, para todo arco no básico, entonces la solución en curso es óptima.
En este caso eso no es cierto y se observa que dos arcos pueden entrar a la base, mejorando
119
el valor de la función objetivo. En la sección siguiente mostraremos cómo iterar para realizar
el cambio de base.
15-ʄ
1 1 45
35
20
ʄ
30+ʄ 2 20
50 2 20-ʄ
3 30
10
40 3 30 4 30
Las condiciones de factibilidad que debe cumplir el valor λ solamente se deben imponer en
los arcos del ciclo que el arco ingresado genera, tal como se indica en la figura. Entonces, se
impone:
15 − λ ≥ 0
λ≥ 0
30 + λ ≥ 0
20 − λ ≥ 0
120
lo que implica que 0 ≤ λ ≤ 15. El mayor decrecimiento de la función objetivo se obtiene con
λ = 15, lo cual implica que la variable (arco) x11 se anula y sale de la base (si hay más de
una arco que se anula al maximizar λ, entonces solamente uno de ellos debe salir de la base,
quedando los demás en la base con valor de flujo igual a cero). En nuestro ejemplo, la nueva
solución básica está dada por el grafo siguiente, con valor de la función objetivo z = 1050.
Ofertas Demandas
1 1 45
35 20
15
45 2 20
50 2 5
3 30
10
40 3 30 4 30
Este procedimiento se puede entonces reiterar, realizando de nuevo los cálculos mostrados
en la sección anterior, hasta que todos los costos reducidos sean mayores o iguales a cero.
121
Consideremos de nuevo el problema del ejemplo introductorio de este capı́tulo:
(4, 2)
2 4 Destino
(-5)
(10, 6)
(15, 4)
Origen
(ь, 2)
1 (ь, 2)
(15, 1)
(20)
(8, 4)
(5, 3)
3 5 Destino
(4, 1)
(-15)
pero, en este ejemplo, usamos lij = 0 para todos los arcos. En este caso, tampoco imponemos
de manera explı́cita la integridad de las variables de flujo (en el caso de ofertas y demandas
enteras), pues las bases factibles son también árboles.
Sean n el número de nodos de la red y m = #A, el número de arcos. La matriz del grafo
es de n × m y las bases están compuestas por n − 1 arcos, como en el caso del ejemplo,
mostrado en el grafo más abajo. Los arcos no dibujados se entienden de flujo nulo. La base
indicada está compuesta por 4 arcos: {(1, 2), (2, 4), (2, 5), (3, 4)}. Los arcos (1, 3) y (3, 5) no
122
2
2 4 Destino
(-5)
10
12
Origen
1
3
(20)
8
5
3 5 Destino
(-15)
Figura 6.13: Base del problema de flujo. Los valores de los flujos están indicados en los arcos.
son básicos, pero tampoco tienen flujo nulo. Extenderemos ahora el concepto de base al caso
de la programación lineal con cotas, que es el caso del problema de flujo de costo mı́nimo.
Una variable no básica es aquella fijada en alguna de sus cotas y las variables básicas se
determinan resolviendo el sistema de ecuaciones (respetando sus cotas). Entonces:
123
xNi = lNi ∨ uNi
lB ≤ xB ≤ uB , donde BxB = b − N xN
En el caso del problema de flujo del ejemplo los arcos (1, 3) y (3, 5) son no básicos y están en
su cota superior. De manera análoga al caso del problema de transporte, los costos reducidos
se pueden determinar usando usando el hecho que
c̄TB = cTB − π T B = 0,
c̄TN = cTN − π T N,
lo que implica
(β ′ ) c̄ij = cij − πi + πj para todo arco no básico.
Las ecuaciones (α′ ), para las variables básicas, permiten determinar los valores de las varia-
bles duales. Dado que hay n nodos y n − 1 arcos básicos, basta fijar arbitrariamente el valor
de una variable dual. Para el caso del ejemplo, fijemos π2 = 0, de donde se obtiene:
4
0
π= −1
−2
−6
Luego, se calculan los costos reducidos de los arcos no básicos mediante (β ′ ), de donde se
obtiene:
124
c̄13 = c13 − (π1 − π3 ) = −1
c̄23 = c23 − (π2 − π3 ) = 1
c̄35 = c35 − (π3 − π5 ) = −2
c̄45 = c45 − (π4 − π5 ) = −2
c̄53 = c53 − (π5 − π3 ) = 6
En este caso, solamente el flujo x45 puede entrar a la base, pues está en su cota inferior (cero)
y tiene costo reducido negativo (c̄45 = −2).
2+ʄ
2 4 Destino
(-5)
10-ʄ
12
Origen
1 ʄ
3
(20)
8
5
3 5 Destino
(-15)
Sea λ el flujo del arco (4, 5). Por factibilidad, se debe cumplir:
0≤ 2+λ≤4
0≤ λ
0 ≤ 10 − λ ≤ 10
125
de manera que 0 ≤ λ ≤ 2, lo que implica que el arco (2, 4) sale de la base (alcanza su cota
superior) y se genera una nueva solución básica, que consta de las variables x12 , x25 , x34 y
x45 .
4
2 4 Destino
(-5)
8
12
Origen
1 2
3
(20)
8
5
3 5 Destino
(-15)
Este proceso se puede entonces repetir, de manera de verificar si esta solución es óptima y,
si no lo es, mejorarla de la misma manera aquı́ mostrada.
Notar que el valor del flujo (λ) que entra a la base se considera siempre positivo, pero
si se tratara de un arco que está fuera de la base, pero en su cota superior, este valor deberı́a
ser restado a ese flujo. Se procede en consecuencia en los demás arcos del ciclo generado por
ese arco.
126
Capı́tulo 7
En este capı́tulo estudiaremos algunos métodos numéricos para la resolución del problema
mı́n f (x)
x∈S
donde la función f : IRn −→ IR es en general diferenciable (en algunos casos, puede ser
necesario imponer condiciones adicionales) y el conjunto S es un convexo no vacı́o en IRn .
En el caso que S = IRn se habla de Optimización sin restricciones.
Aunque el conjunto S puede tener naturaleza bastante variable y general, en este capı́tu-
lo consideramos solamente el caso en que S puede ser descrito mediante un conjunto de
igualdades y desigualdades, es decir,
mı́n f (x)
gi (x) ≤ 0, i = 1, . . . , m
hj (x) = 0, j = 1, . . . , l
xk+1 = xk + λk dk
127
donde dk es una dirección de descenso (es decir, ∇f (xk )T dk < 0) y λk es un paso, que
satisface
f (xk + λk dk ) ≤ f (xk + λdk ) ∀λ ≥ 0, xk + λdk ∈ S
Ciertamente, el valor de λk podrı́a no ser único. Otra posibilidad es que f (xk + λdk ) diverja
a −∞ cuando λ tiende a infinito y se cumple xk + λdk ∈ S, para todo λ ≥ 0. En ese caso,
el problema (P ) es no acotado.
La dirección dk puede ser elegida de diversas maneras, según veremos en las secciones si-
guientes. A modo de ejemplo, en el caso no restringido, se puede elegir simplemente
dk = −∇f (xk ),
pues si xk no es punto estacionario (∇f (xk ) ̸= 0), entonces ∇f (xk )T dk < 0. Esta es la base
del método del gradiente, que veremos a continuación.
Más en general, si S es una matriz definida positiva, entonces es fácil probar que
dk = −S∇f (xk )
es también una dirección de descenso, puesto que ∇f (xk )T dk = −∇f (xk )T S∇f (xk ) < 0, si
∇f (xk ) ̸= 0. Esto justifica el método de Newton, en el cual se elige
dk = −H(xk )−1 ∇f (xk ),
siendo H(xk ) la matriz Hessiana de f , evaluada en xk . Este método es muy bueno cuando
la función f es (estrictamente) convexa.
128
Una propiedad interesante de la dirección del gradiente es que ella es la de máximo descenso
en el punto xk , en el sentido que es solución del problema
mı́n ∇f (xk )T d
∥d∥ ≤ 1
En efecto, de la desigualdad de Cauchy-Schwarz se puede decir que ∇f (xk )T d ≥ − ∥∇f (xk )∥ ∥d∥
y la igualdad se alcanza en
∇f (xk )
d=− .
∥∇f (xk )∥
Esto sugiere usar la dirección dk = −∇f (xk ) como dirección de búsqueda, es decir, el algo-
ritmo está dado por la formula iterativa:
xk+1 = xk − λk ∇f (xk ) (7.1)
Observación 7.1.1 Observar que el método elige, a partir de xk , una dirección ortogonal a
la curva de nivel de la función f en ese punto. En ese sentido corresponde a una discretiza-
ción de la trayectoria dada por la ecuación diferencial ordinaria
ẋ(t) = −∇f (x(t)), t ≥ 0, x(0) = xk
la cual, bajo ciertas condiciones de regularidad, satisface x(t) −→ x∗ si t −→ ∞, siendo
x∗ un punto estacionario de f .
129
x4 d4 x 5 d5 x*
d3
d2 x3
x2
d1
x
1
Se necesita determinar el paso en cada iteración. Recordemos que, de la definición del pro-
blema (L), debemos minimizar la función
0 = φ′ (λ) = −∇f (xk − λgk )T gk = −[c + Q(xk − λgk )]T gk = −gkT gk + λgkT Qgk
gkT gk
de donde λk = − .
gkT Qgk
Se obtiene entonces la formula iterativa (explı́cita) del método del gradiente en el caso
cuadrático definido positivo:
∥gk ∥2
xk+1 = xk − T gk .
gk Qgk
130
Este método es convergente a un punto estacionario de f , bajo hipótesis bastante generales.
Demostraremos esta convergencia solamente en el caso de funciones cuadráticas definidas
positivas, como la del ejemplo anterior.
Para esto, definamos una función auxiliar que mide el error de una estimación, es decir,
la distancia entre un punto dado y el punto estacionario,
1 1
ϵ(x) = (x − x∗ )T Q(x − x∗ ) = ∥x − x∗ ∥2Q ,
2 2
Notar que este es esencialmente el cuadrado del error de x con respecto a x∗ , usando la
norma inducida por la matriz Q. Observemos además que las funciones f y ϵ difieren sola-
mente en una constante, puesto que
1
ϵ(x) = f (x) + x∗ T Qx∗ ,
2
lo que significa que minimizar f es equivalente a minimizar ϵ, cuyo valor mı́nimo es obvia-
mente cero, dado que Q es definida positiva.
[ ]
(gkT gk )2
Lema 7.1.1 ϵ(xk+1 ) = 1 − T ϵ(xk )
(gk Qgk )(gkT Q−1 gk )
1
Notando que Q(xk − x∗ ) = gk y que ϵ(xk ) = gkT Q−1 gk se tiene
2
1[ ]
ϵ(xk+1 ) = (xk − x∗ )T Q(xk − x∗ ) + λ2k gk Qgk − 2λk (xk − x∗ )T Qgk
2
λ2
= ϵ(xk ) + k gkT Qgk − λk gkT gk
2
(gkT gk )2
= ϵ(xk ) − T
2gk Qgk
[ ]
(gkT gk )2
= 1− T ϵ(xk ),
(gk Qgk )(gkT Q−1 gk )
131
lo que termina la prueba.
Este lema permite dar una tasa de convergencia del método del gradiente, en el caso de
funciones cuadráticas definidas positivas. Para esto, es necesario recordar una propiedad
de las matrices definidas positivas, conocida como desigualdad de Kantorovich: sea Q una
matriz definida positiva y sean λm y λM sus valores propios más pequeño y más grande
respectivamente. Entonces se cumple:
(uT u)2 4λm λM
T T −1
≥ ∀u ∈ IRn , u ̸= 0
(u Qu)(u Q u) (λn + λM )2
Aplicando esta desigualdad al lema precedente (bajo el supuesto evidente que gk ̸= 0),
tenemos que [ ]
4λm λM
ϵ(xk+1 ) ≤ 1 − ϵ(xk ),
(λm + λM )2
es decir, [ ]2
λM − λm
ϵ(xk+1 ) ≤ ϵ(xk ).
λM + λm
[ ]
λM − λm
Si denotamos ρ = ∈ [0, 1[, entonces
λM + λm
ϵ(xk+1 ) ≤ ρ2 ϵ(xk ),
o bien
∥xk+1 − x∗ ∥Q ≤ ρ∥xk − x∗ ∥Q
Se puede ver que si la matriz Q es diagonal, entonces los dos valores propios extremos
coinciden y se tiene que ϵ(x1 ) = 0, cualquiera que sea x0 ∈ IRn , lo que significa que el méto-
do converge en una iteración. Si no, la velocidad de convergencia depende la diferencia entre
λM y λm , es decir, de la excentricidad de la forma cuadrática. Esto muestra que el método
del gradiente converge linealmente en este caso (cuadrático definido positivo), según la
definición que damos a continuación.
132
{xk } converge superlinealmente si existen {βk } ⊂ IR+ con βk → 0 si k → ∞, y k0
tales que
∥xk+1 − x̄∥ ≤ βk ∥xk − x̄∥ , ∀k ≥ k0 .
{xk } converge cuadráticamente si existen β ∈ IR+ y k0 tales que
∥xk+1 − x̄∥ ≤ β ∥xk − x̄∥2 , ∀k ≥ k0 .
e−x
2
Ejemplo 7.1.1 Veamos el caso simple (P ) mı́n f (x), con f (x) = − (campana de
2
Gauss invertida). La formula de Newton aplicada a este caso es
2x3k
xk+1 = xk − f ′′ (xk )−1 f ′ (xk ) = .
1 − 2x2k
133
Entonces, se observa que si |x0 | < 1/2, se tiene que {xk } converge a cero, que es la solución
del problema (P ).
Si se parte de un punto tal que |x0 | = 1/2, entonces x1 = −x0 , x2 = −x1 , x3 = −x2 y
ası́ sucesivamente, es decir, la sucesión oscila sin converger.
Si se parte de un punto tal que x0 > 1/2 o bien x0 < −1/2, entonces la sucesión diver-
ge a +∞ o bien −∞, según el caso.
Se ha detectado ası́ una región de convergencia del método, dada por la bola abierta B(0, 12 ).
e−(x +y )
2 2
Se sugiere, como ejercicio, analizar similarmente el caso (en dos variables) f (x, y) = −
2
y describir la región de convergencia. Damos a continuación, sin demostración, el teorema
de convergencia (local) del algoritmo de Newton.
Teorema 7.1.1 Sean f ∈ C 2 y x∗ ∈ IRn , tales que ∇f (x∗ ) = 0 y H(x∗ ) es definida positiva.
Entonces existe r > 0, tal que si x0 ∈ B(x∗ , r), el algoritmo
converge a x∗ .
xk+1 − x∗ = xk − x∗ − Hk−1 gk
= Hk−1 [Hk (xk − x∗ ) − (gk − g ∗ )] (7.2)
donde g ∗ = ∇f (x∗ ) = 0.
134
Como f ∈ C 2 , existen µ > 0 y r > 0 tales que
∥H(x)−1 ∥ ≤ µ, ∀x ∈ B(x∗ , r)
de donde
∫ 1
∗ ∗ ∗
∥∇f (xk ) − ∇f (x ) − H(xk )(xk − x )∥ ≤ ∥xk − x ∥ ∥H(x∗ + λ(xk − x∗ )) − H(x∗ )∥dλ
0
≤ ∥xk − x∗ ∥ sup {∥H(x∗ + λ(xk − x∗ )) − H(x∗ )∥}
0≤λ≤1
∗
= θk ∥xk − x ∥ (7.4)
siendo θk = sup {∥H(x∗ + λ(xk − x∗ )) − H(x∗ )∥} > 0 finito, pues H es continua, dado que
0≤λ≤1
f ∈ C 2.
Esta convergencia puede ser cuadrática, en el caso que la matriz hessiana H es de Lips-
chitz, es decir, existe L tal que
En ese caso,
∥H(x∗ + λ(xk − x∗ )) − H(x∗ )∥ ≤ L ∥λ(xk − x∗ )∥
135
y la desigualdad (7.4) puede ser recalculada:
∫ 1
∗ ∗ ∗
∥∇f (xk ) − ∇f (x ) − H(xk )(xk − x )∥ ≤ ∥xk − x ∥ ∥H(x∗ + λ(xk − x∗ )) − H(x∗ )∥dλ
0
∫ 1
∗
≤ L∥xk − x ∥ ∥λ(xk − x∗ )∥dλ
0
L
= ∥xk − x∗ ∥2
2
Aplicando a (7.3),
µL
∥xk+1 − x∗ ∥ ≤ ∥xk − x∗ ∥2 ,
2
lo cual muestra que el método de Newton tiene, en este caso, convergencia cuadrática.
Debemos notar que este algoritmo puede no converger, dependiendo del punto de partida, tal
como se ha visto en el ejemplo antes mostrado. Una forma de evitar o al menos aminorar este
problema del método es usar la dirección dk como dirección de búsqueda lineal y minimizar en
cada iteración sobre la variedad lineal determinada por esa dirección. Esto permite modificar
el método como se indica a continuación.
Al usar esta estrategia, aparece la necesidad de minimizar la función (de una variable)
φ(t) = f (xk + tdk ), para t ≥ 0. Este subproblema es analizado en lo que sigue.
136
7.1.4. Método de paso (minimización unidimensional)
En general, en este tipo de métodos se debe realizar una minimización unidimensional en
cada iteración. Es decir, tal como se dijo antes, resolver el problema
en que φ(λ) = f (xk + λdk ). En ciertos casos, dependiendo de las propiedades de la función f ,
puede ser posible encontrar el mı́nimo unidimensional resolviendo directamente la ecuación
φ′ (α) = 0, es decir la ecuación ∇f (xk + αdk )T dk = 0, pero lo más frecuente es verse obligado
a aproximar el mı́nimo numéricamente mediante algún procedimiento como el denominado
”método de dicotomı́a”, que exponemos a continuación.
Sunpongamos que se sabe que el mı́nimo de φ está en algún intervalo [0, λ̄k ]. Esto puede
ocurrir en casos en que se sabe que la función es unimodal, es decir, que posee un solo valor
λk que resuelve (L). Una función unimodal es lo que se conoce como función estrictamente
casi-convexa, definida a continuación.
Si dk es una dirección de descenso, entonces es claro que φ′ (0) < 0. En efecto, se puede
advertir que en el caso diferenciable: φ′ (λ) = ∇f (xk + λdk )T dk . Entonces, evaluando
en el cero, φ′ (0) = ∇f (xk )T dk = f ′ (xk ; dk ) < 0.
137
Teorema 7.1.2 Sea φ : IR → IR una función estrictamente casi-convexa, que tiene un
mı́nimo global en el intervalo [a, b], entonces para α1 , α2 ∈ [a, b] tales que α1 < α2 se tiene:
a) φ(α1 ) > φ(α2 ), entonces el nuevo intervalo de confianza para el mı́nimo es [α1 , b].
Método de dicotomı́a
donde φ es unimodal.
[0] Sean ε > 0, ρ > 0 (precisión), j = 1, [a1 , b1 ] intervalo inicial (por ejemplo, puede ser
a1 = a, b1 = b).
aj + bj
• α1 = −ε
2
aj + bj
• α2 = +ε
2
138
[2] Si φ(α1 ) > φ(α2 ) hacer aj+1 = α1 y bj+1 = bj
Si φ(α1 ) ≤ φ(α2 ) hacer aj+1 = aj y bj+1 = α2
[3] j ← j + 1 y volver a [1]
Observación 7.1.4 Como ejercicio, probar que este método requiere que 2ε < ρ y también
probar que este procedimiento de determinación de paso produce una secuencia anidada de
intervalos cerrados, tal que
1 1
bj+1 − aj+1 =j
(b1 − a1 ) + 2ε(1 − j ),
2 2
que converge a un intervalo de ancho 2ε, el cual contiene un punto que es solución de (L).
Este procedimiento de minimización unidimensional es muy rápido, pero está limitado a ca-
sos en que la función es unimodal. En general, la minimización de funciones de una variable es
un problema no trivial, especialmente si no se conoce alguna propiedad general de la función.
Siguiendo con el caso unimodal, resta por saber cómo determinar un intervalo inicial [a, b]
para partir este método, en el caso de la función φ(t) = f (xk + tdk ). Sobre la base que dk es
dirección de descenso se tiene que φ′ (0) < 0 (en efecto, φ′ (t) = ∇f (xk + tdk )T dk ) y si existe
un punto que minimiza φ en [0, ∞[, se puede aplicar el procedimiento simple siguiente:
139
7.2.1. Método del gradiente proyectado
Este método es una generalización del método del gradiente, al caso de un problema de
función objetivo no lineal y restricciones lineales. Una extensión al caso de restricciones no
lineales puede también ser propuesta, pero está fuera del alcance de este texto. La idea es
la siguiente: a partir de un punto factible, es decir que satisface las restricciones que definen
el poliedro factible, se propone la dirección del método del gradiente (la misma usada en el
método correspondiente al caso sin restricciones). Si esta dirección es admisible entonces se
determina un paso sobre ella, tal como en el método irrestricto. Si no, entonces se procede a
proyectar esta dirección sobre la cara ”más cercana”del poliedro y se elige esa nueva direcc-
ción como dirección de búsqueda unidimensional. Este método es también conocido como
método de Rosen y data de comienzos de la década de 1960.
Definición 7.2.1 Una matriz P ∈ Mn×n se dice matriz de proyección si ella es simétrica
e idempotente (es decir, satisface P = P T y P = P 2 ).
Algunas propiedades
P es semidefinida positiva.
Si P es invertible, entonces P = I (esto significa que en general las proyecciones son
no invertibles, a menos que se trate de la identidad).
I-P es una proyección.
El conjunto L = {P x / x ∈ IRn } es ortogonal a L⊥ = {(I − P )x / x ∈ IRn } y
IRn = L ⊕ L⊥ .
140
Si x̄ es un punto factible de P , entonces definamos la descomposición de la matriz A de
la manera siguiente (eventualmente reordenando filas):
[ ]
A1
A= tal que A1 x̄ = b1 , A2 x̄ < b2 ,
A2
( )
b
donde b = 1 es la correspondiente descomposición del lado derecho de la inecuación. Se
b2
observa que esta descomposición permite identificar cuáles son las restricciones activas y las
no activas.
La idea es entonces proyectar la dirección del método del gradiente sobre la cara [”más ]
A1
cercana”del poliedro, definida por las restricciones activas. Sea entonces la matriz M = .
E
La proyección de −∇f (x̄) sobre el núcleo de M es d = −P ∇f (x̄), donde
P = I − M T (M M T )−1 M
Es un buen ejercicio demostrar que la proyección sobre el núcleo de M está dada por la
matriz P , en el caso que el rango-filas de M es completo, es decir sus filas son linealmente
independientes.
Observación 7.2.1 Notar que una dirección es admisible para el sistema de inecuaciones
Ax ≤ b, Ex = e, si y sólo si satisface A1 d ≤ 0 y Ed = 0. Para las restricciones inactivas
en un punto dado x̄, representadas por la matriz A2 , cualquier dirección a partir de x̄ es
admisible, dado que A2 x̄ < b2 .
141
El siguiente teorema justifica que proyectar la dirección del método del gradiente es una
buena elección en el caso de restricciones lineales, en el sentido que eso permite deducir una
dirección admisible y de descenso, ası́ como inducir un criterio de detención.
(P ) mı́n f (x)
Ax ≤ b
Ex = e
Se cumple que:
0 = −P ∇f (x̄)
= ∇f (x̄) − M T (M M T )−1 M ∇f (x̄)
= ∇f (x̄) + M T w
( )
[ T T] u
= ∇f (x̄) + A1 , E
v
= ∇f (x̄) + AT1 u + E T v,
142
y es claro que esta es la condición de Karush-Kuhn-Tucker.
Veamos ahora el caso u 0. Elijamos una coordenada uj < 0 y definamos d¯ = −P̄ ∇f (x̄),
suponiendo que es igual a cero. Entonces, como antes, se puede escribir
0 = ∇f (x̄) + M̄ T w̄,
donde w̄ = −(M̄ M̄ T )−1 ∇f (x̄). También, por hipótesis, tenemos que
0 = ∇f (x̄) + M T w,
luego
M̄ T w̄ = M T w
= AT1 u + E T v
= ĀT1 ũ + E T v + uj aTj
.
..
siendo aj la fila j de A1 y ũ = ui
..
. i̸=j
( )
ũ
Ası́, tenemos que M̄ T w̄ = M̄ T w̃ + uj aTj , donde w̃ = . De allı́, obtenemos que
v
M̄ T (w̄ − w̃) − uj aTj = 0
El lado izquierdo de esta expresión es una combinación lineal de las filas de M , en que al
menos un ponderador es no nulo, puesto que uj < 0.
Esto contradice que M tenga rango-filas completo, por lo tanto d¯ = −P̄ ∇f (x̄) ̸= 0 y,
por el lema anterior, d¯ es dirección de descenso.
143
y, en particular, Ā1 d¯ = 0, E d¯ = 0. Luego, para probar que A1 d¯ ≤ 0, basta probar aj d¯ ≤ 0.
Para eso, retomemos
0 = P ∇f (x̄)
= ∇f (x̄) + M T w
= ∇f (x̄) + M̄ T w̃ + uj aTj
= aj P̄ ∇f (x̄) + aj P̄ M̄ T w̃ + uj aj P̄ aTj (multiplicamos por aj P̄ )
= aj P̄ ∇f (x̄) + uj aj P̄ aTj (notamos que M̄ P̄ = 0)
= −aj d¯ + uj aj P̄ aT j
] [ ( )
A1 b
(1) Sea la descomposición A = , b = 1 tal que A1 xk = b1 , A2 xk < b2 y definamos
[ ] A2 b2
A1
M= .
E
(2) Sean P = I − M T (M M T )−1 M , dk = −P ∇f (xk )
(si M es vacı́a, se usa P = I)
144
donde λ̄k = sup{λ / xk + λdk ∈ P}.
xk+1 = xk + λk dk , k ← k + 1 e ir a (1).
Observación 7.2.2 El valor de λ̄k puede ser calculado en forma explı́cita en el caso de
restricciones lineales. En primer lugar notemos que dado que Exk = e y que la dirección
satisface Edk = 0, entonces E(xk + λdk ) = e, cualquiera que sea λ. Por lo tanto, solamente
se debe determinar λ̄k > 0 que garantice A(xk + λdk ) ≤ b, para todo λ ∈ [0, λ̄k ].
Entonces, imponemos λAdk ≤ b−Axk , para todo λ ∈ [0, λ̄k ], lo cual se escribe por coordenada
de la manera siguiente:
Dado que el lado derecho es positivo, para los valores de i tales que (Adk )i ≤ 0, la desigualdad
anterior es trivialmente satisfecha. Esto significa que
{ }
(b − Axk )i
λ̄k = mı́n / (Adk )i > 0 .
(Adk )i
Como A1 dk = 0, entonces se puede escribir en forma más simple
{ }
(b2 − A2 xk )i
λ̄k = mı́n / (A2 dk )i > 0 .
(A2 dk )i
Notar que este es esencialmente el criterio de salida de la base en el método Simplex. De
hecho, si no existe (A2 dk )i > 0, entonces se considera λ̄k = +∞.
145
caso el trazo lineal de búsqueda está contenido en una cara del poliedro.
y un punto factible x̄. Usando la misma notación de la sección anterior, recordemos que d¯ es
una dirección admisible si cumple A1 d¯ ≤ 0 y E d¯ = 0. Además, es de descenso si ∇f (x̄)T d¯ < 0.
Observación 7.2.4 Notar que (D) es un problema de Programación Lineal cuyo poliedro
factible es acotado, lo cual implica que tiene solución finita. Además, dado que d = 0 es
factible, la solución d¯ de (D) satisface ∇f (x̄)T d¯ ≤ 0.
Veamos qué ocurre si el óptimo d¯ de este problema es tal que ∇f (x̄)T d¯ = 0. Entonces es
claro que no existe d tal que
∇f (x̄)T d < 0
A1 d ≤ 0
Ed = 0
−1 ≤ dj ≤ 1 j = 1, . . . , n
lo cual dice que no existe d tal que
∇f (x̄)T d < 0
A1 d ≤ 0
Ed = 0
146
(si existiese, bastarı́a normalizar la solución), es decir, no existe d tal que
−∇f T
(x̄) d > 0
A1
E d ≤ 0
−E
Haciendo v = v ′ − v ′′ se obtiene
∇f (x̄) + AT1 u + E T v = 0, u ≥ 0
∇f (x̄)T d < 0
A1 d ≤ 0
Ed = 0
Teorema 7.2.2 Sea x̄ un punto factible de (P ). Consideremos problema (D), que permite
encontrar una dirección admisible de descenso para el problema (P ). Entonces, x̄ es punto
de Karush-Kuhn-Tucker si y solamente si el óptimo d¯ de (D) satisface ∇f (x̄)T d¯ = 0.
147
][ ( )
A1 b
(1) Sea la descomposición A = , b = 1 tal que A1 xk = b1 , A2 xk < b2 .
A2 b2
Si no, ir a (3).
xk+1 = xk + λk dk , k ← k + 1 e ir a (1).
Observación 7.2.5 Notar que el valor de λ̄k podrı́a ser igual a +∞, en el caso en que
Adk ≤ 0. En esa situación, podrı́a detectarse no acotamiento de (P ), si es que f (xk + λdk )
es monótona decreciente con λ ≥ 0.
(P ) mı́n f (x)
hj (x) = 0 j = 1, . . . , l
148
La idea del método de penalización es resolver una secuencia de problemas de optimización
irrestricta, aproximando ası́ de manera sucesiva, la solución del problema (P ). Sea entonces
el problema
∑
l
(Pµ ) mı́n f (x) + µ hj (x)2
j=1
donde µ > 0 es una constante arbitraria. De un punto de vista intuitivo, si µ es un valor re-
lativamente grande, entonces la solución óptima de (Pµ ) tenderá a satisfacer las restricciones
de (P ). Se puede entonces interpretar el factor µ como un ”pago o castigo”por insatisfacción
de las restricciones.
El problema penalizado es
[ ]
(Pµk ) mı́n x21 + x22 + x23 + µk (x1 + x2 + x3 − 1)2 + (x1 − x2 )2
149
Definición 7.2.2 Una función continua ψ : IR −→ IR+ se dice función de penalización
si satisface la propiedad:
y = 0 =⇒ ψ(y) = 0
y ̸= 0 =⇒ ψ(y) > 0
Bajo ciertas hipótesis generales de regularidad, se puede demostrar la convergencia del méto-
do de penalización, en el sentido del teorema siguiente.
∑
l
Sea además α(x) = ψ(hj (x)) y supongamos que, cualquiera que sea la sucesión real
j=1
{µk } divergente a +∞, el problema irrestricto
(Pk ) mı́n f (x) + µk α(x)
x ∈ IRn
tiene solución xk y la sucesión {xk } es acotada.
Entonces
µk α(xk ) −→ 0, si µk −→ +∞.
Cualquier punto de adherencia de {xk } (y existe al menos uno), es solución de (P ).
(1) Resolver
(Pk ) mı́n f (x) + µk α(x)
x ∈ IRn
usando xk como punto de partida. Sea xk+1 solución de (Pk ).
(2) Si µk α(xk+1 ) < ε, parar.
Si µk α(xk+1 ) ≥ ε, hacer µk+1 = βµk , k ←− k + 1 e ir a (1).
150
Capı́tulo 8
Problemas Propuestos
151
El coste de producción es 3 unidades monetarias por unidad de energı́a.
Proyecto Ri Ii
P1: Extensión Costanera 1,5 1,1
P2: Plazas de Peaje 3,0 2,5
P3: Pavimentación en Ruta 5 5,3 4,5
P4: Extensión de la Ruta 5 3,3 3,1
P5: Pasos Peatonales en Costanera 2,5 1,8
P6: Casetas de Emergencia 0,5 0,3
Las condiciones requeridas son las siguientes:
4. Como variante del problema anterior, suponga que el Ministerio de Obras Públicas
debe asignar los 6 proyectos a dos empresas constructoras (las cuales se repartirán las
6 obras). Los costos para el Ministerio, de acuerdo a las cotizaciones entregadas por
las empresas, son (en millones de dólares):
152
Las condiciones requeridas son las siguientes:
5. Considere una fábrica con tres tipos de máquinas: A, B y C, que pueden producir
cuatro productos: 1, 2, 3 y 4. Cada producto debe pasar por alguna operación en cada
uno de los tres tipos de máquina. Suponga que la producción es continua (es decir,
se puede producir una cantidad no necesariamente entera de productos) y que cada
producto debe pasar primero por una máquina A, luego por una B y finalmente por
una C. Suponga además que el tiempo requerido para ajustar las máquinas al cambiar
de producto es despreciable.
La tabla siguiente muestra las horas requeridas en cada tipo de máquina por unidad
de cada producto, el tiempo total disponible por semana por máquina y la ganancia
por la venta de una unidad de cada producto.
153
Se desea determinar la producción semanal de cada producto que maximiza las ganan-
cias. Plantee el problema como un problema de programación lineal.
6. La empresa OPTI-TV posee dos plantas de fabricación para TVs de alta definición
(TVAD) en Seoul y en Busan, posee también dos fuentes de componentes en Ansan y
Guni y tres mercados principales en el mundo: Nueva York, Tokio y Londres. Un set
completo de componentes se necesita para producir una unidad de producto TVAD.
Los costos de transporte desde las fuentes a las fábricas y desde las fábricas a los mer-
cados, están dados por las siguientes tablas:
a) Los centros de Nueva York, Tokio y Londres tienen demandas de 8.000, 14.000
y 3.000 TVAD, respectivamente. Formule el problema de encontrar la manera
óptima de manejar el proceso de transporte (planta-fábrica-mercado) de manera
de minimizar el costo de transporte.
b) Asuma ahora que cada mercado requiere al menos 2.000 TVADs OPTI-TV y
que cada unidad se vende a un precio de $120, $90, $110 en Nueva York, Tokio
y Londres, respectivamente (note que ya no son las demandas de la parte a)).
Formule el problema de maximizar el beneficio neto.
7. La empresa minera ABFR Asoc. tiene 2 plantas de producción de cobre cuyos stocks,
al dı́a de hoy, son a1 = 90.000, a2 =70.000 toneladas de mineral. Por contratos ya fir-
mados, la empresa debe satisfacer las demandas de 3 clientes: b1 =55.000, b2 =75.000,
b3 =50.000. Suponga que los costos cij (unitarios, por tonelada) entre plantas y clientes
están dados por: [ ]
2 4 6
(cij ) =
1 5 6
Considere finalmente que, por cada tonelada no provista (demanda insatisfecha), la
empresa debe pagar una penalización p1 = 3, p2 = 2, p3 = 1 al cliente correspondiente.
Formule un problema de optimización que represente esta situación.
Indicación: defina las variables xij , toneladas que la planta i entrega al cliente j.
154
8. Escriba un modelo para el problema descrito a continuación.
La National Free Transportation Agency (NAFTA), debe decidir un programa de for-
mación y contratación de nuevas azafatas para los próximos seis meses.
Las exigencias a respetar son expresadas en horas de vuelo de azafatas: 8.000 en enero,
9.000 en febrero, 8.000 en marzo, 10.000 en abril, 9.000 en mayo y 12.000 en junio.
La formación de una nueva azafata dura un mes. Esta formación comprende 100 horas
de vuelo en lı́neas de la compañı́a. Estas 100 horas se pueden deducir de exigencias
que las azafatas deben cumplir, es decir, sirven para satisfacer las exigencias de horas
de vuelo de azafatas de la compañı́a.
Cada azafata experimentada puede entregar hasta 150 horas de vuelo por mes. La
compañı́a dispone de 60 azafatas experimentadas al 1 de enero.
Cada azafata experimentada recibe un sueldo de US$800 por mes, independientemente
del número de horas que preste servicio. Cada mes, el 10 % de las azafatas experimen-
tadas deja su trabajo por diversas razones.
Al cabo de un mes de formación, que cuesta US$400 a la compañı́a, una azafata apren-
diz se convierte en azafata experimentada.
9. Un granjero posee 100 hectáreas (ha.) que pueden ser utilizadas para el cultivo de trigo
y maı́z. El rendimiento por ha. es de 60 quintales anuales de trigo y de 95 quintales de
maı́z.
Cualquier fracción de las 100 ha. puede ser destinada al cultivo de trigo o maı́z. El
trabajo necesario es de 4 hrs. por ha. anuales, más 0.15 hr. por quintal de trigo y 0.70
hr. por quintal de maı́z. El costo de las semillas y abono es de $20 por quintal de trigo
y $12 por quintal de maı́z.
El granjero puede vender su trigo a $175 el quintal y su maı́z a $95 el quintal. A la
compra, le costarı́an respectivemente $250 y $150. Puede también criar cerdos y pollos.
Los vende cuando han alcanzado la edad de 12 meses. Un cerdo se vende a $4.000. Un
ave se vende en términos de cerdo-equivalente (el número de pollos necesarios para
obtener $4.000 al momento de la venta).
Un cerdo requiere 25 quintales de trigo o 20 quintales de maı́z, ası́ como 25 hrs. de
trabajo y 25 m2 de terreno. Un cerdo-equivalente de pollos requiere 25 quintales de
maı́z o 10 quintales de trigo, ası́ como 40 hrs. de trabajo y 15 m2 de terreno.
El granjero dispone de 10.000 m2 de terreno para la crianza. Dispone también de 2.000
hrs. de trabajo anuales y puede poner a su familia a trabajar, disponiendo ası́ de
155
2.000 hrs. suplementarias. Puede también contratar horas suplementarias de obreros
agrı́colas al costo de $150 la hora.
Cada hora de obrero agrı́cola demanda 0,15 hr. de trabajo de supervisión de parte del
granjero.
Escriba un modelo que permita determinar las superficies a destinar al cultivo de trigo
y/o maı́z y las cantidades de cerdos y/o pollos a producir, de manera de maximizar el
beneficio. Explicite los supuestos usados en la modelación.
156
5. (a) Demuestre que un poliedro es acotado si y solo si no tiene direcciones extremas.
(b) Sea P = {x ∈ Rn : Ax = b, x ≥ 0} un poliedro convexo compacto (cerrado y
acotado) en Rn , con A ∈ M(R)m×n de rango m < n. Demuestre la siguiente
equivalencia:
Cada elemento de P tiene al menos m componentes mayores que cero
⇐⇒
Cada punto extremo de P tiene exactamente m componentes mayores que cero.
7. Sea φ(x) = Ax una función lineal, donde A es una matriz de dimensión m × n. De-
muestre que si S es polı́topo en IRn , entonces φ(S) es un polı́topo en IRm .
Recuerdo: Un polı́topo es la envoltura convexa de un conjunto finito de puntos.
8. Encuentre los puntos extremos y las direcciones extremas de los siguientes poliedros:
x1 + 2x2 + 3x3 − 4x4 = 0
P1 : x1 + 4x2 + 3x3 − 8x4 = 0
x1 , x2 , x3 , x4 ≥ 0
x1 + x2 + x3 + x4 + x5 = 10
P2 : x1 − x2 + x3 − x4 − x5 = 10
x1 , x2 , x3 , x4 , x5 ≥ 0
−x1 + 2x2 ≤ 4
x1 − 3x2 ≤ 3
x1 , x2 ≥ 0
a) Usando los teoremas de caracterización, encuentre los puntos extremos y las di-
recciones extremas de P.
( )
4
b) En base a lo anterior, represente el punto como combinación convexa de
1
puntos extremos más una combinación lineal no negativa de direcciones extremas.
157
Determine todos los puntos y direcciones extremas de P, usando los teoremas de ca-
racterización. Repita su cálculo para el poliedro
P ′ = {x ∈ IR2 / − x1 + x2 ≤ 2, x1 + x2 ≥ 4, x2 ≤ 4, x1 ≥ 0, x2 ≥ 0}.
12. Sean A matriz p × n y B matriz q × n. Demuestre que uno y sólo uno de los siguientes
sistemas tienen solución
a) Ax < 0 Bx = 0
b) A u + B v = 0 u ̸= 0, u ≥ 0
T T
AT y ≥ c
y≥0
máx cT x
Ax ≤ 0
x≥0
es no acotado.
15. Sea S un conjunto convexo no vacı́o en IRn , α ∈ IR, y sea f : S → IR una función
convexa. Demuestre que los siguientes conjuntos son convexos:
158
a) Sα = {x ∈ S / f (x) ≤ α}
b) C = {(x, α) ∈ S × IR / f (x) ≤ α}
16. Pruebe o contradiga la concavidad de la función f (x1 , x2 ) = 10 − 3(x2 − x21 )2 definida
en los siguientes conjuntos:
a) S = {(x1 , x2 ) : −1 ≤ x1 ≤ 1, −1 ≤ x2 ≤ 1}
b) S = {(x1 , x2 ) : x21 ≥ x2 }
17. Sean
z(b) = máx{cT x / Ax ≤ b, x ≥ 0}
v(c) = máx{cT x / Ax ≤ b, x ≥ 0}
Demuestre que z es cóncava y v es convexa, suponiendo que b y c están en dominios
convexos en que estos dos problemas son factibles y acotados.
18. Sean fi : IRn −→ IR, i = 1, . . . , m, funciones convexas y considere la función
f (x) = máx{f1 (x), . . . , fm (x)}
Demuestre que el problema
(P ) mı́n f (x), x ≥ 0,
es equivalente al problema de optimización en IRn+1
(P ′ ) mı́n t
fi (x) ≤ t, i = 1, . . . , m
x ≥ 0,
en el sentido que una solución de (P ′ ) define de manera trivial una solución de (P ) y
viceversa. Diga por qué el problema (P ′ ) es convexo.
19. Sea g : IRn −→ IR una función convexa y se define f (x) = eg(x) . Demuestre que f es
convexa.
20. Sea S un conjunto convexo en IRn . Demuestre que si g : S −→ IR es convexa y
f : IR −→ IR es convexa y creciente, entonces f ◦ g es convexa.
21. Sea g : IRn −→ IR una función convexa y suponga que
S = {x ∈ IRn / g(x) < 0} ̸= ∅.
Muestre que f es convexa, donde
−1
f (x) = , x∈S
g(x)
159
22. Utilizando argumentos de convexidad de funciones demuestre la siguiente propiedad
(Media geométrica vs Media aritmética): sean a1 , ..., an reales estrictamente positivos,
entonces v
u n
u∏ 1∑
n
tn
ai ≤ ai
i=1
n i=1
160
es un subgradiente de ψ en x̄.
Demuestre que:
√ x si x ∈] − 1, 1[
∂f (x) = 1 − x2
∅ si x ∈] − ∞, −1] ∪ [1, ∞[
(P ) mı́n f (x)
gi (x) ≤ 0, i = 1, . . . , m
F0 = {d : ∇f (x̄)t d < 0}
G = {d : ∇gi (x̄)t d ≤ 0, i ∈ I}
∀x ∈ C, ∀α > 0 ⇒ αx ∈ C
161
TS (x0 ) = {d ∈ IRn tal que ∃dk → d, ∃tk → 0, tk ≥ 0, x0 + tk dk ∈ S ∀k}
3. Considere una caja rectangular situada en el primer octante, con uno de sus vértices
en el origen, las tres caras adyacentes a los planos formados por los ejes coordenados y
el vértice opuesto w = (x, y, z) restringido a la superficie del paraboloide de ecuación
x2 + y 2 + z = 1. Determine las coordenadas de w para que la caja sea de volumen
máximo. Para ello:
4. Sea
(P ) mı́n −3x + y − z 2
x+y+z ≤0
−x + 2y + z 2 = 0
Escriba las ecuaciones de KKT para (P ) y resuelva (P ) a partir de allı́.
mı́n x2 + y 2
x+y =5
xy ≥ 4
(x − 4)2 + (y − 2)2 ≤ 1
162
6. (a) Sea x0 ∈ IRn , A ∈ Mm×n (IR) y b ∈ IRm . Considere el siguiente problema
1
(P ) mı́n ∥x − x0 ∥2
2
Ax ≤ b
Muestre que los multiplicadores de KKT deben satisfacer:
uT AAT u = uT (Ax0 − b)
u ≥ 0
u ∈ IRm
(b) Usando lo anterior, resuelva
1 2
mı́n (x + y 2 + z 2 )
2
x + y + z ≤ −3
163
a) Argumente la existencia de solución de (P ).
b) Si x̄ es mı́nimo local de (P ) muestre que existe λ̄ ∈ IR tal que:
′
fi (x̄i ) + λ̄ = 0 ∀i tal que x̄i > 0
′
fi (x̄i ) + λ̄ ≥ 0 ∀i tal que x̄i = 0
pT x + α
(P ) mı́n
qT x + β
Ax ≤ b
x≥0
Sea
(P ′ ) mı́n pT y + αz
Ay − zb ≤ 0
q T y + βz = 1
y, z ≥ 0
Demuestre que ambos problemas son equivalentes, en el sentido que se indica a conti-
nuación.
Use lo anterior para deducir una solución óptima del problema siguiente:
−2x1 + x2 + 2
(Q) mı́n
x1 + 3x2 + 4
−x1 + x2 ≤4
2x1 + x2 ≤ 14
x2 ≤6
x1 , x2 ≥0
164
9. Sea el problema:
mı́n x21 + x22 − 6x1 − 8x2
x21 + x22 − 2x1 − 4x2 ≥ 0
x1 ≤ 2
x2 ≤ 2
x1 ≥ 0
x2 ≥ 0
∑
n
(P ) máx xi
n ( )2
i=1
∑ xi
≤ b
i=1
ai
11. Una empresa fabrica un producto (en cantidad que denominamos x), que vende en
el mercado a un precio de 1 por unidad. Para generar este producto y ser capaz de
venderlo, la empresa necesita de un insumo en cantidad y, que compra en el mercado
a un precio de 1 por unidad. La cantidad del insumo y que necesita para producir x
viene dada por la regla de producción:
y = x2
Por restricciones de disponibilidad del mercado suponga que la empresa se enfrenta a
la restricción adicional:
x2 + y 2 ≤ 4
165
La ganancia por venta G viene dada por la cantidad x que se vende en el mercado
(asuma que todo lo que se produce se vende), mientras que el costo de producción
C viene dado por la cantidad del insumo y que se requiere para producir x. De esta
manera las utilidades son G − C.
13. Use las condiciones de KKT para decidir si x̄ = (2/3, 4/3, 1)T y x̄ = (4/5, 6/5, 0)T son
soluciones del problema:
166
14. Resuelva utilizando las condiciones de KKT
mı́n x2 + y 2
x+y = 5
xy ≥ 4
(x − 4) + (y − 2)2 ≤ 1
2
16. Use las condiciones de KKT para decidir si x̄ = (2/3, 4/3, 1)T y x̄ = (4/5, 6/5, 0)T son
soluciones del problema:
mı́n −2x1 − 6x2 − 2x1 x2 + x21 + 2x22 + 2x23
x1 + x2 ≤ 2
−x1 + 2x2 ≤ 2
x3 ≤ 2
1 2 1 2
(Pκ ) mı́n x + x − x1 − 2x2
2 1 2 2
x1 + x2 ≥ κ
x1 , x2 ≥ 0
167
donde κ ∈ IR. Diremos que una instancia de esta familia de problemas, es considerar
(Pκ ) para un κ ∈ IR fijo.
18. Sea
(P ) mı́n −3x1 + x2 − x23
s.a. x1 + x2 + x3 ≤0
−x1 + 2x2 + x23 = 0
Escriba las ecuaciones de KKT para (P ) y encuentre úselas para encontrar la solución
del problema.
19. Considere las funciones fi : IRn+ −→ IR, i = 1, . . . , k, convexas y diferenciables. Defini-
mos la función
f (x) = máx{f1 (x), . . . , fk (x)}
Considere además el problema
(P ) mı́n f (x)
x≥0
a) Demuestre que todo mı́nimo local de (P ) es un mı́nimo global.
b) Demuestre que el problema (P ) es equivalente al problema
(P ′ ) mı́n t
fi (x) ≤ t i = 1, . . . , k
x≥0
en el sentido que una solución de (P ) permite deducir en forma trivial una solución
de (P ′ ) y viceversa.
168
c) Sean x̄ una solución de (P ) e I = {i = 1, ..., k : fi (x̄) = f (x̄)}. Demuestre que
existen µi ≥ 0, i ∈ I y v ∈ IRn+ tales que
∑
µi ∇fi (x̄) = v
i∈I ∑
µi = 1
i∈I
x̄T v = 0
21. Considere
(P ) mı́n f (x)
gi (x) ≤ 0, i = 1, . . . , m
(P L) mı́n ∇f (x̄)t d
∇gi (x̄)t d ≤ 0 i ∈ I
−1 ≤ dj ≤ 1 j = 1, . . . , m
169
(b) Sean fi : IR → IR, i = 1, ..., n funciones derivables. Considere el siguiente problema
de minimización:
{ n }
∑ ∑
n
(P ) mı́n fi (xi ) / xi = 1, xi ≥ 0, i = 1, . . . , n
i=1 i=1
170
2. Considere el problema de programación lineal:
a) Usando Fase I del algoritmo Simplex, determine un punto extremo del poliedro
factible de (P ).
b) A partir de la base obtenida, resuelva (P ) usando Fase II del algoritmo Simplex.
(P ) mı́n f (x1 , x2 )
x1 + |x2 | ≤ 1
x1 ≥0
171
5. (a) Considere el poliedro P definido por:
−x1 − 2x2 + x3 − x4 = 3
−2x1 + 3x2 + x4 = 3
x1 , x2 , x3 , x4 ≥ 0
Usando los teoremas de caracterización, encuentre todos los puntos extremos tales
que x1 = 0 y pruebe que (1, 0, 3, 2) es dirección extrema de P.
(b) Considere el siguiente problema lineal:
(P ) mı́n x1
(x1 , x2 , x3 , x4 ) ∈ P
Diga por qué este problema es acotado. Determine el conjunto solución y el valor
óptimo de (P ).
-γ 0 0 2 0 10
-1 0 1 6 0 4
α 1 0 -4 0 1
0 0 0 3 1 θ
172
b) El problema es no acotado ¿Cuál es dirección extrema correspondiente a este no
acotamiento?
c) La solución en curso es óptima pero no es única (indique el conjunto solución).
d) La solución en curso es factible, pero no es óptima (realice, a partir de ella, una
iteración más).
8. Sea
(P ) mı́n cT x
Ax = b
x ≥0
Demuestre que al final de la Fase I del algoritmo Simplex, en el caso de encontrar
una base factible inicial para (P ), los costos reducidos de las variables artificiales (no
básicas) son todos iguales a 1.
(P ) mı́n y1 + y3
y1 + y2 − y3 ≤ 0
y2 + 3y3 = 1
y1 , y 2 , y 3 ≥ 0
173
10. Considere el problema:
(Pα ) mı́n z(α) = αx1 + x3
x1 − x2 + x3 = 1
−x1 + x3 + x5 = 2
x1 − x3 + x4 = 3
x1 , x2 , x3 , x4 , x5 ≥ 0
174
8.5. Dualidad en Programación Lineal y Aplicaciones
1. Sea (P ) el problema
máx cT x
Ax = 0
x≥0
y suponga que es acotado. Demuestre que x̄ = 0 es solución de (P ).
2. a) Sean c ∈ IRn , b ∈ IRm y A ∈ Mm×n (IR). Considere el par primal/dual siguiente:
(P ) máx{cT x: Ax ≤ b, x ≥ 0 }
(D) mı́n{bT y: AT y ≥ c, y ≥ 0 }
Sean x̄, ȳ ∈ IRn primal y dual factibles, respectivamente. Desmuestre que x̄, ȳ son
óptimos respectivos si y solamente si
(b − Ax̄)T ȳ = 0
(AT ȳ − c)T x̄ = 0
máx x1 + x2 + x3
x1 + x2 ≤ 10
2x1 + x3 ≤ 20
x1 , x2 , x3 ≥ 0
Usando la parte a), demuestre que x̄ = (0, 10, 20)T es óptimo y determine una
solución del problema dual.
3. Escriba el problema dual de
(P ) mı́n −20x1 −16x2 −12x3
x1 +x4 = 400
2x1 +x2 +x3 +x5 = 1000
2x1 +2x2 +x3 +x6 = 1600
xi ≥ 0 i = 1, . . . , 6
y usando el Teorema de Holgura Complementaria, demuestre que
175
4. Considere el problema
(P ) mı́n x1 + x2 − 4x3
x1 + x2 + 2x3 + x4 = 9
x1 + x2 − x3 + x5 = 2
−x1 + x2 + x3 + x6 = 4
x1 , x2 , x3 , x4 , x5 , x6 ≥ 0
a) Encuentre el dual del problema (P ).
b) Verifique que el punto x∗ = (1/3, 0, 13/3, 0, 6, 0) es factible para (P ).
c) Demuestre usando el teorema de holgura complementaria que el punto x∗ de la
parte anterior es solución del problema (P ).
d) Encuentre una solución para el problema dual, descrito en la parte a).
5. Deduzca un dual para
mı́n 2x1 + 3x2 + 5x3
x1 + x2 − x3 ≥ −5
|8x1 − 7x2 + 5x3 | ≤ 13
−6x1 + 7x2 − 9x3 = 15
x1 , x2 ≥ 0
6. Encuentre el dual de
(P ) mı́n 2x1 + 3x2 + 5x3
x1 + 12x2 − x3 ≥ −5
8x1 − 7x2 + 5x3 ≤ 13
−6x1 + 7x2 − 9x3 = 15
x2 , x3 ≥ 0
Su solución debe ser un problema (D) en el cual los costos son los recursos de (P )
y viceversa, y la matriz de coeficientes debe ser la transpuesta de aquella de (P ).
Justifique adecuadamente sus pasos.
7. Sea
(P ) mı́n ψ(x), x ∈ P = {x ∈ IRn / Ax = b, x ≥ 0},
donde ψ(x) = máx{cT1 x + d1 , . . . , cTk x + dk } y c1 , . . . , ck ∈ IRn , d1 , . . . , dk ∈ IR.
176
8. Considere el siguiente problema de programación lineal:
10. Sea
(P ) mı́n x1 + 2x2 + x3
x1 + 3x2 + x3 ≥ 4
x1 + 2x2 − x3 ≥ 6
x1 + x3 ≤ 12
x1 , x2 , x3 ≥0
177
a) Transforme (P ) en un problema canónico y aplique Fase I para encontrar una
base inicial factible.
b) Pase a la Fase II y encuentre la solución óptima de (P ).
c) Transforme (P ) de modo de aplicar el algoritmo Simplex-dual y resuélvalo usando
dicho algoritmo.
d) Es única la solución de (P )? Justifique mediante el cuadro final del Simplex en
las partes anteriores.
e) Usando el teorema de holgura complementaria, encuentre una solución del pro-
blema dual de (P ). Diga si es única y por qué.
mı́n cT x
Ax = b
l≤ x ≤u
donde c, l, u ∈ IRn , b ∈ IRm y A ∈ Mmn , son dados. Indique bajo qué condiciones este
dual posee una solución factible.
1
0 9 0 11 2
294
1 6 0 4 -1 36
1
0 -1 1 -1 2
6
178
max −x1 + 2x2
s.a −3x1 + 5x2 ≤ 15
−x1 + 4x2 ≤ 20
7x1 + 4x2 ≤ 84
x1 , x2 ≥ 0
179
15. Un parque de diversiones requiere dividir su nuevo terreno de 50 hectáreas en tres ca-
tegorı́as: Tiendas, Comida y Entretenciones. Cada hectárea usada para Entretenciones
genera un beneficio de 150 US$/hora; cada hectárea de Comida, 200 US$/hora y una
de Tiendas, 300 US$/hora. Además, existe una serie de restricciones sobre como se
debe dividir el terreno:
180
16. Considere el problema de programación lineal:
(P ) mı́n z = 2x1 + x2
3x1 + x2 ≥3
4x1 + 3x2 ≥6
x1 + 2x2 ≤3
x1 , x2 ≥0
a) Escriba el problema dual (D) asociado a (P ).
b) Resuelva el problema (P ), usando el método simplex-dual. Para esto, escriba el
problema (P ) en forma canónica y utilice como base dual-factible [x3 , x4 , x5 ].
c) Si cambia z a z ′ = αx1 + x2 . ¿Para qué valores de α la base óptima no cambia?
17. Considere siguiente problema:
máx −5x1 + 5x2 + 13x3
−x1 + x2 + 3x3 ≤ 20
12x1 + 4x2 + 10x3 ≤ 90
x1 , x2 , x3 ≥ 0
Haciendo que x4 , x5 sean las variables de holgura, la tabla óptima de Simplex queda:
0 0 2 5 0 100
-1 1 3 4 0 20
16 0 -2 -4 1 10
181
c) Introduzca una nueva restricción dada por 2x1 + 3x2 + 5x3 ≤ 50
d) Cambie la segunda restricción por 10x1 + 5x2 + 10x3 ≤ 100
18. Considere un problema de maximización con todas las restricciones del tipo “ ≤ ” tal
que la tabla óptima del Simplex es:
x1 x2 x3 x4 x5 z̄
0 0 1/4 1/4 0 5
0 1 1/2 -1/2 0 2
1 0 -1/8 3/8 0 3/2
0 0 1 -2 1 4
182
5
e) Si b cambia a b = 4 (en el problema original), ¿cuál es el conjunto de solu-
′
1
ciones óptimas?
f) Si se introduce (al problema original)
una nueva actividad u, cuyo costo unitario
−1
es 4 y columna correspondiente es −3, ¿cuál es la nueva solución óptima?
1
g) Si se agrega (al problema original) la restricción −x1 − x2 − x3 ≤ −5, ¿cuál es la
nueva solución óptima?
20. Considere
(P ) mı́n 9x2 +x3 −2x5 −x6
5x2 +50x3 +x4 +x5 = 10
x1 −15x2 +2x3 =2
x2 +x3 +x5 +x6 =6
xi ≥0 i = 1, . . . , 6
a) Resuelva (P ).
b) Resuelva (P ), pero suponiendo que el coeficiente de x5 en la función objetivo es
c5 = 1 (en lugar de -2).
c) Suponga que al problema (P ) se le modifica el recurso b1 de manera que b1 = 10α.
¿Para que valores de α la base óptima no cambia?
d) ¿Qué sucede si al problema (P ) se le agrega la variable x7 , con costo c7 = 1 y
vector columna (0, −1, 0)T ?
e) ¿Que sucede si a (P ) se le agrega la restricción x1 + x2 + x3 + x4 + x5 + x6 ≤ β?
Analice en función de β.
183
b) A partir de la base obtenida en a), resuelva (P ) usando la Fase II del algoritmo
Simplex.
c) Determine la solución óptima del problema dual de (P ).
d) Si se agrega la restricción: x1 + x2 + x3 ≤ 5 al problema (P ), determine la nueva
solucion óptima o justifique por qué no existe.
e) Determine la región de los recursos (coeficientes del lado derecho del sistema) para
la cual la base encontrada en (b) es óptima para (P ).
f) Determine el rango de variación del costo de x1 de manera que la base óptima
encontrada en (b) no cambie.
22. Usted es empresario del Transantiago y debe transportar pasajeros en el rango horario
9:00 a 10:00 AM, según el siguiente esquema:
b12=$380 b24=$40
b23=$80
1 4
b13=$420 b34=$0
Los beneficios unitarios bij dependen del tramo y están indicados en los arcos.
Suponga que:
Desde el nodo 1 hacia los nodos 2 y 3, no puede transportar más de 1000 pasajeros
en total.
No puede llevar más de 800 pasajeros en total hasta el nodo 4 (desde los nodos 2
y 3).
No puede transportar más de 500 pasajeros en ningún tramo.
184
Todos los pasajeros que toman un bus en el nodo 1, transbordan en los nodos 2
y/o 3, pagando el valor que corresponde al nuevo tramo, y llegan al nodo 4.
Pueden subir pasajeros en nodos 2 y 3.
x12 = 500, x13 = 300, x23 = 200, x24 = 300, x34 = 500
∀(i, j) ∈ A, i ∈ P ∨ j ∈ P
∀i ∈ N , ∃j ∈ N , (i, j) ∈ E ∨ (j, i) ∈ E
185
vigilar todas las calles que converjan a ese punto i. Sea P el conjunto de los carabi-
neros con |P | > |N |. Suponga que el costo de mandar el carabinero p al punto n es
cpn . Además, para evitar distracciones sólo puede haber un carabinero por punto clave.
Formule un problema de programación lineal (posiblemente entera) tal que todas las
calles esten bajo supervisión policial, minimizando el costo.
186
a) Modele el problema anterior como un problema de programación lineal.
b) Utilizando el método de saturación, encuentre una solución factible.
c) Verifique si la solución de la parte anterior es óptima.
5. Considere tres centros productivos O1, O2 y O3, con ofertas respectivas de 5, 25 y 25.
Hay además dos centros D1 y D2, con demandas 15 y 30. Suponga que la matriz de
costos unitarios de transporte es
D1 D2
O1 9 12
O2 1 1
O3 2 2
7. Se desean embarcar 40 mil toneladas de cobre desde los puertos de Antofagasta y San
Antonio (20 mil toneladas desde cada puerto), con destino a las ciudades de Hong
Kong, New York y Tokio. Estas ciudades demandan 15 mil, 15 mil y 10 mil toneladas
del mineral, respectivamente. Supongamos que las rutas entre los puertos y las ciudades
destino son fijas y conocidas, y que los costos asociados a transportar mil toneladas
(medidos en millones de pesos) son estimados en la siguiente tabla:
187
Origen\Destino Hong Kong New York Tokyo
Antofagasta 10 11 20
San Antonio 6 9 8
Notar que la oferta excede a la demanda. Suponga que lo sobrante se manda a un bo-
tadero, a costo unitario 10 para el oferente 1, 15 para el oferente 2 y 8 para el oferente 3.
¿Qué ocurre (cómo cambia la solución) si el costo de enviar a botadero fuese nulo
para los tres oferentes?
9. Considere el grafo G = ({1, 2, 3, 4}, {(1, 2), (1, 3), (3, 2), (2, 4), (3, 4)}) con capacidades
y costos dados por la siguiente tabla:
10. Considere un problema de flujo de costo mı́nimo en una red de 5 nodos y 9 arcos. Los
nodos se enumeran de 1 a 5 y los costos unitarios son:
c12 = 4, c13 = 4, c23 = 2, c24 = 2, c25 = 6, c34 = 1, c35 = 3, c45 = 2, c53 = 1.
188
Las capacidades máximas de los arcos son:
u12 = 15, u13 = 8, u23 = ∞, u24 = 4, u25 = 10, u34 = 15, u35 = 5, u45 = ∞, u53 = 4.
El nodo 1 tiene oferta 20 y los nodos 4 y 5 tienen demanda 10 cada uno; los demás son
de trasbordo.
a) Dibuje el grafo correspondiente, indicando los datos en los arcos.
b) Dibuje una solución básica factible, indicando sobre los arcos los valores de los
flujos. Indique con lı́neas punteadas los arcos no básicos con flujos no nulos.
c) Diga si es solución óptima (justifique).
d) Itere una vez, si es necesario. Diga si la nueva solución es óptima y, de ser ası́, si
es única.
Encuentre una aproximación del óptimo ocupando 2 iteraciones del método de Newton
partiendo de (x0 , y0 ) = (0, 3). Realice además 2 iteraciones del método del gradiente.
2. a) Considere el siguiente problema de optimización:
(P ) mı́n f (x1 , x2 ) = x21 + (x2 + 1)4
Haga dos iteraciones con el método de Newton para (P ). Tome como punto de
partida (1,0) y el paso tk = 1, ∀k ∈ IN.
b) Repetir la parte a), pero hacer una sola iteración, usando el paso
αk = arg mı́n f (xk + tdk ),
donde xk es el punto inicial y dk es la dirección de Newton.
3. Considere el problema:
mı́n −2x1 − 6x2 − 2x1 x2 + x21 + 2x22 + 2x23
x1 + x2 ≤ 2
−x1 + 2x2 ≤ 2
x3 ≤ 2
189
Haga dos iteraciones del método de direcciones admisibles, a partir del punto inicial
x0 = (0, 0, 0)T . Chequee optimalidad en cada etapa.
4. Sea el problema
Hacer dos iteraciones del método de penalización, usando penalización cuadrática, con
µ = 0,1, µ = 1 y x0 = (0, 0).
6. Considere el problema:
(P ) mı́n x21 + 2x22 − 2x1 x2 − 4x1 − 6x2
x1 + x2 ≤ 3
x1 + 10x2 ≤ 10
x 1 , x2 ≥ 0
Realice dos iteraciones del método de direcciones admisibles, a partir x0 = (0, 0).
Chequee, en cada iteración, si está o no en presencia de una solución estacionaria. Si
alcanza un punto estacionario, se puede afirmar que es un mı́nimo?
Debe explicitar claramente los subproblemas que resuelva, tanto para la elección de la
dirección como para el paso. Si le conviene, puede usar procedimientos gráficos para la
resolución de los subproblemas.
7. Considere el siguiente problema de optimización
(P ) mı́n 3x2 + 2y 2 − 6x − 4y + 3
x2 + y 2 ≤ 1
x+y ≤1
190
a) Demuestre que el problema (P ) tiene solución.
b) Grafique las curvas de nivel de la función objetivo y el conjunto factible.
c) Determine si D(⃗x)∩G(⃗x) = ∅, es decir, si la intersección del conjunto de direcciones
de descenso con el conjunto de direcciones admisibles es vacı́a, para ⃗x1 = (1; 0)
y ⃗x2 = (0,6; 0,4). En base a los resultados obtenidos, clasifique los dos puntos
anteriores.
⃗
Ind.: Recuerde D(⃗x) = {d/∇f (⃗x) · d⃗ < 0} y G(⃗x) = {d/∇g
⃗ x) · d⃗ < 0, ∀i ∈ I}, donde
i (⃗
I es el conjunto de indices de restricciones activas en el punto ⃗x.
191
Bibliografı́a
[1] Bazaraa, M.S., H.D. Sherali, C.M. Shetty. Nonlinear Programming: Theory and Algo-
rithms. Wiley and Sons, 2006.
[2] Bazaraa, M.S., J.J. Jarvis, H.D. Sherali. Programación lineal y flujo en redes. Limusa,
1998.
[3] Bazaraa, M.S., J.J. Jarvis, H.D. Sherali. Linear Programming and Network flows. Wiley
and Sons, 2010.
[6] Peressini, A.L., F.E. Sullivan, J.J. Uhl. The Mathematics of Nonlinear Programming.
Springer Verlag (Undergraduate Texts in Mathematics), 1988.
[7] Williams, H. P. Model Building in Mathematical Programming. Wiley and Sons, 2013.
192