lalala

Problemas de Programación Entera

(PLE)

Min

c.x
Ax=b
x≥0, entero

Min

c.x
Ax=b
x{0,1}

A menudo son de la forma

(PLE)

(P) Min

- 2 x1x1 +
- x1+

x2
x2  5
x2

6 x1 + 2 x2
(5/2, 5/2)

(11/4, 9/4)
•

•
(0,0)
•

•

•

•

•

•

(7/2, 0)

x1

, x2  0 enteras

0
 21

PROBLEMAS DE PROGRAMACIÓN ENTERA
(P) Min

- 2 x1x1 +

x2
x2 5

- x1+ x2

0

6 x1 + 2 x2  21
x1 , x2  0 enteras

S={(0,0), (1,0), (2,0), (3,0),
(1,1), (2,1), (3,1), (2,2)}
(5/2, 5/2)

(11/4, 9/4)
•

•
(0,0)
•

•

•

•

Conv(S)
x1 + x2 ≤ 4
x1 ≤ 3

•

•

(7/2, 0)

Algunos Problemas de Programación Entera:

•
•
•
•
•
•
•
•

Problema de la mochila
Problema del viajante de comercio
Problemas de Localización dePlantas
Problemas de Itinerarios de vehículos
Problemas de asignación de tareas
Problemas de secuenciación de tareas
Problemas de Flujos en redes
Problemas en grafos



Problema de optimización combinatoria con
función objetivo lineal
Dada (E, ℑ, c), donde
E: conjunto finito
Ա  c (E) : conjunto de soluciones factibles
(eventualmente multiconjuntos)
c: E  ℝ, que induce unafunción lineal
e ce
Hallar I* Ա tal que

c: Ա  Թ,
I  ∑eE ce

c(I*) = min c(I)
I Ա

Aunque E es finito la resolución del problema mediante la enumeración
de todas las soluciones factibles no suele ser una posibilidad real.

Ejemplo
•

E={1, 2, 3, 4},

•

I ={IE ;  aj  k}, con a=(6, 5, 4, 7) y k=12

•

c=(3, 2, 6, 4)

Encontrar el conjunto factible de coste máximoEjemplo
•

E={1, 2, 3, 4},

•

I ={IE ;  aj  k}, con a=(6, 5, 4, 7) y k=12

•

c=(3, 2, 6, 4)

I
{1}
{1, 2}
{1, 3}
{2}
{2, 3}
{2, 4}
{3}
{3, 4}
{4}

c(I)
3
3+2
3+6
2
2+6
2+4
6
6+4
4



Max  ce : I  I  Max c( I )  c({3, 4})  10
 eI
 II

Ejemplos de Problemas de Optimización Combinatoria (1)

Problemas de Matching
Dado un grafo G=(V,E), MEes un Matching si cada nodo es incidente con como mucho
(exactamente) una arista de M

de cardinalidad máxima
Encontrar el matching
de coste total mínimo (suponemos que cada arista tiene un coste)

Matching de cardinalidad máxima
(no es perfecto)

Matching perfecto

Ejemplo de formulación de un Problema de Matching Perfecto de coste mínimo
como
Problema de OptimizaciónCombinatoria

Conjunto de base E ?
1

3

2

3
4

2

1

5

1

6
4

5

4

6

Conjunto de elementos factibles I ?

Ejemplos de Problemas de Optimización Combinatoria (2)

Problema del viajante de comercio (TSP)
Dado un grafo G=(V, E) un circuito hamiltoniano es un circuito (camino cerrado que no repite
ningún nodo) que pasa por todos los nodos.
Suponemos que tenemos un costeasociado a cada arista del grafo
1

3

2

1

3

3

2

4
2

1

5

1

5

1

2
6

6
4

3
4

4

6

4

5

4

Encontrar el circuito hamiltoniano de coste total mínimo.

6

Ejemplos de Problemas de Optimización Combinatoria (2)

Problema del viajante de comercio (TSP)
Dado un grafo G=(V, E) un circuito hamiltoniano es un circuito (camino cerrado queno repite
ningún nodo) que pasa por todos los nodos.
Suponemos que tenemos un coste asociado a cada arista del grafo
1

3

2

1

3

3

2

4
2

1

5

1

5

1

2
6

6
4

3
4

4

6

4

5

4

Encontrar el circuito hamiltoniano de coste total mínimo.

6

Ejemplos de Problemas de Optimización Combinatoria (3)

Problema de caminos mínimos
Dadauna red N=(V, A) (grafo dirigido) y dos nodos s, t V
una función de coste c sobre los arcos de la red
Encontrar el camino de s a t de coste total mínimo

Ejemplo de formulación de un Problema de Camino de coste mínimo como
Problema de Optimización Combinatoria

Supongamos s=1, t=6

E={(1, 2), (1, 4), (1, 5), (2, 5), (2, 6), (4, 3), (3, 6), (5, 6)}
1

3

2

3
4

2

1

5...