Pontificia Universidad Católica de Chile

Escuela de Ingenierı́a
Departamento de Ingenierı́a Industrial y de Sistemas

Teorı́a Poliedral
Optimización ICS1113

Jaime González

Pontificia Universidad Católica de Chile

Primer semestre 2019

Tabla de Contenidos

1 Geometrı́a lineal

2 Relación con Programación Lineal

González (PUC) Teorı́a Poliedral Primer semestre 2019 2 / 19

Subespacio lineal
Subespacio lineal
Un subespacio lineal es un conjunto S ⊂ Rn definido por un conjunto finito de
igualdades lineales homogéneas:

S = {x ∈ Rn : Ax = 0}

Ejemplos:
El origen
Rn
Recta / plano / hiperplano que pasa por el origen.
Algunas propiedades:
Todo subespacio contiene al origen.
Si x1 ∈ S y x2 ∈ S, entonces λ1 x1 + λ2 x2 ∈ S, para todo λ1 , λ2 ∈ R.
Un subespacio S ⊂ Rn tiene dimensión Dim(S) = n − rango(A)
Dados m vectores l.i. x1 , ..., xm en S con Dim(S) = m. Todo vector y ∈ S es
generado por una combinación lineal de x1 , ..., xm . Es decir, existen λ1 , ..., λm
m
P
tales que y = λ i xi .
i=1
González (PUC) Teorı́a Poliedral Primer semestre 2019 4 / 19
Poliedro
Poliedro
Un poliedro es un conjunto P ⊂ Rn representable por cualquier conjunto de de-
sigualdades lineales:
P = {x ∈ Rn : Ax ≤ b}

Ejemplos:
El origen.
El vacı́o.
Rn
{x1 , x2 ∈ R2 : x1 + 4x2 ≤ 16}
{x1 , x2 ∈ R2 : |x1 + 4x2 | ≤ 16}
{x1 , x2 ∈ R2 : max{x1 , x2 } ≤ k}
Observaciones:
Un poliedro es convexo.
Un polı́topo P es un poliedro acotado. Es decir, que existe k ∈ R tal que:
P ⊂ {x ∈ Rn : ||x|| ≤ k}
González (PUC) Teorı́a Poliedral Primer semestre 2019 5 / 19
Vértice

Vértice
Un vértice de un poliedro P es una solución factible que no puede ser expresada
como punto intermedio de otras dos soluciones factibles.

x1 +x2
Es decir, no existen x1 , x2 tales que v = 2

González (PUC) Teorı́a Poliedral Primer semestre 2019 6 / 19

Vértice

Observaciones sobre vértices de poliedros en Rn :

Un vértice está determinado por n restricciones l.i. activas.
Para un poliedro de m restricciones existen a lo más mn

Por ejemplo, un poliedro de 4 restricciones en R2 tiene a lo más 6 vértices.

González (PUC) Teorı́a Poliedral Primer semestre 2019 7 / 19

Cono
Cono
Un cono es un poliedro C ⊂ Rn representable por desigualdades lineales ho-
mogéneas:
C = {x ∈ Rn : Ax ≤ 0}

Ejemplo:
  x2
1 −2
x ≤0
−2 1 6
5
Es equivalente a
estas dos 4
restricciones: 3
x1 − 2x2 ≤ 0 2
1
−2x1 + x2 ≤ 0
0
0 1 2 3 4 5 6 x1
González (PUC) Teorı́a Poliedral Primer semestre 2019 8 / 19
Cono
Observaciones:
Un cono es un poliedro.
Todo cono contiene al origen.
El origen se denomina cono trivial. Un cono se denomina regular si contiene
un x 6= 0.
Sea un cono C . Si x ∈ C , implica que λx ∈ C , ∀λ ∈ R+ .
El único vértice posible de un cono es el origen.
Cono regular: Cono trivial:
x2 x2

~x

x1 x1
González (PUC) Teorı́a Poliedral Primer semestre 2019 9 / 19
Rayo extremo

Rayo extremo
Un rayo extremo r 6= 0 es un punto de un cono C con exactamente n−1 restricciones
l.i. activas.

En el ejemplo anterior:
x2

x1

González (PUC) Teorı́a Poliedral Primer semestre 2019 10 / 19

Rayo extremo

Observaciones:

Dado un cono C = {x : Ax ≤ 0}, los puntos r ∈ C y λr ∈ C son el mismo

rayo escalado por λ.

Dado un cono C = {x : Ax ≤ 0}, todo punto del cono y ∈ C puede escribirse

como combinación lineal positiva (combinación cónica) de sus rayos extremos.

González (PUC) Teorı́a Poliedral Primer semestre 2019 11 / 19

Solución óptima en polı́topos

Teorema
Si P = {x ∈ Rn : Ax ≤ b} es un polı́topo no vacı́o con vértices {v1 , v2 , ..., vP }, el
problema min c T x : Ax ≤ b alcanza su valor óptimo en un vértice para cualquier
A, b, c.

Demostración por contradicción:

Por teorema B-W, sabemos que admite solución óptima x ∗ , con valor c T x ∗ .
Si c = 0, todo el dominio es óptimo y, por lo tanto, todo vértice.
Si c 6= 0, entonces supongamos que x ∗ es óptimo y que no existe vértice
óptimo:
Existe una dirección h tal que c T h ≤ 0.
Esto implica que x ∗ + h activa otra restricción siendo solución óptima.
Repetir esto n veces, hasta activar n restricciones y se llega a un vértice
(óptimo). Se genera una contradicción. Por lo tanto, debe haber un vértice
óptimo.

González (PUC) Teorı́a Poliedral Primer semestre 2019 13 / 19

Poliedro no acotado

Poliedro no acotado
Un poliedro P es no acotado si existe al menos un vector no nulo y ∈ Rn tal que
para todo x ∈ P se tiene que x + y ∈ P.

El vector y se conoce como rayo de escape.

x2

y
y

x1

González (PUC) Teorı́a Poliedral Primer semestre 2019 14 / 19

Cono recesivo

Cono recesivo
Sea P = {x : Ax ≤ b} un poliedro no vacı́o. Se dice que C (P) = {x : Ax ≤ 0} es
el cono recesivo de P.

Teorema
Sea P un poliedro no vacı́o, y C (P) su cono recesivo. Entonces, se cumple que:

P es no acotado ⇔ C (P) es un cono regular

No acotado: Acotado:
x2 x2 x2 x2

x1 x1 x1 x1
González (PUC) Teorı́a Poliedral Primer semestre 2019 15 / 19
Problema no acotado

Se dice que un problema de minimización es no acotado cuando es factible y no

tiene solución óptima, debido a que el valor de la función objetivo puede disminuir
infinitamente.

Teorema
Un problema factible min{c T x : Ax ≤ b} es no acotado.
⇔
El sistema Ay ≤ 0, c T y < 0 tiene solución.

González (PUC) Teorı́a Poliedral Primer semestre 2019 16 / 19

Existencia de vértice
Teorema
Sea P = {x ∈ Rn : Ax ≤ b} un poliedro no vacı́o. Se cumple que:

Existe h 6= 0 tal que Ah = 0 ⇔ P no tiene vértices

Corolario:
P = {x ∈ Rn+ : Ax ≤ b} posee vértices.
Corolario:
Si el cono C (P) es trivial, entonces P posee vértices.

x2 x2

x1 x1
González (PUC) Teorı́a Poliedral Primer semestre 2019 17 / 19
Observaciones
Poliedro: polı́topo + cono
Toda solución factible x ∈ P se descompone en una suma entre un punto x 0 del
polı́topo formado por una combinación convexa de los vértices {v1 , v2 , ..., vP } de P
y un punto h del cono C (P), es decir:

x = x0 + h

x2

x
0
x

x1
González (PUC) Teorı́a Poliedral Primer semestre 2019 18 / 19
Solución óptima en poliedros
Teorema
Si P = {x ∈ Rn+ : Ax ≤ b} es no vacı́o y posee vértices, entonces el problema
min{c T x : Ax ≤ b} es no acotado o alcanza el valor óptimo en un vértice.

Demostración:
Si el problema admite al menos una solución óptima x ∗ , se debe cumplir que
c T h ≥ 0, ∀h ∈ C (P), pues de lo contrario el problema es no acotado.
Supongamos que ningún vértice es óptimo, es decir, c T x ∗ < c T v , para todo
vértice v .
Descomponemos la solución óptima en x ∗ = x 0 + h, con:
c T x ∗ = c T (x 0 + h) = c T x 0 + c T h ≥ c T x 0
Esto implica que existe solución óptima dentro del polı́topo.
Por resultado sobre polı́topos, sabemos que existe vértice vP tal que:
c T x ∗ = c T x 0 = c T vP
Con lo que se llega a una contradicción. Por lo tanto, la solución óptima está
en un vértice.
González (PUC) Teorı́a Poliedral Primer semestre 2019 19 / 19