Cifras

´ 6. PROGRAMACION ENTERA. 6.1. Introducci´n. o 6.2. M´todos de soluci´n. e o 6.3. Definiciones. 6.4. Soluci´n gr´fica. o a 6.5. Algoritmo de ramificaci´n y acotaci´n. o o 6.6. Programaci´n 0-1. o 6.7. Algoritmo de ramificaci´n y acotaci´n 0-1. o o

1

6.1. Introducci´n. o Modelo lineal con variables enteras. • Programaci´n entera mixta: algunas variables eno teras y otras continuas. •Programaci´n entera pura: todas las variables toman o valores enteros. • Programaci´n entera 0-1: todas las variables son o binarias. Ejemplo. El problema del agente viajero. Supongamos un viajante que debe visitar 5 ciudades una sola vez cada una de ellas y regresar a la primera. Se trata de determinar en que orden debe visitar las 5 ciudades para que el recorrido total sea m´ ınimo. La tabla de distanciases la siguiente.
C1 C1 C2 C3 C4 C5 0 40 85 130 70 C2 40 0 50 100 45 C3 85 50 0 50 35 C4 130 100 50 0 65 C5 70 45 35 65 0

Variables.

  0 xij =  1

C i → Cj C i → Cj
2

Ejemplo. Problema de producci´n. o
Horas A1 A2 A3 Disp. 30 20 60 4.500 Mat.Prima 40 30 40 5.500 Coste Prod. 60 40 80 Precio Venta 120 80 150

Costes de inicio: 2.000, 1.500 y 1.000 semanales. • xj : unidades que seproducen de Aj , j = 1, 2, 3.

  0 • yj =  1
Modelo entero.

si no se produce Aj si se produce Aj

max z = (120 − 60)x1 + (80 − 40)x2 + (150 − 80)x3 − −2.000y1 − 1.500y2 − 1.000y3 sujeto a 30x1 + 20x2 + 60x3 ≤ 4.500 40x1 + 30x2 + 40x3 ≤ 5.500 x1 ≤ M 1 y 1 x2 ≤ M 2 y 2 x3 ≤ M 3 y 3 x1 , x 2 , x 3 ≥ 0 y1, y2 , y3 = 0, 1
3

6.2. M´todos de soluci´n. e o 1. Enumeraci´n exhaustiva. o maxz = 80x1 + 45x2 sujeto a x1 + x 2 ≤ 7 12x1 + 5x2 ≤ 60 x1 , x2 ≥ 0 y enteras
12x1+5x2=60 x2

x1+x2=7

x1

max

N´mero finito de soluciones. u Conjunto de soluciones no convexo.
4

2. Enumeraci´n y aproximaci´n o o Prescindir de la restricci´n de enteras. o
12x1+5x2=60 x2

x1+x2=7

P = ( 3.6 , 3.4 )

x1

max

Aproximaciones: (3, 3), (3, 4) , (4, 3), (4, 4) 3. Ramificaci´n yacotaci´n o o Considerar aquellos problemas que puedan contener la soluci´n optima, y dividirlos en dos, quitando un o ´ trozo donde la soluci´n optima no est´. o ´ a Resolver dichos problemas.
5

6.3. Definiciones. Definici´n 1 Dado un problema entero (PE), se llama o problema relajado (PR) al mismo problema pero prescindiendo de la restricci´n de enteras. o PE max z = cT x sujeto a sujeto a PRmax z = cT x

Ax ≤ b x ≥ 0 y enteras
Observaciones. • PR infactible ⇒ PE infactible. • En otro caso, z ∗ ≥ z∗ . PR PE

Ax ≤ b x≥0

• PR no acotado ⇒ PE no acotado o infactible. Definici´n 2 Dado un problema entero, en cada iterao ci´n del proceso de resoluci´n llamamos soluci´n cano o o didata a la mejor soluci´n entera obtenida hasta el moo mento. o o ´ La soluci´n candidata puede sersoluci´n optima del PE. El valor de la funci´n objetivo para la soluci´n candidata o o fija una cota inferior, zI , para el PE.
6

6.4. Soluci´n gr´fica. o a
PE max z = 80x1 + 45x2 sujeto a x1 + x 2 ≤ 7 12x1 + 5x2 ≤ 60 x1, x2 ≥ 0 y enteras
12x1+5x2=60 x2

PR max z = 80x1 + 45x2 sujeto a x 1 + x2 ≤ 7 12x1 + 5x2 ≤ 60 x 1 , x2 ≥ 0

x1+x2=7

P=(3.6 , 3.4)

x1

max

x1

→

x1 ≤ 3,

x1 ≥4

7

Problema 2 max z = 80x1 + 45x2 sujeto a x1 + x 2 ≤ 7 12x1 + 5x2 ≤ 60 x1 ≤ 3 x1 , x 2 ≥ 0
12x1+5x2=60 x2 x1=3 x1=4

Problema 3 max z = 80x1 + 45x2 sujeto a x 1 + x2 ≤ 7 12x1 + 5x2 ≤ 60 x1 ≥ 4 x 1 , x2 ≥ 0

x1+x2=7

P=(3,4) Problema 2 P = (4 , 2.4 ) Problema 3
x1

max

Prob. 2: (x∗ , x∗ ) = (3, 4) → candidata → zI = 420. 1 2 Prob. 3: (x∗ , x∗ ) = (4, 2.4), 1 2 z ∗ = 428
8Problema 4 max z = 80x1 + 45x2 sujeto a x1 + x 2 ≤ 7 12x1 + 5x2 ≤ 60 x1 ≥ 4 x2 ≤ 2 x1 , x 2 ≥ 0
12x1+5x2=60 x2 x1=3 x1=4

Problema 5 max z = 80x1 + 45x2 sujeto a x 1 + x2 ≤ 7 12x1 + 5x2 ≤ 60 x1 ≥ 4 x2 ≥ 3 x 1 , x2 ≥ 0

x1+x2=7

Problema 5
x2=3 x2=2

P = ( 4.16 , 2 ) Problema 4
x1

max

Prob. 4: (x∗ , x∗ ) = (4.16, 2), 1 2 Prob. 5: infactible.

z ∗ = 422, 8 > 420 = zI .

9...