Gfdh

Universidad de Chile
Departamento de Ingeniería Matemática

Problemas de Optimización para Estudiantes de
Ingeniería
Capítulo 1: Matemáticas para la Optimización
Capítulo 2: Condiciones de Optimalidad
Capítulo 3: Programación Lineal
Capítulo 4: Dualidad en Programación Lineal
Capítulo 5: Modelos y Algoritmos de flujos en redes

Autores:
Jorge A MAYA A.
Cristopher H ERMOSILLA J.Nicolás H ERNÁNDEZ S.

14 de junio de 2009

Índice general
1. Matemáticas para la Optimización

2

1.1. Conjuntos Convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .

7

1.2. Funciones Convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.Caracterización de Optimalidad

16

2.1. Optimización con Restricciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3. Programación Lineal23

3.1. Algoritmo Simplex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4. Dualidad en Programación Lineal

32

4.1.Dualidad y Análisis de Sensibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5. Modelos y alg. para flujos en redes

42

5.1. Problemas detransporte y de flujo a costo mínimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.1.1. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.1.2. Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1

Capítulo 1

Matemáticas para la Optimización
1.1.

Conjuntos Convexos1.1.1.

Problemas Resueltos

P1. Considere la norma euclideana en las siguientes definiciones:
Dados v ∈ R3 \{0} y ε > 0, se llama Cono de Bishop-Phelps al conjunto K (v, ε) definido por:
K (v, ε) = {x ∈ R3 :

εv

x ≤ v, x }

(1.1.1)

Dados a, b ∈ R2 y γ ∈ [0, 1], se llama Pétalo de Penot al conjunto Pγ (a, b) definido por:
Pγ (a, b) = {x ∈ R2 :

γ a−x + x−b ≤ b−a }

(1.1.2)Dados C ⊆ R2 y x0 ∈ R2 , se llama Gota de Danes al conjunto [C, x0 ] definido por:
[C, x0 ] = Co({x0 } ∪ C)

(1.1.3)

a) Pruebe que K (v, ε) es convexo para cualquier v ∈ R3 \{0} y ε > 0
b) Pruebe que Pγ (a, b) es convexo para cualquier a, b ∈ R2 y γ ∈ [0, 1]
c) Pruebe que [C, x0 ] = {x0 + t (c − x0 ) : t ∈ [0, 1], c ∈ C} ∀C ⊆ R2 convexo y x0 ∈ R2
d) Pruebe que dados a, b ∈ R2 y γ ∈ (0, 1)entonces B(b, r) ⊆ Pγ (a, b), donde
1−γ
r = a−b
. Concluya que [c, B(b, r)] ⊆ Pγ (a, b) ∀c ∈ Pγ (a, b)
1+γ
Solución:
a) Sean v ∈ R3 \{0} y ε > 0 fijos, consideremos x, y ∈ K (v, ε) y t ∈ [0, 1].
Sea z = tx + (1 − t )y, veamos que z ∈ K (v, ε):
εv

z = ε v t x + (1 − t )y
≤ tε v

x + (1 − t )ε v

≤ t v, x + (1 − t ) v, x

y

(propiedades de normas)
(x, y ∈ K (v, ε))

= v, x...