Universidad de Valladolid ´ micas y Empresariales Facultad de Ciencias Econo Departamento de Econom´ıa Aplicada ´ n de Matema ´ticas Subseccio Esquemas te´ oricos de la asignatura de las licenciaturas en Econom´ıa y ADE - Derecho

´ ´ METODOS MATEMATICOS DE LA ECONOM´IA II. CONVEXIDAD ´ MATEMATICA ´ III. PROGRAMACION Confeccionados por los profesores Miguel Mart´ınez Panero ´ n Zapatero Juan Pablo Rinco

´ ´ METODOS MATEMATICOS DE LA ECONOM´IA

II. CONVEXIDAD 3. CONJUNTOS CONVEXOS ´ 4. FUNCIONES CONCAVAS Y CONVEXAS ´ MATEMATICA ´ III. PROGRAMACION ´ A LA PROGRAMACION ´ MATEMATICA ´ 5. INTRODUCCION ´ CLASICA ´ 6. PROGRAMACION SIN RESTRICCIONES ´ CLASICA ´ 7. PROGRAMACION CON RESTRICCIONES DE IGUALDAD ´ CON RESTRICCIONES DE DESIGUAL8. PROGRAMACION DAD ´ LINEAL 9. PROGRAMACION

´todos Matema ´ ticos Me

Convexidad

TEMA 3. CONJUNTOS CONVEXOS 3.1 Convexidad conjuntista. V´ertice. Combinaci´on convexa 3.2 Operaciones con conjuntos convexos 3.3 Caracterizaci´on de conjunto convexo 3.4 Conjuntos convexos notables 3.5 Teoremas de separaci´on

2

´todos Matema ´ ticos Me

3

Convexidad

3

CONJUNTOS CONVEXOS

3.1

3.1.1

´ CONVEXIDAD CONJUNTISTA. VERTICE. COMBINA´ CONVEXA CION ´ DEFINICION

Dados x¯, y¯ ∈ Rn, el segmento con extremos x¯, y¯ es el conjunto: [¯ x, y¯] = {λ¯ x + (1 − λ)¯ y | λ ∈ [0, 1]}.

3.1.2

´ DEFINICION

Un conjunto C ⊆ Rn es convexo si y s´olo si x¯, y¯ ∈ C ⇒ [¯ x, y¯] ⊆ C.

3.1.3

OBSERVACIONES Y EJEMPLOS

1. M´as expl´ıcitamente, C ⊆ Rn es convexo si y s´olo si ) x¯, y¯ ∈ C ⇒ λ¯ x + (1 − λ)¯ y ∈ C. λ ∈ [0, 1] 2. El conjunto vac´ıo es convexo. 3. Un conjunto finito no vac´ıo es convexo si y s´olo si consta de un u´nico punto.

´todos Matema ´ ticos Me 3.1.4

Convexidad

4

´ DEFINICION

Sea C ⊆ Rn un conjunto convexo no vac´ıo. Un punto z¯ ∈ C es un v´ertice o punto extremo de C si y s´olo si z¯ ∈ [¯ x, y¯] ⊆ C ⇒ (¯ z = x¯) ∨ (¯ z = y¯). 3.1.5

´ DEFINICION

Un punto x¯ ∈ Rn es combinaci´on convexa de x¯1, . . . , x¯m ∈ Rn si y s´olo si existen λ1, . . . , λm ≥ 0 tales que λ1 + · · · + λm = 1 y x¯ = λ1x¯1 + · · · + λmx¯m. 3.2

OPERACIONES CON CONJUNTOS CONVEXOS

1. La intersecci´on de conjuntos convexos es un conjunto convexo. 2. Dados S, T ⊆ Rn convexos no vac´ıos, el conjunto S + T = {¯ s + t¯ | s¯ ∈ S, t¯ ∈ T } ⊆ Rn es convexo. 3. Dados S ⊆ Rn, T ⊆ Rm convexos no vac´ıos, el conjunto S × T = {(¯ s, t¯) | s¯ ∈ S, t¯ ∈ T } ⊆ Rn+m es convexo. 4. Dados S ⊆ Rn convexo no vac´ıo y α ∈ R, el conjunto αS = {α¯ s | s¯ ∈ S} ⊆ Rn es convexo.

´todos Matema ´ ticos Me 3.2.1

Convexidad

5

´ OBSERVACION

La uni´on de conjuntos convexos no es, en general, un conjunto convexo. Por ejemplo, consid´erese la uni´on del primer y tercer cuadrantes de R2. 3.3 3.3.1

´ DE CONJUNTO CONVEXO CARACTERIZACION ´ DEFINICION

La envolvente convexa de un conjunto C ⊆ Rn, e(C), es el conjunto de todas las combinaciones convexas de puntos de C. Es decir, x¯ ∈ e(C) si y s´olo si existen x¯1, . . . , x¯m ∈ C, λ1, . . . , λm ≥ 0, tales que λ1 + · · · + λm = 1 y x¯ = λ1x¯1 + · · · + λmx¯m. 3.3.2

´ PROPOSICION

La envolvente convexa de un conjunto C ⊆ Rn es el menor conjunto convexo, respecto a la relaci´on de inclusi´on, que lo contiene. 3.3.3

COROLARIO

Dado C ⊆ Rn, son equivalentes: 1. C es convexo. 2. C = e(C). 3. Toda combinaci´on convexa de puntos de C pertenece a C.

´todos Matema ´ ticos Me

3.4 3.4.1

Convexidad

6

CONJUNTOS CONVEXOS NOTABLES ´ DEFINICION

Dados u¯ ∈ Rn no nulo y a ∈ R, el conjunto H = {¯ x ∈ Rn | u¯ · x¯ = a} es un hiperplano. 3.4.2

´ DEFINICION

Dados u¯ ∈ Rn no nulo y a ∈ R, los conjuntos • {¯ x ∈ Rn | u¯ · x¯ ≤ a}, {¯ x ∈ Rn | u¯ · x¯ ≥ a} son semiespacios cerrados, x ∈ Rn | u¯ · x¯ < a}, {¯ x ∈ Rn | u¯ · x¯ > a} son semiespacios • {¯ abiertos. 3.4.3

´ DEFINICION

Un conjunto C ⊆ Rn es un politopo si y s´olo si es intersecci´on finita de semiespacios cerrados de Rn. 3.4.4

´ DEFINICION

Un conjunto C ⊆ Rn es un poliedro si y s´olo si es un politopo acotado.

´todos Matema ´ ticos Me 3.4.5

Convexidad

7

´ DEFINICION

Un conjunto C ⊆ Rn es un s´ımplex si y s´olo si es un poliedro de exactamente n + 1 v´ertices

3.4.6

TEOREMA

Todo hiperplano, semiespacio, politopo, poliedro o s´ımplex es un conjunto convexo.

3.4.7

´ DEFINICION

Un conjunto C ⊆ Rn es un cono convexo si y s´olo si es un conjunto convexo y se verifica: x¯ ∈ C λ≥0

3.5 3.5.1

) ⇒ λ¯ x ∈ C.

´ TEOREMAS DE SEPARACION TEOREMA (Hiperplano l´ımite)

Dados un conjunto convexo C ⊆ Rn no vac´ıo, x¯0 ∈ Rn, x¯0 ∈ / C, existe un hiperplano H = {¯ x ∈ Rn | u¯ · x¯ = a} tal que x¯0 ∈ H y C ⊆ {¯ x ∈ Rn | u¯ · x¯ ≥ a} o bien C ⊆ {¯ x ∈ Rn | u¯ · x¯ ≤ a}.

´todos Matema ´ ticos Me 3.5.2

Convexidad

8

TEOREMA (Hiperplano soporte)

Dados un conjunto convexo C ⊆ Rn no vac´ıo y x¯0 ∈ ∂C, existe un hiperplano H = {¯ x ∈ Rn | u¯ · x¯ = a} tal que x¯0 ∈ H y C ⊆ {¯ x ∈ Rn | u¯ · x¯ ≥ a} o bien C ⊆ {¯ x ∈ Rn | u¯ · x¯ ≤ a}. 3.5.3

TEOREMA (Hiperplano separador)

Dados dos conjuntos convexos C1, C2 ⊆ Rn no vac´ıos tales que ◦

◦

C1 ∩ C2= ∅, existe un hiperplano H = {¯ x ∈ Rn | u¯ · x¯ = a} tal que C1 ⊆ {¯ x ∈ Rn | u¯ · x¯ ≥ a} y C2 ⊆ {¯ x ∈ Rn | u¯ · x¯ ≤ a}.

´todos Matema ´ ticos Me

Convexidad

9

´ TEMA 4. FUNCIONES CONCAVAS Y CONVEXAS 4.1 Convexidad funcional 4.2 Operaciones con funciones c´oncavas y convexas 4.3 Relaci´on entre convexidad conjuntista y funcional. Cuasiconvexidad 4.4 Caracterizaci´on de las funciones c´oncavas y convexas de clases C1 y C2 4.5 Optimizaci´on y convexidad. Teorema Local–Global

´todos Matema ´ ticos Me

Convexidad

10

´ FUNCIONES CONCAVAS Y CONVEXAS

4 4.1 4.1.1

CONVEXIDAD FUNCIONAL DEFINICIONES

Sean C ⊆ Rn convexo no vac´ıo y f : C −→ R. • La funci´on f es convexa si y s´olo si ) x¯, y¯ ∈ C ⇒ f (λ¯ x + (1 − λ)¯ y ) ≤ λf (¯ x) + (1 − λ)f (¯ y ). λ ∈ [0, 1] • La funci´on f es c´oncava si y s´olo si ) x¯, y¯ ∈ C ⇒ f (λ¯ x + (1 − λ)¯ y ) ≥ λf (¯ x) + (1 − λ)f (¯ y ). λ ∈ [0, 1] • La funci´on f es estrictamente convexa si y s´olo si  x¯, y¯ ∈ C    ⇒ f (λ¯ x + (1 − λ)¯ y ) < λf (¯ x) + (1 − λ)f (¯ y ). x¯ 6= y¯   λ ∈ (0, 1)  • La funci´on f es estrictamente c´oncava si y s´olo si  x¯, y¯ ∈ C    ⇒ f (λ¯ x + (1 − λ)¯ y ) > λf (¯ x) + (1 − λ)f (¯ y ). x¯ 6= y¯   λ ∈ (0, 1) 

´todos Matema ´ ticos Me 4.1.2

Convexidad

11

OBSERVACIONES

1. (Desigualdades de Jensen). Las definiciones anteriores se pueden extender inductivamente a combinaciones convexas de puntos de C. As´ı f es convexa si y s´olo si dados x¯1, . . . , x¯m ∈ C m X y λ1, . . . , λm ≥ 0 tales que λi = 1, se verifica i=1

f (λ1x¯1 + · · · + λmx¯m) ≤ λ1f (¯ x1) + · · · + λmf (¯ xm). Si f es c´oncava, cambia el signo de la desigualdad anterior (≥). En el caso de que f sea estrictamente convexa (resp. estrictamente c´oncava) hay que tomar x¯1, . . . , x¯m distintos dos a dos y λi ∈ (0, 1), ∀i ∈ {1, . . . , m}, as´ı como la desigualdad estricta: f (λ1x¯1 + · · · + λmx¯m) < λ1f (¯ x1) + · · · + λmf (¯ xm) (resp. > para f estrictamente c´oncava). 2. Si f es estrictamente c´oncava (resp. estrictamente convexa), entonces f es c´oncava (resp. convexa). 3. Los conceptos de funci´on c´oncava y funci´on convexa no son exhaustivos ni contrarios entre s´ı: existen funciones que no son ni c´oncavas ni convexas (un ejemplo son las funciones trigonom´etricas seno y coseno con dominio en R) y funciones que son a la vez c´oncavas y convexas (las funciones lineales, caso l´ımite en que la desigualdad de Jensen es una igualdad).

´todos Matema ´ ticos Me

Convexidad

12

4. Una funci´on puede tener distinto car´acter en cuanto a su concavidad o convexidad, es decir, distinta curvatura, dependiendo del conjunto convexo sobre el que est´e definida. As´ı, la funci´on seno con dominio en R no es c´oncava ni convexa, es c´oncava en [0, π], y convexa en [π, 2π]. 5. En dimensiones n = 1, 2 las definiciones anteriores tienen el siguiente significado geom´etrico: Una funci´on es convexa (resp. c´oncava) si y s´olo si la cuerda que une dos puntos cualesquiera de la gr´afica de la funci´on est´a por encima (resp. por debajo) de dicha gr´afica. En el caso no estricto se puede dar yuxtaposici´on de la cuerda sobre la gr´afica, pero si la convexidad o concavidad de la funci´on es estricta, la yuxtaposici´on no ha de darse m´as que en los puntos extremos de la cuerda. 6. Las funciones c´oncavas y convexas son continuas en el interior de su dominio de definici´on.

´todos Matema ´ ticos Me

4.2 4.2.1

Convexidad

13

´ OPERACIONES CON FUNCIONES CONCAVAS Y CONVEXAS ´ PROPOSICION

Sean C ⊆ Rn convexo no vac´ıo y f, g : C −→ R. 1. f , g convexas (resp. c´oncavas) ⇒ f + g convexa (resp. c´oncava). 2. f , g estrictamente convexas (resp. estrict. c´oncavas) ⇒ f +g estrictamente convexa (resp. estrict. c´oncava). 3. f convexa (resp. c´oncava), α ≥ 0 ⇒ αf convexa (resp. c´oncava). 4. f convexa (resp. c´oncava), α ≤ 0 ⇒ αf c´oncava (resp. convexa). 5. f estrictamente convexa (resp. estrict. c´oncava), α > 0 ⇒ αf estrictamente convexa (resp. estrict. c´oncava). 6. f estrictamente convexa (resp. estrict. c´oncava), α < 0 ⇒ αf estrictamente c´oncava (resp. estrict. convexa). 7. En particular, f convexa (resp. c´oncava) ⇒ −f c´oncava (resp. convexa). An´alogo para el caso estricto. 4.2.2

´ OBSERVACION

El apartado 7. de 4.2.1 permite trasladar los resultados v´alidos para funciones convexas a funciones c´oncavas y viceversa, sin m´as que cambiar de sentido las desigualdades.

´todos Matema ´ ticos Me

4.3

4.3.1

Convexidad

14

´ RELACION ENTRE CONVEXIDAD CONJUNTISTA Y FUNCIONAL. CUASICONVEXIDAD DEFINICIONES

Sean C ⊆ Rn no vac´ıo y f : C −→ R. • El grafo de f , G(f ), es el conjunto G(f ) = {(¯ x, y) ∈ C × R | f (¯ x) = y}. • El ep´ıgrafe de f , E(f ), es el conjunto E(f ) = {(¯ x, y) ∈ C × R | f (¯ x) ≤ y}. • El hip´ografo de f , H(f ), es el conjunto H(f ) = {(¯ x, y) ∈ C × R | f (¯ x) ≥ y}. • Dado α ∈ R, el α-corte inferior, Nα (f ), es el conjunto Nα (f ) = {¯ x ∈ C | f (¯ x) ≤ α}. • Dado α ∈ R, el α-corte superior, N α (f ), es el conjunto N α (f ) = {¯ x ∈ C | f (¯ x) ≥ α}.

´todos Matema ´ ticos Me 4.3.2

Convexidad

15

TEOREMA

Sean C ⊆ Rn convexo no vac´ıo y f : C −→ R. Se verifica: 1. f convexa ⇔ E(f ) convexo. 2. f c´oncava ⇔ H(f ) convexo. 3. f convexa ⇒ Nα (f ) convexo. 4. f c´oncava ⇒ N α (f ) convexo. 4.3.3

´ OBSERVACION

No son ciertos los rec´ıprocos de los dos u´ltimos apartados. As´ı, por ejemplo, una funci´on mon´otona tiene α-cortes (superiores e inferiores) convexos sin necesidad de ser c´oncava o convexa. 4.3.4

DEFINICIONES

Sean C ⊆ Rn convexo no vac´ıo y f : C −→ R. • La funci´on f es cuasiconvexa si y s´olo si Nα (f ) es convexo para todo α ∈ R. • La funci´on f es cuasic´oncava si y s´olo si N α (f ) es convexo para todo α ∈ R.

´todos Matema ´ ticos Me 4.3.5

Convexidad

16

COROLARIO

Sean C ⊆ Rn convexo no vac´ıo y f : C −→ R. Se verifica: 1. f convexa ⇒ f cuasiconvexa. 2. f c´oncava ⇒ f cuasic´oncava. 4.3.6

TEOREMA

Sean C ⊆ Rn convexo no vac´ıo y f : C −→ R. Se verifica: 1. La funci´on f es cuasiconvexa si y s´olo si ) x¯, y¯ ∈ C ⇒ f (λ¯ x + (1 − λ)¯ y ) ≤ max{f (¯ x), f (¯ y )}. λ ∈ [0, 1] 2. La funci´on f es cuasic´oncava si y s´olo si ) x¯, y¯ ∈ C ⇒ f (λ¯ x + (1 − λ)¯ y ) ≥ min{f (¯ x), f (¯ y )}. λ ∈ [0, 1] 4.4 4.4.1

´ DE LAS FUNCIONES CONCAVAS ´ CARACTERIZACION Y CONVEXAS DE CLASES C 1 y C 2 TEOREMA

Sean C ⊆ Rn abierto, convexo y no vac´ıo y f : C −→ R de clase C 1. Se verifica: 1. f convexa ⇔ ∀¯ x, y¯ ∈ C, f (¯ x) − f (¯ y ) ≥ ∇f (¯ y )(¯ x − y¯).

´todos Matema ´ ticos Me

Convexidad

17

2. f estrictamente convexa ⇔ ∀¯ x, y¯ ∈ C, x¯ 6= y¯, f (¯ x) − f (¯ y ) > ∇f (¯ y )(¯ x − y¯). 3. f c´oncava ⇔ ∀¯ x, y¯ ∈ C, f (¯ x) − f (¯ y ) ≤ ∇f (¯ y )(¯ x − y¯). 4. f estrictamente c´oncava ⇔ ∀¯ x, y¯ ∈ C, x¯ 6= y¯, f (¯ x) − f (¯ y ) < ∇f (¯ y )(¯ x − y¯).

4.4.2

´ OBSERVACION

En dimensiones n = 1, 2 los resultados anteriores tienen el siguiente significado geom´etrico: Una funci´on es convexa (resp. c´oncava) si y s´olo si la recta o plano tangente a la gr´afica en cada punto est´a bajo (resp. sobre) la misma. En el caso no estricto se puede dar yuxtaposici´on de la tangente sobre la gr´afica, pero si la convexidad o concavidad de la funci´on es estricta, la yuxtaposici´on no ha de darse m´as que en el punto de tangencia. 4.4.3

´ OBSERVACION

Dada una funci´on f : D −→ R, D ⊆ Rn abierto no vac´ıo, tal que f es de clase C 2 en D, identificaremos la matriz hessiana de f en x¯0, Hf (¯ x0), con la forma cuadr´atica que define sobre Rn.

´todos Matema ´ ticos Me 4.4.4

Convexidad

18

TEOREMA

Sean C ⊆ Rn abierto, convexo y no vac´ıo y f : C −→ R de clase C 2. Se verifica: 1. f convexa ⇔ ∀¯ x ∈ C, Hf (¯ x) definida positiva o semidefinida positiva. 2. f c´oncava ⇔ ∀¯ x ∈ C, Hf (¯ x) definida negativa o semidefinida negativa. x ∈ C, Hf (¯ x) definida positiva ⇒ f estrictamente con3. ∀¯ vexa. 4. ∀¯ x ∈ C, Hf (¯ x) definida negativa c´oncava. 4.4.5

⇒

f estrictamente

COROLARIO

Sean C ⊆ Rn abierto, convexo y no vac´ıo y f : C −→ R de clase C 2. Se verifica: 1. Si Hf (¯ x) es indefinida para alg´un x¯ ∈ C, entonces f no es c´oncava ni convexa. 2. Si Hf (¯ x) y Hf (¯ y ) son definidas, o semidefinidas y no nulas, positiva y negativa, respectivamente, para alg´un par de puntos x¯, y¯ ∈ C, entonces f no es c´oncava ni convexa.

´todos Matema ´ ticos Me 4.4.6

Convexidad

19

´ OBSERVACION

No es cierto el rec´ıproco de los dos u´ltimos apartados del teorema anterior. As´ı, por ejemplo, la funci´on f (x, y) = x4 + y 4 es estrictamente convexa; sin embargo, Hf (0, 0) = (0) es la matriz nula, que tiene asociada una forma cuadr´atica que no es definida positiva. 4.5 4.5.1

´ Y CONVEXIDAD. TEOREMA LOCALOPTIMIZACION GLOBAL DEFINICIONES. Extremos (u ´ optimos) de una funci´ on

Sean D ⊆ Rn no vac´ıo, f : D −→ R , x¯0 ∈ D. • x¯0 es un m´aximo local (o relativo) de f en D si y s´olo si existe r > 0 tal que ∀¯ x ∈ Br (¯ x0) ∩ D, f (¯ x0) ≥ f (¯ x). Si la desigualdad es estricta (>) siempre que x¯ 6= x¯0, entonces x¯0 es un m´aximo local estricto. • x¯0 es un m´ınimo local (o relativo) de f en D si y s´olo si existe r > 0 tal que ∀¯ x ∈ Br (¯ x0) ∩ D, f (¯ x0) ≤ f (¯ x). Si la desigualdad es estricta () siempre que x¯ 6= x¯0, entonces x¯0 es un m´aximo global estricto.

´todos Matema ´ ticos Me

Convexidad

20

• x¯0 es un m´ınimo global (o absoluto) de f en D si y s´olo si ∀¯ x ∈ D, f (¯ x0) ≤ f (¯ x). Si la desigualdad es estricta ( 0, existen x¯1, x¯2 ∈ Br (¯ x0) ∩ D tales que f (¯ x1) < f (¯ x0) < f (¯ x2). 6.2 6.2.1

CONDICIONES NECESARIAS Y SUFICIENTES DE SEGUNDO ORDEN ´ PROPOSICION n

2

◦

Sean f : D −→ R, D ⊆ R , f de clase C en D y x¯0 ∈D punto cr´ıtico de f . 1. x¯0 m´aximo local de f ⇒ Hf (¯ x0) definida negativa o semidefinida negativa. x0) definida positiva o semidefi2. x¯0 m´ınimo local de f ⇒ Hf (¯ nida positiva. 3. Hf (¯ x0) definida positiva ⇒ x¯0 m´ınimo local estricto de f . x0) definida negativa ⇒ x¯0 m´aximo local estricto de f . 4. Hf (¯

´todos Matema ´ ticos Me 6.2.2

Programaci´on matem´atica

34

COROLARIO

Si Hf (¯ x0) es indefinida, entonces x¯0 es punto de silla de f . 6.2.3

´ (Test de la derivada primera) OBSERVACION

Sea f : (a, b) −→ R derivable en (a, b). 1. Si existen a ≤ c ≤ d ≤ b tal que f 0 < 0 en (c, x0) y f 0 > 0 en (x0, d), entonces x0 es m´ınimo local estricto de f . En el caso en que c = a y d = b, x0 es m´ınimo global estricto de f en (a, b). 2. Si existen a ≤ c ≤ d ≤ b tal que f 0 > 0 en (c, x0) y f 0 < 0 en (x0, d), entonces x0 es m´aximo local estricto de f . En el caso en que c = a y d = b, x0 es m´aximo global estricto de f en (a, b) Los rec´ıprocos de las dos implicaciones anteriores no son ciertos. 6.3

PROGRAMAS CONVEXOS

Cuando el programa (2) es convexo, es aplicable el teorema contenido en 4.5.7.

´todos Matema ´ ticos Me

Programaci´on matem´atica

35

´ CLASICA ´ TEMA 7. PROGRAMACION CON RESTRICCIONES DE IGUALDAD 7.1 Planteamiento del problema. Eliminaci´on de restricciones 7.2 Condiciones necesarias de primer orden: Teorema de Lagrange 7.3 Condiciones necesarias y suficientes de segundo orden 7.4 Programas convexos 7.5 Interpretaci´on econ´omica de los multiplicadores de Lagrange

´todos Matema ´ ticos Me

7

7.1

Programaci´on matem´atica

36

´ ´ PROGRAMACION CLASICA CON RESTRICCIONES DE IGUALDAD ´ PLANTEAMIENTO DEL PROBLEMA. ELIMINACION DE RESTRICCIONES

El problema general de programaci´on cl´asica con restricciones de igualdad es opt f (¯ x) s.a: x¯ ∈ S,

(3)

donde f : D ⊆ Rn −→ R, g¯ = (g1, . . . , gm) : D −→ Rm, m < n y S = {¯ x ∈ D | g¯(¯ x) = ¯b}. 7.1.1

´ OBSERVACION

Si en el programa (3) es posible encontrar una funci´on continua ¯ que permita expresar m variables (mediante una reordenaci´on h se pueden suponer que son las primeras) en funci´on de las n − m restantes: ¯ m+1, . . . , xn) (x1, . . . , xm) = h(x de manera que este sistema de ecuaciones equivalga a g¯(¯ x) = ¯b, entonces x¯0 = (x0m+1, . . . , x0n) es soluci´on del problema sin restricciones ¯ m+1, . . . , xn), xm+1, . . . , xn) opt f (h(x ¯ x0), x¯0) es soluci´on de (3). si y s´olo si (h(¯

´todos Matema ´ ticos Me

Programaci´on matem´atica

37

¯ que permita expreNo siempre es posible encontrar una funci´on h sar m variables en funci´on de las restantes o, a´un existiendo, su c´alculo puede ser costoso, por lo que se hace preciso buscar otras v´ıas de resolver este tipo de problemas. 7.2

CONDICIONES NECESARIAS DE PRIMER ORDEN: TEOREMA DE LAGRANGE

Sean D ⊆ Rn abierto y f : D −→ R, g¯ : D −→ Rm, tal que f, g¯ son de clase C 1 en D. 7.2.1

´ DEFINICION

Se dice que x¯0 ∈ S es un punto regular de (3) si y s´olo si el rango de la matriz J g¯(¯ x0) es m. 7.2.2

´ DEFINICION

Se define la funci´on lagrangiana de (3) como ¯ = f (¯ ¯ · (¯b − g¯(¯ L(¯ x, λ) x) + λ x)), ¯ = (λ1, . . . , λm) ∈ Rm. donde x¯ = (x1, . . . , xn) ∈ D y λ 7.2.3

TEOREMA

Si x¯0 ∈ S es regular y soluci´on de (3), entonces existe un u´nico ¯ 0 = (λ0, . . . , λ0 ) ∈ Rm tal que (¯ ¯ 0) es un punto cr´ıtico vector λ x0 , λ 1 m de la funci´on lagrangiana de (3).

´todos Matema ´ ticos Me 7.2.4

Programaci´on matem´atica

38

DEFINICIONES

¯ 0) es un punto cr´ıtico de la funci´on lagrangiana de (3), enSi (¯ x0 , λ tonces se dice que x¯0 es un punto cr´ıtico de f condicionado por S y que λ01, . . . , λ0m ∈ R son sus multiplicadores de Lagrange asociados. 7.2.5

OBSERVACIONES

1. El Teorema de Lagrange 7.2.3 afirma que, supuestas condiciones de regularidad, los extremos de f condicionados por S est´an entre los puntos cr´ıticos de f condicionados por S. El rec´ıproco no es cierto. El Teorema de Lagrange proporciona una condici´on necesaria de optimalidad, pero no suficiente. ¯ del sistema de En consecuencia, entre las soluciones (¯ x, λ) ecuaciones: ∂g1 ∂gm ∂f ∀i ∈ {1, . . . , n} (¯ x)−λ1 (¯ x)−· · ·−λm (¯ x) = 0, ∂xi ∂xi ∂xi tales que x¯ ∈ S, se encuentran las posibles soluciones regulares x¯0 de (3). ¯ 0) = ¯0 se deduce 2. De la igualdad ∇x¯ L(¯ x0, λ ∇f (¯ x0 ) =

m X

λ0i ∇gi(¯ x0),

i=1

es decir, el vector gradiente de la funci´on objetivo en el ´optimo es combinaci´on lineal de los vectores gradientes de las funciones que definen las restricciones en dicho punto.

´todos Matema ´ ticos Me

Programaci´on matem´atica

39

3. Si el conjunto factible S es compacto, el Teorema de Weierstrass garantiza la existencia de soluciones globales de (3). Supuesta la condici´on de regularidad, estas soluciones globales han de estar entre los puntos cr´ıticos de f condicionados por S y se determinar´an evaluando dichos puntos cr´ıticos mediante la funci´on objetivo; los valores extremos obtenidos determinan los m´aximos y m´ınimos globales de f sobre S. 7.3

CONDICIONES NECESARIAS Y SUFICIENTES DE SEGUNDO ORDEN

Sean D ⊆ Rn abierto y f : D −→ R, g¯ : D −→ Rm, tal que f, g¯ son de clase C 2 en D. 7.3.1

DEFINICIONES

¯ tiene por • La matriz hessiana de L respecto a x¯, Hx¯ L(¯ x, λ), elemento ij: ∂ 2L ¯ (¯ x, λ). ∂xi∂xj • El subespacio tangente a las restricciones en el punto x¯0 ∈ S viene dado por T g(¯ x0) = {¯ y ∈ Rn | J g(¯ x0) y¯ = ¯0}. 7.3.2

TEOREMA (Condiciones necesarias de segundo orden)

Sea x¯0 un punto regular de (3) que verifica las condiciones nece¯ 0. Entonces sarias de primer orden, con multiplicador asociado λ

´todos Matema ´ ticos Me

Programaci´on matem´atica

40

1. Si x¯0 es un m´ınimo local de f sobre S, entonces la forma ¯ 0) restringida al subespacio T g(¯ cuadr´atica Hx¯ L(¯ x0, λ x0) es definida positiva o semidefinida positiva. 2. Si x¯0 es un m´aximo local de f sobre S, entonces la forma ¯ 0) restringida al subespacio T g(¯ cuadr´atica Hx¯ L(¯ x0, λ x0) es definida negativa o semidefinida negativa. 7.3.3

COROLARIO

¯ 0) restringida al subespacio T g(¯ Si la forma cuadr´atica Hx¯ L(¯ x0 , λ x0) es indefinida, entonces x¯0 no es ni m´aximo ni m´ınimo local de f sobre S. 7.3.4

TEOREMA (Condiciones suficientes de segundo orden)

Sea x¯0 un punto regular de (3) que verifica las condiciones nece¯ 0. Entonces sarias de primer orden, con multiplicador asociado λ ¯ 0) restringida al subespacio 1. Si la forma cuadr´atica Hx¯ L(¯ x0 , λ T g(¯ x0) es definida positiva, entonces x¯0 es un m´ınimo local estricto de f sobre S. ¯ 0) restringida al subespacio x0 , λ 2. Si la forma cuadr´atica Hx¯ L(¯ T g(¯ x0) es definida negativa, entonces x¯0 es un m´aximo local estricto de f sobre S.

´todos Matema ´ ticos Me

7.4

Programaci´on matem´atica

41

PROGRAMAS CONVEXOS

Sean D ⊆ Rn abierto y f : D −→ R, g¯ : D −→ Rm, tal que f, g¯ son de clase C 1 en D. 7.4.1

TEOREMA

1. Si f es convexa (resp. estrict. convexa) en D, S es convexo, y x¯0 ∈ S es un punto regular que verifica las condiciones necesarias de primer orden del programa (3), entonces x¯0 es un m´ınimo global (resp. m´ınimo global estricto) de f en S. 2. Si f es c´oncava (resp. estrict. c´oncava) en D, S es convexo, y x¯0 ∈ S es un punto regular que verifica las condiciones necesarias de primer orden del programa (3), entonces x¯0 es un m´aximo global (resp. m´aximo global estricto) de f en S. 7.4.2

´ OBSERVACION

Aunque el programa no sea convexo se pueden establecer condiciones suficientes de optimalidad basadas en la convexidad o concavidad respecto de x¯ de la lagrangiana de (3). 7.4.3

TEOREMA

1. Si x¯0 ∈ S es un punto cr´ıtico de f condicionado por S con ¯ 0 y L(¯ ¯ 0) es convexa respecto x¯, multiplicador asociado λ x, λ entonces x¯0 es un m´ınimo global de f sobre S.

´todos Matema ´ ticos Me

Programaci´on matem´atica

42

2. Si x¯0 ∈ S es un punto cr´ıtico de f condicionado por S con ¯ 0 y L(¯ ¯ 0) es c´oncava respecto x¯, multiplicador asociado λ x, λ entonces x¯0 es un m´aximo global de f sobre S. 7.5

´ ECONOMICA ´ INTERPRETACION DE LOS MULTIPLICADORES DE LAGRANGE

Se considera el problema max f (¯ x) s.a: g¯(¯ x) = ¯b 7.5.1

(4)

´ DEFINICION

La funci´on valor ´optimo asociada a (4) es V (¯b) = max {f (¯ x) | g(¯ x) = ¯b}, donde ¯b ∈ B ⊆ Rm. 7.5.2

´ OBSERVACION

Si x¯0(¯b) es soluci´on de (4), entonces V (¯b) = f (¯ x0(¯b)). 7.5.3

TEOREMA

Sean f : D −→ R con D ⊆ Rn abierto, g¯ : D −→ Rm, f y g¯ de clase C 2 en D, ¯b ∈ Rm y x¯0(¯b) una soluci´on regular de (4). Si se verifica:   ¯ (0) J g(¯ x0(b))   6= 0, det ¯ J tg(¯ x0(¯b)) Hx¯ L(¯ x0(¯b), λ)

´todos Matema ´ ticos Me

Programaci´on matem´atica

43

¯ es el vector de multiplicadores de Lagrange asociado a donde λ x¯0(¯b), entonces V es de clase C 1 en un entorno abierto B de ¯b y adem´as: ∂V ¯ λi = (b). ∂bi 7.5.4

´ Y DEFINICION ´ OBSERVACION

El multiplicador de Lagrange λi asociado a la i–´esima restricci´on de (4) mide la sensibilidad de la funci´on valor ´optimo respecto a variaciones de la constante bi, y se denomina precio sombra o valor marginal de una unidad adicional de bi. 7.5.5

´ OBSERVACION

En las condiciones establecidas en 7.5.3, si ¯b var´ıa en ∆¯b ≈ ¯0, entonces ¯ ¯b) · ∆¯b. V (¯b + ∆¯b) − V (¯b) ≈ λ( En particular, si el incremento es unitario en la restricci´on i–´esima, es decir, ∆¯b = e¯i, entonces V (¯b + e¯i) − V (¯b) ≈ λi(¯b).

´todos Matema ´ ticos Me

Programaci´on matem´atica

44

´ CON RESTRICCIOTEMA 8. PROGRAMACION NES DE DESIGUALDAD 8.1 Planteamiento del problema 8.2 Teoremas de Kuhn–Tucker 8.3 Programas convexos 8.4 Interpretaci´on econ´omica de los multiplicadores de Kuhn–Tucker

´todos Matema ´ ticos Me

8

8.1

Programaci´on matem´atica

45

´ CON RESTRICCIONES DE PROGRAMACION DESIGUALDAD PLANTEAMIENTO DEL PROBLEMA

El problema b´asico de programaci´on matem´atica que se estudia en este tema es: max f (¯ x) s.a: x¯ ∈ S,

(5)

donde f : D −→ R, con D ⊆ Rn. El conjunto S puede presentar alguna de las tres estructuras siguientes: S = {¯ x ∈ D | x1 ≥ 0, . . . , xn ≥ 0}, S = {¯ x ∈ D | g1(¯ x) ≤ b1, . . . , gm(¯ x) ≤ bm, x1 ≥ 0, . . . , xm ≥ 0}, S = {¯ x ∈ D | g1(¯ x) ≤ b1, . . . , gm(¯ x) ≤ bm}, con gi : D ⊆ Rn −→ R, bi ∈ R, ∀i ∈ {1, . . . , m}, a cada una de las cuales corresponde el programa: max f (¯ x) s.a: x¯ ≥ ¯0, ( g¯(¯ x) ≤ ¯b, max f (¯ x) s.a: x¯ ≥ ¯0,

(6)

max f (¯ x) s.a: g¯(¯ x) ≤ ¯b,

(8)

(7)

respectivamente, con la notaci´on g¯ = (g1, . . . , gm) y ¯b = (b1, . . . , bm).

´todos Matema ´ ticos Me 8.1.1

Programaci´on matem´atica

46

´ OBSERVACION

Una restricci´on del tipo gi(¯ x) ≥ bi es equivalente a −gi(¯ x) ≤ −bi. El programa min f (¯ x), s.a: x¯ ∈ S es equivalente al programa max −f (¯ x), s.a: x¯ ∈ S. 8.2 8.2.1

TEOREMAS DE KUHN–TUCKER TEOREMA (Condiciones necesarias para (6))

Sean f : D −→ R, donde D ⊆ Rn es abierto, f de clase C 1 en D y S = {¯ x ∈ D | x¯ ≥ ¯0}. Se verifica: Si x¯0 es un m´aximo local de f en S, entonces  ∂f   (¯ x0) ≤ 0  ∂xi ∀i ∈ {1, . . . , n} ∂f    x0i (¯ x0) = 0. ∂xi 8.2.2

DEFINICIONES

Sean g¯ : D −→ Rm, con D ⊆ Rn abierto, g¯ de clase C 1 en D y consid´erense los programas (7) y (8). • x¯0 ∈ S satura la restricci´on i–´esima si y s´olo si gi(¯ x0) = bi. En tal caso se dice que la restricci´on no tiene holgura. • x¯0 ∈ S es regular si y s´olo si no satura ninguna restricci´on o bien el sistema de vectores de Rm formado por los gradientes de las restricciones saturadas en dicho punto (inclu´ıdas las de no negatividad), es libre.

´todos Matema ´ ticos Me 8.2.3

Programaci´on matem´atica

47

´ DEFINICION

La funci´on lagrangiana asociada a (7) y (8) es: ¯ = f (¯ ¯ · (¯b − g¯(¯ L(¯ x, λ) x) + λ x)), ¯ = (λ1, . . . , λm) ∈ Rm. donde λ 8.2.4

TEOREMA (Condiciones necesarias para (7))

Sean f : D −→ R con D ⊆ Rn abierto, g¯ : D −→ Rm, f y g¯ de clase C 1 en D, ¯b ∈ Rm. Sea x¯0 un punto regular de S de (7). Se verifica: ¯ 0 = (λ0, . . . , λ0 ), Si x¯0 es un m´aximo local de f en S, entonces existe λ 1

m

tal que:

∀i ∈ {1, . . . , n}

∀i ∈ {1, . . . , m}

8.2.5

  0 ∂L ¯ 0) = 0,  (¯ x0 , λ x  i ∂xi ∂L   ¯ 0) ≤ 0,  (¯ x0 , λ ∂xi ( 0¡ ¢ λi bi − gi(¯ x0) = 0, λ0i ≥ 0.

OBSERVACIONES

¯ 0 = (λ0, . . . , λ0 ) se denomina vector de multipli1. El vector λ 1 m cadores de Kuhn–Tucker.

´todos Matema ´ ticos Me

Programaci´on matem´atica

48

2. Si un m´aximo local de f en S no es regular, entonces no puede asegurarse que cumpla las condiciones necesarias establecidas en 8.2.4. 3. (Condiciones de holgura complementaria). Las condiciones ∂L ¯ 0) se anecesarias establecidas en 8.2.4 afirman que (¯ x0 , λ ∂xi 0 0 nula si xi > 0 y es no positiva si xi = 0. Por otra parte, si λ0i > 0, entonces x¯0 satura la i–´esima restricci´on. 4. Una forma pr´actica de aplicar las condiciones de 8.2.4 es encontrar las soluciones del sistema de n+m ecuaciones e inc´ognitas:  ∂L  ¯  (¯ x, λ) = 0 x  1  ∂x  1  ... ... ...        ∂L ¯ xn (¯ x, λ) = 0 ∂x ¡ n ¢    λ1 b1 − g1(¯ x) = 0     ... ... ...      ¢  ¡ λm bm − gm(¯ x) = 0, mediante las condiciones de holgura complementaria. De las ¯ obtenidas se eliminan aquellas tales que soluciones (¯ x, λ) x¯ ∈ / S o bien no verifiquen el resto de condiciones: ∀i ∈ {1, . . . , n}

∂L ¯ ≤ 0, (¯ x, λ) ∂xi

∀i ∈ {1, . . . , m}

λi ≥ 0.

´todos Matema ´ ticos Me 8.2.6

Programaci´on matem´atica

49

TEOREMA (Condiciones necesarias para (8))

Sean f : D −→ R con D ⊆ Rn abierto, g¯ : D −→ Rm, f y g¯ de clase C 1 en D, ¯b ∈ Rm y x¯0 un punto regular de (8). Se verifica: Si x¯0 es un m´aximo local de f en S, entonces existe un vector ¯ 0 = (λ0, . . . , λ0 ) ∈ Rm, tal que: λ 1 m ∀i ∈ {1, . . . , n}

∀i ∈ {1, . . . , m}

8.2.7

∂L ¯ 0) = 0, (¯ x0, λ ∂xi ( 0¡ ¢ λi bi − gi(¯ x0) = 0, λ0i ≥ 0.

OBSERVACIONES

¯ 0) = ¯0 se deduce x0, λ 1. En el programa (8), de la igualdad ∇x¯ L(¯ ∇f (¯ x0 ) =

m X

λ0i ∇gi(¯ x0),

i=1

es decir, el vector gradiente de la funci´on objetivo en el ´optimo es combinaci´on lineal, con escalares positivos, de los vectores gradientes de las funciones que definen las restricciones en dicho punto. 2. En los programas (7) y (8), si el conjunto factible S es compacto, entonces el Teorema de Weierstrass garantiza la existencia de soluciones globales. Supuesta la condici´on de regularidad, estas soluciones globales han verificar las condiciones

´todos Matema ´ ticos Me

Programaci´on matem´atica

50

necesarias establecidas en 8.2.4 o 8.2.6 y se determinar´an evaluando los puntos hallados mediante la funci´on objetivo; los valores mayores obtenidos determinan los m´aximos globales de f sobre S. 8.3

PROGRAMAS CONVEXOS

Sean D ⊆ Rn abierto y f : D −→ R, g¯ : D −→ Rm, tal que f, g son de clase C 1 en D. 8.3.1

TEOREMA

1. Si en (6) la funci´on f es c´oncava, habida cuenta de que S es convexo, las condiciones establecidas en 8.2.1 son tambi´en suficientes y si x¯0 ∈ S las verifica, entonces x¯0 es un m´aximo global de f en S. 2. Si en (7) o (8) la funci´on f es c´oncava y las funciones g1, . . . , gm son convexas, las condiciones establecidas en 8.2.4 y 8.2.6 respectivamente, son tambi´en suficientes y si x¯0 ∈ S las verifica, entonces x¯0 es un m´aximo global de f en S. 8.3.2

´ OBSERVACION

En los casos anteriores cuando la funci´on f es estrictamente c´oncava s´olo puede existir un u´nico m´aximo global de f en S. Esta propiedad es muy u´til, ya que permite parar el proceso de b´usqueda de puntos que verifican las condiciones necesarias en el momento en que se ha encontrado uno.

´todos Matema ´ ticos Me

8.4 8.4.1

Programaci´on matem´atica

51

´ ECONOMICA ´ INTERPRETACION DE LOS MULTIPLICADORES DE KUHN–TUCKER ´ DEFINICION

La funci´on valor ´optimo del problema (7) es V (¯b) = max{f (¯ x) | g(¯ x) ≤ ¯b, x¯ ≥ ¯0}, donde ¯b ∈ B ⊆ Rm. 8.4.2

´ OBSERVACION

Si x¯0(¯b) es soluci´on de (7), entonces V (¯b) = f (¯ x0(¯b)). 8.4.3

´ PROPOSICION

1. Si existe V : B −→ R, funci´on valor ´optimo del problema (7), entonces V es creciente respecto a cada una de las variables b 1 , . . . , bm . 2. Si, adem´as, f es c´oncava y S, B son conjuntos convexos, entonces V es c´oncava. 8.4.4

TEOREMA

Sea x¯0(¯b) una soluci´on regular del problema (7), en el que f es c´oncava y g1, . . . , gm son convexas y de clase C 2. Si se verifica:   ¯ (0) J g(¯ x0(b))   6= 0, det ¯ J tg(¯ x0(¯b)) Hx¯ L(¯ x0(¯b), λ)

´todos Matema ´ ticos Me

Programaci´on matem´atica

52

¯ es el vector de multiplicadores de Kuhn–Tucker asociado donde λ a x¯0(¯b), entonces V es de clase C 1 en un entorno abierto B de ¯b y: λi = 8.4.5

∂V ¯ (b). ∂bi

´ OBSERVACION

En las condiciones del Teorema 8.4.4, si ¯b var´ıa en ∆¯b ≈ ¯0, entonces ¯ ¯b) · ∆¯b. V (¯b + ∆¯b) − V (¯b) ≈ λ( En particular, si el incremento es unitario en la restricci´on i–´esima, es decir, ∆¯b = e¯i, entonces V (¯b + e¯i) − V (¯b) ≈ λi(¯b). N´otese que si en el ´optimo x¯0(¯b) no se satura la restricci´on i–´esima, entonces λi = 0 y, por tanto, ligeras variaciones de bi no alterar´ıan el valor de la funci´on objetivo.

´todos Matema ´ ticos Me

Programaci´on matem´atica

´ LINEAL TEMA 9. PROGRAMACION 9.1 Planteamiento del problema. Formas est´andar y can´onica 9.2 Teoremas fundamentales de la Programaci´on Lineal 9.3 El problema dual de un programa lineal 9.4 Teorema fundamental de la dualidad 9.5 Condiciones de holgura complementaria

53

´todos Matema ´ ticos Me

9 9.1 9.1.1

Programaci´on matem´atica

54

´ LINEAL PROGRAMACION ´ PLANTEAMIENTO DEL PROBLEMA. FORMAS ESTAN´ DAR Y CANONICA ´ Y FORMULACION ´ DE UN PROGRAMA LINEAL NOTACION

Sean x¯ = (x1, . . . , xn)t, y¯ = (y1, . . . , yn)t con x¯i, y¯i ∈ R y ¯ = (¯1, · · · , ¯m)t tal que cada ¯i es uno de los signos ≥, =, ≤. Se denota x¯ ¯ y¯ si y s´olo si xi ¯i yi para cada i = 1, . . . , n. Asimismo x¯ ≤ y¯ significa xi ≤ yi para cada i = 1, . . . , n (an´alogo para ≥). El problema b´asico de programaci´on matem´atica que se estudia en este tema es: opt c¯t · x¯

s.a: A¯ x ¯ ¯b, x¯ ≥ ¯0,

(9)

donde c¯t 6= ¯0t, x¯t ∈ Rn, ¯bt ∈ Rm, A = (aij ) ∈ Mm×n(R). 9.1.2

´ DEFINICION

Un problema lineal viene dado en forma est´andar si se expresa como min c¯t · x¯

s.a: A¯ x = ¯b, x¯ ≥ ¯0,

(10)

donde c¯t 6= ¯0t, x¯t ∈ Rn, ¯b ≥ ¯0 ∈ Rm, A = (aij ) ∈ Mm×n(R) . 9.1.3

´ DEFINICION

Un problema lineal viene dado en forma can´onica si se expresa de alguna de las dos formas siguientes: min c¯t · x¯

s.a: A¯ x ≥ ¯b, x¯ ≥ ¯0,

(11)

´todos Matema ´ ticos Me

Programaci´on matem´atica

55

s.a: A¯ x ≤ ¯b, x¯ ≥ ¯0,

(12)

o bien max c¯t · x¯

donde c¯t 6= ¯0t, x¯t ∈ Rn, ¯bt ∈ Rm, A = (aij ) ∈ Mm×n(R) . 9.1.4

OBSERVACIONES

1. El problema lineal gen´erico (9) se puede expresar en forma est´andar (10) o can´onicas (11) y (12) mediante las siguientes operaciones: max c¯t · x¯

≡

ai1x1 + · · · + ainxn ≤ bi

≡

ai1x1 + · · · + ainxn = bi

≡

ai1x1 + · · · + ainxn ≤ bi ≡

ai1x1 + · · · + ainxn ≥ bi ≡

min − c¯t · x¯ −ai1x1 − · · · − ainxn ≥ −bi    ai1x1 + · · · + ainxn ≤ bi   ai1x1 + · · · + ainxn ≥ bi

  ai1x1 + · · · + ainxn + x0i = bi  x0 ≥ 0 i   ai1x1 + · · · + ainxn − x0i = bi  x0 ≥ 0 i

La nueva variable introducida, x0i, se denomina de holgura. 2. La forma est´andar (10) es la requerida en la resoluci´on de (9) mediante el algoritmo del s´ımplex. Las formas can´onicas (11) y (12) son las que se utilizan en las secciones 9.3 y 9.4.

´todos Matema ´ ticos Me

9.2

Programaci´on matem´atica

56

´ TEOREMAS FUNDAMENTALES DE LA PROGRAMACION LINEAL

Un programa lineal, en cualquiera de sus formas, es un problema de optimizaci´on al que pueden aplicarse los resultados del tema anterior. No obstante, la linealidad de la funci´on objetivo y de las restricciones permiten desarrollar m´etodos espec´ıficos de resoluci´on. 9.2.1

OBSERVACIONES

1. Al ser la funci´on objetivo no constante, c´oncava y convexa simult´aneamente, y el conjunto factible convexo (un politopo), en virtud de 4.5 los m´aximos (resp. los m´ınimos) de (9), si existen, (a) son globales (por el teorema local-global) (b) forman un conjunto convexo (c) se encuentran en la frontera del conjunto factible. 2. Al ser la funci´on objetivo continua (polin´omica homog´enea de grado 1) y el conjunto factible cerrado (definido mediante un n´umero finito de desigualdades no estrictas e igualdades relativas a funciones continuas) se puede asegurar la existencia de soluciones (m´aximos y m´ınimos globales de (9)) cuando el conjunto factible sea acotado y no vac´ıo (en virtud del teorema de Weierstrass).

´todos Matema ´ ticos Me 9.2.2

Programaci´on matem´atica

57

TEOREMA

Si el conjunto factible de (9) es acotado y no vac´ıo, entonces dicho programa lineal tiene soluci´on en alguno de sus v´ertices. 9.2.3

TEOREMA

Si (9) tiene soluci´on, entonces alguna soluci´on se encuentra en alg´un v´ertice. 9.2.4

TEOREMA

Si dos puntos son m´ınimos (resp. m´aximos) de (9), entonces tambi´en es m´ınimo (resp. m´aximo) cualquier combinaci´on convexa de dichos puntos. 9.2.5

COROLARIO

Si el conjunto factible de (9) es compacto, entonces el conjunto de sus soluciones es la envolvente convexa de un n´umero finito de v´ertices del conjunto factible y, por tanto, es un poliedro. 9.2.6

OBSERVACIONES Y DEFINICIONES

1. Los resultados anteriores no excluyen que (9) carezca de soluci´on, lo cual sucede cuando (a) El conjunto factible es vac´ıo. En este caso se dice que (9) es un problema imposible.

´todos Matema ´ ticos Me

Programaci´on matem´atica

58

(b) La funci´on objetivo no est´a acotada superior o inferiormente en el conjunto factible. En este caso de dice que (9) es un problema sin soluci´on. 2. En el caso de que (9) admita soluci´on el programa puede ser (a) un problema con soluci´on u´nica o bien (b) un problema con soluci´on m´ultiple. 3. Supuesta la existencia de soluciones de (9), pudiera pensarse que, evaluando la funci´on objetivo sobre los v´ertices del conjunto factible, ser´ıa posible determinar los m´aximos y m´ınimos de (9). Esta idea es v´alida para problemas lineales sencillos, y de hecho, mejorada mediante un criterio selectivo, es el fundamento del m´etodo del s´ımplex. No obstante, en general este procedimiento es inviable en la pr´actica, ya que la localizaci´on de tales v´ertices requiere resolver sistemas de ecuaciones lineales tanto m´as complicados cuantas m´as variables y restricciones tenga (9). 9.3 9.3.1

EL PROBLEMA DUAL DE UN PROGRAMA LINEAL ´ DEFINICION

Sean A ∈ Mm×n(R), c¯t ∈ Rn, ¯bt ∈ Rm, m < n. Dado el programa lineal en forma can´onica ( A¯ x ≥ ¯b t min c¯ · x¯ s.a: (P) ¯ x¯ ≥ 0,

´todos Matema ´ ticos Me

Programaci´on matem´atica

se dice que su programa dual asociado es ( t ¯ ≤ c¯ Aλ t ¯ s.a: max ¯b · λ ¯ ≥ ¯0. λ

59

(D)

Las variables λ1, . . . , λm se denominan variables duales y el problema (P) es un programa primal. 9.3.2

OBSERVACIONES

1. Los programas lineales (P) y (D) est´an expresados en forma can´onica sim´etrica. 2. El n´umero de variables (resp. restricciones) del problema dual coincide con el n´umero de restricciones (resp. variables) del problema primal (no se tienen en cuenta las restricciones sobre el signo). 3. El dual del programa ( max

t

c¯ · x¯ s.a:

es

( min

¯bt · λ ¯ s.a:

A¯ x ≤ ¯b x¯ ≥ ¯0, ¯ ≥ c¯ Atλ ¯ ≥ ¯0. λ

4. El dual de un programa lineal dual del problema (P) es el propio (P). Esto es inmediato si se tiene en cuenta la definici´on de problema dual y el item anterior.

´todos Matema ´ ticos Me

9.4

Programaci´on matem´atica

60

TEOREMA FUNDAMENTAL DE LA DUALIDAD

Existe una relaci´on entre las soluciones de los problemas primal y dual, la cual se precisa en esta secci´on. Se denota por Sp (resp. Sd) al conjunto factible del problema (P) (resp. (D)). 9.4.1

´ PROPOSICION

Se verifica: ¯ ∈ Sd, c¯t · x¯ ≥ ¯bt · λ. ¯ 1. Para todo x¯ ∈ Sp, para todo λ 2. Si el programa (P) (resp. (D)) no admite soluci´on, entonces (D) (resp. (P)) es imposible. ¯ ∗ ∈ Sd tales que c¯t · x¯∗ = ¯bt · λ ¯ ∗, entonces 3. Si existen x¯∗ ∈ Sp, λ ¯ ∗ es soluci´on de (D). x¯∗ es soluci´on de (P) y λ 9.4.2

TEOREMA

Si existe soluci´on, x¯∗, del programa (P), entonces existe soluci´on, ¯ ∗, del programa (D) y es cierto el rec´ıproco. Adem´as, el valor λ ¯ ∗. ´optimo de ambos programas coincide: c¯t · x¯∗ = ¯bt · λ 9.5

CONDICIONES DE HOLGURA COMPLEMENTARIA

Dados el par de programas (P)–(D), las condiciones de holgura complementaria permiten conocer una soluci´on ´optima de uno de los problemas a partir de una soluci´on ´optima del otro problema.

´todos Matema ´ ticos Me 9.5.1

Programaci´on matem´atica

61

´ (Condiciones de holgura complementaria) PROPOSICION

¯ ∗ soluci´on de (D), se verifican las Dados x¯∗ soluci´on de (P) y λ siguientes igualdades:   m X ∗ ∀i ∈ {1, . . . , n} xi ajiλ∗j − ci = 0 j=1

 ∀i ∈ {1, . . . , m}

λ∗i 

n X

 aij x∗j − bi = 0.

j=1 9.5.2

OBSERVACIONES

1. La primera igualdad de 9.5.1 se interpreta as´ı: si la soluci´on de (D) no satura la restricci´on i–´esima de (D), entonces la componente i–´esima de la soluci´on de (P) es cero; si la soluci´on de (P) tiene su i–´esima componente positiva, entonces la soluci´on de (D) satura la restricci´on i–´esima de (D). La segunda igualdad admite an´aloga interpretaci´on. 2. Una vez conocida una soluci´on de (P) (resp. (D)), es inmediato obtener una soluci´on de (D) (resp. (P)), sin m´as que resolver el sistema lineal formado por los dos conjuntos de igualdades de 9.5.1. Un ejemplo muy interesante es aqu´el en que (P) consta s´olo de dos restricciones, en cuyo caso (D), al tener dos variables, podr´a resolverse f´acilmente mediante el m´etodo gr´afico. Las condiciones de holgura complementaria permiten entonces hallar la soluci´on de (P).

´todos Matema ´ ticos Me

9.6 9.6.1

Programaci´on matem´atica

62

´ DE LAS VARIABLES DUALES INTERPRETACION ´ DEFINICION

La funci´on valor ´optimo del problema (P) es z ∗(¯b) = min{¯ct · x¯ | A¯ x ≥ ¯b, x¯ ≥ ¯0}. 9.6.2

´ OBSERVACION

Si x¯∗(¯b) es soluci´on de (P), entonces z ∗(¯b) = c¯t · x¯∗(¯b). 9.6.3

TEOREMA

Sea (P) con soluci´on x¯∗(¯b) y (P∆) un nuevo problema construido a partir de (P) modificando ¯b en cantidades ∆¯b suficientemente peque˜nas para que sus respectivos problemas duales tengan la ¯ ∗. Entonces misma soluci´on λ ¯ ∗ · ∆¯b. z ∗(¯b + ∆¯b) − z ∗(¯b) = λ 9.6.4

´ OBSERVACION

En particular, si el incremento es unitario en la restricci´on i–´esima, es decir, ∆¯b = e¯i, y se cumplen las hip´otesis del teorema anterior, entonces z ∗(¯b + e¯i) − z ∗(¯b) = λ∗i .