1.71 Esercizio. Si formuli il problema della partizione, con il vincolo aggiuntivo che uno dei due sottoinsiemi abbia una cardinalit` a ﬁssata, usando variabili 0-1.

(1)

1.71 Esercizio. Si formuli il problema della partizione, con il vincolo aggiuntivo che uno dei due sottoinsiemi abbia una cardinalit` a ﬁssata, usando variabili 0-1.

Soluzione.

max

n i=1

a

i

x

i

n i=1

a

i

x

i

≤

n i=1

a

i

/2

n i=1

x

_i

= k x

i

∈ {0, 1} ∀i

1.73 Esercizio. Si ammettano anche valori negativi nella deﬁnizione di un problema di knapsack. Come ci si pu` o ricondurre al caso di valori non negativi?

Soluzione. Se a

i

< 0 e b

i

≥ 0 `e svantaggioso scegliere l’oggetto i-mo e quindi in ottimalit`a si deve avere ˆ x

i

=0 (detto altrimenti, per ogni soluzione ammissibile con x

i

=1, la soluzione ottenuta cambiando x

i

in x

i

= 0 `e ammissibile di valore superiore). Di conseguenza tali variabili possono essere eliminate a priori.

Se invece b

_i

< 0 e a

_i

≥ 0 non `e svantaggioso scegliere l’oggetto i-mo e quindi in ottimalit`a si deve avere ˆ x

_i

=1 (detto altrimenti, per ogni soluzione ammissibile con x

_i

=0, la soluzione ottenuta cambiando x

_i

in x

_i

= 1 `e ammissibile di valore non inferiore). Di conseguenza tali variabili possono essere eliminate a priori.

Se b

_i

< 0 e a

_i

< 0 basta sostituire la variabile x

_i

con la variabile y

_i

= 1 −x

i

e il problema si riconduce al caso di coeﬃcienti non negativi.

Si noti inoltre che a

i

=0, b

i

≥ 0, implica ˆx

i

= 0 e b

i

=0, a

i

≥ 0, implica ˆx

i

1.71 Esercizio. Si formuli il problema della partizione, con il vincolo aggiuntivo che uno dei due sottoinsiemi abbia una cardinalit` a ﬁssata, usando variabili 0-1.

1.71 Esercizio. Si formuli il problema della partizione, con il vincolo aggiuntivo che uno dei due sottoinsiemi abbia una cardinalit` a ﬁssata, usando variabili 0-1.

Soluzione.

max

a

x

a

x

≤

a

/2

x

= k x

∈ {0, 1} ∀i

1.73 Esercizio. Si ammettano anche valori negativi nella deﬁnizione di un problema di knapsack. Come ci si pu` o ricondurre al caso di valori non negativi?

Soluzione. Se a

< 0 e b

≥ 0 `e svantaggioso scegliere l’oggetto i-mo e quindi in ottimalit`a si deve avere ˆ x

=0 (detto altrimenti, per ogni soluzione ammissibile con x

=1, la soluzione ottenuta cambiando x

in x

= 0 `e ammissibile di valore superiore). Di conseguenza tali variabili possono essere eliminate a priori.

Se invece b

< 0 e a

≥ 0 non `e svantaggioso scegliere l’oggetto i-mo e quindi in ottimalit`a si deve avere ˆ x

=1 (detto altrimenti, per ogni soluzione ammissibile con x

=0, la soluzione ottenuta cambiando x

in x

= 1 `e ammissibile di valore non inferiore). Di conseguenza tali variabili possono essere eliminate a priori.

Se b

< 0 e a

< 0 basta sostituire la variabile x

con la variabile y

= 1 −x

e il problema si riconduce al caso di coeﬃcienti non negativi.

Si noti inoltre che a

=0, b

≥ 0, implica ˆx

= 0 e b

=0, a

≥ 0, implica ˆx

=1.

1