luis miguel torres - math.epn.edu.ecltorres/inv-oper-3/apuntes.pdf · cuaderno de matemática no. 1...

Cuadernos de Matemática

de la Escuela Politécnica Nacional

Luis Miguel Torres

Investigación Operativa III

Cuaderno de Matemática No. 1

Investigación Operativa III

Luis Miguel Torres

Responsable de la Edición: Sandra GutiérrezAsistentes: Stephany Vargas

Registro de derecho autoral No.ISBN:

Publicado por la Unidad de Publicaciones de la Facultad de Ciencias de la EscuelaPolitécnica Nacional, Ladrón de Guevara E11-253, Quito, Ecuador.

Primera edición: 2014Primera impresión: 2014

c© Escuela Politécnica Nacional 2014

Índice general

1 Introducción 11.1 Poliedros y polítopos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Programación Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Dualidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Teoría de la Complejidad Computacional 92.1 Definiciones previas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.1.1 Notación asintótica . . . . . . . . . . . . . . . . . . . . . . . . . 92.1.2 Problemas e instancias . . . . . . . . . . . . . . . . . . . . . . . 11

2.2 Máquinas de Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3 Las clases P y NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.1 Reducciones polinomiales . . . . . . . . . . . . . . . . . . . . . 192.4 Problemas NP-completos . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.1 El Problema de Satisfactibilidad (SAT) . . . . . . . . . . . . . 192.4.2 Teorema de Cook-Levin . . . . . . . . . . . . . . . . . . . . . . 212.4.3 Otros problemas NP-completos . . . . . . . . . . . . . . . . . . 25

3 Programas Enteros 293.1 Formulación y aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1.1 Técnicas de modelización . . . . . . . . . . . . . . . . . . . . . 293.1.2 Calidad de una formulación . . . . . . . . . . . . . . . . . . . . 38

3.2 Formulaciones ideales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.3 Sistemas TDI (Totalmente Dual Integrales) . . . . . . . . . . . . . . . 53

4 Solución de Programas Enteros 594.1 Algoritmo de branch-and-bound . . . . . . . . . . . . . . . . . . . . . . 594.2 Relajación Lagrangeana . . . . . . . . . . . . . . . . . . . . . . . . . . 604.3 Métodos del planos cortantes . . . . . . . . . . . . . . . . . . . . . . . 71

4.3.1 Algoritmo general de planos cortantes . . . . . . . . . . . . . . 764.3.2 Cortes de Gomory . . . . . . . . . . . . . . . . . . . . . . . . . 774.3.3 Rango de Chvátal de un poliedro . . . . . . . . . . . . . . . . . 77

iii

Índice de figuras

1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Cono poliedral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.5 Combinación convexa en el plano poliedro. . . . . . . . . . . . . . . . 41.6 Poliedro Híbrido. Polítopo, cono. . . . . . . . . . . . . . . . . . . . . . 51.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.8 Cono generado por 3 vectores. . . . . . . . . . . . . . . . . . . . . . . 61.9 Poliédro sin vértices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.11 Óptimo en éste polítopo. . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1 Notación asintótica extendida a funciones reales: f ∈ O(g). . . . . . . . 92.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 Orden Lexicográficamente. . . . . . . . . . . . . . . . . . . . . . . . . 132.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.5 n = 〈I〉 = |ϕ(I)| . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563.14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

v

vi Índice de figuras

4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684.5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

Capítulo 1

Introducción

1.1 Poliedros y polítopos

Consideremos el conjunto solución del sistema de ecuaciones lineales

Ax = b, (1.1)

donde A ∈ Rm×n, b ∈ Rm. Contemplamos dos casos:

1. Si b = 0, el conjunto solución V de (1.1) es un espacio vectorial. Conocemos delálgebra lineal que todo espacio vectorial puede ser expresado como el conjuntode todas las combinaciones lineales de un conjunto finito S := x1, x2, ..., xkde vectores :

V = 〈S〉 :=

k∑

i=1

αixi, : αi ∈ R

.

Decimos entonces que S es un conjunto generador para V . Un conjunto gene-rador minimal respecto a la inclusión es una base de V . Se conoce que todaslas bases de un espacio vectorial V tienen la misma cardinalidad, esta cantidades llamada la dimensión de V , dim(V). La dimensión de V coincide además conla máxima cardinalidad de un conjunto de vectores linealmente independientespertenecientes a este espacio.

Podemos resumir la observación anterior en el siguiente teorema:

Teorema 1. Para todo espacio vectorial V ⊆ Rn, existen A ∈ Rm×n y S ⊆ Rn

finito tales que

V = x ∈ Rn : Ax = 0 = 〈S〉.

2. Si b 6= 0, el conjunto solución A de (1.1) es un espacio afín. Todo espacio afínA puede ser descrito como el conjunto de combinaciones afines de un conjuntofinito S := x1, x2, ..., xk de puntos:

1

2 Introducción

aff(S) =

k∑

i=1

αixi, : αi ∈ R,n∑

i=1

αi = 1

.

El mayor número de puntos afínmente independientes en un espacio afín Acoincide con el menor número de puntos contenidos en un conjunto finito S quesatisfagaaff(S) = A. Restando uno a cualquiera de los dos valores anteriores seobtiene la dimensión de A.

Teorema 2. Para todo espacio afín A ⊆ Rn, existen A ∈ Rm×n, b ∈ Rm y

S ⊆ Rn finito tales que

A = x ∈ Rn : Ax = b = aff(S).

Ejemplo Considerar el conjunto solución en R2 de x+ y = 5. Este conjunto defineuna recta A en R2, como puede verificarse en la Figura 1.1. Notar que, en particular,los puntos (2, 3)T y (3, 2)T pertenecen a A. Además, la ecuación de esta recta puedeponerse en la forma (ver Figura 1.2):

A =

x ∈ R2 : x = r1

(2

3

)

+ r2

(3

2

)

, r1, r2 ∈ R, r1 + r2 = 1

= aff(

(2

3

)

,

(3

2

)

).

/∈ Recta

Figura 1.1

x (23

)

(32

)

y

x r1(23

)+ r2

(32

)

r1 + r2 = 1

Figura 1.2

1.1 Poliedros y polítopos 3

Por otra parte, al considerar los conjuntos solución de sistemas de desigualdades

lineales llegamos a las definiciones de cono y poliedro.

Sea A ∈ Rm×n. El conjunto solución del sistema Ax ≤ 0 es un cono poliedral. Seconoce que todo cono poliedral C puede ser expresado como la combinación cónicade un conjunto finito de vectores Y := y1, y2, ..., yk:

C = cone(S) :=

k∑

i=1

αiyi, αi ≥ 0

.

Figura 1.3: Cono poliedral

La dimensión de un cono poliedral C es la máxima cardinalidad de un conjunto depuntos afínmente independientes pertenecientes a C, menos uno. A diferencia de lo queocurre con espacios vectoriales y espacios afines, la dimensión de C no necesariamentecoincide con la menor cardinalidad de un conjunto generador para C.

De manera similar a lo que ocurre con espacios vectoriales y espacios afines, po-demos establecer el siguiente resultado para conos:

Teorema 3. Para todo cono poliedral C, existen A ∈ Rm×n y Y ⊆ Rn finito tales

que

C = x ∈ Rn : Ax ≤ 0 = cone(Y ).

El conjunto solución del sistema no homogéneo de desigualdades Ax ≤ b, conA ∈ Rm×n y b ∈ Rm es un poliedro. Antes de formular el resultado equivalentea los tres últimos teoremas en el caso de poliedros, necesitamos introducir algunasdefiniciones adicionales.

Ejercicio Encontrar ejemplos de conos poliedrales de dimensión tres que requieranconjuntos generadores con cardinalidades arbitrariamente grandes.

4 Introducción

Figura 1.4

Ax ≤ b (1.2)

Si Ax ≤ b, Ay ≤ b

r, s ≥ 0; A(rx+ sy) = r(Ax) + s(Ay) ≤ rb+ sb = b(r + s) = br + s = 1; ≤ b ≤ b

conv(S) =

n∑

i=1

αnxi, αi ≥ 0,n∑

i=1

αi = 1

(1.3)

C.S. es cerrado a combinaciones convexas.

S = x1, x2, ..., xn

Figura 1.5: Combinación convexa en el plano poliedro.

(Un objeto que se obtiene)Un polítopo es una región obtenida como combinación convexa de un conjunto finitode puntos.

1.2 Programación Lineal 5

P

v2

v1

y2

y1

a11x1 + a12x2=b

Figura 1.6: Poliedro Híbrido. Polítopo, cono.

Teorema FundamentalPara todo poliedro P existen A ∈ Rm×n, b ∈ Rm y V, Y ⊆ Rn (finitos) tal que

P = x ∈ Rn : Ax ≤ b = cone(Y ) + conv(V )

donde + es suma de Minkovsky

Cara: Hiperplano de soporte ∩PVértices: dim = 0Aristas: dim = 1Faceta: dim = n− 1

CTx = α

π CTx = β

v2

v1

v3

y1

y2

Figura 1.7

Con α < β.

1.2 Programación Lineal

Sea c ∈ Rn, b ∈ Rm, A ∈ Rm×n.

PL =

max CTxs.r Ax ≤ b

6 Introducción

Conjunto factible es un poliedro (hiperplano):

CTX = α (1.4)

1. PL puede ser no acotado.

∀α ∈ R, ∃x ∈ P, CTx > 0

2. PL es acotado. En este caso el conjunto de soluciones óptimas para PL formanuna cara de P. Si P tiene vértices, entonces toda cara tiene vértices y por lotanto hay al menos una solución óptima que es un vértice.

0

o

Figura 1.8: Cono generado por 3 vectores.

v

y1

y2

y3

o

Figura 1.9: Poliédro sin vértices.

3. P = ∅, el sistema se llama no factible. Un polítopo es acotado y siempre tienevértices.

Obs: En la práctica es común acotar las variables de decisión.

• Trabajamos sobre polítopos.

• Casi siempre hay una solución óptima que sea un vértice.

Si P = conv(V ) + cone(Y ):

• V = v1, v2, Y = y1, y2, y3

x ∈ P ⇔ X = α1v1 + α2v2 + β1y1 + β2y2 + β3y3

α1, α2, β1, β2, β3 ≥ 0

α1 + α2 = 1

1.3 Dualidad 7

max CTx =∑

αiCT vi +

∑βiC

T vi +∑

βiCT yi

⇒ CT yi > 0 ∃i ∈ 1, 2, 3

Entoces el problema es no acotado.

Si ∃yi tal que CT yi > 0 ⇒ (PL) es no acotado.

• Caso contrario algún vi ∈ V alcanza el valor óptimo.

1.3 Dualidad

Sea (PL)

max x1 + 3x2 + 3x3y1 = 3x1 + 2x2 + x3 ≤ 2y2 = −2x1 + x2 + 3x3 ≤ 3y3 = −5x1 − x2 + x3 ≤ −5

y1 ∗ 2 6x1 + 4x2 + 2x3 ≤ 4+y3 −5x1 − x2 + x3 ≤ −5

x1 + 3x2 + 3x3 ≤ −1

y1 3x1 + 2x2 + x3 ≤ 2+y2 −2x1 + x2 + 3x3 ≤ 3

x1 + 3x2 + 3x3 ≤ 5

y1, y2, y3 ≤ 0 3y1 − 2y2 − 5y3 = 12y1 + y2 − y3 = 3−5y3 − y3 + y3 = −5

Con lo que se tiene que 2y1 + 3y2 − 5y3 es una cota superior al valor óptimo.

Si yTA = CT , y ≤ 0, → yT b es una cota superior.

(DL)

min yTbs.r.yTA = CT

y ≤ 0

∀x factible para PL

CTx ≤ yT b (1.5)

8 Introducción

∀y factible para D.L.⇒ Si x∗ es una solución óptima de PL.

y∗ es una solución óptima de DL.

CTx∗ ≤ (y∗)T b (1.6)

(P)

max CTxs.r.Ax ≤ bx ∈ Rn

(D)

min bTys.r.Ay = c, y ≤ 0y ∈ Rm

Figura 1.10

Figura 1.11: Óptimo en éste polítopo.

Capítulo 2

Teoría de la ComplejidadComputacional

2.1 Definiciones previas

2.1.1 Notación asintótica

Sean f y g dos funciones N→ N. Decimos que

1. f ∈ O(g) (“f es de orden g”), si ∃no, c ∈ N, tal que ∀n ≥ no, |f(n)| ≤ c|g(n)|.

cg

f

Figura 2.1: Notación asintótica extendida a funciones reales: f ∈ O(g).

2. f ∈ Ω(g), si ∃no, c ∈ N tal que ∀n ≥ no, c|f(n)| ≥ |g(n)|.

3. f ∈ o(g), si f ∈ O(g) y f ∈ Ω(g).

Ejemplos

1. Demostrar que 5n2 + 4n+ 10 ∈ O(n2)Eligiendo c = 19, no = 1, obtenemos que para todo n ≥ 1 se cumple

5n2 + 4n+ 10 ≤ 5n2 + 4n2 + 10n2 = 19n2 = cn2.

9

10 Teoría de la Complejidad Computacional

2. Demostrar que 5n2 + 4n+ 10 ∈ Ω(n2)Basta elegir c = 5, no = 1, pues

5n2 + 4n+ 10 ≥ 5n2 ≥ n2, ∀n ≥ 1.

3. Notar que de los dos ejemplos anteriores se sigue que 5n2 + 4n+ 10 ∈ o(n2).

4. Demostrar que n3 + 2n ∈ Ω(100n2). Basta elegir c = 100, n0 = 1. Tenemosentonces que

100(n3 + 2n) = 100n3 + 200n ≥ 100n3 ≥ 100n2, ∀n ≥ 1.

5. Demostrar que n4 ∈ O(2n).Elijamos n0 = 16 y c = 1.. Demostraremos primero que para n ≥ n0 se cumplela identidad

4n3 + 6n2 + 4n+ 1 < n4. (2.1)

En efecto, basta observar que si n ≥ n0, tenemos:

4n3 ≤1

4n4,

6n2 <1

4n4,

4n <1

4n4,

1 <1

4n4,

y (2.1) se sigue al sumar las cuatro desigualdades anteriores.

Con esto, podemos demostrar por inducción que n4 ∈ O(2n): Para n = n0 = 16,se cumple 164 = 216 = 65,536. Por otra parte, empleando el binomio de Newton,obtenemos para n ≥ n0:

(n+ 1)4 = n4 + 4n3 + 6n2 + 4n+ 1 < n4 + n4 ≤ 2n + 2n = 2n+1.

6. Demostrar que para todo k ∈ N, nk ∈ O(2n).Tenemos que demostrar la existencia de no inN tal que:

(a) Si k ≥ 4:

nk ≤ 2n ⇔ k log2 n ≤ n

⇔ k ≤n

log2 n→ ∞

∀n ≥ no, ∃ k tal que se cumple la anterior relación. Basta elejir no = 2k.

2.1 Definiciones previas 11

Si n ≥ no

n

log2 n≥

no

log2 no=

2k

k≥ 4

(b) Si k = 1, 2, 3nk ≤ n4 ∈ O(2n)

nk ∈ O(2n), log n ∈ O(n).

Si f ∈ O(1)→ f = c

7. Sea f un polinomio de grado k, con k ∈ N. Demostrar que f ∈ o(nk).(Ejercicio.)

El cuadro siguiente ordena algunas clases comunes de funciones de acuerdo a sucomplejidad:

O(1) ⊂ O(logn) ⊂ O(n) ⊂ O(n · log(n)) ⊂ O(n2) ⊂ O(nk) ⊂ O(2n) ⊂ O(n!)

2.1.2 Problemas e instancias

Un problema es una pregunta general que depende de parámetros. Una instancia esla pregunta específica que se obtiene al dar valores particulares a los parámetros deun problema.

Notación

II denota un problema.

I denota una instancia.

I(II) denota el conjunto de todas las instancias II.

Un problema se llama problema de decisión si todas sus instancias admiten sólodos respuestas posibles, “si” o “no”.

Llamaremos alfabeto∑

a un conjunto finito de símbolos.

Llamaremos palabra a una sucesión finita de símbolos de∑

.

Denotaremos por∑∗ al conjunto de todas las palabras que pueden formarse con

símbolos de∑

.

Dados un problema II y un alfabeto∑

, un esquema de codificación es una funciónbiyectiva.

C : I(II) →∑

⊆∗∑

(2.2)


Dada una instancia I∈ I(II), la longitud de codificación de I respecto al esquemaC es la longitud (igual número de símbolos) de la palabra C(I). Notaremos éste valorpor 〈C(I)〉, o simplemente 〈I〉.

Ejemplos

1. II: Dado n ∈ Z, ¿es n un número primo?

∑= 0, 1, ..., 9, C es la notación decimal de n.

∑= 0, 1, C es la notación binaria.

• Longitud de codificaciónlog10(n = 1)

•∑

= 0, 1︸︷︷︸r

, C es la notación binaria.

⌈logr(n+ 1)⌉

Con +1 símbolo O (log(n)), con 1 símbolo O(n).

2. II: Dados un grafo dirijido D = (V,A) y un vector de costos c ∈ NA (costo porcada arco), encontrar un circuito de costo mínimo que visite todos los nodos deV . ∑

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, (, ), , y, ,

SeaV (nodos) : |V | = n

A(arcos) : |A| = m

C(costos)

2

1

4

3

4

2

1

3(1, 2, 2)

nodo inicial

nodo final

costo

Figura 2.2

(1, 2, 2), (2, 3, 3), (1, 4, 4), (4, 3, 1), (7)

2.2 Máquinas de Turing 13

∑

= a1, ..., ak

2

1

3

4

6

5

8

9

7 10

Figura 2.3: Orden Lexicográficamente.

(1, 2, 3) (2, 4, 9) (3, 1, 6) (3, 2, 7) (4, 3, 8) (4, 4, 10) (7)

m bloques (ai, bi, ci)

m∑

i=1

(⌈log10(ai + 1)⌉+ ⌈log10(bi + 1)⌉+ ⌈log10(ci + 1)⌉) + 4

≤ m⌈log10(n+ 1)⌉+ ⌈log10(n+ 1)⌉+ ⌈log10(k + 1)⌉+ 4

k := maxi∈ACi

∈ O(m log (n · k))

2.2 Máquinas de Turing

Una máquina de Turing está definida por:

• Un conjunto de estados Q finito.

• Un alfabeto Γ que contiene un símbolo xy (espacio en blanco),∑

= Γ \xy.

• Un conjunto F ⊆ Q de estados de parada.

• Una función de transición δ : (Q\F )× Γ → Q× Γ×M donde M = L,R.


Símbolo de Γ

Figura 2.4

La máquina consiste de:

• Una cabeza lectora/ecritora.

• Una cinta infinita hacia ambos lados, dividida en celdas, donde cada celta con-tiene un símbolo de Γ.

• La máquina está simpre en algún estado q ∈ Q. La cabeza está posicionadasiempre sobre alguna celda.

La máquina de Turing opera de la siguiente manera:

1. Inicialmente, la máquina está en un estado qo ∈ Q.

2. Sean,

q: El estado alcual de la máquina.

s: El símbolo de la celda bajo la cabeza.

Mientras q /∈ F

• Evaluar (q′, s′,m) = δ(q, s).

• Escribir s′ bajo la cabeza.

• Mover la cabeza una celda en la dirección m.

• Pasar al estado q′.

3. Finalizar. Generalmente el contenido de la cinta es el “resultado” de la instanciaque estamos resolviendo.

Ejemplo: 3-state busy beaver

Q = A,B,C,HF = HΓ = 0, 1 donde 0 es el símbolo blanco.qo = Aδ está dada por la tabla de trancisión:


ΓQ

A B C

0 (1,R,B) (0,R,C) (1,L,C)1 (1,R,H) (1,R,B) (1,L,A)

Si la cinta está en “blanco”, es decir, si cada celda contiene el cero.

· · 0 0 0 0 0 0 0 0 · · qo = A δ(A, 0) = (1, R,B)↑

· · 0 1 0 0 0 0 0 0 · · q1 = B δ(0, B) = (0, R, C)↑

· · 0 1 0 0 0 0 0 0 · · q2 = C δ(0, C) = (1, L, C)↑

· · 0 1 0 1 0 0 0 0 · · q3 = C δ(0, C) = (1, L, C)↑

· · 0 1 1 1 0 0 0 0 · · q4 = C δ(1, C) = (1, L,A)↑

· · 0 1 1 1 0 0 0 0 · · q5 = A δ(0, A) = (1, R,B)↑

· · 1 1 1 1 0 0 0 0 · · q6 = B δ(1, B) = (1, R,B)...

· · 1 1 1 1 0 0 0 0 · · q9 = B δ(0, B) = (0, R, C)↑

· · 1 1 1 1 0 0 0 0 · · q10 = C δ(0, C) = (1, L, C)↑

· · 1 1 1 1 0 1 0 0 · · q11 = C δ(0, C) = (1, L, C)↑

· · 1 1 1 1 1 1 0 0 · · q12 = C δ(1, C) = (1, L,A)↑

· · 1 1 1 1 1 1 0 0 · · q13 = A δ(1, A) = (1, R,H)↑

· · 1 1 1 1 1 1 0 0 · · q14 = H↑

Máquina de Copiado Considerar la Máquina de Turing definida por:Γ = 0, 1, 6 b = 0Q = q1, ..., q5, H, F = H

Función de Transición:


ΓQ

q1 q2 q3 q4 q5

0 (0,−, H) (0, R, q3) (1, L, q4) (0, L, q5) (1, R, q1)

1 (0, R, q2) (1, R, q2) (1, R, q3) (1, L, q4) (1, L, q5)

Q δ· 0 1 1 0 0 0 0 · q1 δ(1, q1) = (0, R, q2)

↑· 0 0 1 0 0 0 0 · q2 δ(1, q2) = (1, R, q2)

↑· 0 0 1 0 0 0 0 · q2 δ(0, q2) = (0, R, q3)

↑· 0 0 1 0 0 0 0 · q3

↑· 0 0 1 0 1 0 0 · q4

↑· 0 0 1 0 1 0 0 · q5

↑· 0 0 1 0 1 0 0 · q5

↑· 0 1 1 0 1 0 0 · q1

↑· 0 1 0 0 1 0 0 · q2

↑· 0 1 0 0 1 0 0 · q3

↑· 0 1 0 0 1 0 0 · q3

↑· 0 1 0 0 1 1 0 · q4

↑· 0 1 0 0 1 1 0 · q4

↑· 0 1 0 0 1 1 0 · q5

↑· 0 1 1 0 1 1 0 · q1

↑· 0 1 1 0 1 1 0 · H

↑


Ejercicios

1.

Inicio: · 0 1 1 1 1 0 0 ·↑

Fin: · 0 1 1 1 1 0 0 ·↑

“0” porque la longitud de la palabra es par.

Inicio: · 0 1 1 1 0 1 0 ·↑

“1” porque la longitud de la palabra es impar.

¿Cómo?

↓q2 ↓q2

· 0 1 1 1 1 0 0 ·↑q1 ↑q1 ↑q1

Entonces

q1 q2 q3 q40 (0, R, q3) (0, R, q4) (0, L,H) (1, L,H)1 (1, R, q1) (1, R, q1) — —

Tal que — significa que no va a ocurrir.

2.

Inicio: # 1 0 1 1 0 1 # #↑

Fin: # 1 0 1 1 0 1 # 1↑

“1” porque la longitud de la palabra es impar.

q1 q2 q3 q4# (#, R, q3) (#, R, q4) (0, L,H) (1, L,H)0 (0, R, q1) (0, R, q2) — —1 (1, R, q2) (1, R, q1) — —

3.

0 00 Inicio: # 1 2 0 3 # # #1 012 10 Fin: # 1 2 0 3 # 0 1 1 0 0 0 1 1 # #3 11


ΓQ

qo q1 q2 q3 q4 q5 · · ·

# (#, R,H) (#, R, q2) (0, R, q3) (0, L, q4) (#, L, q5) (0, R, qo) ·0 (#, R, q1) (0, R, q1) (0, R, q2) — (0, L, q4) (0, L, q5) ·1 (#, R, q1) (1, R, q1) (1, R, q2) — (1, L, q4) (1, L, q5) ·2 (#, R, q1) (2, R, q1) — — — (2, L, q5)3 (#, R, q1) (3, R, q1) — — — (3, L, q5)

2.3 Las clases P y NP

Dados:

Π un problema de decisión.

I conjunto de todas las instancias de Π.

Σ un alfabeto.

ϕ : I →∑∗ un esquema de codificación para Π.

Definimos al conjunto L como el conjunto de todas las instancias (palabras aso-ciadas) que tienen respuesta “sí”.

L = ϕ(I) ∈ Σ∗ : la respuesta a I es s

Todo problema de decisión puede escribirse en la forma general

dada ϕ(I) ∈ Σ∗, determinar si ϕ(I) ∈ L.

Decimos que una máquina de Turing M resuelve un problema Π bajo un esquemade codificación ϕ, si:

1. ∀I ∈ I, si la cinta contiene inicialmente ϕ(I), entonces M alcanza el estado deparada en un número finito de operaciones.

2. Cuando M alcanza el estado de parada, la configuración final de la máquina(dada por su estado final, el contenido de la cinta la cinta y la posición de lacabeza) nos permite concluir si ϕ(I) ∈ L.

Sea t(I) el número de operaciones que la máquina M requiere para resolver unainstancia I ∈ I. La función de complejidad (de tiempo) de M está definida por:

tM : N→ N

tM (n) := maxt(I) : I ∈ I, 〈I〉 ≤ n.

Un problema Π se dice polinomial si existen un esquema de codificación ϕ, unamáquina de Turing M y un polinomio p : N→ N tales que:

tM ∈ O(p),

2.4 Problemas NP-completos 19

⇔ ∃no, c ∈ N tal que ∀n ≥ no, tM (n) ≤ cp(n).

P : La clase de todos los problemas de decisión polinomiales.

Un problema Π se llama no determinísticamente polinomial si existen un conjuntoC ⊆ Σ∗ y una relación L2 ⊆ C × Σ∗ tales que:

1. ∀I ∈ I(Π), si ϕ(I) ∈ L entonces existe c(I) ∈ C tal que (c(I), ϕ(I)) ∈ L2.

2. Sea∀I ∈ III Existe c(I) ∈ C tal que

⇔ϕ(I) ∈ L (c(I), ϕ(I)) ∈ L2, 〈c〉 ∈ O (p(I))

3. El problema de decisión auxiliar Π2 definido por:Π2: Dado (c(I), ϕ(I)) ∈ C × Σ∗, determinar si (c(I), ϕ(I)) ∈ L2,es polinomial.

La clase de todos los problemas no determinísticamente polinomiales se denotanpor NP.

P ⊆ NP, c(I) = ∅

2.3.1 Reducciones polinomiales

Dados dos problemas de decisión Π1 y Π2, decimos que Π1 es reducible polinomial-

mente a Π2 (

Π1 −→p

Π2

)

,

si:

1. Existe una máquina de Turing que “transforma” cada instancia I1 de Π1 en unainstancia M(I1) de Π2.

2. ∀I ∈ I(Π1) se tiene que I tiene respuesta sí ⇔M(I) tiene respuesta sí.

Obs: Si ∃Π1 −→p

Π2, y Π2 ∈ P entonces: Π1 ∈ P

P1(〈I1〉)

P2(〈I2〉)

P2 (P1(〈I1〉))

2.4 Problemas NP-completos

2.4.1 El Problema de Satisfactibilidad (SAT)

Estudiaremos a continuación fórmulas del cálculo proposional. Una fórmula es unaexpresión que involucra literales (variables que pueden tomar valores de “verdadero”


o “falso”) y conectores lógicos (operaciones).

Consideraremos los conectores lógicos:

∧ = y

∨ = o

∼ = negacion

⇒ = implicacion

Para toda combinación de valores de los literales se obtiene un valorespacíficopara la fórmula.

Ejemplo Considerar la fórmula: f(x1, x2, x3) = (x1 ∨ x2)→∼ x3 ∧ x1

Si 1 ≡ V , 0 ≡ F

f(0, 0, 0) = 1, f(1, 0, 0) = 1

Una cláusula es una fórmula que involucra literales y literales negados conectadospor la disyunción (∨).

Ejemplos

C1 = x1 ∨ x2 ∨ x3C2 =∼ x1 ∨ x2∨ ∼ x3C3 = x1∨ ∼ x1

El problema SAT es un problema de decisión que puede formularse de la siguientemanera:

Dado un conjunto finito de cláusulas c1, ..., cn, determinar si existe al menos unaasignación de valores de verdad para los literales que hace verdadera a la conjunción.

C1 ∧ C2 ∧ ... ∧ Cm

Ejemplo Existen valores para x1, x2 y x3 tales que

(x1∨ ∼ x2) ∧ (x2 ∨ x3) ∧ (∼ x1∨ ∼ x3)V V V

Sea verdadero si x1 = x2 = 1, x3 = 0

(x1∨ ∼ x2) ∧ (x2∨ ∼ x3) ∧ (x3 ∨ x1)∧ ∼ x1


2.4.2 Teorema de Cook-Levin

Teorema 4. Para todo problema Π ∈ NP, se cumple Π −→p

SAT.

Demostración Sea Π un problema de la clase NP para el cual se ha definido unesquema de codificación ϕ : I(Π) → Σ∗ asociado a un alfabeto Σ. Por definición,conocemos que para toda instancia I ∈ I(Π) con respuesta afirmativa existe uncertificado c(I) cuya longitud |c(I)| está acotada por |c(I)| ≤ p1(〈I〉), para un ciertopolinomio p1 : N→ N.

Por otra parte, el problema Π′ de verificar la validez de c(I) puede resolverseen tiempo polinomial. Es decir, existen una máquina de Turing M y un polinomiop2 : N→ N tales que M resuelve cada instancia I2 := (I, c(I)) ∈ I(Π′) en un númerode operaciones acotado por p2(〈I2〉) = p2(〈I1〉+ |c(I)|).

Definimos la función c : I(Π)→ Σ∗ de la manera siguiente:

c(I) =

c(I), si I tiene respuesta afirmativa,φ, caso contrario.

Consideremos la operación de M al resolver la instancia (I, c(I)) del problema deverificación Π′. Sin restricción de la generalidad, asumiremos las siguientes caracte-rísticas acerca del comportamiento de M .

• Al inicio, la cinta de M contiene ϕ(I) en las celdas 0, ..., n − 1 y contiene c(I)en las celdas −1, ...,−m. Llamaremos en adelante n = 〈n〉.

Observación Sea f : N → N, f ∈ O(p(n)) con p polinomio. ∀n ≥ no,f(n) ≤ p(n) ⇒ ∃ p del mismo grado que p tal que f(n) ≤ p(n). En efecto,p(n) = c p(n) +M , con M = maxf(n) : 0 ≤ n ≤ no.

Es decir, m ≤ p1(n), para un cierto polinomio p1.

c(I) ϕ(I)

︷︸︸︷︷︸︸︷

−m . . . 0 . . . m

[−r ↑ r]

Figura 2.5: n = 〈I〉 = |ϕ(I)|

• La cabeza está originalmente sobre la celda 0.

• Suponemos que Q = 0, ..., q − 1⋃H es el conjunto de estados de M , con

H el estado de parada, y qo = 0 el estado inicial.


• Supongamos que Γ = a1, ..., as son los símbolos del alfabeto.

• Tres funciones de transición están asociadas a M .

δΓ : Q\H × Γ→ Σ

δQ : Q\H × Γ→ Q

δM : Q\H × Γ→ −1, 1, 0 ≡ L,R,−

• Si al terminar la ejecución, la celda O contiene el símbolo a1, entonces la res-puesta de la verificación es “sí”. Si ϕ(I) ∈ L entonces al terminar la ejecuciónla celda O contiene a a1.

• Como M es polinomial, el número de operaciones realizadas por M para resolvercualquier instancia (I, c(I)) de Π′ está acotado por

p2(n+m) = p2(n+ p1(n)) ≤ p3(n),

con p2 y p3 polinomios.

Llamaremos r = p3(n).Notar que los símbolos escritos por M están dentro del intervalo −r, ..., r.

Vamos a definir una instancia de SAT que describa el funcionamiento de M alverificar la instancia I.

Literales

• Qij : 0 ≤ i ≤ r, 0 ≤ j ≤ q − 1Qij = 1⇔M está en el estado j después de i iteraciones.

• Silk : 0 ≤ i ≤ r,−r ≤ l ≤ r, 1 ≤ k ≤ sSikl = 1⇔ si después de i iteraciones la celda l de la cinta contiene el símboloak.

• Hil : 0 ≤ i ≤ r,−r ≤ l ≤ rHil = 1⇔ después de i iteraciones, la cabeza de M está sobre la celda l.

Cláusulas

1. En cada iteración i ∈ 0, ..., r, M debe estar en un único estado.

(a) M debe estar en almenos un estado. (Qio∨Qi1∨ . . .∨Qi(q−1)) ∀ 0 ≤ i ≤ r,(1 + r)q · k símbolos con q− literales.

(b) En cada iteración M debe estar máximo en un estado. ∼ Qij∨ ∼ Qij ∀ 0 ≤

i ≤ r, ∼ Qij∨ ∼ Qij ≤ 2q2(r−1)k símbolos ∀ 0 ≤ j; j ≤ q−1. Los literalesestán acotados por k.


• La longitud total de éstas cláusulas

kr · q+k · 2q(q−1) · r = k(rq+q(q−1) · r) = krq(1+(q−1)) ∈ O(p3(n))

2. En cada iteración, cada celda en −r, ..., r debe contener un único símbolo.

∀ 0 ≤ i ≤ r,−r ≤ l ≤ r

Sil1 ∨ . . . ∨ Sils

∼ Silk∨ ∼ Silk

, ∀ 1 ≤ k, k ≤ s con k 6= k.

• La longitud de éstas cláusulas

k

(

s+ s(s− 1)

2

)

(r + 1)(2r + 1) ∈ O(r2) ∈ O(p4(n))

3. En cada iteración, la cabeza está ubicada exactamente sobre una celda: ∀ 0 ≤i ≤ r

Hi,−r ∨Hi,−r+1 ∨ ... ∨Hi,r−1 ∨Hi,r

∀ − r ≤ l, l ≤ con l 6= l∼ Hi,l∨ ∼ H

i,l

• La longitud de codificación está acotada por:

k

(

(2r + 1) +(2r + 1)2r · 2

2

)

(r + 1) ∈ O(r3) ∈ O(p5(n))

4. Describir las funciones de transición:

δQ : Γ×Q∗ → Q

∀ 0 ≤ i < r, 0 ≤ j < q, −r ≤ l ≤ r, 1 ≤ k ≤ s,

Hil ∧ Silk ∧Qij =⇒ Qi+1,δQ(ak,j)

Lo que puede formularse de manera equivalente como

∼ (Hil ∧ Silk ∧Qij) ∨Qi+1,δQ(ak,j)

⇔ ∼ Hil∨ ∼ Silk∨ ∼ Qij ∨Qi+1,δQ(ak,j)

• Longitud de codificación:

4 · k · r · q · (2r + 1) · 5 ∈ O(r2) ∈ O(p4(n))


5. δΓ :1

Hil ∧ Silk ∧Qij → Si+1,l,δΓ(ak,j)

∼ Hil∨ ∼ Silk∨ ∼ Qij ∨ Si+1,l,δΓ(ak,j)

• Longitud de Codificación ∈ O(p4(n))

6. δm : similar

7. Si la celda l contiene un símbolo ak en la iteración i-ésima, y si la cabeza de Mno está sobre la celda l es ésta iteración, entonces la celda l contiene ak en laiteración i+ 1.

8. Condiciones iniciales y finales:

Q00 H00

v, F0, 1

Asumiendo ϕ(I) = aioai1...ain−1 aio ... ... ain−1

Con aio = 0 si I ∈ L ⇔ a1 ∈ O.

So,l,il 0 ≤ l < n

Sr,o,1

Longitud de codificación ∈ O(n).

Corolario 1. Si SAT ∈ NP, entonces

P = NP.

Corolario 2. Para todo problema Π ∈ NP, si SAT −→p

Π y Π ∈ P, y entonces

P = NP.

Corolario: SiSAT ∈ P ⇒ P = NP

• Un problema de decisión II se llama NP-completo, si:

1. II ∈ NP

2. Si II ∈ P ⇒ P = NP

• Si II (no necesariamente de decisión) satisface al menos el numeral 2 anterior,II se llama NP-difícil.

1Considere que p → q ⇒∼ p ∨ q


2.4.3 Otros problemas NP-completos

Observación: Si II1 es NP-completo y II1p−→II2, entonces II2 es NP-difícil.

Karp 1972.

SAT

CLIQUE-K 3-SAT FACT (Binaries)Programas Binarios

1. δM : Q \ H × Γ→ −1, 1

Qij ∧ Silk ∧Hil → Hi+1,l+δM (ak,j)

∼ Qij∨ ∼ Silk∨ ∼ Hil ∨Hi+1,l+δM (ak,j)

2. Por otro lado:Silk∧ ∼ Hil → Si+1,l,k

∼ Silk ∨Hil ∨ Si+1,l,k

• Si II ∋ NP pero ∀ II’∈ NP, II’−→pII, II es NP-difícil.

II SAT

(SA)II’

p

pp

Karp 1972:2

2(D): Versiones de decisión


SAT

CLIQUE-K 3-SAT FACT PROGENTERA

SETPACKING

(D)

VERTEXCOVER

(D)

CIRCUITOHAMILTONIANO

(D)

SET COVERING(D)

NUMCROMATICO

(D)

3-SAT Caso especial de SAT donde cada cláusula tiene solo 3 literales.

CLIQUE Dados G · (V,E) y k ∈ N, contiene G un subgrafo completo (= clique)con al menos k nodos.

FACT-PROG-ENTERA Dados A ∈ Qm×n, b ∈ Qm ¿Existe un x ∈ 0, 1n talque Ax ≤ b?

SET PACKING Dados X un conjunto y una familia F de subconjuntos de X,F = A1, A2, ..., Am.

Encontrar la subfamilia F ′ ⊆ F tal que

Ai ∩Aj = ∅, ∀ Ai, Aj ∈ F′

|F ′| sea máxima.

(D) Dado además k ∈ N, ¿Existe F ′ tal que |F ′| ≥ k?

VERTEX COVER-Recubrimiento por Vértices Dado G = (V,E), encontrarV ′ ⊆ V tal que toda arista de E sea incidente a al menos un modo de V ′. |V ′|sea mínima.

Figura 2.6


SET COVERING Dados un conjunto X y una familia F de subconjuntos de X,F = A1, ..., Am; encontrar F ′ ⊆ F tal que

∀ a ∈ X, ∃Ai ∈ F′ tal que a ∈ Ai

|F ′| sea mínima.

CIRCUITO HAMILTONIANO Dado G = (V,E) contiene G un circuito (ciclo)que pase por todos sus vértices.

NÚMERO CROMÁTICO

Problema de Coloración: Dado G = (V,E), asignar colores a un grafo, demanera que nodos adyacentes tengan siempre colores distintos. El menor nú-mero de colores necesario se llama el número cromático χ(G) del grafo. Número

cromático: Dados G = (V,E) y k ∈ N ¿Es χ(G) ≤ k?

P NP−difícilM ST (árbol generador) Steiner tree problemcaminos más corto Camino más corto con ventanas de tiempoFlujo máximo Flujo multiproductoFlujo de costo mínimo Flujo multiproductoLP PE

PEM

Cic. Hamiltoniano y agente viajero.

Problemas de Coloramiento

6

5

4

1

2

3

Figura 2.7

r ∈ 1, ..., 6

yr =

1 si se usa el color r0 caso contrario


xir =

1 si se pinta i con color0 caso contrario

min∑6

r=1 yr

s.t.∑6

r=1 xir = 1∀i

xir + xjr ≤ 1, ∀ i, j ∈ E, ∀ r

xir ≤ yr ∀ i, r

xir, yr ∈ 0, 1 ∀ i, r

Capítulo 3

Programas Enteros

3.1 Formulación y aplicaciones

Un problema de optimización combinatoria (optimización discreta), consiste en ma-ximizar o minimizar una función objetivo sobre un conjunto de estructura discreta.

Un programa entero mixto (MIP, mixed integer program) es el problema de mi-nimizar una función lineal sobre una región factible definida mediante restriccioneslineales, bajo la condición adicional de que algunas variables pueden tomar única-mente valores enteros:

(MIP)

mın cTx+ dT ys.r.Ax+ Ey = b,x ∈ Zn1

+ , y ∈ Rn2

+ ,

donde c ∈ Zn1 , d ∈ Zn2 , A ∈ Zm×n1 , E ∈ Zm×n2 y b ∈ Zm.Muchos problemas de optimización combinatoria pueden ser formulados como

MIPs.Las variables x se llaman variables enteras (o variables discretas) y las variables

y son las variables continuas del problema.Si el problema no tiene variables continuas, se conoce simplemente como progra-

ma entero (IP, integer program). Una variable entera que está restringida a tomarúnicamente valores de 0 ó 1 se llama variable binaria. Un programa que contieneúnicamente variables binarias es un programa binario.

3.1.1 Técnicas de modelización

Variables de decisión binarias

Una selección entre dos alternativas posibles puede representarse con una variablebinaria.

Ejemplo Problema de la mochila (KP, Knapsack Problem)

29

30 Programas Enteros

Dados una mochila de capacidad K y n objetos, con pesos w1, . . . , wn y valoresa1, . . . , an, encontrar un subconjunto de objetos tales que la suma de sus valores seamáxima y la suma de sus pesos no sobrepase K.

Introduciendo n variables binarias x1, ..., xn donde

xi = 1⇔ el i-ésimo objeto es seleccionado,

el problema puede formularse como un programa entero:

(KP)

max∑n

i=1 aixis.r.∑n

i=1wixi ≤ K,xi ∈ 0, 1, ∀ 1 ≤ i ≤ n.

Ejemplo: Problemas de empacamiento, particionamiento y recubrimientode conjuntos(Set packing [SSP], set partitioning [SPP], and set covering [SCP] problems)

Dados un conjunto base X, una familia F := A1, A2, . . . , An de subconjuntosde X y una función de costos c : F → Z+, se pide encontrar una subfamilia F ′ ⊆ Ftal que cada elemento de X pertenezca

(empacamiento:) máximo a un conjunto de F ′ y que además∑

Aj∈F ′ c(Aj) seamáxima;

(particionamiento:) exactamente a un conjunto de F ′ y que además∑

Aj∈F ′ c(Aj)sea mínima;

(recubrimiento:) por lo menos a un conjunto de F ′ y que además∑

Aj∈F ′ c(Aj)sea mínima.

Para formular estos problemas como programas enteros, conviene representar alos subconjuntos de F mediante sus vectores de incidencia. Empleamos luego unavariable binaria xj para indicar si un subconjunto de Aj ∈ F será o no incluido en lasubfamilia F ′ a seleccionar.

Sea A ∈ 0, 1m×n, con m = |X| y n = |F|, una matriz cuyas columnas estánformadas por los vectores de incidencia de todos los conjuntos de F . Definimos

b := Ax =n∑

j=1

xjA ·j =∑

j∈F ′

A ·j .

Notar que b ∈ Z+, y que bi indica cuántos conjuntos de la subfamilia F ′ contienen alelemento i ∈ X.

Con esta idea, los tres problemas pueden ser formulados como los programasenteros indicados a continuación.

Empacamiento:

3.1 Formulación y aplicaciones 31

(SSP)

max cTxs.r.Ax ≤ 1,x ∈ 0, 1n.

Particionamiento

(SPP)

mın cTxs.r.Ax = 1,x ∈ 0, 1n.

Recubrimiento

(SCP)

mın cTxs.r.Ax ≥ 1,x ∈ 0, 1n.

Enforzamiento de decisiones

A menudo las decisiones a tomar en un problema son dependientes entre sí. Supon-gamos que una decisión A sólo puede ser tomada si otra decisión B es tomada. Ladecisión A puede representarse por una variable binaria x1 y la decisión B por unavarible x2. Para representar la dependencia entre las dos decisiones podemos usar larestricción de enforzamiento:

x1 ≤ x2.

Notar que como ambas variables son binarias, esta restricción es equivalente a laimplicación lógica

x2 = 0⇒ x1 = 0,

es decir,B no es tomada⇒ A no es tomada.

Ejemplo Problema de localización de instalaciones(Facility Location Problem)

Suponemos dados un conjunto N := 1, . . . , n de usuarios y un conjunto M :=1, . . . ,m de posibles instalaciones a construir, para proveer a los usuarios de undeterminado servicio. El costo de construir la instalación j ∈ M es igual a cj , y elcosto por asignar el usuario i ∈ N a la instalación j ∈M está dado por dij .

El problema consiste en determinar cuáles instaciones construir y cómo asignarlos usuarios a las instalaciones construidas, de tal forma que el servicio sea provistoa todos los usuarios a un costo global mínimo. Cada usuario debe ser asignado a unainstalación.

Emplearemos las siguientes variables de decisión:


yj =

1, si se construye la instalación j ∈M ,0, caso contrario.

xij =

1, si el cliente i ∈ N es asignado a la instalación j ∈M ,0, caso contrario.

La función objetivo a minimizar consiste de los costos de construcción de lasinstalaciones y de los costos de asignación de usuarios a instalaciones:

Costos construcción instalaciones:

m∑

j=1

cjyj

Costos asignaciones usuario-instalación:

n∑

i=1

m∑

j=1

dijxij

Restricciones:

• Cada usuario debe ser asignado exactamente a una instalación.

m∑

j=1

xij = 1, ∀ 1 ≤ i ≤ n.

• Un cliente i puede ser asignado a una instalación j, solo si ésta es construida.Emplearemos aquí la restricción de enforzamiento:

xij ≤ yj , ∀ 1 ≤ i ≤ n, 1 ≤ j ≤ m.

Obtenemos así el siguiente programa entero:

(FLP)

mın

m∑

j=1

cjyj +

n∑

i=1

m∑

j=1

dijxij

s.r.m∑

j=1

xij = 1, ∀ 1 ≤ i ≤ n,

xij ≤ yj , ∀ 1 ≤ i ≤ n, 1 ≤ j ≤ m,

xij ∈ 0, 1, ∀ 1 ≤ i ≤ n, 1 ≤ j ≤ m,

yj ∈ 0, 1, ∀ 1 ≤ j ≤ m.


Restricciones disyuntivas

Asumir que a, b ∈ Zn+ y x ∈ Rn

+. Queremos asegurar que al menos una de las dosrestricciones siguientes se cumpla

aTx ≥ c ∨ bTx ≥ d. (3.1)

Introducimos una nueva variable binaria y ∈ 0, 1. Considerar ahora el sistema derestricciones

(P)

aTx ≥ cy,

bTx ≥ d(1− y).

Sea (x, y) una solución factible a este sistema. Notar que si y = 1, x debe satisfacerforzosamente la primera restricción en (3.1) aunque no necesariamente la segunda(pues de b ∈ Zn

+ se sigue que bTx ≥ 0 para todo x ∈ Rn+ ).

De manera similar, si y = 0, exigimos que x satisfaga la segunda restricción de(3.1) e ignoramos la primera. Por lo tanto, todas las soluciones factibles de P estánasociadas a soluciones que satisfacen al menos una de las desigualdades en (3.1).Puede verse que la implicación inversa también se cumple.

De manera más general, sean a1, . . . , an ∈ Zn+ y x ∈ Rn

+. Nos interesan solucionesque satisfagan al menos m restricciones del siguiente sistema (con m ≤ n):

(P1)

aT1 x ≥ b1,aT2 x ≥ b2,

...aTnx ≥ bn.

Empleando la misma idea utilizada para (3.1), introducimos nuevas variables bi-narias y1, . . . , yn y modificamos las restricciones:

(P2)

aT1 x ≥ b1y1,aT2 x ≥ b2y2,

...aTnx ≥ bnyn,

∑ni=1 yi ≥ m.

Dada una solución (x, y) factible para P2, puede verificarse que, para cualquieri ∈ 1, . . . , n, si yi = 1 entonces x satisface la i-ésima desigualdad del sistema P1.Debido a la última restricción de P2, se tiene que x satisface al menos m desigualdadesde P1.

Variables con valores de un conjunto arbitrario

Suponer que una variable puede tomar únicamente valores de entre un conjunto finitodado:

x ∈ a1, a2, ..., ak ⊂ R.


Esta condición puede modelarse empleando k variables binarias y1, . . . , yk talesque

yi =

1, si x = ai,0, caso contrario.

Introduciendo las restricciones:

k∑

i=1

yi = 1,

x =k∑

i=1

aiyi,

se obtiene el resultado esperado.

EjercicioDado un grafo G = (V,E), el problema de coloración de G consiste en pintar todoslos nodos de V usando el menor número posible de colores, de tal forma que nodosadyacentes reciban siempre colores distintos entre sí.

Formular este problema como un programa entero.

Sugerencia: Notar que una solución factible trivial consiste en pintar los nodosusando n := |V | colores. Para i, k ∈ 1, . . . , n, definir las variables de decisión:

yk =

1, si el color k es empleado en la coloración,0, caso contrario,

xik =

1, si el vértice i es pintado con el color k,0, caso contrario.

Emplear estas variables para expresar restricciones que indiquen que cada nodo debeser pintado exactamente con un color, y que nodos adyacentes deben recibir coloresdistintos. Una restricción de enforzamiento debe garantizar que si el color k es usandoen algún nodo, entonces yk = 1, para todo k ∈ 1, . . . , n. Finalmente, la funciónobjetivo debe medir la cantidad de colores empleados.


Funciones objetivo lineales a trozos

f(x)

x0 x1 x2 · · · xk

(x2, f(x2))

(x1, f(x1))

(x, f(x))

Figura 3.1

(P )

min f(x)s.t.xo ≤ x ≤ xk

x ∈ [x1, xk], x = λ1x1 + λ2x2 con λ1 + λ2 = 1 (Combinación Lineal)

Función Lineal:f(αx+ βy) = αf(x) + βf(y)

f(x) = λ1f(x1) + λ2f(x2)

Si x ∈ [xi, xi+1] con 0 ≤ i < k → ∃ xi, xi+1 tal que

x =λixi + λi+1xi+1

f(x) =λif(xi) + λi+1f(xi+1)

λi + λi+1 = 1; λi + λi+1 ≥ 0

min∑k

i=0 λif(xi)

s.a.∑k−1

i=0 yi = 1 Un tramo a la vez

λo ≤ yoλk ≤ yk−1

λ2 ≤ y1 + y2λi ≤ yi−1 + yi ∀ 2 ≤ i ≤ k − 1

∑ki=0 λi = 1


Solo 2λ son distintos de 0 a la vez.

Aplicación: Problema de secuenciamiento de máquinas

Suponemos que tenemos una máquina capaz de realizar m operaciones distintasM = 1, ...,m. Cada operación requiere de una herramienta j ∈M .

La máquina puede tener cargadas únicamente B < m herramientas a la vez. Lamáquina debe procesar n tareas, cada tarea 1 ≤ i ≤ n requiere de un conjunto Ji ⊆Mde herramientas para que sea procesada. Por simplicidad, supondremos que |Ji| ≤ B.

Para cargar o descargar una herramienta j ∈M , la máquina requiere Sj unidadesde tiempo.

El modo de trabajo es el siguiente:

• Inicialmente, la máquina no tiene herramientas caragadas.

• Para procesar un trabajo i, se cargan previamente todas las herramientas de Jique no estén en la máquina. De ser necesario, se descargan herramientas queno se necesiten.

• El trabajo se procesa sin interrupción.

Modelo:

xir =

1, si el trabajo i se procesa en el r− esimo lugar0, si no

yjr =

1, si la herramienta j esta cargada al procesarel trabajo de la r− esima posicion

0, si no

Con n = 3 y m = 5; J1 = 1, 3, 4, J2 = 2, 3, 5 J3 = 1, 4, 5.

2 1 3H∅ 2, 3, 5 3, 1, 4 1, 4, 5

Cargas-Descargas|Yjr − Yir+1| = 1

x21 = x12 = x33 = 1y21 = y31 − y51 = 1y32 = y12 = y42 = 1

x =

0 1 01 0 00 0 1


0 1 2 3y1r 0 0 1 1y2r 0 1 0 0y3r 0 ↓ 1 1 ↑ 0y4r 0 0 1 1y5r 0 ↓ 1 ↑ 0 ↓ 1 ↑

Restricciones:

• No pueden estar cargadas más de B herramientas.∑

y∈M

Yjr ≤ B

• Cada trabajo debe ejecutarse una sola vez.

n∑

r=1

Xir = 1

• En cada momento, exactamente una tarea debe estar en cada posición.

n∑

i=1

Xir = 1

• Inicialmente la máquina no tiene herramientas cargadas.

Yjo = 0

• ∀ j ∈ Ji, para procesar el trabajo i, se cargan previamente todas las herramien-tas Ji.

Xir ≤ Yjr

Notar que

|Yjr − Yj,r+1| =

1, si la herramienta i fue cargada o descargada0, entre la posicion r y r + 1

La cantidad de cargas/descargas de la herramienta j es

n−1∑

r=0

|yjr − yj,r+1|


Es decir, la función objetivo a minimizar es

minm∑

j=1

n−1∑

r=0

Sj |yjr − yj,r+1|

con |yjr − yj,r+1| = zjr.

zjr = |yjr − yj,r+1|

zjr ≥ yjr − yj,r+1

zjr ≥ yj,r+1 − yjr

zjr ∈ 0, 1.

3.1.2 Calidad de una formulación

Dados un programa entero mixto

(PEM)

min cTx+ dT ys.t.Ax+By = bx ∈ Zn1

+ , y ∈ Rn2

+

Con c ∈ Zn1 , d ∈ Zn2 , A ∈ Zm×n1 , B ∈ Zm×n2 , b ∈ Zm.

La relajación lineal de PEM es el programa lineal

(RL)

min cTx+ dT ys.t.Ax+By = bx ∈ Rn1

+ , y ∈ Rn2

+

Notar que toda solución factible de (PEM) es solución factible de (RL). Es decir,el valor óptimo de (RL) es una cota inferior al valor óptimo de (PEM).

ZRL ≤ ZPEM

Consideremos que las variables de (PEM) están acotadas. Entonces el conjunto:

P := conv(x ∈ Rn1

+ , y ∈ Rn2

+ , Ax+By = b)

es un politopo. Entonces (PEM) puede ser reformulado de la siguiente manera

(PEM ′)

min cTx+ dT ys.t.x ∈ P ∩ (Zn1

+ ×Rn2

+ )


P

Zn1

+ ×Rn2

+

Figura 3.2

Notar que

(RL′)

min cTx+ dT ys.t.x ∈ P

es una relajación lineal de (PEM ′), pues P es un politopo, y por tanto P es lasolución de un sistema de desigualdades lineales. (Ax ≤ b)

Ax+ By = b

ZRL′ ≤ ZPEM ′ = ZPEM

Pero notar que todos los vértices de P tienen por construcción coordenadas enterasde las variables x.

b b

b b

b b

P

y (real)

x (entero)

Figura 3.3

Es decir, todos los vértices son puntos factibles del problema original. De la pro-gramación lineal conocemos que al menos un vértice de P es solución óptima de (RL′).

⇒ Hay al menos una solución óptima de (RL′) que es factible para (PEM ′) y(PEM).

Por lo tanto, (PEM) puede transformarse en un programa lineal


(RL′) =

min cTx+ dT ys.t.

Ax+ By = bx ∈ Rn1

+ , y ∈ Rn2

+

Considerar los dos politopos siguientes

P1 = x ∈ Rn1

+ , y ∈ Rn2

+ : Ax+By = b

P2 = x ∈ Rn1

+ , y ∈ Rn2

+ : Ax+ By = b

Suponer queP1 ∩ (Zn1

+ ×Rn2

+ ) = P2 ∩ (Zn1

+ ×Rn2

+ )

Entonces los dos programas mixtos

(PEM − 1)

min cTx+ dT ys.t.P1 ∩ (Zn1

+ ×Rn1

+ )

(PEM − 2)

min cTx+ dT ys.t.x ∈ P2 ∩ (Zn1

+ ×Rn2

+ )

Son equivalentes si tienen las mismas soluciones factibles (y por lo tanto las mis-mas soluciones óptimas). Se dice en éste caso que (PEM − 1) y (PEM − 2) son dosformulaciones alternativas de un mismo programa entero mixto.

Si además se cumple que P1 ⊆ P2 entonces se tiene para el valor óptimo de lasrelajaciones correspondientes, RL− 1 y RL− 2 que

ZRL−1 ≤ ZRL−2 ≤ ZPEM−1 = ZPEM−2

Decimos entonces que (PEM − 1) es una formulación más fuerte (o de mejorcalidad) para el programa entero mixto.

Las formulaciones más fuertes generalmente se resuelven más eficientemente.

1

2

3

4

5

6

74

21

2 1

3

25

12

3

Figura 3.4

3.2 Formulaciones ideales 41

X34 +X31 +X36 +X35 ≤ 1

Variables de Decisión

Xij =

1, si ij ∈ E es seleccionado dentro del emparejamiento0, caso contrario

max∑

ij∈E

wijXij

∑

j∈V

Xij = 1, ∀ i ∈ V

Xij ∈ 0, 1 ij ∈ E

Figura 3.5

3.2 Formulaciones ideales

Motivación Problema de flujo máximo en una red.

3

5

7

4

2

8 4

6

2

1 2

3 4

5 6

Figura 3.6

Uij : Capacidad sobre el arco (i,j)


Xij : Flujo sobre el arco (i,j)

Formulación como un programa lineal. Sea A el conjunto de arcos:

max∑

(i,t)∈A xi,ts.t.0 ≤ xij ≤ Uij ∀ (i, j) ∈ A (Restriccion de capacidad)

∑

(i,j)∈A xij −∑

(j,i)∈A xji = 0 (Conservacion de flujo)

xij ∈ Z+ ∀ (i, j) ∈ A

Al examinar el algoritmo de solución combinatorio, podemos ver que la soluciónóptima es entera siempre que las capacidades de los arcos sean enteras. Esto sugiereque el poliedro de flujos

PF = x ∈ RA :∑

xij −∑

xji = 0, ∀ i ∈ V \s, t, 0 ≤ xij ≤ uij , ∀ (i, j) ∈ A

tiene únicamente vértice con coordenadas enteras.

En general, consideremos los poliedros siguientes:

P (A, b) = x ∈ Rn+ : Ax ≤ b

P=(A, b) = x ∈ Rn+ : Ax = b

Donde A ∈ Zm×n, b ∈ Qm.

A

AB AN

B ⊆ 1, ..., n︷︸︸︷

(AB, AN )

xB

xN

Figura 3.7

ABxB +ANxN = b

xB = A−1B b−A−1

B ANxN

Se conoce que cada vértice de P=(A, b) está asociado a una base AB, con B ⊆1, ..., n, |B| = m. Las coordenadas del vértice (excepto por permutaciones) están


dadas por (vértice del poliedro):

xB = A−1B b, xN = 0

Teorema 2.1: Regla de Cramer

Si A ∈ Rm×m invertible y b ∈ RM , la solución del sistema Ax = b está dada por:

xi =det(Ai)

det(A)

Donde Ai es la matriz que se obtiene al sustituir la i-ésima columna de A por elvector b.

det(Ai) = k det(A)

Del Teorema 2.1 se sigue que una condición suficiente para que el vector xB seaentero es que det(AB) ∈ ±1.

Por lo tanto, una condición suficiente para que tenga vértices enteros es que:

• b ∈ Zn

• Cada submatriz cuadrada no singular de orden m×m de A tenga determinanteigual a ±1.

Definición

1. Una matriz A ∈ Zm×n de rango completo de filas, se llama unimodular (UM)si e determinante de cada base (cada submatriz cuadrada de orden m × n nosingular es ±1).

En particular si m = 1, A es unimodular si det(A) ∈ 1,−1.

2. Una matriz A ∈ Zm×n se llama totalmente unimodular (TUM) si para todasubmatriz cuadrada B se cumple que det(B) ∈ 0,±1

Ejemplos

A =

(1 1 01 0 1

)

Es TUM

B =

(3 21 1

)

Es UM, pero no TUM

Observación Toda matriz TUM tiene exclusivamente entradas en −1, 0, 1

Definición un poliedro es integral si todos sus vértices tienen únicamente coorde-nadas enteras.


Propiedades

Lema 2.2

1. A es TUM ⇔ (A, I) es UM .

2.

A es TUM ⇔

A−A

I−I

es TUM

3. A es TUM ⇔ AT es TUM .

Teorema 2.3:

1. Sea A ∈ Zm×n de rango completo de filas. A es UM ⇔ P=(A, b) es integralpara todo b ∈ Zm, tal que P=(A, b) 6= ∅

2. Sea A ∈ Zm×n. A es TUM ⇔ P (A, b) es integral para todo b ∈ Zm tal queP (A, b) 6= ∅

Demostración:

1. Se procede a demostrar la primera implicación del teorema 2.3.

⇒

Sea x un vértice de P=(A, b) y AB la base asociada. Las coordenadas de x estándadas por xB = ABb, xN = 0. Por la regla de Cramer (Teorema 2.1), si A esUM , entonces xB es entero

⇐

Sea AB una base de A. Definimos el vector z ∈ Zm de tal forma que

z +A−1B ei ≥ 0, ∀ i ∈ 1, ..., n

donde ei es el i-ésimo vector unitario canónico.

Para i ∈ 1, ..., n. Definimos el vector

b(i) := ABz + ei

Notar que el punto x = (xB, xN )

xB = A−1B b(i) = z +A−1

B ei ≥ 0, xN = 0

es un vértice del poliedro P=(A, b(i)), excepto por el orden de las coordenadas.


Como además b(1) ∈ Zm, se sigue que xB tiene únicamente componentes enteras,

xB = z +A−1B ei

de donde se sigue que A−1B ei ∈ Zm. Es decir, la i-ésima columna de A−1

B es unvector entero. Como esto se cumple para cualquier i:

A−1B ∈ Zm×n, det(A−1

B ) ∈ Z

AdemásAB ∈ Zm×m ⇒ det(AB) ∈ Z

det(I) = det(AB ·A−1B ) = det(AB) · det(A

−1B ) = 1

Se obtiene finalmente que

det(AB) ∈ 1,−1

⇒ A es UM

Ax ≡ bx ≥ 0

⇔Ax+ Iy = bx ≥ 0y ≥ 0

este poliedro es integral ssi el otro es integral

A = (A, I)

P (A,B) es integral ⇔ P = (A′, b) es integral.Lema 2.2

(a) A es TUM ⇔ A es UM ⇔ P = (A′, b) por Teorema 2.3 (1).

(b)

A es TUM ⇔

A−A

I−I

es TUM

Corolario 2.4: Sea A ∈ Zm×n

1. A es TUM ⇔ P=(a, b, µ) := x ∈ Rn : Ax = b, 0 ≤ x ≤ µ es integral (Lema(1)), ∀ b ∈ Zm, µ ∈ Zn (o es vacío).

2. A es TUM ⇔ P (A, a, b, l, µ) := x ∈ Rn : a ≤ Ax ≤ b, l ≤ x ≤ µ es integral,∀ a, b ∈ Zm, ∀ l, µ ∈ Zn.(o es vacío). (Lema(2))


Teorema 2.5: A es TUM si y solo si cada conjunto J de columnas puede particio-narse en dos subconjuntos J1, J2 de tal forma que la suma de las columnas en J1menos la suma de las columnas J2 da como resultado un vector con componentes en0, 1,−1 (J1 o J2) pueden 2n ser vacías.

Demostración (Teorema 2.5)

“⇒” A ∈ 0,±1m×n

Sea A una matriz TUM y J un conjunto de columnas de A. Definimos el vectorde 0, 1n.

dj =

1, si j ∈ J0, si no

Consideremos el poliedro

P := x ∈ Rn|0 ≤ x ≤ d, 1/2 A · d ≤ Ax ≤ 1/2 A · d

Notar que d2 ∈ P por lo que P 6= ∅, P es acotado (P es un politopo).

Es decir, P tiene al menos un vértice. Sea x un vértice de P . Del corolario 2.4(2)sabemos que x es entero y además, como 0 ≤ x ≤ d, se sigue que x ∈ 0, 1n.

Sea y := d− 2x

yj =

±1, j ∈ J0, caso contrario (x ≤ d)

dj − 2xj

Calculemos el valor z = Am×nyn

zj = (A · y)j = (A · d)j − 2(A ·x)j ⋆

Caso I Si (A · d)j = 2k + 1 con k ∈ N

1

2(A · d)j ≤ (A ·x)j ≤

1

2(A · d)j

k ≤ (A ·x)j

Sustituyendo en ⋆

zj =

2k + 1− 2k = 1, si (A− x)j = k

(2k + 1)− 2(k + 1) = 1, si (A− x)j = k + 1

Caso II Si (A− d)j = 2k, con k ∈ N


k ≤1

2(A− d)j ≤ (A− x)j ≤

1

2(A− d)j = k

Y luego de ⋆ se sigue:

zj = 2k − 2k = 0

Es decir, las componentes en z están dadas en 0, 1,−1. Definimos la siguientepartición de Ji

J1 = j ∈ J | yj = 1

J2 = j ∈ J | yj = −1

Además∑

j∈J1

A · j −∑

j∈J2

A · j =n∑

j=1

A · jyj = A · y = z

“⇐′′

Sea A una matriz para la cual todo conjunto J de columnas puede particionarseen dos dos conjuntos (J1, J2) tales que

∑

j∈J1

A · j −∑

j∈J2

A · j ∈ 0,±1n

Sea B una matriz cuadrada no singular de A de orden k × k. Tenemos quedemostrar que det(B) ∈ ±1

Emplearemos inducción sobre k. Tenemos que demostrar que los elementosdet(A) están todos en 0,±1. Ésto se verifica tomando J = j, para 1 ≤j ≤ n.

Si k > 1: Sea r = det(B). Tenemos que demostrar que r ∈ 1,−1. Sea b−1ij el

elemento ij de la matriz B−1, de la regla de Cramer se sigue que:

B ·B−1· j = ej

b−1ij =

det(Bi)

det(B)

Bij : Matriz donde se cambia la columna i por ej Bij : Matriz que se obtiene al

sustituir la i-ésima columna de B por el vector ej .


Por hipótesis de inducción, det(Bij) ∈ 0, 1. Sea B la matriz cuyas entradasson det(Bij). Es decir,

B−1 =1

rB

y hemos demostrado que B tiene todas sus entradas en 0,±1. Además,

B · B · 1 = r · e1 =

r0...0

Sean

J := 1 ≤ j ≤ k |bi1 6= 0

J ′1 := 1 ≤ i ≤ k |bi1 6= 1

Notar que para i = 2, ..., k, se tiene:

∑

j∈J ′

1

bij −∑

j∈J\J1

bij = Bi · · B · 1 = 0

Esto implica que |j ∈ J |bij 6= 0| es un número par, ∀ i = 2, ..., k. Pero éstoimplica que para toda partición (H1, H2) de J se tiene

|∑

j∈H1

bij −∑

j∈H2

bij | ≤ 1 ⇒∑

j∈H1

bij −∑

j∈H2

Bij = 0(⋆⋆)

Por hipótesis, J puede particionarse en dos subconjuntos J1, J2 tales que

∑

j∈J1

A · j −∑

j∈J2

A · j ∈ 0,±1

|∑

j∈J1

bij −∑

j∈J2

bij | ≤ 1

y de (⋆⋆) se sigue que

∑

j∈J1

bij −∑

j∈J2

bij = 0 ∀ i = 2, ..., k

Definiendo z ∈ 0,±1n como

zj =

1, si j ∈ J1−1, si j ∈ J20, si j 6∈ J


Tenemos que B · z = λe1 ⇔ e1 =1λB · z con λ ∈ ±1. En efecto, Bz ∈ 0,±1.

Además, (Bz) 6= 0, pues B es no singular y z 6= 0.

BB · 1 = r ·B · z

λ1 ·B−1

B · 1 =r · z

λ= r

( z

λ

)

Como B · 1 tiene únicamente entradas en 0,±1, se sigue que r ∈ ±1.

Corolario 2.6 A es TUM ssi cada conjunto F de filas puede particionarse en dossubconjuntos F1, F2 de tal forma que la suma de las filas en F1 menos la suma delas columnas en F2 da como resultado un vector con componentes en 0, 1,−1 (F1,F2 pueden ser vacíos).

Ejemplo

A =

1 0 0 1 0 00 1 0 0 0 11 0 0 0 1 00 0 1 0 0 0

J = 1, 3, 4, 5, J1 = 1, 3 y J2 = 4, 5.

∑

J∈J1

A · j =

1011

∑

J∈J2

A · j =

1010

∑

J∈J1

A · j −∑

J∈J2

A · j =

0001

Lema 2.6: Las siguientes matrices son TUM :

1. La matriz de incidencia nodo-arco de un grafo dirigido.

2. La matriz de incidencia nodo arista de un grafo no dirigido bipartito.

3. Las matrices de intervalo:


0 1 0 · · · 01 1 0 · · · 01 1 1 · · · 01 0 0 · · · 11 0 0 · · · 00 0 0 · · · 10 0 0 · · · 00 0 0 · · · 0

Son matrices con entradas 0, 1 donde los 1s de cada columna forman unintervalo consecutivo.

1. D = (V,A)

1

2

3

4

2

1

3

4

5

Figura 3.8

−1 −1 0 0 01 0 −1 −1 00 1 1 0 −10 0 0 1 1

F1

F1

F1

F1

Veamos MTI es TUM

−1 1 0 0−1 0 1 00 −1 1 00 −1 0 10 0 −1 1

∑

j∈J1

A · j = (0, 1,−1)

Dado un conjunto J de columnas MTI , notar que la suma de las columnas en J

es un vector con entradas en 0, 1,−1. Por lo tanto, eligiendo J1 = J y J2 = ∅obtenemos una partición con las propiedades deseadas.

⇒ MTI es TUM

⇔ MI es TUM


2. V1, V2. M = mij = 1 ssi i es incidente aj .

G = (V,E)V = V1 ∪ V2

1 2

3

4

V1 V2

321

654

Figura 3.9

MI =

1 0 0 00 1 1 00 0 0 1

0 1 0 01 0 1 00 0 0 1

Verifiquemos que MTI es TUM :

• Las columnas de MTI pueden particionarse en dos conjuntos, que corres-

ponden a V1 y V2.

• Cada fila tiene exactamente una entrada igual a 1 en las filas de V1 y unaentrada en las filas de V2.

• Dado un conjunto J de columnas construimos la partición (J1, J2), comosigue:

J1 := J ∪ V1

J2 := J ∪ V2

• Notar que la suma de columnas en J1 es un vector con entradas en 0, 1.Lo mismo ocurre con la suma de columnas en J2.

• Por lo tanto,∑

j∈J1

(MTI ) · j

tiene únicamente entradas en 0, 1,−1

Ejemplo


Figura 3.10

Su matriz de incidencia no es TUM .

3. A es una matriz de intervalos.

A =

0 0 1 0 0

0 1 0 0 10 1 0 1 1

1 0 0 1 1

1 0 0 1 11 0 0 1 0

· J1J2J1

· J2· J1· J2

Verificamos que AT es TUM .

• Toda submatriz obtenida borrando filas de A es a su vez matriz de inter-valo.

• J1: filas impares de la submatriz.

• J2: filas pares de la submatriz.

3

4

5

3

2

1

4

2

25 t

Figura 3.11

Flujo de coste mínimo (flujo máximo=corte mínimo):

max cTxa ≤ Ax ≤ a0 ≤ x ≤ u

3.3 Sistemas TDI (Totalmente Dual Integrales) 53

3.3 Sistemas TDI (Totalmente Dual Integrales)

Sean A ∈ Zm×n, b ∈ Qm, c ∈ Qn. Del teorema de dualidad para la programaciónlineal, conocemos que

max cTxs.t.Ax ≤ bx ∈ Zn

≤

max cTxs.t.Ax ≤ bx ∈ Rn

=

max bT ys.t.AT y = cy ≥ 0, y ∈ Rm

≤

max bT ys.t.AT y = cy ≥ 0, y ∈ Zm

⋆

yTAx ≤ yT b

cTx ≤ yT b

Definición Un sistema Ax ≤ b, con A ∈ Zm×n y b ∈ Qm se llama totalmente

dual integral (Totally Dual Integral TDI), si para cada c ∈ Zn el sistema dual:

max bT ys.t.AT y = cy ≥ 0

Tiene una solución óptima entera, en caso de ser acotado.Observación: Si Ax ≤ b es TDI y además

• P = x ∈ Rn|Ax ≤ b es integral.

• c ∈ Zn

Entonces la cadena de desigualdades en ⋆ se cumple todas con igualdad y tenemosun equivalente al Teorema de Dualidad Fuerte para la Programación Entera.

Teorema 2.2 Sea A ∈ Zm×n, b ∈ Zm. Si el sistema Ax ≤ b es TDI entonces

P (A, b) = x ∈ Rn : Ax ≤ b

es integral.

DemostraciónPor simplicidad, supondremos que P (a, b) es acotado. Entonces, P (A, b) tiene al

menos un vértice x. Conocemos que existe I ⊂ 1, ..., n, tal que

AIx = bI (3.2)

donde AI es la submatriz de A formada por las filas con índice en I, y bI son lasentradas de b correspondientes. Seank = |I|, supongo que x 6∈ Zn. De la versión delLema de Farkos para sistemas enteros, existe z ∈ Qk, tal que

zTAI = cT ∈ Zn (3.3)


zT bI = γ 6∈ Z (3.4)

Ax = b Ax ≤ byTA = OT yTA = OT

yT b = r 6= 0 yT b = r < 0y ≥ 0

Notar que en este caso

max cTxs.t.Ax ≤ b

es acotado y x es una solución óptima por 3.1.

zTAIx = cTx = γ AIx = bIzT b ≡ γ zTAIx = bI

cTx = bI

Considerar el programa dual

min bT ys.t.AT y = cy ≥ 0

Por el teorema de Dualidad para PL, este programa también es acotado y paracualquier solución óptima su valor coincide con cTx. Como Ax ≤ b es TDI y c ∈ Zn

(ecuación 3.2), existe una solución óptima y al programa dual tal que yZm.

bT y = cTx = zTAIx = zT bI = γ 6∈ Z

Pero b, y ∈ Zm y por lo tanto bT y ∈ Z ⇒⇐, entonces x ∈ Rn

Ejemplo

P

x1

x2

(3,0)

(2,2)

(0,3)

∆z

Figura 3.12


y − y1 = m(x− x1), m = y2−y1x2−x1

La ecuación de la recta que pasa por (x1, y1), (x2, y2) es

y − y1 =y2 − y1x2 − x1

(x− x1)

1. La recta (0,3),(2,2):

x2 − 3 = 2−32−0(x1 − 0)

2x2 − 6 = −xx1 + 2x2 = 6

2. La recta (2,2),(3,0):

x2 − 0 = 2−02−3(x1 − 3)

x2 = 2x1 + 62x1 + x2 = 6

Entonces: Poliedro Integral

P (A, x) :

x1 + 2x2 ≤ 62x1 + x2 ≤ 6x1, x2 ≥ 0

max x1 + x2 = cTx = (1, 1)T (x1, x2)s.t. x⋆ = (2, 2)x1, x2 ∈ P (a, x) z⋆ = 4

⇔

max x1 + x2s.t.x1 + 2x2 ≤ 6 y12x1 + x2 ≤ 6 y2−x1 ≤ 0 y3 ⋆−x2 ≤ 0 y4 ⋆⋆

El Problema Dual:

min 6y1 + 6y2s.t.y1 + 2y2 − y3 = 12y1 + y2 − y4 = 1y1, y2, y3, y4 ≥ 0

⇔

min 6y1 + 6y2s.t.y1 + 2y2 ≥ 12y1 + y2 ≥ 1yi ≥ 0, i ∈ 1, 2

L asolución óptima del dual no es entera.

y⋆ =

(1

3,1

3, 0, 0

)


−∆z

(13 ,13)

y1

y2

P ′

Figura 3.13

Combinación Canónica

⇔ y1

(n

k

)

+ y2

(2

1

)

+ y3

(−1

0

)

+ y4

(0

−1

)

=

(1

1

)

yi ≥ 0

Ya que (⋆), (⋆⋆) no se cumplen con igualdad. El dual busca representar C comocombinación cónica en función de vectores normales a las caras de P .

Condiciones de Holgura Suplementaria

v1

v2

C

Figura 3.14

v1, v2 son vectores normales a caras de P (A, b).1

Teorema 2.9 Todo Poliedro Racional puede ser descrito por un sistema TDI conA ∈ Zm×n y b ∈ Qm.

1(Teoría Poliedral) Bertsmas, Weismante (“Optimization Over Integers”)


Corolario 2.10 Un poliedro P (A, b) es integral ssi existe un sistema TDI Ax ≤ btal que

P (A, b) = P (A, b)

y además b ∈ Zm

Capítulo 4

Solución de Programas Enteros

4.1 Algoritmo de branch-and-bound

min cTxs.t.Ax ≤ bx ∈ Zn

Ejemplo−2x1 − 3x2

s.t.29x1 +

14x2 ≤ 1

17x1 +

13x2 ≤ 1

x1, x2 ∈ Z

La solución x⋆ = (2, 17; 2, 07), p⋆ = −10, 56

x1 ≤2, 17

(1)= 2

x1 ≥2, 17

(2)= 3

59

60 Solución de Programas Enteros

x⋆ p⋆

Po (2,17; 2,07) −10,56P1 (2,0; 2,14) −10,43 (Rama)P2 (3,0; 1,33) −10 (Rechazo)P3 (2; 2) −10P4 (0; 3) −9P5 (3,38; 1) −9,75P6 ∞P7 −P8 −P9 −P10 −P11 −P12 −

1211

109

P8P7

P6P5P4P3

P2P1

Po

x1 ≥ 5x1 = 4

x2 = 1x2 = 0

x1 ≥ 4x1 = 3

x2 ≤ 2 x2 ≥ 3 x2 ≤ 1 x2 ≤ 2

x1 ≤ 2 x1 ≥ 3

Figura 4.1

4.2 Relajación Lagrangeana

Considerar el siguiente programa entero:

4.2 Relajación Lagrangeana 61

(IP )

IP max cTxs.t.A1x ≤ b1A1x ≤ b1 x ∈ Zn

donde c ∈ Zn, A1 ∈ Zm1×n, b1 ∈ Zm1 , A2 ∈ Zm2×n, b2 ∈ Zm2 . Suponer quese dispone de algún método eficiente; por ejemplo (algoritmo ccombinatorio) pararesolver el problema:

(IP − 1)

max cTxs.r.A1x ≤ b1x ∈ Zn

IP−1 es una relajación de IP , por lo que su valor óptimmo es una cota superior alvalor óptimo del problema original. Sea λ ∈ Qm2

+ . Definimos la relajación lagrangeana

de IP respecto a λ como:

(RLλ)

max cTx+ λT (b2 −A2x) = cTx− λTA2x+ λT b2= λT b2 + (cT − λTA2)x

s.t.A1x ≤ b1x ∈ Zn

Notar que el valor óptimo de RLλ puede calcularse resolviendo una instancia delIP − 1. De esta manera es posible definir una función

z : Qm2

+ → Q

que asocia a cada λ el valor óptimo Z(λ) de RLλ.Lema 3.1 Para todo λ ∈ Qm2

+ ,

Z(λ) ≥ ZIP

Demostración

Cx⋆ cTx⋆ = ZIP

Sea x⋆ una solución óptima de IP . Notar que x⋆ debe satisfacer las restricciones

A1x⋆ ≤ b1

A2x⋆ ≤ b2 ⇔ b2 −A2x

⋆ ≥ 0

x⋆ ∈ Zn

Luego,


ZIP = cTx⋆ ≤ cTx⋆ + λT (b2 −A2x⋆) ≤ Z(λ)

La última desigualdad se da porque x⋆ es factible para RLλ.

Definición La cota lagrangeana de IP , respecto a las restricciones A2x ≤ b2 es elvalor.

ZDL = minλ≥0 Z(λ) Dual Lagrangeano

Corolario Del Lema 3.1. Se tiene que

ZDL ≥ ZIP

Teorema 3.2 Teorema de Dualidad Lagrangeana. Sea F := x ∈ Zn : A1x ≤ b1.Entonces,

ZDL =

max cTxs.r.A2x ≤ b2x ∈ conv(F)

Con

conv(F) =

n∑

i=1

αixi, αi ≥ 0,n∑

i=1

αi = 1

Demostración Por definición, tenemos que

z(λ) = maxx∈F cTx+ λT (b2 −AT

2 x)

Conocemos además que z(λ) puede calcularse de forma equivalente como:

z(λ) = maxx∈conv(F) cTx+ λT (b2 −A2x) = λT b2 + maxx∈conv(F) c

T − λTA2x

Como conv(F) es un poliedro, siempre es posible escribirlo como

conv(F) = conv(V) + cone(Y)

Donde V = v1, ..., vI (vértices) y Y son finitos. Ademas W = w1, ..., wJ(rayos) y para cualquier λ ≥ 0.1

1Ziegler, G: “Lectures on Polytopes


z(λ) =

+∞ si ∃j ∈ 1, ..., J tal que (cT − λT −A2)Wj > 0

max1≤i≤I λT b2 + (cT − λTA− 2)vi, caso contrario

De aquí se concluye que ZDL es el óptimo del problema.

ZDL = minλ≥0 Z(λ) =

minλ≥0 max1≤i≤I λT b2 + (cT − λTA2)vi

s.t.(cT − λTA2)wj ≤ 0 ∀ j ∈ 1, ..., Jλ ≥ 0

De manera equivalente

ZDL =

min ys.t.y ≥ λT b2 + (cT − λTA2)vi ∀ 1 ≤ i ≤ I(cT − λTA2)wj ≤ 0, ∀ j ∈ 1, ..., J ∀ 1 ≤ j ≤ Jλ ≥ 0, y ∈ R

=

min ys.t.y − λT (b2 −A2vi) ≥ cT vi ∀ 1 ≤ i ≤ I αi

λTA2wj ≥ cTwj , ∀ j ∈ 1, ..., J ∀ 1 ≤ j ≤ J βjλ ≥ 0, y ∈ R

Donde usando el Teorema de Dualidad de la PL

ZDL =

max

I∑

i=1

αicT vi +

J∑

j=1

βjcTwj

I∑

i=1

αi = 1

I∑

i=1

αi(A2vi − b2)T →

J∑

j1

βi(A2wj)T ≤ 0

αi ≥ 0, βj ≥ 0


(A2v1 − b2)T

...(A2vI − b2)

T

(A2w1)T

...(A2wI)

T

αi

βi

ZDL =

max cT

I∑

i=1

αivi +J∑

j=1

βjwj

A2

I∑

i=1

αivi +

J∑

j=1

βjwj

≤ b2

I∑

i=1

αi

I∑

i=1

αi = 1

αi ≥ 0, βj ≥ 0

Sustituyendox =

∑

i

αivi +∑

j

βjwj

Obtenemos:

ZDL =

max cTxs.t.A2x ≤ b2

x =I∑

i=1

αivi +J∑

j=1

αjwj

I∑

i=1

αi = 1

αi ≥ 0, βj ≥ 0

x ∈ conv(V) + cone(W)

m

x ∈ conv(F)


Corolario 3.4ZLP ≥ ZDL ≥ ZIP

Demostración (Relajación Lineal)

• La desigualdad zDL ≥ zIP se sigue del Corolario.

• Para la desigualdad zLP ≥ zDL, basta notar que toda que toda solución factiblede (DL) satisface A2x ≤ b2 y A1x ≤ b1, y por lo tanto es una solución factiblea LP .

Corolario 3.5

1. zDL = zIP para todo c ∈ Zn ssi

conv(F ∩ x| A2x ≤ b2) = conv(F) ∩ x| A2x ≤ b2

2. zDL = zLP para todo c ∈ Zn ssi

conv(F) =x| A1x⋆ ≤ b1

=x| A1x ≤ b1

Ejemplo (Cota Held-Karp) Agente Viajero

Considerar el problema del agente viajero sobre un grafo completo no dirigidoG = (V , E), con vector de costos c ∈ ZE . Este problema puede formularse como unprograma entero con un número exponencial de restricciones.

(ISP )

min∑

e∈E

ceχe

s.t.

∑

e∈δ(V )

χe = 2, ∀ v ∈ V (1)

∑

e∈E[δ]

χe ≤ |s| − 1, ∀ s ⊆ V , s 6= ∅, s 6= V (2)

χe ∈ 0, 1 ∀ e ∈ E

δ(V) : δ(V) = vi ∈ E


E[s] : E[s] = ij ∈ E|i ∈ S, j ∈ S

Las restricciones (1) se llaman restricciones de grado, las restricciones (2) se llamanrestricciones de eliminación de subtuores.

(A) Sea 1 ∈ V un nodo arbitrario del grafo. Añadiendo restricciones redundantes,TSP puede reescribirse en la forma:

(TSP − 2)

min∑

e∈E

ceχe

s.t.∑

e∈δ(V)

χe = 2, ∀ v ∈ V\1 (1a)

∑

e∈γ(1)

χe = 2 (1b)

∑

e∈E[s]

χe ≤ |s| − 1, ∀s ⊆ V\1, s 6= ∅ (2′)

∑

e∈E[s\1]

χe = |V| − 2 (3)

χe ∈ 0, 1, ∀ e ∈ E

Si relajamos las restricciones (1a), entonces el conjunto de soluciones factibles delproblema son vértices de incidencia de subgrafos de 6 que tienen dos características:

• Forman un árbol generador sobre V\1.

• Tienen exactamente dos aristas incidentes al nodo 1.

Este tipo de subgrafos se conocen como 1-árboles. Notar que los toures son uncaso especial de 1-árboles.

1V\1 si es un tour

V\1 no es un tour

Figura 4.2


Encontrar un 1-árbol de costo mínimo puede hacerse de forma eficiente modifican-do alguno de los cálculos de árboles generadores de costo mínimo. De ésta forma z(λ)puede ser evaluada de manera eficiente para cualquier λ ≥ 0. Esto se combina conun esquema numérico para encontrar zDL (método del sublagrangeano). Los costosobtenidos de esta manera se llaman cotas Held-Karp.

conv(F) = x ∈ Rn| A1x ≤ b1

¿Cómo minimizar Jz(λ)? Considerar un PE

(PE)

max − 3x1 + x2s.t.−x1 + x2 ≤ −1 [⋆]−x1 + 2x2 ≤ 53x1 + 2x2 ≥ 36x1 + x2 ≤ 15x1, x2 ≥ 0x1, x2 ∈ Z

-3 -2 -1 0 1 2 3 4 5-2

-1

0

1

2

3

4

5

Figura 4.3

Relajemos [⋆] empleando un multiplicador λ ≥ 0, λ ∈ R.

(Rlλ) =

z(λ))max − 3x1 + x2 + λ(1 + x1 − x2)s.r.−x1 + 2x2 ≤ 53x1 + 2x2 ≥ 36x1 + x2 ≤ 15x1, x2 ∈ R+


v1 v2

v3v4

v5

v1 = (1, 3)

v2 = (2, 3)

v3 = (2, 0)

v4 = (1, 0)

v1 = (0, 1)

Figura 4.4

V = V1, v2, ..., V5

z(λ) = max1≤i≤5 λ+ (λ− 3)x1 + (λ+ 1)x2

z(λ) en

V1 : λ

V2 : −3

V3 : 3λ− 6

V4 : 2λ− 3

V5 : −λ+ 2

z(λ) = max −λ,−3,−3λ− 6, 2λ− 3,−λ+ 2

−λ+ 2 y 3λ− 6 ⇒ λ = 2

−λ+ 2 y 2λ− 3 ⇒ λ = 53


-2 -1 0 1 2 3 4 5-2

-1

0

1

2

3

4

5

3λ− 6

−λ+ 2

2λ− 3

z(λ)

λ

(53 ,

13

)

(3, 3)

Figura 4.5

zDL = z(λ) =

−λ+ 2, si 0 ≤ λ ≤ 53

2λ− 3, si 53 ≤ λ ≤ 3

3λ− 6, si λ > 3

minλ≥0 z(λ) = z

(5

3

)

= 2

(5

3

)

− 3 =1

3

Lema 3.6 La función z : Rn+ → R es convexa, es decir, ∀ α ∈ [0, 1], ∀ λ1, λ2 ∈ Rn

+

z(αλ1 + (1 + α)λ2) ≤ αz(λ1) + (1− λ)z(λ2)

Demostración

Sea λ⋆ = αλ1+(1−α)λ2. Sea x⋆ la solución óptime del problema PLλ⋆ , es decir:

z(λ⋆) = cTx⋆ + (λ⋆)T (b2 −A2x⋆) (⋆)

Como x⋆ es además solución factible para los problemas RLλ1, RLλ2

z(λ1) ≥ cTx⋆ + λT1 (b2 −A2x

⋆) ·α (4.1)

z(λ2) ≥ cTx⋆ + λT2 (b2 −A2x

⋆) · (1− α) (4.2)

Sumando 4.1 y 4.2:


αz(λ1) + (1− α)z(λ2) ≥αcTx⋆ + αλT

1 (b2 −A2x⋆) + (1− α)cTx⋆ + (1− α)λT

1 (b2 −A2x⋆)

=cTx⋆ +[αλT

1 + (1− α)λT2

](b2 −A2x

⋆)

=cTx⋆ + (λ⋆)T (b2 −A2x⋆)

=z(λ⋆)

Lema 3.7 Una función f : Rn → R es convexa ssi paar todo x⋆ ∈ Rn, existe unvector s ∈ R tal que

f(x) ≥ f(x⋆) + s⋆(x− x⋆) ∀ x ∈ Rn

Demostración

(Ejercicio) Modificar el teorema del hiperplano de separación para regiones con-vexas.

Un vector s ∈ Rn que cumple las características del Lema 3.7 es un subgradiente

de f en el punto x⋆. El conjunto de todos lod subgradientes de f en x⋆ se llama elsubdiferencial de f en x⋆ y se denota por ∂f(x⋆). Notar que si f es diferenciable enx⋆, entonces:

∂f(x⋆) = ∇f(x⋆)

Por otra parte, para funciones como z(λ), ∂z(λ) puede ser un conjunto infinito.

Lema 3.8 Sea f : Rn → R convexa. Si x⋆ ∈ R es tal que O ∈ ∂f(x⋆), entonces x⋆

minimiza f sobre Rn.

Demostración

Basta sustituir s = 0 en el Lema 3.7.

f(x) ≥ f(x⋆), ∀x ∈ Rn

4.3 Métodos del planos cortantes 71

Lema 3.9 Sean

z(λ) = max1≤i≤I hi + λT fi

E(λ) = 1 ≤ i ≤ I|z(λ) = hi + λT fi

Entonces para λ⋆ > 0 se tiene:

1. ∀ i ∈ E(λ), fi ∈ ∂z(λ⋆)

2. ∂z(λ⋆) = conv(fi, i ∈ E(λ))

Método del subgradiente

1. Elegir λo ∈ Rn+, L = 0.

2. Si O ∈ ∂z(λ⋆)→ FN

3. Seleccionar s ∈ ∂(λt)

∀ j = 1, ..,m λjt+1 = max λ⋆j + θts

⋆j > 0

4. t = t+ 1, regresar al paso 2.

4.3 Métodos del planos cortantes

Motivación Considerar el siguiente programa entero:

(PE)

max 2x1 + 3x2s.t.x1 + 2x2 ≤ 5 (1)3x1 + 2x2 ≤ 9 (2)x1, x2 ∈ Z+


0 1 2 3 4 50

1

2

3

4

5

b

b

b

b

b

b

b

b

b

(2, 32)

x2

Suma de Desigualdades

Plano Cortante

Figura 4.6

La relajación de lineal de PE tiene por solución óptima a x =(2, 32), cuyo valor

es z = 172 . Sumando las desigualdades (1) y (2), obtenemos una nueva desigualdad

redundante para el sistema

4x1 + 4x2 ≤ 14 ⇔ x1 + x2 ≤7

2

Si x1, x2 ∈ Z de x1 + x2 ≤ 3,5 podemos conluir que

x1 + x2 ≤ 3 (3)

Esta nueva desigualdad es válida para todas las soluciones factibles de PE peropuede ser violada por algunas soluciones de su relajación lineal. Por ejemplo:

x1 + x22 =7

2> 3

Agregando (3) al sistema obtendremos una nueva formulación para el programaentero.

(PE − 2)

max 2x1 + 3x2s.t.x1 + 2x2 ≤ 5 (Se corta el punto optimo)3x1 + 2x2 ≤ 9x1 + x2 ≤ 3x1, x2 ∈ Z+

Al resolver la relajación lineal de (PE − 2) se obtiene el óptimo de programaentero x⋆ = (1, 2) cuyo valor es z⋆ = 8.

• ¿Es posible llegar siempre al óptimo de un programa entero empleando unasucesión de planos cortante?

• ¿Hay algún método sistemático para hacerlo?


• ¿Es eficiente?

En general, consideramos en adelante el siguiente programa entero:

(PE)

max cTxs.t.Ax ≤ bx ∈ Zn

con c ∈ Zn, b ∈ Zm y A ∈ Am×n. Sean P = x ∈ Rn|Ax ≤ b y F = P ∩ Zn.Asumiremos que P es un polítopo, P 6= ∅ y que el rango por filas de A es n. Vamosa suponer que x⋆ es una solución óptima de la relajación lineal (PE), es decir,

cTx⋆ ≥ cTx, ∀ x ∈ P

Podemos asumir que x⋆ es un vértice de P . Sea I ⊆ 1, ...,m el conjunto deíndices de desigualdades del sistema Ax ≤ b que x⋆ satisface con igualdad: Entoncesx⋆ es la solución única del sistema de ecuaciones.

aTi x⋆ = bi, ∀ i ∈ I (⋆)

Sea C el cono generado por los vectores ai : i ∈ I, al mismo que notaremos enadelante

C = cone(Ai) =

∑

i∈I

yiai

∣∣∣∣∣yi ≥ 0, ∀ i ∈ I

a1

a2

x⋆Conjunto

Generador

Figura 4.7

Para todo d ∈ C y x ∈ P se cumple que:

dTx =∑

i∈I

(yiaTi )x ≤

∑

i∈I

yibi =∑

i∈I

yiaTi x

⋆

↑ ↑ ↑d ∈ C aTi x ≤ bi (⋆)

= dTx⋆


En particular, si d ∈ C∩Zn y x ∈ F , entonces dTx ∈ Z y de la última desigualdadpodemos concluir que

dTx ≤ dTx (⋆⋆)

es válida para F .

• Además si dTx⋆ 6∈ Z, entonces la desigualdad (⋆⋆) es un plano cortante quedescarta la solución fraccionaria x⋆.

Se conoce que existe un conjunto generador entero H = h1, ..., hk para C ∩Zn,el mismo que tiene la propiedad:

∀ d ∈ C ∩Zn :

d =k∑

i=1

αihi, con αi ∈ Z+

El siguiente resultado afirma que basta con examinar el conjunto H para encontrarplanos cortantes.

Lema 3.10

1. x⋆ ∈ Zn ⇔ hTx⋆ ∈ Z, ∀ h ∈ H

2. Para todo d ∈ C ∩Zn, la desigualdad

dTx ≤ dTx⋆

está dominada por una combinación convexa de las desigualdades

hTx ≤ hTx⋆, h ∈ H

Demostración

1. ⇒ Es trivial (n ∈ Zn, ∀ n ∈ H).

2. ⇐ sup x⋆ 6∈ Z. De aquí se sigue que el sistema de ecuaciones

aTi x = bi, ∀ i ∈ I

no tiene solución entera. La versión entera del Lema de Farkos garantiza laexistencia de un vector y ∈ Qm

+ , con yi = 0, ∀ i 6∈ I tal que:

dT := yTA ∈ Zn, yT b 6∈ Z (1)∑

i∈I

yiAi

yTAx = yT b

Luego, d ∈ C ∩Zn, es decir,


d =k∑

i=1

αihi con αi ∈ Z+ (2)

Pero ahora:

yT b =∑

i∈I

yibi =∑

i∈I

yiaTi x

⋆ =

(∑

i∈I

yiaTi

)

x⋆ = dTx⋆

↑(⋆)

(1) = dTx =

(h∑

i=1

αihTi

)

x⋆ =h∑

i=1

αi(hTi x

⋆)

↑(2)

Como yT b 6∈ Z se concluye que hTi x⋆ 6∈ Z para al menos un hi ∈ H.

3. Si d ∈ C ∩Zn, entonces d =∑k

i=1 αihi, con αi ∈ Z+

dTx =k∑

i=1

αihTi x ≤

k∑

i=1

αihTi x

⋆ ≤k∑

i=1

αihTi x

⋆ = dTx⋆

x⋆

d

Figura 4.8

max dTx ⇔ dTx⋆ ≥ dTx ∀ x ∈ Ps.t. d ∈ Zn

x ∈ P ⇒ dTx ≤ dTx⋆

1. d ∈ Zn (x entero).

2. dTx⋆ ≥ dTx, ∀x ∈ P

3. dTx⋆ 6∈ Z


C = ∑

yiai|yi ≥ 0

d ∈ C ∩Zn vector candidato a plano cortante.

4.3.1 Algoritmo general de planos cortantes

1. Hacer t = 0, Ao = A, bo = b, Po := x ∈ Rn|Ax ≤ b

2. Resolver: max cTx, x ∈ Pt

Si Pt = ∅ → FIN. El problema no tiene solución factible. Caso contrario, sea xtuna solución óptima.

3. Si xt ∈ Zn → FIN. xt es la solución óptima al PE.

4. Sea I el conjunto de índices de desigualdades del sistema que se satisfacenconigualdad por xt.

5. Determinar un conjunto generador entero para cone(AI)∩Zn. Sea Ht = ht1, ..., htk

este conjunto.

6. Fijar

At+1 =

At

ht1...htk

bt+1 =

btht1xt

...htkxt

Pt+1 = x ∈ Rn : At+1x ≤ bt+1 Po ⊇ P1 ⊇ P2 ⊇ · · ·PI

7. t = t+ 1 y regresar a 2.

Observación

Se ha demostrado que este algoritmo termina en un número finito de iteraciones,si en cada paso xt se elige como la solución óptima lexicográficamente más pequeña.Esto puede conseguirse, por ejemplo, utilizando el algoritmo del simplex con la reglade pivotaje del índice más pequeño. Es decir, cuando existan varios candidatos paraentrar/salir de la base, seleccionamos aquel con el índice más pequeño.

(1, 2, 0)→ (0, 1, 1)

(0, 1, 2)(0, 1, 0) ←


4.3.2 Cortes de Gomory

Considerar el programa entero

(PE)

max cTxs.t.Ax = bx ∈ Zn

+

con A ∈ Zm×n, b ∈ Zm, c ∈ Zn. Suponer que la relajación lineal de (PE) ha sidoresuelta con el algoritmo del simplex hasta encontrar una solución óptima básica,x⋆ = (x⋆B, x

⋆N ) con B ⊆ 1, ..., n el conjunto de índices de la base.

A = (AB,AN )

Con A matriz cuadrada invertible y B base.

ABxB +ANxN = b

Con xB las variables básicas y xN las variables no básicas.

xB = A−1B (b−ANxN ) = A−1

B b−A−1B ANxN

Denotaremos b := A−1B b y AN = A−1

B AN . La ecuación anterior puede escribirseen la forma

xB = b−ANxN ⇔ xi = bi −∑

j∈N

aijxj , ∀ i ∈ B ⇔ xi +∑

j∈N

aijxj = bi

Como xj ≥ 0 ∀ j ∈ N , de ésta última ecuación se sigue:

xi +∑

j∈N

aijxj ≤ bi, ∀ i ∈ B

Por lo tanto, las siguientes desigualdades son válidas para todas las solucionesenteras.

xi +∑

j∈N

aijxj ≤ bi

Cada vez que bi 6∈ Z, ésta expresión genera un plano cortante conocido comoCorte de Gomary.

4.3.3 Rango de Chvátal de un poliedro

Un hiperplano de soporte (aTx) de un poliedro P ⊆ Rn es un hiperplano h = x ∈Rn : aTx = b tal que:

1. P ∩H 6= ∅


2. P ⊆ x ∈ Rn| aTx ≤ b

Notar que P ∩H es una cara de P .

La clausura de CHvótal de un poliedro P es el conjunto P ′ := x ∈ R| aTx ≤ b,para todo hiperplano de soporte aTx = b de P con a ∈ Zn.

cTx = b = cTx⋆

x⋆

Figura 4.9

Teorema 3.11 Sea P = x ∈ Rn| Ax ≤ b con A ∈ Zm×n, b ∈ Qm tal que elsistema Ax ≤ b es TDI.

EntoncesP ′ = x ∈ Rn| Ax ≤ b

Demostración

Sea Q = x ∈ Rn| Ax ≤ b.

PD: P ′ ⊆ Q.Sea x ∈ P ′. Sea aTi x ≤ i la i-ésima del sistema Ax ≤ b. Notar que está desigualdadde soporte para P . Luego

aTi x ≤ bi

⇒ Ax ≤ bx ∈ Q.

PD. Q ⊆ P ′

Sea x ∈ Q, c ∈ Zn

Sea cTx ≤ d una desigualdad de soporte arbitraria para P . Conocemos que:

d = max cTx| x ∈ P

= max cTx| x ∈ Rn, Ax ≤ b

= min bT y| y ≥ 0, y ∈ Rm, AT y = c, y ≥ 0

Además, como Ax ≤ b es TDI, existe y ∈ Zm+ tal que bT y = d. Se sigue que:


cTx = yTAx ≤ yT b = yT b ≤ yT b = d

↑ ↑x ∈ Q b ≤ bAx ≤ by ≥ 0 y ≥ 0

Como el hiperplano cTx = d fue elegido arbitrariamente, entonces podemos con-cluir x ∈ P ′

⇒ Q ∈ P ′

Corolario 3.12 Para todo poliedro P ⊆ Rn tenemos que

P ′ es un poliedro

Demostración

Del Teorema 2.9, conocemos que todo poliedro puede ser escrito como el conjuntosolución de un sistema TDI.

Observación

Notar que

1. conv(P ∩Zn) ⊆ P ′ ⊆ P

2. P ′ es un poliedro.

Considerar la sucesión de poliedros

P o = P Procedimiento de G− CP 1 = P ′

...P k+1 = (P k)′

Notar que

P o ⊇ P 1 ⊇ P 2 ⊇ ... ⊇ P k+1 ⊇ ... ⊇ conv(P ∩Zn) = PI

Lema 3.13 Sea F una cara de P (Recorddar que F es a su vez un poliedro).

F ′ = P ′ ∩ F


Demostración

Sea cTx ≤ d el hiperplano de soporte que define F , es decir,

F = x ∈ P | cTx = d

= x ∈ Rn| Ax ≤ b, cTx ≤ d, −cTx ≤ −d

Suponemos que Ax ≤ b es TDI. Suponemos además que c ∈ Zn y d ∈ Z. Notarque el sistema

Ax ≤ bcTx ≤ d−cTx ≤ −d

es también TDI. Luego,

F ′ = x ∈ Rn| Ax ≤ d, cTx ≤ d,−cTx ≤ −d

por el Teorema 3.10. Por lo tanto,

P ′ ∩ F = x ∈ Rn| Ax ≤ b ∩ x ∈ Rn, Ax ≤ b, cTx = d

= x ∈ Rn| Ax ≤ b, cTx ≤ d ∧ −cTx ≤ −d

= x ∈ Rn| Ax ≤ b, cTx ≤ d, cTx ≤ −d, porque d ∈ Z

= F ′

luis miguel torres - math.epn.edu.ecltorres/inv-oper-3/apuntes.pdf · cuaderno de matemática no. 1...

Documents