Rilassamento lineare

Programmazione Lineare Intera

Programmazione Lineare Intera – p. 1/44

Programmazione Lineare Intera

Problema di PLI in forma standard:

max cx

Ax = b

x ≥ 0, x ∈ Iⁿ I → insieme degli interi.

Regione ammissibile:

Z_a = {x ∈ Iⁿ : Ax = b, x ≥ 0}, Insieme delle sue soluzioni ottime:

Z_ott = {x^∗ ∈ Z^a : cx^∗ ≥ cx ∀ x ∈ Z^a}.

Rilassamento lineare

Il rilassamento lineare di un problema di PLI è il problema di PL ottenuto dal problema di PLI omettendo la richiesta che le variabili siano intere, e quindi

max cx

Ax = b x ≥ 0

S_a e S_ott denotano rispettivamente la regione ammissibile e l’insieme delle soluzioni ottime del rilassamento lineare del problema di PLI.

Programmazione Lineare Intera – p. 3/44

Esempio

Problema di PLI:

max x₁ + x₂ x₁ + 2x₂ ≤ 4 2x₁ + x₂ ≤ 4

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

Rilassamento lineare:

max x₁ + x₂ x₁ + 2x₂ ≤ 4 2x₁ + x₂ ≤ 4

x₁, x₂ ≥ 0.

Relazioni tra i due problemi

Si ha che:

Z_a ⊆ S^a

e i due problemi hanno la stessa funzione obiettivo ^cx quindi:

Se S_a = ∅, allora Z_a = ∅.

Se _{∃ {xk}} tale che ^x_{k ∈ Za} per ogni k e cx_k → +∞ k → +∞,

(obiettivo del problema di PLI illimitato), allora é

illimitato anche l’obiettivo del suo rilassamento lineare.

Programmazione Lineare Intera – p. 5/44

Continua

Se S_ott 6= ∅ e Z_ott 6= ∅, allora dato ^x∗ _{∈ Sott} e ^z∗ _{∈ Zott}, si ha

z^∗ ∈ Z^ott ⇒ z^∗ ∈ Z^a ⇒ z^∗ ∈ S^a ⇒ cz^∗ ≤ cx^∗

cioè il valore ottimo del problema di PLI non puó essere superiore al valore ottimo del suo rilassamento lineare.

Se S_ott 6= ∅ contiene un punto ^x∗ a coordinate tutte

intere, allora ^x∗ _{∈ Zott} e i valori ottimi dei due problemi coincidono. Infatti:

x^∗ ∈ S^ott ⇒ cx ≤ cx^∗ ∀ x ∈ S^a ⇒ cx ≤ cx^∗ ∀ x ∈ Z^a x^∗ a coordinate intere _{⇒ x}^∗ _{∈ Za}

Esempio

max x₂

x₁ + 2x₂ ≤ 4 2x₁ + x₂ ≤ 4

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

Programmazione Lineare Intera – p. 7/44

Altri casi possibili

Z_a = ∅ ma S_ott 6= ∅

Z_a = ∅ ma l’obiettivo del rilassamento lineare é illimitato Se ^A, b e ^c contengono solo valori razionali, allora

Z_ott 6= ∅ implica S_ott 6= ∅. Se vi sono coefficienti irrazionali allora puó accadere che Z_ott 6= ∅ ma il rilassamento lineare ha obiettivo illimitato.

Esempi

max x₂

x₁ ≥ ¹₄ x₁ ≤ ³₄ x₂ ≤ 2

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

Programmazione Lineare Intera – p. 9/44

Esempi

max x₂

x₁ ≥ ¹₄ x₁ ≤ ³₄

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

max x₂

x₂ = √

2x₁

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

Un’importante osservazione

I problemi di PL sono in generale molto piú semplici e rapidi da risolvere dei problemi di PLI In particolare il rilassamento lineare di un problema di PLI é tipicamente molto piú facile da risolvere del problema di PLI stesso.

Programmazione Lineare Intera – p. 11/44

Metodi di risoluzione

Perché non risolvere il rilassamento lineare e poi

arrotondare a valori interi gli eventuali valori non interi nella soluzione ottima del rilassamento lineare?

Tale procedura é accettabile solo se i valori delle variabili sono elevati. In tal caso infatti l’arrotondamento introduce un errore relativo del tutto trascurabile.

É del tutto inaccettabile quando le variabili assumono valori piccoli (in particolare con le variabili binarie che assumono solo i valori 0 e 1)

Problema di PLI in forma standard

Si adottano le stesse regole già viste per i problemi di PL ma occorre prestare attenzione ad un ulteriore aspetto.

Un esempio:

max x₂

x₁ ≤ ¹₂ x₂ ≤ ¹₂

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

Programmazione Lineare Intera – p. 13/44

Continua

Con un problema di PL potremmo trasformarlo in forma standard con l’aggiunta di due variabili y₁ e y₂:

max x₂

x₁ + y₁ = ¹₂ x₂ + y₂ = ¹₂

x₁, x₂, y₁, y₂ ≥ 0, x¹, x₂ ∈ I.

Ma: ci ritroviamo con un problema in cui alcune variabili (x₁ e x₂) possono assumere solo valori interi e altre possono assumere anche valori non interi. Infatti, ad esempio, se

scelgo x₁ = x₂ = 0, valori ammissibili per il nostro problema di PLI, il corrispondente valore di y₁ e y₂ è pari a 1/2.

Il rimedio

Per fare in modo che anche le nuove variabili possano

assumere solo valori interi quando quelle originarie hanno valori interi, è sufficiente:

trasformare i vincoli in modo tale che in essi compaiano solo coefficienti e termini noti interi.

Programmazione Lineare Intera – p. 15/44

Nell’esempio

Nel nostro esempio basta moltiplicare entrambi i vincoli per 2:

max x₂

2x₁ ≤ 1 2x₂ ≤ 1

x₁, x₂ ≥ 0, x¹, x₂ ∈ I.

e solo a questo punto aggiungere le due variabili y₁ e y₂:

max x₂

2x₁ + y₁ = 1 2x₂ + y₂ = 1

x₁, x₂, y₁, y₂ ≥ 0, x¹, x₂, y₁, y₂ ∈ I.

Taglio valido

Sia ^x∗ una soluzione ottima del rilassamento lineare, che si suppone abbia almeno una coordinata non intera (se tutte le sue coordinate fossero intere allora ^x∗ _{∈ Zott}).

Definizione 1 Una disequazione ^wx _{≤ v} si definisce taglio valido per il problema di PLI se non é soddisfatta da ^x∗ ma é soddisfatta da tutti i punti nella regione ammissibile del problema di PLI, ovvero

wx^∗ > v, wx ≤ v ∀ x ∈ Z^a

Programmazione Lineare Intera – p. 17/44

Algoritmi di taglio

Inizializzazione Si risolva il rilassamento lineare

max cx

a_ix = b_i i = 1, . . . , m x_j ≥ 0 j = 1, . . . , n Se:

S_a = ∅, allora STOP con Z_a = ∅;

esiste una soluzione ottima, indicata con ^x∗1. Se ^x∗1 ha coordinate tutte intere, allora STOP: ^x∗1 _{∈ Zott}. Altrimenti si ponga k = 1 e si vada al Passo 1.

Continua

Passo 1 Si generi un taglio valido, ovvero una disequazione w_kx ≤ v^k tale che

w_kx^∗k > v_k w_kx ≤ v^k ∀ x ∈ Z^a

Programmazione Lineare Intera – p. 19/44

Continua

Passo 2 Si aggiunga il nuovo taglio valido ai vincoli originari del problema e ai tagli validi generati in precedenza e si risolva il problema di PL

max cx

a_ix = b_i i = 1, . . . , m w_rx ≤ v^r r = 1, . . . , k

x_j ≥ 0 j = 1, . . . , n Se:

il problema ha regione ammissibile vuota, allora STOP: Z_a = ∅.

Altrimenti sia ^x∗(k+1) la sua soluzione ottima. Se x^∗(k+1) ha coordinate tutte intere, allora STOP:

x^∗(k+1) ∈ Z . Altrimenti si ponga k = k + 1 e si ritorni

Nota bene

Il problema di PL con l’aggiunta dei tagli non é in forma

standard. Basta la semplice aggiunta di una variabile y_r ≥ 0 in ciascuno dei tagli per portarlo alla forma standard:

max cx

a_ix = b_i i = 1, . . . , m w_rx + y_r = v_r r = 1, . . . , k

x_j ≥ 0 j = 1, . . . , n y_r ≥ 0 r = 1, . . . , k

Programmazione Lineare Intera – p. 21/44

Tagli di Gomory

Sia data la base ottima B^∗ = {xⁱ¹, . . . , x_im} per il

rilassamento lineare del problema di PLI con la seguente riformulazione rispetto a tale base é la seguente:

max γ₀ + Pn−m

j=1 γ_jx_im+j x_i1 = β₁ + Pn−m

j=1 α_1jx_im+j

· · · x_ik = β_k + Pn−m

j=1 α_kjx_im+j

· · ·

x_im = β_m + Pn−m

j=1 α_mjx_im+j x₁, . . . , x_n ≥ 0

Ipotesi

Si suppone che almeno uno dei valori β_r, r = 1, . . . , m, sia non intero (se fossero tutti interi la soluzione di base

associata a B^∗ sarebbe non solo ottima per il rilassamento lineare ma anche per il problema di PLI).

Programmazione Lineare Intera – p. 23/44

Esempio

max ⁵₆x₁ − ¹³₃ x₄

5x₁ + 6x₃ − 8x⁴ = 12

−5x¹ + 30x₂ + 22x₄ = 150

x₁, x₂, x₃, x₄ ≥ 0, x¹, x₂, x₃, x₄ ∈ I.

Rilassamento lineare

Base ottima B^∗ = {x¹, x₂}

max 2 − x³ − 3x⁴

x₁ = ¹²₅ − ⁶₅x₃ + ⁸₅x₄ x₂ = ²⁷₅ + ¹₅x₃ + ²₅x₄

x₁, x₂, x₃, x₄ ≥ 0

Programmazione Lineare Intera – p. 25/44

Il taglio di Gomory

Sia β_k un valore non intero. Equazione relativa a x_ik (equazione generatrice del taglio):

x_ik = β_k + α_k1x_im+1 + α_k2x_im+2 + · · · + α^k,n−mx_in. Taglio di Gomory:

−f^k + f_k1x_im+1 + f_k2x_im+2 + · · · + f^k,n−mx_in ≥ 0 dove

f_kj, j = 1, . . . , n − m, é la mantissa di _−αkj, cioé f_kj = −α^kj − ⌊−α^kj⌋ ≥ 0,

f_k é la mantissa di β_k, cioé

f_k = β_k − ⌊β^k⌋ > 0. Programmazione Lineare Intera – p. 26/44

Esempio

Equazione generatrice del taglio:

x₁ = 12

5 − 6

5x₃ + 8 5x₄ Mantissa di ¹²₅ :

12

5 − ⌊12

5 ⌋ = 12

5 − 2 = 2 5 Mantissa di ⁶₅:

6

5 − ⌊6

5⌋ = 6

5 − 1 = 1 5

Programmazione Lineare Intera – p. 27/44

Continua

Mantissa di ₋⁸₅:

−8

5 − ⌊−8

5⌋ = −8

5 − (−2) = 2 5 Taglio di Gomory:

−2

5 + 1

5x₃ + 2

5x₄ ≥ 0

Continua

Per mantenere il formato standard, possiamo aggiungere una nuova variabile y₁ e riscrivere il taglio attraverso la seguente coppia di vincoli:

y₁ = −f^k + f_k1x_im+1 + f_k2x_im+2 + · · · + f^k,n−mx_in y₁ ≥ 0.

Programmazione Lineare Intera – p. 29/44

Nell’esempio

−2

5 + 1

5x₃ + 2

5x₄ ≥ 0 m

y₁ = −2

5 + 1

5x₃ + 2

5x₄ y₁ ≥ 0

Il taglio di Gomory è valido

La soluzione ottima del rilassamento lineare non soddisfa il taglio. Nella soluzione ottima del rilassamento lineare si ha:

x_im+1 = · · · = xⁱⁿ = 0

quindi, in corrispondenza della soluzione ottima del rilassamento lineare si ha:

y₁ = −f^k < 0.

Programmazione Lineare Intera – p. 31/44

Il taglio di Gomory è valido

Generico punto in Z_a:

x_i1, . . . , x_in

Sostituiamo le coordinate di tale punto nell’ equazione generatrice del taglio:

x_ik = β_k +

n−mX

j=1

α_kjx_im+j

e nel taglio di Gomory:

y₁ = −f^k +

n−mX

j=1

f_kjx_im+j

Continua

Si vuole dimostrare che il valore di y₁ é _{≥ 0} e cioé che la generica soluzione ammissibile in Z_a soddisfa il taglio. Ma prima dimostriamo che:

in corrispondenza di ogni punto in Z_a, il valore di y₁ ^{´e intero} Sommo membro a membro le due equazioni:

x_ik = β_k +

n−mX

j=1

α_kjx_im+j

e:

y₁ = −f^k +

n−mX

j=1

f_kjx_im+j

Programmazione Lineare Intera – p. 33/44

Continua

Dalla somma ho:

y₁ + x_ik = (β_k − f^k) +

n−mX

j=1

(α_kj + f_kj)x_im+j

−f^k + β_k = ⌊β^k⌋ f^kj + α_kj = −⌊−α^kj⌋ Quindi:

y₁ = ⌊β^k⌋ − x^ik −

n−mX

j=1

⌊−α^kj⌋x^im+j

Continua

y₁ ≥ 0 in corrispondenza di punti in Z_a

y₁ + f_k =

n−mX

j=1

f_kj

|{z}

≥0

x_im+j

| {z }

≥0

Quindi:

y₁ + f_k ≥ 0

e, per la interezza di y₁ e f_k < 1, abbiamo che deve essere y₁ ≥ 0.

Programmazione Lineare Intera – p. 35/44

Osservazione 1

Abbiamo dimostrato che la nuova variabile che viene introdotta (la y₁) assume sempre valori interi in

corrispondenza di ogni punto di Z_a. Quindi con l’aggiunta del taglio posso riscrivere il mio problema di PLI in questo modo:

max cx

a_ix = b_i i = 1, . . . , m y₁ = −f^k + Pn−m

j=1 f_kjx_im+j

x_j ≥ 0, x^j ∈ I j = 1, . . . , n y₁ ≥ 0, y¹ ∈ I

Nell’esempio

max ⁵₆x₁ − ¹³₃ x₄

5x₁ + 6x₃ − 8x⁴ = 12

−5x¹ + 30x₂ + 22x₄ = 150 y₁ = −²₅ + ¹₅x₃ + ²₅x₄

x₁, x₂, x₃, x₄, y₁ ≥ 0, x¹, x₂, x₃, x₄, y₁ ∈ I.

Programmazione Lineare Intera – p. 37/44

Continua

Quindi: dal momento che il nuovo problema con l’aggiunta del taglio é ancora un problema di PLI (tutte la variabili,

compresa la nuova, y₁, sono vincolate ad essere intere) possiamo iterare la procedura, cioé se dopo l’aggiunta del primo taglio la risoluzione del nuovo rilassamento lineare non ha coordinate tutte intere, possiamo generare un nuovo taglio utilizzando la stessa regola di generazione.

Osservazione 2

Il rilassamento lineare del problema di PLI dopo l’aggiunta del taglio non deve essere risolto da zero. Infatti, possiamo prendere la coppia di vincoli

y₁ = −f^k +

n−mX

j=1

f_kjx_im+j y₁ ≥ 0,

che esprime il taglio ed aggiungerla alla riformulazione

rispetto alla base ottima B^∗ del rilassamento lineare prima dell’introduzione del taglio.

Programmazione Lineare Intera – p. 39/44

Continua

max γ₀ + Pn−m

j=1 γ_jx_im+j x_i1 = β₁ + Pn−m

j=1 α_1jx_im+j

· · · x_ik = β_k + Pn−m

j=1 α_kjx_im+j

· · ·

x_im = β_m + Pn−m

j=1 α_mjx_im+j y₁ = −f^k + Pn−m

j=1 f_kjx_im+j x₁, . . . , x_n, y₁ ≥ 0

Continua

Questa è giá la riformulazione del nuovo rilassamento lineare rispetto alla base B^∗ ∪ {y¹}. Tale base è

non ammissibile per il primale (y₁ = −f^k < 0) ammissibile per il duale

Programmazione Lineare Intera – p. 41/44

Nell’esempio

Base B^∗ ∪ {y¹} = {x¹, x₂, y₁} ammissibile per il duale max 2 − x³ − 3x⁴

x₁ = ¹²₅ − ⁶₅x₃ + ⁸₅x₄ x₂ = ²⁷₅ + ¹₅x₃ + ²₅x₄ y₁ = −²₅ + ¹₅x₃ + ²₅x₄

x₁, x₂, x₃, x₄, y₁ ≥ 0.

Continua

Applicando il simplesso duale si arriva in una iterazione alla base ottima _{x1, x₂, x₃}:

max 0 − 5y¹ − x⁴

x₁ = 0 − 6y¹ + 4x₄ x₂ = 5 − y¹ + 3x₄ x₃ = 2 + 5y₁ − 2x⁴ x₁, x₂, x₃, x₄, y₁ ≥ 0

Soluzione ottima del rilassamento lineare e del problema di PLI:

x^∗₁ = 0 x^∗₂ = 5 x^∗₃ = 2 x^∗₄ = 0

Valore ottimo del rilassamento lineare e del problema di PLI

= 0

Programmazione Lineare Intera – p. 43/44

Osservazione 3

Se ad ogni iterazione il taglio di Gomory viene realizzato a partire dalla prima equazione con un termine noto β_k non intero, allora l’algoritmo termina in un numero finito di

iterazioni.