Ortiz Varas Vera

Universidad de los Andes
Facultad de Ingenier´ıa y Ciencias Aplicadas

Apuntes del Curso

Introducci´
on a la Optimizaci´
on

´Indice general
1. Modelamiento en Optimizaci´
on
1.1. Introducci´
on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Problemas cl´
asicos de modelamiento . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Problemas Resueltos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4
4
6

2. Problemas equivalentes y existencia de ´
optimos
28
2.1. Introducci´
on a problemas equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.2. Existencia de soluciones ´
optimas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3. Problemas Resueltos . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . 29
3. Convexidad
3.1. Introduci´
on . . . . . .
3.1.1. Aplicaciones de
3.2. Funciones convexas . .
3.3. Problemas Resueltos .

. . . . . . . .
la convexidad
. . . . . . . .
. . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

..
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

40
40
40
41
42

4. Optimizaci´
on sin restricciones
51
4.1. Introducci´
on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5. Optimizaci´
on con restricciones
54
5.1. Introducci´
on . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.2. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6. Programaci´
on Lineal
6.1. Definiciones b´
asicas . . . . . . . . .
6.2. Algoritmo Simplex . . . . . . . . .
6.2.1. Fase I . . . . . . . . . . . .
6.2.2. Casos especiales del m´etodo
6.3. Problemas Resueltos . . . . . . . ..
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

62
62
63
65
65
66

7. Dualidad en Programaci´
on Lineal
75
7.1. Introducci´
on . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.3. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

2

8. Programaci´
on Lineal Entera
77
8.1. Programaci´
on Entera . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . 77
8.1.1. Algoritmo “Branch & Bound” . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.2. Problemas Resueltos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

3

Cap´ıtulo 1

Modelamiento en Optimizaci´
on
1.1.

Introducci´
on

En este curso estudiaremos el problema
min{f (x) | x ∈ Ω}.

(P)
donde f :

❘n → ❘ y Ω ⊆ ❘n . Diremos que x∗ ∈ Ω essoluci´on de (P) si satisface
f (x∗ ) ≤ f (x)∀x ∈ Ω.

Denotaremos por v(P ) al valor ´
optimo del problema y argmin(P ) o bien S(P ) ⊆ ❘n al conjunto
de todas las posibles soluciones, esto es, S(P ) = {x∗ ∈ ❘n | f (x∗ ) = v(P )}. Por supuesto, el
problema de minimizaci´
on no siempre tiene soluci´on, por ejemplo, el problema de encontrar x ∈ ❘
que minimice la expresi´
on ex satisface v = 0 pero S = ∅.
Lafunci´on f se denomina funci´
on objetivo, llamaremos conjunto factible o de restricciones al conjunto Ω, un punto x ∈ Ω se denomina punto factible, si el conjunto Ω es vac´ıo diremos que el
problema es infactible.
Si existe una sucesi´
on (xk )k ⊆ Ω satisfaciendo f (xk ) → −∞ diremos que el problema es no acotado.
En forma an´aloga se define el problema de maximizaci´on:
max{f (x) | x ∈ Ω}....