Esercizi Branch and Bound

Esercizi con il branch & bound

1. z = 6x₁ + x₂
2. x₁ + x₂ ≥ 2
3. -x₁ + x₂ ≤ 29
4. x₁ + 5x₂ ≥ 65
5. 2x₁ - x₂ ≥ 0

x₁ = 6 + x₂ = 2.75

x₁ + 5x₂ = 65

6 - 9x₁ + 5x₂ = 65

4x₂ = 9

x₂ = 2.2

z = 19.5

x₁ = 2.5

x₂ = 6.5

(x₁ ≥ 3)

27 + 5x₁ = 65

x₂ = 3.6

z = 18 + 36 = 21.6

x₁ ≤ 3

z = 18 + 6*4 = 22

Esercizi con il branch & bound

1. z = 6x₁ + x₂
2. x₁ + x₂ ≥ 6
3. -x₁ + x₂ ≤ 2
4. 9x₁ + 5x₂ ≥ 45
5. 2x₁ - x₂ ≥ 0

x₁ = 6, x₂ = 2.25

x₁ = 27.5, x₂ ≥ 2.5

9x₁ + 5x₂ = 65

54 - 9x₁ + 5x₂ = 65

x₁ = 27, x₂ = 27.5

x₂ = 3.6

z = 19.5

x₁ = 2.5

x₂ = 6.5

x₂ ≥ 3

8x₁ - 5x₂ = 45

x₁ = 22.3

S₁

S₂

S₂

x₂ ≥ 3

z ≤ UB

z = 18 + 36 = 27.5

x₃ = 22

x₂ = 3.6

2) Min z = 2x₁ + x₂

1. 5x₁ + 2x₂ ≥ 9
2. 2x₁ + 2x₂ ≥ 5
3. -x₁ + x₂ ≥ -1
4. x₁ ≥ 0 x₂ ≥ 0

interne

x₁ = 1

x₂ = 1.5

z = 2 + 1.5 = 3.5

x₂ ≥ 2

x₂ ≤ 1

x₁ ≤ 0.8

LB_x > UB → chiudo S_k

ub val + basso

3) Max z = -x₁ + 4x₂

-10x₁ + 20x₂ ≤ 27

5x₁ + 20x₂ ≤ 6

9x₁, x₂ ≥ 3

x₁ = 3

30 + 20x₂ ≥ 22 ⇒ x₂ = 52/20 - 2.6

(3, 2.6)

S₄

S₂

S₃

S₁

S₅ = 8.4

X₂ ≥ 3

Z = 6.2

X₁ = 1

Z = 16

X₁ = 2

X₁ = 0

Z = 6

-10x₁ = 20 - 40 = x₂

4) Max z = (4x₁ - x₂)

1. x₁ - 2x₂ = 2
2. x₂ = 3

2x = 3

0 = 0,7x - 3,6

(2 - 3,5 - 3)x, 2, 3, 5

Impossibile

5) Zaino binario

Max z = Σc_jx_j

Σp_ix_i ≤ p_max

Σx_i ≤ m_i

x_i ≥ 0

i: 1...n

Max z = 0

10x_A + 12x_B + 5x_C + 5x_D + 9x_E

5x_A + 8x_B + 6x_C + 2x_D + 7x_E ≤ 14

x_i = {0/1}

Ap_i: 5

v: 10

B812

C65

D22

E791.5

0.9

3.5

1.29

P2

A5

B8

E7

C6

J/p3.5

2

1.5

1.29

0.9

S₀

K_D=1, K_A=1, K_B=1/2, Q.P=5, K_F=0, K_C

z=7+10+10.5=27.5

K_B=0

K_B=0, K_D=1, x_A=1, x_E=1

K_E=0

z=7+10+9.26

03^a parte: Dite Docendo: qual` è la dimensione

minimo di vincoli a numero di vertici

x un problema DI max flusso con 20 vertici

x 100 archi.

6) Zaino binario

A Es. 7

Max z = ∑_j=1^m c_jx_j

∑_j=1^m p_jx_j ≤ b

x_j ≤ m_j

x_j ≥ 0 int.

Max z = ∑_j=1^m c_jx_j

∑_j=1^m p_jx_j ≤ b

x_j {0,1}

j=1-m

peso

val.

val/peso

A1002002

B503504

C501503

D201005

Ordine rispetto a val/peso:

B50350

D20100

C50150

A100200

Max z = 200 x_A + 350 x_B + 150 x_C + 100 x_D

100 x_A + 50 x_B + 50 x_C + 20 x_D ≤ 200

x_j{0,1}

best-first

x_B=1

x_D=1

x_C=0

x_A=0

Z=450

S₀

x_B=1

x_D=1

x_C=3/5=0.6

x_A=0

Z=350+10c+90=540 <Z_s

S₂

x_C=1

x_D=0

x_B=0

x_A=1

Z=500

ottimo

x_A=0

x_C=0

x_B=1

Z=450

Il candidato

all'ottimo

x_A=1

x_B=0

x_C=0

x_D=-

Z=200

8) Zaino intero

Es. zaino

capacità zaino di 45

2 prodotti disponibili da 4 e 5 unità

AV PB K

A 10 5 4

B 30 10 5

Modello dello zaino intero

Max z = 10x_A + 30x_B

Vincoli di peso: 5x_A + 10x_B ≤ 45

Vincoli di disponibilità: x_A ≤ 4

x_B ≤ 5

x_A, x_B ≥ 0 intero

Dualità grafica e B & B

z = 40 + 30·2.5 = 415

x_B = 2

x_A = 4

z = 100 = LB

x_B = 3

x_A = 3

z^* = 120

9) Zaino binario

Es. zaino A e B

Max z = Σv_ix_i

Σp_ix_i ≤ p_max

0 ≤ x_i ≤ di

x_i p_i v_i p_i/v_i

A 10 5 8

B 20 6 5

C 15 3 4

D 6 6 14 vertici -> 16 sol.

Ordinamento su v_i/p_i

B 20 €/g 5

C 15 3 4

A 10 5 2

D 6 6 1

Sup. che p_max = 11

S₃

x_B = 1

x_C = 1

x_A = 0

x_D = 0

z* = 40 - 45

S₂

S₁₂

x_D = 0

z = 30

S₂₂

z = 33

S₂₂

z = 33

x_B = 1/3 = 0.3

x_C = 1/3 = 0.9

x_D = 1/3 = 0.1

z = 30

S₂

z = 30.3

S₂₂

1 z = 23.9

ottimo con L.P. = 45